[Operating System Concepts 10th] 5. CPU Scheduling 리뷰 (1)

2022-08-18 7 분 소요

본 글은 Operating System Concepts 10th (운영체제) 책을 보며 내용을 개인 공부에 목적으로 정리했습니다.
이전에 운영체제 관련 강의들을 들으면서 정리한 시리즈 글들이 있는데,
지식을 습득하는 데 있어 가장 느리지만 가장 빠른 방법이 원본책을 자세히 보는 것이라 생각됩니다.
책 내용들을 최대한 이해하기 위해 거의 모든 내용을 담고 있습니다.

책 pdf 링크 : Operating System Concepts 10th Edition by Abraham Silberschatz Peter B Galvin Greg Gagne pdf free download
연습 문제 정답지 : Solutions of Practice Exercises, Tenth Edition of Operating System Concepts, AVI SILBERSCHATZ

5. CPU Scheduling

운영체제는 CPU를 프로세스 간에 교환함으로써, 컴퓨터를 보다 생산적으로 만든다.
프로세스 스케줄링과 스레드 스케줄링 용어는 상호 교환적으로 사용되는데, 일반적인 스케줄링 개념을 논의하는 경우에는 프로세스 스케줄링을 사용하고 스레드에 국한된 개념을 가리키는 경우에는 스레드 스케줄링 용어를 사용하기로 한다.
- 스케줄링(schedule) 한다 : 프로세스가 교체된다. 즉, 문맥 교환(context switching)이 일어나는 것을 말한다. ¹

목표
- 다양한 CPU 스케줄링 알고리즘을 설명한다.
- 스케줄링 기준에 따라 CPU 스케줄링 알고리즘을 평가한다.
- 멀티 프로세서 및 멀티 코어 스케줄링과 관련된 쟁점을 설명한다.
- 다양한 실시간 스케줄링 알고리즘을 설명한다.
- CPU 스케줄링 알고리즘을 평가하기 위해 모델링 및 시뮬레이션을 적용한다.
- 여러 가지 다른 CPU 스케줄링 알고리즘을 구현하는 프로그램을 설계한다.

5.1 Basic Concepts

코어가 하나인 시스템에서는 한순간에 오직 하나의 프로세스만이 실행될 수 있다.
나머지 프로세스는 CPU의 코어가 가용(free) 상태가 되어 다시 스케줄될 수 있을 때까지 기다려야 한다.
멀티 프로그래밍의 목적은 CPU 이용률을 최대화하기 위해 항상 실행 중인 프로세스를 가지게 하는 데 있다.
하나의 프로세스는 어떤 I/O 요청이 완료되기를 기다려야만 할 때까지 실행된다.
멀티 프로그래밍에서는 시간을 생산적으로 활용하기 위해 어느 한순간에 다수의 프로세스를 메모리 내에 유지한다.
어떤 프로세스가 대기해야 할 경우, 운영체제는 CPU를 그 프로세스로부터 회수해 다른 프로세스에 할당한다.
- 다른 프로세스가 CPU 사용을 양도받을 수 있다.

5.1.1 CPU-I/O Burst Cycle

프로세스 실행은 CPU 실행과 I/O 대기의 사이클로 구성된다.
- 프로세스들은 이들 두 상태 사이를 교대로 왔다 갔다 한다.
프로세스 실행은 CPU 버스트(burst)로 시작된다. 뒤이어 I/O 버스트가 발생하고 이를 반복 진행된다.
- 버스트(burst) : 특정 기준에 따라 한 단위로서 취급되는 연속된 신호나 데이터의 모임. 즉, 입출력 요청을 위해 CPU 사용을 사용했다가 쉬었다가를 반복한다. ¹

위의 그림은 CPU 버스트들의 지속 시간을 광범위하게 측정한 것이다.
대체로 짧은 CPU 버스트가 많이 있으며, 긴 CPU 버스트는 적은 빈도수를 보인다.

5.1.2 CPU Scheduler

