5. Virtualization) CPU Scheduling

이전에 process를 virtualization하기 위해서는 low-level machinery mechanism과 high-level intelligence가 필요하다 했고,

앞선 글에서 context switch등 low-level mechanism들에 대해서 알아보았다.

이제는 OS Scheduler를 위한 scheduling policies 혹은 disciplines를 알아보자.

 

우리는 scheduling policies를 점차적으로 개선해나가며 공부할 것이다. 

하지만 스케줄링 정책을 만드는 것에 있어서 workload는 굉장히 중요한 부분이고 원활한 예시를 위해 몇가지 가정을 둘것이다.

(물론 실제로 이 가정은 매우매우 비현실적이지만 공부를 위한것이다..)

Workload Assumptions

1. Each job runs for the same amount of time

2. All jobs arrive at the same time

3. Once started, each job runs to completion

4. All jopbs only use the CPU(ex. they perform no I/O)

5. The run-time of each jop is known

 

Scheduling metrics : turnaround time

또 여러 scheduling policy를 비교하기 위한 공식이 필요하고 여기서는 turnaround time으로 performance를 측정할 것이다.

Workload Assumption 2번에서 모든 jop은 같은 시작에 도착한다고 가정했으므로 T(arrival)=0이고 결국 T(turnaround)=T(completion)이다.

 

First In, First Out (FIFO)

가장 기본적인 알고리즘은 FIFO스케줄링이다. 먼저 도착한 것이, 먼저 실행되는 알고리즘이다

7.1의 예를 보자. A,B,C의 job은 workload가정에 따라 모두 동시에 도착했고 10초씩 실행되고 종료된다.

FIFO스케줄링에서 A는 10초, B는 20초, C는 30초에 종료되었고 평균 turnaround time은

(10+20+30)/3 = 20초이다.

 

7.1 예시에서는 성능이 괜찮아 보인다. 하지만 이제 workload 가정 1번을 없애보자.

더 이상 각 job들이 같은 시간 동안 실행되지 않는다.

7.2에서는 A의 실행 시간이 100초에 달한다. 가장 최악의 경우 A가 제일 먼저 실행된다고 하면

평균 turnaround time은 (100+110+120)/3=110초이다. 효율이 굉장히 떨어진다..

7.2의 예시에서 보이듯, 상대적으로 자원의 소비가 짧은 소비자들이 heavyweight한 소비자들에게 밀려 대기하는 현상을 convey effect라고 한다.

 

그렇다면 각 job마다 실행 시간이 다를 때 어떻게 더 좋은 알고리즘으로 발전시킬 수 있을까?

 

Shortest Job First (SJF)

Shortest Job First, 이름 그대로 가장 짧은 job부터 실행하는 것이다.

예시 7.2에서 FIFO를 통해 실행했을 때의 성능에 비해 SJF를 통해 스케줄링 하면 평균 turnaround time을 110초에서 (10+20+120)/3=50초까지 줄일 수 있다. 

모든 job들이 동시에 도착해서 가장 짧은 것 부터 실행할 수 있는 것은 매우 좋아보이지만, 모든 job이 동시에 도착하는 것은 매우 비현실적인 일이다.

 

이제 workload 가정 2번을 없애보자. 더 이상 각 job들은 동시에 도착하지 않는다. 제각각 도착한다.

A는 0초에 도착해서 100초 동안 실행되고, B와 C는 10초에 도착해서 10초씩 실행된다.

결국 A가 먼저 도착했기 때문에 B,C는 A의 수행을 모두 기다려야 하고,

SJF스케줄링 또한 FIFO때와 마찬가지로 convey effect가 발생한다.

평균 turnaround time은 (100+(110-10)+(120-10))/3 = 103.33초이다.

 

그렇다면 각 job이 도착하는 시간이 다를 때 어떻게 더 좋은 알고리즘으로 발전시킬 수 있을까?

지금까지 알아본 스케줄러 방식(FIFO, SJF)들은 non-preemptive 스케줄러이다.
실행하는 job이 다 실행될 때까지 다른 job을 실행하지 않는다. 즉, context switch를 하지않는다.
반대로 preemptive 스케줄러는 context switch를 수행하여 다른 프로세스를 실행하기 위해 현 프로세스를 멈출 수 있다.

 

Shortest Time-to-Completion First (STCF)

7.4에서의 문제를 해결하기 위해 workload 가정 3번을 없애겠다.

이제 timer interrupt를 통해 context switching을 할 것이다.

STCF는 preemptive 스케줄러이고 Preemtive Shortest Jop First (PSJF)라고도 부른다.

새로운 job이 도착하면 남아있는 job들 중 가장 적은 시간이 걸리는 것을 실행하는 것이다.

7.5에서 A가 먼저 도착했고 A를 가장 먼저 실행한다. 도중에 B와 C가 도착하고 STCF는 남아있는 A,B,C 중 가장 빨리 끝나는 B로 context switch를 해 실행하고 그 후 가장 짧은 C, 마지막으로 A를 실행한다.

결과적으로 평균 turnaround time은 (120+(20-10)+30-10)/3=50초이다.

이렇듯 preemitive스케줄러를 통해 convey effect에서 벗어날 수 있다.

 

A New Metric : Response Time

이때까지 turnaround time을 기준으로 성능을 측정했고 이 기준에서 STCF는 매우 좋은 스케줄러이다.

하지만 옛적의 batch computing system때면 몰라도 요즘날의 상호작용적인 시스템에서 turnaround time만을 기준으로 삼기에는 문제가 있다. 그러므로 요즘날의 time shared machine은 새로운 기준이 필요하다.

바로 response time이다. 

T(response)는 job이 시스템에 도착한 시점에서 처음 실행되기까지 걸리는 시간이다.

 

