#04 CPU 스케줄링 알고리즘

CPU 스케줄링 알고리즘 — 어떤 순서로 실행할 건데?

프로세스/스레드 파트에서 CPU 스케줄링을 잠깐 언급했는데, 이번엔 제대로 파보자. "어떤 프로세스에 CPU를 줄 것인가"를 결정하는 게 스케줄링이야. 근데 그 방식이 하나가 아니라 여러 가지가 있고, 각각 트레이드오프가 있어.

---

왜 스케줄링이 필요해?

CPU core가 하나라면 한 번에 하나의 프로세스밖에 실행 못 해. 근데 컴퓨터에는 수십 개의 프로세스가 동시에 돌아가고 있어. 어떤 프로세스에 CPU를 줄지, 얼마나 줄지를 결정하는 게 CPU 스케줄링이야.

CPU - I/O Burst Cycle

프로세스는 계속 CPU만 쓰는 게 아니야. CPU를 쓰다가(CPU burst) → I/O를 기다리다가(I/O burst) → 다시 CPU를 쓰는 사이클을 반복해.

CPU burst → I/O burst → CPU burst → I/O burst → ...

위의 이미지에서 본 히스토그램을 보면 CPU burst 빈도가 흥미로운 분포를 가져.

• 짧은 CPU burst가 압도적으로 많아 — I/O bound job들. 잠깐 CPU 쓰고 I/O 기다리는 걸 반복해. 주로 사용자와 상호작용하는 프로그램들이야 (브라우저, 텍스트 에디터 등)
• 긴 CPU burst는 드물어 — CPU bound job들. 한 번 잡으면 오래 써. 영상 인코딩, 과학 계산 같은 거야

이 두 종류가 섞여 있어서 스케줄링이 필요해. CPU bound job이 CPU를 오래 독점하면 I/O bound job이 응답을 못 받아서 사용자가 답답함을 느끼거든. I/O bound job에 CPU를 우선적으로 주는 게 사용자 경험 면에서 유리해.

---

CPU Scheduler가 필요한 경우

프로세스는 실행 중에 네 가지 상태 전환을 겪어.

스케줄러가 개입해야 하는 시점은 이 전환이 일어날 때야.

1. running → waiting: I/O 요청 등으로 대기 상태로 전환될 때
2. running → ready: 인터럽트 발생으로 준비 상태로 밀려날 때
3. waiting → ready: I/O 완료 후 다시 준비 상태가 될 때
4. terminated: 프로세스가 종료될 때

여기서 1번과 4번만 해당하면 비선점형, 나머지까지 포함하면 선점형이야.

비선점형은 프로세스가 스스로 CPU를 놓을 때(1, 4번)만 스케줄링이 일어나고, 선점형은 인터럽트나 I/O 완료 같은 외부 이벤트(2, 3번)에도 스케줄러가 끼어들어.

---

선점형 vs 비선점형

스케줄링 알고리즘을 이해하려면 이 두 개념을 먼저 구분해야 해.

비선점형 (Non-preemptive)

CPU를 한 번 주면 그 프로세스가 자발적으로 내놓을 때까지 뺏지 않아. I/O를 기다리거나 종료할 때만 다른 프로세스로 넘어가.

• 컨텍스트 스위칭이 적어서 오버헤드가 낮아
• 응답 시간 예측이 가능해
• 긴 작업이 CPU를 독점하면 짧은 작업이 무조건 기다려야 해

선점형 (Preemptive)

더 높은 우선순위 프로세스가 들어오거나, 할당 시간이 끝나면 현재 실행 중인 프로세스에서 강제로 CPU를 회수해.

• 빠른 응답이 필요한 시분할 시스템에 유리
• CPU 독점을 막을 수 있어
• 컨텍스트 스위칭이 많아지면 오버헤드가 발생해

디스패처(Dispatcher)는 스케줄러가 선택한 프로세스에 실제로 CPU를 넘겨주는 모듈이야. 컨텍스트 교환, 사용자 모드 전환, 프로그램 재시작 위치로 이동하는 일을 해. 이 과정에 걸리는 시간을 디스패치 지연(Dispatch Latency)이라고 해.

