CPU 스케줄링

준비 큐에 줄 선 프로세스 중 누구를 다음 실행으로 올릴지 결정하는 단기 스케줄러의 정책 — 알고리즘 8종(비선점 4·선점 4)과 평균 대기/반환 시간 계산을 한 번에 잡는다. 매 회차 2~3문항이 굳어 나오고, 그중 평균 대기/반환 시간 계산 1문항은 빠지지 않는 4과목의 중심 영역이다. 33강 준비 큐·Dispatch·Timeout 전이가 여기서 알고리즘으로 살아 움직인다.

핵심 암기 + 공식: 목표 5종 이처대반응(이용률↑·처리량↑·대기↓·반환↓·응답↓) · 시간 용어 5종 도실완반대(도착·실행·완료·반환·대기) · 핵심 2공식 반환=완료−도착 / 대기=반환−실행 · HRN=(대기+서비스)÷서비스(클수록 먼저)

스케줄링 기초

CPU 스케줄링 정의와 스케줄러 3종 ·스케줄링 개요·

[정의] CPU 스케줄링(CPU Scheduling) = 준비 큐(Ready Queue)의 여러 프로세스 중 다음에 CPU를 사용할 프로세스를 선택하는 OS의 의사결정. 이 선택을 담당하는 것이 단기 스케줄러이고, 그 결정 정책이 오늘의 알고리즘 8종이다.

[흐름] 단기 스케줄러가 '누구'를 정하면 → Dispatch(33강 전이)가 그 프로세스를 실제 CPU로 올린다. 단일 코어는 한 순간 한 프로세스만 실행하므로 매 순간 '누가 먼저?'의 판단이 필요하다.

[분류] 스케줄러 3종 — 호출 빈도와 결정 대상으로 갈린다.

🔑 암기 장기=메모리 적재 / 중기=Swap / 단기=CPU 할당. 8종 알고리즘은 전부 단기 스케줄러의 정책. ⚠️ 함정 보기에서 장기·중기 스케줄러가 'CPU 할당 결정' 자리에 들어가 있으면 오답. CPU 할당은 단기 전속. 🎯 빈출 스케줄러 3종 결정 대상 매칭. 간헐.

스케줄링 목표 5종 — 이처대반응 ·스케줄링 목표·

[분류] CPU 스케줄링이 추구하는 5대 목표. 방향(↑/↓)이 함께 묶여 외워야 한다.

🔑 암기 이처대반응 — 위 둘(이용률·처리량)은 ↑, 아래 셋(대기·반환·응답)은 ↓. ⚠️ 함정 방향 뒤집기가 매년 1순위 — "CPU 이용률 최소화"·"처리량 최소화"·"대기 시간 최대화"는 전부 함정(방향 반대). 처리량(완료 개수·↑)과 응답 시간(첫 응답까지·↓)을 바꿔치기하는 함정도 단골. 🎯 빈출 "목표가 아닌 것" 소거형 — 방향이 뒤집힌 보기 골라내기. 보통. 💡 보충 반환 시간 vs 응답 시간 — 반환=도착~완료까지 전체, 응답=요청 후 첫 반응까지. 둘 다 ↓ 목표지만 측정 구간이 다르다.

시간 용어 5종 + 핵심 2공식 — 도실완반대 ·계산의 입력·시험 1순위·

[분류] 모든 계산 문제의 입력 단어가 그대로 두문자에 들어 있다. 측정 3축(주어지거나 간트로 읽음) + 계산 2축(공식으로 구함).

[흐름] 핵심 2공식 — 매 회차 계산 1문항의 정답 키.

 반환 시간 = 완료 시간 − 도착 시간
 대기 시간 = 반환 시간 − 실행 시간

검증 예: P1(도착0·실행5·완료5) → 반환=5−0=5, 대기=5−5=0(바로 실행). P2(도착1·실행3·완료8) → 반환=8−1=7, 대기=7−3=4(P1 끝까지 4 기다림).

🔑 암기 도실완반대 — 도실완=측정 3축 / 반대=계산 2축. 반환=완료−도착 / 대기=반환−실행. ⚠️ 함정 "대기=완료−도착"❌(→그건 반환). "반환=도착−완료"❌(→부호 반대, 완료−도착). 측정/계산 분류 바꿔치기. 🎯 빈출 도착·실행이 주어지면 반환·대기를 두 공식으로 계산. 매 회차 계산 문제의 토대.

알고리즘 8종 — 비선점 4 · 선점 4

비선점 vs 선점 + 호위·기아·Aging 3쌍 ·알고리즘 분류·34강 관통·

[비교] 8종은 CPU를 강제로 뺏을 수 있는가로 갈린다 — 이 분별이 시험 1순위.

