[OS] 03. CPU Scheduling

CPU Scheduling

다중 프로그래밍을 통해 CPU의 활용도 향상 가능
CPU burst 또는 I/O burst : 프로세스 실행은 CPU 실행과 I/O 대기의 사이클로 구성
CPU burst 뒤에 I/O burst가 뒤따라옴 / CPU burst 분포는 컴퓨터 시스템의 주요 관심사
Short-term Scheduler는 Ready Queue의 프로세스 중 하나를 선택하고 선택된 프로세스에게 CPU를 할당

 

CPU Scheduling 결정이 일어나는 경우

1. 프로세스가 Running에서 Waiting으로 전환될 때
2. 프로세스가 Running에서 Ready로 전환될 때
3. 프로세스가 Waiting에서 Ready로 전환될 때
4. 프로세스가 종료될 때 (Terminate)

1, 4의 상황은 비선점적(프로세스 스스로 CPU를 포기한 상황)

2, 3은 선점적

 

선점 스케줄링에서 고려해야 할 사항

• 공유 데이터 접근
• 커널 모드에서의 선점
• 중요한 OS 활동 중에 발생하는 인터럽트

비선점 스케줄링

• 일단 CPU가 하나의 프로세스에 할당되면 그 프로세스가 CPU를 놓을 때까지 CPU를 점유
• 종료되거나 대기 상태로 전환

선점 스케줄링

• Ready 큐에 새 프로세스가 들어올 때마다, CPU가 비었을 때마다 스케줄링을 수행
• 현재 수행되고 있는 프로세스는 언제든지 다른 프로세스로 교환 가능 -> 인터럽트가 언제든지 발생할 수 있음
• 프로세스 간 데이터 공유 시, 일관성 유지에 따른 관련 비용이 발생
• OS의 커널 설계에 영향을 줌
• UNIX의 경우, Context Switch 발생 전, 시스템 콜의 완료 혹은 입출력 봉쇄(block)이 일어나기를 기다림
• 중요한 코드의 시작 부분에서는 인터럽트를 비활성화시키고 끝부분에는 활성화 -> 중요한 커널 코드 보호

Dispatcher

• Dispatcher 모듈은 Short-term 스케줄러에 의해 선택된 프로세스에게 CPU의 제어권을 제공
• Context Switching을 해주는 역할
• 사용자 모드로 전환
• 프로그램 재시작을 위해 사용자 프로그램을 적절한 위치로 이동

Dispatch latency : 디스패치 지연

• 디스패처가 하나의 프로세스를 중단하고 다른 프로세스를 시작하는데 걸리는 시간
• Linux에서 vmstat 명령어로 모니터링 가능

Scheduling 평가 기준 - 최대화하기 위한 기준