---

스케줄링 성능 척도

알고리즘이 얼마나 좋은지 뭘로 판단하는지 알아야 비교가 돼.

아래 이미지를 보면 각 시간 개념이 잘 나와 있어.

 

척도	설명	목표
CPU 이용률 (Utilization)	CPU가 실제로 일한 시간 비율	최대화
처리량 (Throughput)	단위 시간당 완료된 프로세스 수	최대화
반환 시간 (Turnaround Time)	프로세스 생성부터 종료까지 전체 시간	최소화
대기 시간 (Waiting Time)	Ready Queue에서 기다린 시간의 합	최소화
응답 시간 (Response Time)	처음으로 CPU를 얻기까지 걸린 시간	최소화

대기 시간이랑 응답 시간이 헷갈리기 쉬운데, 차이가 있어.

• 대기 시간: Ready Queue에서 기다린 시간을 전부 합산한 것
• 응답 시간: CPU를 처음 받기까지 딱 한 번만 측정

 

주의할 점이 하나 있어 — 이 척도들은 "한 프로세스가 시작해서 끝날 때까지" 전체가 아니라 "CPU burst 건 1개"에 대한 것이야. 프로세스가 I/O 기다리는 시간은 스케줄링 성능 척도에서 빠져 있어.

 

---

알고리즘 별 정리

1. FCFS (First Come First Served) — 먼저 온 놈이 임자

먼저 도착한 프로세스가 먼저 CPU를 받는 방식. 비선점형이야.

P1이 24초를 혼자 쓰는 동안 P2, P3가 멍하니 기다려야 해. P2, P3는 3초짜리인데 17초나 기다리는 셈이야.

이게 호위 효과(Convoy Effect)야. CPU를 오래 쓰는 프로세스 뒤에 짧은 프로세스들이 줄줄이 늘어서서 기다리는 현상이야. CPU bound job 하나가 I/O bound job 여러 개를 막아버리면 전체 효율이 떨어져.

 

2. SJF (Shortest Job First) — 짧은 놈 먼저

CPU burst time이 짧은 프로세스에 먼저 CPU를 줘. 비선점형 + 선점형 둘 다 있어.

비선점형 SJF 

P1이 끝난 시점(7초)에 P2, P3, P4가 모두 도착해 있어. 이 중 가장 짧은 P3(burst=1)를 먼저 실행해. 비선점이라 실행 중인 P1은 끝까지 실행해.

 

선점형 SJF (SRTF, Shortest Remaining Time First) 

2초에 P2 도착 → P2 burst(4) < P1 남은 시간(5) → P1 중단하고 P2 실행. 이런 식으로 새 프로세스가 도착할 때마다 현재 실행 중인 프로세스의 남은 시간과 비교해서 더 짧으면 교체해.

 

여기서 의문이 생겼어 — "새 프로세스가 도착했다는 걸 어떻게 알아?" 새 프로세스가 Ready Queue에 들어오는 이벤트 자체가 스케줄러를 트리거해. 정확히는 프로세스를 생성하는 시스템 콜이 완료될 때 OS 커널이 스케줄러를 호출해서 현재 실행 중인 프로세스의 남은 시간과 새 프로세스의 burst time을 비교하는 거야. 

 

SJF의 이론적 장점은 명확해 — 평균 대기 시간이 가장 짧아. 근데 실제로 쓰기 어려운 이유가 있어. 다음 CPU burst time을 미리 알 수 없어. 보통 과거 burst 기록을 기반으로 지수 평균(Exponential Average)으로 예측하는 방식을 써.

 

3. Round Robin (RR) — 돌아가면서 공평하게

각 프로세스에 동일한 시간(Time Quantum, q)을 주고, 그 시간이 지나면 강제로 CPU를 빼앗아 다음 프로세스에게 줘. 선점형이야.

n개의 프로세스가 있을 때 어떤 프로세스도 (n-1) × q 이상 기다리지 않아. 응답 시간 보장이 가능해서 대화형 시스템에 적합해.

q 크기가 핵심이야.