CPU가 유휴 상태가 될 때마다, 운영체제는 준비 큐(ready queue)에 있는 프로세스 중에서 하나를 선택해 실행해야 한다.
선택 절차는 CPU 스케줄러(scheduler)에 의해 수행된다.
스케줄러는 실행 준비가 되어 있는 메모리 내의 프로세스 중에서 선택하여, 이들 중 하나에게 CPU를 할당한다.

준비 큐는 FIFO 큐, priority 큐, 트리 또는 단순히 순서가 없는 연결 리스트로 구현할 수 있다.
개념적으로 볼 때 준비 큐에 있는 모든 프로세스는 CPU에게 실행될 기회를 기다리며 대기하고 있다.
큐에 있는 레코드들은 일반적으로 프로세스들의 PCB들이다.

5.1.3 Preemptive and Non-preemptive Scheduling

CPU 스케줄링 결정은 다음 4가지 상황에서 발생할 수 있다.
1. 한 프로세스가 실행(running) 상태에서 대기(waiting) 상태로 전환될 때
2. 프로세스가 실행(running) 상태에서 준비(ready) 완료 상태로 전환될 때
3. 프로세스가 대기(waiting) 상태에서 준비(ready) 완료 상태로 전환될 때
4. 프로세스가 종료(terminate)할 때

비선점형(non-preemptive) 스케줄링 : 상황 1과 상황 2의 경우에 스케줄링 면에서 선택의 여지가 없다. 실행을 위해 새로운 프로세스가 반드시 선택되어야 한다.
선점형(preemptive) 스케줄링 : 상황 1, 2뿐만 아니라 상황 3, 4의 경우에도 스케줄링이 발생할 수 있는 방식이다. 동작하고 있던 프로세스를 강제로 멈추고 스케줄링할 수 있는 방법.
- 데이터가 다수의 프로세스에 의해 공유될 때 경쟁 조건을 초래할 수 있다.
비선점형(non-preemptive) 커널은 문맥 교환을 하기 전에 시스템 콜이 완료되거나 입출력 완료를 기다리며 프로세스가 블록되기를 기다린다.
선점형(preemptive) 커널에는 공유 커널 데이터 구조에 액세스 할 때 경쟁 조건(race condition)을 방지하기 위해 mutex 락과 같은 기법이 필요하다.

인터럽트(interrupt)는 어느 시점에서건 일어날 수 있고, 커널에 의해서 항상 무시될 수는 없기 때문에, 인터럽트에 의해서 영향을 받는 코드 부분은 반드시 동시 사용으로부터 보호되어야 한다.

5.1.4 Dispatcher

디스패처(dispatcher)는 CPU 스케줄링 기능에 포함된 또 하나의 요소로, CPU 코어의 제어를 CPU 스케줄러가 선택한 프로세스에 주는 모듈이며 다음과 같은 작업을 포함한다.
1. 한 프로세스에서 다른 프로세스로 문맥을 교환하는 일
2. 사용자 모드로 전환하는 일
3. 프로그램을 다시 시작하기 위해 사용자 프로그램의 적절한 위치로 이동(jump)하는 일

디스패처는 모든 프로세스의 문맥 교환 시 호출되므로, 가능한 한 최고로 빨리 수행되어야 한다.
디스패처가 하나의 프로세스를 정지하고 다른 프로세스의 수행을 시작하는 데까지 소요되는 시간을 디스패치 지연(dispatch latency)라 한다.

5.2 Scheduling Criteria

CPU 스케줄링 알고리즘들은 서로 다른 특성을 가지고 있으며, 이를 비교하는 데 사용되는 기준은 다음을 포함한다.

CPU 이용률(utilization) : 가능한 한 CPU를 최대한 바쁘게 유지하기를 원한다.
처리량(throughput) : 작업량 측정의 한 방법은 단위 시간당 완료된 프로세스의 개수로, 이것을 처리량이라고 한다.
- CPU가 프로세스를 수행하느라고 바쁘다면, 작업이 진행되고 있는 것이다.
총처리 시간(turnaround time) : 프로세스의 제출 시간과 완료 시간의 간격을 총처리 시간이라고 한다.
- 총처리 시간은 준비 큐에서 대기한 시간, CPU에서 실행하는 시간, 그리고 I/O 시간을 합한 시간이다.
대기 시간(waiting time) : 대기 시간은 준비 큐에서 대기하면서 보낸 시간의 합이다.
- 스케줄링 알고리즘은 단지 프로세스가 준비 큐에서 대기하는 시간의 양에만 영향을 준다.
응답 시간(response time) : 응답 시간은 하나의 요구를 제출한 후 첫 번째 응답이 나올 때까지의 시간

