💿

05 : Multi-Level Feedback Queue

course

last review

2023/04/10

mastery

intermediate

progress

pending

date

2023/03/16

4 more properties

Previous chapter

04 : CPU Scheduling

Main Question : Scheduling without Information

Basic Rules

Attempt 1 : Change Priority

example1 : One long workload

example2 : with short jobs

How about I/O?

Problems with current MLFQ

Attempt 2 : Priority Boost

Attempt 3 : Better Accounting

Another

Main Question : Scheduling without Information

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

짧은 작업을 먼저 실행시켜 반환시간을 최적화한다.

SJF나 STCF는 작업 실행시간 정보를 필요로 하지만, 운영체제는 이 실행시간을 알 수 없다.

대화형 사용자에게 나은 경험을 위해 응답시간을 최적화한다.

RR은 응답시간은 단축시키지만 반환시간은 최악이다.

즉, 프로세스에 대한 정보 없이 이런 두가지 문제를 모두 만족할 수 있는 스케줄러는 어떤 것이 있는가?

작업의 실행시간에 대한 선행 정보 없이 대화형 작업의 응답 시간을 최소화하고 동시에 반환시간을 최소화하는 스케줄러를 어떻게 설계할 수 있는가?

Basic Rules

MLFQ는 여러개의 큐로 구성되며, 각각 다른 우선순위(priority level)가 배정된다.

실행 준비가 된 프로세스는 이 중 하나의 큐에 존재한다.

즉, 높은 우선순위 큐에 존재하는 작업이 선택되는 방식이다.

•

큐에는 둘 이상의 작업이 존재할 수 있다. 이때 두 작업 사이에는 RR방식이 적용된다.

MLFQ의 핵심은 우선순위를 정하는 방식이다.

•

키보드 입력을 기다리며 반복적으로 CPU를 양보한다면 해당 작업의 우선순위를 높게 유지한다.

•

긴 시간동안 CPU를 집중적으로 갈구면 MLFQ는 우선순위를 낮춘다.

우리는 위 작업의 특성을 다음과 같이 해석할 수 있다.

•

I/O-bound jobs

◦

Interactive and short-running

•

CPU-bound jobs

◦

compute intensive and longer-running

작업이 진행되는 동안 해당 작업의 과거의 정보를 얻고, 이 정보를 이용해 미래 행동을 예측하는 방식이 MLFQ이다.

MLFQ의 기본 규칙은 다음과 같다.

Priority(A) > Priority(B) 이면, A가 우선적으로 실행된다. (B는 실행되지 않는다.)

Priority(A) = Priority(B) 이면, A와 B는 RR방식으로 실행된다.

그러나 사소한(?) 문제가 생긴다.

다음과 같이 큐가 배치되었을 경우, A와 B가 가장 우선순위가 높으므로 A와 B가 RR로 돌아갈 것이며, C와 D는 영영 실행되지 않는다. 어떻게 이런 일이!!!

다행히도 앞에서 말했던 것 처럼 작업의 우선순위는 고정되지 않는다. 작업의 우선순위가 어떻게 바뀌는지 이제부터 알아보도록 하자.

Attempt 1 : Change Priority

MLFQ의 핵심은 우선순위를 정하는 방식이다.

•

키보드 입력을 기다리며 반복적으로 CPU를 양보한다면 해당 작업의 우선순위를 높게 유지한다.

•

긴 시간동안 CPU를 집중적으로 갈구면 MLFQ는 우선순위를 낮춘다.

우리는 위 작업의 특성을 다음과 같이 해석할 수 있다.

•

I/O-bound jobs

◦

Interactive and short-running

•

CPU-bound jobs

◦

compute intensive and longer-running

위 특성을 이용해서 우언순위 조정 알고리즘을 다시 짜보도록 하자.

작업이 시스템에 진입하면, 가장 높은 우선순위, 즉 맨 위 큐에 놓여진다.

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

example1 : One long workload

길 실행시간을 가진 작업이 도착했을 때 어떤 일이 일어나는지 알아보자.