[분류] 호위·기아·Aging — 34강 전체를 관통하는 3쌍. 부작용 2 + 해결책 1.

🔑 암기 비선점=못 뺏음·호위·오버헤드↓ / 선점=강제 회수·응답성↑·오버헤드↑. 호위=FCFS / 기아=SJF·우선순위 / Aging=방지. ⚠️ 함정 호위 vs 기아 — 호위는 결국 완료(길게 기다려도 끝남), 기아는 완료 불가(영원히 못 받음). "Aging=부작용"❌(→해결책). 비선점에선 Timeout 전이가 없다(Timeout은 선점·RR 전속). 🎯 빈출 비선점/선점 분류·3쌍 매칭. 매 회차 1순위. 💡 보충 비선점=식당 선착순 줄서기 / 선점=응급실, 더 급한 환자 즉시 우선.

FCFS — 도착 순서 그대로 ·비선점 ①·

[정의] FCFS(First Come First Served) = 준비 큐에 도착한 순서 그대로 CPU 할당. 가장 단순한 알고리즘.

🔑 암기 FCFS = 비선점 + 도착 순서 + 호위 효과 + FIFO. ⚠️ 함정 "FCFS=평균 대기 최소"❌(→그건 SJF). 호위 효과를 SJF 단점으로 바꿔치기하는 함정. 🎯 빈출 결정 단서 '도착 순서·선입선출·호위'면 즉답 FCFS. 보통. 💡 보충 마트에서 카트 가득 채운 한 명 뒤에 음료 한 병 든 사람도 길게 기다리는 모습이 호위 효과.

SJF — 짧은 작업 먼저 ·비선점 ②·

[정의] SJF(Shortest Job First) = 준비 큐 중 실행 시간이 가장 짧은 프로세스에 CPU 할당. FCFS 호위 효과를 풀려고 등장했다.

🔑 암기 SJF = 비선점 + 짧은 작업 + 평균 대기 최소 + 기아. ⚠️ 함정 "SJF=선점"❌(→비선점, 선점 버전은 SRT). "SJF=호위 효과"❌(→호위는 FCFS). 🎯 빈출 "평균 대기 최소 알고리즘"·SJF/SRT 선점 분별. 매 회차. 💡 보충 빠른 계산대에서 짧은 손님 먼저 — 평균 대기는 줄지만, 짧은 손님이 끝없이 오면 카트 가득한 손님은 차례가 안 온다(기아).

HRN — SJF 기아를 공식으로 보완 ·비선점 ③·시험 1순위·

[정의] HRN(Highest Response Ratio Next) = 응답률(우선순위 값)이 가장 높은 프로세스에 CPU 할당. SJF의 기아를 공식 하나로 보완한다.

 우선순위(응답률) = (대기 시간 + 서비스 시간) ÷ 서비스 시간
                  → 값이 클수록 먼저

[흐름] 한 공식에 두 효과 — 분모(서비스)가 작을수록 값↑(짧은 작업 우대=SJF 효과), 분자의 대기가 커질수록 값↑(오래 기다림 우대=Aging 효과). 효율 + 공정성 동시.

계산 예:

→ 순서 P2 → P1 → P3 (값 클수록 먼저)

🔑 암기 HRN = (대기+서비스)÷서비스 · 값 클수록 먼저 · SJF 기아 보완. ⚠️ 함정 분자분모 자리 바꾸기가 매년 1순위 — "(서비스+대기)/대기"❌·"서비스/(대기+서비스)"❌. 분모는 항상 서비스. "값 작을수록 먼저"❌(→클수록). 🎯 빈출 공식 계산(가장 먼저 실행될 프로세스). 매 회차. 💡 보충 분자(대기+서비스)가 같으면 분모(서비스)가 작은 쪽이 값이 커서 먼저.

우선순위 스케줄링 — 비선점·선점 + Aging ·비선점 ④ / 선점 ③·

[정의] 우선순위가 가장 높은 프로세스에 CPU 할당. 비선점·선점 두 버전이 모두 존재한다.

[분류] 우선순위 결정 방식 — 정적(생성 시 고정·변경 없음) vs 동적(실행 중 자동 조정·Aging·HRN 공식).

[흐름] Aging = 대기 시간이 길어질수록 우선순위를 점진 자동 상승시키는 기아 방지 기법.

 T=0    P5 우선순위 5 (낮음)
 T=10   P5 → 6
 T=20   P5 → 7
 T=30   P5 → 8
 T=40   P5 → 9 → CPU 획득

🔑 암기 우선순위 = 비선점·선점 두 버전 / 정적·동적 / 기아 → Aging. Aging = 대기 길수록 우선순위 자동↑·기아 방지. ⚠️ 함정 "Aging=부작용"❌(→해결책). "Aging=우선순위 자동 하락"❌(→상승). HRN의 동적 우선순위도 같은 원리(공식이 매번 갱신). 🎯 빈출 Aging 정의(상승/하락 방향)·기아 방지 기법 매칭. 매 회차.

