</>PatchNote
목록으로

2023-04-23

운영체제 #4 — CPU 스케줄링

Operating SystemOS 2023Scheduling

CPU 스케줄링은 지금 CPU 자원을 수행 중인 프로세스 중 누구에게 줄 것인지를 결정하는 것이다. 프로세스 스케줄링(프로세스들의 상태를 바꿔주는 것)과는 좀 다르다. 그중에서도 특히 어떤 프로세스를 running 상태로 바꿔줄 것인가를 의미한다. short-term scheduler다.

CPU burst

모든 프로그램은 CPU로 일하다가 I/O를 발생시키고를 반복한다. alternating sequence다. 단, 얼마나 자주 바뀌는지는 프로그램마다 다르다.

한 번 잡으면 얼마나 오래 쓰는지를 x축, CPU를 잡는 빈도를 y축으로 두고 프로그램 하나당 점을 찍으면 hyperexponential distribution이 나온다. 여기서 두 부류가 갈린다.

  • CPU bound job — CPU를 잡는 횟수는 적지만 한 번 잡으면 오래 쓴다. 계산 위주.
  • I/O bound job — CPU를 잠시 썼다 다시 내놓는다. 에디터 같은 것.

이걸 구분하는 이유는 CPU를 누구에게 줄지 선택해야 하기 때문이다. 사용자와 interaction이 많은 프로그램에는 CPU를 빨리빨리 줘야 사용자의 action이 바로바로 반영되어 불만이 적다. 그래서 원칙은 I/O bound job에 CPU를 먼저 주자가 된다. 이 원칙에 따라 알고리즘들이 만들어진다.

스케줄링은 언제 일어나나

  1. running하다가 waiting이 되었을 때(I/O를 발생시켰을 때).
  2. running에서 ready로 갈 때(timer interrupt). 할당된 시간이 끝나 강제로 CPU를 빼앗아 ready queue에 넣는 경우다. 멀티프로그래밍 환경에서만 일어난다.
  3. 지금 실행 중이 아닌 프로세스가 waiting에서 ready로 갈 때. 이게 처음에는 왜 CPU와 상관있는지 몰랐다. waiting queue에 있는 프로세스에 대해 인터럽트가 오면 CPU가 interrupt handling을 해야 한다. 그리고 handling이 끝나면 아까 실행 중이던 프로세스로 반드시 돌아가야 하느냐 하면 아니다. 보장되지 않는다. 실행 중이던 프로세스는 ready queue로 가고, handling이 끝나면 그때 다시 CPU 스케줄링으로 받을 프로세스를 고른다. 약간 불공평하긴 하다.
  4. running 중인 프로세스가 terminate되었을 때. CPU가 비니 골라야 한다.

1번과 4번은 자발적으로 CPU를 내놓는 경우라 non-preemptive, 2번과 3번은 강제로 빼앗는 경우라 preemptive다.

dispatcher

스케줄링이 일어나면 dispatcher module이 구동된다. context switching을 하는 녀석이다. 현재 돌고 있는 프로세스의 상태를 저장하고, 선택된 프로세스의 예전 상태를 CPU 레지스터에 다시 로드해서 이어서 실행할 수 있게 한다. dispatcher는 커널 코드이므로 다시 유저 코드를 실행하는 모드로 바꿔주고(kernel → user), 프로그램이 중단되었던 위치로 점프한다. 이 과정에서 대부분의 시간이 context switching에 들어간다.

성능 지표

  • CPU utilization — 스케줄링 알고리즘은 CPU를 놀지 않게 만들려고 만드는 것이니 이게 높아져야 한다.
  • Throughput — 단위 시간당 종료시키는 프로세스의 개수. 최대화.
  • Turnaround time — 프로세스가 시작한 뒤 끝날 때까지 걸리는 시간. 최소화.
  • Waiting time — 프로그램이 ready 상태에서 기다리는 시간. (waiting 상태가 아니다.)
  • Response time — 프로그램을 시작했을 때 첫 응답이 나올 때까지 걸리는 시간. 사용자에게 interactivity를 느끼게 해주는 시간이다. 메신저에서 ㄱ을 눌렀을 때 화면에 나오기까지 걸리는 시간을 생각하면 된다. 짧을수록 즉각적이라고 느낀다.

이 중 가장 중요한 건 CPU utilization과 waiting time이다. CPU가 놀지 않게 하는 것과, 프로세스가 ready queue에서 기다리는 시간을 짧게 만드는 것.

FCFS

First Come First Served. 먼저 들어온 프로세스에게 준다. 가장 기본적으로 떠오르는 방식이고 CPU 스케줄링이 아닌 다른 곳(DB 등)에서도 많이 쓴다.

장점은 fairness다. 실생활에서 가장 많이 쓰이는 이유이기도 하고, fairness가 가장 좋은 알고리즘이다. 하지만 fairness를 제외한 나머지에서는 단점이 많다.

