안녕하세요! 지난 글에서 운영체제 스케줄링의 기본 개념과 주요 알고리즘인 FIFO, SJF, STCF, RR에 대해 살펴보았습니다.
이번에는 멀티레벨 피드백 큐(Multi-Level Feedback Queue, MLFQ)라는 스케줄링 알고리즘을 소개하려고 합니다.
MLFQ는 앞서 다룬 알고리즘들의 단점을 보완하며, 현대 운영체제에서 널리 사용되는 강력한 방식입니다.
이번 글에서는 MLFQ의 작동 원리와 규칙, 그리고 개선된 버전에 대해 알아보겠습니다.
MLFQ란 무엇인가요?
MLFQ는 작업의 특성을 기반으로 우선순위를 동적으로 조정하여, 짧은 작업에는 빠른 응답을 제공하고 긴 작업에는 공정한 CPU 할당을 보장하는 스케줄링 알고리즘입니다.
MLFQ의 핵심 목표
- 반환 시간(Turnaround Time) 최소화
짧은 작업을 먼저 처리함으로써 반환 시간을 줄입니다. - 응답 시간(Response Time) 최적화
대화형 작업(예: 사용자 입력 처리)에 빠른 응답을 제공합니다. - 공정성(Fairness) 보장
긴 작업도 일정 시간 동안 CPU를 사용할 수 있도록 보장합니다.
MLFQ의 기본 구조
MLFQ는 여러 개의 큐로 구성되어 있으며, 각 큐는 서로 다른 우선순위를 가집니다. 초기 작업은 높은 우선순위 큐에 배치되고, 작업의 실행 시간에 따라 점차 낮은 우선순위 큐로 이동합니다.
- 높은 우선순위 큐는 짧은 작업이나 대화형 작업을 처리합니다.
- 낮은 우선순위 큐는 긴 작업을 처리합니다.
MLFQ의 규칙
기본 규칙
- 우선순위가 높은 작업 우선 실행
- Rule 1: 우선순위(Priority)가 높은 작업이 실행됩니다.
- Rule 2: 동일한 우선순위에서는 라운드 로빈(Round Robin) 방식으로 실행합니다.
- 작업의 우선순위 조정
- Rule 3: 새 작업은 가장 높은 우선순위 큐에서 시작합니다.
- Rule 4: 작업이 할당된 시간(allotment)을 모두 사용하면 우선순위를 낮춥니다.
- Rule 5: 일정 시간(S) 후 모든 작업의 우선순위를 초기화(Boost)합니다.
- MLFQ는 작업의 행동을 관찰하여 우선순위를 동적으로 변경합니다:
MLFQ의 작동 방식
1. 짧은 작업 우선 처리
MLFQ는 작업이 처음에는 짧은 작업일 가능성이 높다고 가정하고, 높은 우선순위를 부여합니다. 만약 작업이 짧다면 높은 우선순위 큐에서 빠르게 완료됩니다.
긴 작업(A)이 낮은 우선순위 큐에 있을 때 짧은 작업(B)이 도착하면, B는 높은 우선순위 큐에서 빠르게 실행됩니다.
2. 대화형 작업 지원
대화형 작업은 CPU 사용 후 I/O 작업을 수행하며, 할당된 시간을 모두 사용하지 않기 때문에 높은 우선순위를 유지할 수 있습니다. 이를 통해 대화형 작업이 신속히 처리됩니다.
대화형 작업은 높은 우선순위를 유지하면서 빠르게 실행됩니다.
MLFQ의 문제와 개선 방법
1. 기아(Starvation) 문제
- 문제: 대화형 작업이 너무 많으면 긴 작업이 CPU를 받지 못할 수 있습니다.
- 해결책: 우선순위 부스트(Priority Boost)를 사용해 모든 작업의 우선순위를 주기적으로 초기화합니다.
2. 스케줄링 악용(Gaming)
- 문제: 작업이 의도적으로 I/O 작업을 수행하여 높은 우선순위를 유지할 수 있습니다.
- 해결책: 정확한 CPU 사용 시간 계정으로 I/O 여부와 관계없이 할당 시간을 기준으로 우선순위를 조정합니다.
개선된 규칙으로 스케줄링 악용을 방지합니다.
MLFQ의 튜닝과 한계
MLFQ는 환경에 따라 여러 매개변수를 조정해야 합니다:
- 큐의 개수 및 각 큐의 시간 할당량
- 우선순위 부스트 주기(S)
- 시스템 워크로드에 따른 설정 최적화
정리하며: MLFQ의 장점과 활용
MLFQ는 짧은 작업에 빠른 응답을 제공하면서도 긴 작업에 공정한 CPU 사용을 보장하는 강력한 스케줄링 알고리즘입니다. 작업의 행동을 관찰하여 우선순위를 동적으로 조정하는 방식은 현대 운영체제에서도 유용하게 활용됩니다.
다음 글에서는 MLFQ와 관련된 I/O 및 동시 작업 환경에서의 스케줄링 사례를 살펴보겠습니다.
질문이나 의견이 있다면 댓글로 남겨주세요! 😊
다음 글에서 만나요! ✨
이 글은 Operating Systems: Three Easy Pieces를 참고하여 작성되었습니다.
