OS - CPU Scheduling

본 글은 (KOCW) 운영체제, 이화여자대학교 반효경 교수님의 강의를 듣고 내용을 요약 및 정리했습니다.
스터디를 진행하는 것에 목적이 있으며, 자세한 사항은 여기를 참고하시면 됩니다.

---

 여러 개의 프로그램이 실행될 때 다음과 같은 이슈가 발생

• 여러 Process가 CPU를 점유하려고 할 때, 누구에게 줄 것인가?
• 하나의 Process에게 얼마나 오랫동안 CPU를 할당할 것인가?

이러한 이슈들을 해결하는 작업이 CPU 스케쥴링이다

• 어떠 프로세스에게 얼마 동안 CPU를 할당할 지 결정하는 작업

CPU 스케쥴링에서 중요한 두 가지 관점

• CPU를 누구한테 줄 것인가
• CPU를 줬으면 처리가 끝날때까지 사용할 수 있게 해 줄 것이냐 중간에 뺏을 것이냐

---

CPU burst와 I/O burst

하나의 프로세스가 실행될 때 CPU burst와 I/O burst가 교대로 실행

https://walkccc.me/CS/OS/Chap06/

• CPU burst
  • 프로그램 실행중 연속적으로 CPU를 사용하는 단절된 구간(스케쥴링의 단위)
• I/O burst
  • 프로그램 실행중 I/O작업이 끝날 때까지 block 되는 구간

프로세스의 종류에 따라 CPU burst, I/O burst의 빈도와 길이가 다르며 이러한 특성에 따라 프로세스를 두 가지로 나눌 수 있음

• I/O bound Process
  • CPU를 잡고 계산하는 시간보다 I/O에 많은 시간이 필요한 프로세스
  • 사용자와 인터랙션이 많아서 I/O burst가 빈번하게 발생하는 경우가 여기 해당
  • Many short CPU bursts
• CPU bound Porcess
  • 계산 위주의 프로세스
  • CPU를 진득하게 쓰는 프로그램
  • Few very long CPU bursts 

https://reese-dev.netlify.app/OS/ban-07/

다양한 종류의 process가 섞여 있기 때문에 CPU 스케쥴링이 필요

• CPU 스케쥴링으로 I/O bound job에 우선적으로 CPU 할당
• CPU bound job이 CPU를 잡고 놓지 않을 경우 I/O bound job은 하염없이 기다려야 하고 사용자는 답답함을 느끼게 됨
  • CPU를 안쓰는 동안에는 빼앗아서 다른 프로세스가 사용하도록 해야 할 것 -> 스케쥴링 필요

---

CPU Scheduler와 Dispatcher

CPU Scheduler와 Dispatcher는 운영체제 커널 코드의 한 부분으로(별도의 하드웨어 X), 각각 다음의 역할을 수행

• CPU Scheduler
  • Ready 상태의 프로세스 중 CPU를 할당할 프로세스를 선택
• Dispatcher
  • CPU Scheduler에 의해 선택된 프로세스에게 CPU를 할당
    • Context Switching을 처리해줌
  • CPU를 할당한다는 것은 커널 모드이므로 프로세스가 CPU를 할당받아 작업을 처리할 수 있도록 유저 모드로 전환

---

CPU 스케쥴링이 필요한 경우

1. Running -> Blocked(ex. I/O request system call, wait() for child)
2. Running -> Ready(ex. timer interrupt)
3. Blocked -> Ready(ex. completion of I/O)
4. Terminate

1, 4에 의한 CPU 스케쥴링은 Non Preemptive(비선점)으로 자진 반납하는 형태

2, 3에 의한 CPU 스케쥴링은 Preemptive(선점) - 강제로 빼앗는 형태

 

CPU 스케쥴링 성능 척도 (Scheduling Criteria)

 

Performance Index 또는 Performance Measure라고도 함

 

시스템 입장에서의 성능 척도

-> 제한된 시간 내에 최대한 많은 프로세스를 처리 ('작업량'이 관건)

• CPU utilization (이용률)
  • 전체 시간 중에서 CPU가 프로세스들을 실행한 시간의 비율 (놀게 하지 마라)
