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

2022-08-18 14 분 소요

본 글은 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

이 글은 Operating System Concepts 10th의 5장 CPU Scheduling을 정리한 글이다. 한정된 CPU를 여러 프로세스가 나누어 쓰도록 순서를 정하는 기본 개념과 평가 기준을 세우고, 다양한 CPU 스케줄링 알고리즘의 동작 원리와 간트 차트 기반 대기 시간 계산을 비교한다. 나아가 프로세스 단위를 넘어 최신 시스템의 실행 단위인 커널 스레드 스케줄링과 멀티 프로세서·멀티 코어 환경에서의 부하 균등화 및 프로세서 선호도까지 단계적으로 살펴본다.

이 글에서 다루는 것
- CPU 버스트와 I/O 버스트 사이클, 선점 및 비선점 스케줄링의 기본 개념과 디스패처의 역할
- CPU 이용률, 처리량, 총처리 시간, 대기 시간, 응답 시간 등 스케줄링 평가 기준
- FCFS, SJF, RR, 우선순위, 멀티레벨 큐 및 멀티레벨 피드백 큐 스케줄링 알고리즘
- 프로세스 내부(PCS)와 시스템 전체(SCS) 경합 범위에 따른 스레드 스케줄링
- SMP 환경에서의 대칭적 다중 처리 및 멀티 코어 프로세서의 메모리 스톨 은폐 기법
- 프로세서 간 부하 균등화(Push/Pull 이주)와 캐시 친화성을 고려한 프로세서 선호도(Processor Affinity)

5. CPU Scheduling

CPU 스케줄링은 결국 실행할 프로세스를 골라 CPU를 넘겨주는 일이다 — 그 개념과 다룰 범위는 아래와 같다.

운영체제는 CPU를 프로세스 간에 교환함으로써, 컴퓨터를 보다 생산적으로 만든다.
프로세스 스케줄링과 스레드 스케줄링 용어는 상호 교환적으로 사용되는데, 일반적인 스케줄링 개념을 논의하는 경우에는 프로세스 스케줄링을 사용하고 스레드에 국한된 개념을 가리키는 경우에는 스레드 스케줄링 용어를 사용하기로 한다.
- 스케줄링(schedule) 한다 : 프로세스가 교체된다. 즉, 문맥 교환(context switching)이 일어나는 것을 말한다. ¹
목표
- 다양한 CPU 스케줄링 알고리즘을 설명한다.
- 스케줄링 기준에 따라 CPU 스케줄링 알고리즘을 평가한다.
- 멀티 프로세서 및 멀티 코어 스케줄링과 관련된 쟁점을 설명한다.
- 다양한 실시간 스케줄링 알고리즘을 설명한다.
- CPU 스케줄링 알고리즘을 평가하기 위해 모델링 및 시뮬레이션을 적용한다.
- 여러 가지 다른 CPU 스케줄링 알고리즘을 구현하는 프로그램을 설계한다.

5.1 Basic Concepts

CPU 스케줄링의 바탕에는 코어 하나가 한순간에 하나의 프로세스만 실행한다는 제약이 있다 — 여기서는 그 제약이 만드는 기본 개념들을 정리한다.

코어가 하나인 시스템에서는 한순간에 오직 하나의 프로세스만이 실행될 수 있다.
나머지 프로세스는 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)할 때

주의: 비선점형과 선점형의 구분은 상황 1·2의 발생 여부가 아니라, 상황 3·4에서도 스케줄링(선점)이 가능한지에 있다.

비선점형(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 코어를 할당할 것인지를 결정하는 문제를 다룬다.
이러한 스케줄링 알고리즘은 처리 코어가 하나뿐이라고 가정하고 설명한다.
- 즉, 한 개의 처리 코어를 가진 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) : 시간을 기준으로 하여 활동(작업 또는 이벤트)을 표시하는 프로젝트 관리 방법 중 하나이다. ³

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

정리하면, FCFS는 도착한 순서를 그대로 지키므로 긴 작업 뒤에 짧은 작업이 밀리면 평균 대기 시간이 크게 늘어난다.

