[ OS ] 4. Multi-Level Feedback Queue

들어가며

지금까지 여러가지 스케줄링 알고리즘들을 알아봤었다. 그런데 마지막 가정인, 작업에 대한 사전 지식이 없다면 어떤 방식으로 스케줄링을 해야 할까? 이 글에서는 마지막 가정을 해결하는 스케줄링 방식인 MLFQ에 대해 알아보려 한다.

스케줄링 평가 항목(Scheduling Metrics)

추가적인 스케줄링 평가 항목을 알아보자.

Turnaround time(반환 시간)

• OS는 보편적으로 프로세스가 얼마나 걸릴지 모른다.

Response time(응답 시간)

• OS는 유저 상호적으로 시스템을 만드는데 책임이 있다.

문제

지금까지의 스케줄러는 3가지 문제가 있었다.

• 상호적인 작업 응답 시간 최소화
• 반환 시간 최소화
• 작업에 대한 사전 지식 없이

이 3가지를 동시에 만족하는 스케줄러가 있다. 바로 MLFQ이다.

Multi-Level Feedback Queue(MLFQ)

MLFQ(Multi-Level Feedback Queue)는 프로세스 스케줄링 알고리즘으로, 여러 개의 큐를 사용하여 프로세스의 우선순위를 동적으로 조정한다. 이 알고리즘은 프로세스의 특성을 학습하고 그에 따라 우선순위를 변경함으로써, 시스템의 전반적인 성능을 향상시키는 것을 목표로 한다.

MLFQ의 주요 특징

• 여러 개의 우선순위 큐를 사용
• 프로세스의 행동에 따라 우선순위 동적 조정
• CPU 집중 프로세스와 I/O 집중 프로세스를 효과적으로 구분
• 응답 시간과 처리량 사이의 균형 유지

기본 규칙

1. 만약 Priority(A) > Priority(B) 일 때, A가 실행,B는 실행되지 않는다.
2. 만약 Priority(A) = Priority(B) 일 때, A와 B는 RR로 실행된다.
3. 작업이 시스템에 들어가면 최상위 큐에 배치된다.
4. a: 주어진 타임 슬라이스를 모두 사용하면 우선순위는 낮아진다. 즉, 한 단계 아래 큐로 이동한다.
5. b: 타임 슬라이스를 소진하기 전에 CPU를 양도하면 같은 우선순위를 유지한다.

기존 규칙의 문제

Starvation

• 만약 시스템이 너무 많은 작업이 있을 경우 할당받지 못하는 작업이 있을 수 있다.

Gaming the scheduler

• 타임 슬라이스(time slice)가 끝나기 전에 I/O 작업을 요청하는 경우, 우선순위가 낮아지지 않는다.

Priority Boost: Starvation, Changing behavior에 대한 해결책

• 주기적으로 모든 시스템에 있는 작업들의 우선순위를 끌어올린다.(규칙 추가)
• starvation, changing behavior에 대한 문제해결을 할 수 있다.

1. 만약 Priority(A) > Priority(B) 일 때, A가 실행,B는 실행되지 않는다.
2. 만약 Priority(A) = Priority(B) 일 때, A와 B는 RR로 실행된다.
3. 작업이 시스템에 들어가면 최상위 큐에 배치된다.
4. a: 주어진 타임 슬라이스를 모두 사용하면 우선순위는 낮아진다. 즉, 한 단계 아래 큐로 이동한다.
5. b: 타임 슬라이스를 소진하기 전에 CPU를 양도하면 같은 우선순위를 유지한다.
6. 일정 주기 S 이후, 모든 작업들을 시스템의 최상위 큐에 이동시킨다.

Better Acounting: gaming the scheduler 해결책

• 규칙 4a와 4b를 수정

1. 만약 Priority(A) > Priority(B) 일 때, A가 실행,B는 실행되지 않는다.
2. 만약 Priority(A) = Priority(B) 일 때, A와 B는 RR로 실행된다.
3. 작업이 시스템에 들어가면 최상위 큐에 배치된다.
4. 작업이 지정된 단계에서 배정받은 시간을 소진하면(CPU를 포기한 횟수와 상관없이), 작업의 우선순위는 감소한다.(즉, 한 단계 아래 큐로 이동한다.)
5. 일정 주기 S 이후, 모든 작업들을 시스템의 최상위 큐에 이동시킨다.

MLFQ의 최종 규칙

1. 만약 Priority(A) > Priority(B) 일 때, A가 실행,B는 실행되지 않는다.
2. 만약 Priority(A) = Priority(B) 일 때, A와 B는 RR로 실행된다.
3. 작업이 시스템에 들어가면 최상위 큐에 배치된다.
4. 작업이 지정된 단계에서 배정받은 시간을 소진하면(CPU를 포기한 횟수와 상관없이), 작업의 우선순위는 감소한다.(즉, 한 단계 아래 큐로 이동한다.)
5. 일정 주기 S 이후, 모든 작업들을 시스템의 최상위 큐에 이동시킨다.