[OS] Chapter 6. CPU 스케줄링

Table of Contents

운영체제와 정보기술의 원리 강의를 듣고 공부한 노트입니다.

CPU 버스트와 I/O 버스트 #

프로그램 실행과 관련된 기계어 명령들
- CPU 내에서 수행되는 명령: Add 명령
- 메모리 접근을 수행하는 명령: Load, Store 명령
- 메모리를 접근하는 명령
- 입출력을 동반하는 명령 → 운영체제를 통해서만 가능한 특권명령

사용자 프로그램이 수행되는 과정은 CPU 작업와 I/O 작업의 반복으로 구성된다.
- CPU 버스트: 사용자 프로그램이 CPU를 직접 가지고 빠른 명령을 수행하는 단계
- I/O 버스트: I/O 요청이 발생해서 커널에 의해 입출력 작업을 진행하는 비교적 느린 단계
- CPU 바운드 프로세스: I/O 작업이 거의 없어서 CPU 버스트가 길게 나타나는 프로세스이다.
  - → 계산 위주의 프로그램
- I/O 바운드 프로세스: I/O 요청이 빈번해서 CPU 버스트가 짧게 나타나는 프로세스이다.
  - → 대화형 프로그램(interactive program)
동일한 시스템 내부에서 CPU 바운드 프로세스와 I/O 바운드 프로세스가 함께 섞여서 실행되기 때문에 CPU 스케줄링이 필요하다.
- 대부분의 프로세스는 짧은 CPU 바운드를 가진다. 따라서 I/O 바운드 프로세스의 우선순위를 높여주면, 대화형 프로세스의 빠른 응답성 제공과 I/O 장치의 이용률을 높일 수 있다.

CPU 스케줄러 #

CPU 스케줄러(scheduler)
- 준비 상태에 있는 프로세스들 중에서 어떤 프로세스에게 CPU를 할당할지 결정하는 운영체제의 코드이다.

CPU 스케줄러가 호출되는 예시
- (1) Running → Blocked : I/O 요청하는 시스템 콜
- (2) Running → Ready : 타이머 인터럽트
- (3) Blocked → Ready : I/O 완료로 인터럽트 (우선순위가 높아서 바로 CPU를 얻는 경우)
- (4) Terminate : 프로세스 종료

비선점형(nonpreemptive) 방식
- 프로세스가 CPU를 스스로 반납하기 전까지는 빼앗기지 않는다.
- (1), (4)의 경우
선점형(preemptive) 방식
- 프로세스에게 할당된 CPU를 강제로 빼앗을 수 있다.
- (2), (3)의 경우

디스패처 #

디스패처(dispatcher)
- CPU 스케줄러가 어떤 프로세스에게 CPU를 할당할지 결정하고 나면, 실제로 CPU를 이양하기 위해 환경설정을 하는 운영체제의 코드를 말한다.
- 현재 수행 중이던 프로세스의 문맥(context)을 PCB에 저장하고, 새롭게 선택된 프로세스의 문맥을 PCB로부터 복원한다. 그리고 시스템 상태를 사용자 모드로 전환해서 사용자 프로그램에게 CPU의 제어권을 넘긴다.

디스패치 지연시간(dispatch latency)
- 디스패쳐가 하나의 프로세스를 정지시키고 다른 프로세스에게 CPU를 전달하기까지 걸리는 시간을 말한다.
- 이것은 대부분 문맥교환의 오버헤드에 해당한다.

스케줄링의 성능 평가 #

시스템 관점
- (1) CPU 이용률(CPU utilization)
  - 전체 시간에서 CPU가 일을 한 시간의 비율
- (2) 처리량(throughput)
  - 주어진 시간 동안 프로세스 몇 개를 끝마쳤는지 (CPU 버스트를 완료한 프로세스의 개수)
사용자 관점
- (3) 소요 시간(turnaround time)
  - 프로세스가 CPU를 요청한 시점 ~ CPU 버스트를 완료하는데까지 걸린 시간
- (4) 대기 시간(waiting time)
  - CPU 버스트 기간 중 프로세스가 준비 큐에서 CPU를 얻기 위해 기다린 시간의 합
  - 시분할 시스템에서는 타이머 인터럽트를 사용하므로, 한 번의 CPU 버스트 중에도 준비 큐에서 기다린 시간이 여러번 발생할 수 있다.
- (5) 응답 시간(response time)
  - 프로세스가 준비 큐에 들어온 후 ~ 첫 번째 CPU를 획득하기까지 기다린 시간
  - 타이머 인터럽트가 빈번히 발생할 수록 처음 CPU를 획득하기까지 걸리는 시간은 줄어들겠다.

스케줄링 알고리즘 #

선입선출(FCFS) 스케줄링 #

First-Come First-Served
준비 큐에 도착한 시간 순서대로(CPU를 먼저 요청한 프로세스에게) CPU를 할당하는 방식이다.

