IT › 컴퓨터 시스템 › 운영체제 › 프로세스 관리

CPU 스케줄링CPU Scheduling

준비 큐에서 기다리는 프로세스 · 스레드 가운데 다음에 CPU 를 쓸 하나를 고르고, 언제 그 차례를 거둘지 정하는 운영체제의 규칙이다.

1요약

  1. CPU 스케줄링은 운영체제 커널이 준비 큐에서 다음 실행 주체를 고르는 규칙이며, 리눅스는 일반 작업에 2.6.23 부터 CFS 를, 6.6 부터 EEVDF 를 쓰고(커널 CFS 문서 · Kernel Newbies 6.6) 실시간 작업에는 SCHED_FIFO · SCHED_RR · SCHED_DEADLINE 을 따로 둔다(sched(7)).
  2. 고르는 규칙 하나가 같은 작업의 체감을 바꾼다 — 본문의 작업 넷(가정 값)에서 도착 순서로만 돌리면 평균 응답 시간이 4.75 ms 이고, 2 ms 씩 돌아가며 나누면 1.75 ms 로 줄지만 문맥 교환은 3회에서 7회로 는다.
  3. 「느리다」는 실행 큐 대기인지 실행 자체인지로 가른다 — 실행 가능한 작업 수가 코어 수보다 계속 크고 프로세스의 큐 대기 시간이 실행 시간보다 크면 스케줄링 문제이고, 그렇지 않으면 코드 · 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분이 다 되면 의자 맨 뒤로 돌아가고, 서류를 놓고 온 손님은 의자를 비우고 나갔다가 돌아와 다시 줄을 선다. 너무 오래 기다린 손님은 안내원이 순번을 올려 준다.

대기 의자 준비 큐 손님 B 손님 C 손님 D 번호표 맨 앞 = 왼쪽 · 새 손님은 오른쪽 끝에 앉음 안내원 스케줄러 누구를 부를지 정함 창구 하나 CPU 손님 A 퀀텀 모래시계 2분 1 2 모래시계가 다 되면 맨 뒤로 서류 가지러 나감 I/O 대기 3 순번 올리기 에이징 4 1 안내원이 다음 손님을 창구로 부름 → 디스패치 2 2분이 다 되면 맨 뒤로 → 선점 3 서류를 가지러 나갔다 돌아와 다시 줄 → 대기 · 깨어남 4 오래 기다린 손님은 순번을 올림 → 에이징

그림 1 · 안내원(스케줄러)이 의자(준비 큐)의 손님(프로세스) 가운데 하나를 창구(CPU)로 부르고, 모래시계(타임 퀀텀)가 다 되면 그 손님을 다시 줄 뒤로 보낸다.

번호표 뽑기손님이 의자에 앉음
안내원 호출다음 손님을 고름
모래시계2분이 지나면 뒤로
서류 찾기의자를 비우고 나감
순번 올리기오래 기다린 손님을 앞으로
업무 끝창구를 떠남
먼저 온 순서대로 FCFS · 비선점 처음 창구에 서기까지 기다린 분 A · 업무 6분 바로 B · 업무 3분 5 C · 업무 1분 7 D · 업무 4분 7 평균 4.75분 · 교대 3회 2분씩 나누기 RR · 퀀텀 2 처음 창구에 서기까지 기다린 분 A · 업무 6분 바로 B · 업무 3분 1 C · 업무 1분 2 D · 업무 4분 4 평균 1.75분 · 교대 7회 막대 = 처음 창구에 서기까지 기다린 시간 → 응답 시간 손님 A · B · C · D 는 0 · 1 · 2 · 3분에 차례로 도착 · 교대 = 문맥 교환

그림 2 · 업무가 긴 손님이 먼저 창구에 서면 짧은 손님들이 줄줄이 기다리고, 모래시계로 2분씩 나누면 모두 곧 창구 앞에 한 번은 선다.

