[OS] HRN(Highest Response Ratio Next) 스케줄링 이란?

서론

이번 글에서는 운영체제의 프로세스 스케줄링 기법 중 하나인 HRN 스케줄링에 대하여 살펴본다.

HRN 스케줄링을 이해하기 위해서는 선수 지식으로 SJF(Shortest Job First) 스케줄링 기법에 대한 개념이 필요하다.

 

SJF 스케줄링에 대한 이해가 부족한 분들은 아래 글을 참고하면 좋을 것 같다.

• [OS] 최단 작업 우선 스케줄링(SJF) 이란?

[OS] 최단 작업 우선 스케줄링(SJF) 이란?

HRN 이란?

HRN(Highest Response Ratio Next) 스케줄링은 최고 응답 우선 스케줄링 이라고 불린다. HRN의 등장배경은 SJF 스케줄링 기법의 문제점인 기아 상태(Starvation) 문제를 해결하기 위해 나타난 비선점형 스케줄링이다.

• 기아 상태 : 특정 프로세스의 우선 순위가 낮아, 원하는 자원을 할당 받지 못하는 상태
• 비선점형 : 특정 프로세스가 자원을 할당 받으면 일이 끝날 때까지 CPU를 독점하는 것

SJF 스케줄링의 경우 CPU 점유 시간이 작은 프로세스에 우선권이 주어진다. 따라서 작업량이 많아 CPU 점유 시간이 높은 프로세스의 경우 자원을 할당 받지 못하거나 오래 기다려야 하는 경우가 발생한다.

 

그러나 HRN 스케줄링 기법의 경우는 CPU 점유 시간과 더불어 대기 시간(기다린 시간)을 함께 고려하여 우선순위를 부여하고 우선 순위에 따라 CPU를 차례대로 할당 받아 작업을 수행한다.

우선 순위 구하는 방법

우선 순위 = (대기 시간 + CPU 점유 시간) / CPU 점유 시간

HRN 스케줄링 기법에서 우선 순위를 구하는 방법은 위와 같다.

프로세스가 실행되는 순서는 우선 순위가 높은 순에서 낮은 순서대로 차례대로 CPU를 할당 받아 작업을 수행한다.

 

예시를 통해 HRN 스케줄링 기법을 이해해보자.

작업	대기 시간	서비스 실행 시간
A	5	20
B	40	20
C	15	45
D	20	2

위와 같은 4개의 프로세스가 있고 해당 프로세스들의 대기 시간, 실행 시간이 있다고 할 때 우선순위는 다음과 같다.

 

• 프로세스 A : (5 + 20) / 20 = 1.25
• 프로세스 B : (40 + 20) / 20 = 3
• 프로세스 C : (15 + 45) / 45 = 1.3333...
• 프로세스 D : (20 + 2) / 2 = 11

프로세스 실행 순서는 우선 순위가 높은 순에서 낮은 순으로 실행된다고 했으므로 4개의 프로세스에 대한 실행 순서는 다음과 같다.

 

• D → B → C → A

결론

HRN 스케줄링 기법은 Starvation 문제를 해결할 수 있다는 점에서는 장점이 될 수 있다.

그러나, SJF 스케줄링 기법과 마찬가지로 공평성에 어긋난다는 단점이 있기 때문에 프로세스 스케줄링 방식을 선정할 때 많이 사용되지는 않는다.