MLFQ (Multi-Level Feedback Queue)

저번 글에서 FIFO, SJF, STCF, RR에 대해 이야기했습니다.

그런데, 반환시간이랑 응답시간을 둘 다 좋게 만드는 방법이 없을까 고민한 사람이 있었고(By F. Cormato),

MLFQ로 튜링 상을 타셨습니다.

 

기본적인 기계학습의 개념입니다.

여러개의 레벨이 다른 큐(레디 큐)를 이용해(멀티레벨) 과거를 기반으로(피드백) 스케줄링합니다.

 

스케줄링의 규칙이 있습니다.

1. 우선순위가 높은 잡부터 실행

2. 우선순위가 동일하면 라운드 로빈

3. 새로 들어오는 작업은 가장 높은 우선순위를 가지는 큐에 넣음

4a. 어떤 큐에서 스케줄링되고 타임 퀀텀이 끝나면 우선순위가 감소

4b. 스케줄링 되었는데 자기 시간을 다 못썼으면(IO등에 의한 블록 상태) 꺠어났을 때 원래 있던 큐로

 

이 규칙을 기반으로, IO를 자주 하는, 즉 상호작용을 많이 하는 잡은 우선순위가 높게 유지될 것입니다.

아니면, CPU를 많이 쓰는 작업은 우선순위가 낮을 것입니다.

 

프로세스의 우선순위가 계속 바뀌는데, 과거의 행동에 따라 피드백되어 우선순위가 결정됩니다.

 

장점:

- 롱-러닝 잡 끼리는 공평하게 대해줍니다.

- I/O나 짧은 잡의 경우 빠르게 처리됩니다.

 

단점:

- 기아 상태(Starvation), 우선순위가 높은 잡이 너무 많으면 실행이 안되는 잡이 발생합니다.

  => 프라이어티 부스트. 주기적으로 우선순위를 끌어올려서 실행이 되도록 해줍니다.

  => 규칙 5번. 일정 주기가 지나면 시스템의 모든 잡을 최고 프라이어티 큐로 올려준다.

 

- 스케줄러를 속이는 경우,  주어진 시간이 끝나기 직전 Sleep(1)이런 식으로 블럭 상태에 들어가면 우선순위가 유지

  => 규칙 4번 수정-통합. 잡이 주어진 레벨에서 쓴 시간의 총 합이 주어진 타임 퀀텀을 채우면 내려가도록 한다.

 

결과적으로, 상호작용 프로세스도, 긴 길이의 batch 작업도 좋아집니다.

 

1. 우선순위가 높은 잡부터 실행 2. 우선순위가 동일하면 라운드 로빈 3. 새로 들어오는 작업은 가장 높은 우선순위를 가지는 큐에 넣음 4. 잡이 주어진 레벨에서 쓴 시간의 총 합이 주어진 타임 퀀텀을 채우면 내리기 5. 일정 주기가 지나면 시스템의 모든 잡을 최고 프라이어티 큐로 올려줌

 

 

다음 게시글에서 FIFO, STJ, STCF, RR, MLFQ의 레디-큐가 어떻게 바뀌는지,

그리고 평균 반환 시간(ATT)과 평균 응답 시간(ART)을 알아보겠습니다.