RR — Time Quantum 시분할 ·선점 ①·시험 1순위·

[정의] RR(Round Robin) = 각 프로세스에 Time Quantum(시간 할당량)만큼만 CPU 할당, 소진 시 강제 회수(Timeout). 시분할(Time Sharing)의 대표.

[흐름] 한 주기 — A를 CPU로 올림(Dispatch) → Quantum 동안 실행 → 소진 시 Timeout → 문맥 교환(상태를 PCB에 저장) → A를 준비 큐 맨 뒤로 → 큐 맨 앞 B Dispatch → 반복.

[비교] Time Quantum 트레이드오프 — 양 끝 모두 단점, 중간이 정답.

🔑 암기 RR = 선점 + Time Quantum + 시분할 + Timeout 전이 + 원형 큐 + 기아 없음. ⚠️ 함정 "Quantum 작을수록 좋음"❌(→너무 작으면 오버헤드 폭증). "Quantum 무한대=응답성↑"❌(→FCFS화·응답성↓). 🎯 빈출 Time Quantum 크기의 영향(방향 뒤집기). 매 회차. 💡 보충 노래방 — 1인당 30분=Quantum 너무 큼, 5초=마이크 돌리는 시간이 노래보다 김(오버헤드), 한 곡=적절.

SRT — SJF의 선점 버전 ·선점 ②·

[정의] SRT(Shortest Remaining Time) = 매 순간 잔여 실행 시간이 가장 짧은 프로세스에 CPU 할당. SJF를 선점형으로 만든 것.

🔑 암기 SRT = SJF 선점 버전 · 트리거: 새 도착 시 잔여 비교 · 기아 가능. ⚠️ 함정 RR과 트리거 혼동 — RR은 Quantum 소진(Timeout)으로 선점, SRT는 새 프로세스 도착으로 선점. 🎯 빈출 SJF vs SRT 분별('선점' 단어가 키). 보통. 💡 보충 응급실에서 진료 중 더 위급한 환자 도착 시 즉시 교체 — 새 도착이 트리거.

MLQ vs MLFQ — 큐 간 이동 여부 ·선점 ④·

[비교] 둘 다 여러 개의 큐를 둔다. 큐 간 프로세스 이동이 되는가가 분별 키.

🔑 암기 MLQ=분리만 / MLFQ=분리+이동(Feedback)·Aging 내장. F=Feedback=큐 간 이동. ⚠️ 함정 "MLFQ는 큐 1개"❌(→여러 개). "둘 다 비선점"❌(→둘 다 선점). "MLFQ는 Quantum 사용 안 함"❌(→큐별 Quantum 사용). 🎯 빈출 MLQ/MLFQ 핵심 차이(이동 가능 여부). 간헐~보통.

알고리즘 8종 종합 매트릭스 ·종합·시험 직전 회수·

[표] 선점/비선점 → 기준 → 단점 → 보완 — 네 칸을 한 줄로.

[분류] 목표별 최적 알고리즘

🔑 암기 비선점 4 = FCFS·SJF·HRN·우선순위 / 선점 4 = RR·SRT·우선순위·MLQ/MLFQ. ⚠️ 함정 HRN을 선점으로 분류하는 함정 단골('H=Highest'라 선점처럼 보이나 비선점). 우선순위·MLQ/MLFQ는 비선점/선점 양쪽 보기로 흔들기. 🎯 빈출 8종 분류·단점 매칭·목표별 최적. 매 회차 1순위.

평균 대기·반환 시간 계산

계산 4단계 절차 + FCFS 계산 ·계산·매 회차 고정·

[흐름] 모든 계산 문제는 같은 4단계 — 알고리즘만 바뀌고 절차는 동일.

[표] FCFS 예 — 입력: P1(도착0·실행10) P2(도착1·실행5) P3(도착2·실행3). 순서 P1→P2→P3.

 시간:  0          10      15    18
 구간:  |    P1    |  P2  | P3 |

평균 대기 = (0+9+13)/3 = 22/3 ≈ 7.33 · 평균 반환 = (10+14+16)/3 = 40/3 ≈ 13.33

P3는 실행 3으로 짧지만 P1·P2 뒤에서 13 기다림 — 호위 효과.

🔑 암기 도착·실행 표 → 간트 → 반환·대기 표 → 평균. 도착이 0이 아니면 완료를 간트에서 정확히 읽어 반환=완료−도착. ⚠️ 함정 머리로만 계산하면 분기점에서 실수 — 간트를 그려 완료 시간을 눈으로 확정. 🎯 빈출 FCFS 평균 대기/반환. 매 회차. 💡 보충 모두 동시 도착(도착 0)이면 대기 = 앞 프로세스 실행 시간의 누적 합 — 간트 없이도 즉답.