• Throughput (처리량)
  • 단위 시간당 완료한 프로세스들의 개수
  • 네트워크에서는 단위 시간당 전송한 양을 의미 (ex. Mbps, Kbps)
  • 주어진 시간 동안 몇 개의 작업을 완료?

프로세스 입장에서의 성능 척도

-> CPU를 최대한 빨리 얻어서 빨리 실행 ('시간'이 관건)

• Turnaround time (소요시간, 반환시간)
  • 특정 프로세스에 대해 실행을 요청한 시점부터 완전히 종료된 시점까지의 소요 시간
    • 실제 실행 시간 외에 Ready 큐에서의 대기시간과 Device 큐에서의 대기시간 포함
• Waiting time (대기시간)
  • 프로세스가 Ready 큐에서 기다린 시간의 총 합
• Response time (응답시간)
  • 실행이 요청된 시점부터 최초로 CPU를 얻기까지 소요된 시간
  • Time sharing 상황(실시간)에서 중요한 척도

---

CPU 스케쥴링 알고리즘

1. FCFS (First-Come First-Served)

• nonpreemtive
• 프로세스를 ready queue에 들어온 순서대로 실행하는 알고리즘이다. FCFS 알고리즘의 평가 기준은 평균적인 waiting time이고, burst time과 ready queue에 추가된 순서를 고려하여 계산한다.

<Case 1>

Process	Burst Time
P1	24
P2	3
P3	3

• Order: P1 → P2 → P3
• Average waiting time = (0 + 24 + 27) / 3 = 17ms

<Case 2>

• Order: P2 → P3 → P1
• Average waiting time = (0 + 3 + 6) / 3 = 9ms

nonpreemtive 방식이기 때문에 먼저 처리하는 프로세스의 burst time에 따라 average waiting time이 달라진다

burst time이 긴 프로세스가 ready queue에 먼저 들어오게 되면 나중에 들어온 모든 프로세스들은 기다릴 수밖에 없다 (convoy effect)

이러한 문제점을 해결하려면 burst time이 짧은 프로세스를 먼저 처리하면 된다

 

2. SJF (Shortest-Job-First)

• SPN (Shortest-Process-Next)라고도 한다.
• nonpreemtive & preemtive 두 가지 방식으로 구현할 수 있다.
• burst time이 짧은 프로세스를 먼저 처리하기 때문에 평균적인 waiting time을 평가 기준으로 했을 때 가장 최적의 성능을 보장한다. (preemtive 방식일 때)

 

<Case 1 - nonpreemtive>

• 하나의 프로세스가 CPU를 잡으면 burst가 완료될 때까지 CPU를 빼앗기지 않는다. (하나의 프로세스가 완료될 때마다 burst time을 비교하여 실행할 프로세스를 선정)

Process	Arrival Time	Burst Time
P1	0	8
P2	1	4
P3	2	9
P4	3	5

Arrival Time: ready queue에 들어온 시점

• Average waiting time = (0 + (8 - 1) + (8 + 4 + 5 - 2) + (8 + 4 - 3)) / 4 = 7.75ms

가장 먼저 도착한 P1부터 실행한다. P1의 실행이 완료되면 (P2, P3, P4가 모두 도착해 있는 상태) burst time이 짧은 P2 → P4 → P3 순으로 실행한다.

 

<Case 2 - preemtive>

• 현재 수행 중인 프로세스의 남은 burst time보다 더 짧은 burst time을 가지는 새로운 프로세스가 도착하면 CPU 제어권을 빼앗아서 새로운 프로세스에게 할당한다. (ready queue에 새로운 프로세스가 도착할 때마다 burst time을 비교하여 실행할 프로세스를 선정)
• 이 방법을 SRTF (Shortest-Remaining-Time-First)라고도 한다.

Process	Arrival Time	Burst Time
P1	0	8
P2	1	4
P3	2	9
P4	3	5

 

• Gantt chart

https://walkccc.me/CS/OS/Chap06/

• Average waiting time = [(10 - 1) + 0 + (17 - 2) + (5 - 3)] / 4 = 26 / 4 = 6.5 ms

preemtive 방식에서 계산된 average waiting time은 최적화된 값이므로, 위와 같은 예제에서는 6.5ms 보다 짧은 average waiting time을 얻을 수 없다.

 

문제점 및 해결방법