CPU 이용률과 처리량을 최대화하고 총처리 시간, 대기 시간, 응답 시간을 최소화하는 것이 바람직하다.

5.3 Scheduling Algorithms

CPU 스케줄링은 준비 큐에 있는 어느 프로세스에 CPU 코어를 할당할 것인지를 결정하는 문제를 다룬다.
이러한 스케줄링 알고리즘은 처리 코어가 하나뿐이라고 가정하고 설명한다.
- 즉, 한 개의 처리 코어를 가진 CPU가 한 개인 시스템이므로 한 번에 하나의 프로세스만 실행할 수 있다.

이미지출처 ²

5.3.1 First-Come, First-Served(FCFS) Scheduling

이 방법에서 CPU를 먼저 요청하는 프로세스가 CPU를 먼저 할당받는다.
- FCFS 알고리즘은 non-preemptive이다.
선입 선처리 정책의 구현은 선입선출(FIFO) 큐로 쉽게 관리할 수 있다.
프로세스가 준비 큐에 진입하면, 이 프로세스의 프로세스 제어 블록(PCB)을 큐의 끝에 연결한다.
CPU가 가용 상태가 되면, 준비 큐의 앞부분에 있는 프로세스에 할당된다.
- 이 실행 상태의 프로세스는 이어 준비 큐에서 제거된다.

프로세스들이 $P_1$, $P_2$, $P_3$ 순으로 도착하고, FCFS 순으로 서비스받는다면, 다음의 간트(Gantt) 차트에 보인 결과를 얻는다.
- 간트 차트(gantt chart) : 시간을 기준으로 하여 활동(작업 또는 이벤트)을 표시하는 프로젝트 관리 방법 중 하나이다. ³

Wiating time for $P_1$ = 0, $P_2$ = 24, $P_3$ = 27
Average waiting time : (0 + 24 + 27)/3 = 17

호위 효과(convoy effect) : 모든 다른 프로세스들이 하나의 긴 프로세스가 CPU를 양도하기를 기다리는 것
- 이 효과는 짧은 프로세스들이 먼저 처리되도록 허용될 때보다 CPU와 장치 이용률이 저하되는 결과를 낳는다.

5.3.2 Shortest-Job-First(SJF) Scheduling

SJF 알고리즘은 각 프로세스에 다음 CPU 버스트 길이를 연관시킨다.
CPU가 이용 가능해지면, 가장 작은 다음 CPU 버스트를 가진 프로세스에 할당한다.
두 프로세스가 동일한 길이의 다음 CPU 버스트를 가지면, 순위를 정하기 위해 FCFS 스케줄링을 적용한다.

SJF 스케줄링을 이용하면, 이들 프로세스를 다음 간트 차트와 같이 스케줄이 된다.

Waiting Time for $P_1$=3, $P_2$=16, $P_3$=9, $P_4$=0
Average Waiting Time: (3+16+9+0)/4=7

SJF 알고리즘이 최적이긴 하지만, 다음 CPU 버스트의 길이를 알 방법이 없기 때문에 CPU 스케줄링 수준에서는 구현할 수 없다.
한 가지 접근 방식은 SJF 스케줄링과 근사한 방법을 사용하는 것이다.
- 다음 CPU 버스트의 길이를 알 수는 없으나, 그 값을 예측할 수는 있다.
- 다음 CPU 버스트 길이의 근삿값을 계산해, 가장 짧은 예상 CPU 버스트를 가진 프로세스를 선택한다.
- 다음 CPU 버스트는 일반적으로 측정된 이전의 CPU 버스트들의 길이를 지수 평균한 것으로 예측한다.

