다단계 피드백 큐 스케줄링 (Multilevel Feedback Queue)

핵심 개념

다단계 피드백 큐 스케줄링은 프로세스가 CPU 버스트 특성에 따라 큐 사이를 이동할 수 있는 가장 유연한 스케줄링 알고리즘입니다. 다단계 큐에서는 프로세스가 영구적으로 한 큐에 고정되어 적응성이 없지만, 피드백 큐는 프로세스의 행동에 따라 큐를 동적으로 변경합니다.

동작 원리

1. CPU 시간을 많이 사용하면 → 낮은 우선순위 큐로 강등(Demotion)
2. 낮은 큐에서 오래 대기하면 → 높은 우선순위 큐로 승격(Promotion) - 에이징
3. I/O-bound, 대화형 프로세스는 자연스럽게 높은 우선순위 유지

정의에 필요한 파라미터

큐의 개수, 각 큐의 스케줄링 알고리즘, 승격/강등 조건, 진입 큐 결정

3개 큐 시스템 예시

새 프로세스 ──▶ [큐 0: RR, q=8ms]  ──(8ms 초과)──▶ [큐 1: RR, q=16ms]
                     │                                    │
                     ▼                            (16ms 초과)
                   CPU  ◀──────────────────────── [큐 2: FCFS]
                                                         │
                                               (오래 대기: 에이징)
                                                         │
                         [큐 1 또는 0으로 승격] ◀─────────┘

예시

CPU 버스트 30ms 프로세스:

1. 큐 0에서 8ms 실행 → 큐 1로 강등 (남은: 22ms)
2. 큐 1에서 16ms 실행 → 큐 2로 강등 (남은: 6ms)
3. 큐 2에서 6ms 실행 → 완료

CPU-bound 프로세스는 자동으로 낮은 우선순위로 이동하고, 짧은 I/O-bound 프로세스는 큐 0에서 빠르게 완료됩니다.

일반성

다른 알고리즘의 상위 집합입니다:

• 큐 1개, 퀀텀 무한대 → FCFS

• 큐 1개, 고정 퀀텀 → RR

• 큐 여러 개, 이동 없음 → 다단계 큐

• 장점: 가장 유연한 스케줄링, I/O-bound 프로세스 자동 우대, 에이징으로 기아 방지

• 단점: 가장 복잡한 알고리즘, 최적 파라미터 선택이 어려움

관련 개념

• 다단계 큐 스케줄링 - 큐 간 이동 불가능한 기본형
• UNIX CPU 스케줄링
• 멀티태스킹 (Multitasking)