CPU 스케줄링

이 고민을 해결하기 위해서 CPU 스케줄링이 필요하다. 여러 종류의 job(=process)이 섞여 있기 때문이다. Interactive job에게는 적절한 response를 제공하는 것이 필요하다. CPU 스케줄링은 CPU와 I/O 장치 등 시스템 자원을 골고루 효율적으로 사용할 수 있도록 한다.

목차

1. CPU and I/O Bursts in Program Execution
2. CPU-burst Time의 분포
3. CPU Scheduler & Dispatcher
4. Scheduling Algorithms
   1. FCFS (First-Come First-Served)
   2. SJF (Shortest- Job First)
   3. SRTF (Shortest-Remaining-Time-First)
   4. Priority Scheduling
   5. RR (Round Robin)
   6. Multilevel Queue
   7. Multilevel Feedback Queue
5. 다음 CPU Burst Time의 예측
6. 특수한 CPU 스케줄링
7. Algorithm Evaluation

 

---

CPU and I/O Bursts in Program Execution

 

위 그림은 한 프로세스의 일생을 시작부터 종료까지 담았다.

 

Burst : 계속되는 작업을 의미한다.

CPU burst : CPU를 사용하는 구간을 의미한다.

I/O burst : I/O를 실행하는 구간을 의미한다.

 

어떤 프로세스는 CPU를 굉장히 오래 사용하고, I/O는 아주 잠깐만 사용한다. 다른 어떤 프로세스는 CPU 잠깐, I/O 잠깐 자주 번갈아 가면서 사용하기도 한다. 이처럼 항상 상황은 다르다. 주로 과학 계산과 같이 연산량이 많이 필요한 프로그램은 CPU를 오래 사용하고, 사람과 Interaction이 많은 프로그램은 CPU와 I/O가 번갈아가면서 사용된다. 아래 CPU-burst Time의 분포를 보면 이를 확인할 수 있다.

 

 

---

CPU-burst Time의 분포

 

위 그래프에서 보다시피 프로세스는 특성에 따라 두 종류로 나눈다. CPU를 길게 쓰는 프로세스를 CPU bound job(= CPU bound process), I/O가 중간에 많이 끼어들어서 CPU를 짧게 씩 쓰는 프로세스를 I/O bound job(= I/O bound process)이라고 한다.

 

프로세스의 특성 분류

➳ I/O-bound process

    •  CPU를 잡고 계산하는 시간보다 I/O에 많은 시간이 필요한 job

    •  many short CPU bursts

➳ CPU-bound process

    • 계산 위주의 job

    • few very long CPU bursts

 

 

그럼 둘 중 CPU를 누구한테 먼저 주어야 할까 ? 준다면 얼마만큼 주어야 할까 ?

 

이 고민을 해결하기 위해서 CPU 스케줄링이 필요하다. 여러 종류의 job(=process)이 섞여 있기 때문이다. Interactive job에게는 적절한 response를 제공하는 것이 필요하다. CPU 스케줄링은 CPU와 I/O 장치 등 시스템 자원을 골고루 효율적으로 사용할 수 있도록 한다.

 

 

---

CPU Scheduler & Dispatcher

" CPU Scheduler "

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

 

" Dispatcher "

➳  CPU의 제어권을 CPU scheduler에 의해 선택된 프로세스에게 넘긴다.

➳  이 과정을 context switch(문맥 교환)라고 한다.

 

CPU 스케줄링이 필요한 경우는 프로세스에게 다음과 같은 상태 변화가 있는 경우이다.

 

1) Running ➳ Blocked (e.g. I/O 요청하는 system call)

2) Running ➳ Ready (e.g. 할당시간만료로 timer interrupt)

3) Blocked ➳ Ready (e.g. I/O 완료 후 interrupt)

4) Terminate

 

1), 4)의 경우는 nonpreemptive (= 강제로 빼앗지 않고 자진 반납)

All other scheduling is preemptive (= 강제로 빼앗음)

 

 

---

Scheduling Criteria

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

 

✔ CPU utilzation (이용률)

