MLFQ(Multilevel Feedback Queue)는 각각 서로 다른 우선 순위 수준과 시간 양자 값을 가진 여러 개의 준비 대기열을 유지 관리하는 CPU 스케줄링 알고리즘입니다. 새로운 프로세스는 우선순위가 가장 높은 대기열에서 시작되며 해당 동작에 따라 대기열 간에 승격되거나 강등될 수 있습니다. 이러한 적응형 접근 방식은 대화형 프로세스와 CPU 집약적 프로세스의 요구 사항 사이의 균형을 유지합니다.
다단계 피드백 큐 구조 큐 0(가장 높은 우선순위) 시간 퀀텀:1 큐 1(중간 우선순위) 시간 퀀텀:2 큐 2(가장 낮은 우선순위) FCFS CPU 새 프로세스 시간이 만료되면 강등 에이징:대기 후 승격 프로세스 이동 규칙 ? 새 프로세스가 대기열 0에서 시작됩니까? 시간 할당량이 만료되면? 다음 낮은 대기열로 이동하시겠습니까? 노화 메커니즘은 기아를 방지합니다
MLFQ 작동 방식
알고리즘은 다음과 같은 주요 원칙에 따라 작동합니다:
-
우선순위 기반 스케줄링 우선순위가 높은 대기열이 먼저 제공됩니다
-
가변 시간 퀀텀 우선 순위가 높은 대기열은 시간 조각이 더 짧습니다
-
동적 우선순위 조정 프로세스는 행동에 따라 대기열 사이를 이동합니다.
-
노화 메커니즘 오랫동안 기다리는 프로세스를 촉진하여 기아를 방지합니다
예
다음과 같은 특성을 지닌 세 가지 프로세스를 고려해보세요:
대기열 0의 시간 할당량 =1, 대기열 1의 시간 할당량 =2, 대기열 2의 FCFS 사용:
MLFQ 실행 타임라인 P1 P2 P3 P2 P1 P2 P1 (큐 2 - FCFS) 0 1 2 3 4 6 8 14 Q0 Q0 Q0 Q1 Q1 Q1 Q2
사용 사례
MLFQ는 다음과 같은 시나리오에서 특히 효과적입니다:
-
대화형 애플리케이션 웹 브라우저, 텍스트 편집기 및 GUI 애플리케이션은 사용자 상호 작용에 대한 빠른 응답 시간의 이점을 얻습니다.
-
시분할 시스템 대화식 프로세스와 일괄 프로세스가 공존하는 다중 사용자 시스템
-
중요한 작업과 중요하지 않은 작업에 대해 서로 다른 우선 순위 수준이 필요한 실시간 시스템 시스템
-
게임 응용 프로그램 게임에는 오디오 및 네트워킹과 같은 백그라운드 작업을 관리하는 동시에 반응형 입력 처리가 필요합니다.
장점
-
향상된 응답 시간 짧은 프로세스는 우선순위가 높은 대기열에서 빠르게 주목을 받습니다
-
동적 우선순위 조정 프로세스 동작 패턴에 자동으로 적응
-
Starvation Aging 메커니즘을 방지하여 오랫동안 대기 중인 프로세스가 결국 CPU 시간을 확보하도록 보장합니다.
-
처리량 균형이 양호하여 대화형 및 일괄 처리가 효율적으로 필요합니다.
-
유연한 구성 시간 할당 및 대기열 수는 특정 작업 부하에 맞게 조정 가능
단점
-
구현 복잡성 서로 다른 정책으로 여러 대기열을 관리하면 시스템 복잡성이 증가합니다
-
높은 오버헤드 &마이너스
