[OS] CPU 스케줄링 - 7

CPU 스케줄링

CPU 스케줄링이 왜 필요한지, 어떤 기준으로 나뉘는지, 그리고 각 기법이 어떻게 동작하는지 정리한 글이다.

💡 핵심: CPU 스케줄링은 준비 큐에 있는 프로세스 중 누구에게 CPU를 줄지 결정하는 과정이다. 어떤 기준으로 고르느냐에 따라 시스템의 응답성과 처리 효율이 완전히 달라진다.

1. 스케줄링 3단계

스케줄링은 한 가지 시점에서만 일어나는 게 아니다. 프로세스가 생성되어 CPU에서 실행되기까지의 과정에서 총 세 단계의 스케줄러가 각자의 타이밍에 개입한다. 이 세 단계는 순서도, 범위의 크고 작음도 아니다. 언제 개입하느냐, 얼마나 자주 동작하느냐로 구분된 것이다.

프로그램 실행 요청

→

① 장기 스케줄러

→

준비 큐 대기

→

② 중기 스케줄러

→

③ 단기 스케줄러

→

CPU 실행

단계	다른 이름	하는 일	발생 빈도
장기 (Long Term)	작업 스케줄러, Job Scheduling	프로세스를 준비 큐에 올릴지 결정	드물게 (분 단위)
중기 (Medium Term)	중간 스케줄러, Swapping	메모리 과부하 시 프로세스를 디스크로 내림	가끔 (필요할 때)
단기 (Short Term)	CPU 스케줄러, Dispatcher	준비 큐 → CPU 할당 결정	매우 자주 (ms 단위)

이름의 "장기/중기/단기"는 각 스케줄러가 얼마나 긴 주기로 동작하는지를 가리킨다. 단기 스케줄러는 밀리초마다 계속 돌고 있는 반면, 장기는 새 프로그램이 실행될 때처럼 드물게만 개입한다.

⚠️ 현대에서 장기 스케줄링은 거의 사라졌다.
가상 메모리¹가 등장하면서 "프로세스 전체를 메모리에 올려야 실행 가능하다"는 전제가 무너졌다. 필요한 페이지만 그때그때 올리면 되니, 입장을 통제하는 문지기 역할이 불필요해진 것이다.

2. 선점 vs 비선점

단기 스케줄러가 CPU를 할당할 때, 이미 실행 중인 프로세스를 강제로 내보낼 수 있느냐 없느냐에 따라 방식이 나뉜다. 이게 선점/비선점의 핵심 질문이다.

🔒 비선점 (Non-Preemptive)

CPU를 한번 받으면
스스로 끝낼 때까지 독점

→ 다른 프로세스는
   무조건 기다려야 함

Context Switching 없음
오버헤드 낮음

⚡ 선점 (Preemptive)

더 높은 우선순위가 오면
CPU를 강제로 빼앗김

→ OS가 언제든
   개입할 수 있음

Context Switching 발생
응답성 높음

비선점은 구조가 단순하고 예측 가능하지만, 긴 작업 하나가 CPU를 오래 물고 있으면 뒤에 있는 짧은 작업들이 불필요하게 오래 기다린다. 반대로 선점은 응답성이 좋지만 Context Switching이 일어날 때마다 오버헤드가 발생하고, 공유 자원에 대한 동기화 문제도 함께 따라온다.

💡 현대 OS는 전부 선점 방식이다.
Linux 2.6+, Windows NT 계열, macOS 모두 선점 커널을 사용한다. 수십 개의 프로세스가 동시에 도는 환경에서 비선점은 응답성 자체를 포기하는 것이나 다름없기 때문이다. 단, 커널이 중요한 자료구조를 수정하는 순간만큼은 선점을 잠깐 차단한다. 선점 OS 안에 비선점 구간이 섬처럼 존재하는 셈이다.

3. 비선점 스케줄링 기법

CPU를 한번 주면 끝날 때까지 뺏지 않는 방식들이다. 어떤 프로세스를 먼저 고를지 기준만 다를 뿐이다.

