멀티 레벨 피드백 큐 스케줄러(MLFQ)가 해결하려하는 문제 두가지

1. 짧은 작업을 먼저 실행시켜 반환 시간을 최적화
2. 대화형 사용자에게 응답이 빠른 시스템이란 느낌을 주기 위해 응답 시간 최적화

8.1 MLFQ: 기본 규칙

• MLFQ는 여러개의 큐로 구성, 각각 다른 우선순위 배정

• 실행 준비 된 프로세스는 이중 하나의 큐에 존재

• 큐에 둘 이상 작업 존재 가능

• 이 경우 모두 같은 우선순위 가지고

• 라운드 로빈 스케줄링 알고리즘 사용

• MLFQ는 각 작업의 특성에 따라 동적으로 우선순위 부여

• 긴 시간동안 CPU를 집중적 사용하는 작업의 우선순위 낮춤

MLFQ의 두가지 기본 규칙

1. Priority(A) > Priority(B)이면 A 실행.(B는 실행X)
2. Priority(A) = Priority(B)이면 A와 B는 RR 방식으로 실행

8.2 시도 1: 우선순위 변경

규칙

1. 작업이 시스템 진입시 가장 높은 우선순위, 즉 맨 위 큐에 놓여짐

   4 - a. 주어진 타임 슬라이스를 모두 사용하면 우선순위 낮아짐(한 단계 아래 큐로 이동 )

   4 - b. 타임 슬라이스 소진 전 CPU를 양도하면 같은 우선순위 유지
   

현재 MLFQ의 문제점

1. 기아 상태 발상 가능

• 시스템에 너무 많은 대화형 작업이 있으면 그것이 모든 CPU 시간을 소모할 것이고 실행시간이 긴 작업은 CPU 시간을 할당받지 못함

1. 스케줄러를 자신에게 유리하게 동작하도록 프로그램을 다시 작성할 수 있음

• 똑똑한 사용자가 스케줄러를 속여 지정된 몫보다 더 많은 시간을 할당하게 만들어 CPU를 독점할 수 있음

1. 프로그램은 시간 흐름에 따라 특성이 변할 수 있음

• CPU 위주 작업이 대화형 작업으로 바뀔 수 있음

시도 2: 우선순위의 상향 조정

단순한 기아 방지법: 주기적으로 모든 작업의 우선순위를 상향 조정 하는 것

규칙

1. 일정 기간 S가 지나면 시스템의 모든 작업을 최상위 큐로 이동 시킬 것

5번 규칙은 두가지 문제점을 모두 해결함

• 프로세스가 굶지 않음을 보장함
• CPU위주 작업이 대화형 작업으로 특성이 변할 경우 우선순위 상향으로 변경된 특성에 적합한 스케줄링 방법을 적용

8.4 시도 3: 더 나은 시간 측정

사용자가 스케줄러를 자신에게 유리하게 동작시키는 것을 막아야 함

해결책은 MLFQ의 각 단계에서 CPU 총 사용 시간을 측정하는 것

• 현재 단계에서 프로세스가 소진한 CPU 사용 시간 저장
• 프로세스가 타임 슬라이스에 해당하는 시간을 소진하면 다음 우선순위 큐로 강등

규칙 4: 주어진 단계에서 시간 할당량 소진 시 우선순위 낮아짐