5장 - 다중 레벨 피드백 큐(MLFQ) 스케줄링 알고리즘 (37)

다중 레벨 피드백 큐(MLFQ) 스케줄링 알고리즘

이전 포스팅에서는 다중 레벨 큐(MLQ) 스케줄링 알고리즘에 대해 살펴보았습니다. 이번 포스팅에서는 MLQ의 한계를 개선한 더 유연하고 적응적인 스케줄링 방식인 다중 레벨 피드백 큐(Multilevel Feedback Queue, MLFQ) 스케줄링 알고리즘에 대해 자세히 알아보겠습니다. MLFQ는 현대 운영체제에서 널리 사용되는 고급 스케줄링 기법 중 하나로, 프로세스의 행동 패턴에 따라 동적으로 우선순위를 조정하는 특징을 가지고 있습니다.

 

다중 레벨 피드백 큐(MLFQ) 스케줄링 개요

다중 레벨 피드백 큐 스케줄링은 1962년에 Fernando J. Corbató에 의해 처음 제안된 알고리즘으로, 프로세스가 여러 우선순위 큐 사이를 이동할 수 있도록 하여 MLQ의 유연성을 크게 향상시킨 방식입니다. MLFQ는 프로세스의 CPU 사용 패턴에 따라 우선순위를 동적으로 조정함으로써, 짧은 작업과 I/O 집약적인 작업(대화형 프로세스)에 높은 우선순위를 부여하고, 장시간 실행되는 CPU 집약적 작업에는 낮은 우선순위를 부여합니다.

MLFQ 스케줄링 알고리즘 설계 의도

MLFQ 스케줄링은 다음과 같은 목적으로 설계되었습니다:

1. 기아 현상 방지: MLQ의 가장 큰 단점인 낮은 우선순위 큐의 기아 현상을 해결
2. 학습 및 적응: 프로세스의 행동 패턴을 학습하여 적절한 스케줄링 결정을 내림
3. 짧은 작업 우선 처리: SJF(Shortest Job First)의 장점을 살리면서도 실행 시간을 미리 알 필요가 없음
4. 대화형 프로세스 우대: 사용자 반응성이 중요한 대화형 프로세스에 높은 우선순위 부여
5. CPU 활용 최적화: 다양한 유형의 프로세스에 적절한 CPU 시간 할당

MLFQ 알고리즘 특징

알고리즘 동작 방식

• 시스템은 여러 개의 우선순위가 다른 준비 큐를 유지합니다.
• 새로운 프로세스는 처음에 가장 높은 우선순위 큐에 배치됩니다.
• 각 큐는 자체적인 스케줄링 알고리즘(일반적으로 Round-Robin)과 타임 슬라이스를 가지고 있으며, 낮은 우선순위 큐일수록 더 긴 타임 슬라이스를 사용합니다.
• 프로세스는 다음과 같은 규칙에 따라 큐 간에 이동합니다:
  • 프로세스가 타임 슬라이스를 모두 사용하면(CPU를 오래 사용하면) 한 단계 낮은 우선순위 큐로 이동합니다.
  • 프로세스가 타임 슬라이스가 끝나기 전에 CPU를 자발적으로 반납하면(I/O 요청 등으로 인해), 같은 우선순위 큐에 머물거나 경우에 따라 더 높은 우선순위 큐로 이동할 수 있습니다.
  • 일정 시간이 지나면 모든 프로세스를 가장 높은 우선순위 큐로 다시 이동시키는 '우선순위 부스팅(Priority Boosting)'을 수행하여 기아 현상을 방지합니다.

핵심 특성

• 스케줄링 파라미터: 큐 타임 슬라이스, 우선순위 부스팅 주기
• 스케줄링 타입: 선점형 스케줄링
• 프로세스 이동: 프로세스가 큐 간에 자유롭게 이동 가능
• 기아 현상: 우선순위 부스팅을 통해 방지 가능
• 적응성: 프로세스의 행동 패턴에 따라 적응적으로 스케줄링

MLFQ 규칙 상세 설명

MLFQ의 주요 동작 규칙을 좀 더 자세히 살펴보겠습니다:

규칙 1: 우선순위에 따른 스케줄링

• 높은 우선순위 큐의 프로세스가 항상 낮은 우선순위 큐의 프로세스보다 먼저 실행됩니다.
• 같은 우선순위 큐 내에서는 보통 Round-Robin 방식으로 프로세스를 스케줄링합니다.

규칙 2: 초기 할당