프로세스는 우선순위 Q2로 진입한다. 10msec 타임슬라이스를 모두 소진했으므로, Q1으로 강등당한다. 다시 하나의 타임슬라이스를 모두 소진한 후, Q0로 최하위 큐까지 강등당한 뒤, 이후에는 계속 Q0에 머무르게 된다.

example2 : with short jobs

A는 오래 실행되는 CPU-bound job이고, B는 짧은 I/O-bound job이다. A는 얼마동안 이미 실행한 상태이며, B는 이제 막 도착한 상태이다.

T=200일 때, A는 최하위 티어의 큐에서 실행되고, B는 방금 도착했기 때문에 최상위 티어의 큐로 배치된다. 실행시간이 짧기 때문에 B는 두번의 타임슬라이스 슬롯을 모두 소모하고 하위티어로 강등되기 전에 종료된다. 이후 A는 계속 실행된다.

→ MLFQ는 작업이 짧은 작업인지 긴 작업인지 알 수 없으므로, 일단 들어오는 모든 작업의 우선순위를 높인다.

•

만약 진짜 짧은 작업이라면, 빨리 실행되고 바로 종료된다.

•

긴 작업이라면 천천히 아래 큐로 이동하게 되고 스스로 긴 배치형 작업이라는 걸 증명하는 꼴이다.

이런 식으로 MLFQ는 SJF를 흉내낼 수 있다.

How about I/O?

B는 I/O-bound job으로 입출력을 수행하기 전에 1msec만 실행된다. A는 CPU-bound job으로 B와 경쟁하는 상태이다.

Problems with current MLFQ

기아 상태의 발생

시스템의 한 구간에 너무 많은 I/O-bound job이 존재하면 그들이 모든 CPU시간을 소모하게 되며, 저티어 큐에 있는 작업은 여전히 시간을 배정받지 못할 것이다.

악용가능성

프로그래머가 타임슬라이스의 99%까지만 실행하고 CPU를 양도한다면 CPU를 독점할 수 있게 된다.

티어 승급의 부재

CPU-bound job이 I/O-bound job으로 바뀔 수 있다. 지금 상태의 MLFQ는 이때 티어를 다시 올리는 기능이 없다.

Attempt 2 : Priority Boost

CPU 위주 작업이 조금이라도 진행하는 것을 보장하기 위해서 다음과 같은 규칙을 새로 만들 수 있다.

다음은 규칙 5에 대한 설명이다.

일정 기간 S가 지나면, 시스템의 모든 작업을 최상위 큐로 이동시킨다.

규칙 5는 놀랍게도! 문제1과 문제3을 동시에 해결한다.

프로세스의 기아 현상을 방지한다.

최상위 큐에 존재하는 동안에는 다른 작업들과 RR방식으로 CPU를 공유한다.

CPU바운드 작업이 IO바운드 작업으로 바뀔 경우 우선순위 상향을 통해 변경된 특성에 맞출 수 있다.

왼쪽은 우선순위 부스팅이 적용되지 않을 경우, 오른쪽은 적용될 경우의 그림이다.

다만 S의 값을 적절히 결정해야하며, S값은 정확한 공식이 없다. 이러한 종류의 값을 부두상수(voo-doo constants) 라고 부른다.

너무 크면 긴 실행시간을 가진 작업이 여전히 굶을 수 있으며, 너무 작으면 대화형 작업이 적절한 양의 CPU 시간을 사용할 수 없게 된다.

Attempt 3 : Better Accounting

문제2를 해결하기 위해서는 어떻게 해야할까?

규칙4는 스케쥴러에서 작업이 실행될때에만 해당 시간이 타임슬라이스의 threshold를 넘는지 확인해왔다. 이 과정을 더 확장해서 CPU 총 사용시간을 측정하는 방식으로 바꿔보자.

규칙4-a,b를 다음과 같이 통합한다.

주어진 단계에서 시간 할당량을 모두 소진하면 우선순위는 낮아진다. CPU의 양도 여부는 따지지 않는다.

Another

Next chapter

06 : Multiprocessor Scheduling