FCFS

비선점

도착한 순서대로 처리. 구현이 제일 단순하다. 긴 작업이 앞에 오면 짧은 작업이 줄줄이 기다리는 Convoy Effect가 생긴다.

SJF (단기작업 우선)

비선점

남은 실행시간이 가장 짧은 것부터. 평균 대기시간이 가장 짧다는 게 수학적으로 증명됐다. 대신 긴 프로세스는 계속 밀려 무한연기에 빠질 수 있다.

HRN

비선점

우선순위 = (대기시간 + 실행시간) / 실행시간. 오래 기다릴수록 우선순위가 자동으로 올라가서 SJF의 무한연기 문제를 보완한다.

Priority (우선순위)

비선점

각 프로세스에 우선순위 숫자를 부여. 높은 것부터 실행. 우선순위가 같으면 FCFS로 처리한다. 낮은 우선순위 프로세스가 기아 상태에 빠질 수 있어 에이징²으로 해결한다.

Deadline (기한부)

비선점

각 프로세스에 마감 시간을 부여한다. 기한 내에 끝내면 유효하고, 못 끝내면 제거 후 처음부터 재시작한다. 작업이 필요한 자원 정보를 미리 정확하게 알아야 해서 실제로는 쓰기 까다롭다.

4. 선점 스케줄링 기법

실행 중인 프로세스를 내보낼 수 있는 방식들이다. 현대 OS가 실제로 사용하는 기법들이 여기 속한다.

RR (라운드 로빈)

선점

모든 프로세스에 Time Slice³를 동일하게 주고 순환. 가장 공평하다. Time Slice가 너무 짧으면 Context Switching 오버헤드가 커지고, 너무 길면 FCFS와 다를 게 없어진다.

SRT

선점

SJF의 선점 버전. 새 프로세스가 도착할 때마다 현재 실행 중인 것의 남은 시간과 비교해서 더 짧으면 즉시 교체한다. 대기시간이 SJF보다 짧지만 잦은 교체로 오버헤드가 발생한다.

선점 우선순위

선점

새로 도착한 프로세스의 우선순위가 현재 실행 중인 것보다 높으면 즉시 선점. 비선점 Priority를 선점 방식으로 바꾼 것이다.

다단계 큐 (MQ)

선점

프로세스를 여러 그룹으로 나눠 각 그룹마다 다른 큐를 사용한다. 큐마다 다른 스케줄링 정책을 적용할 수 있다. 단, 한번 배정된 큐에서 다른 큐로 이동이 불가능하다.

다단계 피드백 큐 (MFQ — Multi-Level Feedback Queue)

현대 OS가 실제로 채택한 알고리즘이다. Linux, Windows NT, macOS 모두 MFQ 기반의 스케줄러를 사용한다. 이름이 길고 생소해서 어렵게 느껴지지만, 단계별로 뜯어보면 앞서 나온 개념들의 조합이다.

왜 MFQ가 필요했나 — MQ의 한계

MFQ 이전에 다단계 큐(MQ)가 있었다. MQ는 프로세스를 성격별로 나눠 각 그룹에 다른 큐를 주는 방식이다. 예를 들어 "대화형 프로세스는 1번 큐, 배치 작업은 2번 큐" 같은 식이다. 그런데 치명적인 문제가 하나 있었다.

❌ MQ의 문제

한번 큐가 정해지면
절대 이동 불가

→ 프로세스 성격이
   바뀌어도 반영 안 됨

→ 낮은 큐 프로세스는
   계속 기아 상태

✅ MFQ의 해결

실행하면서 큐 간
이동이 가능

→ CPU 많이 쓰면
   낮은 큐로 강등

→ 오래 기다리면
   에이징으로 승격

"피드백"이라는 단어가 핵심이다. 프로세스가 실제로 CPU를 어떻게 쓰는지 결과를 보고, 그에 맞춰 큐 위치를 다시 조정한다. 미리 성격을 알 필요가 없다. 실행하면서 알아낸다.

