08 Scheduling: The Multi-Level Feedback Queue

MLFQ : 가까운 과거를 이용하여 미래를 예측하는 방식, 짧은 작업을 먼저 실행시켜 반환 시간을 최적화, 응답 시간도 최적화 -> 어떻게?

 

MLFQ에서는 priority가 다른 다수의 작업큐를 사용한다.

큐에 둘 이상의 작업이 존재하면 그들은 RR방식으로 스케쥴되고 한번 실행 후에 해당 작업의 특성에 따라 priority를 유지시키거나 강등시키는 방법을 사용한다.

 

다음과 같은 규칙을 사용한다.

 

Rule 1. Priority(A) > Priority(B)이면 A가 실행된다.

Rule 2. Priority(A) = Priority(B)이면 A와 B는 RR 방식으로 실행된다.

 

그렇다면 Rule1에서 B는 영원히 실행되지 않는것인가?

그렇지 않다.

MLFQ에서는 작업의 우선순위를 변경해주기 위한 다른 Rule이 존재한다.

 

Rule 3. 작업이 시스템에 도착하면 가장 높은 priority의 큐에 배치한다.

Rule 4a. 작업이 주어진 time slice를 모두 사용하면 한단계 낮은 priority 큐에 배치한다.

Rule 4b. 작업이 주어진 time slice를 모두 사용하지 않고 CPU를 양도한다면 priority를 유지한다.

 

rule 4b의 의도는 interactive 작업을 빨리 실행시킨다는 것이다.

 

발생가능한 문제점

1. starvation (기아상태)

가장 높은 priority 큐에 여러개의 입출력 작업이 존재한다면?

그들이 time slice 전에 CPU작업을 마무리한다면 그들끼리만 RR방식으로 실행되고 lower prioriry queue의 작업은 영원히 실행되지 않을 것이다.

 

2. gaming the OS

만약 어떤 작업이 time slice의 99% 시간만큼 CPU를 사용하고 입출력작업으로 전환하는 방식을 사용하면 어떻게 되는가?

이 작업은 time slice를 다 소진하지 않고 CPU를 양도하기 때문에 priority를 유지한다. 즉, CPU를 거의 독점할 수 있게 된다.

 

3. 프로그램의 특성이 변할 경우

만약 CPU-intensive 작업이 어느순간부터 입출력 중심으로 바뀌면 어떻게 되겠는가?

이 작업은 이미 lower priority queue에 배치된 상태이고 다시는 higher priority queue에 배치될 수 없다.

 

Priority Boost

일정시간 간격마다 모든 작업을 최상위 priority queue로 배치해준다.

이 방식이라면 위의 1번과 3번 문제점을 해결할 수 있다.

 

 

자 그럼 위의 2번 문제점은 어떻게 해결할 것인가?

2번 문제점은 time slice 안에 작업이 CPU를 양도할 때 발생한다.

이는 MLFQ의 각 단계에서 각 작업의 CPU 총 사용시간을 측정한 뒤 그 값이 time slice에 해당하는 값에 다다르면 그 작업의 priority를 낮춰주는 방식으로 해결할 수 있다.

 

 

추가로, 낮은 priority queue일수록 time slice를 길게 잡는 방식도 있다.

 

정리

Rule 1. priority(A) > priority(B) 일 경우 A가 실행 되고 B는 실행되지 않는다.

Rule 2. priority(A) = priority(B) 일 경우 A와 B는 RR 방식으로 실행된다.

Rule 3. 작업이 시스템에 들어가면 우선 최상위 priority의 큐에 배치된다.

Rule 4. 작업이 지정된 단계에서 배정받은 시간(time slice값)을 소진하면 작업은 한단계 낮은 priority 큐에 배치된다.

Rule 5. 일정 주기 S가 지난 후, 시스템의 모든 작업을 최상위 priority 큐로 이동시킨다. (priority boost)