[OS101] CPU 스케줄링

 

본 글은 2023.09.15에 새롭게 업데이트되었습니다.

 

서울대학교 평생 교육원에서 제공하는 운영체제의 기초 강의 내용을 중점으로 정리했다. 부족한 부분은 <Operating System Concepts> 책을 참고하면서 채워 나갔다. 이해를 돕기 위한 그림들은 여기에서 가져왔다.

 

목차

• 스케줄링
• 스케줄링 기준
• 스케줄링 정책

 

스케줄링

• CPU-I/O Burst Cycle
• CPU 스케줄러
• 선점적 스케줄링
• 디스패처

 

프로세스는 능동적으로 여러 자원을 사용한다. 이 때 자원의 종류로는 두 가지가 있다.

• 선점적 자원(Preemptive Resource): 한 프로세스가 점유한 상태에서 다른 프로세스에게 양보할 수 있는 자원, 예) CPU, 메모리
• 비선점적 자원(Nonpreemptive Resource): 한 프로세스가 점유하면 사용을 마칠 때까지 다른 프로세스에게 양보할 수 없는 자원, 예) 파일 공간, 프린터, ...

 

여러 개의 프로세스들은 각자 필요한 자원을 원한다. 자원을 어떻게 하면 효율적으로 프로세스들에게 '잘' 나눠줄 수 있을까? 특히나 선점적 자원 중 CPU는 모든 프로세스들이 간절하게 원하고 있는 자원이다. 그렇다면 어떤 프로세스에게 얼마만큼의 시간동안 CPU를 할당해야할까? CPU의 효율적인 분배를 위해 CPU 스케줄링이라는 개념이 등장하게 된다. CPU 스케줄링을 수행하는 스케줄러는 현재 수행하고 있는 프로세스 이후 CPU 자원을 가질 바로 다음 프로세스는 무엇이 될지, 그리고 CPU를 선점한 프로세스가 얼마나 CPU를 오래 사용하게 둘 것인지를 결정한다.

 

그렇다면 스케줄링을 하면서 신경써야할 것은 무엇일까?

• 자원 사용 극대화: 최대한 자원 사용률을 극대화시켜야 한다. 예) CPU 사용, I/O 사용
• 오버헤드 단축: 스케줄링을 수행하면 운영체제 코드가 돌아가게 되는데, 이 코드 수행 양이 적어야 한다.
• 컨텍스트 스위칭 단축: 빈번한 컨텍스트 스위칭은 추가적인 오버헤드를 발생시킨다.
• 앱에 맞는 공정성: 상황에 맞는 스케줄링이 필요하다. 

 

CPU-I/O Burst Cycle

CPU 스케줄링에서 사용되는 중요한 용어는 아래와 같다.

• CPU burst: 프로그램 수행 중에 연속적으로 CPU를 사용하는 구간
• I/O burst: 프로그램 수행 중에 I/O 완료를 기다리며 CPU 사용이 블락되는 구간

CPU 스케줄링의 단위는 CPU burst이다. 따라서 CPU burst에 따라 스케줄링 기법이 달라져야 한다. 

 

 

CPU 스케줄러 (= short-term scheduler)

CPU 스케줄러는 CPU가 idle한 상태일 때, 레디 큐(ready queue)에서 (이미 순서가 정해진) 우선순위가 가장 높은 프로세스에게 CPU를 할당하는 것이다. 즉, CPU 스케줄러는 프로세스 간 우선순위를 설정하는 것이 아니라, 이미 순서가 정해져있는 FIFO 형태의 레디 큐에서 프로세스를 가져와 CPU를 할당하는 것 뿐이다. 레디 큐에 프로세스를 하나씩 넣을 때 순서를 정하는 작업은 long-term scheduler의 역할이며, long-term scheduler에서 우선 순위가 정해지면 그 순서에 따라 레디 큐에 넣는다.

 

선점적 스케줄링

CPU 스케줄링은 아래의 경우에 대해 결정을 내려야한다.

1. running → waiting
2. running → ready
3. waiting → ready
4. running → terminate

 