• CPU 활용도 : CPU가 busy state인 시간의 비율 = CPU를 가능한 바쁘게 유지
• Throughput(처리량) : 단위 시간당 완료된 프로세스의 개수(#)

Scheduling 평가 기준 - 최소화하기 위한 기준

• Turnaround time (반환 시간) : 특정 프로세스를 실행하는데 걸리는 시간 (시작부터 종료)
• Waiting time (대기 시간) : 프로세스가 Ready Queue에서 대기한 시간
• Response time (응답 시간) : 요청이 제출되고 첫 응답이 생성될 때까지 걸리는 시간 (출력이 아닌 응답)

---

CPU Scheduling Algorithm

스케줄링 알고리즘 비교는 평균 대기 시간(average waiting time)을 주로 사용

CPU 사용률, 처리량, 총처리 시간, 응답 시간 등도 함께 고려

 

First-Come, First Served : FCFS / 선입 선처리 스케줄링

• 도착한 순서대로 CPU에서 처리
• 장점 : 구현이 쉬움
• 단점 : Worst Case에 가까움
• Non-Preemptive 스케줄링 (비선점 스케줄링)

Convoy effect

긴 CPU burst를 가진 하나의 CPU 중심 프로세스와 짧은 CPU burst를 가진 많은 입출력 중심 프로세스가 순서대로 수행되면 모든 입출력 중심 프로세스는 I/O 장치들이 놀고 있으면서 CPU 중심 프로세스가 CPU를 놓을 때까지 기다려야 함 (모든 입출력/CPU 중심 프로레스는 CPU가 놀고 있으면서 입출력 연산을 수행) 결론적으로 낮은 CPU와 장치 사용률을 보임

 

FCFS 예시

 

Average waiting time : (0+24+27) / 3 = 17

Turnaround time : (24+27+30) / 3 = 27

 

Shortest Job First : SJF / 최단 작업 우선 스케줄링 (비선점 스케줄링)

• CPU burst의 길이를 고려하여 가장 짧은 시간을 가진 프로세스를 먼저 스케줄링
• Average waiting time을 최소화
• 현실적으로 CPU burst를 정확히 예측할 수 없어 불가능
• 컴파일러가 컴파일 시, 대략적인 CPU burst를 알려주면 유사하게 구현 가능 (OS에게 힌트를 제공)
• 다음 CPU burst를 예측하는 방법 : 지수적 평균 exponential averaging
• 이전 CPU burst 길이와 예측한 CPU burst 중 가장 짧은 프로세스를 선택

SJF 예시

 

Average waiting time : (3+16+9+0) / 4 = 7
Turnaround time : (9+24+16+3) / 4 = 13

 

Shortest-remaining-time-first

• SJF의 Preemptive(선점) 버전
• Arrival time(도착 시간)을 고려

Shortest-remaining-time-first 예시

 

Average waiting time = [(10-1)+(1-1)+(17-2)+(5-3)] / 4 = 26 / 4 = 6.5
Average waiting time of SJF = (0+7+15+9) / 4= 7.75

 

Priority Scheduling : 우선순위 스케줄링

• 각 프로세스에 우선순위 번호가 할당 (숫자가 낮을수록 우선순위는 높음)
• CPU는 가장 높은 우선순위를 가진 프로세스에 할당 (선점, 비선점 둘 다 가능)
• SJF도 우선순위의 한 종류 : 예상 CPU burst 시간의 역수로 우선순위를 지정
• 장점 : OS가 프로세스의 특성에 맞게 우선순위를 지정 가능
• 문제 : Starvation / 낮은 우선순위는 오랫동안 실행되지 않을 수 있음
• 해결책 : Aging / 시간이 경과함에 따라 프로세스의 우선순위를 증가

Priority Scheduling 예시

 

Average waiting time = (0+1+6+16+18)/5 = 8.2

 

Round Robin Scheduling : RR / 라운드 로빈 스케줄링 (무조건 선점형)

• 각 프로세스는 CPU 시간의 작은 단위(time quantum q)를 받음 (보통 10-100ms)
• 이 시간이 경과하면 프로세스는 선점되고 Ready Queue의 끝에 추가됨
• Ready Queue에 n개의 프로세스가 있고 time quantum이 q이면 각 프로세스는 1/n의 CPU 시간을 얻음
• 그리고 최대 q시간 단위로 작동
• 어떤 프로세스도 (n-1)q 시간 단위 이상만큼 기다리지 않음
• 타이머 인터럽트가 다음 프로세스를 스케줄링하기 위해 매 퀀텀마다 발생 (q가 끝나면 -> wait -> ready)
• 성능 분석 : 긴 q => FIFO(선입선출) / 아주 크면 큰 의미가 없음
• 성능 분석 : 작은 q => q는 Context Switch에 비해 커야 함, 그렇지 않으면 오버헤드가 높아짐
• 일반적으로 80% 이상의 프로세스가 time quantum보다 짧아야 함
• 일반적으로 SJF보다 average turnaround time은 높을 수 있지만 더 나은 response time을 제공
• q는 Context Switch 시간에 비해 커야 함
• Context Switch 시간이 시간 퀀텀의 10%라면 CPU 시간의 약 10%가 Context Switch에 소비
• 현대 OS의 대부분은 시간 퀀텀 값이 10-100ms 범위
• Context Switch 시간은 10ms 미만임

---

리눅스 CFS 스케줄링

CFS : Completely Fair Scheduling

우선순위+RR의 특성을 가짐

비선점 스케줄링
목적 : 모든 프로세스가 공평하게 CPU를 할당받도록 스케줄링 (기아가 발생하지 않도록) 

 

프로세스 사이의 공평성을 위한 4가지 요소

1. 가상 실행 시간
    - 프로세스의 실제 CPU 사용 시간과 가중치를 고려하여 계산된 시간 / 작을수록 우선순위가 높음
2. 대기 큐 (Run Queue) = Ready Queue
    - 실행 대기 중인 프로세스들이 들어있는 큐 / Red-Black 트리(이진 트리)로 구성
    - 누적 가상 실행 시간이 적은 순으로 정렬된 트리
3. 타임 슬라이스 = RR의 time quantum 개념
    - 한 번 스케줄되면 강제 중단 없이 CPU 실행을 보장받는 시간
    - 스케줄링 시마다 선택된 프로세스의 타임 슬라이스를 새로 계산
    - Ready Queue에서 대기 중인 프로세스의 개수에 반비례
4. 가중치 (Weight) - 프로세스의 스케줄링 우선순위에 영향을 미치는 값 / 프로세스마다 가중치 별도 유지
    - weight는 nice 값에 따라 결정 / weight가 클수록 가상 실행 시간은 적고 타임 슬라이스는 크게 계산

개요 : CPU 사용 시간이 짧은 프로세스 우선 선택 / 프로세스는 타임 슬라이스동안 강제 중단 X

작동 과정

1. 프로세스가 생성되면 Run Queue에 삽입, 가상 실행 시간은 현재 Run Queue에 들어있는 가장 적은 시간으로 설정, Run Queue의 원은 준비 상태의 프로세스, 숫자는 누적 가상 실행 시간
2. 스케줄링 – Run Queue에서 가장 짧은 누적 가상, 실행 시간을 가진 프로세스를 선택, 프로세스의 타임 슬라이스를 결정한 후 실행
3. 실행
4. 실행 도중 – 프로세스가 타임 슬라이스를 다 소진하면 가상 실행 시간과 누적 가상 실행 시간을 계산하고 Run Queue에 삽입, 프로세스의 실행 중 I/O가 발생하면 Run Queue에 삽입, 입출력이 완료되면 깨어나 가상 실행 시간과 누적 가상 실행 시간을 계산하고 Run Queue에 삽입

준비 큐 = Run Queue

• 준비 상태의 프로세스들이 스케줄을 기다리는 큐
• CPU마다 1개 있음
• CPU의 가상 실행 시간순으로 정렬

가상 실행 시간

• 할당된 타임 슬라이스에서 프로세스가 CPU를 실제 사용한 시간에 다른 프로세스에게 양보한 대가를 반영, 계산한 값
• 계산 시점 : 프로세스가 생성되었을 때, 준비 큐의 가장 짧은 누적 가상 실행 시간으로 설정
  (프로세스가 자신의 타임 슬라이스를 소진하거나, 대기 큐에서 준비 큐로 이동할 때)
• 가상 실행 시간의 의미 : I/O 집중 프로세스에게 더 높은 우선순위 / 대화식 응용프로그램이 많으면 적합

누적 가상 실행 시간

• 프로세스가 지금까지 사용한 가상 실행 시간의 총합

 

nice

• 프로세스마다 가지는 값
• 디폴트값 : 0
• -20~19 범위
• 값이 클수록 양보를 잘함 = 스케줄링 우선순위 낮음
• 시스템 콜을 통해 nice 값을 조절 가능

weight

• CFS는 nice 값을 weight(가중치)로 바꾸어서 사용
• 클수록 높은 스케줄링 순위 (가상 실행 시간이 작게 계산)
• 더 오래 CPU 사용 가능 (타임 슬라이스를 크게 할당)

타임 슬라이스 : 중단없이 실행되도록 CPU를 부여하는 시간
scheduling_period : 준비 큐에 있는 모든 프로세스를 한 번씩 실행시킬 수 있도록 CFS에서 계획한 주기 시간

 

스케줄링 알고리즘

1. 프로세스 p를 준비 큐에 삽입하기 전, 가상 실행 시간 계산
2. 누적 가상 실행 시간 계산
3. 스케줄러에 의해 선택된 프로그램 q의 타임 슬라이스 계산
4. p와 q의 Context Switch

---

Multilevel Queue Scheduling

Ready Queue가 분리된 큐로 분할

foreground (interactive 사용자와 대화) & background (batch 일괄식)

보통 foreground 큐 먼저 CPU로 넘어가고 비워지게 되면 background 큐의 프로세스가 실행

주어진 큐의 프로세스는 영구적

각 큐끼리의 우선순위가 존재함
각 큐는 고유한 스케줄링 알고리즘을 가짐 (예시 foreground : RR / background : FCFS)

 

큐 사이의 스케줄링 결정 방식

• 고정 우선순위 스케줄링 (foreground 모두 처리 후 background 처리) (기아 현상 발생 가능성 존재)
• 타임 슬라이스 : 각 큐는 일정 양의 CPU 시간을 할당, 자체적으로 스케줄링 (예시 : fore 80% & back 20%)

Multilevel-feedback-queue

• 프로세스는 다양한 큐 사이를 이동할 수 있음 : Aging으로 구현 가능

Multilevel-feedback-queue 스케줄러는 다음의 매개변수로 정의

• 큐의 개수 / 각 큐의 스케줄링 알고리즘
• 프로세스를 높은 우선순위 큐로 이동시킬 때 사용하는 방법 (upgrade)
• 프로세스를 낮은 우선순위 큐로 이동시킬 때 사용하는 방법 (demote)
• 프로세스가 서비스되어야 할 때 어느 큐에 들어갈지 결정하는 방법

Multilevel-feedback-queue 스케줄러 예시

 - Q0 : RR with time quantum 8ms
 - Q1 : RR with time quantum 16ms
 - Q2 : FCFS
 - 새로운 프로세스는 일단 Q0로 스케줄링
 8ms 안에 waiting 상태로 되면 다음에도 Q0로 스케줄링
 8ms 안에 작업을 끝내지 못하면 Q1로 이동
 Q1에서 16ms 안에 작업을 끝내지 못하면 Q2로 이동

 

장점 : Interactive 프로세스에게 높은 우선순위를 주는 효과 + 큐 선택이 단순함
기아 현상이 발생할 수 있으므로 Aging 기법을 적용해서 높은 우선순위 큐로 이동시킬 수 있음

---

Multiprocessor Scheduling

homogeneous multiprocessors 기반 (동종 멀티 프로세서)

 

Asymmetric multiprocessors

• 비대칭
• 하나의 프로세서만 시스템 데이터 구조에 접근
• 데이터 공유의 필요성을 완화

Symmetric multiprocessors

• 대칭
• 각 프로세서는 자체 스케줄링
• 가장 일반적인 방식 (SMP) 모든 프로세서가 공통된 Ready 큐를 가지거나 자체적인 Ready 큐를 가질 수 있음

Load balancing

• 모든 CPU를 유사하게 작업하도록 균등하게 분산 (SMP에서)
• Push migration : 주기적인 작업이 각 프로세서의 부하를 확인하고 과다한 CPU에서 아닌 CPU로 작업을 이동
• Pull migration : 각 프로세서마다 자신의 Ready 큐를 검사하고 비어있다면 다른 프로세서에서 작업을 가져옴

Processer affinity (프로세서 친화성) : 프로세스의 프로세서 이주 정도

• 프로세서가 수행될 때는 프로세서(CPU)의 cache에 올라가므로 프로세서를 이주하는 것은 상당한 비용이 듦
• 약한 친화성 (soft affinity) : 가급적 동일 프로세서에서 수행하려 하나, 이주할 가능성 있음
• 강한 친화성 (hard affinity) : 시스템 콜을 사용하여 특정 프로세스는 프로세서를 이주하지 않는 것을 명시
• 대부분의 OS는 2가지 모두 지원, Linux의 경우 sched_setaffinity() 시스템 콜 제공
• NUMA (Non-Uniform Memory Access) 구조인 경우, 프로세서 친화성을 심도 있게 고려해야 함

Multicore Processors

• 동일한 물리 칩에 여러 코어를 배치 -> 속도가 빠르고 전력 소모가 줄어듦
• CPU 계산 프로세스랑 I/O 사용 프로세스를 번갈아 배치하면 효율적

멀티 스레드 다중 코어 시스템

• 칩 다중 스레드 : 하나의 코어에 여러 개의 하드웨어 스레드를 할당 (Hyperthreading in Intel)
• 하나의 코어에 2개의 하드웨어 스레드를 할당하는 쿼드코어 시스템은 8개의 논리 스레드를 OS에서 사용
• 두 계층 스케줄링 : OS가 논리적 CPU에서 동작할 SW 스레드를 결정 – CPU 스케줄링
  각 코어는 물리적 코어에서 실행될 하드웨어 스레드를 결정

---

Real-Time CPU Scheduling

Soft Real-Time Systems : 핵심 Real-Time 프로세스가 언제 스케줄될지에 대한 보장이 없음
Hard Real-Time Systems : 작업은 데드라인까지 서비스받아야 함

 

성능에 영향을 미치는 2가지 지연

1. Interrupt Latency : 인터럽트가 도착한 시점부터 인터럽트를 처리하는 루틴이 시작하는 데 걸리는 시간
2. Dispatch Latency : 현재 프로세스를 CPU에서 제거하고 다른 프로세스로 전환하는 데 걸리는 시간

디스패치 지연의 충돌 단계

• 커널 모드에서 실행 중인 프로세스의 선점
• 높은 우선순위에서 필요한 리소스를 낮은 우선순위 프로세스에서 허용

Hard Real-Time 스케줄링에서 시스템은 데드라인을 맞출 수 있는 능력을 제공해야 함

Periodic(주기)의 역수가 우선순위임

 

Rate Monotonic Scheduling (정적 우선순위를 이용하는 경우 최적)

• 두 개의 프로세스 P1, P2
• P1의 주기는 50, P2의 주기는 100
• P1의 수행시간 t1은 20, P2의 수행시간 t2는 35임
• P1의 CPU 이용률은 20/50, P2의 이용률은 35/100이므로 총 75%
• P2가 P1보다 우선순위가 높으면 데드라인을 만족하지 못할 수 있음
• P1이 전부(20) 실행되고 P2가 30만큼 실행되고 P1이 들어오면 P1이 먼저 실행되고 남은 P2 5가 실행

Rate Monotonic은 CPU 이용률에 한계가 있기 때문에 자원을 최대로 사용하는 것은 불가능

CPU 이용률 상한 : N x (2의 1/N승 - 1)       ( N = 프로세스 개수 / 1개 : 100%, 2개 : 83%, 최저 : 69%)

 

Earliest Deadline First Scheduling (EDF)

• 데드라인이 더 빠를수록 높은 우선순위, 데드라인이 늦을수록 낮은 우선순위를 부여
• Rate Monotonic과 달리 프로세스들이 주기적일 필요가 없고, CPU 할당 시간도 상수값으로 정해질 필요 X
• Rate Monotonic : Static Scheduling / EDF : Dynamic Scheduling
• 이론적으로 EDF는 최적으로 100% CPU를 사용 가능
• 동적으로 정확한 데드라인을 알지 못함, Context Switch 등의 오버헤드로 100% CPU 사용률은 불가능

Proportional Share Scheduling

• T개를 시스템의 모든 프로세스들에게 할당 / 한 프로세스는 N개를 할당, N < T
• 결국, 각 프로세스는 총 프로세서 시간의 N/T를 할당
• 승인 제어 정책(admission control policy)과 함께 동작
• A가 50, B가 15, C가 20을 할당받은 상황에서 D가 30을 요구하면 승인하지 않음

---

Linux Scheduling

O(1) 스케줄러
CFS 스케줄러
BFS 스케줄러

---

Algorithm Evaluation

Deterministic evaluation : 결정론적 평가

Queueing models : 대기열 모델
Simulations : 시뮬레이션
Implementation : 구현