CPU 스케줄링

Reporting Date: May. 09, 2025

---

단기(CPU) 스케줄러에 대해 다루고자 한다.

---

목차

01 다중 프로그래밍
02 CPU 스케줄러
03 디스패처 모듈
04 스케줄러 기준
05 알고리즘
06 예제

---

 

 

 

01 다중 프로그래밍

Multiprogramming

 1 .  주요 목적

CPU 이용률(Utilization)을 극대화하는 것이 주요 목적이며,
이를 위해 OS는 항상 실행 가능한 프로세스를 유지하려고 한다.

OS의 핵심 기능 중 하나인 CPU 스케줄링은
여러 프로세스 중에서 어떤 프로세스에 CPU를 할당할지를
결정하는 메커니즘으로, OS 설계에서 매우 중요한 요소이다.

프로세스의 실행은 일반적으로 CPU 실행(CPU Burst)과
입출력 대기(I/O Wait) 사이클로 반복된다.

입출력 중심 프로그램은 일반적으로 짧은 CPU Burst가 자주 발생하는 반면,
CPU 중심 프로그램은 긴 CPU Burst를 상대적으로 적게 가지는 경향이 있다.
이러한 특성에 따라 적절한 CPU 스케줄링 알고리즘을 선택하는 것이 중요하다.

 

---

 

CPU와 I/O 버스트가 교대로 나타나는 실행 흐름.

단계	구분	작업	내용 설명
1	CPU Burst	load, store, add, store	연산 수행
2	I/O Burst	read from file	파일 읽기 요청
3	I/O Wait	wait for I/O	I/O 작업 완료 대기
4	CPU Burst	store, increment index	연산 및 인덱스 증가
5	I/O Burst	write to file	파일 쓰기 요청
6	I/O Wait	wait for I/O	I/O 작업 완료 대기
7	CPU Burst	load, store, add, store	연산 수행
8	I/O Burst	read from file	파일 읽기 요청
9	I/O Wait	wait for I/O	I/O 작업 완료 대기

 

CPU 버스트 시간의 히스토그램은
일반적으로 초지수형 분포를 따른다.

Hyperexponential Distribution

이는 다양한 유형의 프로세스들이
서로 다른 버스트 특성을 갖기 때문이다.

예를 들어, I/O 중심 작업(I/O Bound Job)은
짧은 CPU 버스트를 자주 발생시키는 반면,

CPU 중심 작업(CPU Bound Job)은
상대적으로 긴 CPU 버스트를 드물게 발생시키는 경향이 있다.

이러한 차이로 인해 전체적인 CPU 버스트 시간 분포는 단일 지수형 분포가 아닌,
여러 지수 분포가 혼합된 형태인 초지수형 분포의 특성을 띄게 된다.

---

 

02 CPU 스케줄러

CPU Scheduler

실행 준비가 된 프로세스들 중 하나를 선택하여
CPU를 할당하는 운영체제의 핵심 구성 요소이다.

CPU가 유휴 상태가 될 때마다, OS는 준비 큐(Ready Queue)에
있는 프로세스들 중에서 하나를 선택해 실행하도록 한다.

 

CPU 스케줄링이 발생하는 네 가지 주요 상황

번호	상태 전이	예시 스케줄링	유형 선택	OS 개입 여부
1	실행 → 대기	I/O 요청	비선점 (Nonpreemptive)	없음 (자동 선택)
2	실행 → 준비완료	타이머 종료, 인터럽트 발생	선점 (Preemptive)	있음 (선택 가능)
3	대기 → 준비완료	I/O 작업 완료	선점 (Preemptive)	있음 (선택 가능)
4	실행 종료	프로세스 종료	비선점 (Nonpreemptive)	없음 (자동 선택)

---

 

03 디스패처 모듈

Dispatcher Module

디스패처는 단기(CPU) 스케줄러가 선택한 프로세스에게
실제로 CPU 제어권을 넘겨주는 역할을 수행하는 OS의 구성 요소이다.

즉, 선택된 프로세스를 실제 실행 상태로 전환시키는 기능을 담당한다.

 

 1 .  주요 기능

문맥 교환(Context Switch)

이전 프로세스의 상태인 레지스터, 프로그램 카운터 등을
저장하고, 새 프로세스의 상태를 복원한다.

 

모드 전환

커널 모드에서 사용자 모드로 전환하여
사용자 프로그램 실행 환경으로 복귀한다.

 

프로그램 제어 이동 (Jump)

프로그램 카운터 값과 같이 새로 실행할
사용자 프로그램의 적절한 위치로 제어를 이동시킨다.

 

 

 2 .  디스패치 지연

Dispatch Latency