• 새로운 프로세스는 항상 가장 높은 우선순위 큐에 배치됩니다.
• 이는 모든 프로세스에게 처음에는 "짧은 작업"일 것이라는 가정 하에 기회를 부여하는 것입니다.

규칙 3: CPU 사용 패턴에 따른 이동

• 프로세스가 할당된 타임 슬라이스를 모두 사용하면, 우선순위가 한 단계 낮아집니다(한 단계 아래 큐로 이동).
• 프로세스가 타임 슬라이스를 다 사용하기 전에 CPU를 자발적으로 반납하면(I/O 요청 등), 같은 우선순위 큐에 남습니다.

규칙 4: 우선순위 부스팅(에이징)

• 일정 시간 간격마다 모든 프로세스를 가장 높은 우선순위 큐로 다시 이동시킵니다.
• 이 메커니즘은 낮은 우선순위 큐에 오래 머물러 있는 프로세스의 기아 현상을 방지합니다.
• 또한 프로세스의 행동 패턴이 시간에 따라 변할 수 있다는 점을 고려합니다.

규칙 5: CPU 버스트 감지와 우선순위 조정(변형)

• 일부 MLFQ 구현에서는 프로세스의 I/O 요청 패턴을 감지하여 대화형 프로세스에게 더 높은 우선순위를 부여합니다.
• 예를 들어, I/O 요청 후 짧은 CPU 버스트를 반복하는 프로세스는 대화형으로 간주되어 우선순위가 상승할 수 있습니다.

MLFQ 구현 예시

MLFQ의 일반적인 구현은 다음과 같은 구조를 가질 수 있습니다:

큐 구조 예시

• 큐 0(최고 우선순위): 타임 슬라이스 = 8ms
• 큐 1: 타임 슬라이스 = 16ms
• 큐 2: 타임 슬라이스 = 32ms
• 큐 3: 타임 슬라이스 = 64ms
• 큐 4(최저 우선순위): 타임 슬라이스 = 128ms

각 큐의 타임 슬라이스는 보통 2의 거듭제곱으로 증가하며, 우선순위가 낮아질수록 더 긴 타임 슬라이스가 할당됩니다. 이는 CPU 집약적인 작업에게 더 긴 타임 슬라이스를 제공하여 문맥 교환(Context Switch) 오버헤드를 줄이기 위함입니다.

우선순위 부스팅 주기

모든 프로세스를 최고 우선순위 큐로 다시 이동시키는 우선순위 부스팅은 보통 정해진 시간 간격(예: 1초 또는 특정 타임 틱 수)마다 또는 낮은 우선순위 큐의 프로세스가 특정 시간 이상 대기했을 때 수행됩니다.

MLFQ 스케줄링 사례 예제

다음과 같은 프로세스들이 있다고 가정해 봅시다:

프로세스	도착 시간	CPU 버스트 패턴
P1	0ms	10ms(CPU) - 종료
P2	0ms	4ms(CPU) - I/O - 4ms(CPU) - 종료
P3	0ms	2ms(CPU) - I/O - 2ms(CPU) - I/O - 2ms(CPU) - 종료
P4	10ms	6ms(CPU) - 종료

3개의 큐를 사용하는 MLFQ 스케줄링을 적용해보겠습니다:

• 큐 0(높은 우선순위): 타임 슬라이스 = 2ms
• 큐 1(중간 우선순위): 타임 슬라이스 = 4ms
• 큐 2(낮은 우선순위): 타임 슬라이스 = 8ms
• 우선순위 부스팅 주기: 10ms

스케줄링 과정은 다음과 같습니다:

