HRN(Highest Response-ratio Next) 스케줄링

0 / 6

HRN(Highest Response-ratio Next) 스케줄링

앞 프로세스가 끝날 때마다 줄에 선 프로세스의 응답비율을 계산해서 가장 큰 프로세스를 먼저 실행한다. 응답비율은 기다린 시간과 실행 시간을 더한 값을 실행 시간으로 나눈 것이다. 실행 시간이 짧을수록 크고 오래 기다릴수록 커지기 때문에, 긴 프로세스도 결국 차례가 온다. 비선점형이다.

은행으로 치면: 볼일이 짧은 손님을 먼저 부르되, 오래 기다린 손님에게는 그만큼 가산점을 줘서 한 사람만 계속 밀리지 않게 한다.

1 / 6

0ms: P1 실행 시작

줄에 P1밖에 없으니 고를 것도 없이 바로 실행된다. 비선점형이라 P1은 끝까지 실행된다.

2 / 6

1~3ms: P2·P3·P4가 줄을 섬

P2가 1ms에, P3가 2ms에, P4가 3ms에 도착했다. 기다리는 동안 응답비율이 조금씩 커진다.

3 / 6

5ms: 응답비율이 가장 큰 P2 실행

P1이 끝나서 응답비율을 계산한다. P2는 4ms를 기다렸고 실행 시간이 3ms라 (4 + 3) ÷ 3 = 2.33이다. P3는 (3 + 8) ÷ 8 = 1.38, P4는 (2 + 2) ÷ 2 = 2다. 가장 큰 P2가 실행된다. SJF였다면 가장 짧은 P4가 먼저였다.

4 / 6

8ms: P2가 끝나고 P4 실행

다시 계산한다. P3는 (6 + 8) ÷ 8 = 1.75, P4는 (5 + 2) ÷ 2 = 3.5라서 P4가 실행된다. P3는 이번에도 밀렸지만, 기다린 만큼 응답비율이 1.38에서 1.75로 올랐다.

5 / 6

10ms: P4가 끝나고 P3 실행

줄에 P3만 남아 실행된다. 짧은 프로세스가 계속 들어와도 P3는 기다릴수록 응답비율이 커지니, 언젠가는 가장 커져서 실행된다. SJF의 기아 문제를 이렇게 줄인다.

6 / 6

18ms: 모두 끝남

기다린 시간은 P1 0ms, P2 4ms, P3 8ms, P4 5ms로 평균 4.25ms다. SJF(평균 4ms)와 거의 같으면서도 오래 기다린 프로세스를 함께 챙긴다.