OS - 멀티레벨피드백큐(MLFQ)

김인회·2021년 10월 7일
0

OS

목록 보기
3/5

멀티 레벨 피드백 큐(MLFQ) 개관

이전 글에서 올린 스케줄링 기법들(SJF,FCFS,STCF,RR)은 명확하고 단순한 규칙으로 동작되는 스케줄 기법들 이었다.

단순한 규칙으로 진행되는 스케줄링 공정으로 인해 그 과정이 눈에 쉽게보였고, 또 그로 인해 생기는 장단점들도 명확하게 구분되는 느낌이었다.

명확하게 보이는 장점은 좋을성치더라도 고쳐쓸수 있는 기계 공정에 단점 또한 명확히 보인다는 것은 그냥 그러려니 넘어가기는 조금 그렇다.

기계에서의 단점은 어찌보면 고민을 통해 개선하고 고쳐나가야 하는 것이기 때문이다.

멀티레벨 피드백 큐(MLFQ) 스케줄링 기법은 기존의 스케줄링 기법들에 비해 다소 복잡한 공정을 가지고 있지만 그만큼 각 단점들을 보완해온 기법이다.

MLFQ는 기존의 기법들 보다 더 많은 규칙과 조건을 내걸었고 그 결과 프로세스의 응답시간과 평균 변환시간 양쪽의 성능을 모두 챙겨 최적화 시켰다.

MLFQ의 스케줄링 동작과정

입출력의 관점에서 프로세스는 IO 작업이 많이 존재하는 프로세스와 그렇지 않은 프로세스로 나누어볼 수 있을 것같다.

(IO작업 [IO Burst]이 많이 존재하는 프로세스 : IO-Bound-Process , CPU 연산 작업 [Cpu_Burst]이 많이 존재하는 프로세스 : CPU-Bound-Process)

그리고 IO작업이 많은(IO-Burst가 큰) 프로세스들은 그렇지 않은 프로세스들보다 상대적으로 응답시간이 중요한 프로세스들이다.

이러한 프로세스들은 되도록이면 빠르게 스케줄하여 처리해야지만이 전체 시스템을 중첩적으로 움직이게끔 설계할 수 있으며, IO작업이라는 것 자체가 사용자와의 상호작용 행위와 밀접하게 연관되어 있을 확률이 큰 작업들이므로 빠른 처리를 통하여 사용자에게 빠른 상호작용의 느낌을 전해주어야 한다.

결국 프로세스들 사이에서도 처리 우선순위가 보다 높은 것들이 존재한다는 것이다. (IO작업이 많은 프로세스들이 우선순위가 더 크다)

MLFQ 스케줄러는 이같은 프로세스별 우선순위에 주목한 스케줄러로서 프로세스들의 처리 우선순위를 추측하고 파악하여 스케줄링을 진행한다.

MLFQ는 서로 다른 우선순위도를 가지고 있는 여러 개의 큐를 준비하여 우선순위에 따라 프로세스들을 적절하게 나눠담은 뒤, 더 높은 우선순위를 가지고 있는 큐에서 프로세스를 꺼내와 작업을 진행시키는 방식으로 동작한다.

여기서 한가지 주목해야할 것은 그럼 대체 어떤방식으로 스케줄러가 프로세스들의 우선순위를 판단하고 결정지을 수 있을까?라는 의문이다.

사실 스케줄러의 입장에서 각 프로세스가 IO-Bound 인지 CPU-Bound 인지 그 종류를 파악하고 결정짓는다는 것은 결코 쉬운 일이 아니다.

프로세스라는 것은 실행환경에 따라서 작업 과정이 유동적으로 변하기도하고 실제로 실행시켜보기 전까지는 정확히 어떠한 작업을 진행하는지 명확하게 예측하는 것이 불가능하기 때문이다.

따라서 MLFQ는 프로세스의 우선순위를 미리 예상하고 파악하여 큐에 나눠 담는 식으로 스케줄링을 진행하는 것이 아니라, 우선 프로세스를 실행시켜보고 점차적으로 우선순위를 파악해 나가는 방식으로 동작한다.