• q가 너무 크면: FCFS처럼 동작해. 한 프로세스가 오래 독점하는 효과가 생겨
• q가 너무 작으면: 컨텍스트 스위칭이 너무 자주 일어나서 오버헤드가 커져. CPU 실제 작업보다 전환하는 데 더 많은 시간을 써

 

실무에서 Linux 커널은 CFS(Completely Fair Scheduler)를 써. RR의 발전된 형태인데, 고정된 Time Quantum 대신 각 프로세스가 CPU를 사용한 시간을 추적해서 가장 적게 쓴 프로세스에 우선권을 줘. 더 공정하게 분배하는 방식이야.

 

 

4. Priority Scheduling — 우선순위 높은 놈 먼저

각 프로세스에 우선순위를 부여하고 높은 순서대로 CPU를 줘. SJF도 CPU burst time이 우선순위인 Priority Scheduling의 일종이야. 비선점형 + 선점형 둘 다 있어.

우선순위는 내부/외부 요인으로 결정돼.

• 내부: 제한 시간, 메모리 사용량, I/O vs CPU 비율 등
• 외부: 프로세스 중요도, 사용자 등급, 정책 등

문제 — 기아(Starvation)

높은 우선순위 프로세스가 계속 들어오면 낮은 우선순위 프로세스는 영원히 CPU를 못 받아. 이게 기아 현상이야.

해결 — 에이징(Aging)

오래 대기한 프로세스의 우선순위를 점진적으로 올려줘. 기다릴수록 우선순위가 올라가니까 결국엔 CPU를 받게 돼.

 

5. 다단계 큐 (Multilevel Queue) — 큐를 여러 개로 나눠

우선순위 스케줄링 + Round Robin을 결합한 방식이야. 선점형.

Ready Queue를 여러 개로 분할해. 각 큐는 독립적인 스케줄링 알고리즘을 가져.

Highest priority
│  System processes      → 실시간 응답 필요
│  Interactive processes → RR (응답 시간 짧게)
│  Interactive editing   → RR
│  Batch processes       → FCFS (응답 시간 덜 중요)
▼  Student processes     → FCFS
Lowest priority

보통 CPU 시간의 80%는 Foreground(상위 큐), 20%는 Background(하위 큐)에 할당해.

핵심 제약: 프로세스가 한 번 큐에 배정되면 큐 간 이동이 불가해. 이게 문제야 — 하위 큐는 기아 현상이 생길 수 있어.

 

6. 다단계 피드백 큐 (Multilevel Feedback Queue) — 큐 간 이동 가능

다단계 큐의 단점을 보완한 버전이야. 큐 간 이동이 가능해. 선점형.

큐 0 (q 짧음, 높은 우선순위)
  → Time Quantum 다 쓰면 → 큐 1로 강등
큐 1 (중간)
  → Time Quantum 다 쓰면 → 큐 2로 강등
큐 2 (q 김, 낮은 우선순위)
  → CPU를 오래 쓰는 프로세스들이 모임

Time Quantum을 다 못 쓰고 끝난 프로세스(짧은 작업 or I/O bound)는 원래 큐에 남아. Time Quantum을 다 쓴 프로세스(긴 작업 or CPU bound)는 아래 큐로 내려가.

장점이 여러 개야.

• 짧은 작업이 빠르게 처리돼
• I/O bound 작업에 우선권을 줘
• Aging으로 Starvation 해결 가능
• 현대 OS에서 가장 일반적으로 쓰이는 알고리즘이야

 

가장 유연한 만큼 가장 복잡하기도 해. 큐 개수, 각 큐의 Time Quantum, 언제 올리고 언제 내릴지 등 설정해야 할 매개변수가 많거든. 이걸 잘 튜닝하는 게 핵심이야.

 

 

7. HRN (Highest Response-ratio Next) — SJF의 기아 문제 보완

SJF의 기아 현상을 보완하기 위해 나왔어. 우선순위를 수식으로 계산해. 비선점형.

우선순위 = (대기시간 + 실행시간) / 실행시간

 

SJF는 burst time만 보는데, HRN은 대기시간도 분자에 포함시켜. 오래 기다릴수록 우선순위가 올라가서 기아 현상이 자연스럽게 해결돼.

---

알고리즘 비교 요약

