CPU Scheduling

http://www.kocw.net/home/search/kemView.do?kemId=1046323 

KOCW 반효경 교수님의 운영 체제 강의를 수강하면서 작성한 포스트입니다. 😁

CPU만 연속적으로 실행하고 있는 단계를 CPU burst, I/O만 실행하고 있는 단계를 I/O burst라고 합니다. 어떤 프로그램이든, 프로그램이 실행된다는 것은 CPU burst와 I/O burst가 반복적으로 실행이 된다고 말할 수 있습니다. 단, 프로그램의 종류에 따라 그 빈도수는 달라질 수 있습니다. interactive한 job을 많이 수행하는 경우에는 CPU burst와 I/O burst가 서로 번갈아 나오는 횟수가 많아지게 되겠죠. 

 

CPU burst와 I/O burst의 교체가 잦은 경우는 그만큼 I/O burst가 자주 일어났다는 뜻이므로 I/O bound job이라고 부릅니다. CPU burst가 긴 경우는 CPU bound job이라고 부릅니다.

I/O bound job과 CPU bound job이 섞여 있기 때문에 CPU 스케줄링이 필요합니다. I/O bound job은 interactive한 job입니다. I/O bound job이 너무 오래 기다리지 않도록, CPU와 I/O 장치 등의 시스템 자원을 골고루 효율적으로 사용하게 하기 위해 CPU 스케줄링을 이용합니다. 

 

CPU Scheduler & Dispatcher

CPU Scheduler

Ready 상태의 프로세스 중에서 이번에 CPU를 줄 프로세스를 고릅니다.

 

Dispatcher

CPU의 제어권을 CPU scheduler에 의해 선택된 프로세스에게 넘깁니다. 이 과정을 context switch라고 부릅니다. 

 

CPU Scheduling이 필요한 경우

1. Running -> Blocked (ex. I/O를 요청하는 시스템 콜)

2. Running -> Ready (ex. timer interrupt) 

3. Blocked -> Ready (ex. I/O 완료를 알리는 인터럽트)   

4. Terminate 

 

1, 4에서의 스케줄링은 nonpreemptive (=강제로 빼앗지 않고 자진 반납), 다른 모든 스케줄링 방식은 preemptive (=강제로 빼앗음) 입니다. 

 

Scheduling Criteria

performance Index (= Performance Measure, 성능 척도)

• CPU Utilization (이용률): keep the CPU as busy as possible
• Throughput (처리량): # of process that complete their execution per time unit
• Turnaround time (소요시간, 반환시간): amount of time to execute a particular process
• Wating time (대기 시간): amount of time a process has been waiting in the ready queue
• Response time (응답 시간): amount of time it takes from when a request was submitted until the first response is produced, not output 

 

Scheduling Algorithms

FCFS (First-Come First-Served)

먼저 온 순서대로 프로세스들을 처리합니다. 

P1: 24, P2: 3, P3: 3 의 burst time을 가지고, P1, P2, P3의 순서대로 도착했다면

P1 (24)

P2 (3)

P3 (3)

waiting time for P1 = 0; P2 = 24; P3 = 27

average wating time = (0 + 24 + 28) / 3 = 17

 

FCFS는 앞에 어떤 프로세스가 오느냐에 따라서 기다리는 시간에 상당한 영향을 미치게 됩니다. 긴 프로세스가 앞에 오게 되서, 짧은 프로세스들이 오래 기다려야 하는 현상을 convoy effect라고 부릅니다. 

 

SJF (Shortest-Job-First)

CPU burst가 가장 짧은 프로세스에게 CPU를 스케줄하는 스케줄링 알고리즘입니다. 

• Nonpreemptive: 일단 CPU를 잡으면 이번 CPU burst가 완료될 때까지 CPU를 선점(preemptive)당하지 않는 방식입니다.
• Preemptive: 현재 수행중인 프로세스의 남은 burst time보다 더 짧은 CPU burst time을 가지는 새로운 프로세스가 도착하면 CPU를 빼앗깁니다. 이 방법을 SRTF(Shortest-Reamining-Time-First)라고도 부릅니다. 