1. 0ms: P1, P2, P3가 모두 도착하고 큐 0에 배치됩니다. 큐 0의 타임 슬라이스는 2ms입니다. Round-Robin 순서에 따라 P1이 먼저 실행됩니다.
2. 2ms: P1의 타임 슬라이스가 끝납니다. P1은 타임 슬라이스를 모두 사용했으므로 큐 1로 이동합니다. P2가 실행을 시작합니다.
3. 4ms: P2의 타임 슬라이스가 끝납니다. P2도 타임 슬라이스를 모두 사용했으므로 큐 1로 이동합니다. P3가 실행을 시작합니다.
4. 6ms: P3는 2ms 실행 후 I/O 요청을 하여 대기 상태가 됩니다. P3는 타임 슬라이스를 다 사용하기 전에 CPU를 반납했으므로 큐 0에 남습니다(현재 대기 상태). 현재 큐 0에는 실행 가능한 프로세스가 없고, 큐 1에는 P1과 P2가 있습니다. Round-Robin 순서에 따라 P1이 실행됩니다.
5. 8ms: P1이 큐 1의 타임 슬라이스(4ms)를 다 사용했으므로 큐 2로 이동합니다. P2가 실행을 시작합니다.
6. 10ms: P4가 도착하고 큐 0에 배치됩니다. 또한 우선순위 부스팅이 발생하여 모든 프로세스가 큐 0로 이동합니다(P1, P2). P2는 실행 도중에 I/O 요청을 했다고 가정합니다. 큐 0에는 이제 P1, P2(대기 상태), P3(I/O가 끝났다고 가정), P4가 있습니다. 높은 우선순위 큐부터 스케줄링하므로 P1, P3, P4 중 하나가 실행됩니다. Round-Robin에 따라 P4가 실행을 시작합니다.
7. 12ms: P4의 타임 슬라이스가 끝납니다. P4는 큐 1로 이동하고, P1이 실행됩니다.
8. 14ms: P1의 타임 슬라이스가 끝납니다. P1은 큐 1로 이동하고, P3가 실행됩니다.
9. 16ms: P3는 2ms 실행 후 I/O 요청을 하여 대기 상태가 됩니다. P3는 타임 슬라이스를 다 사용하기 전에 CPU를 반납했으므로 큐 0에 남습니다(현재 대기 상태). 현재 큐 0에는 실행 가능한 프로세스가 없고, 큐 1에는 P1과 P4가 있습니다. P1이 실행을 시작합니다.
10. 18ms: P1이 완료됩니다. P4가 실행을 시작합니다.
11. 20ms: 우선순위 부스팅이 다시 발생하여 모든 프로세스가 큐 0로 이동합니다. P4와 P3(I/O가 끝났다고 가정)가 큐 0에 있습니다. P3가 실행을 시작합니다.
12. 22ms: P3가 완료됩니다. P4가 실행을 시작합니다.
13. 24ms: P4가 완료됩니다.

이 예제에서 볼 수 있듯이, MLFQ는 프로세스의 CPU 사용 패턴에 따라 우선순위를 동적으로 조정합니다. 짧은 CPU 버스트를 가진 대화형 프로세스(P3)는 높은 우선순위를 유지하여 빠른 응답 시간을 얻고, CPU 집약적인 프로세스(P1)는 점차 낮은 우선순위로 이동하여 대화형 프로세스의 응답성을 향상시킵니다. 또한 우선순위 부스팅을 통해 모든 프로세스가 결국에는 CPU를 할당받을 수 있도록 보장합니다.

MLFQ의 장점과 단점

장점

1. 적응성: 프로세스의 행동 패턴에 따라 우선순위를 동적으로 조정하여 다양한 유형의 작업을 효율적으로 처리합니다.
2. 응답성 향상: 대화형 프로세스와 짧은 작업에 높은 우선순위를 부여하여 시스템의 응답성을 향상시킵니다.
3. 기아 방지: 우선순위 부스팅을 통해 모든 프로세스가 결국에는 CPU를 할당받을 수 있도록 보장합니다.
4. SJF 근사: 실행 시간을 미리 알 필요 없이 짧은 작업을 우선적으로 처리하는 SJF의 장점을 근사적으로 구현합니다.
5. 유연성: 다양한 시스템 요구사항과 워크로드에 맞게 파라미터를 조정할 수 있습니다.

단점

1. 구현 복잡성: 여러 큐와 우선순위 조정 메커니즘으로 인해 구현이 복잡해질 수 있습니다.
2. 파라미터 튜닝: 최적의 성능을 위해 큐의 수, 타임 슬라이스 크기, 우선순위 부스팅 주기 등 다양한 파라미터를 신중하게 설정해야 합니다.
3. 오버헤드: 프로세스의 우선순위 조정과 큐 간 이동으로 인한 관리 오버헤드가 발생할 수 있습니다.
4. 게이밍(Gaming) 문제: 일부 프로세스가 의도적으로 시스템의 스케줄링 규칙을 악용할 가능성이 있습니다(예: 타임 슬라이스가 끝나기 직전에 I/O 요청을 하여 높은 우선순위를 유지).
5. 예측 어려움: 우선순위 변화로 인해 특정 프로세스의 완료 시간을 정확히 예측하기 어려울 수 있습니다.

MLFQ의 변형과 최적화

1. 가변 타임 슬라이스

• 시스템 부하나 활성 프로세스 수에 따라 타임 슬라이스의 크기를 동적으로 조정합니다.
• 예를 들어, 시스템 부하가 높을 때는 타임 슬라이스를 줄여 응답성을 유지하고, 부하가 낮을 때는 타임 슬라이스를 늘려 문맥 교환 오버헤드를 줄입니다.

