HRN
대기 시간과 실행 시간을 모두 고려한 우선순위 공식으로 프로세스를 선택하는 비선점형 스케줄링 알고리즘으로, SJF의 기아 문제를 보완합니다.
우선순위 공식
우선순위 = (대기 시간 + 실행 시간) / 실행 시간
→ 값이 클수록 높은 우선순위
예시
| 프로세스 | 대기 시간 | 실행 시간 | 우선순위 |
|---|---|---|---|
| P1 | 20ms | 20ms | (20+20)/20 = 2.0 |
| P2 | 15ms | 5ms | (15+5)/5 = 4.0 |
| P3 | 5ms | 15ms | (5+15)/15 = 1.3 |
실행 순서: P2(4.0) → P1(2.0) → P3(1.3)
SJF vs HRN
| SJF | HRN | |
|---|---|---|
| 기준 | 실행 시간만 고려 | 대기 시간 + 실행 시간 고려 |
| 기아 발생 | O | X |
| 대기 시간 반영 | X | O |
| 구현 복잡도 | 단순 | 보통 |
기아 방지 원리
대기 시간이 길어질수록
→ 분자(대기 시간 + 실행 시간)가 커짐
→ 우선순위 자동으로 높아짐
→ 언젠가는 반드시 실행됨 O
단점
- 실행 시간을 미리 알기 어려움 (SJF와 동일한 한계)
- 비선점이므로 응답성 낮음
- 매번 우선순위를 계산해야 함
HRN은 대기 시간을 우선순위에 반영하여 SJF의 기아 문제를 해결하지만, 실행 시간을 예측해야 한다는 현실적 한계는 여전히 존재합니다.