[OS] MLFQ (Multi-Level Feedback Queue)

반환시간, 응답시간 둘 다 최소화하고 싶음

MLFQ 설명 및 규칙 + 예제 3개

• 여러 개의 큐로 구성
• 각 큐마다 우선순위가 부여됨
• 높은 우선순위 큐의 작업이 먼저 선택됨
• 우선 순위가 높은 프로세스 작업이, 우선순위 높은 큐에 들어감
• 하나의 큐 안에서는 동일한 우선순위로, RR 방식으로 동작함

그러면 낮은 우선순위 큐에 들은 프로세스는 기아 상태 ?

우선순위는 어떻게 바꿀래 ?

예제 1번

3개의 멀티 큐가 있을 때,

1. A 작업이 들어오면 룰3에 의해 젤 높은 우선순위
2. 타임슬라이스 끝나면 Context Switch되면서 다음 단계로 내려감
   근데, 같은 PID면 Context Switch 생략, 우선순위만 낮아짐
3. 또 타임 슬라이스 지나서, 우선순위 낮아짐
   제일 낮은 우선순위 큐에서도 타임 슬라이스는 계속 동작하지만, Context Switch X

예제 2번

1. 제일 우선순위 낮은 A가 동작 중에 B가 들어옴
2. 우선순위 높은 B 작업으로 Context Switch 동작, B 시작
3. B가 작업 중, 타임 슬라이스 종료 → 우선순위 한 단계 낮아짐
4. 3번 반복, B 작업 끝 (20ms)

예제 3번

1. B는 1ms 동작 후, I/O 작업을 함

2. I/O 작업에 들어가면 해당 프로세스는 CPU를 포기함

   → Rule 4b 규칙에 의해 타임슬라이스 안에 CPU 포기 시, 우선순위 유지

3. 계속 Q2 높은 우선순위 큐에 머물게 됨

MLFQ 장단점

MLFQ 장점

I/O 작업을 많이 하면

RR 라운드 로빈도 짧아 응답시간이 짧음

T turnaround도 짧음

MLFQ 단점

• 기아 상태
  대화형 작업이 항상 높은 우선순위를 차지하기 때문에 낮은 우선순위 큐 애들은 기아가 됨
• 스케줄러 어장관리 (갖고놈)
  99% 때 I/O 작업 들어가면 우선순위 유지됨
• 실행 중 특성 변화 대처에 불가능함
  → CPU 위주 작업이 대화형 작업이 될 수 있음, 그래도 대우는 CPU 위주 작업

MLFQ 개선

우선순위 상향 조정 (Priority Boost)

Rule 5: 일정 시간 S가 지나면, 모든 작업을 최상위 큐로 이동시킴

결과

• 기아 상태 해결 → O
• 스케줄러 어장관리 → X
• 특성 변화 → O

그럼 S는 어떻게 설정할래 ?

S가 길면, CPU 위주 작업이 불리하고, 대화형이 유리

S가 짧으면, CPU 위주 작업이 유리, 대화형이 불리

더 나은 시간 측정 (Better Accounting)

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

I/O 작업이든 아니든 전부 타임 슬라이스 끝나면 우선순위를 낮춤

결과

• 기아 상태 해결 → O
• 스케줄러 어장관리 → O
• 특성 변화 → O

스케줄러 어장관리도 해결함

MLFQ 튜닝

조정할 수 있는 요소

• 큐의 개수
• 큐 당 타임 슬라이스의 크기
• 우선순위 상향 조정 주기 (S)

큐마다 다른 타임 슬라이스

우선순위가 높은 큐는 타임 슬라이스를 적게 줌

타임 슬라이스가 길 수록, Context Switch가 적게 발생함

정리

대화형 작업을 위한 빠른 반응 시간과
CPU 위주 작업을 위한 반환시간 모두 고려함

Multi-Level: 서로 다른 특성을 가진 여러 개의 큐

Feedback: 프로세스 실행 특성을 관찰하여 큐 이동에 반영

MLFQ 규칙 5가지

1. 우선 순위가 높은 큐의 프로세스가 먼저 실행됨
2. 하나의 큐 안에서는 우선순위가 같음, RR 방식으로 타임 슬라이스에 따라 진행
3. 새로운 작업은 가장 높은 우선순위에서 시작
4. 현재 큐에서 할당 받은 시간을 모두 소모하면 우선순위 하향
5. 일정 시간 S가 지나면 모든 작업이 최고 순위 큐로 이동

퀴즈

priority boost가 적용되면 Gantt chart는 어떻게 바뀌는가? (S = 100)

1. S 100에서 A, B 모두 최상위 큐로 올라감
2. 이후 A작업 먼저 실행 → Q1으로 내려옴
3. B작업 실행 → Q1로 내려옴
4. A 작업 실행 → Q2로 내려옴
5. B 작업 실행 → Q2로 내려옴