SJF 알고리즘은 주어진 프로세스들에 대해 minimum average waiting time을 보장합니다. (preemptive 일 경우)

SJF는 극단적으로 CPU 사용이 짧은 job을 선호합니다. 사용 시간이 긴 프로세스는 영원히 스케줄되지 않을 수 있습니다. (=starvation) 

또한 CPU burst time을 정확히 알 수 없고 추정(estimate)만이 가능하다는 단점이 있습니다.

 

추정하는 방법은 과거의 CPU burst time을 이용해서 추정하게 됩니다. (exponential averaging)

$t_{n}$: actual length of $n^{th}$ CPU burst

$\tau_{n+1}$: predicted value for the next CPU burst

$\alpha$, $0 \leq \alpha \leq 1$

$\tau_{n+1} = \alpha t_{n} + (1 - \alpha)\tau_{n}$

 

$\alpha$와 $(1 - \alpha)$가 둘 다 1 이하이므로, 점화식을 계산하게 되면, 후속 term은 선행 term 보다 적은 가중치 값을 가지게 됩니다. 그렇기 때문에 가장 최근 걸린 시간에 더 가중치를 많이 줘서 계산하게 되는 셈이죠. 

 

example of SJF

P1 (arrival: 0, burst: 7)

P2 (arrival: 2, burst: 4)

P3 (arrival: 4, burst: 1)

P4 (arrival: 5, burst: 4) 

 

* Non-preemptive SJF

P1 (7)

P3 (1)

P2 (4)

P4 (4)

average waiting time = (0 + 6 + 3 +7) / 4 = 4

 

* Preemptive SJF (SRTF)

P1 (2)

P2 (2)

P3 (1)

P2 (2)

P4 (4)

P1 (5)

average waiting time = (9 + 1 + 0 + 2) / 4 = 3

 

Priority Scheduling

높은 priority를 가진 프로세스에게 CPU를 할당하는 스케줄 방법입니다. (smallest integer = highest priority)

priority scheduling에도 preemptive와 nonpreemptive 방식이 있습니다. SJF는 일종의 priority scheduling이라고 볼 수도 있습니다. priority를 CPU burst time을 이용해서 설정해준 것이라고 볼 수 있겠죠. Priority scheduling의 문제점은 SJF 스케줄링의 문제점이기도 했던 starvation입니다. 낮은 priority의 프로세스는 실행될 수 없는 일이 발생할 수도 있습니다. 이 문제는 aging을 통해 해결이 가능합니다. 시간이 지날수록 아직 실행되지 않은 프로세스들의 priority를 올려줍니다. 

 

Round Robin (RR)

현대적인 컴퓨터 시스템에서 사용하는 CPU 스케줄링은 RR에 기반하고 있습니다. 시분할 시스템이 바로 RR을 이용한 것이죠. 각 프로세스는 동일한 크기의 할당 시간(time quantum)을 가집니다. 할당 시간이 지나면 프로세스는 선점 당하고 ready queue의 제일 뒤에 가서 다시 줄을 서게 됩니다.

 

n개의 프로세스가 ready queue에 있고 할당 시간이 q time unit인 경우, 각 프로세스는 최대 q time unit 단위로 CPU 시간의 1 / n을 얻게 됩니다. 어떤 프로세스도 (n - 1)q time unit 이상 기다리지 않습니다. 

 

RR의 경우, q의 크기에 따라서 performance가 달라지게 됩니다.

• q large: FCFS와 같은 성능
• q small: context switch 오버헤드가 커짐

그래서 적당한 크기의 time quantum을 잡는 것이 중요하고 보통은 10-100 milliseconds라고 알려져 있습니다. RR은 SJF보다 average turnaround time은 길지만, response time은 더 짧습니다. 

 