SJF 알고리즘은 preemptive이거나 non-preemptive 일 수 있다.
앞의 프로세스가 실행되는 동안 새로운 프로세스가 준비 큐에 도착하면 선택이 발생한다.
Nonpreemptive : 일단 CPU를 잡으면 이번 CPU burst가 완료될 때까지 CPU를 선점(preemption)당하지 않는다.
Preemptive : 현재 수행중인 프로세스의 남은 burst time보다 더 짧은 CPU burst time을 가지는 새로운 프로세스가 도착하면 CPU를 빼앗긴다.
- 이 방법을 Shortest-Remaining-Time-First (SRTF)이라고도 부른다.

프로세스들이 위에 보인 시간에 준비 큐에 도착하고, 표시된 버스트 시간을 요구한다면, 결과로 얻어지는 선점형 SJF 스케줄은 다음의 간트 차트로 묘사될 수 있다.

Waiting Time for $P_1$=(10-1)=9, $P_2$=(1-1)=0, $P_3$=(17-2)=15, $P_4$=(5-3)=2
Average Waiting Time: (9+0+15+2)/4 = 6.5

5.3.3 Round-Robin(RR) Scheduling

라운드 로빈(RR) 스케줄링 알고리즘은 FCFS 스케줄링과 유사하지만 시스템이 프로세스들 사이를 옮겨 다닐 수 있도록 선점(preemption)이 추가된다.
- 시간 할당량(time quantum) 또는 타임슬라이스(time slice)라고 하는 작은 단위의 시간을 정의한다.
CPU 스케줄러는 준비 큐를 돌면서 한 번에 한 프로세스에 한 번의 시간 할당량 동안 CPU를 할당한다.

라운드 로빈 스케줄링을 구현하기 위해, 다시 준비 큐가 FCFS 큐로 동작하게 만든다.
새로운 프로세스들은 준비 큐의 tail 부분에 추가된다.
CPU 스케줄러는 준비 큐에서 첫 번째 프로세스를 선택해 한 번의 시간 할당량 이후에 인터럽트를 걸도록 타이머(timer)를 설정한 후, 프로세스를 디스패치(dispatch)한다.

2가지 경우 중 하나가 발생한다.
프로세스의 CPU 버스트가 한 번의 시간 할당량보다 작을 경우, 프로세스 자신이 CPU를 자발적으로 방출할 것이다.
- 스케줄러는 그 후 준비 큐에 있는 다음 프로세스로 진행할 것이다.
현재 실행 중인 프로세스의 CPU 버스트가 한 번의 시간 할당량보다 긴 경우, 타이머가 끝나고 운영체제에 인터럽트를 발생할 것이다.
- 문맥 교환이 일어나고 실행하던 프로세스는 준비 큐의 tail에 넣어진다.
- 그 후 CPU 스케줄러는 준비 큐의 다음 프로세스를 선택할 것이다.

시간 할당량을 4밀리초로 한다면, RR 스케줄의 결과는 다음과 같다.

Waiting Time for $P_1$=(10-4)=5, $P_2$=4, $P_3$=7
Average Waiting Time: (5+4+7)/3 = 5.66

RR 스케줄링 알고리즘은 preemptive이다.
준비 큐에 n개의 프로세스가 있고 시간 할당량이 q이면, 각 프로세스는 최대 q시간 단위의 덩어리로 CPU 시간의 1/n을 얻는다.
각 프로세스는 자신의 다음 시간 할당량이 할당될 때까지 (n-1)xq 시간 이상을 기다리지 않는다.

RR 알고리즘의 성능은 시간 할당량(q)의 크기에 많은 영향을 받는다.
- q가 크면, FCFS와 같다.
- q가 작다면, 문맥 교환(context switch) 오버헤드가 커진다.

총처리 시간(turnaround time) 또한 시간 할당량의 크기에 좌우된다.

5.3.4 Priority Scheduling