SJF·RR 계산 + 3세트 비교 ·계산·

[표] SJF(비선점) — 같은 입력 P1(0·10) P2(1·5) P3(2·3). t=10에 P1 완료 후 큐의 P2(5)·P3(3) 중 짧은 P3 먼저 → 순서 P1→P3→P2.

 시간:  0          10    13      18
 구간:  |    P1    | P3 |  P2  |

평균 대기 = (0+8+12)/3 = 20/3 ≈ 6.67 (FCFS 7.33보다 작음 — SJF 평균 대기 최소 확인)

[표] RR(Time Quantum=2) — 입력 P1(5)·P2(3)·P3(1), 모두 t=0 도착.

 순서: P1(0-2) P2(2-4) P3(4-5) P1(5-7) P2(7-8) P1(8-9)
 시간:  0  2  4 5  7 8 9
 구간:  |P1|P2|P3|P1|P2|P1|

평균 대기 = (4+5+4)/3 = 13/3 ≈ 4.33

[비교] 같은 입력, 다른 알고리즘, 다른 결과 — 절차(4단계)는 동일.

🔑 암기 SJF는 큐에 모인 것 중 짧은 것을 고름(도착 시각 주의) · RR은 Quantum 소진마다 맨 뒤로 + 완료 시각으로 반환 계산. ⚠️ 함정 RR에서 완료 시각을 간트 끝이 아니라 마지막 실행 구간 끝으로 읽어야(P3는 t=5 완료, 전체 끝 9 아님). SJF는 선점 안 함 — 도착해도 현재 작업 끝까지. 🎯 빈출 SJF·RR 평균 대기/반환. 매 회차 고정.

기출 다지기

[기출 1 출제] 다음 중 선점(Preemptive) 스케줄링에 해당하는 알고리즘을 모두 고른 것은? (모두 고르기)

• ① FCFS, SJF
• ② SJF, RR
• ③ RR, SRT
• ④ RR, SRT, HRN

[기출 2 출제] 다음 중 CPU 스케줄링의 목표로 옳지 않은 것은? (부정형)

• ① CPU 이용률을 높인다
• ② 단위 시간당 처리량을 높인다
• ③ 평균 대기 시간을 늘린다
• ④ 응답 시간을 줄인다

[기출 3 출제] HRN 스케줄링에서 다음 4개 프로세스 중 가장 먼저 실행될 프로세스는? (계산)

• ① P1
• ② P2
• ③ P3
• ④ P4

[기출 4 출제] FCFS 스케줄링에서 평균 대기 시간은? (모두 t=0 동시 도착, 순서 P1→P2→P3→P4) (계산)

• ① 6
• ② 7
• ③ 7.5
• ④ 8

[기출 5 출제] RR 스케줄링에서 Time Quantum 크기의 영향으로 옳은 것은? (옳은 것 고르기)

• ① Quantum이 너무 작으면 응답성이 떨어진다
• ② Quantum이 너무 크면 문맥 교환 오버헤드가 증가한다
• ③ Quantum이 무한대에 가까우면 FCFS와 같아진다
• ④ Quantum 크기는 평균 대기 시간에 영향을 주지 않는다

[기출 6 출제] Aging(에이징) 기법에 대한 설명으로 옳은 것은? (옳은 것 고르기)

• ① 짧은 작업이 긴 작업 뒤에서 길게 대기하는 현상
• ② 짧은 작업이 계속 도착해 긴 작업이 무한 대기하는 현상
• ③ 대기 시간이 길어질수록 우선순위가 점진적으로 상승하는 기법
• ④ 대기 시간이 길어질수록 우선순위가 점진적으로 하락하는 기법

[기출 7 출제] MLFQ와 MLQ의 가장 핵심적인 차이는? (옳은 것 고르기)

• ① MLFQ는 큐가 1개, MLQ는 여러 개이다
• ② MLFQ는 비선점, MLQ는 선점이다
• ③ MLFQ는 큐 간 프로세스 이동이 가능하다
• ④ MLFQ는 Time Quantum을 사용하지 않는다

한 장 요약

🎯 합격 한 끗: 이처대반응(목표·방향) + 도실완반대(시간·2공식) + 8종(비선점 4/선점 4) + HRN=(대기+서비스)/서비스·클수록 먼저 + 3쌍(호위=FCFS/기아=SJF·우선순위/Aging=방지) + 계산 4단계(순서→간트→공식→평균). 34강 출제 2~3문항은 거의 모두 알고리즘 분류·HRN 공식·Aging 분별·평균 대기/반환 계산 네 영역에서 나온다.