Multi-level Feedback Queue (Scheduling: Multi-level Feedback Queue)

본 글의 내용은 Operating Systems: Three Easy Pieces의 Scheduling: The Multi-Level Feedback Queue 챕터를 정리한 것입니다.

☑️ 개요

• SJF 혹은 STCF 는 작업에 필요한 시간을 알아야 가능한 스케줄링이기 때문에, 현실적으로 사용하기 어렵고, 응답 시간이 좋은 편이 아니다.

• 그러나 RR 을 사용하기에는 처리 시간을 개선하기가 힘들다.

• 처리 시간과 응답 시간을 동시에 개선하려면 어떤 접근 방식이 필요할까?

☑️ MLFQ 기본 규칙

• Multi-Level Feedback Queue는 과거의 정보로 미래를 예측하는 스케줄링의 대표적인 예시이다.

• MLFQ 에는 우선 순위 레벨에 따른 여러 개의 대기열이 있고, 실행할 준비가 된 작업은 단일 대기열에 존재한다.
  

• 우선 순위가 높은, 즉, 더 높은 레벨의 대기열에 존재하는 작업이 먼저 선택되며,
  만약 같은 레벨의 대기열에 여러 개의 작업이 있다면, RR 스케줄링에 맞게 처리된다.

• 이 우선 순위는 작업이 어떤 동작을 하냐에 따라 달라진다.
  예시로, 입출력 요청을 자주 하는 프로세스의 우선 순위는 유지되며,
  장시간 집중적으로 CPU를 사용하는 프로세스의 우선 순위는 하락한다.

☑️ 우선순위 변경

• 만약 우선순위가 변하지 않는다면 특정 작업은 실행조차 되지 않을 것이다.

• 그래서 우선순위를 동적으로 변경해주어야 하고, 어떤 기준으로 변경할 것인지가 정의되어 있어야 한다.

• 아래와 같은 규칙이 있다고 가정해보자.

  1. 시스템에 들어온 작업은 먼저 우선 순위를 가장 높게 배치한다.
  2. 작업이 전체 타임 슬라이스를 사용하면 우선 순위가 감소한다. (대기열 아래로 이동)
  3. 타임 슬라이스가 끝나기 전에 CPU를 포기하면 우선 순위가 유지된다.

▶️ 예시 1: 오래 실행되는 단일 작업

• 장기간 실행되는 작업이 있다고 가정해보자.

• 가정에 맞게 시스템에 들어간 작업은 가장 높은 우선 순위에 배치된다.

• 위 작업은 타임 슬라이스를 다 사용하는 작업이기 때문에 처음 타임 슬라이스를 모두 사용한 뒤 스케줄러에 의해 우선 순위가 하락한다.

• 타임 슬라이스를 더 사용하여 최하위 우선 순위에 배치된다.

▶️ 예시 2: 짧은 작업과 함께 실행될 때

• 위 예시에 짧은 작업이 추가됐다고 가정해보자.

• 긴 작업은 점점 우선 순위가 하락하고, 짧은 작업은 최고 우선 순위로 시작하여 더 하락하기도 전에 마무리 된다.

• 심지어 긴 작업이 다시 실행되기 전에 연속 두 번의 타임 슬라이스를 사용했다.

• 본 예시는 MLFQ 가 SJF 와 비슷한 역할을 할 수 있음을 보여준다. 어떤 작업이 단기 작업인지 알 수 없기 때문에 우선은 단기 작업일 것이라 가정한다.

▶️ 예시 3: 입출력이 있다면?

• 대화형 작업이 키보드 혹은 마우스 등의 사용자 입력을 기다린다면 많은 I/O를 수행하게 되고, 타임 슬라이스가 완료되기 전에 CPU를 포기하게 된다.

• 그래서 입출력 관련 동작을 하는 작업은 계속해서 우선 순위가 유지되며, 입출력이 발생하는 사이 사이에 장시간 실행되는 작업이 CPU를 사용한다.

⚠️ MLFQ의 문제점

• 만약 우선 순위가 높은 작업이 여러 개 존재한다면, 장시간 실행되는 작업과 같은 우선 순위가 낮은 작업은 실행조차 되지 못한다. (이것을 starvation이라고 한다.)

• 이것을 악용하기 위해 프로그래머가 프로그램을 교묘하게 구성할 수도 있다. 타임 슬라이스가 완료되기 전에 CPU를 포기하게 하거나, 가짜 I/O 작업을 수행한다면 우선 순위가 악용된다.