호위 효과(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 버스트 길이를 미리 알아야 한다는 전제가 붙는다.

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

정리하면, 같은 작업 집합이라도 선점형 SJF에서는 더 짧은 작업이 도착하는 순간 CPU를 넘겨주므로 평균 대기 시간이 7에서 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은 정해진 시간 할당량만큼씩 돌아가며 실행해 응답 시간을 보장하는 대신, 문맥 교환 비용을 함께 떠안는다.

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

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

주의: 멀티레벨 큐는 프로세스를 진입 시 하나의 큐에 고정하지만, 멀티레벨 피드백 큐는 큐 사이 이동을 허용한다는 점이 다르다.

프로세스들을 CPU 버스트 성격에 따라서 구분한다.
- 어떤 프로세스가 CPU 시간을 너무 많이 사용하면, 낮은 우선순위의 큐로 이동된다.
이 방법에서는 I/O 중심의 프로세스와 대화형 프로세스들을 높은 우선순위의 큐에 넣는다.
마찬가지로 낮은 우선순위의 큐에서 너무 오래 대기하는 프로세스는 높은 우선순위의 큐로 이동할 수 있다.
- 이러한 노화(aging) 형태는 기아(starvation) 상태를 예방한다.
일반적으로, 멀티레벨 피드백 큐 스케줄러는 다음의 파라미터에 의해 정의된다.
1. 큐(queue)의 개수
2. 각 큐를 위한 스케줄링 알고리즘
3. 한 프로세스를 높은 우선순위 큐로 올려주는 시기를 결정하는 방법
4. 한 프로세스를 낮은 우선순위 큐로 강등시키는 시기를 결정하는 방법
5. 프로세스에 서비스가 필요할 때 프로세스가 들어갈 큐를 결정하는 방법

단일 코어 환경에서 프로세스 단위로 CPU를 배분하는 고전적인 스케줄링 알고리즘을 살펴보았다면, 이제 현대 운영체제의 실제 실행 흐름으로 시야를 넓혀야 한다. 최신 OS에서 CPU를 할당받는 실제 주체는 프로세스가 아닌 스레드이며, 하드웨어 역시 단일 코어를 넘어 멀티 코어와 멀티 프로세서 구조로 진화했다. 이어지는 절에서는 사용자 수준 스레드와 커널 수준 스레드의 스케줄링 기법을 살펴보고, 멀티 코어 및 멀티 프로세서 시스템에서 발생하는 새로운 스케줄링 쟁점들을 정리한다.

5.4 Thread Scheduling

최신 운영체제에서 실제 스케줄 대상은 프로세스가 아니라 커널 수준 스레드이며, 사용자 수준 스레드는 커널 수준 스레드에 사상되어야 한다 — 이 절은 그 스케줄링 쟁점을 다룬다.

대부분 최신 운영체제에서는 스케줄 되는 대상은 프로세스가 아니라 커널 수준 스레드이다.
사용자 수준 스레드는 스레드 라이브러리에 의해 관리되고 커널은 그들의 존재를 알지 못한다.
사용자 수준 스레드는 궁극적으로 연관된 커널 수준 스레드에 사상되어야 한다.
이 절에서는 사용자 수준과 커널 수준 스레드의 스케줄링에 관한 쟁점을 탐구하고 Pthreads의 스케줄링 사례를 알아본다.

5.4.1 Contention Scope

스레드를 스케줄하는 경쟁 범위는 프로세스 내부와 시스템 전체 두 가지로 나뉘며, 각각 PCS와 SCS라 부른다.

사용자 수준과 커널 수준 스레드의 차이 중 하나는 그들이 어떻게 스케줄 되느냐에 있다.
다대일과 다대다 모델을 구현하는 시스템에서는 스레드 라이브러리는 사용자 수준 스레드를 가용한(available) LWP상에서 스케줄 한다.

이미지출처 ⁴

이러한 기법은 동일한 프로세스에 속한 스레드들 사이에서 CPU를 경쟁하기 때문에 프로세스-경쟁-범위(process-contention scope, PCS)로 알려져 있다.
우리가 스레드 라이브러리가 사용자 수준 스레드를 가용한 LWP상에서 스케줄(schedule) 한다고 말하는 경우, 스레드가 실제로 CPU상에서 실행(running) 중이라는 것을 의미하지 않는다.
실제로 CPU상에서 실행되기 위해서는 운영체제가 LWP의 커널 스레드를 물리적인 CPU 코어로 스케줄 하는 것을 필요로 한다.
CPU상에 어느 커널 스레드를 스케줄 할 것인지 결정하기 위해서 커널은 시스템-경쟁 범위(system-contention scope, SCS)를 사용한다.
- SCS 스케줄링에서의 CPU에 대한 경쟁은 시스템상의 모든 스레드 사이에서 일어난다.
- Windows와 Linux 같은 일대일 모델을 사용하는 시스템은 오직 SCS만을 사용하여 스케줄한다.

주의: PCS와 SCS는 모두 ‘경쟁 범위’지만, 전자는 프로세스 내부에서, 후자는 시스템 전체에서 CPU를 경쟁한다는 점이 다르다.

경쟁의 무대가 프로세스 안과 시스템 전체로 갈린다.

전형적으로, PCS는 우선순위에 따라 행해진다. 즉, 스케줄러는 가장 높은 우선순위를 가진 실행 가능한 프로세스를 선택한다.
사용자 수준 스레드의 우선순위는 프로그래머에 의해 지정되고 스레드 라이브러리에 의해 조정되지 않는다.
- 그러나 몇몇 스레드 라이브러리는 프로그래머가 스레드의 우선순위를 변경하는 것을 허용한다.
PCS는 통상 더 높은 우선순위의 스레드를 위하여 현재 실행 중인 스레드를 선점(preemptive)한다는 것을 주의해야 한다.

스레드 수준의 스케줄링 쟁점을 봤으니, 이제 CPU가 여러 개인 상황으로 넘어간다.

5.5 Multiple-Processor Scheduling

CPU가 여러 개면 스레드가 병렬로 실행될 수 있으므로 부하 공유가 가능해진다 — 이 절은 멀티 프로세서 스케줄링의 구조와 접근법을 다룬다.

만일 여러 개의 CPU가 사용 가능하다면, 여러 스레드가 병렬로 실행될 수 있으므로 부하 공유(load sharing)가 가능해진다.
멀티 프로세서는 여러 개의 물리적 프로세서를 제공하는 시스템을 말하며, 각 프로세서에는 하나의 싱글 코어 CPU가 포함되어 있다.
그러나 멀티 프로세서의 정의는 크게 발전했으며 최신 컴퓨팅 시스템에서는 다음 시스템 아키텍처들에 이것을 사용할 수 있다.
- 멀티 코어 CPU
- 멀티 스레드 코어
- NUMA 시스템
- 이기종(Heterogeneous) 멀티 처리

5.5.1 Approaches to Multiple-Processor Scheduling

멀티 프로세서 스케줄링에는 하나의 프로세서가 결정을 독점하는 비대칭 방식과 각 프로세서가 스스로 스케줄하는 대칭(SMP) 방식이 있다.

멀티 프로세서 시스템의 CPU 스케줄링에 관한 한 가지 해결 방법은 마스터 서버(master server)라는 하나의 프로세서가 모든 스케줄링 결정과 I/O 처리 그리고 다른 시스템의 활동을 취급하게 하는 것이다.
다른 프로세서들은 사용자 코드만을 수행하는데, 이러한 비대칭 멀티 프로세싱(asymmetric multiprocessing)는 오직 하나의 코어만 시스템 자료구조에 접근하여 자료 공유의 필요성을 배제하기 때문에 간단하다.
- 이 접근 방식의 단점은 마스터 서버가 전체 시스템 성능을 저하할 수 있는 병목이 된다는 것이다.
멀티 프로세서를 지원하기 위한 표준 접근 방식은 대칭 멀티프로세싱(symmetric multiprocessing, SMP)이며 각 프로세서는 스스로 스케줄링 할 수 있다.

이미지출처 ⁵
각 프로세서의 스케줄러가 준비 큐를 검사하고 실행할 스레드를 선택하여 스케줄링이 진행된다.
이는 스케줄 대상이 되는 스레드를 관리하기 위한 2가지 가능한 전략을 제공한다.
1. 모든 스레드가 공통 준비 큐에 있을 수 있다.
2. 각 프로세서는 자신만의 스레드 큐를 가질 수 있다.

2번째 옵션은 각 프로세서가 자신만의 실행 큐에서 스레드를 스케줄 할 수 있도록 허용하므로 공유 실행 큐와 관련되어 발생할 수 있는 성능 문제를 겪지 않는다.
따라서, SMP를 지원하는 시스템에서 가장 일반적인 접근 방식이다.
자신만의 프로세스별 큐가 있으면 캐시 메모리를 보다 효율적으로 사용할 수 있다.

결국 준비 큐를 어디에 두느냐의 문제다.

5.5.2 Multicore Processors

코어 하나에 물리 자원이 공유되는 멀티 코어 프로세서에서는 메모리 스톨을 어떻게 숨기느냐가 핵심이다 — 거친/세밀한 멀티 스레딩이 그 해법이다.

SMP 시스템은 다수의 물리 프로세서를 제공함으로써 다수의 프로세스가 병렬로 실행되게 한다.
그러나 현대 컴퓨터 하드웨어는 동일한 물리적인 칩 안에 여러 개의 처리 코어를 장착하여 멀티 코어 프로세서(multicore processor)가 된다.
멀티코어 프로세서를 사용하는 SMP 시스템은 각 CPU가 자신의 물리 칩을 가지는 시스템과 비교해 속도가 빠르고 적은 전력을 소모한다.

프로세서가 메모리에 접근할 때 데이터가 가용해지기를 기다리면서 많은 시간을 허비하는, 메모리 스톨(memory stall)이라고 하는 이 상황은 최신 프로세서가 메모리보다 훨씬 빠른 속도로 작동하기 때문에 자주 발생한다.
Figure 5.12 같은 시나리오에서 프로세서는 메모리의 데이터를 사용할 수 있을 때까지 기다리느라 최대 50%의 시간을 허비할 수 있다.

이러한 상황을 해결하기 위해 최근의 많은 하드웨어 설계는 멀티 스레드 처리 코어를 구현하였다.
이러한 설계에서 하나의 코어에 2개 이상의 하드웨어 스레드가 할당된다.
- 이렇게 하면 메모리를 기다리는 동안 하나의 하드웨어 스레드가 중단되면 코어가 다른 스레드로 전환할 수 있다.

운영체제 관점에서 각 하드웨어 스레드는 명령어 포인터 및 레지스터 집합과 같은 구조적 상태를 유지하므로 소프트웨어 스레드를 실행할 수 있는 논리적 CPU로 보인다.
- 이 기술을 칩 멀티 스레딩(chip multithreading, CMT)라 부른다.
일반적으로 프로세서를 멀티 스레드화 하는 데에는 거친(coarse-grained) 멀티 스레딩과 세밀한(fine-grained) 멀티 스레딩의 2가지 방법이 있다.
거친 멀티 스레딩에서는 스레드가 메모리 스톨과 같은 긴 지연시간을 가진 이벤트가 발생할 때까지 한 코어에서 수행된다.
- 긴 지연시간을 가진 이벤트에 의한 지연 때문에 코어는 다른 스레드를 실행하게 된다.
- 그러나 그 프로세서 코어에서 다른 스레드가 수행되기 전에 명령어 파이프라인이 완전히 정리되어야 하므로 스레드 간 교환은 비용이 많이 든다.
- 이 새로운 스레드가 실행을 시작하게 되면 자신의 명령어들로 파이프라인을 채우기 시작한다.
세밀한 멀티 스레딩은 보통 명령어 주기의 경계에서 같이 좀 더 세밀한 정밀도를 가진 시점에서 스레드 교환이 일어난다.
- 그러나 세밀한 시스템의 구조적 설계는 스레드 교환을 위한 회로를 포함한다.
- 그 결과 스레드 간 교환의 비용이 적어진다.

차이는 스레드 교환 비용에서 갈린다.

물리적 코어(캐시 및 파이프라인 등)의 자원은 하드웨어 스레드 간에 공유되어야 하므로 처리 코어는 한 번에 하나의 하드웨어 스레드만 실행할 수 있다.
결과적으로 멀티 스레드 멀티 코어 프로세서는 Figure 5.15와 같이 현실적으로 2개의 다른 스케줄링 단계가 필요하다.

정리하면, 거친 방식은 파이프라인을 비우는 큰 교환 비용을, 세밀한 방식은 교환 회로로 그 비용을 줄이는 대신 더 잦은 교환을 감수하는 셈이다.

코어 내부의 이야기를 마쳤으니, 다음은 프로세서 사이의 부하 배분이다.

5.5.3 Load Balancing

프로세서별로 준비 큐가 따로 있으면 부하가 한쪽으로 기울 수 있으므로, 이를 고르게 맞추는 것이 부하 균등화다.

부하 균등화(load balancing)는 SMP 시스템의 모든 프로세서 사이에 부하가 고르게 배분되도록 시도한다.
- 부하 균등화는 통상 각 프로세서가 실행할 스레드를 위한 자기 자신만의 준비 큐를 가지고 있는 시스템에서만 필요한 기능임을 알아야 한다.
부하 균등화를 위해서는 push 이주(migration)와 pull 이주 방식의 2가지 접근법이 있다.
push 이주에서는 특정 태스크가 주기적으로 각 프로세서의 부하를 검사하고 만일 불균형 상태로 밝혀지면 과부하인 프로세서에서 쉬고 있거나 덜 바쁜 프로세서로 스레드를 이동(push)시킴으로써 부하를 분배한다.
pull 이주 방식은 쉬고 있는 프로세서가 바쁜 프로세서를 기다리고 있는 프로세스를 pull할 때 일어난다.

정리하면, push와 pull 모두 프로세서별 준비 큐의 불균형을 해소하려는 이주 방식이다.

5.5.4 Processor Affinity

스레드를 다른 프로세서로 옮기면 원래 프로세서의 캐시를 무효화하고 다시 채워야 한다 — 그 비용을 아끼려는 전략이 프로세서 선호도다.

스레드에 의해 가장 최근에 접근된 데이터가 그 프로세서의 캐시를 채우게 된다.
그 결과 스레드에 의한 잇따른 메모리 접근은 캐시 메모리에서 만족한다.
- 이것을 warm cache라고 한다.
만약 스레드가 다른 프로세서로 이주한다면 어떻게 되는가.
첫 번째 프로세서의 캐시 메모리의 내용은 무효화 되어야 하며 두 번째 프로세서의 캐시는 다시 채워져야 한다.
캐시 무효화 및 다시 채우는 비용이 많이 들기 때문에 SMP를 지원하는 대부분의 운영체제는 스레드를 한 프로세서에서 다른 프로세서로 이주시키지 않고 대신 같은 프로세서에서 계속 실행시키면서 warm cache를 이용하려고 한다.
- 이를 프로세서 선호도(processor affinity)라고 한다.
- 즉, 프로세스는 현재 실행 중인 프로세서에 대한 선호도를 보인다.

결국 캐시를 되찾는 비용이 기준이다.

핵심 정리

스케줄링은 CPU 제어권의 교환이다. 실행 준비가 된 프로세스나 스레드에 CPU 코어를 할당하여 문맥 교환을 수행함으로써 시스템의 생산성을 극대화한다.
선점 여부가 알고리즘의 동작 방식을 가른다. 자발적 양보(I/O 요청, 종료)에만 전환되는 비선점형과 달리, 인터럽트나 타이머 만료 시 CPU를 회수할 수 있는 선점형 방식이 현대 시분할 시스템의 표준이다.
스케줄링 기준 간 트레이드오프가 존재한다. CPU 이용률과 처리량을 최대화하고 총처리·대기·응답 시간을 최소화하는 것이 목표이나, 대화형 환경에서는 특히 응답 시간과 예측 가능성이 중요하다.
SJF는 평균 대기 시간 면에서 최적이지만 예측이 필요하다. 다음 CPU 버스트 길이를 미리 완벽히 알 수 없으므로 과거 버스트 기록의 지수 평균(Exponential Average)을 통해 근삿값을 추정한다.
RR과 우선순위 스케줄링은 튜닝과 보완책이 핵심이다. RR은 시간 할당량(q)의 크기에 따라 FCFS와 문맥 교환 오버헤드 사이에서 성능이 좌우되며, 우선순위 스케줄링의 기아(Starvation) 문제는 노화(Aging) 기법을 적용한 멀티레벨 피드백 큐로 해결한다.
현대 운영체제의 실제 스케줄링 단위는 커널 스레드이다. 사용자 수준 스레드는 LWP를 매개로 프로세스 경합 범위(PCS)에서 경쟁하고, 커널 스레드는 시스템 경합 범위(SCS)에서 전체 CPU 코어를 두고 경쟁한다.
멀티 코어 시스템은 하드웨어 멀티스레딩(CMT)으로 메모리 스톨을 극복한다. 메모리 접근 지연 시간 동안 다른 하드웨어 스레드를 실행하여 코어 유휴 시간을 최소화한다.
다중 처리기에서는 부하 균등화와 프로세서 선호도 사이의 균형이 관건이다. 코어별 큐의 부하를 맞추기 위한 Push/Pull 이주(Migration)와, 캐시 무효화 비용을 절감하기 위한 프로세서 선호도(Processor Affinity) 사이에서 적절한 조율이 요구된다.

References

KakaoTalk Twitter Facebook LinkedIn