Chapter 5 (CPU Scheduling)

Basic Concepts

CPU의 효율을 높이기 위해 우리는 multiprogramming을

사용합니다.

그러나 CPU가 1개이면 오직 1개의 process만

작동할 수 있습니다.

이는 CPU scheduling이 필요합니다.

process는 CPU burst와 I/O burst를 왔다갔다 하면서

프로그램을 실행합니다.

CPU burst는 cpu 명령을 실행하는 것이고

I/O burst는 i/o를 요청한 다음 기다리는 시간입니다.

 

process는 CPU bound process와 I/O bound process

로 나눌 수 있습니다.

CPU burst가 큰 process가 CPU bound process

I/O burst가 큰 process를 I/O bound process

라고 합니다.

 

우리가 대부분 사용하는 많은 프로그램들은 CPU burst가 I/O burst보다 작습니다.

따라서 많은 process 대부분이 I/O bound process입니다.

 

CPU Scheduler

cpu 스케줄러는 메모리에 있는 여러 process들 중 하나를 고르는 것을 말합니다.

cpu 스케줄링 결정은 아래 4가지 상황에서 발생할 수 있습니다.

1. process가 running state에서 waiting state로 전환할 경우(wait을 호출할 때)

2. process가 running state에서 ready state로 전환될 경우(interrupt가 발생할 때)

3. process가 waiting state에서 ready state로 전환 될 경우(completion of I/O)

4. process가 종료될 경우

 

1과 4의 경우에서만 스케줄링이 발생하면 non-preemptive(비선점) 또는 cooperative(협조적) 합니다.

비선점 스케줄링에서는, 일단 CPU가 한 process에 할당되면 process가 종료하든지 또는 

waiting state로 전환해 CPU를 방출할 때 까지 CPU를 점유합니다.

즉, process가 스스로 다음 process에게 자리는 넘겨주는 방식입니다.

 

나머지의 경우는 스케줄링이 preemptive(선점)형 일 수 있습니다.

선점형 스케줄링은 data가 다수의 process에 의해 공유될 때 race condition을 발생시킬 수 있습니다. 

즉, OS가 강제로 process의 사용권을 통제하는 방식입니다.

CPU에 process가 할당되어 있을 때도 OS가 개입해 다른 process에게 CPU를 할당할 수 있습니다.

 

Dispatcher

cpu 스케줄러는 Ready queue에 있는 process들을 고른다고 하면

dispatch는 cpu 스케줄러가 고른 process를 cpu에 올리는 것을 의미합니다.

크게 보면 CPU 스케줄링 기능에 포함된 요소입니다.

dispatcher는 아래와 같은 작업을 수행합니다.

1. switching context

2. user 모드로 전환

3. 프로그램을 다시 시작하기 위해 user program을 적절한 위치로 이동시킴

 

dispatcher는 모든 process의 switching시에 호출 되므로, 가능한 빨리

수행되어야 합니다.

dispatcher가 하나의 process를 정지하고, 다른 process의 수행을 시작하는 데까지

소요되는 시간을 dispatch latency라고 합니다.

 

Scheduling Criteria

스케줄링 알고리즘들이 여러 존재하는데 그 중에서 평가의 척도를 scheduling criteria라고 합니다.

1. CPU utilization

cpu가 놀지 않고 얼마나 많이 사용되고 있는가 를 말합니다. 

cpu는 비싼 자원이기 때문에 얼마나 cpu가 노는일이 없고 많은 일을 할 수록 좋은 알고리즘 입니다.

 

2. Throughput (처리량)

초당 얼마나 많은 instruction을 처리했느냐는 중요합니다.

즉, 주어진 시간동안 몇 개의 process를 처리했는가

 

3. Turnaround time

process를 실행해 달라고 요청을 하고 끝날 때 까지의 시간을 의미합니다.

이는 Ready queue에서 대기하고 CPU에서 실행하며 I/O를 수행하는 데 소요된 기간을 합한 것입니다.

 

4. Waiting time

process를 실행해 달라고 요청을 했느데 다른 process가 실행되고 있어서 기다려야 하는 시간입니다.

즉, Ready queue에서 running이 되기 위해 기다리는 시간을 의미합니다.

 

5. Response time

process가 처음으로 CPU를 할당받기 까지 걸린시간 입니다.

