CPU Scheduling(스케줄링) - HRRN 스케줄링, 라운드 로빈 스케줄링

<HRRN(Highest Respone Ratio Next) 스케줄링>

수행 시간이 긴 프로세스의 무한 대기 현상을 방지하기 위한 기법이다.

준비 큐에 있는 프로세스들 중에서 응답률(Response Ratio)이 가장 높은 프로세스에게 높은 우선순위를 주며, 비선점식 방식이다.

응답률 = (대기시간 + CPU요구량) / CPU요구량

즉, 대기시간이 올라갈 수록 응답률이 높아진다.

이 기법을 사용하면 프로세스가 기다리는 시간이 길어질수록 우선순위가 높아지므로 수행시간이 긴 프로세스도 머지않아 CPU를 할당받을 수 있게 된다.

[프로세스에 대해 응답률을 구하는 방법]

그래서 P1 -> P2 -> P3순으로 실행시키는 것이다.

<라운드 로빈 방식>

FCFS 스케줄링을 기반으로 하여 CPU를 할당하되, 각 프로세스는 한 번에 쓸 수 있는 CPU 시간 크기 즉, 시간 할당량(Time Quantum)이 지나면 시간 종료 인터럽트에 의해 CPU를 뺏기게 되는 선점 방식이다.

 

위 그림을 보면 시간 할당량이 지나 시간 종료가 되면 다시 준비 큐의 끝에 들어가게 되고, 준비 큐의 맨 앞에 있는 프로세스가 CPU를 받게되는 방식이다. 그리고 입출력 큐에서 입출력을 마친 프로세스들은 ①번 경로를 따라 준비큐로 들어가도록 해주면 이것 또한 라운드 로빈 방식이 구현되는 것이다.

[계산법]

모든 프로세스들이 0초에 시작했다고 가정하자.

이 기법은 한 프로세스가 CPU를 독점하는 단점은 방지하나, CPU의 선점에 따른 문맥교환의 오버헤드를 감수해야 한다.

입출력 위주의 프로세스보다 연산위주의 프로세스를 더 우대한다. 이유는 연산 위주는 주어진 시간 할당량을 모두 소진하고 큐의 맨 뒤로 가는데 반해, 입출력 위주는 대부분 시간 할당량을 남긴 채 입출력을 발생시킨 다음 입출력이 완료되면 당시 남겨진 시간 할당량 부분을 보상받지 못한 채 큐의 맨 뒤로 들어간다.

이 기법은 대화식 시스템이나 시분할 시스템에 적합한 방식이다.

이러한 문제점을 보완하기 위해, 가상 라운드 로빈을 사용한다.

가상 라운드 로빈은 준비 큐를 따로 하나 두고 우선 순위는 더 높게 하되, 이 큐에서 CPU를 받을 때는 이전 입출력을 발생했을 때 쓰지 못하고 남긴 시간 할당량 만큼만 주도록 하는 방법이다.

 

Copyrightⓒ2014 By 휴먼사이언스