이 중에서 1, 4 경우에는 선택의 여지가 없다. 1의 경우 I/O 이벤트가 발생하면 waiting 상태로 넘어가는 것이고, 4의 경우 프로세스 실행이 종료 되는 것이기 때문이다. 이러한 경우를 비선점적(non-preemptive) 또는 협력적(cooperative)이라고 표현한다. 비선점적인 경우에는 하나의 프로세스가 실행되면 이 프로세스가 자진해서 실행을 그만둔다거나 종료하기 전까지 실행이 멈추지 않는다. 이 외의 경우에 대해서는 선점적(preemptive)이라고 말한다. 선점적인 경우에는 지금 실행하고 있는 프로세스를 계속 실행하게 둬야하는지 또는 다른 프로세스로 교체해야하는지에 대해 결정을 내려야만 한다. 요약하자면 아래와 같다.

• 선점적 스케줄링 (Preemptive scheduling): 현재 실행 중인 프로세스에 인터럽트를 걸어서 ready 상태로 이동시키는 것을 말한다. 우선순위가 높은 프로세스들이 빠르게 처리를 원할 때 유용하다. 
• 비선점적 스케줄링 (Nonpreemptive scheduling): 다른 프로세스에 할당된 자원을 빼앗을 수 없는 스케줄링이다.

 

디스패처 (Dispatcher)

스케줄러에 의해 선택된 (다음으로 실행될) 프로세스와 현재 실행 중인 (실행이 중단되고 나갈) 프로세스의 컨텍스트를 교환하는, 컨텍스트 스위칭을 하는 주체이다. 디스패처에 의해 컨텍스트 스위칭하는데 드는 시간을 디스패치 지연 시간(dispatch latency)이라고 한다.

 

스케줄링 기준

• CPU 이용률 (CPU utilization): 전체 시스템 시간 중 CPU가 작업을 처리하는 시간의 비율
• 처리량/작업 처리율 (Throughput): 단위 시간동안 시스템이 수행시키는 프로세스의 개수
• 응답 시간 (Response time): 요청 후 응답이 오기 시작할 때까지의 시간
• 대기 시간 (Waiting time): 프로세스가 레디 큐(ready queue) 내에서 대기하는 시간의 총합
• 총처리 시간/반환 시간 (Turnaround time): 프로세스가 시작해서 끝날 때까지 걸리는 시간

 

스케줄링 정책

• First-Come First-Serve Scheduling, FCFS
• Round Robin Scheduling, RR
• Adaptive Scheduling
• Priority Scheduling
• Shortest-Job-First Scheduling, SJF
• Shortest Remaining Time First Scheduling, SRTF
• Highest Response-Rate Next Scheduling, HRN
• Multilevel Queue Scheduling
• Multilevel Feedback-Queue Scheduling, MFQS
• Fair Sharing Scheduling
• Completely Fair Sharing Scheduling, CFS
• Real-Time CPU Scheduling

 

First-Come First-Serve Scheduling, FCFS

먼저 들어온 프로세스부터 CPU를 사용할 수 있게 해주는 방식으며 스케줄링 단위는 CPU burst이다. 이는 비선점적인 스케줄링이기 때문에 CPU burst가 매우 긴 프로세스가 있을 경우 매우 비효율적이다. 이같은 문제를 해결하기 위해서 타이머 인터럽트를 둬서 일정 시간이 지나면 다음 프로세스가 CPU를 사용할 수 있게 한다. 이러한 방법이 아래에서 배울 라운드 로빈 스케줄링(round robin scheduling)이다.

 

FCFS 알고리즘을 사용할 경우, 아래와 같은 상황을 생각해보자.

• P1의 CPU burst time: 24ms
• P2의 CPU burst time: 3ms
• P3의 CPU burst time: 3ms

 

만약 P1이 제일 먼저 CPU를 점령하게 된다면 평균 대기 시간은 (0 + 24 + 27) / 3 = 17.0ms가 된다.

 

반면, 위의 경우에는 평균 대기 시간이 (0 + 3 + 6) . 3 = 3.0ms이다. 총 실행 시간(total running time)은 같지만 두번째의 경우는 두 개의 프로세스를 훨씬 더 빨리 끝낼 수 있으며 각 프로세스의 대기 시간이 짧다는 장점이 있다.

 

Round Robin Scheduling, RR