구조 이해 — 큐가 여러 층으로 쌓여 있다

MFQ는 여러 개의 준비 큐가 계층적으로 존재한다. 위로 갈수록 우선순위가 높고, Time Slice가 짧다. 아래로 갈수록 우선순위가 낮고, Time Slice가 길다.

새 프로세스 →

큐 1 (최상위) — Time Slice: 8ms    [우선순위 높음 / RR]

시간 초과 시
↓ 강등

큐 2 — Time Slice: 16ms    [우선순위 중간 / RR]

시간 초과 시
↓ 강등

큐 3 (최하위) — Time Slice: 무제한    [우선순위 낮음 / FCFS]

↑ 에이징: 오래 기다리면 상위 큐로 승격

단계별 작동 원리

1

새 프로세스 진입 — 항상 최상위 큐부터

어떤 프로세스든 처음 들어오면 무조건 큐 1에 배정된다. 아직 이 프로세스가 어떤 성격인지 모르니까 일단 좋은 자리부터 주는 것이다.

2

8ms 안에 끝내면 — 그냥 종료

짧게 CPU를 쓰고 끝나는 프로세스 (예: 키 입력 처리, 클릭 이벤트)는 큐 1의 Time Slice 8ms 안에 작업이 완료된다. 이 프로세스는 계속 큐 1에 머물게 된다.

3

8ms 안에 못 끝내면 — 큐 2로 강등

Time Slice 8ms가 다 지나도 작업이 안 끝났다면, "이 프로세스는 CPU를 오래 쓰는 녀석이구나"라고 판단하고 큐 2로 내린다. 큐 2에서는 16ms를 주고 다시 실행 기회를 준다.

4

16ms도 못 끝내면 — 최하위 큐로 강등

큐 2에서도 못 끝내면 큐 3으로 이동된다. 최하위 큐는 Time Slice 제한 없이 FCFS로 처리된다. 여기서 작업이 완전히 완료될 때까지 실행된다. 단, 상위 큐에 새 프로세스가 오면 즉시 선점당한다.

5

오래 기다리면 — 에이징으로 승격

하위 큐에서 너무 오래 기다린 프로세스는 에이징에 의해 우선순위가 점진적으로 올라가서 상위 큐로 이동된다. 기아 상태를 막는 안전장치다.

왜 이게 좋은가 — 실제 예시로

실제 컴퓨터를 쓸 때를 생각해보면 된다. 사용자가 마우스를 움직이거나 키를 누르는 이벤트 처리는 순식간에 끝난다. 반면 파일 압축이나 영상 인코딩은 CPU를 계속 오래 쓴다. MFQ는 이 두 가지를 미리 분류하지 않고도 자동으로 구분해낸다.

프로세스 유형	실제 예시	MFQ에서의 위치	이유
I/O 중심	키보드 입력, 마우스 이벤트, 네트워크 응답	높은 큐 (1번)	조금 쓰고 I/O 대기로 빠지니 Time Slice 안에 끝남
CPU 중심	파일 압축, 영상 인코딩, 과학 계산	낮은 큐 (3번)	CPU를 계속 오래 써서 계속 강등됨
혼합형	게임 메인 루프, 서버 요청 처리	중간 큐 (2번)	짧은 연산 후 I/O, 반복하다 보면 중간에 자리잡음

응답이 빨라야 하는 대화형 작업은 자연스럽게 상위 큐에 머물고, 오래 걸리는 배치 작업은 하위 큐에서 천천히 처리된다. 스케줄러가 프로세스의 성격을 스스로 파악하는 구조다.

💡 한 줄 요약
MFQ는 "일단 다 좋은 자리에 앉혀놓고, CPU를 오래 쓰는 놈은 뒤로 밀고, 오래 기다린 놈은 앞으로 당기는" 자동 분류 시스템이다. 사전에 아무것도 몰라도 되고, 실행 결과가 곧바로 다음 스케줄링에 피드백된다는 게 핵심이다.

