운영체제 CPU 스케줄링 정리
1. CPU 스케줄링이란?
운영체제가 프로세스들에게 CPU 자원을 공정하고 합리적으로 배분하는 과정.
효율적인 스케줄링이 이루어지지 않으면 CPU와 I/O 자원이 균형 있게 사용되지 못해 전체 시스템 성능이 저하될 수 있음.
프로세스는 크게 두 종류로 나뉜다.
| 종류 | 설명 |
|---|---|
| CPU 집중(CPU-bound) | CPU 연산 시간이 길고 CPU 사용량이 큰 프로세스 |
| I/O 집중(I/O-bound) | I/O 작업이 많고 CPU 사용 시간은 짧은 프로세스 |
운영체제는 I/O 집중 프로세스를 먼저 처리하여 I/O 장치를 꾸준히 동작시키고, 그동안 CPU는 다른 작업을 진행할 수 있게 만들어 전체 시스템 효율을 높인다.
2. PCB와 스케줄링 큐
프로세스들의 정보는 PCB(Process Control Block)에 저장되며 우선순위(priority) 역시 여기 포함된다.
하지만 OS가 필요한 순간마다 PCB를 뒤져서 우선순위를 직접 비교하는 것은 비효율적이므로,
운영체제는 아래 두 가지 주요 스케줄링 큐를 사용한다.
| 큐 종류 | 설명 |
|---|---|
| 준비 큐(Ready Queue) | CPU 사용을 기다리는 프로세스들이 줄 서 있는 곳 |
| 대기 큐(Wait Queue) | I/O 작업이 완료되기를 기다리는 프로세스들의 큐 |
운영체제는 대기 큐에서 I/O가 끝난 프로세스를 찾아 다시 준비 큐로 이동시킨다.
3. 선점형 vs 비선점형 스케줄링
| 구분 | 설명 |
|---|---|
| 선점형(Preemptive) | 실행 중인 프로세스에서 CPU를 강제로 빼앗아 더 급한 프로세스에게 배분 |
| 장점 | 급한 작업을 빠르게 처리 가능, CPU 독점 방지 |
| 단점 | 문맥 교환(Context Switch)의 오버헤드 증가 |
| 비선점형(Non-preemptive) | 실행 중인 프로세스가 스스로 CPU를 반납할 때까지 기다림 |
| 장점 | 문맥 교환 오버헤드 적음 |
| 단점 | 급한 작업이 기다려야 하는 상황 발생 |
4. 주요 CPU 스케줄링 알고리즘
4-1. 선입 선처리(FCFS, First Come First Served)
-
먼저 온 프로세스를 먼저 처리.
-
비선점형.
-
단순하지만 호위 효과(convoy effect) 발생:
- CPU 집중 프로세스 하나 때문에 뒤의 모든 I/O 집중 프로세스가 오래 기다리는 문제.
4-2. 최단 작업 우선(SJF, Shortest Job First)
- 실행 시간이 가장 짧은 작업을 먼저 수행.
- 평균 대기 시간을 최소화하는 이론적으로 최적 알고리즘.
- 비선점형.
- 하지만 실행 시간을 미리 알기 어렵다는 단점이 있음.
4-3. 최소 잔여 시간 우선(SRTF, Shortest Remaining Time First)
- SJF의 선점형 버전.
- 도착한 프로세스의 남은 시간이 더 짧으면 실행 중인 프로세스를 중단하고 교체한다.
- 대기 시간 최소화 효과가 크지만 문맥 교환 증가.
4-4. 라운드 로빈(Round Robin, RR)
-
타임 슬라이스(quantum)만큼 CPU를 나눠 주는 방식.
-
선점형.
-
시분할 시스템(Time-sharing)에 적합.
-
타임 슬라이스 크기 조절이 핵심:
- 너무 짧으면 문맥 교환 오버헤드 증가
- 너무 길면 FCFS처럼 변함
4-5. 우선순위 스케줄링(Priority Scheduling)
- PCB에 저장된 우선순위를 사용해 높은 우선순위 프로세스부터 실행.
- 선점형 / 비선점형 모두 가능.
문제: 기아(Starvation)
- 계속 우선순위가 낮은 작업은 영원히 CPU를 못 받을 수 있음.
해결책: 에이징(Aging)
- 오래 기다린 프로세스의 우선순위를 조금씩 올려주는 방식.
4-6. 다단계 큐 스케줄링(Multilevel Queue)
- 프로세스를 성격별로 큐를 나누어 관리
(예: 시스템 프로세스, 대화형 프로세스, 배치 작업) - 큐마다 다른 스케줄링 알고리즘 사용 가능.
- 큐 간 우선순위 존재 → 하위 큐는 CPU를 잘 못 받을 수 있음.
4-7. 다단계 피드백 큐 스케줄링(MLFQ, Multilevel Feedback Queue)
가장 일반적이며 현대 운영체제가 실제로 사용함.
특징
- 프로세스는 처음에는 높은 우선순위 큐에 배치됨
- 오래 사용할수록 점점 낮은 우선순위 큐로 이동(Feedback)
- 짧은 작업(I/O-bound)은 상단 큐에서 빨리 끝남
- 긴 작업(CPU-bound)은 아래 큐로 내려간다
장점
- CPU-bound / I/O-bound 프로세스 모두 효율적으로 처리
- 실제 환경에서 매우 높은 성능
단점
-
파라미터 설정이 매우 복잡
- 큐 개수
- 각 큐의 타임 슬라이스
- 큐 간 이동 규칙
-
운영체제마다 구현 방식이 다르며 최적값 찾기 어려움
스케줄링 알고리즘 비교표
| 알고리즘 | 선점 여부 | 특징 | 장점 | 단점 |
|---|---|---|---|---|
| FCFS | X | 먼저 온 순서대로 처리 | 단순 | 호위 효과 발생 |
| SJF | X | 가장 짧은 작업 우선 | 평균 대기시간 최소 | 실행 시간 예측 어려움 |
| SRTF | O | 남은 시간 기준 | 매우 효율적 | 문맥 교환 많음 |
| RR | O | 타임 슬라이스 기반 | 시분할에 적합 | 슬라이스 조절 어려움 |
| Priority | O/X | 우선순위 기반 | 중요도 반영 | 기아 문제 |
| Multilevel Queue | O/X | 큐 종류별 분리 | 성격별 관리 | 하위 큐 기아 |
| MLFQ | O | 동적 우선순위 | 실제 OS들이 사용 | 파라미터 설정 복잡 |