기본적으로 FIFO 스케줄링인데 타이머가 적용된 것이다. 때문에 선점적 스케줄링 방식이다. 타이머 내에 CPU 사용을 마치지 못하면 ready 상태로 전환된다. 이 때 레디 큐의 맨 마지막으로 들어간다. RR에서 CPU를 제공하는 일정 시간인 time quantum(=time slice)을 얼마로 잡아야할지 생각해야 한다. Time quantum 값이 아주 길면 FIFO 방식과 유사해진다. 반대로 time quantum이 너무 짧으면 잦은 컨텍스트 스위칭 때문에 CPU idle time이 길어진다. RR은 다른 알고리즘에 비해 대기 시간이 길어질 수 있다는 단점이 있으나 모든 프로세스들이 CPU를 공평하게 사용할 수 있다는 장점이 있다.

• P1의 CPU burst time: 24ms
• P2의 CPU burst time: 3ms
• P3의 CPU burst time: 3ms

 

평균 대기 시간은 5.66?

 

 

dfdf

 

dd

 

Adaptive Scheduling

CPU의 워크로드 특성에 따라 time quantum 값을 동적으로 바꿔주는 기법이다.

• CPU-bound 프로세스: 대부분의 시간이 CPU 연산을 하는데 사용되는 프로세스이다. 이런 경우 time quantum 값을 길게 주는 것이 좋다.
• I/O-bound 프로세스: 대부분의 시간을 I/O 처리하는데 사용되는 프로세스이다. 이런 경우 time quantum 값을 짧게 주는 것이 좋다.

 

프로세스가 CPU-bound인지 I/O-bound인지 알려면 어떻게 해야할까? Time quantum을 다 사용했는데도 계속 CPU 수행을 원하면 CPU-bound일 확률이 높다. 반대로 time quantum이 끝나기 전에 CPU 사용을 중단하는 프로세스인 경우 I/O-bound일 확률이 높다.

 

Priority Scheduling

최고 우선순위의 프로세스에게 CPU를 할당하는 방법이다. 선점적 및 비선점적 방식에 모두 적용이 가능하다. 우선순위를 할당하는 방법으로는 내부적인 방법과 외부적인 방법으로 나뉜다. 내부적인 방법은 OS가 평균 burst time, 시스템 자원 사용 등 커널에 영향이 가능 요소들을 활용해서 우선순위를 할당하는 방법이다. 외부적인 방법으로는 유저가 직접 우선순위를 정하는 방법이다. 우선순위가 높은 프로세스들이 계속 들어오면 우선순위가 낮은 프로세스들은 CPU 할당을 받지 못하는 starvation 상태에 빠질 수 있다. 이 방식을 해결하기 위해서 aging 기법을 사용한다. aging은 프로세스가 CPU를 기다리는 시간에 비례하여 우선순위를 점차적으로 높이는 방법이다.

 

아래와 같은 상황일 때, 평균 대기 시간은 (0 + 1 + 6 + 16 + 18) / 5 = 8.2ms이다. 

• P1의 CPU burst time: 10ms, Priority: 3
• P2의 CPU burst time: 1ms, Priority: 1
• P3의 CPU burst time: 2ms, Priority: 4
• P4의 CPU burst time: 1ms, Priority: 5
• P5의 CPU burst time: 5ms, Priority: 2

 

 

Shortest-Job-First Scheduling, SJF

CPU burst time이 가장 짧은 프로세스부터 CPU를 할당해주는 방법며 일종의 priority scheduling 기법이다. 스케줄링 단위는 CPU burst이다. 이상적으로 프로세스들의 대기 시간이 가장 짧으나, CPU burst를 미리 정확하게 예측하는 것이 불가능하기 때문에 사실상 SJF를 구현하는 것은 불가능하다. 그러나 대략적으로 adaptive scheduling에서 언급한 CPU-bound 프로세스인지 I/O-bound 프로세스인지 예측하는 방법을 사용해서 유사 SJF를 구현해볼 순 있다. 이상적인 구현이 가능하다고 하더라도 CPU burst time이 짧은 프로세스들에게 CPU를 먼저 주기 때문에 CPU burst time이 긴 프로세스들은 영원히 CPU를 할당받을 수 없는 starvation 상태에 도달할 수 있다. SJF는 선점적 또는 비선점적 스케줄링이 모두 가능하다. 보통 SJF 알고리즘이 선점적 스케줄링으로 사용된다면 SRTF 스케줄링이라고 부른다.

 

