CPU 스케줄링: 비선점

CPU 스케줄링(CPU scheduling)은 준비 상태에서 기다리는 프로세스 가운데 다음에 CPU를 줄 하나를 고르는 일입니다. 비선점(non-preemptive) 스케줄링은 한번 CPU를 받은 프로세스가 끝날 때까지 빼앗지 않는 방식이고, 고르는 규칙에 따라 같은 프로세스들의 기다리는 시간이 크게 달라집니다.

프로세스와 스레드에서 본 디스패치가 바로 이 고르기입니다. 시험은 규칙을 주고 평균 대기 시간을 계산하게 합니다. 아래 그림은 프로세스 넷을 같은 묶음으로 두고 고르는 규칙만 바꿔 가며 간트 차트(Gantt chart)를 깔고, 기다린 칸을 셉니다.

1대기 시간과 반환 시간 — FCFS

그림의 프로세스 넷입니다. 우선순위는 숫자가 작을수록 높습니다.

규칙을 견주는 잣대는 둘입니다.

• 반환 시간(turnaround time) = 끝난 시각 − 도착 시각. 도착해서 끝날 때까지 걸린 시간입니다.
• 대기 시간(waiting time) = 반환 시간 − 실행 시간. 준비 상태에서 CPU를 기다린 시간이고, 비선점에서는 시작 시각 − 도착 시각과 같습니다.

FCFS(First Come First Served)는 먼저 온 순서대로 줍니다. 자료에 따라 FIFO(First In First Out)라고도 부릅니다. 단순하고 공평하지만, 긴 프로세스가 앞에 서면 짧은 프로세스가 모두 그 뒤에서 기다립니다.

2짧은 것부터 — SJF

SJF(Shortest Job First)는 기다리는 프로세스 가운데 실행 시간이 가장 짧은 것을 고릅니다. 짧은 것이 먼저 빠져나가면 뒤에서 기다리는 수가 줄어, 같은 때 도착한 묶음이라면 평균 대기 시간이 가장 짧은 방식입니다.

고를 때는 그 시각까지 도착한 프로세스만 봅니다. 시각 3에 P4는 아직 오지 않아 P2와 P3만 견줍니다.

대가는 긴 프로세스가 치릅니다. 짧은 프로세스가 계속 들어오면 긴 프로세스는 끝없이 뒤로 밀릴 수 있습니다. 이렇게 차례가 끝없이 밀리는 것을 기아 상태(starvation)라고 합니다.

3기다린 만큼 올려 준다 — HRN과 우선순위

HRN(Highest Response-ratio Next)은 SJF의 기아 상태를 줄이려고 기다린 시간을 셈에 넣습니다. 우선순위 = (대기 시간 + 실행 시간) ÷ 실행 시간이고, 이 값이 가장 큰 프로세스를 고릅니다. 1절 표의 우선순위는 작을수록 높았지만, HRN의 값은 클수록 먼저입니다. 시험에서는 실행 시간을 서비스 시간이라고도 씁니다. 실행 시간이 짧을수록, 오래 기다릴수록 값이 커져 긴 프로세스도 기다리다 보면 차례가 옵니다.

우선순위(priority) 스케줄링은 미리 매긴 우선순위로 고릅니다. 낮은 우선순위는 기아 상태에 빠질 수 있어, 기다린 시간만큼 우선순위를 조금씩 올려 주는 에이징(aging)으로 막습니다. 비선점이라 우선순위가 가장 낮은 P1도 먼저 잡은 CPU는 끝까지 씁니다.

예제

그림의 HRN을 표로 따라갑니다. CPU가 빌 때마다 기다리는 프로세스의 값을 셉니다.

끝난 시각에서 반환 시간과 대기 시간을 셉니다.

평균 반환 시간은 28 ÷ 4 = 7, 평균 대기 시간은 14 ÷ 4 = 3.5입니다. 네 규칙을 견주면 다음과 같습니다.

시험 포인트

• 필기: 비선점은 한번 받은 CPU를 끝날 때까지 쥡니다. FCFS는 도착순, SJF는 실행 시간이 짧은 순으로 고릅니다. 같은 때 도착하면 SJF가 평균 대기 시간이 가장 짧은 대신, 긴 프로세스가 기아 상태에 빠질 수 있습니다. HRN은 (대기 시간 + 실행 시간) ÷ 실행 시간이 큰 순으로 골라 기아 상태를 줄입니다. 우선순위 방식의 기아 상태는 에이징으로 막습니다. 반환 시간 = 끝난 시각 − 도착 시각, 대기 시간 = 반환 시간 − 실행 시간입니다.
• 실기: 평균 대기 시간·평균 반환 시간을 계산해 문제가 정한 꼴(소수 자리)대로 씁니다. 이름은 FCFS(First Come First Served)·SJF(Shortest Job First)·HRN(Highest Response-ratio Next)·에이징(Aging)입니다.

확인 문제

1. HRN 스케줄링에서 CPU가 비었을 때 네 프로세스가 기다리고 있습니다. 다음에 CPU를 받는 프로세스를 고르세요.

• ① 가
• ② 나
• ③ 다
• ④ 라

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

• (가) 은행 창구처럼 번호표를 뽑은 차례대로 CPU를 줍니다.
• (나) 끝내는 데 드는 시간이 가장 적은 것부터 줍니다. 평균 대기는 가장 짧지만, 덩치 큰 작업은 하염없이 밀릴 수 있습니다.
• (다) 기다린 시간과 일의 크기를 함께 따져, 오래 기다린 큰 작업도 언젠가 앞으로 나오게 합니다.
• (라) 줄에 오래 서 있던 프로세스일수록 우선순위를 조금씩 올려 줍니다.

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

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