스케줄링 중 가장 잘 알려진 방법 중 하나인 다중 피드백 대기열 MLFQ:The Multi-Level Feedback Queue에 대해 알아보자
MLFQ는 작업이 단계별로 작동하며, 따라서 '예측' 가능할 때 작동한다. MLFQ가 해결하려는 문제는 두가지이다.
첫 번째, 회전 시간(turnaround time)을 최적화 하려한다. 이것은 더 짧은 작업을 먼저 실행함으로써 이룰 수 있지만, OS는 작업의 길이를 알지 못한다.
두 번째, 응답 시간(response time)을 최적화한다. RR과 같은 방법으로 실현할 수 있지만, 이것은 회전시간을 증가시킨다.
우리는 프로세스에 대해 아무것도 모르는데 이런 목표를 달성할 수 있는 스케줄러를 구축할 수 있을까?
Basic Rules 기본 규칙
MLFQ의 기본 알고리즘에 대해 알아보자
MLFQ는 우선순위가 있는 여러개의 Queue를 갖는다. 실행 준비가 된 프로세스는 Queue에 있다.
MLFQ는 어떤 작업이 실행될지 정하기 위해 우선순위를 사용한다. 더 높은 우선 순위를 가진 작업부터 실행하며, 하나의 Queue에 여러 작업이 있을 수 있으므로 동일한 우선순위도 가질 수 있다. 같은 우선순위의 작업들간에는 RR알고리즘을 사용한다. 따라서 MLFQ 스케줄링의 두가지 기본 규칙은 다음과 같다.
- 작업 우선순위 순으로 실행
- 우선순위가 같다면 RR로 실행
MLFQ의 핵심은 스케줄러가 우선순위를 어떻게 설정하는지에 달렸다. 각 작업에 고정된 우선순위를 부여하는 대신, 관찰된 동작에 따라 작업의 우선순위를 변경한다. 예를 들어 잦은 I/O로 CPU를 많이 반납하면, 우선순위를 높이고, CPU를 오래 쓰면 우선순위를 낮춘다.
아래 사진을 통해 MLFQ의 구조를 시각적으로 확인 할 수 있다. MLFQ는 프로세스의 행동을 보고 우선순위를 변경한다. 만약 우선순위의 변경이 없다면, A와 B가 RR을 통해 완료되기 전에는 C와 D는 실행되지 않고 응답 시간이 매우 나빠질 것이다.
How To Change Priority 우선 순위 변경 방법
MLFQ가 우선순위를 변경하기 위해 작업부하(workload)를 고려해야한다. 즉, 짧게 짧게 실행되는(CPU 반납이 잦은) 상호작용적인 작업인지, 응답 시간이 중요하지 않고, CPU시간이 많이 필요한 작업인지를 고려해야한다.
이를 위해 작업의 할당(allotment)이라는 개념이 필요하다. 할당은 스케줄러가 우선순위를 낮추기 전에 작업이 특정 우선 순위 레벨에서 사용할 수 있는 시간이다.
새로운 MLFQ 규칙을 살펴보자
- 작업이 시스템에 들어오면 가장 높은 우선순위에 배치된다.
- 작업이 실행중에 할당을 모두 사용하면 우선순위가 낮아진다.
- 작업이 할당을 모두 사용하기 전에 CPU를 반납하면 우선순위 수준이 유지된다.
아래 사진은 CPU를 오래 쓰는 작업의 예시이다. 높은 우선순위(Q2)로 들어와 일정시간(할당)뒤에 우선순위가 내려가고, 가장 낮은 우선순위에서 작업이 완료된다.
아래 사진은 CPU를 오래쓰는 작업인 A와 상호 작용 작업인 B를 나타낸다.
왼쪽은 A,B가 할당을 사용후 우선순위가 내려가며 실행되는 상황이며,
오른쪽은 B가 입출력을 많이 사용하며 우선순위를 유지하는 상황이다.
Problems With Our Current MLFQ MLFQ의 문제
MLFQ에는 몇 가지 문제가 있다.
첫 번째, 기아(starvation) 문제가 있다. 시스템에 너무 많은 대화형 작업이 있다면, 이러한 작업들은 모두 CPU 시간을 소비하여 장기 실행 작업은 CPU시간을 받지 못할 수 있다.
두 번째, 사용자가 프로그램을 작성하여 스케줄러를 속일 수 있다. 할당을 99% 정도 사용한 후에 I/O 작업을 만들어 CPU 사용을 독점할 수 있다.
세 번째, 프로그램이 시간이 지남에 따라 행동을 변경할 수 있다. CPU 중심적인 작업이 대화형으로 전환될 수 있다. 현재는 운이 없어서 다른 대화형과 같이 처리되지 않을 수 있다.
The Priority Boost 우선 순위 부스팅
규칙을 변경하여 기아(starvation)문제를 해결해 보겠다. 간단한 아이디어는 주기적으로 모든 작업의 우선 순위를 높이는 것이다.
- 어떤 시간 간격 S 후, 시스템 내 모든 작업을 가장 높은 우선 순위 큐로 이동한다.
이 규칙으로 두 가지 문제를 동시에 해결할 수 있다. 1. 최상위 큐에 CPU 중심 작업이 들어가면 다른 작업과 같이 RR로 CPU를 공유하기에 기아문제가 해결된다. 2.CPU 중심 작업이 대화형으로 전환되었을 때 스케줄러가 올바르게 처리한다.
아래 사진의 왼쪽은 Priority Boost가 없는 상태, 오른쪽은 있는 상태이다.
시간 상수 S는 어떻게 설정해야 할까? 너무 높게 설정하면 긴 작업이 기아 상태에 빠지고, 너무 낮게 설정하면 대화형 작업이 CPU를 너무 적게 받을 수 있다. 따라서 적절한 값으로 설정해야한다.
이런 상수 S나 timeslice를 부두상수(voo-doo constants)라고 한다.
되도록 이런 상수가 나오지 않게 프로그램을 설계하는 것이 가장 좋으며,
불가피하게 이런 상수를 적절한 값으로 설정해야하는 상황이 나온다면,
과거의 레퍼런스를 참고하거나 실험적으로 결정해야한다.Better Accounting 더 나은 계산
스케줄러를 조작하는 것은 어떻게 방지할 수 있을까?
해결 책은 MLFQ의 각 수준에서 CPU시간을 더 잘 계산하는 것이다. I/O 수행 시 할당을 초기화하는 대신 계속 추적하는 것이다. 이전에 정했던 규칙(할당 소모시 우선순위 감소,할당 소모 전 CPU 반납시 우선순위 유지)을 변경하여 해결할 수 있다.
- CPU 반납과 관계 없이, 할당 소모시 우선순위가 낮아진다.
아래 사진은 예시이다.
왼쪽은 할당 소모 전 I/O를 하여 우선순위를 유지시키는 상황이다.(부당 독점)
오른쪽은 I/O를 하여도 주어진 할당을 소모하면 우선순위가 내려가는 상황이다.
Tuning MLFQ And Other Issues MLFQ 조정 및 기타 문제
MLFQ를 세부 조정하기 위한 고려 사항들이 있다. 하나는 스케쥴러를 매개변수화 하는 것이다. 예를 들어 Queue는 몇개나 있어야 할지, 각 Queue 당 시간 조각은 얼마나 커야할지, 할당은 얼마여야하는지, 어떻게 우선 순위를 주기적으로 높이며 기아를 피할지 등이다.
예를 들어 MLFQ에서 Queue의 우선순위 마다 시간 조각의 길이를 다르게 한다. 높은 우선 순위 Queue는 대화형 작업으로 구성되기에 짧은 시간 조각을 주로 사용하며, 낮은 우선 순위 Queue는 CPU에 바운드 되는 장기 실행 작업을 포함하므로 더 긴 시간조각을 사용한다.
Solaris MLFQ 구현인 Time Sharing 스케줄링 클래스는 구성이 특히 간단하다. 이는 프로세스의 우선순위 변경 추세, 시간조각의 길이, 우선 순위 상승 타이밍 등을 결정하는 테이블을 제공하며 이 테이블을 수정하여 스케줄러의 동작을 다르게 만들 수 있다. 이 테이블의 기본 값은 60개의 Queue이며, 우선순위가 낮아지며 시간조각의 길이를 서서히 증가시킨다.
많은 스케줄러에서 만날 수 있는 몇가지 다른 기능이 있다. 예를 들어, 일부는 운영 체제 작업을 가장 높은 우선 순위에 둔다. 따라서 일반적인 사용자 작업은 가장 높은 우선 순위를 얻을 수 없다. 일부는 우선 순위 설정에 사용자의 조언을 허락한다. 사용자가 명령어를 사용하여 작업의 우선순위를 바꿀 수 있다.
규칙 정리
- 우선 순위 높은 순으로 실행
- 우선 순위 같다면 시간조각을 사용해 RR방식으로 실행
- 작업이 시스템에 들어오면, 가장 상위 큐(가장 높은 우선 순위)에 배치
- CPU 반납 여부와 상관 없이 할당 소모시 우선 순위 하락
- 일정 시간 S후, 시스템의 모든 작업을 최상위 큐로 이동