비유 속 역할실제 이름실제로 하는 일
손님프로세스 · 스레드CPU 를 쓸 차례를 기다리는 실행 주체
번호표 · 의자준비 큐실행 가능한 작업을 정책이 정한 순서로 줄 세운다
안내원스케줄러큐에서 다음 작업 하나를 고른다
창구CPU 코어한 번에 작업 하나만 명령을 실행한다
모래시계타임 퀀텀 · 타이머 인터럽트시간이 다 되면 실행 중인 작업을 선점한다
서류 찾으러 나감I/O 대기작업이 스스로 CPU 를 내놓고 대기 큐로 간다
순번 올리기에이징오래 기다린 작업의 우선순위를 올려 기아를 막는다
업무 끝종료반환 시간이 정해지고 큐에서 빠진다

⚠ 비유가 맞지 않는 곳: 실제 스케줄러는 손님의 남은 업무 시간을 미리 알지 못해 지난 실행 기록으로 추정하며, 교대 한 번(문맥 교환)에도 레지스터 저장 · 캐시 손실 같은 비용이 붙는다.

4구조 — 준비 큐 · 스케줄러 · 디스패처와 다시 고르는 때

스케줄러는 준비 큐에서 하나를 고르는 정책이고, 디스패처는 고른 작업의 문맥을 CPU 에 올리는 장치다. 고르는 때가 «실행 중인 작업이 스스로 내놓을 때»(대기 진입 · 종료)뿐이면 비선점, 타이머 만료 · 더 높은 우선순위 작업의 도착에도 고르면 선점이다.

선점 — 타이머 만료 · 더 높은 우선순위 도착(선점형만) 생성 도착 · fork 준비 큐 B C D 스케줄러 정책 = 다음 하나 CPU 실행 중 = A 디스패치 문맥 교환 대기 큐 I/O · 이벤트 기다림 종료 I/O 요청(둘 다) exit(둘 다) I/O 완료 (선점형은 다시 고름) 작업이 줄 서는 큐 정책 · 제어 선점 경로 그 밖의 전이 · 「둘 다」 = 비선점 · 선점 모두 다시 고름

그림 3 · 비선점 스케줄러는 작업이 대기에 들거나 끝날 때만 다시 고르고, 선점 스케줄러는 타이머 만료 · 우선순위 도착에도 실행 중인 작업을 준비 큐로 돌려보낸다.

요소역할값 · 근거
준비 큐실행 가능 작업의 줄CFS = vruntime 순 레드블랙 트리(커널 CFS 문서)
스케줄러다음 작업 하나 고르기CFS = 트리 맨 왼쪽 · EEVDF = 자격 있는 작업 중 가상 마감이 가장 이른 것(커널 EEVDF 문서)
디스패처문맥 저장 · 복원 · CPU 넘기기교환마다 레지스터 · 캐시 비용
타이머 인터럽트선점의 방아쇠SCHED_RR 퀀텀 기본 100 ms(sched_rr_get_interval(2))
대기 큐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 · 같은 시각이면 새 도착이 선점된 작업보다 앞에 선다).

  1. t = 0 — 준비 큐에 A 하나라 A 가 오르고 타이머가 2 ms 를 잰다.
  2. t = 2 — A 의 퀀텀이 끝나 선점되어 큐 끝으로 간다. 그사이 B(1) · C(2)가 와 있어 큐는 C · A 가 되고 B 가 오른다.
  3. t = 4 — B 가 선점되고 t = 3 에 온 D 뒤에 선다. 큐 맨 앞 C 가 오른다.
  4. t = 5 — C 는 1 ms 만 쓰고 끝난다. 퀀텀이 남아도 곧바로 A 가 오른다(C 반환 3 ms).
  5. t = 7 · 9 — A 가 다시 2 ms 를 쓰고 큐 끝으로, D 가 2 ms 를 쓰고 큐 끝으로 간다.
  6. t = 10 · 12 · 14 — B(남은 1 ms) · A · D 가 차례로 끝난다(반환 9 · 12 · 11 ms).
  7. 결과 — 평균 응답 1.75 · 대기 5.25 · 반환 8.75 ms · 문맥 교환 7회다.
