CPU 스케줄링 2

CPU 스케줄링에서 본 선점(preemption)과 평가 기준을 바탕으로, 다음 차례를 고르는 대표 알고리즘을 이어서 다룬다. 짧은 작업을 먼저 돌리면 평균 대기 시간(waiting time)이 줄지만 긴 작업이 영영 밀릴 수 있다. 시간을 잘게 잘라 돌아가며 실행하면 모든 프로세스(process)가 금방 첫 차례를 받는다.

SJF와 SRTF: 짧은 작업 먼저

SJF(Shortest Job First, 최단 작업 우선)는 다음 CPU 버스트(CPU burst)가 가장 짧은 프로세스를 먼저 실행한다. CPU 스케줄링의 FCFS(First-Come First-Served, 선입 선처리) 예에서는 시각 0에 함께 도착한 P1 24ms, P2 3ms, P3 3ms를 P2, P3, P1 순서로 돌렸을 때 평균 대기 시간이 17ms에서 3ms로 줄었다. 이 두 번째 순서가 SJF의 선택이다. 짧은 작업을 앞에 두면 기다리는 프로세스 수가 빨리 줄어든다. 그래서 모든 작업이 동시에 도착했다면 SJF는 평균 대기 시간이 가장 작은 순서를 만든다.

문제는 다음 CPU 버스트 길이를 실행 전에 알 수 없다는 점이다. 실제로는 과거 버스트 길이의 지수 평균(exponential average)¹으로 다음 길이를 추측하는 근사만 할 수 있다. 또 짧은 작업이 계속 들어오면 긴 작업은 한없이 뒤로 밀린다. 이렇게 차례가 영영 오지 않는 상태를 기아(starvation)라고 한다.

SRTF(Shortest Remaining Time First, 최소 잔여 시간 우선)는 SJF의 선점 버전이다. 새 프로세스가 도착했을 때 그 버스트가 실행 중인 프로세스의 남은 시간보다 짧으면 CPU를 빼앗아 넘긴다. 도착 시각이 제각각이어도 짧은 작업을 바로 처리할 수 있지만, 길이를 모른다는 문제와 기아는 그대로다. 또 새 프로세스가 도착할 때마다 실행 중인 작업을 멈출 수 있어 문맥 교환(context switch)이 늘어난다.

우선순위 스케줄링과 에이징

우선순위 스케줄링(priority scheduling)은 프로세스마다 우선순위를 붙이고 가장 높은 것부터 실행한다. 선점 방식으로도 비선점(non-preemptive) 방식으로도 만들 수 있다. 선점 방식이면 더 높은 우선순위 프로세스가 도착하는 즉시 CPU를 빼앗고, 비선점 방식이면 실행 중인 프로세스가 CPU를 내놓을 때까지 기다렸다가 다음 차례로 준다. SJF도 "버스트가 짧을수록 우선순위가 높다"는 규칙을 쓴 우선순위 스케줄링의 한 종류로 볼 수 있다.

이 방식의 대표 문제도 기아다. 높은 우선순위 작업이 끊임없이 들어오면 낮은 작업은 실행되지 못한다. 해결책은 에이징(aging)이다. 준비 큐(ready queue)에서 오래 기다린 프로세스일수록 우선순위를 조금씩 올려 주므로, 아무리 낮게 시작한 작업도 언젠가는 차례가 온다.

라운드 로빈: 시간을 잘라 돌아가며

라운드 로빈(round robin)은 FCFS에 선점을 더한 방식이다. 모든 프로세스가 같은 길이의 타임 슬라이스(time slice)를 받아 돌아가며 실행하고, 시간을 다 쓰면 준비 큐 맨 뒤로 가서 다시 줄을 선다. 같은 예(P1 24ms, P2 3ms, P3 3ms)를 타임 슬라이스 4ms로 돌리면 다음과 같다.

구간(ms)	0~4	4~7	7~10	10~30
실행	P1	P2	P3	P1

P1은 6ms, P2는 4ms, P3는 7ms를 기다려 평균 대기 시간은 약 5.67ms다. SJF의 3ms보다는 길다. 하지만 세 프로세스 모두 7ms 안에 처음 CPU를 받는다. P1부터 시작하는 FCFS였다면 P3는 27ms를 기다려야 첫 실행을 한다. 이렇게 처음 CPU를 받기까지 걸리는 시간을 응답 시간(response time)이라 한다. 응답 시간이 짧기 때문에 라운드 로빈이 대화형 시스템의 기본 뼈대가 됐다.

타임 슬라이스 길이가 성능을 좌우한다.

• 너무 길면 대부분의 작업이 한 번에 끝나 사실상 FCFS와 같아지고, 응답 시간이 나빠진다.
• 너무 짧으면 문맥 교환이 지나치게 잦아진다. 전환할 때마다 레지스터(register)를 저장·복원하고 캐시 메모리(cache memory)를 다시 채우는 비용이 들어, CPU 시간 가운데 실제 일에 쓰는 몫이 줄어든다.

그래서 타임 슬라이스는 문맥 교환 비용보다는 충분히 크게, 대화형 반응이 굼떠지지 않을 만큼은 작게 잡는다.

이어지는 내용은 CPU 스케줄링 3에서 다룬다.

면접 포인트

• "SJF가 최적인데 왜 그대로 안 쓰나요?" → 다음 CPU 버스트 길이를 미리 알 수 없고, 긴 작업이 기아에 빠진다.
• "SJF와 SRTF의 차이는?" → SRTF는 SJF의 선점 버전이다. 새로 온 작업이 실행 중인 작업의 남은 시간보다 짧으면 CPU를 빼앗는다.
• "라운드 로빈의 타임 슬라이스를 줄이면?" → 응답 시간은 좋아지지만 문맥 교환 비용이 커져 처리량(throughput)이 떨어진다. 너무 늘리면 FCFS가 된다.
• "기아는 어떻게 막나요?" → 에이징. 오래 기다린 프로세스의 우선순위를 조금씩 올린다.
• 호위 효과(convoy effect)는 FCFS에서, 기아는 SJF·우선순위 방식에서 나온다. 둘을 섞어 말하지 않는다.

참고

1. 최근 값에 더 큰 가중치를 주는 평균. 예를 들어 "다음 예측 = 0.5 × 직전 실제 길이 + 0.5 × 직전 예측"처럼 계산해, 최근 행동을 더 믿으면서 과거도 조금 반영한다. ↩︎