운영체제 MLFQ

MLFQ 는 multi level feedback queue 로, 앞서 말한 stcf 는 반환시간이 가장 최적화된 스케줄링인데, 이는 현실적으로는 불가능하다. 

 

그 이유는 stcf 의 경우에는 남아있는 시간을 판별해야 하는데, 이는 미래를 보아야 하기 때문에 불가능 하다. 

 

그리고 stcf 의 경우는 반응시간이 길고 반대로 round robin 의 경우는 반환시간이 길다. 

 

따라서 이 둘의 이점을 둘 다 가지는 mlfq 를 만들려고 한다. 

 

mlfq 는 높은 우선순위의 프로세스를 먼저 시행하는 스케줄링이다. 

 

그리고 우선순위를 계속 내리기 때문에 규칙을 정해 보도록 한다. 

 

따라서 규칙 

1. 높은 우선순위를 시행한다. 

 

2. 우선순위가 같으면 round robin 으로 공정하게 시행한다. 

 

3. 일단 처음의 시행은 가장 높은 우선순위로 시행한다. 

 

4.

- 만약 타임 아웃 해질때까지 계속 cpu 를 사용하면 long job 으로 간주하여 우선순위를 내린다. 

 

- 그런데 타임아웃 전에 I/O 발생할 경우 우선순위를 유지한다.

 

(이 규칙을 지킬때에 I/O 처리 후에 처리 하고 있던 프로세스를 time out 까지 할 수 도 있고, 중간에 interrupt 가 발생하여 I/O 가 끝난 프로세스를 처리 할 수 도 있다.)

 

하지만, 위의 규칙을 지킬 때에 문제가 두개 발생한다.  

 

1. starvation - 계속 short job이 들어오면 시행이 안 될수 도 있다.

 

2. 프로그래머가 편집으로 (중간에 I/O 삽입으로) 강제로 우선순위를 조정할 수 있다. 

 

이 둘을 해결하기 위해서 먼저 규칙 하나를 추가한다. 

 

규칙 5. 주기적으로 같은 시간에 모든 JOB 을 맨 위로 올린다. (boosting)

따라서 starvation을 해결한다.

 

2번째 문제를 해결하기 위해서는 규칙 4를 고쳐서 time out 전에 I/O 가 나오면 유지하는 것이 아닌, I/O 처리와 상관 없이 한 프로세스가 일정시간을 쓰게 되면, 우선순위를 내린다. 

 

또한, 더 개선하기 위해서 각각의 우선순위 큐 별로 time out 시간을 길게 조정한다. 

 

(이때의 시간과 boosting 의 주기는 알아서 잘 정해야한다.)