이번 글은 OSTEP 7장 CPU Scheduling을 공부하며 정리한 내용입니다. 앞 장에서 제한적 직접 실행으로 운영체제가 CPU 제어권을 회수하는 메커니즘을 봤다면, 이번 장은 그 위에서 어떤 프로세스를 먼저 실행할지 정하는 정책을 다룹니다.
한 문장 요약
CPU 스케줄링은 준비된 작업 중 무엇을 언제 실행할지 정하는 정책이며, FIFO, SJF, STCF, RR은 반환 시간, 응답 시간, 공정성 사이의 기본 절충을 보여 줍니다.
핵심 질문
| 질문 | 핵심 답변 |
|---|---|
| 스케줄링 정책은 어떻게 개발하는가? | 먼저 워크로드에 대한 가정을 세우고, 어떤 지표로 정책을 평가할지 정합니다. 그런 다음 가정을 하나씩 완화하면서 더 현실적인 정책을 만듭니다. |
| 어떤 평가 기준이 중요한가? | 일괄 처리 관점에서는 반환 시간(turnaround time)이 중요하고, 대화형 시스템에서는 응답 시간(response time)이 중요합니다. 공정성도 중요하지만 성능 지표와 충돌할 수 있습니다. |
| FIFO는 언제 문제가 되는가? | 긴 작업이 먼저 도착하면 뒤의 짧은 작업들이 오래 기다리는 convoy effect가 생깁니다. |
| SJF는 왜 반환 시간에 유리한가? | 모든 작업이 동시에 도착하고 실행 시간을 알고 있다면 짧은 작업부터 끝내는 것이 평균 반환 시간을 최소화합니다. |
| STCF는 SJF를 어떻게 개선하는가? | 새 작업이 도착할 때마다 남은 실행 시간이 가장 짧은 작업을 선택합니다. 선점이 가능하므로 늦게 도착한 짧은 작업이 긴 작업을 중단시키고 먼저 실행될 수 있습니다. |
| RR은 어떤 문제를 해결하는가? | 각 작업을 일정 시간 조각만큼 번갈아 실행해 응답 시간을 줄입니다. 대신 문맥 교환 비용이 늘고 반환 시간은 나빠질 수 있습니다. |
| I/O를 고려하면 스케줄러는 어떻게 달라져야 하는가? | I/O를 요청한 작업은 CPU를 쓰지 못하므로 대기 상태로 보내고 다른 작업을 실행해야 합니다. CPU burst를 짧은 작업처럼 다루면 CPU와 I/O를 중첩시켜 자원 이용률을 높일 수 있습니다. |
워크로드 가정
책은 단순한 모델에서 시작해 가정을 하나씩 완화합니다. 좋은 스케줄러를 만들려면 어떤 환경을 대상으로 하는지 먼저 명확히 해야 합니다.
| 초기 가정 | 왜 비현실적인가 |
|---|---|
| 모든 작업은 같은 시간 동안 실행된다. | 실제 작업의 실행 시간은 다양합니다. |
| 모든 작업은 동시에 도착한다. | 실제 시스템에서는 작업이 계속 새로 도착합니다. |
| 작업은 시작되면 끝날 때까지 실행된다. | 현대 운영체제는 타이머 인터럽트로 선점할 수 있습니다. |
| 모든 작업은 CPU만 사용한다. | 대부분의 프로그램은 I/O를 수행합니다. |
| 각 작업의 실행 시간은 미리 알려져 있다. | 범용 운영체제는 작업이 얼마나 오래 실행될지 알 수 없습니다. |
평가 기준
| 지표 | 식 | 의미 |
|---|---|---|
| 반환 시간 | T_turnaround = T_completion - T_arrival |
작업이 도착해서 끝날 때까지 걸린 전체 시간 |
| 응답 시간 | T_response = T_first_run - T_arrival |
작업이 도착해서 처음 CPU를 받을 때까지 걸린 시간 |
| 공정성 | 정책별 정의 필요 | CPU가 작업들 사이에 얼마나 균등하게 배분되는지 |
반환 시간과 응답 시간은 서로 충돌할 수 있습니다. 짧은 작업을 먼저 몰아서 실행하면 평균 반환 시간은 좋아지지만, 뒤에 밀린 작업의 첫 응답은 늦어질 수 있습니다. 반대로 모두를 조금씩 돌리면 응답은 빠르지만 완료 시점은 늦어질 수 있습니다.
FIFO / FCFS
FIFO(First In First Out)는 먼저 도착한 작업을 먼저 실행합니다. 구현은 단순하지만 작업 길이가 다양해지면 문제가 생깁니다.
| 작업 | 도착 | 실행 시간 | 완료 | 반환 시간 |
|---|---|---|---|---|
| A | 0 | 100 | 100 | 100 |
| B | 0 | 10 | 110 | 110 |
| C | 0 | 10 | 120 | 120 |
| 평균 | 110 |
긴 작업 A가 먼저 실행되면서 짧은 작업 B, C가 오래 기다립니다. 이 현상을 convoy effect라고 합니다.
SJF
SJF(Shortest Job First)는 실행 시간이 가장 짧은 작업을 먼저 실행합니다. 모든 작업이 동시에 도착하고 실행 시간이 알려져 있다면 평균 반환 시간 기준으로 최적입니다.
| 작업 | 도착 | 실행 시간 | 완료 | 반환 시간 |
|---|---|---|---|---|
| B | 0 | 10 | 10 | 10 |
| C | 0 | 10 | 20 | 20 |
| A | 0 | 100 | 120 | 120 |
| 평균 | 50 |
하지만 SJF는 비선점 정책입니다. 긴 작업 A가 이미 실행 중이라면, 뒤늦게 도착한 짧은 작업 B, C가 있어도 A를 밀어낼 수 없습니다.
STCF / PSJF
STCF(Shortest Time-to-Completion First)는 SJF에 선점을 더한 정책입니다. 새 작업이 도착할 때마다 현재 실행 중인 작업과 새 작업들의 남은 실행 시간을 비교해 가장 짧은 작업을 실행합니다.
| 작업 | 도착 | 실행 시간 | 완료 | 반환 시간 |
|---|---|---|---|---|
| A | 0 | 100 | 120 | 120 |
| B | 10 | 10 | 20 | 10 |
| C | 10 | 10 | 30 | 20 |
| 평균 | 50 |
비선점 SJF였다면 A가 끝날 때까지 B, C가 기다려야 합니다. STCF는 타이머 인터럽트와 문맥 교환을 활용해 긴 작업을 중단하고 짧은 작업을 먼저 끝냅니다.
RR
RR(Round Robin)은 각 작업을 타임 슬라이스만큼 실행하고 다음 작업으로 넘깁니다. 핵심 목표는 완료 시점보다 첫 응답 시간을 줄이는 것입니다.
| 정책 | 장점 | 단점 |
|---|---|---|
| SJF/STCF | 평균 반환 시간에 유리 | 응답 시간이 나쁠 수 있고 작업 길이를 알아야 함 |
| RR | 응답 시간과 공정성에 유리 | 평균 반환 시간이 나빠지고 문맥 교환 비용이 증가 |
타임 슬라이스가 짧을수록 응답 시간은 좋아지지만 문맥 교환이 자주 발생합니다. 타임 슬라이스가 길수록 문맥 교환 비용은 줄지만 응답 시간은 나빠집니다.
문맥 교환 비용 상쇄
문맥 교환 비용이 1ms라고 가정하면 타임 슬라이스 길이에 따라 비용 비율이 크게 달라집니다.
| 타임 슬라이스 | 문맥 교환 비용 비율 |
|---|---|
| 10ms | 약 10% |
| 100ms | 약 1% |
문맥 교환 비용은 단순한 레지스터 저장/복원만이 아닙니다. 캐시, TLB, 분기 예측 상태도 영향을 받기 때문에 너무 잦은 전환은 실제 성능을 떨어뜨립니다.
I/O와 중첩
I/O를 요청한 작업은 CPU를 사용하지 못합니다. 이때 스케줄러가 다른 작업을 실행하면 CPU와 I/O가 겹쳐 수행되어 전체 자원 이용률이 좋아집니다.
- Job A가 짧은 CPU burst를 실행합니다.
- A가 디스크 I/O를 요청하고 대기 상태로 이동합니다.
- A가 기다리는 동안 스케줄러는 Job B를 CPU에서 실행합니다.
- 디스크 I/O가 끝나면 인터럽트가 발생하고 A는 다시 준비 상태가 됩니다.
- 스케줄러는 다음 CPU burst에서 A를 다시 실행할 수 있습니다.
I/O 중심 작업은 짧은 CPU burst를 반복하는 경우가 많습니다. STCF 관점에서는 이 burst들을 짧은 독립 작업처럼 다루면, 대화형 작업을 자주 실행하면서도 CPU를 놀리지 않을 수 있습니다.
간단한 스케줄러 시뮬레이터
FIFO, SJF, STCF, RR의 차이는 작은 시뮬레이터로 직접 확인할 수 있습니다.
|
1 2 3 4 |
python3 code/ostep/cpu-scheduling/scheduler.py --policy fifo --jobs A:0:100,B:0:10,C:0:10 python3 code/ostep/cpu-scheduling/scheduler.py --policy sjf --jobs A:0:100,B:0:10,C:0:10 python3 code/ostep/cpu-scheduling/scheduler.py --policy stcf --jobs A:0:100,B:10:10,C:10:10 python3 code/ostep/cpu-scheduling/scheduler.py --policy rr --quantum 1 --jobs A:0:5,B:0:5,C:0:5 |
정리
이 장은 CPU 스케줄링 정책을 평가하는 기본 언어를 제공합니다. FIFO는 단순하지만 convoy effect에 취약하고, SJF는 작업 시간이 알려져 있고 동시에 도착한다면 반환 시간에 최적입니다. STCF는 선점을 통해 늦게 도착한 짧은 작업도 먼저 처리할 수 있어 반환 시간을 더 개선합니다. RR은 응답 시간과 공정성을 개선하지만 반환 시간과 문맥 교환 비용 측면에서 손해를 봅니다.
마지막으로 I/O를 고려하면 스케줄러는 CPU burst와 I/O 대기를 중첩해야 합니다. 하지만 범용 운영체제는 작업의 미래 실행 시간을 알 수 없으므로, 다음 장의 MLFQ처럼 과거 동작을 바탕으로 미래를 추정하는 정책이 필요합니다.