Keep the CPU as busy as possible

 

✔ Throughput (처리량)

# of processes that complete their execution per time unit

 

✔ Turnaround time (소요시간, 반환시간)

amount of time to execute a particular process

 

✔ Waiting 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 

(for time-sharing environment)

 

 

이용률과 처리량은 높을수록 좋다. 시간과 관련된 세 가지 성능 척도는 낮을수록 좋다.

 

 

---

Scheduling Algorithms

• FCFS (First-Come First-Served)
• SJF (Shortest-Job-First)
• SRTF (Shortest-Remaining-Time-First)
• Priority Scheduling
• RR (Round Robin)
• Multilevel Queue
• Multilevel Feedback Queue

 

 

---

FCFS (First-Come First-Served)

 

먼저 온 순서대로 처리해 준다. 강제로 빼앗지 않는 nonpreemptive이다. 인간 세상에서는 널리 쓰이는 방법이지만, CPU 스케줄링에서는 대단히 효율적이지 못하다. 위 예제를 보면 성능 척도 중 하나인 waiting time의 평균은 17초이다. 만약 CPU를 짧게 쓰는 프로세스가 먼저 도착했다면 어떻게 될까 ?

 

 

똑같은 세 개의 프로세스가 똑같이 선착순으로 왔지만 이번엔 waiting time이 굉장히 짧아졌다. 

CPU를 오래 쓰는 프로세스가 먼저 도착한 바람에 CPU를 짧게 쓰는 프로세스가 아주 오래 기다려야 하는 안 좋은 효과를 Convoy effect라고 한다.

 

 

---

SJF (Shortest-Job-First)

➳ 각 프로세스의 CPU burst time을 가지고 스케줄링에 활용한다.

➳ CPU burst time이 가장 짧은 프로세스를 제일 먼저 스케줄 한다.

 

💡 Two schemes :

1) Nonpreemptive

일단 CPU를 잡으면 이번 CPU burst가 완료될 때까지 CPU를 선점 (preemption)하지 않는다.

2) Preemptive

현재 수행 중인 프로세스의 남은 burst time 보다 더 짧은 CPU burst time을 가지는 새로운 프로세스가 도착한다면 CPU를 빼앗긴다. 이 방법을 Shortest-Remaining-Time-First (SRTF)이라고도 부른다.

 

" SJF is optimal "

주어진 프로세스에 대해 minimum average waiting time을 보장한다. optimal은 최적의 방법이라는 뜻이다. 즉, 다른 어떤 CPU 스케줄링 알고리즘을 쓰더라도 SJF보다 대기 시간의 평균을 더 짧게 할 수는 없다는 의미이다. SJF는 두 가지로 나뉘지만 제일 optimal 한 방법은 Preemptive 버전인 SRTF이다.

 

 

Example of Non-Preemptive SJF

 

 

Example of Preemptive SJF

 

 

그러나 SJF는 치명적인 약점을 가지고 있다. 바로 starvation을 발생시킬 수 있다는 점이다. SJF는 극도로 효율성을 중시하다 보니 짧은 프로세스에게 무조건 우선순위를 준다. 따라서 long job, 즉 CPU를 길게 쓰는 프로세스는 영원히 CPU를 못 얻을 수도 있다. Queue가 계속 쌓일 수 있기 때문이다. 어떤 프로세스가 10초라고 한다면 앞에 계속 1초짜리 10000개, 3초짜리 10000개가 속속히 도착을 한다면 10초가 걸리는 프로세스는 아예 기회가 없을 수 있다는 것이다.

 

SJF는 CPU를 짧게 쓰는 프로세스한테 준다고 했다. 하지만 누가 짧게, 누가 길게 쓰는지 처음에 알 수가 없다. 짧게 쓴다고 했는데 막상 계속 길게 쓰는 경우가 있고, 길게 쓴다고 했는데 막상 짧게 쓰고 I/O를 하러 가버리는 경우도 있기 때문이다. 즉, 얼마큼 CPU를 사용한 후 I/O를 하러 갈 것인지, CPU burst를 예측하기 힘들다는 것이다. 정확히는 예측하기 어렵지만 과거의 CPU burst 이력을 보고 다음번의 CPU burst를 예측하는 방법을 알아보자 !

 

 