예를 들어 어떤 프로그램이 실행했는데 5초 동안 아무 반응이 없다면 렉 걸렸다고 인식합니다.

하지만 프로그램이 실행하고 2초 뒤에 렉 걸린게 아니고 작업 중인 것이다 라는 메시지를 보내면

우리는 안심할 수 있습니다. 이러한 응답시간이 response time입니다.

 

~time 들은 최소화 하는 것이 좋고

cpu utilization과 throughput은 최대화 하는 것이 좋습니다.

Scheduling Algorithm

이제 부터 스케줄링 알고리즘을 살펴봅니다.

FCFS Scheduling

먼저 들어온 process를 먼저 CPU에 할당하는 방식입니다.

queue의 형태와 동일합니다. 구현이 쉬워 간단한 시스템에 자주 사용됩니다.

process 처리 순서에 따라 성능이 크게 달라질 수 있습니다.

수행 시간이 큰 process가 먼저 들어오면 그 뒤에 들어온 processe들이 불필요하게 오랜 시간을

기다리게 되는 convoy effect가 발생합니다.

먼저 온 process가 끝날 때 까지 OS가 개입하지 않는 non-preemptive 스케줄링 방식입니다.

즉, starvation은 없고, fair 합니다.

P1, P2, P3 process가 들어온 순서대로 할당되었습니다. 

P2, P3는 수행시간이 짧음에도, P1이 끝날 때 까지 기다리게 되어 평균 대기 시간이 늘어났습니다.

만약 P3, P2, P1 순서로 들어오게 되면 대기시간이 3이 됩니다.

즉, FCFS는 모든 process에게 공평하지만, 비효율적일 때가 많습니다.

이런 현상을 Convoy effect 입니다.

즉, 내 앞에 엄청 긴 process가 있어 내 waiting time이 매우 길어지는 현상을 말합니다.

 

Shortest-Job-First (SJF) Scheduling

process의 수행시간이 짧은 순서에 따라 CPU에 할당합니다.

FCFS에서 발생하는 convoy효과를 해결할 수 있습니다.

SJF는 preemptive 한 버전과 non-preemptive한 버전이 있습니다.

먼저 non-preemptive한 버전은 그냥 말 그대로 SJF를 수행하는 것입니다.

예를 들어 5초짜리 process를 진행시키다 갑자기 2초 까지 process가 들어왔다면 

그냥 5초 짜리 진행하고 2초 짜리 진행합니다.

반면에 preemptive는 5초까지 process를 진행하다 2초 짜리가 들어오면 5초 짜리를 중단시키고

2초짜리를 진행합니다.

이는 Shortest Remainng Time First(SRTF)라고 합니다.

 

burst 시간이 큰 process는 계속 뒤로 밀려나는 starvation이 발생합니다.(non-preemptive)

SJF는 주어진 process 집합에 대해 최소 평균 대기 시간을 제공한다는 점에서 최적입니다.
long process이전에 short process를 먼저하면 short process의 대기 시간이

long process의 대기 시간보다 더 단축됩니다.
문제는 다음에 진행할 process의 길이를 알기 어렵다는 것입니다.

non-preemptive 이므로 먼저 P1이 들어오면 P1이 끝날 때 까지 진행합니다.

P1이 수행되는 동안 P2, P3, P4가 들어왔습니다.

P1 이후에는 burst time이 가장 작은 P3가 진행되고 그 다음에는 P2와 P4가 burst time이 같지만 

P2가 먼저 들어왔으므로 P2를 먼저 시작합니다.



P1은 waiting time이 0초

P2는 2초에 들어 왔는데 8초 부터 시작되었으니 waiting time이 6초

P3는 4초에 들어왔는데 7초에 시작되었으니 waiting time이 3초

P4는 5에 들어왔는데 12초에 시작되었으니 waiting time이 7초기 됩니다.

이제는 preemptive한 상황을 살펴볼것입니다.

SJF에서 발생하는 starvation을 해결할 수 있습니다.

먼저 P1에서 시작하다가 2초에서 P2가 들어왔습니다. P2의 burst time은 4초이고 남은 P1의 burst time은

5(7-2)초입니다. 따라서 P2로 바꿔치기해 P2를 시작합니다.

근데 또 P2를 시작하고 2초 뒤 4초에서 P3가 들어왔습니다. P2의 남은 burst time은 2초(4-2) 이고, 