2. 행동 기반 우선순위 조정

• 프로세스의 CPU와 I/O 사용 패턴을 더 정교하게 분석하여 우선순위를 조정합니다.
• CPU 버스트와 I/O 버스트의 비율, 메모리 접근 패턴 등을 고려하여 프로세스의 특성을 더 정확히 파악합니다.

3. 우선순위 부스팅 최적화

• 모든 프로세스를 동시에 부스팅하는 대신, 특정 조건을 만족하는 프로세스만 선택적으로 부스팅합니다.
• 예를 들어, 특정 시간 이상 낮은 우선순위 큐에 머물러 있는 프로세스만 부스팅할 수 있습니다.

4. 하이브리드 접근 방식

• MLFQ와 다른 스케줄링 알고리즘(예: Fair-share Scheduling, Real-time Scheduling)을 결합하여 다양한 요구사항을 충족합니다.
• 예를 들어, 일부 프로세스에게는 최소 CPU 시간을 보장하면서 MLFQ를 적용할 수 있습니다.

실제 시스템에서의 MLFQ 활용

MLFQ 또는 그 변형은 많은 현대 운영체제에서 사용되고 있습니다:

1. UNIX 계열 운영체제

전통적인 UNIX 시스템은 다중 레벨 피드백 큐와 유사한 스케줄링 방식을 사용했습니다:

• FreeBSD: ULE 스케줄러는 MLFQ의 개념을 발전시킨 형태로, 대화형 프로세스와 배치 프로세스를 구분하여 처리합니다.
• Solaris: 타임 공유(Time-sharing) 스케줄링 클래스는 MLFQ를 기반으로 하며, 프로세스의 CPU 사용 패턴에 따라 우선순위를 동적으로 조정합니다.

2. Windows 운영체제

Windows 운영체제는 MLFQ와 유사한 가변 우선순위 스케줄링을 구현합니다:

• 프로세스 우선순위 클래스와 스레드 우선순위의 조합으로 여러 우선순위 레벨을 제공합니다.
• 대화형 프로세스의 우선순위를 동적으로 높이고, CPU 집약적 프로세스의 우선순위를 낮추는 메커니즘을 사용합니다.
• 우선순위 부스팅을 통해 기아 현상을 방지합니다.

3. Linux 운영체제

최신 Linux 커널은 완전 공정 스케줄러(Completely Fair Scheduler, CFS)를 기본 스케줄러로 사용하지만, 이전 버전과 특정 설정에서는 O(1) 스케줄러가 MLFQ와 유사한 방식으로 동작했습니다:

• 다중 우선순위 레벨과 동적 우선순위 조정을 제공했습니다.
• 대화형 프로세스에게 높은 우선순위를 부여하고, CPU 집약적 프로세스에게는 낮은 우선순위를 부여했습니다.
• 에이징(Aging) 메커니즘을 통해 기아 현상을 방지했습니다.

4. 실시간 및 임베디드 시스템

일부 실시간 운영체제(RTOS)는 MLFQ의 개념을 채택하되, 실시간 제약 조건을 만족시키기 위해 수정된 형태를 사용합니다:

• 높은 우선순위 큐에는 경성 실시간(Hard Real-time) 태스크를 배치하고, 낮은 우선순위 큐에는 연성 실시간(Soft Real-time) 및 비실시간 태스크를 배치합니다.
• 우선순위 역전(Priority Inversion) 문제를 해결하기 위한 추가 메커니즘을 구현합니다.

MLFQ와 다른 알고리즘 비교

MLFQ vs MLQ

• MLFQ에서는 프로세스가 큐 간에 자유롭게 이동할 수 있지만, MLQ에서는 프로세스가 한 번 할당된 큐에 영구적으로 머물러 있습니다.
• MLFQ는 프로세스의 행동 패턴에 따라 우선순위를 동적으로 조정하므로 더 적응적이지만, MLQ는 정적인 분류에 의존합니다.
• MLFQ는 우선순위 부스팅을 통해 기아 현상을 효과적으로 방지할 수 있지만, MLQ는 추가 메커니즘 없이는 기아 현상이 발생할 수 있습니다.

MLFQ vs Priority 스케줄링