1. Starvation (Indefinite Blocking)
   • SRTF(preemtive) 방식의 경우 우선순위가 낮은 프로세스(long burst time)는 마지막까지 실행되지 않을 수 있음

해결방법: Aging 기법

사람이 나이를 먹는 것처럼 프로세스도 시간이 지나면 priority가 1씩 높아지게 된다. 따라서 아무리 낮은 priority를 가지고 있는 프로세스도 언젠가는 높은 priority를 갖게 되기 때문에 CPU에 의해 실행될 수 있게 된다.

 

    2. CPU burst time을 미리 알 수 없다

해결방법 : exponential average을 사용, 과거 burst time 패턴을 통해 ‘추정’할 수 있다.

https://reese-dev.netlify.app/OS/ban-07/

최근 데이터일수록 더 큰 비중으로 반영하고 오래된 데이터일수록 적은 비중으로 반영하는 특성이 있다.

 

3. Priority Scheduling

• 프로세스마다 적절한 우선순위를 부여하여 우선순위가 높은 프로세스부터 실행하는 알고리즘
• 우선순위는 프로세스 생성 시에 사용자에 의해 지정되기도 하고 운영체제에서 내부적으로 메모리 용량이나 실행 시간 등을 기준으로 하여 결정하기도 한다.
• 우선순위를 부여하는 방식에 따라 결과가 FCFS와 같게 만들 수도 있고 SJF나 SRTF와 같게 만들 수도 있다. (SJF, SRTF는 Priority Scheduling의 일종)
• 프로세스별로 priority number (integer)를 할당하여 우선순위를 나타낼 수 있으며 일반적으로 priority number가 ‘작을수록’ 높은 우선순위를 뜻한다.
• nonpreemtive & preemtive 두 가지 방식으로 구현할 수 있다.
• 우선순위가 높은 프로세스가 계속해서 ready queue에 들어올 경우 우선순위가 낮은 프로세스는 영원히 실행되지 않을 수 있다. (Starvation) → Aging 기법으로 해결

 

4. Round-Robin (RR)

• preemtive
• ready queue의 프로세스들을 일정한 할당 시간 단위(quantum)로 돌아가면서 실행한다
  • 선택된 프로세스는 실행을 위해 할당된 시간을 가지며 이 시간이 만료되면 CPU를 빼앗기고 강제로 ready queue에 삽입된다
  • 할당 시간 단위를 정하기 때문에 응답시간이 빠르다 (다른 프로세스가 CPU를 획득하기까지 시간이 빠름)
• CPU burst time과 대기시간이 비례한다는 특징이 있다
  • CPU 작업량이 많을수록 더 빈번하게 기다려야 하기 때문.
• 할당 시간 단위(q)가 길어질수록 FCFS에 가까워진다
• 할당 시간 단위(q)가 짧아질수록 Response Time이 짧아지는 대신 빈번한 문맥 교환으로 인한 오버헤드가 늘어난다

장점

1. 할당 시간만큼 CPU를 줬다가 뺐는 작업을 반복하기 때문에 Response Time이 짧아지는 효과가 있다.
   → 짧은 계산 작업과 입출력 작업이 반복적으로 발생하는 대화형 프로세스에 적합
2. CPU burst time을 예측할 필요가 없고 모든 프로세스가 CPU를 얻을 수 있다.→ 다양한 burst time을 가지는 프로세스들이 뒤섞여 있을 때 효과적 (burst time이 길어도 CPU를 얻을 수 있기 때문에)
3. 어떤 프로세스도 할당 시간 단위(q) x (프로세스 개수(n) - 1)만큼의 시간 이상 기다릴 필요가 없다. 이 시간 내에 반드시 실행할 기회가 주어진다.

 

ProcessBurst Time

Process	Burst Time
P1	24
P2	3
P3	3

• Gantt chart:

https://walkccc.me/CS/OS/Chap06/

• Average waiting time = [(10 - 4) + 4 + 7] / 3 = 5.66 ms

일반적으로 SJF보다 Turnaround time, Waiting time은 길지만 Response Time은 더 짧다