5. 전체 기법 한눈에 보기

기법	방식	핵심 기준	문제점
FCFS	비선점	도착 순서	Convoy Effect
SJF	비선점	실행시간 최소	무한연기 (긴 작업)
HRN	비선점	응답비율 최대	실행시간 예측 필요
Priority	비선점	우선순위	기아 상태 → 에이징 필요
Deadline	비선점	마감 시간	자원 정보 사전 필요
RR	선점	Time Slice 균등	Time Slice 크기 민감
SRT	선점	남은 시간 최소	잦은 교체 오버헤드
MQ	선점	그룹별 정책	큐 간 이동 불가
MFQ	선점	적응형 피드백	파라미터 튜닝 복잡

6. 현대 OS — 스케줄링 단위는 스레드

교재에서는 스케줄링 단위가 프로세스다. 그런데 현대 OS는 실제로 스레드¹¹ 단위로 CPU를 할당한다. 스케줄링 구조 자체가 바뀐 게 아니라, 그 구조를 적용하는 대상이 바뀐 것이다.

왜 스레드 단위로 내려왔나

초창기에는 프로세스 하나 = 실행 흐름 하나였다. 멀티스레드 개념 자체가 없었기 때문에 스케줄링 단위가 당연히 프로세스였다. 그런데 프로그램이 복잡해지면서 하나의 프로세스가 여러 작업을 동시에 처리해야 하는 상황이 됐다.

📦 옛날 — 프로세스 단위

CPU → 프로세스 A 전체
CPU → 프로세스 B 전체

프로세스 하나 = 실행 흐름 하나
→ 한 작업이 끝나야
   다음 작업 가능

🧵 현대 — 스레드 단위

CPU → 프로세스 A의 스레드 2
CPU → 프로세스 B의 스레드 1
CPU → 프로세스 A의 스레드 4

프로세스 안의 스레드 각각이
독립적인 스케줄링 단위

크롬을 예로 들면, 탭 렌더링·네트워크 요청·자바스크립트 실행이 동시에 일어난다. 이걸 프로세스 단위로 스케줄링하면 크롬 전체가 실행 흐름 하나밖에 가질 수 없다. 스레드 단위가 되면서 크롬 안의 스레드들이 각각 독립적으로 CPU를 받을 수 있게 됐다.

알고리즘은 그대로, 대상만 바뀐다

중요한 건 MFQ, RR, 선점/비선점 같은 알고리즘 자체는 아무것도 달라지지 않는다는 점이다. "다음에 CPU 줄 녀석을 어떻게 고르냐"는 방법론은 그대로고, 그 방법론이 판단하는 단위가 프로세스에서 스레드로 내려온 것이다. 중기 스케줄러(Swapping)는 예외로, 여전히 프로세스 단위로 동작한다. 메모리를 통째로 내리는 작업이기 때문이다.

스케줄러	현대의 대상 단위	달라진 점
장기	프로세스	현대에서는 거의 사라짐 (가상 메모리)
중기	프로세스	변화 없음. Swapping은 프로세스 단위
단기	스레드	CPU 할당 대상이 스레드로 바뀜
선점/비선점	스레드	개념 동일. "실행 중인 스레드"를 선점하는 것

💡 핵심: 스케줄링 구조와 알고리즘은 그대로다. "누구에게 CPU를 줄지 고르는 대상"이 프로세스에서 스레드로 바뀐 것뿐이다. 같은 프로세스 안의 스레드 간 Context Switching은 메모리 공간을 공유하기 때문에 프로세스 간 교체보다 훨씬 가볍다는 것도 스레드 단위로 내려온 부수적인 이점이다.

7. Unity 개발자 관점

Unity의 메인 스레드⁴ 구조는 비선점에 가깝다. Update 루프⁷가 돌고 있는 동안 다른 게임 로직이 끼어들 수 없고, 한 프레임이 끝나야 다음으로 넘어간다. 이 구조 때문에 메인 스레드에서 무거운 작업을 하면 프레임이 통째로 막혀버린다.