알고리즘	선점 여부	평균 대기 시간	특징	문제점
FCFS	비선점	길 수 있음	구현 단순	Convoy Effect
SJF	비선점	최적	이론적 최소 대기	burst time 예측 어려움
SRTF	선점	최적	SJF 선점 버전	컨텍스트 스위칭 많음
Round Robin	선점	보통	응답 시간 보장	q 크기 튜닝 필요
Priority	비선점/선점	우선순위 의존	유연한 정책	Starvation
Multilevel Queue	선점	보통	성격별 분리 관리	큐 간 이동 불가
Multilevel Feedback Queue	선점	좋음	현대 OS 표준	설정 복잡
HRN	비선점	SJF 개선	Starvation 해결	burst time 예측 필요

 

아래의 질문으로 추가적으로 공부해보자!

Q1. CPU 스케줄링이 왜 필요한가? 멀티프로그래밍 환경에서 CPU 이용률을 극대화하기 위해. CPU core 하나에 여러 프로세스가 경쟁하는 상황에서 어떤 프로세스에 CPU를 줄지 결정해야 해.

Q2. 선점형과 비선점형 스케줄링의 차이는? 선점형은 더 높은 우선순위 프로세스가 들어오면 실행 중인 프로세스에서 강제로 CPU를 빼앗아. 비선점형은 프로세스가 자발적으로 CPU를 놓을 때까지 기다려.

Q3. Round Robin에서 Time Quantum 크기가 왜 중요해? 너무 크면 FCFS처럼 동작해 응답 시간이 길어지고, 너무 작으면 컨텍스트 스위칭 오버헤드가 커져서 실제 작업보다 전환하는 데 더 많은 시간을 쓰게 돼.

Q4. Starvation이란? 어떻게 해결해? 낮은 우선순위 프로세스가 높은 우선순위 프로세스들에게 계속 밀려 CPU를 받지 못하는 현상이야. Aging으로 해결해 — 오래 기다린 프로세스의 우선순위를 점점 높여줘.

Q5. Multilevel Feedback Queue가 현대 OS에서 많이 쓰이는 이유는? 다양한 성격의 프로세스를 유연하게 처리할 수 있어. 짧은 작업은 빠르게 처리되고, CPU 집약적 작업은 아래 큐로 내려가 방해 없이 실행돼. Aging으로 Starvation도 해결 가능하고, 매개변수 조정으로 시스템에 맞게 튜닝할 수 있어.

Q6. 선점형 SJF(SRTF)에서 새 프로세스가 왔을 때 어떻게 CPU를 넘기나?

새 프로세스 생성은 시스템 콜로 이루어져. 시스템 콜이 완료되면 OS 커널이 스케줄러를 호출해서 Ready Queue 전체를 확인해. 현재 실행 중인 프로세스의 남은 시간과 새 프로세스의 burst time을 비교해서 새 프로세스가 더 짧으면 인터럽트를 걸어 컨텍스트 스위칭을 수행하는 거야.

Q7. 다단계 큐에서 CPU time을 비율로 할당한다는 게 무슨 뜻이야?

전체 CPU 시간 중 Foreground 큐에 80%, Background 큐에 20%를 배분한다는 뜻이야. Time Slice 방식으로 구현하는데, 예를 들어 10ms를 주기로 봤을 때 Foreground가 8ms, Background가 2ms를 쓰는 방식이야. 어느 큐에 배분된 시간인지를 비율로 제어하는 거야.

Q8. 별개의 큐를 두는 게 왜 부하 분산(Load Sharing)이랑 관련 있어?

큐가 하나면 모든 프로세스가 같은 줄에 서야 해. 큐를 여러 개로 나누면 성격이 다른 프로세스들이 독립적인 큐에서 관리돼. 한 큐가 과부하 상태여도 다른 큐의 프로세스들은 정상적으로 처리될 수 있어. 이게 부하를 여러 큐로 분산시키는 효과야.

---

오늘 유독 좀 어려운 파트긴했는데 정처기나 adsp, 리눅스 마스터 등 여러 자격증에도 나오는 내용이니깐 꼭 이해하고 넘어가기! 

오늘 공부는 여기서 끝!