모든 프로세스가 동일한 burst time을 가지는 경우
→ FCFS: 먼저 도착한 프로세스를 먼저 처리하여 종료시킬 수 있음
→ Round-Robin: 모든 프로세스를 일정 단위로 잘게 쪼개서 번갈아가며 처리하기 때문에 Turnaround time, Waiting time이 길어지고 모든 프로세스가 마지막까지 메모리에 남아있다가 거의 동시다발적으로 종료됨

 

5. Multilevel Queue

• ready queue를 프로세스들의 특성에 따라 여러 레벨로 분리하고 높은 레벨(=높은 우선순위)의 queue에 프로세스가 없는 경우에 한해서 그다음 레벨의 queue에 있는 프로세스를 실행한다
• 각 레벨별로 별도의 스케줄링 알고리즘을 적용할 수도 있다.
• foreground(interactive) process - RR
  • 사용자와 상호작용하기 때문에 오래 기다리면 안 됨 (응답시간 작게)
• background (batch) process(CPU를 오래 사용하는 프로세스) - FCFS
  • 백그라운드에서 실행되는 처리이기 때문에 컨텍스트 스위칭 오버헤드를 줄이고 한 번에 처리 

 

• queue에 대한 스케줄링이 필요
  • Fixed priority scheduling ─ 높은 레벨의 queue를 절대적으로 먼저 처리하는 스케줄링. 즉, 높은 레벨의 queue가 비었을 때만 낮은 레벨의 queue에 있는 프로세스를 실행함 → 낮은 레벨에 있는 queue는 영원히 실행되지 않을 수 있음 (Starvation 문제)
  • Time slice ─ 각 queue에 CPU 시간을 적절한 비율로 할당하는 (e.g. CPU의 80%를 높은 레벨의 queue에 할당하고 나머지 20%는 낮은 레벨의 queue에 할당)

https://walkccc.github.io/CS/OS/Chap06/#611-cpuio-burst-cycle

6. Multilevel Feedback Queue

• 프로세스들이 상황에 따라 queue와 queue 사이를 이동할 수 있는 스케줄링 알고리즘

 

• Multilevel Feedback Queue를 정의하는 파라미터들과 일반적인 운영방식
  • queue를 몇 개 둘 것인가
  • 각 queue별로 어떤 스케줄링 알고리즘을 적용할 것인가
  • 상위 queue로 갈수록 RR + 짧은 quantum unit, 가장 하위의 queue는 FCFS
  • 프로세스를 상위(또는 하위) queue로 보내는 기준은 무엇인가
  • 상위 queue에서 할당한 시간이 만료될 경우 바로 다음 하위 queue로 강등되며 상위 queue가 빌 때까지 대기해야 함
  • 프로세스가 queue로 들어갈 때 어떤 queue로 들어갈 것인가 > 가장 먼저 도착한 프로세스를 가장 상위 queue로 배치

 

• queue 하나에 대해 RR을 적용하는 것보다 더 CPU burst가 짧은 프로세스를 우대해 주는 스케줄링 방식이다.

https://tutorialwing.com/multilevel-feedback-queue-scheduling-tutorial-example/

---

Multiple-Processor Scheduling

• CPU가 여러 개인 경우의 스케줄링
• Homogeneous processor인 경우
  • queue에 한 줄로 세워서 각 프로세서가 알아서 꺼내가게 할 수 있다.
  • 반드시 특정 프로세서에서 수행되어야 하는 job이 있는 경우, 해당 job을 특정 프로세서에 먼저 할당할 수 있다.

 

• Load Sharing 필요
  • 일부 프로세서에 job이 몰리지 않도록 부하를 적절히 공유하는 메커니즘이 필요하다.
  • 별개의 queue를 두는 방법 vs 공동 queue를 사용하는 방법

 

• Symmetric Multiprocessing (SMP)
  • 각 프로세서가 각자 알아서 스케줄링 결정

 

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

 

Real-Time Scheduling

real-time job은 주로 특수 목적의 컴퓨터 시스템에서 적용되는데, 실행 결과가 제대로 출력되는 것뿐만 아니라 실행되는 시점도 지정된 시간 내에 실행이 완료되어야 한다. (e.g. 미사일 방어 시스템, 자동 브레이크 시스템)

real-time job들은 periodic 한 특성을 가진 경우가 많다. (e.g. 10초에 한 번씩 최소한 1초 동안 CPU를 가져야 한다.)