burst time이 24, 3, 3인 세 프로세스가 거의 동시에 도착했다고 하자. 1, 2, 3 순서면 average waiting time은 (0 + 24 + 27) / 3 = 17이다. 그런데 2, 3, 1 순서면 (0 + 3 + 6) / 3 = 3이다. 간발의 차이로 엄청난 차이가 생긴다.

원인은 convoy effect(호위병 효과)다. 날쌘 호위병들이 느린 왕 때문에 천천히 갈 수밖에 없다. burst time이 긴 프로세스가 먼저 도착하면 짧은 프로세스들이 오래 기다린다. 뒤집어 생각하면, 순서를 약간만 조정해도 waiting time을 대폭 줄일 수 있다는 뜻이다. 여기서 여러 알고리즘이 나온다.

SJF와 SRTF

날쌘 놈을 앞으로 보내자. 각 프로세스가 CPU를 잡으면 얼마나 쓸지 미리 예측해서, burst time이 짧을 프로세스에게 먼저 준다.

두 가지 방식이 있다. 실행 중인데 더 짧을 것 같은 프로세스가 들어왔을 때,

  • Non-preemptive (SJF) — 실행 중인 프로세스가 끝날 때까지 기다린다.
  • Preemptive (SRTF, Shortest Remaining Time First) — 강제로 CPU를 넘긴다.

SJF는 optimal이다. 이보다 더 좋은 방법은 존재하지 않는다. 정확히 말하면 waiting time을 가장 짧게 만드는 알고리즘은 preemptive 버전인 SRTF다.

같은 입력에 대해 non-preemptive SJF는 average waiting time 4가 나오고, SRTF는 3이 나온다. SRTF의 waiting time은 (처음 온 시간부터 끝날 때까지) - burst time으로 계산한다.

burst time을 어떻게 아는가

모른다. estimate밖에 할 수 없다. exponential averaging을 쓴다.

tau(n+1) = alpha * t(n) + (1 - alpha) * tau(n)

t는 실제값, tau는 예측값, alpha는 가중치다. n+1번째 CPU burst를 예측할 때 직전 실제값과 직전 예측값을 쓴다.

  • alpha = 0이면 직전 history를 반영하지 않는다. 과거 전체의 평균을 보겠다는 뜻.
  • alpha = 1이면 바로 직전 값만 쓴다.

식을 풀어쓰면 과거 실제 데이터가 모두 포함되어 있는데, alpha와 1-alpha가 1보다 작으므로 오래된 값일수록 점점 반영이 안 된다. alpha * (1-alpha)^n * t(n) 꼴이기 때문이다. 그래서 tau(n+1)을 계산할 때 tau(n)을 쓰는 것으로 충분하다.

alpha가 크면 최근 값을 많이 반영하고 과거는 조금 반영한다(skewness가 크다). alpha가 작으면 과거 데이터가 비교적 공평하게 반영된다.

실제로 잘 맞을까? CPU burst가 단조 증가하거나 감소하는 프로그램이라면 alpha가 클수록 잘 맞는다. 반대로 burst가 왔다 갔다 하면 alpha가 클 때 아주 잘못된 예측이 나올 수 있다.

Priority Scheduling

이건 사실 알고리즘이 아니라 fallacy다. priority를 무엇으로 설정하느냐에 따라 하나의 알고리즘이 만들어지는 형태다. priority를 next burst time으로 설정하면 그게 곧 SJF다. "priority scheduling"이라는 말만 가지고는 어떻게 스케줄링하는지 알 수 없다.

기본은 우선순위가 높은 프로세스에게 CPU를 먼저 주는 것이다. 실시간성이 강한 프로세스에 우선순위를 높게 주는 식으로 쓴다. 단독으로 쓰기보다 다른 방식과 섞어서 우선순위까지 고려한 스케줄링으로 쓰는 경우가 많다. priority 방식으로 동작하는 알고리즘은 모두 preemptive와 non-preemptive 두 가지가 있다.

문제는 starvation이다. 우선순위가 낮은 프로세스가 계속 밀려서 영영 실행되지 않을 수 있다. 해결은 aging이다. 오래 ready 상태일수록 우선순위를 점점 올린다. 다만 starvation을 완화할 뿐이다. starvation과 aging은 항상 쌍으로 묶인다.

Round Robin

기본 철학은 FCFS인데, 각 프로세스가 CPU를 잡았을 때 쓸 수 있는 시간의 한계를 정한다. 그 한계를 time quantum이라고 한다.

  • 시간 내에 안 끝났어도 반드시 CPU를 반납하고 ready queue로 들어간다.
  • I/O를 발생시키거나 terminate되면 시간을 다 쓰지 않아도 넘겨준다.
  • time quantum은 최대 시간이지 보장 시간이 아니다.
  • 프로세스마다 다른 quantum을 갖는 게 아니라 모두 같은 값을 갖는다.

장점은 기다리는 시간에 upper bound가 생긴다는 것이다. FCFS는 CPU를 잡으면 I/O나 종료 전까지 계속 쓰니 뒤에 있는 프로세스는 언제까지 기다려야 할지 모른다. RR에서는 앞의 프로세스들이 각각 q 이하만 쓰므로 (n-1)q 이하만 기다리면 된다. upper bound가 존재한다는 건 알고리즘의 가치를 크게 높인다. 그에 맞춰 계획적인 일을 할 수 있게 되기 때문이다.