CPU A B C A D B A D 1 2 3 4 5 6 0 2 4 5 7 9 10 12 14 ms 준비 큐 앞 ↓ 뒤 빔 C A A D B D B B A A D D 빔 도착 — B = 1 ms · C = 2 ms · D = 3 ms (A = 0 ms) 굵은 테두리 = 방금 선점되어 큐 끝으로 간 작업 CPU 위 실행 각 열 = 그 시각에 다음 작업을 고른 직후의 큐 · 퀀텀 2 ms · 시각 = 가정 값

그림 4 · 라운드 로빈은 퀀텀이 끝날 때마다 실행 중인 작업을 큐 끝으로 보내, 차례가 한 작업씩 넘어가며 모든 작업이 4 ms 안에 한 번은 CPU 에 오른다.

같은 작업 넷을 규칙만 바꿔 돌리면 줄어드는 지표가 서로 다르다. 남은 시간이 가장 짧은 작업을 선점해 올리는 SRTF 가 평균 대기를 가장 줄이지만, 가장 긴 A 는 8 ms 를 기다린다.

평균 대기 평균 응답 교환 FCFS A B C D 4.75 4.75 3 SJF A C B D 4.25 4.25 3 SRTF A B C B D A A 가 8 ms 기다림 2.75 0.5 5 RR 2 A B C A D B A D 5.25 1.75 7 0 3 6 9 12 14 ms 실행 긴 작업이 밀린 구간(기아의 씨앗) 굵은 글자 = 그 열의 최솟값 · 교환은 최댓값 · 단위 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/cpur 이 코어 수보다 계속 큼(vmstat(8)) · some avg10 상승(커널 PSI 문서)
2한 프로세스만 늦음순서에서 밀림(nice · 정책)정책cat /proc/<pid>/schedstat · ps -o pid,ni,cls,comm둘째 값(큐 대기 ns)이 첫째 값(실행 ns)보다 빨리 늚(커널 schedstat 문서)
3처리량은 낮은데 교환 수가 큼실행 가능 스레드 과다 · 짧은 조각디스패처vmstat 1 의 cscs(초당 문맥 교환)가 평소보다 크게 늘고 us 는 그대로(vmstat(8))
4일반 작업 전부 멈춘 듯함SCHED_FIFO 작업의 CPU 독점실시간 정책chrt -p <pid> · sysctl kernel.sched_rt_runtime_us실시간 작업은 1초에 0.95초까지만(기본 950000 / 1000000 · sched(7))
5낮은 순위 작업이 끝나지 않음기아정책/proc/<pid>/schedstat 반복 확인셋째 값(실행한 조각 수)이 늘지 않음(커널 schedstat 문서)

1 행으로 «CPU 가 모자란가»를 먼저 가른다. r 이 코어 수 이하인데 느리면 스케줄링이 아니라 I/O · 잠금 쪽이고, 스레드들이 서로 쥔 잠금을 기다려 멈췄으면 교착상태 진단으로 넘긴다.

8시험 대비

출제 정보 정보관리(137회, 119회, 96회) · 컴퓨터시스템응용(138회, 129회)문제 원문 — 큐넷 자료실 「기출문제(기술사)」 www.q-net.or.kr

시험에서는 FCFS · SJF · SRTF · RR 을 같은 작업으로 돌려 지표를 견주는 비교형, CFS 에서 EEVDF 로 바뀐 리눅스 스케줄러를 묻는 동향 · 발전형이 나올 수 있다. 비교형이면 도착 · 실행 시간 표를 먼저 정하고 간트 차트와 평균 대기 · 응답을 계산해 «무엇을 줄이는가»로 결론을 내며, 동향형이면 vruntime → lag · 가상 마감의 차이를 한 표로 둔다.

