CPU 스케줄링 기본 개념
CPU 버스트와 I/O 버스트
프로세스 실행은 CPU 버스트와 I/O 버스트의 교대로 구성된다.
[프로세스 실행 사이클]
CPU 버스트 -> I/O 버스트 -> CPU 버스트 -> I/O 버스트 -> ...
|-------| |--------| |--|
CPU 실행 I/O 대기 CPU 실행
(계산) (디스크 읽기) (계산)
CPU 바운드 프로세스: 긴 CPU 버스트, 적은 I/O 버스트
I/O 바운드 프로세스: 짧은 CPU 버스트, 많은 I/O 버스트
선점형 vs 비선점형 스케줄링
- **비선점형(Non-preemptive)**: 프로세스가 자발적으로 CPU를 반납할 때까지 실행 계속
- **선점형(Preemptive)**: OS가 실행 중인 프로세스로부터 CPU를 강제로 회수 가능
CPU 스케줄링이 필요한 네 가지 상황이 있다.
1. 실행 상태에서 대기 상태로 전환 (I/O 요청) - 비선점
2. 실행 상태에서 준비 상태로 전환 (인터럽트) - 선점
3. 대기 상태에서 준비 상태로 전환 (I/O 완료) - 선점
4. 프로세스 종료 - 비선점
디스패처 (Dispatcher)
디스패처는 CPU 스케줄러가 선택한 프로세스에게 실제로 CPU를 넘겨주는 모듈이다.
- 컨텍스트 스위치 수행
- 사용자 모드로 전환
- 프로그램의 적절한 위치로 점프
디스패치 지연(dispatch latency)은 가능한 짧아야 한다.
스케줄링 기준
| 기준 | 설명 | 최적화 방향 |
| ----------------------- | ---------------------------- | ----------- |
| CPU 이용률 | CPU가 작업하는 시간 비율 | 최대화 |
| 처리량(Throughput) | 단위 시간당 완료 프로세스 수 | 최대화 |
| 총처리 시간(Turnaround) | 제출부터 완료까지 걸린 시간 | 최소화 |
| 대기 시간(Waiting) | 준비 큐에서 대기한 총 시간 | 최소화 |
| 응답 시간(Response) | 제출부터 첫 응답까지 시간 | 최소화 |
스케줄링 알고리즘
1. FCFS (First-Come, First-Served)
가장 단순한 스케줄링. 먼저 도착한 프로세스가 먼저 실행된다.
[FCFS 예시]
프로세스 도착 시간 CPU 버스트
P1 0 24
P2 0 3
P3 0 3
실행 순서: P1 -> P2 -> P3
Gantt 차트:
|----P1----|--P2--|--P3--|
0 24 27 30
대기 시간: P1=0, P2=24, P3=27
평균 대기 시간: (0+24+27)/3 = 17
만약 P2, P3, P1 순서라면?
|P2|P3|----P1----|
0 3 6 30
대기 시간: P1=6, P2=0, P3=3
평균 대기 시간: (6+0+3)/3 = 3 (큰 차이!)
**호위 효과(Convoy Effect)**: 긴 프로세스 뒤에 짧은 프로세스들이 줄서는 현상. FCFS의 대표적 단점이다.
2. SJF (Shortest-Job-First)
CPU 버스트가 가장 짧은 프로세스를 먼저 실행한다. 이론적으로 최적의 평균 대기 시간을 보장한다.
[SJF 예시 - 비선점형]
프로세스 도착 시간 CPU 버스트
P1 0 6
P2 2 8
P3 4 7
P4 5 3
Gantt 차트:
|--P1--|P4|---P3---|----P2----|
0 6 9 16 24
대기 시간: P1=0, P2=16, P3=5, P4=1
평균 대기 시간: (0+16+5+1)/4 = 5.5
[SRTF (Shortest Remaining Time First) - 선점형 SJF]
프로세스 도착 시간 CPU 버스트
P1 0 6
P2 2 8
P3 4 7
P4 5 3
시간 0: P1 시작 (남은: 6)
시간 2: P2 도착 (남은: 8) -> P1 계속 (남은: 4)
시간 4: P3 도착 (남은: 7) -> P1 계속 (남은: 2)
시간 5: P4 도착 (남은: 3) -> P1 계속 (남은: 1)
시간 6: P1 완료 -> P4 시작 (남은: 3)
시간 9: P4 완료 -> P3 시작 (남은: 7)
시간 16: P3 완료 -> P2 시작 (남은: 8)
시간 24: P2 완료
Gantt 차트:
|--P1--|P4|---P3---|----P2----|
0 6 9 16 24
SJF의 핵심 문제는 다음 CPU 버스트 길이를 미리 알 수 없다는 것이다. 실제로는 과거 버스트를 기반으로 **지수 평균(exponential averaging)**으로 예측한다.
다음 예측값 = alpha * 최근 실측값 + (1 - alpha) * 이전 예측값
alpha = 0이면 최근 값 무시 (이전 예측값만 사용)
alpha = 1이면 이전 예측 무시 (최근 실측값만 사용)
보통 alpha = 0.5 사용
3. 우선순위 스케줄링 (Priority Scheduling)
각 프로세스에 우선순위를 부여하고, 가장 높은 우선순위의 프로세스를 먼저 실행한다.
[우선순위 스케줄링 예시] (낮은 숫자 = 높은 우선순위)
프로세스 CPU 버스트 우선순위
P1 10 3
P2 1 1
P3 2 4
P4 1 5
P5 5 2
실행 순서: P2 -> P5 -> P1 -> P3 -> P4
Gantt 차트:
|P2|--P5--|----P1----|P3|P4|
0 1 6 16 18 19
평균 대기 시간: (6+0+16+18+1)/5 = 8.2
**기아(Starvation)**: 낮은 우선순위 프로세스가 영원히 실행되지 않는 문제. **에이징(Aging)** 기법으로 해결한다. 시간이 지남에 따라 대기 중인 프로세스의 우선순위를 점진적으로 높인다.
4. 라운드 로빈 (Round Robin)
시분할 시스템용 스케줄링. 각 프로세스에 고정 시간 할당량(time quantum)을 부여한다.
[라운드 로빈 예시] (시간 할당량 = 4)
프로세스 CPU 버스트
P1 24
P2 3
P3 3
Gantt 차트:
|P1|P2|P3|P1|P1|P1|P1|P1|
0 4 7 10 14 18 22 26 30
P1: 4단위 실행 -> 준비 큐 뒤로
P2: 3단위 실행 (완료)
P3: 3단위 실행 (완료)
P1: 나머지 20단위를 4씩 나눠 실행
대기 시간: P1=6, P2=4, P3=7
평균 대기 시간: (6+4+7)/3 = 5.67
시간 할당량(q)의 선택이 중요하다.
- q가 너무 크면: FCFS와 동일
- q가 너무 작으면: 컨텍스트 스위치 오버헤드 증가
- 경험적으로 CPU 버스트의 80%가 q 이내에 완료되도록 설정
5. 다단계 큐 스케줄링 (Multilevel Queue)
준비 큐를 여러 개의 큐로 분리하고, 각 큐에 다른 스케줄링 알고리즘을 적용한다.
[다단계 큐 스케줄링]
높은 우선순위
+------------------------------------------+
| 시스템 프로세스 | FCFS |
+------------------------------------------+
| 대화형 프로세스 | RR (q=8) |
+------------------------------------------+
| 대화형 편집 프로세스 | RR (q=16) |
+------------------------------------------+
| 배치 프로세스 | FCFS |
+------------------------------------------+
| 학생 프로세스 | FCFS |
+------------------------------------------+
낮은 우선순위
상위 큐가 비어야 하위 큐 실행 (고정 우선순위)
또는 큐 간 시간 분배 (예: 80% 대화형, 20% 배치)
6. 다단계 피드백 큐 (Multilevel Feedback Queue)
프로세스가 큐 사이를 이동할 수 있다. 가장 유연한 스케줄링 알고리즘이다.
[다단계 피드백 큐]
큐 0: RR (q=8) <--- 새 프로세스 진입
|
| q=8 내 미완료 시 큐 1로 이동
v
큐 1: RR (q=16)
|
| q=16 내 미완료 시 큐 2로 이동
v
큐 2: FCFS
동작 예시:
- CPU 버스트 짧은 프로세스: 큐 0에서 바로 완료 (빠른 응답)
- CPU 바운드 프로세스: 큐 0 -> 큐 1 -> 큐 2로 내려감
- I/O 완료 후 복귀하는 프로세스: 다시 큐 0으로 올라감
결과: I/O 바운드 + 대화형 프로세스에 높은 우선순위
CPU 바운드 프로세스는 낮은 큐에서 긴 시간 할당
스레드 스케줄링
- **PCS(Process-Contention Scope)**: 사용자 수준에서 같은 프로세스의 스레드끼리 경쟁
- **SCS(System-Contention Scope)**: 시스템 수준에서 모든 스레드가 경쟁
Linux와 Windows는 SCS를 사용한다. 커널 스레드만 CPU에 스케줄링된다.
다중 프로세서 스케줄링
접근 방법
- **비대칭 멀티프로세싱**: 하나의 프로세서가 모든 스케줄링 결정 (단순하지만 병목)
- **대칭 멀티프로세싱(SMP)**: 각 프로세서가 독립적으로 스케줄링 (현대 표준)
프로세서 친화성 (Processor Affinity)
프로세스는 현재 실행 중인 프로세서에 머무르려는 경향이 있다. 캐시에 데이터가 올라가 있기 때문이다.
- **소프트 친화성**: 가능하면 같은 프로세서에서 실행하지만 보장하지 않음
- **하드 친화성**: 특정 프로세서 집합에서만 실행을 보장
// Linux에서 프로세서 친화성 설정
#define _GNU_SOURCE
#include <sched.h>
void set_cpu_affinity(int cpu_id) {
cpu_set_t cpuset;
CPU_ZERO(&cpuset);
CPU_SET(cpu_id, &cpuset);
// 현재 스레드를 특정 CPU에 바인딩
sched_setaffinity(0, sizeof(cpuset), &cpuset);
}
부하 균형 (Load Balancing)
SMP 시스템에서 모든 프로세서에 작업을 고르게 분배한다.
- **Push 이주**: 주기적으로 과부하 프로세서의 작업을 이동
- **Pull 이주**: 유휴 프로세서가 바쁜 프로세서로부터 작업을 가져옴
Linux CFS (Completely Fair Scheduler)
Linux 2.6.23부터 기본 스케줄러로 사용되는 CFS는 각 프로세스에 "공정한" CPU 시간을 분배한다.
핵심 개념: 가상 실행 시간 (vruntime)
[CFS 동작 원리]
각 프로세스의 vruntime을 추적
vruntime이 가장 작은 프로세스를 다음에 실행
vruntime 증가율 = 실제 실행 시간 / 가중치(nice 값 기반)
nice 값이 낮은(우선순위 높은) 프로세스:
-> 가중치가 큼 -> vruntime이 천천히 증가 -> 더 자주 스케줄링
nice 값이 높은(우선순위 낮은) 프로세스:
-> 가중치가 작음 -> vruntime이 빨리 증가 -> 덜 자주 스케줄링
Red-Black 트리
CFS는 Red-Black 트리를 사용하여 프로세스를 vruntime 기준으로 관리한다.
[CFS의 Red-Black 트리]
vruntime 기준으로 정렬
(P3: 50)
/ \
(P1: 30) (P5: 70)
/ \ \
(P2: 20) (P4: 40) (P6: 80)
가장 왼쪽 노드(P2, vruntime=20)가 다음 실행 대상
삽입/삭제/검색: O(log N) 보장
// CFS에서 다음 실행할 프로세스 선택 (개념적 코드)
struct task_struct *pick_next_task_fair(struct rq *rq) {
struct cfs_rq *cfs_rq = &rq->cfs;
struct rb_node *left;
// Red-Black 트리에서 가장 왼쪽 노드 선택
// = vruntime이 가장 작은 프로세스
left = rb_first_cached(&cfs_rq->tasks_timeline);
if (!left)
return NULL;
struct sched_entity *se = rb_entry(left,
struct sched_entity,
run_node);
return container_of(se, struct task_struct, se);
}
목표 지연 시간 (Target Latency)
CFS는 목표 지연 시간 내에 모든 실행 가능한 프로세스가 최소 한 번은 실행되도록 보장한다.
예시: 목표 지연 시간 = 20ms, 실행 가능 프로세스 = 4개
동일 우선순위라면 각 프로세스에 5ms 할당
프로세스가 너무 많으면 최소 단위(min_granularity) 보장
알고리즘 비교 요약
[스케줄링 알고리즘 비교]
알고리즘 선점 기아 장점 단점
------- ---- ---- ---- ----
FCFS X X 단순함 호위 효과
SJF X O 최적 대기 시간 버스트 예측 어려움
SRTF O O SJF보다 나은 성능 버스트 예측 어려움
우선순위 둘 다 O 유연함 기아 (에이징 필요)
라운드 로빈 O X 공정, 좋은 응답 q 선택 중요
다단계 큐 O O 차별화된 서비스 큐 간 이동 불가
다단계 피드백 큐 O 가능 가장 유연 매개변수 설정 복잡
CFS O X 공정한 CPU 분배 구현 복잡
정리
CPU 스케줄링은 멀티프로그래밍 OS의 핵심이다. FCFS, SJF, 우선순위, 라운드 로빈 등 다양한 알고리즘이 있으며, 각각 처리량, 응답 시간, 공정성 사이에서 다른 절충점을 제공한다. Linux의 CFS는 Red-Black 트리와 가상 실행 시간 개념을 활용하여 효율적이면서도 공정한 스케줄링을 구현한다.
현재 단락 (1/214)
프로세스 실행은 CPU 버스트와 I/O 버스트의 교대로 구성된다.