CPU Scheduling - Scheduling Algorithm_3

Priority Scheduling(이하 PS), 우선순위 스케쥴링

 

Priority Scheduling이란 각각의 Process에게 우선순위를 주어 그 우선순위에 따라 스케쥴링 하는 방식이다.

 

SJF 알고리즘의 경우 CPU-Burst Time의 값이 작은 순으로 스케쥴링을 하고 PS의 경우 Priority의 값이 작은 순으로 스케쥴링을 한다.

 

즉, Priority의 값이 작을수록 높은 우선순위를 가지게 되는 것이다.

 

예를 들어보자. P1, P2, P3, P4의 CPU-Burst Time의 값과 Priority가 아래와 같다고 보자.

 

 

 

이를 PS 알고리즘을 이용해서 스케쥴링 한 결과를 Grantt Chart로 나타내면 아래와 같다.

 

 

 

이 결과 Average Waiting Time은 (0+1+6+16+18)/5 = 8.2 milliseconds가 된다.

 

이런식으로 각각의 Process에 따라 Priority 주어지고 그 값들을 비교하여 더 낮은 Priority값(높은 우선순위)를 가진

 

Process부터 처리를 한다. 그렇다면 각각의 Process의 Priority값은 어떻게 매기는가??

 

Priority 결정 방법은 크게 두가지로 나누어 질수 있다.

 

Internally Defined Priority

 

이는 Priority의 값을 내부적으로 측정된 값을 통해서 정하는 방법이다. 각각 Process들마다 요구되는 자원의 양이나

 

CPU-Burst Time, 제한시간, 사용하는 파일의 수 등을 고려하여 Priority를 정한다.

 

Externally Defined Priority

 

이는 Priority의 값을 외부적으로 주어진 값을 통해서 정하는 방법이다. Process의 중요성이나 컴퓨터 이용료및 이용형태

 

정책적인 사유등을 이유로 Priority를 정한다.

 

PS 알고리즘 역시 SJF 알고리즘과 마찬가지로 Preemptive와 Non-Preemptive둘 모두로 구현이 가능하다.

 

만일 새로 들어온 Process가 현재 수행중인 Process보다 우선순위가 높을때 현재 수행중인 Process를 정지하고

 

새로운 Process를 수행시키면 Preemptive이고 수행중인 Process를 유지하고 새로 들어온 Process를 Ready Queue의

 

머리 부분에 두면 Non-Preemptive형태이다. 또 우선순위가 같다면 상관없이 FCFS형태로 스케쥴링을 한다.

 

이러한 특성을 가진 PS 알고리즘의 가장 큰 문제는 Starvation 즉, 기아상태이다. 지속적으로 새로운 Process가

 

Load되는 시스템에서 낮은 Priority를 가진 Process의 경우 계속해서 수행이 안되는 경우가 생길수 있다.

 

실제로 어떤 슈퍼컴퓨터의 경우 20년이상 수행이 안된 Process가 발견된 적도 있다고 한다. 이러한 문제를 해결하기 위한

 

방법이 바로 Aging이다. Aging이란 낮은 Priority를 가진 Process가 일정 시간 이상 수행되지 못하고 대기하고 있다면

 

Priority의 값을 한 단계씩 상향조정 함으로써 Process가 Starvation상태에 빠지는 것을 방지하는 기법이다.