• MLFQ는 프로세스의 행동에 기반한 동적 우선순위를 사용하지만, 기본 Priority 스케줄링은 주로 정적 우선순위를 사용합니다.
• MLFQ는 타임 슬라이스와 큐 간 이동 메커니즘을 통해 더 복잡한 스케줄링 정책을 구현할 수 있습니다.
• 두 알고리즘 모두 우선순위가 높은 프로세스를 우선적으로 처리하지만, MLFQ는 프로세스 특성에 더 잘 적응합니다.

MLFQ vs SJF/SRTF

• SJF/SRTF는 실행 시간이 짧은 프로세스를 우선적으로 처리하지만, 이를 위해 프로세스의 실행 시간을 미리 알아야 합니다.
• MLFQ는 실행 시간을 미리 알 필요 없이, 프로세스의 행동 패턴을 관찰하여 짧은 작업을 우선적으로 처리하는 SJF의 효과를 근사적으로 달성합니다.
• SJF/SRTF는 평균 대기 시간을 최소화하는 데 최적이지만, MLFQ는 응답성과 처리율 사이의 균형을 더 중시합니다.

MLFQ vs Fair-share 스케줄링

• Fair-share 스케줄링(예: Linux의 CFS)은 모든 프로세스에게 공정한 CPU 시간 비율을 보장하는 데 중점을 둡니다.
• MLFQ는 프로세스의 특성에 따라 차별화된 서비스를 제공하는 반면, Fair-share는 자원 사용의 공정성을 강조합니다.
• 두 알고리즘은 종종 하이브리드 형태로 결합되어 사용됩니다.

결론

다중 레벨 피드백 큐(MLFQ) 스케줄링은 프로세스의 행동 패턴에 따라 우선순위를 동적으로 조정하는 유연하고 적응적인 스케줄링 알고리즘입니다. MLFQ는 MLQ의 기본 구조를 확장하여 프로세스가 큐 간에 이동할 수 있도록 함으로써, 다양한 유형의 워크로드를 효율적으로 처리하고 시스템의 응답성과 처리율을 최적화할 수 있습니다.

 

MLFQ의 주요 장점은 실행 시간을 미리 알 필요 없이 짧은 작업과 대화형 프로세스를 우선적으로 처리하고, 우선순위 부스팅을 통해 기아 현상을 방지한다는 점입니다. 그러나 구현 복잡성, 파라미터 튜닝의 어려움, 관리 오버헤드 등의 단점도 존재합니다.

 

실제 운영체제에서는 순수한 형태의 MLFQ보다는 시스템 요구사항과 워크로드 특성에 맞게 최적화된 변형이 주로 사용됩니다. 이러한 변형은 타임 슬라이스 조정, 행동 기반 우선순위 조정, 선택적 우선순위 부스팅 등 다양한 최적화 기법을 포함합니다.

 

CPU 스케줄링 알고리즘은 운영체제의 핵심 기능 중 하나로, 시스템의 성능과 사용자 경험에 직접적인 영향을 미칩니다. MLFQ는 이러한 스케줄링 알고리즘 중에서도 가장 발전된 형태 중 하나로, 다양한 유형의 프로세스를 효율적으로 관리하고 시스템 자원을 최적화하는 데 중요한 역할을 합니다.

 

MLFQ는 FCFS, SJF, Round-Robin, Priority 스케줄링 등 기본적인 스케줄링 알고리즘의 장점을 결합하고 단점을 보완한 종합적인 스케줄링 방식으로, 현대 컴퓨팅 환경의 복잡한 요구사항을 충족시키는 데 효과적인 솔루션을 제공합니다.

 

지금까지 CPU 스케줄링 알고리즘에 대한 시리즈를 통해 기본적인 알고리즘부터 고급 알고리즘까지 다양한 스케줄링 방식을 살펴보았습니다.

각 알고리즘은 저마다의 장단점과 적합한 사용 환경이 있으며, 실제 시스템에서는 이러한 알고리즘들이 다양한 형태로 결합되어 사용됩니다. 스케줄링 알고리즘의 선택과 최적화는 시스템의 목적, 워크로드 특성, 하드웨어 구성 등 여러 요소를 고려하여 이루어져야 합니다.

참고 문헌

• Silberschatz, A., Galvin, P. B., & Gagne, G. (2018). Operating System Concepts. Wiley.
• Stallings, W. (2017). Operating Systems: Internals and Design Principles. Pearson.
• Tanenbaum, A. S., & Bos, H. (2014). Modern Operating Systems. Pearson.
• Corbató, F. J., Merwin-Daggett, M., & Daley, R. C. (1962). An Experimental Time-sharing System. Proceedings of the Spring Joint Computer Conference, AFIPS.
• Love, R. (2010). Linux Kernel Development. Addison-Wesley Professional.