디스패처가 하나의 프로세스를 중단하고
다른 프로세스를 실행할 때까지 걸리는 시간이다.

대부분의 지연은 문맥 교환 오버헤드로 발생하며,
이 시간 동안 CPU는 실제 작업을 수행하지 못한다.

---

 

04 스케줄링 기준

Scheduling Criteria

OS는 CPU를 효율적으로 활용하기 위해
다양한 스케줄링 기준을 고려하여 프로세스를 관리한다.

주요 기준은 다음과 같다:

 1 .  CPU 이용률

CPU Utilization

CPU를 가능한 한 최대한도로 바쁘게 유지하는 것이 목표이다.
실제 시스템에서는 보통 40 ~ 90% 범위의 이용률을 보이며,
높을수록 좋은 지표이다.

 

 2 .  처리량

Throughput

단위 시간당 완료된 프로세스의 수를 의미한다.
많을수록 효율적인 처리를 의미하며, 시스템 성능 향상에 기여한다.

 

 3 .  총 처리 시간

Turnaround Time

프로세스가 제출된 시점부터 완료될 때까지의 전체 시간이다.
이는 대기 시간, CPU 실행 시간, 입·출력 시간 등을 모두 포함한다.
짧을수록 좋으며, 사용자 입장에서는 작업이 빠르게 끝나는 것이 유리하다.

 

 4 .  대기 시간

Waiting Time

프로세스가 준비완료 큐에서 대기한 시간의 총합이다.
이 역시 짧을수록 좋으며, 자원 낭비를 줄이고
반응 속도를 높이는 데 기여한다.

 

 5 .  응답 시간

Response Time

프로세스가 요청을 제출한 후 첫 번째 응답이 나올 때까지의 시간이다.
완료 시간이 아닌, 처음 반응이 나타나는 시점까지를 측정한다.
짧은 응답 시간은 인터랙티브 시스템에서 특히 중요하다.

---

 

05 알고리즘

OS는 CPU 이용률, 처리량, 대기 시간, 응답 시간 등
다양한 기준을 최적화하기 위해 여러 가지 스케줄링 알고리즘을 사용한다.

대표적인 7가지 스케줄링 알고리즘은 다음과 같다:

 

 1 .  FCFS

First-Come, First-Served

가장 먼저 도착한 프로세스를 먼저 실행하는 방식
구현이 간단하지만, 대기 시간이 길어질 수 있음 (Convoy effect)

 

 2 .  SJF

Shortest Job First

CPU 버스트 시간이 가장 짧은 프로세스를 우선 실행한다.

평균 대기 시간 최소화에 효과적이나
실행 시간을 사전에 예측하기 어렵다는 단점이 있다.

 

 3 .  SRTF

Shortest Remaining Time First

SJF의 선점형 버전으로,
남은 실행 시간이 가장 짧은 프로세스를 우선 실행한다.

새 프로세스가 더 짧은 남은 시간을 가질 경우 현재 작업을 선점하며,
응답 시간과 대기 시간의 최적화에 유리하다.

 

 4 .  Priority Scheduling

프로세스마다 우선순위를 두고, 높은 우선순위부터 실행한다.
우선순위는 PCB(Process Control Block)에 저장되어 있다.

기아(Starvation) 문제 발생할 수 있는 단점이 있다.

에이징(Aging) 기법 사용하여 오래된 프로세스의
우선순위 점진적으로 상승하는 것으로 해결할 수 있다.

 

 5 .  RR

Round Robin

각 프로세스에 고정된 시간 할당량(Time Quantum)을
부여하여 순환 실행하므로, 공정성 보장 측면에서 우수하다.
짧은 타임퀀텀은 응답성을 높이고, 긴 타임퀀텀은 처리량 증가에 유리하다.

 

 6 .  Multilevel Queue Scheduling

여러 개의 큐를 두고, 각 큐에 우선순위 및 정책 부여한다.
큐 간 이동이 불가능하여 하위 큐는 상위 큐가
비워지지 않으면 실행되지 않는다.

예: 시스템 프로세스와 사용자 프로세스를 분리 운영

 

 7 .  Multilevel Feedback Queue Scheduling

Multilevel Queue의 단점을 보완한 방식.

프로세스가 실행 특성에 따라 큐 간 이동 가능하며,
입출력 중심 또는 CPU 중심 프로세스에 따라
유동적인 대응도 가능하다.

---

 

06 예제

모든 프로세스(P1, P2, P3)가 시간 0에 도착했으며,
선입선처리(FCFS: First-Come, First-Served) 방식으로 서비스를 받는다고 가정한다.

이 방식은 비선점(Non-preemptive) 스케줄링이다.

