정보처리산업기사, 정보처리기사 - HRN 스케줄링 알고리즘 집중 탐색!!

※ 공부 내용의 복습 개념으로 정리된 글입니다.

 

HRN 스케줄링 알고리즘

HRN 스케줄링 알고리즘은 우선순위를 결정하기 위해 "응답 비율"을 사용합니다.

SJF 기법을 보완하기 위한 것으로, "대기 시간"과 "실행 시간"을 이용하는 기법입니다.

각 프로세스마다 응답 비율을 계산하고, 가장 높은 응답 비율을 갖는 프로세스가 CPU를 할당받습니다.

응답 비율은 다음과 같이 계산됩니다.

여기서 "대기 시간"은 프로세스가 대기한 시간이며, "실행 시간"은 CPU를 사용한 시간입니다.

 

HRN 알고리즘의 동작 과정

1. 모든 프로세스의 대기 시간을 초기화합니다.
2. 각 프로세스의응답 비율을 계산합니다
3. 가장 높은 응답 비율을 가진 프로세스를 선택하여 CPU를 할당합니다.
4. 선택된 프로세스가 실행되는 동안 다른 프로세스들은 대기 시간을 증가시킵니다.
5. 프로세스가 완료되면 해당 프로세스는 제거됩니다.
6. 모든 프로세스가 완료될 때까지 위 과정을 반복합니다.

 

 

HRN 알고리즘의 장단점

• 장점
  • 응답 시간을 최대화하여 사용자의 대기 시간을 최소화합니다.
  • 상대적으로 간단한 알고리즘으로 구현이 비교적 쉽습니다.
• 단점
  • 모든 프로세스의 실행 시간을 알아야 하므로, 실행 시간을 예측하기 어려운 상황에서는 성능이 저하될 수 있습니다.
  • 오버헤드가 크지 않지만, 대기 시간을 계산하는 과정이 추가됩니다.

 

HRN 알고리즘 예제

다음과 같은 프로세스가 HRN 기법으로 스케줄링될 때 우선순위를 계산하시오.

프로세스 번호	P1	P2	P3
실행 시간	20	4	6
대기 시간	10	20	10
우선순위 계산	(10 + 20) / 20 = 1.5	(20 + 4) / 4 = 6	(10 + 6) / 6 = 2.6
우선순위	P2 → P3 → P1