아래와 같은 상황일 때, 평균 대기 시간은 (0 + 3 + 9 + 16) / 4 = 7.0ms로 FCFS와 비교했을 때 아주 짧다.

• P1의 CPU burst time: 6ms
• P2의 CPU burst time: 8ms
• P3의 CPU burst time: 7ms
• P4의 CPU burst time: 3ms

 

 

Shortest Remaining-Time First Scheduling, SRTF

SJF의 선점적 스케줄링 방식이다. 프로세스가 CPU를 사용하고 있을 때, 다른 프로세스의 CPU burst time이 더 짧다면 컨텍스트 스위칭이 일어난다. SRTF 스케줄링이 일어나는 시점은 현재 수행 중인 태스크가 종료되거나 새로운 태스크가 생성되거나 깨어날 때이다.

 

평균 대기 시간은 ((5-3) + (10-1) + (17-2)) / 4 = 26 /4 = 6.5ms (7.75ms SJF, 8.75 FCFS)

• P1의 CPU burst time: 8ms, Arrival time: 0
• P2의 CPU burst time: 4ms, Arrival time: 1
• P3의 CPU burst time: 9ms, Arrival time: 2
• P4의 CPU burst time: 5ms, Arribal time: 3

 

 

Highest Response-Rate Next Scheduling, HRN

SJF 알고리즘의 단점은 프로세스의 CPU burst가 긴 경우 starvation이 발생할 수 있는 것이다. 이를 보완하기 위해 비선점적 스케줄링인 HRN 알고리즘이 등장했다. HRN 알고리즘은 우선순위를 사용하는데, 우선순위는 (CPU burst time + CPU waiting time) / CPU burst time이다. CPU burst time이 분모에 있기 때문에 CPU burst time이 짧은 프로세스가 우선순위가 높다. 하지만 CPU waiting time이 분자에 있기 때문에 CPU burst time이 긴 작업도 CPU waiting time이 긴 경우에는 우선순위가 높아질 수 있다.

 

Multilevel Queue Scheduling

df

 

Multilevel Feedback-Queue Scheduling

Run queue가 멀티레벨로 존재하며 큐마다 우선순위가 다르다. 새로운 프로세스가 생성이 되면 가장 우선 순위가 높은 큐에 들어간다. 그 곳에서 RR을 한다. RR을 하다가 자신의 time quantum보다 빨리 끝나면 계속 그 큐에 머물로 그렇지 않으면 우선 순위가 한 단계 낮은 큐로 강등된다. 우선 순위가 낮아지는 큐일수록 TS 사이즈가 커진다.

 

 

Fair Sharing Scheduling

Bandwidth scheduling과 proportional share sheduling과 같은 말이다. 대기 중인 프로세스들에게 정해진 비율에 따라 CPU의 Bandwidth를 분배하는 스케줄링 기법이다. 우선순위가 높은 프로세스들은 많은 bandwidth를 가져간다.

 

performance isolation: CPU를 많이 차지할 것 같은 application이 들어왔을 때 해당 application 영향을 제한시키는 것이다.

performance isolation이나 multimedia를 위한 bandwidth scheduling의 필요성이 증가돼서 fair sharing scheduling이 생겨났다.

제일 먼저 리눅스에 제시된 알고리즘은 rotating staircase deadline scheduling 기법이다. 이는 MLFQ랑 비슷하나 데드라인 값에 따라 큐의 중간, 앞, 뒤에 다 들어갈 수 있다는 점이 추가되었다. 예를 들어 한 프로세스가 받아야할 bandwidth가 30%라고 하자. 그런데 이번 턴에 15%밖에 받지 못했다. 그럼 이 프로세스는 데드라인이 짧기 때문에 앞쪽 큐로 들어가 곧바로 CPU를 받을 수 있게 한다. 또 다른 예롤 이 프로세스가 35%나 받았다고 하자. 이 프로세스는 데드라인을 뒤로 해서 나중에 받게 한다.

 

Completely Fair Scheduling, CFS

현재 리눅스는 CFS(Completely Fair Scheduling) 기법을 사용한다.

 

Real-Time CPU Scheduling

dfsdf