프로세스	Burst Time (ms)
P1	24
P2	3
P3	3

 

Gantt 차트

|             P1             | P2 | P3 |
0                           24   27   30

 

대기 시간

• P1: 0 (도착하자마자 실행 시작)
• P2: 24 (P1이 종료될 때까지 대기)
• P3: 27 (P1과 P2가 종료될 때까지 대기)

 

평균 대기 시간

Average Waiting Time

 

---

 

 

FCFS 스케줄링 – Convoy Effect 발생 예시
프로세스들은 시간 0에 도착하며, 도착 순서는 P2, P3, P1이다.

각 프로세스의 Burst Time은 다음과 같다고 가정한다:

• P2: 3ms
• P3: 3ms
• P1: 24ms

 

Gantt 차트 (FCFS, 비선점):

| P2 | P3 |             P1             |
0    3    6                           30

 

대기 시간

• P2: 0ms (가장 먼저 실행)
• P3: 3ms (P2가 끝난 뒤 실행)
• P1: 6ms (P2, P3가 끝난 뒤 실행)

 

평균 대기 시간:

 

호위 효과

Convoy Effect

하나의 긴 작업이 먼저 CPU를 점유하면,
뒤따르는 짧은 작업들이 모두 대기하게 되는 현상이다.

마치 도로에서 느린 차량(군용 차량 등)이 앞을 막고 있어
뒤따르는 차량들이 줄지어 정체되는 상황과 유사하다.

CPU와 입출력 장치의 이용률이 낮아지고, 전체 시스템 성능이 저하된다.

FCFS 방식은 프로세스의 길이를 고려하지 않으므로 
짧은 작업이 긴 작업 뒤에 배치되면 성능에 부정적인 영향을 준다.

 

---

 

SJF 스케줄링

각 프로세스의 다음 CPU 버스트(CPU를 사용하는 시간)를 기준으로,
CPU가 사용 가능해졌을 때 가장 짧은 버스트 시간을 가진 프로세스에게
우선적으로 CPU를 할당하는 방식이다.

 

이 스케줄링 방식에는 두 가지 형태가 있다.

비선점형 (Non-preemptive) 방식.

새로운 프로세스가 도착하더라도
현재 실행 중인 프로세스보다 더 짧은 CPU 버스트를 가지고 있는 경우,
현재 실행 중인 프로세스가 자신의 CPU 버스트를 끝낼 때까지 기다리게 된다.

 

예를 들어, 다음과 같은 프로세스 집합이 있을 때:

프로세스	버스트 시간
P1	6ms
P2	8ms
P3	7ms
P4	3ms

 

비선점형 SJF 스케줄링을 적용하면,
프로세스들이 P4 → P1 → P3 → P2 순으로 실행되며,
각 프로세스의 대기 시간은 각각 0ms, 3ms, 9ms, 16ms가 된다.

 

평균 대기 시간

 

---

 

선점형 (Preemptive) 방식.

최소 잔여 시간 우선 스케줄링
SRTF: Shortest Remaining Time First이라고도 불린다.

이 방식에서는 새로운 프로세스가 도착했을 때,
그 프로세스의 CPU 버스트 시간이 현재 실행 중인 프로세스의
남은 시간보다 짧다면, 현재 프로세스를 중단하고 새로운 프로세스를 실행시킨다.

SJF 스케줄링은 평균 대기 시간을 최소화하는 최적의 알고리즘으로 알려져 있다.

 

프로세스	도착시간	실행시간
P1	0	8
P2	1	4
P3	2	9
P4	3	5

 

 

실행 흐름

Preemptive SJF = SRTF 기준

시간	실행 중인 프로세스	설명
0–1	P1	처음 도착, 실행 시작 (남은 시간: 7)
1–2	P2	P2 도착, P1보다 짧아서 선점 (3 남음)
2–3	P2	P3 도착, 9 vs 3 → P2 계속 실행 (2 남음)
3–4	P2	P4 도착, 5 vs 2 → P2 계속 실행 (1 남음)
4–5	P2	P2 종료
5–10	P4	가장 짧은 5 실행
10–17	P1	남은 7 실행
17–26	P3	9 실행

 

각 프로세스의 종료 시간

프로세스	도착시간	실행시간	완료시간	반환시간(완료 - 도착)	대기시간(반환 - 실행)
P1	0	8	17	17 - 0 = 17	17 - 8 = 9
P2	1	4	5	5 - 1 = 4	4 - 4 = 0
P3	2	9	26	26 - 2 = 24	24 - 9 = 15
P4	3	5	10	10 - 3 = 7	7 - 5 = 2

 

평균 대기 시간

---

[교제] 운영체제 제 10판

---