[운영체제] MULTI-LEVEL FEEDBACK QUEUE

MLFQ가 해결하고자 하는 기본적인 문제는 두 가지이다.

1. 짧은 작업을 먼저 실행시켜 반환 시간을 최적화하고자 한다.
2. 빠른 응답 시간

그리고 추가로 프로세스에 대한 정보가 없다면 어떻게 스케줄링을 할 것인가

MLFQ

Basic Rules

멀티 레밸 큐란 우선순위별로 큐를 분리한 큐의 집합을 의미한다.

주요한 규칙은 다음과 같다
1. 우선순위가 높은 큐가 최우선으로 실행한다!
2. 우선순위가 같다면 RR 로 실행한다.

그러면 생각이 들 것이다.

우선순위는 무엇을 기준으로 나타내어지는가

보통 IO intensive한 작업을 높은 우선순위로 ( CPU를 자주 포기하는)
CPU intensive 한 작업을 낮은 우선순위로 한다( CPU를 잘 포기하지 않는)

하지만 만약 우선순위의 변동이 없다면 
우선순위가 높은 작업이 끝나지 않는 한 우선순위가 낮은 작업은 실행되지 않을 것이다.

 

 

우선순위 변경

기본적인 MLFQ는 다음과 같은 룰로 우선순위를 변경한다.

1. 시스템에 들어올 때 가장 높은 우선 순위 큐에 배치한다.
2. 할당 받은 타임 슬라이스를 모두 소모하면 우선 순위 감소
3. 시간이 되기 전에 CPU를 포기하면 동일한 우선 순위 유지 
(작업 단위가 짧은 즉 io intensive한 작업은 높은 순위 유지)

이렇게 하는 이유는 MLFQ 가 SJF 와 근사하게 하기 위해서이다.

 

예제 1 : 한 개의 긴 작업을 가진 작업

TMI)

위와 같은 상황이면 Context switch 가 일어나지 않는다.

예 1 + 짧은 작업

SJF 에 근접한 알고리즘이 될 수 있다!!

입출력이 있다면

대화형 작업이 항상 가장 높은 우선 순위를 차지한다!

기본 MLFQ 의 문제점

1. 기아 상태
-> 대화형 작업이 굉장히 많다면... 아무고토 못함

2. 스케줄러 갖고 놀기
-> 타임 슬라이스 끝나기 전에 cpu를 반환하면 높은 우선순위를 가진다는 점 악용

3. 만약 작업의 특성이 cpu intensive -> io intensive 하다면 대처 불가능

기본 MLFQ 개선

S 지나면 최상위 큐로(Priority Boost)

1. 기근 문제와
3. 특성 변화 문제를 대비

일정 시간 S 가 지나면 모든 작업ㅇ르 최상위 큐로 이동하게 한다.

S는 어떤 값으로 하는가

S가 커질수록 cpu intensive 프로세스의 굶는 일이 많아지고
S가 작아질수록: cpu intensive 가 높은 우선순위를 차지하게 될 것

Gaming 방지 ( 갖고 놀기 방지)

현재 단계에서 시간을 모두 소모하면 무조건 우선 순위 감소

MLFQ 튜닝

MLFQ의 변수를 조정할 수 있는 것들은

큐의 수
큐당 타임 슬라이스의 크기
우선 순위 상향 조정 주기가 있다

큐 마다 다른 타임 슬라이스

큐마다 다른 타임 슬라이스를 사용한다.