ostep / 가상화 / CPU / MLFQ (한글판 11장, 영문판 8장)

들어가며

이번 장에서는 멀티 레벨 피드백 큐(MLFQ, Multi-Level Feedback Queue)에 대해서 다룹니다.
이전 장에서 다룬 내용 중 이번 장에서 가장 중요한 내용 2가지를 꼽자면 다음과 같습니다.
- 반환 시간을 최적화하기 위해서는 짧은 작업을 먼저 실행시켜야 한다.
  - 평균적으로 대기하는 작업 수를 최소화해야 해서 그렇습니다.
  - 연관 개념: SJF, STCF 알고리즘
- 응답 시간이 짧아지면 짧아질수록 반환 시간이 길어진다.
  - 평균적으로 대기하는 작업 수가 늘어나서 그렇습니다.
  - 연관 개념: 라운드 로빈 알고리즘, 타임 슬라이스
MLFQ 알고리즘은 이전 장에서 다루었던 가정 중 마지막 가정인 "작업의 시간이 사전에 알려져 있다"마저 없앤 현실적인 가정 하에 동작합니다. 현대 운영체제에서 적용하는 알고리즘의 뼈대가 됩니다.
Ostep에서 이 장을 진행하는 구성은 다음과 같습니다.
- 먼저 특정 시각에 MLFQ가 어떻게 동작하는지를 먼저 기술합니다. (Multi, Level, Queue)
- 그리고 시간에 따라 피드백을 받으며 조정하는 부분을 기술합니다. (Feedback)

개요

MLFQ 알고리즘이 달성하고자 하는 목표는 다음과 같습니다.
- 사용자가 실시간으로 기다리는 대화형 작업의 경우 응답 시간을 최소화
- 이외의 작업의 경우 반환 시간을 최소화
이를 어렵게 하는 난관은 다음과 같습니다.
- 사용자 작업의 소요 시간 및 특성을 사전에 알 수 없습니다.
- 응답 시간을 최적화할 경우 반환 시간이 안 좋아지는 트레이드오프가 있습니다.
이를 해결하기 위한 전략은 다음과 같습니다.
- 작업이 지금까지 보여준 과거를 통해서 미래를 예측한다.

기본적인 모델

먼저 MLFQ가 특정 시각에 어떻게 동작하는지 살펴보겠습니다.

먼저 MLFQ의 M, L, Q에 해당되는 부분입니다.
- Queue: 작업은 큐에서 대기합니다.
- Multi: 그런데 큐를 여러 개를 둡니다.
- Level: 그런데 그 여러 개의 큐들의 우선순위에 차등을 둡니다.
우선 순위에 따른 동작은 다음과 같습니다.
- 규칙 1: 우선 순위가 높은 작업이 먼저 실행된다.
- 규칙 2: 우선 순위가 같은 작업은 라운드 로빈 알고리즘으로 실행된다.
이를 구현하기 위해서는 다음과 같습니다.
- 우선 순위가 가장 높은 큐에 작업이 있으면, 라운드 로빈 알고리즘에 따라 다음 실행할 작업을 결정한다.
- 우선 순위가 가장 높은 큐에 작업이 없으면, 다음 우선순위 큐로 넘어간다.
- 우선 순위가 가장 낮은 큐까지 반복한다.
시간에 따른 변화를 고려한 모델 (mk1)
특정 시각으로 시간을 고정할 경우 작업마다 (과거에 실행된 것을 바탕으로) 우선 순위가 고정되어 있습니다. 하지만 특정 시각의 동작만 가지고는 초기에 정보가 없을 때 우선 순위를 어떻게 설정해야 하는지, 또 어떻게 변하는지에 대하는지 이해할 수 없습니다. 따라서 이 섹션에서는 시간에 따른 변화를 고려해보겠습니다.
일단 규칙부터 보여드리겠습니다.
- 규칙 3: 모든 작업은 초기에는 가장 높은 우선순위로 실행된다.
  - 다시 말해 처음 생성된 작업은 우선순위가 가장 높은 큐에 대기시킵니다.
- 규칙 4a: 주어진 타임 슬라이스를 모두 사용하면 우선순위를 한 단계 강등시킨다.
  - 즉, 우선 순위가 한 단계 낮은 큐에서 대기시킵니다.
- 규칙 4b: 주어진 타임슬라이스를 모두 사용하지 않으면 우선순위를 유지시킨다.
  - 즉, 같은 큐에서 대기시킵니다.
ostep에서 Q2 > Q1 > Q0인 3개의 큐를 둔 예시를 설명하고 있습니다. 책을 보시는 게 좋을 것 같아 여기서는 결론만 정리하겠습니다.
- 실행 시간에 따른 분석
  - 긴 실행 시간을 가진 작업: Q2 -> Q1 -> Q0로 떨어져서 낮은 우선 순위로 실행
  - 짧은 실행시간을 가진 작업: Q2, Q1 등 높은 우선 순위에서 실행 후 완료
  - 짧은 실행 시간을 가진 작업을 더 높은 우선순위로 실행시켜 반환 시간을 최적화하는 것을 알 수 있습니다.
