CPU 스케줄링의 기본 모델은 CPU 총량을 늘리는 것이 아니라 runnable 작업 사이에 실행 순서와 시간 예산을 배분하는 것입니다. 응답 시간·대기 시간·반환 시간·최대 대기는 서로 다른 지표이므로, 정책을 고를 때는 작업 도착열과 선점 가능성, 추정 오차, 전환 비용을 같은 모형에서 계산해야 합니다.
대기 시간 지표와 최적화 대상
A는 10ms, B와 C는 각각 1ms의 CPU 작업이고 모두 시각 0에 도착했다고 합시다. 전환 비용을 무시하면 FCFS의 A,B,C 순서는 완료 시각 10,11,12ms입니다. SJF로 B,C,A를 처리하면 1,2,12ms입니다. 전체 끝나는 시각은 같아도 짧은 작업과 평균 대기는 다릅니다.
CPU 스케줄링은 총 작업량을 없애는 것이 아니라 누가 먼저 얼마나 실행할지 정합니다. 앞의 예에서 FCFS의 B는 A가 끝나는 10ms까지 시작하지 못하고 11ms에 끝나지만, SJF의 B는 시각 0에 시작해 1ms에 끝납니다. 따라서 첫 실행까지의 응답 시간, 완료까지의 반환 시간, CPU를 제외한 대기, 가장 오래 기다린 작업을 같은 숫자로 묶지 않고 따로 기록해야 합니다.
기본 계산은 각 작업의 도착 시각, 첫 실행 시각, 완료 시각을 표로 만드는 데서 시작합니다. 응답 시간은 첫 실행까지, 반환 시간은 도착부터 완료까지, 대기 시간은 실행하지 않고 준비 큐에 있던 시간으로 분리하면 FCFS가 짧은 작업에 주는 손해와 RR quantum의 효과를 같은 용어로 섞지 않게 됩니다.
| 정책 | 선택 기준 | 대가 |
|---|---|---|
| FCFS | 도착 순서 | 앞의 긴 작업에 뒤가 묶임 |
| 비선점 SJF | 준비된 작업 중 예상 실행이 짧은 것 | 길이 예측·긴 작업 기아 |
| Round Robin | 각 작업에 최대 quantum씩 순환 | 전환 비용·한 바퀴 대기 |
| SRTF | 남은 시간이 짧은 작업으로 선점 | 예측·선점 비용 |
실행 중 작업의 선점 여부
비선점 SJF에서 A가 먼저 실행된 뒤 B가 도착하면 B가 더 짧아도 A를 끝까지 기다립니다. 현재 A를 중단해 B를 먼저 실행하려면 SRTF 등 선점형 규칙이 필요합니다. “짧은 작업 우선”만으로 도착 시점과 선점 여부를 생략하지 않습니다.
그림을 글로 읽기
- A 실행 중 · B 도착
- 비선점 SJF: A가 끝난 뒤 다시 선택
- Round Robin: quantum 끝에 차례 교체
- A 실행 중 · B 도착 → 비선점 SJF: 실행 중 작업 유지
- A 실행 중 · B 도착 → Round Robin: 시간 예산 적용
Quantum 크기와 문맥 전환 비용
같은 우선순위의 CPU 작업 4개가 항상 runnable이고 quantum이 5ms라면, 한 작업의 차례가 끝난 뒤 다시 실행되기까지 다른 작업의 CPU 시간 약 15ms와 전환 비용을 기다립니다. 400개면 약 1,995ms가 됩니다. 이는 단일 CPU·고정 작업 집합의 모형이지 실제 p99의 절대 보장이 아닙니다.
전환 비용을 s라고 하면 한 바퀴의 대기는 대략 다른 N-1개의 quantum과 관련 전환 비용을 포함합니다. q가 너무 작으면 유용한 계산 대비 전환 비중이 커집니다. q가 매우 크면 FCFS와 비슷해져 짧은 요청이 기다립니다. I/O 작업은 q를 다 쓰기 전에 잠들 수 있고, 실제 OS는 우선순위·그룹·affinity를 함께 적용하므로 교과서 q 하나로 모든 지연을 설명하지 않습니다.
실행 시간 추정과 관측 보정
미래 실행 시간을 정확히 알 수 없으므로 작업 종류·입력 크기별 과거 CPU 시간을 사용해 예측할 수 있습니다. 지수 이동 평균 estimate ← α·actual + (1-α)·estimate는 최근 정보를 반영하지만 갑작스러운 변화와 이상치에 대한 선택이 남습니다.
onCompleted(job, actualCpuTime):
bucket = classify_by_trusted_type_and_size(job)
estimate[bucket] = alpha*actualCpuTime + (1-alpha)*estimate[bucket]
record_prediction_error(job, actualCpuTime)
사용자가 신고한 낮은 비용을 무조건 믿으면 무거운 작업이 항상 앞에 갈 수 있습니다. 실제 사용량 한도·분할·양보 지점을 함께 두어 예측이 틀려도 자원을 독점하지 않게 합니다. CPU 시간과 DB 연결 보유 시간은 다른 비용이므로 하나의 숫자로 억지 합치지 않습니다.
Aging과 완료 기한 보장 범위
오래 기다린 작업의 우선순위를 올리면 기아를 완화할 수 있습니다. 하지만 절대 넘을 수 없는 높은 클래스가 계속 들어오거나, 실행 중인 비선점 작업이 무한히 길면 여전히 기다릴 수 있습니다. 최대 작업량·수락 제한·최소 실행 몫과 함께 설계해야 개별 대기 상한을 논할 수 있습니다.
이미 기한이 지나 쓸모없는 작업을 오래 기다렸다는 이유로 우선 실행하면 유효 요청의 자원을 낭비할 수 있습니다. 완료·만료·거절 정책도 필요합니다. 긴 작업에 예약 용량을 주면 짧은 요청 SLO가 달라질 수 있으므로 둘을 함께 측정합니다.
앱 배치 예산과 OS quantum의 차이
이벤트 루프가 콜백 100개를 한 번에 처리할 때 OS가 스레드를 공정하게 선점해도 그 루프 내부의 뒤 요청은 계속 기다립니다. 개수와 시간 중 먼저 닿는 상한을 두고 나머지는 소유권을 유지한 큐로 넘깁니다. 이미 꺼낸 항목을 그냥 버리거나 원래 큐에 자동 남았다고 가정하지 않습니다.
콜백 하나가 매우 길면 배치 개수 제한만으로 부족합니다. 작업을 작은 단계로 나누거나 격리된 실행기를 사용해야 합니다. 낮은 전환 횟수가 곧 좋은 응답성을 뜻하지 않습니다.
동일 도착열과 정책 결과 대조
모두 준비된 경우, 긴 작업 실행 중 짧은 작업 도착, 짧은 작업 지속 유입, I/O 양보 혼합을 나누어 재생합니다. 첫 응답·완료·최대 대기·전환·CPU·만료율을 기록합니다. 실제 OS 정책은 버전과 설정을 확인하고, 사용자 공간 모형의 결과를 커널 스케줄러의 실행 보장으로 보고하지 않습니다.
재현 연습은 동일 도착열, 긴 작업 실행 중 짧은 작업 도착, 지속적인 짧은 작업 유입, quantum보다 짧게 양보하는 I/O 작업을 각각 재생하는 것입니다. 예상 결과는 비선점 SJF에서 실행 중 A가 중단되지 않고, RR에서는 quantum 경계마다 차례가 바뀌며, quantum을 줄이면 전환 수와 비용이 늘 수 있다는 것입니다. 실제 커널 정책의 보장은 이 모형의 숫자가 아니라 실행 환경에서 별도로 측정해야 합니다.