반면 C# Job System⁵의 Worker Thread⁶들은 OS의 선점 스케줄러 위에서 돌기 때문에 언제든 Context Switching이 발생할 수 있다. 그래서 Job에서 공유 데이터를 건드릴 때 NativeArray⁸나 Interlocked⁹ 같은 스레드 안전한 방식을 써야 하는 것이다. MFQ의 "I/O 중심은 높은 큐, CPU 중심은 낮은 큐"처럼, Unity Job System도 짧은 잡(Job)들이 긴 잡보다 빠르게 처리되도록 작업을 잘게 쪼개는 것이 유리하다.

RR의 Time Slice 개념은 게임 프레임 예산과 구조적으로 같다. 60fps 기준 한 프레임은 약 16ms다. 이 예산 안에서 PlayerLoop¹⁰의 Physics, Animation, Rendering, Script를 모두 나눠 처리해야 한다. Time Slice를 초과하면 프레임이 드랍되는 것처럼, 프레임 예산을 초과하면 프레임 드랍이 발생한다.

📎 용어 설명

1. 가상 메모리 (Virtual Memory) — 프로그램 전체를 물리 메모리(RAM)에 올리지 않아도 실행할 수 있게 해주는 기법. 실제로 필요한 페이지만 RAM에 올리고 나머지는 디스크에 대기시킨다.
2. 에이징 (Aging) — 자원을 오래 기다리는 프로세스의 우선순위를 시간이 지날수록 점진적으로 높여주는 기법. 무한연기와 기아 상태를 방지한다.
3. Time Slice (시간 할당량, Quantum) — RR 스케줄링에서 각 프로세스에게 부여되는 CPU 사용 시간 단위. 이 시간이 끝나면 다음 프로세스로 강제 전환된다.
4. 메인 스레드 (Main Thread) — Unity에서 게임 로직, 렌더링 명령, 물리 등 대부분의 작업이 실행되는 단일 스레드. Unity API 대부분은 메인 스레드에서만 호출 가능하다.
5. C# Job System — Unity에서 멀티스레드 병렬 처리를 안전하게 쓰기 위한 API. 작업을 Job 단위로 정의하고 내부 Worker Thread 풀에 분배해 병렬 실행한다.
6. Worker Thread — Job System이 내부적으로 관리하는 스레드 풀의 개별 스레드. CPU 코어 수에 맞게 자동으로 생성되며, 메인 스레드와 독립적으로 동작한다.
7. Update 루프 — Unity가 매 프레임마다 반복 실행하는 메인 루프. FixedUpdate → Update → LateUpdate 순서로 진행되며, 이 사이클이 한 프레임을 구성한다.
8. NativeArray — Unity Job System에서 스레드 간 데이터를 안전하게 공유하기 위한 배열 컨테이너. 관리 힙(Managed Heap) 대신 비관리 메모리(Unmanaged Memory)를 직접 사용해 GC 부담이 없다.
9. Interlocked — C#에서 여러 스레드가 동시에 같은 변수를 읽고 쓸 때 충돌 없이 원자적(Atomic)으로 연산하도록 보장하는 클래스. 별도의 락(Lock) 없이 Race Condition을 방지한다.
10. PlayerLoop — Unity가 한 프레임 동안 실행하는 전체 처리 순서. Initialization → EarlyUpdate → FixedUpdate → Update → PreLateUpdate → PostLateUpdate 등의 단계로 구성되며, 각 단계에 Physics, Animation, Rendering 등의 서브시스템이 배치된다.
11. 스레드 (Thread) — 프로세스 안에서 실제 실행 흐름을 담당하는 단위. 한 프로세스 안에 여러 스레드가 존재할 수 있고, 같은 프로세스의 스레드들은 메모리 공간을 공유한다. 프로세스가 공장이라면 스레드는 그 안에서 일하는 작업자다.