---

다음 CPU Burst Time의 예측

다음번 CPU burst time을 어떻게 알 수 있을까?

추정(estimate)만이 가능하다. 과거의 CPU burst time을 이용해서 추정한다. (exponential averaging)

 

 

1. t는 실제 과거의 CPU burst 값이다. n은 이미 과거에 지나간 것으로, n번째 CPU burst 값이 얼마였는지 알려준다.

2. 𝛕 는 예측값이다. n+1번째의 CPU Burst 값을 예측하는 것이다.

3. α는 어느 정도 가중치를 두어 반영할 것인지를 결정한다.

4. n번째 실제 CPU Burst 값과  n번째 CPU Burst를 예측한 값에 어느 정도 가중치를 두어 두 값을 더하는 것이다.

 

 

 

 

---

Priority Scheduling

➳ A priority number (integer) is associated with each process`

➳ highest priority를 가진 프로세스에게 CPU를 할당한다. (smallest integer = highest priority)

    •  preemptive

    •  nonpreemptive

 

" SJF는 일종의 priority scheduling이다. "

priority = predicted next CPU burst time

 

🌀 Problem 

➳ Starvation : low priority processes may never execute

🌀 Solution

➳ Aging : as time progresses increase the priority of the process

 

SJF의 문제점인 Starvation을 해결하는 방법은 Aging이다. Aging은 나이 든 프로세스를 우대한다. 먼저 온 프로세스는 시간이 지날수록 우선순위를 높여주는 것이다. 다음은 실제 현재 CPU Scheduling에서 가장 많이 사용하는 방법의 근간이 되는 알고리즘, Round Robin을 알아보자 !

 

 

---

Round Robin (RR)

➳ 각 프로세스는 동일한 크기의 할당 시간 (time quantum)을 가진다.

    • 일반적으로는 10-100 milliseconds

➳ 할당 시간이 지나면 프로세스는 선점(preempted)당하고, ready queue의 제일 뒤에 가서 다시 줄을 선다.

➳ n개의 프로세스가 ready queue에 있고 할당 시간이 q time unit인 경우 각 프로세스는 최대 q time unit 단위로 CPU 시간의 1/n을 얻는다.

    • 어떤 프로세스도 (n-1)q time unit 이상 기다리지 않는다.

➳ Performance

    • q large : FCFS

    • q small : context switch 오버헤드가 커진다.

 

 

long job과 short job이 섞여있기 때문에 Round Robin을 사용하는 것이 효율적인 것이다. 만약 long job만 있거나, short job만 있도록 통일된 프로세스를 생각해 보자. 만약 똑같이 5분 걸리는 프로세스가 100개라고 한다면 Round Robin 알고리즘보다는 그냥 5분씩 끝까지 처리해주는 것이 더 나을 것이다. 

 

 

---

Multilevel Queue

" Ready Queue를 여러 개로 분할한다. "

➳ foreground (interactive)

➳ background (batch - no human interaction)

 

" 각 큐는 독립적인 스케줄링 알고리즘을 가진다. "

➳ foreground - RR

➳ background - FCFS

 

" 큐에 대한 스케줄링이 필요하다. "

➳ Fixed priority scheduling

    • serve all from foreground then from background

    • possibility of starvation

➳ Time slice

    • 각 큐에 CPU time을 적절한 비율로 할당한다.

    • e.g. 80% to foreground in RR, 20% to background in FCFS

 

 

 

---

Multilevel Feedback Queue

➳ 프로세스가 다른 큐로 이동이 가능하다.

➳ 에이징 (aging)을 이와 같은 방식으로 구현할 수 있다.

➳ Multilevel-feedback-queue scheduler를 정의하는 파라미터들

    • Queue의 수

    • 각 큐의 scheduling algorithm

    • Process를 상위 큐로 보내는 기준

    • Process를 하위 큐로 내쫓는 기준

    • 프로세스가 CPU 서비스를 받으려 할 때 들어갈 큐를 결정하는 기준

 

 

Example of Multilevel Feedback Queue

 

 

위의 사진은 Multilevel Feedback Queue의 한 예이다. 제일 우선순위가 높은 맨 위 큐에서 프로세스가 끝나지 않았다면 그다음 큐로 내려가는 방식을 표현한 것이다. Round Robin만 사용하는 것이 아니라 상황에 맞게 이런 식으로도 사용을 한다. I/O Bound, 즉 CPU를 빨리 쓰려는 프로세스를 빨리 걸러내서 처리를 하는 효과가 있다.

 

➳ Three queues

    • Q0 : time quantum 8 milliseconds

    • Q1 : time quantum 16 millisseconds

    • Q2 : FCFS

➳ Scheduling

    • new job이 queue Q0으로 들어간다.

    • CPU를 잡아서 할당 시간 8 milliseconds 동안 수행한다.

    • 8 milliseconds 동안 다 끝내지 못했으면 queue Q1으로 내려간다.

    • Q1에 줄 서서 기다렸다가 CPU를 잡아서 16ms 동안 수행한다.

    • 16 ms에 끝내지 못한 경우 queue Q2로 쫓겨난다.

 

 

---

특수한 CPU 스케줄링

지금까지는 한 CPU가 있는 환경에서의 CPU 스케줄링 알고리즘에 대해 알아보았다.

지금부터는 특수한 경우의 CPU 스케줄링을 알아본다.

 

Multiple-Processor Scheduling

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

➳ Homogeneous processor인 경우

    • Queue에 한 줄로 세워서 각 프로세서가 알아서 꺼내 가도록 할 수 있다.

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

➳ Load sharing

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

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

➳ Symmetric Multiprocessing (SMP)

    • 각 프로세서가 각자 알아서 스케줄링을 결정한다.

➳ Asymmetric multiprocessing

    • 하나의 프로세서가 시스템 데이터의 접근과 공유를 책임지고 나머지 프로세서는 거기에 따른다.

 

 

Real-Time Scheduling

Real-Time OS는 정해진 시간 안에 어떠한 일이 반드시 종료됨이 보장되어야 하는 실시간시스템을 위한 OS이다. 따라서 해당 deadline을 만족시키는 것이 중요하다.

 

➳ 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 library에 의해 어떤 thread를 스케줄 할지 결정한다.

➳ Global Scheduling

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

 

User level thread는 운영체제가 thread의 존재를 모르고, 사용자 본인이 내부에 thread를 여러 개 두는 것이다. Kernel level thread는 운영체제가 thread의 존재를 알고, 운영체제가 직접 CPU 스케줄링에 관여한다.

 

 

---

Algorithm Evaluation

물론 성능 척도가 좋은 것이 좋은 CPU 스케줄링 알고리즘이다. 그렇다면 성능 척도를 어떻게 구해서 알고리즘을 어떻게 평가할까? 알고리즘 평가 방법을 알아보자 !

 

➳ Queueing models

    • 확률 분포로 주어지는 arrival rate와 service rate 등을 통해 각종 performance index 값을 계산한다.

     • 복잡한 수식을 계산하는 대단히 이론적인 방법이다.

     • 현재 CPU Scheduling에서 사용하지는 않는다.  

 

 

➳ Implemetation (구현) & Measurement (성능 측정)

    • 실제 시스템에 알고리즘을 구현하여 실제 작업 (workload)에 대해 성능을 측정하여 비교한다.

    • 실제로 구현하여 성능을 측정하는 것은 매우 어렵다. (대안 = Simulation)  

➳ Simulation (모의 실행)

    • 알고리즘을 모의 프로그램으로 작성 후 trace를 입력으로 하여 결과를 비교한다.

 

trace : input이 되는 데이터이므로 중요하다.

 

 

---

Reference

KOCW 운영체제 강의 (이화여자대학교, 반효경 교수님)