Multilevel Queue

Multilevel queue는 이런 식으로 ready queue가 여러 개로 분할되어 있습니다. 각 큐는 독립적인 스케줄링 알고리즘을 가지고, 큐들에 대한 스케줄링이 필요합니다. (예를 들면 우선 순위가 높은 queue에 80%, 우선 순위가 낮은 queue에 20%를 주는 경우입니다.)

 

Multilevel Feedback Queue

Multilevel queue와는 달리 프로세스가 다른 큐로 이동이 가능합니다. aging을 이와 같은 방식으로 구현할 수 있습니다. 

Multilevel-feedback-queue scheduler를 정의하는 파라미터는 다음과 같습니다.

 

* Queue의 수

* 각 큐의 scheduling algorithm

* process를 상위 큐로 보내는 기준

* process를 하위 큐로 내쫓는 기준

* process가 CPU 서비스를 받으려 할 때 들어갈 큐를 결정하는 기준

 

우선순위가 높은 큐는 RR의 time quantum 크기가 작고, 낮은 큐는 FCFS 방식을 사용하는 것을 볼 수 있습니다. 

 

Multiple-Processor Scheduling

CPU가 여러 개인 경우 스케줄링은 더욱 복잡해집니다. 

 

homogeneous processor인 경우

* queue에 한 줄로 세워서 각 프로세서가 알아서 꺼내가게 할 수 있습니다. 

* 반드시 특정 프로세서에서 수행되어야 하는 프로세스가 있는 경우에는 문제가 더 복잡해집니다.

 

Load sharing

* 일부 프로세서에 job이 몰리지 않도록 부하를 적절히 공유하는 메커니즘이 필요합니다.

* 별개의 큐를 두는 방법 vs. 공동 큐를 사용하는 방법

 

Symmetric Multiprocessing (SMP)

* 각 프로세서가 각자 알아서 스케줄링을 결정합니다.

 

Asymmetric multiprocessing

* 하나의 프로세서가 시스템 데이터의 접근과 공유를 책임지고 나머지 프로세서는 거기에 따르는 것을 말합니다. 

 

Real-Time Scheduling

Hard real-time systems

* Hard real-time task는 정해진 시간 안에 반드시 끝내도록 스케줄링이 되야 합니다.

 

Soft real-time computing

* Soft real-time task는 일반 프로세스에 비해 높은 priority를 갖도록 해야 합니다. 

 

Thread Scheduling

Local Scheduling

* User level thread의 경우, 운영 체제가 thread의 존재를 모릅니다. 그렇기 때문에 사용자 수준의 thread library에 의해 어떤 thread를 스케줄할지 결정해줍니다. 

 

Global Scheduling

* Kernel level thread의 경우 일반 프로세스와 마찬가지로 커널의 단기 스케줄러가 어떤 thread를 스케줄할지 결정합니다.

 

Algorithm Evaluation

CPU Scheduling에 어떤 알고리즘이 있는지 살펴봤습니다. 이 알고리즘들의 성능을 평가할 수 있는 방법도 필요하겠죠. 평가 방법은 크게 세 가지로 분류합니다.

 

Queueing models

* 굉장히 이론적인 방법입니다. 확률 분포로 주어지는 arrival rate와 service rate 등을 통해 각종 performance index 값을 계산합니다. 예전에는 이런 방식을 선호했지만 최근에는 실제 시스템에서 돌려보는 방식을 더 선호하는 경향이 있습니다.

 

Implementation (구현) & Measurement (성능 측정)

* 실제 시스템에서 알고리즘을 구현해서 실제 작업(workload)에 대해서 성능을 측정 비교합니다.

 

Simulation (모의 실험)

* 알고리즘을 모의 프로그램으로 작성 후 trace를 입력해서 결과를 비교합니다.