Operating System: 04. 멀티 레벨 피드백 큐

MLFQ의 기본 알고리즘

• 여러 개의 큐로 구성되며, 각각 다른 우선순위(priority level)가 배정된다.

규칙

1. Priority(A) > Priority(B) 이면, A가 실행된다(B는 실행되지 않는다).
2. Priority(A) = Priority(B) 이면, A와 B는 RR 방식으로 실행된다.
3. 작업이 시스템에 진입하면, 가장 높은 우선순위, 즉 맨 위의 큐에 놓인다.
4. 주어진 타임 슬라이스를 모두 사용하면 우선순위는 낮아진다. 즉, 한 단계 아래 큐로 이동한다.
5. 타임 슬라이스를 소진하기 전에 CPU를 양도하면 같은 우선순위를 유지한다.

현재 규칙의 문제점

1. 기아 상태(starvation)
   • 시스템에 너무 많은 대화형 작업이 존재하면 긴 시행 시간 작업은 CPU 시간을 할당받지 못할 것이다.
2. 사용자의 악용
   • 스케줄러의 규칙을 안다면, 사용자는 타임슬라이스가 끝나기 전에 입출력 요청을 내려 CPU를 양도한다면 독점해서 CPU를 사용할 수 있다.

우선순위 상향 조정

• 일정 시간 S가 지나면, 시스템의 모든 작업을 최상위 큐로 이동시킨다.
  • 프로세스가 굶어 죽지 않는다는 것을 보장한다.
  • CPU 위주의 작업이 대화형 작업으로 특성이 변할 경우 변경된 특성에 맞는 적합한 스케줄링 방법이 적용된다.

CPU의 총사용 시간 측정

• 주어진 단계에서 시간 할당량을 소진하면 (CPU를 몇 번 양도하였는지 상관없이), 우선순위는 낮아진다.

MLFQ 조정과 다른 쟁점들

- 몇 개의 큐가 존재해야 하는가?
- 큐당 타임 슬라이스의 크기는 얼마로 해야 하는가?
- 기아를 피하고 변화된 행동을 반영하기 위하여 얼마나
자주 우선순위가 상향 조정되어야 하는가?

• 쉽게 대답할 수 없고, 워크로드에 대해 충분히 경험하고 계속 조정하면서 균형점을 찾아야 한다.
  • Solaris MLFQ 구현, 프로세스의 우선순위가 어떻게 변하는지, 타임 슬라이스의 길이는 얼마인지, 작업 우선순위는 얼마나 자주 상향되는지 테이블을 제공한다.
  • 다른 MLFQ 구현에서는 수학 공식을 사용(감쇠-사용, decay-usage)하여 우선순위를 조정한다.

요약

1. Priority(A) > Priority(B) 이면, A가 실행된다.
2. Priority(A) = Priority(B) 이면, A와 B는 RR 방식으로 실행된다.
3. 작업이 시스템에 들어가면 최상위 큐에 배치된다.
4. 작업이 지정된 단계에서 배정받은 시간을 소진하면 작업의 우선순위는 감소한다.
5. 일정 주기 S가 지난 후, 시스템의 모든 작업을 최상위 큐로 이동시킨다.

참고자료

• 운영체제: 아주 쉬운 세 가지 이야기