문제는 q를 어떻게 정하느냐다. q가 크면 FCFS와 비슷해져서 효과가 없어지고, q가 작으면 스케줄링이 너무 자주 일어나 context switch 오버헤드가 부각된다.

애초에 왜 이런 방식을 생각했을까. 멀티프로그래밍 때문이다. FCFS나 SJF를 쓰면 CPU를 잡았을 때 I/O를 발생시키거나 종료하기 전까지 놓지 않는다. CPU bound job이 한 번 잡아버리면 뒤에 있는 프로세스는 전혀 진도를 못 나간다. 멀티프로그래밍의 효과가 사라진다. 그래서 조금 쓰고 반납하게 해서 전부 조금씩 나아가게 한다. 대부분의 운영체제는 RR을 기반으로 우선순위를 결합하거나 다른 방식을 추가한 혼합 방식으로 스케줄링한다.

turnaround time은 SJF보다 좋지 않다. 한 번 잡으면 끝날 때까지 쓰는 방식이 아니라 돌아가면서 쓰니 끝날 때까지 꽤 오래 걸린다. 대신 response time은 upper bound가 있으니 평균이 짧다. SJF는 앞에 burst time이 긴 프로세스가 있으면 response time이 매우 길어진다.

주의 — time quantum은 timer interrupt와는 상관없는 개념이다.

I/O bound job에 우선순위를 주려면

원칙은 I/O bound job에 CPU를 빨리 주는 것이었다. 각 알고리즘을 그 기준으로 보면:

  • FCFS — 전혀 고려하지 않는다.
  • SJF — CPU bound와 I/O bound를 명시적으로 구분하진 않지만 효과는 있다. burst time이 적은 프로세스부터 CPU를 받는데, 그게 I/O bound job의 특징이다.
  • Round Robin — 반영되어 있지 않다. 멀티프로그래밍에 필수적이지만 이것만으로는 I/O bound job에 우선순위를 주는 정책을 쓸 수 없다. RR을 바탕으로 다른 것과 결합해야 한다.

Multilevel Queue

Ready queue를 하나가 아니라 여러 개 둔다. 예를 들어 foreground는 RR로, background는 FCFS로 돌린다. 그런데 이러면 CPU bound job이 많은 background가 오래 잡고 있어서 foreground가 불리해진다. 그래서 큐 간의 스케줄링을 한다.

  • Fixed priority scheduling — foreground가 다 끝나야 background에 CPU를 준다. 확실히 I/O bound job에 우선순위를 줄 수 있지만, interactive job이 남아 있으면 CPU bound job은 아예 일을 못 한다. starvation이 심각해진다.
  • Time slice — 한쪽 큐에 몰빵하지 말고 시간을 비율로 나눠 쓴다. CPU bound job도 조금씩 나아가면서 I/O bound job에 우선순위도 줄 수 있다.

Multilevel Feedback Queue

Multilevel queue의 문제는 처음에 프로세스가 I/O bound인지 CPU bound인지 알 수 없다는 것이다. 모르니까 아무 데나 집어넣고, 나중에 알게 되었을 때 다른 큐로 옮기면 된다.

프로세스가 CPU를 사용하는 형태를 보고 그 형태에 대한 feedback을 받아 어느 큐로 옮길지 결정하는 알고리즘이 MLFQ다. 처음에는 아무 생각 없이 첫 번째 큐에 넣고, 구분이 되면 옮긴다.

MLFQ 하나를 정의하려면 네 가지를 정해야 한다.

  1. 큐의 개수
  2. 각 큐 내부의 스케줄링 알고리즘
  3. 하위 큐에서 상위 큐로, 또는 반대로 이동할 수 있는 조건
  4. 프로세스가 처음에 어느 큐로 들어가는지

수업에서 본 형태는 큐 간 이동 조건을 "그 큐에서 정한 time quantum 안에 끝내지 못했다면 다음 큐로 넘어간다"로 정했다. I/O bound job은 상위 큐에서 대부분 끝나므로 원칙을 반영했다고 볼 수 있다.

time quantum이라는 말 자체가 Round Robin 정책에서 나온 말이다. 즉 위쪽 큐들은 Round Robin이다.

이 MLFQ를 xv6에 직접 구현하는 게 Project 1이었다. #7에서 다룬다.

실시간 시스템

실시간 시스템에는 deadline이라는 개념이 있다. 이 시간 안에 반드시 끝나야 한다는 걸 보장한다. 미사일 같은 게 hard real time system이고, real time scheduler가 들어가야 한다.

반드시는 아니지만 deadline을 지켜줬으면 좋겠는 경우도 있다. 동영상 같은 것이고 soft real time computing이라고 한다. 이런 job에 우선순위를 높게 주는 방식이며, 우리가 쓰는 운영체제에도 대부분 들어가 있다.