19_스케줄링 알고리즘 - 우선순위, 라운드 로빈, 다단계 큐, 다단계 피드백큐 스케줄링

19_스케줄링 알고리즘

• 우선순위, 라운드 로빈, 다단계 큐, 다단계 피드백큐 스케줄링

 

 

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

최단 우선 작업 스케줄링(SJF)은 우선 순위 스케줄링 알고리즘의 특별한 경우다. 우선순위가 각 프로세스들에게 연관되어 있으며 CPU는 가장 높은 우선순위를 가진 프로세스에게 할당 된다. 우선 순위가 같은 프로세스들은 선입 선처리(FCFS)순서로 스케줄 된다. SJF 알고리즘은 우선순위(p)가 예상되는 다음 CPU 버스트의 역인 안순한 우선 순위 알고리즘이다. CPU 버스트가 클수록 우선순위가 낮으면 그 역도 성립한다.

 

아래 표와 그림은 프로세스 순서대로 도착한 순서와 버스트 시간 그리고 프로세스 되는 스케줄링 간트 차트 이다.

프로세스	버스트 시간	우선순위
P1	10	3
P2	1	1
P3	2	4
P4	1	5
P5	5	2

 

 

우선순위는 내부적 또는 외부적으로 정의될 수 있다. 내부적으로 정의된 우선순위는 프로세스의 우선순위를 계산하기 위해 어떤 측정 가능한 양들을 사용한다. 우선순위 스케줄링은 선점형 또는 비선점형일 수 있다. 스케줄링 순서이다.

1. 프로세스 준비 완료 큐 도착
2. 새로 도착한 프로세스의 우선순위를 현재 실행 중인 프로세스의 우선순위와 비교
3. 선점형 우선순위 알고리즘은 새로 도착한 프로세스의 우선순위가 현재 실행되는 프로세스의 우선순위보다 높으면 CPU를 선점
4. 비선점형 우선순위 스케줄링 알고리즘은 단순히 준비 완료 큐의 머리 부분에 새로운 프로세스 삽입

 

우선순위 스케줄링의 알고리즘의 주요 문제는 무한 봉쇄(Idefinite blocking)와 기아 상태(starvation)이다.

• 무한 봉쇄(Idefinite blocking) : 실행 준비는 되어 있으나 CPU를 사용하지 못하는 프로세스는 CPU를 기다리면서 봉쇄된 것으로 간주 될 수 있다.
• 기아 상태(starvation) : 우선 순위 알고리즘의 경우 부하가 높은 컴퓨터에서 우선순위가 높은 프로세스들이 꾸준히 들어와 낮은 우선순위 프로세스들이 CPU를 무한히 대기하는 상태가 발생한다.

 

낮은 우선 순위의 프로세스들을 무한히 봉쇄하는 문제에 대한 해결방안으로 Aging이 있다. Aging는 오랫동안 시스템에 대기한 프로세스들의 우선 순위를 점진적으로 증가시키는 기법이다.

 

 

[라운드 로빈 스케줄링(Round Robin Scheduling)]

 

시분할 시스템을 위해 설계된 알고리즘. 선입 선처리 스케줄링 방식과 유사하지만 프로세스들 사이를 옮겨 다니기 위해서 선점이 추가된다. 시간 할당량(time quantum) 또는 시간 조각(time slice)이라고 하는 작은 단위의 시간을 정의한다. 시간 할당량은 일반적으로 10~100ms 이다. 준비 완료 큐는 원형 큐(circular queue)로 동작한다. CPU 스케줄러는 준비 완료 큐를 돌면서 한 번에 한 프로세스에게 한 번의 시간 할당량 동안 CPU를 할당한다.

1. 준비 완료 큐를 프로세스들의 선입선출 큐로 유지
2. 새로운 프로세스들은 준비 완료 큐의 꼬리에 추가
3. CPU 스케줄러는 준비 완료 큐에서 첫 번째 프로세스를 선택
4. 한 번의 시간 할당량 이후 인터럽트 되도록 타이머(timer) 설정 후 프로세스 디스패치(dispatch)

 

다음 예제에서 시간 할당량을 4로 한다면 다음과 같은 스케줄링이 할당 된다.

프로세스	버스트 시간
P1	24
P2	3
P3	3

 

 

라운드 로빈 스케줄링 알고리즘에서는 유일하게 실행 가능한 프로세스가 아니라면 연속적으로 두번 이상의 시간 할당량을 할당 받는 프로세스는 없다. 프로세스의 CPU 버스트가 한 번의 시간 할당량을 초과하면 프로세스는 선점되고 준비 완료 큐로 되돌아간다

 

라운드 로빈 알고리즘의 성능은 시간 할당량 크기에 매우 많은 영향을 받는다. 시간 할당량이 매우 크면 선입 선처리 정책과 같아 지며 매우 적다면 문맥 교환에 의한 성능이 저하 된다. 대부분의 프로세스들이 단일 시간 할당량 안에 다음 CPU 버스트를 끝낸다면 평균 총 처리 시간은 개선된다. 일반적으로 버스트의 80%는 시간 할당량 보다 짧아야 한다.

 

[다단계 큐 스케줄링(Multilevel Queue Scheduling)]

준비 완료 큐를 다수의 별도 큐로 분류한다. 예를 들어 포어그라운드와 백그라운드 프로세스들을 위해 별도의 큐를 사용하는 것이다.

큐와 큐 사이에 반드시 스케줄링이 있어야 하며 일반적으로 고정 우선순위의 선점형 스케줄링으로 구현 된다. 예를 들어 포어그라운드 큐는 백그라운드 큐보다 절대적으로 높은 우선순위를 가질 수 있다.

 

[다단계 피드백 큐 스케줄링(Multilevel Feedback Queue Scheduling)]

다단계 큐 스케줄링 알고리즘에서는 일반적으로 프로세스들이 시스템 진입 시 영구적으로 하나의 큐에 할당 된다. 이러한 방식은 적은 스케줄링 오버헤드가 장점이지만 융통성이 적다.

 

 

다단계 피드백 큐 스케줄링 알고리즘은 프로세스가 큐들 사이를 이동하는 것을 허용 한다. 낮은 우선 순위에 너무 오래 대기하는 프로세스는 높은 우선순위의 큐로 이동 할 수 있다.

 

일반적의 다단계 피드백 큐 스케줄러는 다음 매개변수에 의해 정의 된다.

• 큐의 개수
• 각 큐를 위한 스케줄링 알고리즘
• 한 프로세스를 높은 우선순위 큐로 올려주는 시기를 결정하는 방법
• 한 프로세스를 낮은 우선순위 큐로 강등시키는 시기를 결정하는 방법
• 프로세스가 서비스를 필요로 할 때 프로세스가 들어갈 큐를 결정하는 방법

 

다단계 피드백 큐는 가장 일반적인 CPU 스케줄링 알고리즘이지만 모든 배겨 변수들의 값을 선정하는 특정 방법이 필요하기 때문에 가장 복잡한 알고리즘이기도 하다.

 

 

 

[참고자료]

Operating System Concept / 홍릉과학출판사