Chapter5 프로세스 스케줄링(Multilevel Queue, Multilevel Feedback Queue )

1. Multilevel Queue의 개념(선점형)

ready Queue에는 5개의 종료가 있고 System processes가 가장 우선순위가 높다. 각 Queue들은 아래로 갈수록 우선순위가 낮아진다. 그리고 Multilevel Queue에서는 5개의 Queue간의 이동은 금지한다.

 

system processes에 있는 P1, P2 프로세스와 interactive processes에 있는 프로세스 P3가 있을 때 P1과 P2는 우선순위가 같고 P1,P2가 P3 보다 우선순위가 높다.

그리고 system processes의 P1과 P2는 이들 간에서도 스케줄링을 통해 P1 또는 P2가 실행되게 된다.

 

그리고 낮은 우선순위 Queue에서 프로세스(Q1)가 실행되가가 상대적으로 더 높은 우선순위의 Queue에 프로세스(Q2)가 들어오게 되면 Q1가 CPU를 점유하고 동작하고 있다가 Q2가 들어오면 Q2에 CPU를 점유시키고 Run 시키게 된다.

 

※ interactive, batch

프로세스에는 크게 사용자와 대화형으로 동작하는 foreground(interactive) 프로세스와 사용자 눈에는 보이지 않지만 커널이 실행하고 있는 background(batch) 두 종류의 프로세스로 분류할 수 있다.

이 둘간의 우선순위는 interactive가 더 높다.

 

foreground(interactive) 프로세스는 Round-Robin(RR) 스케줄링 기법이 사용된다.

background(batch)는 First Come First Served(FCFS) 스케줄링 기법이 사용된다.

 

 

● Multilevel Queue Scheduling Algorithm

5개의 Multilevel Queue에서 하나의 Queue에 대해서도 CPU 스케줄링이 일어나는데 이때 Round Robin(RR) 알고리즘 + 우선순위 스케줄링이 사용된다.

 

※ SJF의 문제점으로 starvation이 발생하고 이를 해결하기 위해 Round Robin 방식이 등장함.

멀티 큐 스케줄링에서 한 큐에서 스케줄링을 할 때 우선 순위 스케줄링 기법 중 하나인 SJF를 사용할 수 있는데 이는 startvation 문제를 해결해야한다. 그 방법으로 우선순위를 점진적으로 증가시키는 방법이 있었지만 다른 방법으로 Round Robin과 비선점 우선순위 스케줄링을 결합한 방법으로 스케줄링하는 방법을 사용하여 스케줄링한다.

따라서 Multilevel Queue Scheduling Algorithm에서 하나의 Queue에서는 Round Robin 방식과 비선점형 SJF를 사용한다고 할 수 있다.

 

반면, 5개의 Queue들 간에는 스케줄링이 필요없다. 왜? -> 이들은 우선순위 level을 가지기 때문이다.

---

 

2. Multilevel Feedback Queue Scheduling Algorithm

● 개념(RR – 선점형이다)

다단계 큐 스케줄링 알고리즘(Multilevel Queue Scheduling Algorithm) 에서는 일반적으로 프로세스들이 시스템 진입 시에 영구적으로 하나의 큐에 할당된다.

대조적으로 다단계 피드백 큐 알고리즘(Multilevel Feedback Queue Scheduling Algorithm )에서는 프로세스가 큐들 사이를 이동하는 것을 허용한다.

Iead는 프로세스들을 CPU burst 성격에 따라서 구분한다. 다단계 피드백 큐에서는 I/O중심의 프로세스와 foreground 프로세스들을 높은 우선순위의 큐에 넣는다. 즉 짧은 CPU 버스트를 가진 프로세스가 상대적으로 더 높은 위치의 Queue에 들어가게 된다.

위 이미지는 다단계 피드백 큐이며 위에서부터 차례로 Queue 0,1,2 라고 부르겠다.

스케줄러는 처음에 Queue 0에 모든 프로세스를 실행시킨다.

그리고 0이 비어있을 때만 1을 실행시키고 1이 비어있을 때만 2를 실행시킨다.

예를 들어 새로 진입하는 프로세스가 있을 때 이는 8ms의 시간 할당량이 주어지는데 이 시간안에 끝나지 않는다면 Queue 1의 꼬리로 이동한다. 그리고 큐 0이 비어있다면 큐 1에의 머리에 있는 프로세스를 16ms(time slice)의 시간 할당량을 가지고 실행하게 된다.

그래도 프로세스가 완료되지 않는다면 큐 2(마지막 큐)으로 이동하게 된다.

큐2는 마지막 큐로 큐0, 1이 비어있을 때 FCFS 방식으로 동작한다 .

그리고 우선 순위가 낮은 큐에 너무 오래 대기하는 현상이 발생하면 해당 프로세스를 점차 우선순위가 높은 큐로 이동시킨다. (Aging 기법)

 

다단계 큐 피드백에서는 위 예시라면 8ms 이하의 모든 프로세스에게 가장 높은 우선순위를 주게 되는 것이고 이러한 프로세스는 빨리 CPU burst를 끝내고 I/O burst로 간다

 

※ Queue 0,1 은 RR 방식이고 Queue 2에서는 선입 선처리 방식(FCFS)으로 동작한다.

---