P3의 burst time은 1초 이므로 P3로 바꿔치기해 P3를 시작합니다.

P3를 시작하고 1초뒤 P4가 들어왔습니다. 어차피 P3는 끝났으므로 신경쓰지말고, 

남은 process중에 가장 짧은 burst time인 P2가 2초 남았으므로 P2를 먼저 실행합니다.

P2가 끝난 후 남은 burst time중 가장 짧은 시간인 P4 = 4초 이므로 P4를 실행하고

마지막으로 P1을 시작합니다.

P1은 2초 까지 실행하다가 11초에 다시 시작했으므로 waiting time은 9초입니다.

P2는 2초에서 도착하자마자 시작하고 4초에서 멈추고 다시 5초에서 시작했으므로 waiting time은 1초입니다.

P3는 4초에 도착하자마자 실행되고 끝났으므로 waiting time 은 0초 입니다.

P4는 5초에 도착했지만 실제 실행 시작 시간은 7초이므로 waiting time은 2초입니다.

 

Priority Scheduling

특정 기준으로 process에게 우선순위를 부여해 우선순위에 따라 process에 할당합니다.

process를 aging 해서 오래 대기한 process의 우선순위를 높이는 방식으로 사용됩니다.

SRF의 경우 남은 수행시간을 기준으로 우선순위를 부여 한다고 할 수 있습니다.

다른 스케줄링 알고리즘과 결합해 사용할 수 있으므로 Preemptive, non-Preemptive 모두 가능합니다.

당연하겠지만 우선순위를 기준으로 process가 차례대로 수행됩니다.

 

Round Robin (RR) Scheduling

일정 시간 할당량(Time quantum) 단위로 여러 process를 번갈아 가며 CPU에 할당합니다.

시스템의 time sharing과 같은 방식입니다.

response time이 좋습니다. 

주로 우선순위 스케줄링과 결합해 process의 시간 할당량을 조절하는 방식으로 활용합니다.

시간 할당량에 따라 OS가 계속 개입하는 Preemptive 방식입니다.

쉽게 말하면 FCFS의 preemptive 방식이라고 볼 수 있습니다.

일을 끝내야 할 process마다 얼만큼 시간동안 머물러서 작업을 하고 교체를 할건지를 time quantum이라고

합니다.

RR은 time quantum의 크기에 따라 장점과 단점이 존재합니다.

만약 현재 CPU burst가 10인데 time quantum이 10보다 크면 context switching이 한번도 안일어 납니다.

하지만 time quantum이 6이면 10중에 6까지 쓰고 process를 바꿔야 하기 때문에 context switching이

1번 일어납니다.

결국 time quantum이 작아질 수록 context switching이 늘어납니다.

만약 time quantum이 무한대 이면 한 process의 모든 작업이 끝나야 다른 process로 넘어가므로

FCFS와 똑같이 되기 때문에 결국 적당한 time quantum이 필요합니다.

Time Quantum = 20

전형적으로 SJF 보다 turnaround 가 평균적으로 높지만, response time은 더 좋습니다.

 

Multilevel Queue

어떤 process냐에 따라 여러 종류의 그룹으로 나누고 여러 개의 queue에 다양한 알고리즘을 적용하는

스케줄링 기법입니다.

interactive(상호작용) process들은 응답시간이 빨라야 합니다. 예를 들어 구글링을 하면

빠르게 검색결과를 보여줘야 합니다.

반면에 영화 다운로드 같은 백그라운드 작업은 실행시켜 놓고 오래걸려도 신경쓰지 않습니다.

이러한 이유로 foreground process들은 background process 보다 더 높은 우선순위를 갖게 되고, 

빠른 response time을 위해 다른 알고리즘이 적용되어야 더 효율적으로 성능을 끌어낼 수 있습니다.

보통 background queue는 FCFS알고리즘이 적용되고

foreground queue에는 RR알고리즘이 적용됩니다.

 

이렇게 Queue를 여러개로 분리해놓고 queue별로 스케줄링 알고리즘을 지정하는 것이 multilevel queue

입니다.

마찬가지로 multilevel queue도 preemptive방식을 적용합니다.

즉, batch process를 진행하다 system process가 들어오면  중단하고

system process를 먼저 실행합니다.