[운영체제] 17. 우선순위 스케줄링(Priority 스케줄링) 알고리즘

운영체제의 스케줄링 알고리즘을 평가하기 위해서는 다음과 같은 특성을 충분히 이해해야 한다.

• 프로세서 사용률

프로세서를 항상 실행상태로 유지하여 유휴 상태가 되지 않도록 한다.

• 처리율

단위 시간당 완료하는 작업의 수가 많도록 하여 짧은 작업을 우선 처리하거나 인터럽트 없이 처리한다

• 반환 시간

작업이 메모리에 들어가기 까지 걸린 시간, 준비 큐에 머무르는 시간, 실행 시간, 입출력 시간 등 작업을 완료하는데 소요된 시간

• 대기 시간

프로세스가 실행이 되기 전 까지 대기되는 시간을 뜻한다.

• 반응 시간

작업을 요청한 시간부터 반응을 시작하는 시간까지의 간격

 

우선순위 스케줄링 (Priority Scheduling)

 

우선순위 스케줄링은 다음 그림과 같이 준비 큐에 프로세스가 도착하면, 도착한 프로세스의 우선순위와 현재 실행 중인 프로세스의 우선순위를 비교하여 우선순위가 가장 높은 프로세스에 프로세서를 할당하는 방식이다.

 

 

그럼 만약 우선순위가 동일한 프로세스가 준비 큐로 들어오게 되면 FIFO 의 순서로 스케줄링을 하게 된다.

 

우선순위의 선점과 비선점

 

또한 우선순위 스케줄링은 선점 또는 비선점이 존재하기 때문에 이 둘을 나눠서 생각해야 한다. 선점과 비선점의 방식도 동일하게 도착한 프로세스의 우선순위를 보고 구분을 하는데 기존 프로세스보다 우선순위가 높으면 할당한다.

 

우선순위 결정법

 

우선순위는 내부적, 외부적으로 정의할 수 있다.

• 내부적 우선순위 결정

제한 시간, 기억장소 요청량, 사용 파일 수, 평균 프로세서 버스트에 대한 평균 입출력 버스트의 비율

• 외부적 우선순위 결정

프로세스의 중요성, 사용료를 많이 낸 사용자, 작업을 지원하는 부서, 정책적 요인

 

장점

• 각 프로세스의 상대적 중요성을 정확히 정의할 수 있다.
• 다양한 반응으로 실시간 시스템에 사용 가능하다.

단점

• 높은 우선수위 프로세스가 프로세서를 많이 사용하면 우선순위가 낮은 프로세스는 무한정 연기되는 기아가 발생한다.

 

우선순위 스케줄링의 실행

 

준비 큐에 다음과 같은 프로세스들이 들어왔다고 가정한다. 유념해야 할 것이 우선순위는 높을 수록 빨리 처리가 된다. 1이라고 해서 1순위가 아니라는 소리다.

 

 

이를 토대로 간트 차트를 그려본다면 다음과 같다.

 

선점 우선순위 간트 차트 및 반환 시간

 

• p1프로세스가 준비 큐에 들어오고 기존 준비 큐에 프로세서를 점유하는 프로세스가 없기 때문에 실행한다.
• 1초에 p2가 들어오는데 우선순위가 p1보다 낮기 때문에 프로세서는 p1을 계속 점유한다.
• 2초에 p3가 들어오는데 우선순위가 p1보다 높기 때문에 프로세서는 p3를 점유한다.
• 3초에 p4가 들어오는데 우선순위가 p2보다 낮기 때문에 프로세서는 p3를 점유한다.
• 4초에 p5가 들어오는데 우선순위가 p2보다 낮기 때문에 프로세서는 p3를 점유한다. 이제 모든 프로세스가 준비 큐에 들어왔다.
• p3의 실행이 끝나고 우선순위를 확인하는데 p2의 우선순위와 p5의 우선순위가 같지만 FIFO로 인해 p2를 실행한다.
• ...반복

 

반환 시간 및 대기 시간

 

비선점 우선순위 간트 차트 및 반환 시간

 

 

• p1프로세스가 준비 큐로 들어오고 기존 준비 큐에 프로세서를 점유하는 프로세스가 없기 때문에 실행한다.
• p1이 끝날 때 까지 어떤 프로세스도 점유할 수 없기 때문에 p1이 끝나길 기다린다.
• p1이 끝나고 그 다음 우선순위가 높은 p3를 점유한다.
• p3가 끝나고 그 다음 우선순위가 높은 p2를 점유한다.
• ...반복

 

반환 시간 및 대기 시간

 

문제점과 에이징 방법

우선순위 알고리즘의 주요한 문제는 무한 정지와 기아상태 이다.

 

예를 들어 실행 준비가 되었으나 우선순위가 높은 프로세스가 계속 들어오면 우선순위가 낮은 프로세스는 무한정 대기해야 하는 상황이 발생한다. 이러한 기다림을 해결하는 방법이 바로 에이징이다.

 

에이징은 매 분마다 대기 중인 프로세스의 우선순위를 1씩 증가시킨다.

 

그러면 초기에 우선순위가 0이었단 프로세스가 대기중이면 프로세서를 점유중인 프로세스보다 우선순위가 높아지는 시점이 발생하여 무한 정지와 기아상태를 해결할 수 있다.

 

이를 그래프로 나타내면 다음과 같다.