자 이제 새로운 metric을 가지고 7.5의 예시를 다시 보자.

평균 response time을 구하면 (0+0+10)/3=3.33초이다. 생각해봐도 STCF와 관련된 스케줄러들은 오래걸리는 job들은 뒤로 밀릴테니 response time에 좋은편은 아니다. A,B,C가 동시에 도착했다고 가정하면 A는 B,C의 작업을 다 기다려야 하므로 response time은 더 길어질것이다.

job들의 완료까지 걸리는 시간을 측정하는 turnaround time도 중요하겠지만, I/O작업이 활발한 상호적인 요즘 시스템에서 타이핑 하나에 반응하는데 10초의 시간이 걸린다 생각하면 참 답답하다.

그러므로 여기서 고민이 생긴다. 어떻게 response time에 sensitive하도록 스케줄러를 설계할 수 있을까?

 

Round Robin (RR)

response time을 해결하기 위해 Round-Robin스케줄러가 있다.

Round Robin이란 하나의 job을 완료때까지 실행하는 것이 아닌, 각 job들을 time slice동한 실행하고 switch를 한 후 다음 job을 실행하는 것이다. 모든 job들이 완료될 때까지 time slice마다 switch를 한다.

그래서 round robin을 time-slicing이라고 부르기도 한다.

(무조건 time slice의 길이는 timer-interrupt주기의 배수가 되어야한다.)

 

예시를 통해 알아보자. 3개의 job이 있고 A,B,C는 동시에 도착하며 각각 5초씩 실행된다. round robin의 time slice는 1초이다.

이 예시를 SJF와 Round Robind으로 평균 response time을 계산해봤을때, SJF의 평균 response time은 (0+5+10)/3=5초,

round robin의 평균 response time은 (0+1+2)/3=1초이다.

확실히 round robin이 response time에 탁월한 것을 알 수 있다.

 

또 round robind의 response time을 결정하는데 time slice값이 중요한 것을 알 수 있다.

time slice가 짧을수록 response time이 매우 좋아지겠지만, time slice때마다 발생하는 context switch의 cost는 공짜가 아니다!

context switch를 할때마다 발생되는 OS 동작(register들을 저장하고 복구)들은 성능에 영향을 미친다. 

이뿐만이 아니라 프로그램이 실행될때 생성되는 CPU caches, TLBs, branch predictors등등 다른 것들 또한 큰 performance cost를 갖고있다.

 

우선 round robin이 최적의 time slice값을 가지고 있다면 response time에 좋은 것은 분명하다. 하지만 turnaround time측면에서는 어떨까?

7.7의 turnaround time을 계산해 보면 A는 13초, B는 14초, C는 15초로 평균은 14초이지만... 끔찍하다.

그렇다. round robin을 turnaround time측면에서는 성능이 좋은 편은 아니다.

 

일반적으로 round robin같이 fair한 스케줄러는 cpu를 매우 작은 time조각으로 나눠 사용하므로 turnaround time같은 metric들에 좋지 않은편이다. 이렇듯 turn around time과 response time은 trade-off관계이다.

(여기서 fair 공평하다는 것은 어느 job하나 불공평하게 실행이 미뤄지지 않고 실행되는 것을 말한다.)

 

결국 STCF와 Round Robin은 상반된 장단점을 갖고있다. 하지만 아직 4,5번 가정들을 다루지 않았다!

Incorporating I/O

workload 가정 4번을 없애겠다. 대다수 프로그램이 그렇듯 이제 I/O가 발생한다.

I/O요청이 발생했을 때, 해당 job은 I/O동안 CPU를 사용하지 않기 때문에 스케줄러들은 해당 job을 block하고 I/O이벤트가 완료될 때까지 기다린다. I/O요청이 완료되면 interrupt가 발생되고 OS가 해당 프로세스를 block상태에서 ready상태로 변경한다.

이때 OS는 각 job들을 어떻게 처리해야할까?

 

예시를 하나 들보자. 2개의 job A,B가 있고 각각 50초씩 CPU를 필요로한다. 하지만 A는 10초 실행될때마다 I/O요청이 발생되고 I/O작업이 처리되는데 10초가 소요된다. 반면 B는 I/O요청이 발생하지 않는다.

7.8처럼 A를 실행하고 B를 실행하는  방법이 있지만 I/O요청동안 CPU를 낭비하게 되므로 매우 비효율적이다.

더 일반적인 접근은 I/O작업을 하는 각 10초동안의 job을 독립된 sub job으로 바라보는 접근이다.

7.9를 보면 이 설명을 더 잘 알 수 있다. 시스템이 시작할 때 스케줄러는 10초의 시간이 걸리는 A와 50초가 걸리는 B job을 갖고있다.

STCF로 예를 들면, 가장 먼저 A가 선택되고 A가 완료된다. A가 완료 되었을때 스케줄러는 다음 선택지로 B만 남아있고 B를 실행한다.

B의 실행 도중 A의 sub job이 완료되고, A는 B보다 선제권을 얻어 다시 10초동안 실행된다.

이 과정을 통해 A가 I/O작업을 기다리는동안 다른 프로세스가 CPU를 사용할 수 있고 이는 더 효율적이다.

 

스케줄러는 바로 이런 방식으로 I/O작업을 포함한 job들을 처리하게 된다.

 

자 이제 마지막 문제가 남아있다. "5. The run-time of each jop is known"

OS가 각 job이 얼마동안 실행될지 아는것은 터무니 없는 일이다.

하지만 이런 사전 정보 없이 어떻게 OS가 SJF/STCF처럼 스케줄 할 수 있을까?

그리고 이때까지 본 아이디어를 어떻게 round robin스케줄러 방식에 통합할 수 있을까?

이에 대해선 다음에 알아보도록 한다!