CPU 스케줄링CPU Scheduling
준비 큐에서 기다리는 프로세스 · 스레드 가운데 다음에 CPU 를 쓸 하나를 고르고, 언제 그 차례를 거둘지 정하는 운영체제의 규칙이다.
1요약
- CPU 스케줄링은 운영체제 커널이 준비 큐에서 다음 실행 주체를 고르는 규칙이며, 리눅스는 일반 작업에 2.6.23 부터 CFS 를, 6.6 부터 EEVDF 를 쓰고(커널 CFS 문서 · Kernel Newbies 6.6) 실시간 작업에는 SCHED_FIFO · SCHED_RR · SCHED_DEADLINE 을 따로 둔다(sched(7)).
- 고르는 규칙 하나가 같은 작업의 체감을 바꾼다 — 본문의 작업 넷(가정 값)에서 도착 순서로만 돌리면 평균 응답 시간이 4.75 ms 이고, 2 ms 씩 돌아가며 나누면 1.75 ms 로 줄지만 문맥 교환은 3회에서 7회로 는다.
- 「느리다」는 실행 큐 대기인지 실행 자체인지로 가른다 — 실행 가능한 작업 수가 코어 수보다 계속 크고 프로세스의 큐 대기 시간이 실행 시간보다 크면 스케줄링 문제이고, 그렇지 않으면 코드 · I/O 쪽이다.
2등장 배경
1950년대 일괄 처리 컴퓨터는 들어온 순서대로 작업을 끝까지 돌렸고, 긴 계산 하나가 앞에 서면 짧은 작업도 몇 시간씩 결과를 기다렸다. 1962년 MIT 의 Corbató 등은 시분할 시스템 CTSS 에서 우선순위가 다른 큐 여러 개를 두고 짧게 끝나는 대화형 작업을 위 큐에 남기는 방식을 발표했다(Corbató 외 1962) — 오늘의 다단계 피드백 큐의 출발점이다.
1973년 Liu · Layland 는 주기 작업의 마감을 지키는 고정 우선순위(RMS) · 마감 순서(EDF) 규칙과 그 이용률 한계를 증명했다(Liu · Layland 1973). 1995년 Stoica · Abdel-Wahab 은 몫에 비례해 CPU 를 나누면서 지연 상한을 주는 EEVDF 를 냈다(Stoica · Abdel-Wahab 1995).
리눅스는 2.6.23 에서 「이상적이고 정밀한 다중 작업 CPU」를 흉내 내는 CFS 를 들였고(커널 CFS 문서), 2023-10-29 공개한 6.6 에서 CFS 를 EEVDF 로 바꿨다(Kernel Newbies 6.6) — 공평한 몫은 그대로 두고 짧은 시간 조각을 원하는 작업의 응답을 앞당기려는 변경이다(커널 EEVDF 문서).
3쉽게 이해하기 — 창구 하나뿐인 은행
작은 은행에 창구가 하나뿐이다. 손님은 번호표를 뽑고 의자에 앉고, 안내원이 다음 손님을 창구로 부른다. 업무가 긴 손님도 모래시계 2분이 다 되면 의자 맨 뒤로 돌아가고, 서류를 놓고 온 손님은 의자를 비우고 나갔다가 돌아와 다시 줄을 선다. 너무 오래 기다린 손님은 안내원이 순번을 올려 준다.
그림 1 · 안내원(스케줄러)이 의자(준비 큐)의 손님(프로세스) 가운데 하나를 창구(CPU)로 부르고, 모래시계(타임 퀀텀)가 다 되면 그 손님을 다시 줄 뒤로 보낸다.
그림 2 · 업무가 긴 손님이 먼저 창구에 서면 짧은 손님들이 줄줄이 기다리고, 모래시계로 2분씩 나누면 모두 곧 창구 앞에 한 번은 선다.
| 비유 속 역할 | 실제 이름 | 실제로 하는 일 |
|---|---|---|
| 손님 | 프로세스 · 스레드 | CPU 를 쓸 차례를 기다리는 실행 주체 |
| 번호표 · 의자 | 준비 큐 | 실행 가능한 작업을 정책이 정한 순서로 줄 세운다 |
| 안내원 | 스케줄러 | 큐에서 다음 작업 하나를 고른다 |
| 창구 | CPU 코어 | 한 번에 작업 하나만 명령을 실행한다 |
| 모래시계 | 타임 퀀텀 · 타이머 인터럽트 | 시간이 다 되면 실행 중인 작업을 선점한다 |
| 서류 찾으러 나감 | I/O 대기 | 작업이 스스로 CPU 를 내놓고 대기 큐로 간다 |
| 순번 올리기 | 에이징 | 오래 기다린 작업의 우선순위를 올려 기아를 막는다 |
| 업무 끝 | 종료 | 반환 시간이 정해지고 큐에서 빠진다 |
⚠ 비유가 맞지 않는 곳: 실제 스케줄러는 손님의 남은 업무 시간을 미리 알지 못해 지난 실행 기록으로 추정하며, 교대 한 번(문맥 교환)에도 레지스터 저장 · 캐시 손실 같은 비용이 붙는다.
4구조 — 준비 큐 · 스케줄러 · 디스패처와 다시 고르는 때
스케줄러는 준비 큐에서 하나를 고르는 정책이고, 디스패처는 고른 작업의 문맥을 CPU 에 올리는 장치다. 고르는 때가 «실행 중인 작업이 스스로 내놓을 때»(대기 진입 · 종료)뿐이면 비선점, 타이머 만료 · 더 높은 우선순위 작업의 도착에도 고르면 선점이다.
그림 3 · 비선점 스케줄러는 작업이 대기에 들거나 끝날 때만 다시 고르고, 선점 스케줄러는 타이머 만료 · 우선순위 도착에도 실행 중인 작업을 준비 큐로 돌려보낸다.
| 요소 | 역할 | 값 · 근거 |
|---|---|---|
| 준비 큐 | 실행 가능 작업의 줄 | CFS = vruntime 순 레드블랙 트리(커널 CFS 문서) |
| 스케줄러 | 다음 작업 하나 고르기 | CFS = 트리 맨 왼쪽 · EEVDF = 자격 있는 작업 중 가상 마감이 가장 이른 것(커널 EEVDF 문서) |
| 디스패처 | 문맥 저장 · 복원 · CPU 넘기기 | 교환마다 레지스터 · 캐시 비용 |
| 타이머 인터럽트 | 선점의 방아쇠 | SCHED_ |
| 대기 큐 | I/O · 이벤트 기다림 | 깨어나면 준비 큐로 |
| 정책 · 우선순위 | 고르는 기준 | 실시간 1 ~ 99 · nice −20 ~ +19(sched(7)) |
| 기준 | 뜻 | 좋아지는 방향 |
|---|---|---|
| 처리량 | 단위 시간에 끝난 작업 수 | 클수록 |
| 반환 시간 | 도착 → 종료 | 작을수록 |
| 대기 시간 | 준비 큐에 있던 시간 합(반환 − 실행) | 작을수록 |
| 응답 시간 | 도착 → 처음 CPU 를 받음 | 작을수록 · 대화형의 기준 |
5동작 — 퀀텀 2 ms 라운드 로빈으로 작업 넷 돌리기
작업 A · B · C · D 가 0 · 1 · 2 · 3 ms 에 도착하고 CPU 시간이 6 · 3 · 1 · 4 ms 이다(설명용 가정 값 · 코어 하나 · 교환 비용 0 · 같은 시각이면 새 도착이 선점된 작업보다 앞에 선다).
- t = 0 — 준비 큐에 A 하나라 A 가 오르고 타이머가 2 ms 를 잰다.
- t = 2 — A 의 퀀텀이 끝나 선점되어 큐 끝으로 간다. 그사이 B(1) · C(2)가 와 있어 큐는 C · A 가 되고 B 가 오른다.
- t = 4 — B 가 선점되고 t = 3 에 온 D 뒤에 선다. 큐 맨 앞 C 가 오른다.
- t = 5 — C 는 1 ms 만 쓰고 끝난다. 퀀텀이 남아도 곧바로 A 가 오른다(C 반환 3 ms).
- t = 7 · 9 — A 가 다시 2 ms 를 쓰고 큐 끝으로, D 가 2 ms 를 쓰고 큐 끝으로 간다.
- t = 10 · 12 · 14 — B(남은 1 ms) · A · D 가 차례로 끝난다(반환 9 · 12 · 11 ms).
- 결과 — 평균 응답 1.75 · 대기 5.25 · 반환 8.75 ms · 문맥 교환 7회다.
그림 4 · 라운드 로빈은 퀀텀이 끝날 때마다 실행 중인 작업을 큐 끝으로 보내, 차례가 한 작업씩 넘어가며 모든 작업이 4 ms 안에 한 번은 CPU 에 오른다.
같은 작업 넷을 규칙만 바꿔 돌리면 줄어드는 지표가 서로 다르다. 남은 시간이 가장 짧은 작업을 선점해 올리는 SRTF 가 평균 대기를 가장 줄이지만, 가장 긴 A 는 8 ms 를 기다린다.
그림 5 · 같은 작업 넷이라도 SRTF 는 평균 대기, RR 은 응답 시간을 가장 줄이고, 그 대가로 RR 은 문맥 교환이 가장 많고 SRTF 는 긴 작업 A 를 끝까지 미룬다.
🔑 선점은 응답 시간을 사는 대신 문맥 교환으로 값을 치르고, 짧은 작업 우선은 평균을 줄이는 대신 긴 작업의 기다림에 상한을 없앤다 — 알고리즘은 «무엇을 줄일지»를 정한 뒤에 고른다.
긴 작업이 끝없이 밀리는 기아는 우선순위 · SJF 계열에서 생기고, 기다린 시간만큼 우선순위를 올리는 에이징이 상한을 만든다. 다단계 피드백 큐는 새 작업을 퀀텀이 짧은 위 큐에 넣고, 퀀텀을 다 쓰면 아래 큐로 내려 CPU 를 오래 쓰는 작업과 대화형 작업을 가른다(Corbató 외 1962) — 아래 큐를 주기적으로 위로 올리는 것이 이 방식의 에이징이다.
6비교 — 알고리즘별 고르는 기준과 대가
| 알고리즘 | 선점 | 고르는 기준 | 줄어드는 지표 | 대가 |
|---|---|---|---|---|
| FCFS | 비선점 | 도착 순서 | 교환 수 최소 | 긴 작업 뒤 호위 효과(convoy) |
| SJF | 비선점 | 실행 시간 짧은 순 | 평균 대기 | 실행 시간 추정 필요 · 기아 |
| SRTF | 선점 | 남은 시간 짧은 순 | 평균 대기 · 반환 | 교환 증가 · 긴 작업 기아 |
| 우선순위 | 둘 다 | 정해 둔 순위 | 중요 작업 응답 | 기아 → 에이징 필요 |
| RR | 선점 | 큐 순서 + 퀀텀 | 응답 시간 | 퀀텀이 짧을수록 교환 비용 |
| 다단계 피드백 큐 | 선점 | 큐 위치(사용 이력) | 대화형 응답 | 조정 값(큐 수 · 퀀텀 · 승급 주기)이 많음 |
| CFS → EEVDF | 선점 | 덜 받은 몫 · 가상 마감 | 몫의 공평 · 짧은 조각 작업의 지연 | 우선순위 «절대 보장»은 없음 |
분석대화형 서버 · 데스크톱은 응답 시간이 기준이라 RR 계열(리눅스 일반 정책 = EEVDF)을, 끝나는 시각만 중요한 일괄 작업은 교환이 적은 FCFS · SJF 계열(리눅스 SCHED_BATCH)을 고른다. 근거는 그림 5 의 응답 · 교환 열과 sched(7) 의 SCHED_BATCH 설명(일괄 작업에 맞춘 정책).
실시간 작업은 평균이 아니라 마감을 기준으로 삼아, 주기가 짧을수록 높은 우선순위를 주는 RMS 와 마감이 가까운 순으로 고르는 EDF 를 쓴다(Liu · Layland 1973) — 이용률 판정 식은 임베디드 시스템이 다룬다.
7실무 진단 — 실행 큐 대기와 정책 문제 가르기
분석시스템 전체의 실행 가능 작업 수(vmstat r)를 코어 수와 먼저 견주고, 그다음 느린 프로세스 하나의 큐 대기 시간(schedstat 둘째 값)으로 «CPU 가 모자란가 · 순서에서 밀리는가»를 가른다. 근거는 vmstat(8) 의 r 열 정의와 커널 schedstat 문서의 세 필드.
| # | 증상 | 의심 원인 | 구분 | 확인 명령 | 판정 기준(근거) |
|---|---|---|---|---|---|
| 1 | 모든 응답이 느림 | 실행 가능 작업 > 코어 수 | 준비 큐 | vmstat 1 · cat /proc/pressure/cpu | r 이 코어 수보다 계속 큼(vmstat(8)) · some avg10 상승(커널 PSI 문서) |
| 2 | 한 프로세스만 늦음 | 순서에서 밀림(nice · 정책) | 정책 | cat / · ps -o pid,ni,cls,comm | 둘째 값(큐 대기 ns)이 첫째 값(실행 ns)보다 빨리 늚(커널 schedstat 문서) |
| 3 | 처리량은 낮은데 교환 수가 큼 | 실행 가능 스레드 과다 · 짧은 조각 | 디스패처 | vmstat 1 의 cs | cs(초당 문맥 교환)가 평소보다 크게 늘고 us 는 그대로(vmstat(8)) |
| 4 | 일반 작업 전부 멈춘 듯함 | SCHED_ | 실시간 정책 | chrt -p <pid> · sysctl kernel. | 실시간 작업은 1초에 0.95초까지만(기본 950000 / 1000000 · sched(7)) |
| 5 | 낮은 순위 작업이 끝나지 않음 | 기아 | 정책 | / 반복 확인 | 셋째 값(실행한 조각 수)이 늘지 않음(커널 schedstat 문서) |
1 행으로 «CPU 가 모자란가»를 먼저 가른다. r 이 코어 수 이하인데 느리면 스케줄링이 아니라 I/O · 잠금 쪽이고, 스레드들이 서로 쥔 잠금을 기다려 멈췄으면 교착상태 진단으로 넘긴다.
8시험 대비
www.q-net.or.kr시험에서는 FCFS · SJF · SRTF · RR 을 같은 작업으로 돌려 지표를 견주는 비교형, CFS 에서 EEVDF 로 바뀐 리눅스 스케줄러를 묻는 동향 · 발전형이 나올 수 있다. 비교형이면 도착 · 실행 시간 표를 먼저 정하고 간트 차트와 평균 대기 · 응답을 계산해 «무엇을 줄이는가»로 결론을 내며, 동향형이면 vruntime → lag · 가상 마감의 차이를 한 표로 둔다.
- 개요 — 정의 · 선점 ↔ 비선점 · 기준 넷(처리량 · 반환 · 대기 · 응답)
- 구조 — 그림 3(준비 큐 · 스케줄러 · 디스패처 · 대기 큐 · 다시 고르는 때)
- 동작 — 그림 4 RR 퀀텀 2 ms 사례(큐 변화 · 교환 7회)
- 비교 — 그림 5 간트 비교 + 평균 대기 · 응답 · 교환 수 표
- 문제와 대책 — 기아 · 호위 효과 ↔ 에이징 · 다단계 피드백 큐
- 동향 — 리눅스 CFS(2.6.23) → EEVDF(6.6) · 실시간 RMS · EDF 한 줄
꼭 쓸 키워드
선점비선점응답 시간반환 시간타임 퀀텀호위 효과기아에이징다단계 피드백 큐EEVDF
다른 답안과 차이를 내는 한 가지는 같은 작업 넷의 간트 비교에 문맥 교환 수 열을 붙여 «평균 대기 최소 = 최선»이 아님을 보이는 것이다.
9오해와 사실
- 오해퀀텀을 짧게 할수록 시스템이 빨라진다.사실응답 시간은 줄지만 교환이 늘어 처리량이 준다 — 사례에서 퀀텀 2 ms RR 은 평균 대기가 5.25 ms 로 FCFS 4.75 ms 보다 길고 교환은 7회다(그림 5).
- 오해리눅스의 nice −20 작업은 다른 작업이 끝날 때까지 CPU 를 독차지한다.사실nice 는 일반 정책 안의 몫(가중치)만 바꾸며, 실행 순서를 절대적으로 정하는 것은 실시간 정책 1 ~ 99 다(sched(7)).
- 오해SJF 는 실행 시간을 알고 고른다.사실운영체제는 앞으로의 실행 시간을 미리 알 수 없어 지난 실행 길이로 추정하며, 그래서 실제 커널은 SJF 대신 사용 이력으로 큐를 옮기는 방식(다단계 피드백 큐 · 몫 기반)을 쓴다.
10핵심 정리
| 구분 | 고르는 때 | 고르는 기준 | 줄이는 지표 | 기아 | 리눅스 대응 |
|---|---|---|---|---|---|
| FCFS | 대기 진입 · 종료 | 도착 순서 | 교환 수 | 없음(호위 효과) | SCHED_ |
| SJF · SRTF | 종료(SJF) · 도착(SRTF) | 실행 · 남은 시간 | 평균 대기 | 있음 | 없음(추정 필요) |
| 우선순위 | 도착 · 종료 | 순위 값 | 중요 작업 응답 | 있음 → 에이징 | 실시간 1 ~ 99 |
| RR | 퀀텀 만료 | 큐 순서 | 응답 시간 | 없음 | SCHED_ |
| 다단계 피드백 큐 | 퀀텀 만료 · 승급 | 사용 이력 | 대화형 응답 | 승급으로 막음 | — |
| CFS | 틱 · 깨어남 | 가장 작은 vruntime | 몫의 공평 | 없음 | 2.6.23 ~ 6.5 |
| EEVDF | 틱 · 깨어남 | 자격 + 가장 이른 가상 마감 | 짧은 조각 작업의 지연 | 없음 | 6.6 부터 |
| RMS · EDF | 주기 도착 | 주기 · 마감 | 마감 놓침 | 과부하 때 | SCHED_ |
11참고 문헌
- 먼저 볼 문헌
- ★ EEVDF Scheduler — The Linux Kernel documentation — 리눅스 기본 스케줄러가 CFS 에서 EEVDF 로 바뀐 이유와 lag · 가상 마감을 볼 때
- ★ CFS Scheduler — The Linux Kernel documentation — vruntime · 레드블랙 트리 · 맨 왼쪽 작업 고르기를 원문으로 볼 때
- ★ sched(7) Linux manual page — 리눅스 정책 여섯(SCHED_OTHER ~ SCHED_DEADLINE)과 실시간 우선순위 · 제한 값을 볼 때
- ★ Earliest Eligible Virtual Deadline First: A Flexible and Accurate Mechanism for Proportional Share Resource Allocation (TR-95-22) — EEVDF 의 자격(eligible) · 가상 마감 정의를 처음 낸 논문으로 볼 때
- 본문 근거
- An Experimental Time-Sharing System — F. J. Corbató · M. Merwin-Daggett · R. C. Daley · AFIPS Spring Joint Computer Conference 335-344 · 1962-05 ·
doi.org/10.1145/1460833.1460871· 확인 2026-11-04 - Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment — C. L. Liu · J. W. Layland · Journal of the ACM 20(1) 46-61 · 1973-01 ·
doi.org/10.1145/321738.321743· 확인 2026-11-04 - sched_rr_get_interval(2) Linux manual page — man7.org · 2026-11 ·
man7.org/linux/man-pages/man2/sched_rr_get_interval.2.html· 확인 2026-11-04 - Linux 6.6 — Linux Kernel Newbies — kernelnewbies.org · 2023-10 ·
kernelnewbies.org/Linux_6.6· 확인 2026-11-04 - Scheduler Statistics — The Linux Kernel documentation — kernel.org · 2026-11 ·
docs.kernel.org/scheduler/sched-stats.html· 확인 2026-11-04 - PSI - Pressure Stall Information — The Linux Kernel documentation — kernel.org · 2026-11 ·
docs.kernel.org/accounting/psi.html· 확인 2026-11-04 - vmstat(8) Linux manual page — man7.org · 2026-11 ·
man7.org/linux/man-pages/man8/vmstat.8.html· 확인 2026-11-04 - chrt(1) Linux manual page — man7.org · 2026-11 ·
man7.org/linux/man-pages/man1/chrt.1.html· 확인 2026-11-04