스케줄러는 최초로 프로세스를 실행시켜보기 전까지 아직 프로세스에 대한 어떠한 정보도 파악할 수 없다.

따라서 스케줄러는 프로세스가 최초로 스케줄러에 등록된 상황에서 우선은 해당 프로세스를 그냥 최고 우선순위를 갖는 큐에 배치시켜 버린다.

그리고 프로세스를 실행시켜보면서 (해당 큐에서 정한 CPU 연산 할당량을 모두 소모하였다면) 점차적으로 프로세스의 우선순위를 낮춰버린다.

이것은 오랜 시간동안 CPU를 할당받고도 작업을 끝내지 못한 프로세스라면 CPU-Burst가 큰 프로세스일 확률이 높으므로 점차적으로 해당 프로세스의 우선순위를 낮추겠다는 것을 의미한다.

즉 최초에는 모든 프로세스에게 가장높은 우선순위를 부여하고 점차적으로 우선순위를 낮춰가는 식으로 스케줄을 동작시키겠다는 전략이다.

이와 같은 방식이라면 반환시간이 얼마 걸리지 않는 프로세스들도 최고 우선순위로 실행될 수 있기때문에 작업이 금방 종료될 수 있고 따라서 전체적인 평균 반환시간도 최적화 할 수 있다.

그리고 상대적으로 IO-Burst가 커서 우선순위가 잘 떨어지지 않는 작업들에게도 좋은 응답시간을 제공해줄 수 있다.

결국 이같은 방법을 통해 응답시간과 반환시간 모두를 최적화 시킬 수 있다는 것이다.

하지만 이러한 전략도 한가지 개선해야할 문제점이 아직 존재한다.

아주 굉장할정도로 오랜 시간 실행되고 있는 어떠한 프로세스 A가 있다고 생각해보자.

해당 프로세스는 우선순위 지표가 깍이고 깍여 이젠 더이상은 깍일곳이 없는 지경에마저 이르렀고, 결국은 가장 낮은 우선순위의 큐에 담겨져 있는 상황일 것이다.

이러한 상황에서 만약 새로운 프로세스들이 끊임없이(빈번히) 추가되는 환경이 지속된다면 프로세스 A는 과연 어떻게 될까?

밑바닥에 박혀있는 우리의 A는 높은 우선순위를 부여받고 들어오는 신생 프로세스들에 가로막혀 더이상 CPU의 선택을 받지못하고 결국은 사망하게 된다. (기아상태-Starvation 에 빠지게 된다)

이러한 문제점을 해결하기 위해서 MLFQ는 aging이라는 전략을 추가적으로 시행한다.

밑바닥 큐에 박혀 CPU에게 오랫동안 선택을 받지 못하고 기아상태에 빠져가는 프로세스들에게 다시 한번 높은 우선순위의 큐에 입주할 수 있는 기회를 주는 것이다.

물론 이런식으로 프로세스를 구제하여도 시간이 지나면 결국 다시 우선순위가 깍여 기아상태로 향해 가겠지만, 반복적인 aging을 통하여 계속해서 구원의 손길을 보내준다면 CPU에게 완전히 외면받는 프로세스가 생기는 상황들은 모면할 수 있게 된다.

MLFQ의 스케줄링 동작과정(요약)

큐 A,B가 있을때

1) 우선순위(A) > 우선순위(B)인 경우 A가 실행됨. B는 큐 A가 전부 비워질때 까지 실행불가

2) 작업이 진행중인 큐에 있는 프로세스들은 전부 RR 방식으로 실행됨

3) 최초 프로세스가 시스템에 들어가면 최상위 큐에 배치됨

4) 지정된 단계(큐)에서 배정받은 작업 시간을 모두 소진하면, 작업의 우선순위도가 깍여 한단계 아래의 큐로 이동됨

5) 일정 주기가 지난 후, 시스템의 모든 작업을 최상위 큐로 이동시킴 (Aging)

profile
안녕하세요. 잘부탁드립니다.

0개의 댓글