단점
- 콘보이 현상(Convoy effect)
  - CPU 버스트가 긴 작업이 먼저 들어오면, CPU를 잠깐만 사용하면 준비 큐를 떠나 I/O작업을 수행할 수 있는(CPU 버스트가 짧은) 다수의 프로세스들이 계속 기다려야 하는 상황이 생긴다.
  - 먼저 도착한 프로세스의 CPU 버스트 기간에 따라 평균 대기시간이 크게 달라진다.
  - 평균 대기시간(waiting time)이 길어진다.
  - I/O 장치의 이용률이 하락한다.

프로세스	CPU 버스트 시간
$P_1$	$12$
$P_2$	$3$
$P_3$	$3$

대기 시간: $P_1 = 0$, $P_2 = 12$, $P_3 = 15$
평균 대기 시간: $(0 + 12 + 15) / 3 = 9$

최단작업 우선(SJF) 스케줄링 #

Shortest-Job First
CPU 버스트가 가장 짧은 프로세스에게 제일 먼저 CPU를 할당하는 방식이다.
선점형(Shortest Remaining Time First; SRTF) 과 비선점형 방식으로 구현할 수 있다.
- 선점형의 경우, 어떤 프로세스가 CPU를 할당받고 수행 중이더라도, CPU 버스트 시간이 더 짧은 프로세스가 도착하면 빼앗기는 방식이다.
- 프로세스들이 준비 큐에 도착하는 시간이 불규칙한 환경에서는 선점형 방식이 평균 대기시간을 최소화하는 최적의 알고리즘이 된다.

프로세스	도착 시간	CPU 버스트 시간
$P_1$	$0$	$14$
$P_2$	$4$	$8$
$P_3$	$8$	$2$
$P_4$	$10$	$8$

비선점형 방식 평균 대기시간: $(0 + 12 + 6 + 14) / 4 = 8$
선점형 방식 평균 대기시간: $(18 + 2 + 0 + 4) / 4 = 6$

장점
- 평균 대기시간을 가장 짧게 하는 최적 알고리즘(optimal algorithm)이다.
단점
- 기아 현상(starvation) 이 발생한다.
  - CPU 버스트가 짧은 프로세스가 계속 도착하면 CPU 버스트가 긴 프로세스는 영원히 CPU를 할당받지 못하는 것이다.
- CPU 버스트 시간을 미리 예측할 수 없다.

CPU 버스트 시간 예측 방법
- 과거의 CPU 버스트 시간을 통해 계산된다. 더 오래된 과거일 수록 그 영향력이 적어지도록 반영한다.
- $$ T_n+1 = \alpha t_n + (1 - \alpha)T_n$$
- $t_n$은 $n$번째 실제 CPU 버스트 시간이고, $T_n$은 $n$번째 CPU 버스트의 예측시간이다.
- $\alpha$는 $0 ~ 1$ 사이의 상수로 위의 두 요소를 어느 정도씩 반영할지 조절하는 매개변수이다.

우선순위 스케줄링 #

우선순위가 가장 높은 프로세스에게 제일 먼저 CPU를 할당하는 방식이다.
우선순위 값(priority number)은 그 값이 작을수록 우선순위가 높다.
SJF 스케줄링은 우선순위 스케줄링의 일종이라고 볼 수 있다.
선점형과 비선점형 방식으로 구현할 수 있다.

단점
- 기아 현상이 발생할 수 있다.
- 해결 방안: 노화(aging) 기법
  - 기다리는 시간이 길어지면 우선순위를 조금씩 높여서 언젠가는 가장 높은 우선순위가 되어 CPU를 할당받을 수 있게 해주는 방법이다.

라운드 로빈 스케줄링 #

Round Robin
각 프로세스가 한 번에 CPU를 연속적으로 사용할 수 있는 최대시간(할당시간; timequantum)을 주는 방식이다.
- 할당 시간이 너무 길면, FCFS와 같은 결과를 나타내며,
- 할당 시간이 너무 짧으면, 프로세스가 빈번하게 교체되어 문맥교환의 오버헤드가 커진다.
- 일반적으로 $10$ ~ $100 ms$(밀리초) 정도로 설정한다.
- 타이머 인터럽트를 사용해서 CPU를 회수한다.
- SJF보다 평균 대기 시간은 길지만, 응답시간은 더 짧다.

장점
- CPU 버스트 시간이 짧은 프로세스가 빨리 CPU를 얻을 수 있도록 하는 동시에, CPU 버스트 시간이 긴 프로세스가 불이익을 당하지 않도록한다. (공정하다)
- 대화형 프로세스의 빠른 응답시간을 보장한다.
  - $n$개의 프로세스가 준비 큐에 있고 할당 시간이 $q$라고 하면, 모든 프로세스는 $(n-1)q$시간 이내에 적어도 한 번은 CPU를 할당 받는다.