답안 목차
  1. 개요 — 정의 · 선점 ↔ 비선점 · 기준 넷(처리량 · 반환 · 대기 · 응답)
  2. 구조 — 그림 3(준비 큐 · 스케줄러 · 디스패처 · 대기 큐 · 다시 고르는 때)
  3. 동작 — 그림 4 RR 퀀텀 2 ms 사례(큐 변화 · 교환 7회)
  4. 비교 — 그림 5 간트 비교 + 평균 대기 · 응답 · 교환 수 표
  5. 문제와 대책 — 기아 · 호위 효과 ↔ 에이징 · 다단계 피드백 큐
  6. 동향 — 리눅스 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_FIFO(같은 순위 안)
SJF · SRTF종료(SJF) · 도착(SRTF)실행 · 남은 시간평균 대기있음없음(추정 필요)
우선순위도착 · 종료순위 값중요 작업 응답있음 → 에이징실시간 1 ~ 99
RR퀀텀 만료큐 순서응답 시간없음SCHED_RR · 기본 100 ms
다단계 피드백 큐퀀텀 만료 · 승급사용 이력대화형 응답승급으로 막음—
CFS틱 · 깨어남가장 작은 vruntime몫의 공평없음2.6.23 ~ 6.5
EEVDF틱 · 깨어남자격 + 가장 이른 가상 마감짧은 조각 작업의 지연없음6.6 부터
RMS · EDF주기 도착주기 · 마감마감 놓침과부하 때SCHED_DEADLINE(EDF)

11참고 문헌

  1. 먼저 볼 문헌
  2. ★ EEVDF Scheduler — The Linux Kernel documentation — 리눅스 기본 스케줄러가 CFS 에서 EEVDF 로 바뀐 이유와 lag · 가상 마감을 볼 때
    kernel.org · 2026-11 · docs.kernel.org/scheduler/sched-eevdf.html · 확인 2026-11-04
  3. ★ CFS Scheduler — The Linux Kernel documentation — vruntime · 레드블랙 트리 · 맨 왼쪽 작업 고르기를 원문으로 볼 때
    kernel.org · 2026-11 · docs.kernel.org/scheduler/sched-design-CFS.html · 확인 2026-11-04
  4. ★ sched(7) Linux manual page — 리눅스 정책 여섯(SCHED_OTHER ~ SCHED_DEADLINE)과 실시간 우선순위 · 제한 값을 볼 때
    man7.org · 2026-11 · man7.org/linux/man-pages/man7/sched.7.html · 확인 2026-11-04
  5. ★ Earliest Eligible Virtual Deadline First: A Flexible and Accurate Mechanism for Proportional Share Resource Allocation (TR-95-22) — EEVDF 의 자격(eligible) · 가상 마감 정의를 처음 낸 논문으로 볼 때
    I. Stoica · H. Abdel-Wahab · Old Dominion University · 1995 · people.eecs.berkeley.edu/~istoica/papers/eevdf-tr-95.pdf · 확인 2026-11-04
  6. 본문 근거
  7. 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
  8. 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
  9. 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
  10. Linux 6.6 — Linux Kernel Newbies — kernelnewbies.org · 2023-10 · kernelnewbies.org/Linux_6.6 · 확인 2026-11-04
  11. Scheduler Statistics — The Linux Kernel documentation — kernel.org · 2026-11 · docs.kernel.org/scheduler/sched-stats.html · 확인 2026-11-04
  12. PSI - Pressure Stall Information — The Linux Kernel documentation — kernel.org · 2026-11 · docs.kernel.org/accounting/psi.html · 확인 2026-11-04
  13. vmstat(8) Linux manual page — man7.org · 2026-11 · man7.org/linux/man-pages/man8/vmstat.8.html · 확인 2026-11-04
  14. chrt(1) Linux manual page — man7.org · 2026-11 · man7.org/linux/man-pages/man1/chrt.1.html · 확인 2026-11-04