운영체제5 - 멀티 레벨 피드백 큐

운영체제를 공부하기 위해 운영체제 아주 쉬운 세 가지 이야기 라는 책을 읽고 공부한 내용을 정리합니다.
잘못되거나 부족한 부분이 있으면 언제든 댓글로 가르침 부탁드립니다.

목차

1. 멀티 레벨 피드백 큐(MLFQ)가 해결하고자 하는 문제
2. MLFQ의 기본 규칙

1. 멀티 레벨 피드백 큐(MLFQ)가 해결하고자 하는 문제

1. 짧은 작업을 먼저 실행시켜 반환 시간 을 최적화 한다.
2. 대화형 사용자에게 응답이 빠른 시스템이라는 느낌을 주기 위해 응답 시간 을 최적화한다.

즉, 반환시간과 응답시간을 모두 최적화하려 한다.

2. MLFQ의 기본 규칙

2.1 MLFQ란?

우선순위가 다른 여러개의 큐로 구성되어 있으며, 각 큐에는 같은 우선순위의 작업이 배정된다.

기본 규칙 2가지는 다음과 같다.

1. 우선순위가 더 높은 큐의 작업이 먼저 실행된다.
2. 우선순위가 같은 큐에 있으면 RR 방식으로 작업이 실행된다.

MLFQ의 핵심은 작업의 우선순위를 어떻게 정하는가 이다. 따라서 이를 어떻게 정하는가에 따라 MLFQ가 결정된다.

2.2 우선순위 변경 방식1

워크로드는 짧은 실행 시간을 갖는 대화형 작업과 많은 CPU 시간을 요구하는 긴 실행시간 작업이 혼재되어 있다. 아래는 이러한 특성을 반영하기 위한 첫번째 우선순위 변경 규칙들이다.

3. 작업이 시스템에 도착하면 가장 높은 우선순위인 맨 윈의 큐에 들어간다.

4. • a 주어진 타임 슬라잇를 모두 사용하면 우선순위가 한 단계 낮은 큐로 이동한다.
5. • b 타임 슬라이스를 소진하기 전에 CPU를 양도하면 같은 우선순위를 유지한다.

6. 현재 방식의 문제점

7. 기아 상태(starvation) 발생 : 시스템에 너무 많은 대화형 작업이 존재하면 실행시간이 긴 작업은 CPU를 할당받지 못한다.

8. 똑똑한 사용자가 자신에게 유리한 작업을 만들 수 있다. : 타임 슬라이스가 끝나기 전에 아무 파일을 대상으로 입출력 요청을 내려, 큐를 유지하는 전략을 사용한다면 가장 높은 우선순위 큐에 계속 머무를 수 있다.

2.3 우선순위 변경 방식2

위와 같은 문제를 해결하기 위해 2가지 변화를 준다. 먼저 4-a와 4-b 대신 새로운 규칙 4번을 만든다.

4. 주어진 단계에서 타임 슬라이스를 소진하면(CPU 양도여부와 관계없이) 우선순위가 낮아진다. (2번 문제점 해결)
5. 일정시간 S가 지나면, 시스템의 모든 작업을 최상위 큐로 이동시킨다. (1번 문제점 해결)

S 값은 너무 길면 starving이 길어지고, 짧으면 대화형 작업에 적절한 cpu를 줄 수 없다. 이렇게 결정하기 힘든 변수를 부두 상수(voo-doo constants) 라고 부른다.

2.4 그밖에 결정 사항들

그밖에도 몇개의 큐가 필요한지, 타임 슬라이스의 크기는 어떻게 할지 등을 결정해야 하기에 많은 try & error 가 필요하다.