운영체제 6. 스케줄링 : 멀티 레벨 피드백 큐(MLFQ : Multi-Level Feedback Queue)

6. 스케줄링 : 멀티 레벨 피드백 큐(MLFQ : Multi-Level Feedback Queue)

• 멀티 레벨 피드백 큐 스케줄러는 Compatible Time-Sharing System(CTSS)에 사용된다.
• MLFQ가 해결하려고 하는 기본적인 문제는 두 가지이다.
  • 첫째, 짧은 작업을 먼저 실행시켜 반환시간을 최적화 하고자 한다.
  • 둘째, 응답 시간을 최적화한다.

6.1 MLFQ : 기본 규칙

• MLFQ는 여러 개의 큐로 구성되며, 각각 다른 우선 순위(Priority level)가 배정된다. 실행준비가 된 프로세스는 이 중 하나의 큐에 존재한다. MLFQ는 실행할 프로세스를 결정하기 위하여 우선순위를 사용한다. 높은 우선 순위를 가진 작업이 선택된다.
• 큐에 둘 이상의 작업이 존재 할 수 있다. 이들은 모두 같은 우선순위를 가진다. 이 작업들 사이에서는 라운드 로빈(Round-Robin, RR) 스케줄링 알고리즘이 사용된다.
• MLFQ 스케줄링의 핵심은 우선순위를 정하는 방식이다. MLFQ 각 작업에 고정된 우선순위를 부여하는 것이 아니라 각 작업의 특성에 따라 동적으로 우선순위를 부여한다.
• MLFQ의 두 가지 기본 규칙은 다음과 같다.
  • 규칙1 : Priority(A) > Priority(B)이면, A가 실행된다.
  • 규칙2 : Priority(A) = Priority(B)이면, A와 B는 RR방식으로 실행된다.

6.2 시도1 : 우선 순위의 변경

• 규칙 3 : 작업이 시스템에 진입하면, 가장 높은 우선순위, 즉 맨 위 큐에 놓여진다.
• 규칙 4-a : 주어진 타임 슬라이스를 모두 사용하면 우선순위는 낮아진다. 즉, 한 단계 아래 큐로 이동한다.
• 규칙 4-b : 타임 슬라이스를 소진하기 전에 CPU를 양도하면 같은 우선순위를 유지한다.
• 스케줄러는 작업이 짧은 작업인지 긴 작업인지 알 수 없기 떄문에 일단 짧은 작업이라고 가정하며 높은 우선순위를 부여한다. 진짜 짧은 작업이면 빨리 실행되고 바로 종료할 것이다. 짧은 작업이 아니라하면 천천히 아래 큐로 이동하게 되고 스스로 간 배치형 작업이라는 것을 증명하게 된다. 이러한 방식으로 MLFQ는 SJF를 근사할 수 있다.

현재 MLFQ의 문제점

• 첫째, 기아 상태(Stavation)가 발생할 수 있다.
• 둘째, 똑똑한 사용자라면 스케줄러를 자신에게 유리하게 동작하도록 프로그램을 다시 작성할 수 있다. 스케줄러를 자신에게 유리하게 동작하도록 하는것은 일반적으로 스케줄러를 속여서 지정된 몫보다 더 많은 시간을 할당하도록 만드는 것을 가리킨다.

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

• 주기적으로 모든 작업의 우선순위를 상향 조정(boost)한다.
• 간단한 방법으로는 모두 최상위 큐로 보내는 것이다.
  • 규칙 5 : 일정시간 s가 지나면, 시스템의 모든 작업을 최상위 큐로 이동시킨다.

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

• 스케줄러를 자신에게 유리하게 동작 시키는 것을 어떻게 막을 수 있는가?
  • 여기서의 해결책은 MLFQ의 각 단계에서 CPU 총 사용시간을 측정하는 것이다. 스케줄러는 현재 단계에서 프로세스가 소진한 CPU 사용시간을 저장한다. 프로세스가 타임 슬라이스에 해당하는 시간을 모두 소진하면 다음 우선순위 큐로 강등된다. 타임슬라이스를 한번에 소진하든 짧게 여러번 소진하든 상관없다. 규칙 4a와 4b를 합쳐 하나의 규칙으로 재정의 한다.
  • 규칙 4 : 주어진 단계에서 시간 할당량을 소진하면(CPU를 몇 번 양도하였는지 상관없이), 우선순위는 낮아진다.