• 또한 프로그램은 시간이 흐르면서 다른 동작을 하게될 수도 있기 때문에(장시간 실행되다가 대화형으로 변하는 등), 이런 단순한 접근 방식으로는 모든 경우를 커버할 수는 없다.

🔥 우선순위 부스트

• 위에서 언급된 문제를 해결하기 위해 단순하게 일정 주기마다 모든 작업의 우선 순위를 최고 값으로 높일 수도 있다.

• 이것은 starvation을 방지할 수 있고, 동작이 변하는 작업을 적절하게 처리할 수 있다.

• 그렇다면 여기서는 주기를 어느 정도로 잡을 것인가를 생각해봐야 한다. 이것은 미스터리한 값이기 때문에 부두 상수(voo-doo constants)라고도 불렸다.

• 주기를 너무 낮게 설정하면 대화형 작업이 CPU를 제대로 할당받지 못할 수도 있고, 너무 높게 설정하면 다시 starvation이 발생하게 된다.

☑️ 악용 방지

• 이제 해결할 것은 타임 슬라이스 규칙을 악용하려는 접근이다. 타임 슬라이스가 만료되기 전에 CPU를 의도적으로 포기한다면 어떻게 대응해야 할까?

• 이것을 위해 우선 순위 조정에 대한 기준을 조금 수정해야 한다.

  • CPU를 얼마나 포기했냐와 관계 없이, 작업이 할당받은 시간을 모두 사용하면 우선 순위는 감소한다.

• 이 작업에 할당되는 시간은 레벨에 따라 다르도록 조정한다.

• 그럼 타임 슬라이스와 관계 없이, 자신의 레벨에 맞는 시간을 소모하면 우선 순위는 하락한다.

☑️ 기타 고려 사항

• 결론적으로 위와 같은 접근 방식을 실현하려면, 스케줄러를 매개변수화 해야 한다.

• 대기열은 몇 개가 있어야 하는지,
  우선 순위마다 타임 슬라이스가 얼마나 되어야 하는지,
  우선 순위를 높이는 주기는 얼마나 되어야 하는지 모두 깊게 고민해봐야 할 문제이다.

• 이것에 대한 정답은 없으며, Workload(작업)에 대한 경험과 스케줄러 조정을 통해서 밸런스를 맞출 수 있다.

• 일반적으로 우선 순위가 높은 큐에는 짧은 타임 슬라이스를 설정한다. (대화형 작업은 빠르게 스위칭하는 것이 합리적이다.)

• 반면에 낮은 우선 순위 큐에는 긴 타임 슬라이스가 적합하다. (CPU 종속 장기 실행 작업이 포함되므로)

• 예시로 Solaris MLFQ에서는 관리자가 마음대로 설정할 수 있는 테이블을 제공한다.
  (우선 순위 주기, 타임 슬라이스 길이 등을 결정할 수 있는 테이블)
  기본 값으로는 큐의 개수가 60, 타임 슬라이스는 최고 우선 순위에서 20ms, 부스트 주기는 1초다.

• 다른 MLFQ 스케줄러에서는 수학적 공식으로 우선순위를 조정한다. (Epema의 decay-usage 알고리즘 등이 쓰인다.)

• 끝으로, 스케줄러에는 사용자가 손댈 수 없는 영역도 존재한다. 몇몇 스케줄러에서는 OS 작업에 가장 높은 우선 순위를 부여하기 때문에, 사용자가 최고 우선 순위를 사용할 수 없게 한다.

✅ 요약

• MLFQ 동작 과정

  1. 우선 순위가 높은 것이 실행된다.

  2. 우선 순위가 같다면 해당 작업들이 RR 방식으로 실행된다.

  3. 작업이 시스템에 들어오면 최고 우선 순위로 시작한다.

  4. 작업이 CPU를 얼마나 포기하느냐는 중요하지 않고, 레벨 별로 할당된 시간을 사용하면 우선 순위는 하락한다.

  5. 일정 주기가 지나면 모든 작업은 최고 우선 순위 값으로 올라간다.

• MLFQ 는 대화형 작업에서 우수한 성능을 보이며,
  공정성을 높일 수 있기 때문에 BSD UNIX, Windows 등에서 기본 스케줄러로 사용된다.