다단계 큐 #

muti-level queue
준비 큐를 여러 개로 분할해서 관리하는 방식이다.
일반적으로, 전위 큐(foreground queue)와 후위 큐(background queue)로 분할하여 운영한다.
- 전위 큐: 대화형 작업을 담는다. 라운드 로빈 스케줄링을 사용한다.
- 후위 큐: 계산 위주의 작업을 담는다. FCFS 스케줄링을 사용한다.

어느 큐에게 먼저 CPU를 할당할 것인가?
- 고정 우선순위 방식(fixed priority scheduling)
  - 큐에 고정적인 우선순위를 적용한다. 항상 전위 큐에 있는 프로세스에게 CPU가 먼저 할당된다.
- 타임 슬라이스(time slice) 방식
  - 각 큐에 CPU 시간을 적절한 비율로 할당한다. 예를 들면 전위 큐는 80%, 후위 큐는 20%이다.

다단계 피드백 큐 #

multi-level feedback queue
준비 큐를 여러 개로 둔다는 점은 다단계 큐와 동일하나, 프로세스가 하나의 큐에서 다른 큐로 이동 가능하다는 점이 다르다.
- 대표적인 방식은, 라운드 로빈을 사용하면서 할당시간이 5, 10인 준비 큐가 있고, 그다음에 FCFS 준비 큐가 있는 것이다.
- 프로세스의 CPU 작업시간을 다단계로 분류함으로써, 작업시간이 짧은 프로세스일 수록 더 빠른 서비스가 가능해지며, 작업시간이 긴 프로세스에 대해서는 문맥교환 없이 CPU 작업에만 열중할 수 있는 FCFS 방식을 채택할 수 있다.

정의 요소들
- 큐의 수
- 각 큐의 스케줄링 알고리즘
- 프로세스를 상위 큐로 승격시키는 기준
- 프로세스를 하위큐로 강등시키는 기준
- 프로세스가 도착했을 때 들어갈 큐를 결정하는 기준

다중처리기 스케줄링 #

multi-processor system
CPU가 여러 개인 시스템인 다중처리기 시스템에서 사용하는 스케줄링이다.

Homogeneous processor인 경우
- 큐에 한줄로 세워서 각 프로세서가 알아서 꺼내가게 한다.
특정 CPU에서 수행되어야 하는 프로세스가 있는 경우
- 각 CPU별로 줄 세우기를 할 수 있겠다.
- 하지만 그렇게 되면 특정 CPU에 작업이 편중되는 현상이 발생할 수 있다.
- 그래서 각 CPU별로 부하가 적절히 분산되도록 하는 부하균형(load balancing) 메커니즘을 필요로 한다.

대칭형 다중처리(symmetric multi-processing; SMP)
- 각 CPU가 알아서 스케줄링을 결정하는 방식이다.
비대칭형 다중처리(asymmetric multi-processing)
- 하나의 CPU가 다른 모든 CPU의 스케줄링 및 데이터 접근을 책임지고, 나머지 CPU는 거기에 따라 움직이는 방식이다.

실시간 스케줄링 #

작업의 데드라인이 정해져 있어서 그 안에 반드시 처리해야하는 실시간 시스템(real-time system)에 사용하는 방식이다.
- 경성 실시간 시스템(hard real-time system): 데드라인 안에 반드시 끝내야 하는 시스템
- 연성 실시간 시스템(soft real-time system): 데드라인을 지키지 못했다고 해서 위험한 상황이 발생하는 건 아닌 시스템
EDF(Earlist Deadline First) 스케줄링을 주로 사용한다.
- 데드라인이 얼마 남지 않은 요청을 먼저 처리하는 것이다.

스레드 스케줄링 #

Global scheduling
- Kernel level thread의 경우
- 일반적인 프로세스와 마찬가지로 커널의 단기 스케줄러가 어떤 스레드를 스케줄링할지 결정한다.
Local scheduling
- User level thread의 경우
- 사용자 수준의 스레드 라이브러리에 의해 어떤 스레드를 스케줄링할지 결정한다.

스케줄링 알고리즘의 평가 #

(1) 큐잉모델(queueing model)
- 이론가들이 수행하는 방식이다.
- 확률 분포로 주어지는 도착률(arrival rate)과 처리율(service rate)을 가지고 수학적 계산을 통해 각종 성능지표를 확인한다.
(2) 시뮬레이션(simulation)
- 구현가들이 수행하는 방식이다.
- 실제로 코드를 수정해서 커널을 컴파일한 후 수행시켜보고 실행시간을 측정한다.
(3) 구현 및 실측(implementation & measurement)
- 가상으로 CPU 스케줄링 프로그램(모의 프로그램)을 작성해서 어떤 결과가 나오는지 확인하는 방식이다.
- 입력값은 가상일 수도 있고, 실제 시스템에서 추출한 입력값(트레이스; trace)일 수도 있다.