• Hard real-time system ─ 정해진 시간 안에 반드시 끝나도록 스케줄링해야 함
• Soft real-time computing ─ 일반 프로세스에 비해 높은 priority를 갖도록 해야 함 (deadline 보장 x)

 

Thread Scheduling

• Local Scheduling ─ User level thread의 경우 사용자 프로세스가 직접 thread를 스케줄링한다. 운영체제는 thread의 존재를 모르는 상태에서 해당 프로세스에게 CPU를 줄지 말지를 결정할 뿐이다. 프로세스에 CPU가 주어지면 프로세스 내부에서 어떤 thread에게 CPU를 줄 건지 결정한다.

 

• Global Scheduling ─ Kernel level thread의 경우 운영체제가 thread의 존재를 알고 있다. 프로세스와 마찬가지로 운영체제(커널의 단기 스케줄러)가 thread 스케줄링을 담당한다.

 

Scheduling Algorithm Evaluation

1. Queueing models

https://reese-dev.netlify.app/OS/ban-08/

확률분포로 주어지는 arrival rate(프로세스의 도착률)와 service rate(CPU의 처리율) 등을 통해 각종 performance index 값을 계산해서 여러 가지 성능 척도들을 도출하는 방법

 

   2. Implementation & Measurement

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

 

   3. Simulation

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

---

정리

• CPU 스케쥴링이란?
  • CPU 스케쥴링이란 여러 프로세스가 하나의 CPU를 할당받기 위해 Ready Queue에서 대기 중일 때 어떤 프로세스에게 CPU할당을 할 것인지를 결정하고 할당하는 과정까지를 말합니다
  • CPU 스케쥴링은 어떤 프로세스에게 CPU를 할당할지를 결정하는 CPU 스케쥴러와 선택된 프로세스에 CPU를 할당하는 역할을 하는 Dispatcher로 이루어지며, Dispatcher가  Context Switching을 담당하며 CPU를 할당하는 작업은 Kernel Mode에서 이루어지므로 User Mode로 변경하는 작업까지 처리합니다
• I/O bound Process란?
  •  I/O Burst가 빈번하게 발생하는 프로세스를 말합니다. I/O Burst란 프로세스가 I/O 작업을 처리하기 위해 대기하는 동안 blocked 된 상태로 기다리는 시간을 말하며 사용자와 인터랙션이 자주 발생하여 I/O 작업이 빈번한 프로세스가 이에 해당할 수 있습니다
• CPU 스케쥴링에서 필요한 성능 척도?
  • CPU를 얼마나 쉬는 시간 없이 사용하느냐 시스템 입장에서의 성능 척도와 프로세스가 얼마나 빠르게 CPU를 할당받을 수 있냐의 프로세스 입장에서의 성능 척도로 나뉠 수 있습니다
    • 시스템 입장에서의 성능 척도는 CPU 이용률 즉, 전체 시간 동안 얼마나 CPU를 프로세스가 이용하는지 CPU utilization과 주어진 시간 동안 얼마나 많은 프로세스를 처리할 수 있느냐 Throughput (처리량)이 성능 척도가 됩니다
    • 프로세스 입장에서의 성능 척도는 프로세스가 CPU할당을 받기 위해 대기 한 시점부터 완료되는 시점까지의 시간 Turnaround time(소요시간)과 프로세스가 Ready Queue에서 대기한 시간의 합 Waiting time,  실행이 요청된 시점으로부터 CPU를 할당받기까지의 시간 Response Time이 성능 척도가 됩니다
• 리눅스 멀티태스킹 환경에서 스케쥴링이 어떻게 될까요?
  • 리눅스에서는 time slice방식의 RR을 사용하는 것으로 알고 있습니다
  • 특이하게 time slice가 유동적으로 변하는 방식을 사용합니다
    • time slice가 고정된다면?
    • 프로세스의 특성에 따라 RR의 문제점인  빈번한 문맥 교환으로 인한 오버헤드가 늘어나거나, FCFS처럼 작동하게 되면 FCFS의 문제점인 average waiting time이 커지게 된다
    • 따라서 유동적인 time slice 방식으로 프로세스의 특징에 따라 CPU를 할당하는 방법을 사용합니다