CPU 스케줄링: 선점

선점(preemptive) 스케줄링은 실행 중인 프로세스에게서 CPU를 빼앗아 다른 프로세스에 줄 수 있는 방식입니다. 비선점에서는 긴 프로세스가 CPU를 잡으면 급하거나 짧은 프로세스도 끝날 때까지 기다려야 해서, 여러 사람이 함께 쓰는 시스템의 응답이 느려집니다.

CPU 스케줄링: 비선점의 네 규칙은 한번 준 CPU를 거두지 않았습니다. 선점 규칙은 시간이 다 되거나 더 급한 프로세스가 오면 돌던 프로세스를 끊습니다. 아래 그림은 앞 레슨과 같은 프로세스 넷을 선점 규칙 셋으로 다시 깔고, 막대가 잘리고 끼어드는 자리를 짚습니다.

1라운드 로빈 — 할당량만큼 돌아가며

프로세스 넷은 앞 레슨과 같습니다.

라운드 로빈(RR, Round Robin)은 정해진 시간 할당량(time quantum)만큼만 CPU를 주고, 그 안에 끝내지 못하면 준비 줄 맨 뒤로 보냅니다. 자료에 따라 할당량을 타임 슬라이스(time slice)라고도 부릅니다. 그림의 할당량은 3입니다.

할당량이 끝나는 시각에 새 프로세스가 도착하면 문제가 정한 차례를 따릅니다. 정하지 않았으면 새로 온 프로세스를 먼저 줄에 세우고, 잘린 프로세스를 그 뒤에 세우는 풀이가 흔합니다.

선점에서는 한 프로세스가 여러 토막으로 돌아, 대기 시간을 시작 시각으로 셀 수 없습니다. 반환 시간 − 실행 시간으로 셉니다. 모두가 자주 차례를 받아 응답은 빠르지만, 평균 대기는 오히려 길 수 있습니다.

할당량이 아주 크면 아무도 잘리지 않아 FCFS와 같아집니다. 아주 작으면 CPU를 넘기는 문맥 교환이 잦아져 그만큼 시간을 버립니다.

2SRT — 남은 시간이 가장 짧은 것

SRT(Shortest Remaining Time)는 남은 실행 시간이 가장 짧은 프로세스에 CPU를 줍니다. SJF를 선점으로 바꾼 것이라, 새 프로세스가 올 때마다 돌던 프로세스의 남은 시간과 견줍니다.

견주는 것은 처음 실행 시간이 아니라 남은 시간입니다. 시각 4에 P3의 실행 시간은 4였지만 1만큼 돌아 남은 시간이 3이고, 도착한 P4의 2가 더 짧아 CPU를 빼앗습니다.

그림에서도 평균 대기가 가장 짧지만, SJF처럼 긴 프로세스가 기아 상태에 빠질 수 있습니다.

3다단계 큐와 다단계 피드백 큐

다단계 큐(MLQ, Multi-Level Queue)는 준비 줄을 성격에 따라 여러 큐로 나누고, 큐마다 따로 규칙을 둡니다. 위 큐가 비어야 아래 큐가 돌고, 위 큐 프로세스가 오면 아래 큐 프로세스는 끊깁니다. 그림은 우선순위 1·2를 위 큐(라운드 로빈), 3·4를 아래 큐(FCFS)로 나눴습니다.

다단계 피드백 큐(MLFQ, Multi-Level Feedback Queue)는 프로세스가 큐 사이를 옮겨 다닐 수 있게 한 것입니다.

시험은 규칙을 선점과 비선점으로 나누게 합니다. 우선순위 방식은 두 가지가 다 있고, 기한부(deadline)는 프로세스마다 끝낼 기한을 주고 그 안에 마치게 하는 비선점 방식입니다.

예제

그림의 SRT를 표로 따라갑니다. 프로세스가 도착하거나 끝날 때마다 남은 시간을 견줍니다.

끝난 시각은 P1 3 · P4 6 · P3 9 · P2 14입니다. 대기 시간은 반환 시간 − 실행 시간으로 P1 3 − 3 = 0, P2 13 − 5 = 8, P3 7 − 4 = 3, P4 2 − 2 = 0이고, 평균은 11 ÷ 4 = 2.75입니다. 일곱 규칙을 견주면 다음과 같습니다.

시험 포인트

• 필기: 선점은 돌던 프로세스의 CPU를 빼앗을 수 있습니다. RR은 할당량만큼 돌리고 줄 뒤로 보내며, 할당량이 크면 FCFS와 같아지고 작으면 문맥 교환이 잦아집니다. SRT는 남은 시간이 가장 짧은 것을 고르는 SJF의 선점판입니다. 다단계 큐는 큐 사이를 옮기지 못하고, 다단계 피드백 큐는 옮겨 다닙니다. 비선점은 FCFS·SJF·HRN·우선순위·기한부, 선점은 RR·SRT·선점 우선순위·다단계 큐·다단계 피드백 큐입니다. 선점에서 대기 시간은 반환 시간 − 실행 시간으로 셉니다.
• 실기: 라운드 로빈과 SRT의 평균 대기 시간을 계산해 문제가 정한 꼴대로 씁니다. 이름은 라운드 로빈(RR, Round Robin)·SRT(Shortest Remaining Time)·다단계 큐(MLQ, Multi-Level Queue)·다단계 피드백 큐(MLFQ, Multi-Level Feedback Queue)입니다.

확인 문제

1. SRT로 스케줄링하고 있습니다. 시각 5에 A가 돌고 있고 남은 시간은 4입니다. 준비 줄의 B는 남은 시간이 6입니다. 이때 실행 시간이 3인 C가 도착했습니다. 시각 5 바로 뒤에 CPU를 쓰는 프로세스를 고르세요.

• ① A
• ② B
• ③ C
• ④ A와 C가 한 단위씩 번갈아

2. 다음 (가)~(라)에 맞는 이름을 쓰세요. (가)·(다)·(라)는 한글 이름과 영문 약어·원어로, (나)는 약어와 영문 원어로 쓰세요. 답을 끝까지 쓴 뒤 정답을 펼치세요.

• (가) 모든 프로세스에 같은 몫의 시간을 주고, 몫을 다 쓰면 줄 맨 뒤로 보내 차례를 돌립니다.
• (나) 끝날 때까지 남은 시간을 견주어, 그보다 더 빨리 끝날 프로세스가 오면 돌던 것을 멈추게 합니다.
• (다) 시스템 작업·대화형 작업·일괄 작업 줄을 따로 두고, 한번 들어간 줄에서 다른 줄로 옮기지 않습니다.
• (라) 처음에는 가장 위 줄에 넣고, 받은 몫을 다 쓸 때마다 한 줄씩 아래로 내립니다.

3. 그림의 프로세스 넷에서 P4의 실행 시간만 2에서 4로 바꿨습니다. SRT로 스케줄링할 때 평균 대기 시간을 소수 첫째 자리까지 쓰세요. 답을 끝까지 쓴 뒤 정답을 펼치세요.

4. 다음 네 프로세스를 라운드 로빈(할당량 2)으로 스케줄링할 때 평균 대기 시간을 소수 둘째 자리까지 쓰세요. 답을 끝까지 쓴 뒤 정답을 펼치세요.