- 입출력 작업: 주어진 타임 슬라이스가 끝나기 전에 입출력을 수행한다면 우선 순위 유지한다고 가정
  - 대화형 작업의 경우 타임 슬라이스가 종료되기 전에 입출력을 수행해 높은 우선 순위로 실행되어 응답 시간을 최적화할 수 있습니다.
mk1의 문제점
기아 상태(starvation)
- 대화형 작업 여러 개가 존재한다면, 높은 우선순위의 큐만 실행하느라 낮은 우선순위 큐에 있는 CPU 위주 작업은 계속 실행되지 못하는 가능성이 있습니다.
높은 우선순위를 유지하는 꼼수 존재
- CPU를 오래 사용하는 작업이더라도 타임 슬라이스가 끝나기 직전에 입출력을 수행한다면 높은 우선 순위를 유지할 수 있습니다.
  - 따라서 이 문제를 해결하기 위해서 타임 슬라이스 사용 여부의 boolean이 아닌, 타임 슬라이스의 얼마가 남아있는지를 저장해야 합니다.
시간에 따른 작업의 특성 변화 고려 못함
- CPU 작업이 대화형 작업으로 변화할 수 있지만, mk1에서는 우선 순위가 내려간 작업은 다시 올라오지 않기 때문에 대화형 작업의 응답 시간이 길어질 가능성이 있습니다.

시간에 따른 변화를 고려한 모델 (mk2)

꼼수 문제를 해결하기 위해서 4번 규칙을 보완하겠습니다.
- 규칙 4: 주어진 타임 슬라이스를 모두 사용하면 우선순위를 한 단계 강등시킨다. 단, CPU를 몇 번 양도하였는지와 상관없이 시간 할당량을 소진하는 것으로 강등 여부를 판단한다.
  - 즉, 남은 시간을 확인해서 0이라면
    우선 순위가 한 단계 낮은 큐에서 대기시킵니다. 반면
    0이 아니라면 같은 큐에서 대기시키되, 남은 시간을 저장하여 다음 실행 시에는 타임 슬라이스 시간이 아닌 남은 시간동안만 실행되도록 합니다.
기아 상태 문제와 작업 특성 변화 문제를 해결하기 위해서 규칙을 하나 더 만들겠습니다.
- 규칙 5: 일정 시간 S가 지나면 모든 작업을 최상위 큐로 이동시킨다.

MLFQ의 조정과 다른 쟁점들

MLFQ에는 정확하게 결정하기 위해서는 흑마법이 필요해 보이는 "부두 상수"들이 몇 가지 있습니다.

큐의 개수
큐 별 타임 슬라이스 길이
- 우선 순위가 높으면 대개 타임 슬라이스가 짧습니다. 대화형 작업이 많기 때문입니다. (<10ms)
- 우선 순위가 낮으면 응답 시간보다는 반환 시간을 최적화하기 위해서 타임 슬라이스가 깁니다.
ostep에서 다룬 것과 같이 정확한 규칙이 아닌, 수학 공식을 사용하여 우선순위를 조정하기도 합니다.

또한 스케줄러는 다른 기능을 제공하기도 합니다. 사용자 작업에 대해서 우선순위를 정하게 해주는 nice와 같은 기능이 그 예입니다.

정리

Ostep에서 다룬 MLFQ 알고리즘의 경우 다음 5가지 규칙으로 정리할 수 있습니다.

규칙 1: 우선 순위가 높은 작업이 먼저 실행된다.
규칙 2: 우선 순위가 같은 작업은 라운드 로빈 알고리즘으로 실행된다.
규칙 3: 모든 작업은 초기에는 가장 높은 우선순위로 실행된다.
규칙 4: 주어진 타임 슬라이스를 모두 사용하면 우선순위를 한 단계 강등시킨다. 단, CPU를 몇 번 양도하였는지와 상관없이 시간 할당량을 소진하는 것으로 강등 여부를 판단한다.
규칙 5: 일정 시간 S가 지나면 모든 작업을 최상위 큐로 이동시킨다.

그 결과로 MLFQ는 반환 시간과 응답 시간을 모두 최적화합니다. 짧게 실행되는 작업은 SJF/STCF처럼 처리해 전반적인 성능을 개선시키고, 오래 실행되는 CPU 작업의 경우 공정하게 실행되도록 기아 상태를 방지하고 조금이라도 진행되게 합니다. 이런 이유로 많은 운영체제에서 MLFQ를 기본 스케줄러로 사용하고 있습니다.