SJF 알고리즘은 일종의 우선순위(priority) 스케줄링이다.
- 우선순위가 각 프로세스들에 연관되어 있으며, CPU는 가장 높은 우선순위를 가진 프로세스에 할당된다.
우선순위는 내부적(internally) 또는 외부적으로(externally) 정의될 수 있다.
내부적으로 정의된 우선순위는 프로세스의 우선순위를 계산하기 위해 어떤 측정 가능한 양들을 사용한다.
- ex. 시간 제한, 메모리 요구, 오픈 파일 수, 평균 I/O 버스트의 평균, CPU 버스트에 대한 비율 등이 우선순위의 계산에 사용된다.
외부적 우선순위는 프로세스의 중요성, 컴퓨터 사용을 위해 지불되는 비용의 유형과 양, 그 작업을 후원하는 부서 그리고 정치적인 요인 등과 같은 운영체제 외부적 기준에 의해 결정된다.

우선순위 스케줄링은 preemptive이거나 non-preemptive이 될 수 있다.
우선순위 스케줄링의 주요 문제는 무한 블록(indefinite blocking) 또는 기아 상태(starvation)이다.
- 실행 준비는 되어 있으나 CPU를 사용하지 못하는 프로세스는 CPU를 기다리면서 블록된 것으로 간주할 수 있다.
- 그리고 낮은 우선순위 프로세스들이 CPU를 무한히 대기하는 경우가 발생한다.
낮은 우선순위의 프로세스들이 무한히 블록되는 문제에 대한 한 가지 해결책은 노화(aging)이다.
노화(aging)은 오랫동안 시스템에서 대기하는 프로세스들의 우선순위를 점진적으로 증가시킨다.

5.3.5 Multilevel Queue Scheduling

우선순위와 RR 스케줄링을 사용할 때 모든 프로세스가 싱글 큐에 배치되고 스케줄러는 우선순위가 가장 높은 프로세스를 선택하여 실행시킬 수 있다.
- 큐가 관리되는 방식에 따라 우선순위가 가장 높은 프로세스를 결정하기 위해 O(n) 검색이 필요할 수 있다.

멀티레벨 큐(multilevel queue) 방법은 우선순위 스케줄링이 라운드 로빈과 결합한 경우에도 효과적이다.
우선순위가 가장 높은 큐에 여러 프로세스가 있는 경우 라운드 로빈 순서로 실행된다.

프로세스 유형에 따라 프로세스를 여러 개의 개별 큐로 분할하기 위해 멀티레벨 큐 스케줄링 알고리즘을 사용할 수도 있다.
foreground (interactive) 프로세스와 background (batch) 프로세스를 구분한다.
- ex. background 큐는 FCFS 알고리즘에 의해 스케줄 되는 반면, foreground 큐는 RR 알고리즘에 의해 스케줄 될 수 있다.

5.3.6 Multilevel Feedback Queue Scheduling

멀티레벨 큐(multivelevel queue) 스케줄링 알고리즘에서는 일반적으로 프로세스들이 시스템 진입 시에 영구적으로 하나의 큐에 할당된다.
이와는 대조적으로, 멀티레벨 피드백 큐(multilevel feedback queue) 스케줄링 알고리즘에서는 프로세스가 큐들 사이를 이동하는 것을 허용한다.

프로세스들을 CPU 버스트 성격에 따라서 구분한다.
- 어떤 프로세스가 CPU 시간을 너무 많이 사용하면, 낮은 우선순위의 큐로 이동된다.
이 방법에서는 I/O 중심의 프로세스와 대화형 프로세스들을 높은 우선순위의 큐에 넣는다.
마찬가지로 낮은 우선순위의 큐에서 너무 오래 대기하는 프로세스는 높은 우선순위의 큐로 이동할 수 있다.
- 이러한 노화(aging) 형태는 기아(starvation) 상태를 예방한다.

일반적으로, 멀티레벨 피드백 큐 스케줄러는 다음의 파라미터에 의해 정의된다.
1. 큐(queue)의 개수
2. 각 큐를 위한 스케줄링 알고리즘
3. 한 프로세스를 높은 우선순위 큐로 올려주는 시기를 결정하는 방법
4. 한 프로세스를 낮은 우선순위 큐로 강등시키는 시기를 결정하는 방법
5. 프로세스에 서비스가 필요할 때 프로세스가 들어갈 큐를 결정하는 방법

References

KakaoTalk Twitter Facebook LinkedIn

poeun 🔅