Published on

MLFQS (Multi-Level Feedback Queue Scheduling)

Authors
  • avatar
    Name
    JaeHyeok CHOI
    Twitter
    none

CPU 스케줄링

스케줄링

다중 프로그래밍을 가능하게 하는 OS의 동작 기법이다. OS는 프로세스들에게 CPU 등의 자원 배정을 적절히 함으로써 시스템의 성능을 개선할 수 있다.

유형

  • 장기
  • 중기
  • 단기

단계

  • 1단계 스케줄링
    작업 스케줄링이라고도 한다. 어느 작업부터 시스템 내의 자원들을 실제로 사용할 수 있도록 할지를 결정한다. 작업들이 시스템에 들어오는 것을 승인하는 것이기 때문에 승인 스케줄링(Admission scheduling) 이라고도 한다.
  • 2단계 스케줄링
    어느 프로세스부터 CPU를 차지할 수 있게 할지를 결정한다. 프로세스들을 보류시키고 다시 활성화시키는 기법을 사용하여 시스템에 대한 단기적인 부하를 조절한다. 그렇게 함으로써 시스템을 적절히 운영할 수 있다. 작업 승인(1단계)와 CPU 배당(3단계) 사이의 완충을 작용한다.
  • 3단계 스케줄링
    CPU가 사용 가능한 경우 어느 프로세스에게 배당할지를 결정한다.

결정 시점

CPU 스케줄링의 결정 시점은 다음과 같은 프로세스의 상태 변화가 있을 때이다.

  1. 수행 → 대기
  2. 수행 → 준비
  3. 대기 → 준비
  4. 수행 → 종료

비선점형과 선점형

  • 비 선점형
    결정 시점 중 1번과 4번의 상황에서만 수행됨
  • 선점형
    1 ~ 4번까지의 모든 상황에서 수행됨

정적 스케줄링과 동적 스케줄링

프로세스의 우선순위 변동 여부에 따라 정적 스케줄링과 동적 스케줄링으로 구분할 수 있다.

  • 정적 스케줄링
    프로세스에 부여된 우선순위가 바뀌지 않는다. 고정 우선 순위 스케줄링이라고도 한다.
  • 동적 스케줄링
    스케줄링 과정에서 프로세스의 우선 순위를 변동시킨다. 유동 우선순위 스케줄링이라고도 한다.

스케줄링 알고리즘

  • 비선점 프로세스 스케줄링
    1. FCFS - (First Come First Served)
    2. SJF - (Short Job First)
    3. HRRN - (Highest Response Ratio Next)
  • 선점 프로세스 스케줄링
    1. RR - (Round Robin)
    2. SRTF - (Shortest Remaining-Time First)
    3. 다단계 큐
    4. 다단계 피드백 큐
    5. RM - (Rate Monotonic)
    6. EDF - (Earliest Deadline First)

평가 기준

스케줄링 알고리즘은 다음과 같은 기준을 통해 평가할 수 있다.

  • CPU 사용률(CPU Utilization) : 전체 시스템 시간 중 CPU가 작업을 처리하는 시간의 비율.
  • 처리량(Throughput) : CPU가 단위 시간당 처리하는 프로세스의 개수.
  • 응답 시간(Response Time) : 대화식 시스템에서 요청 후 응답이 오기 시작할 때까지의 시간.
  • 대기 시간(Waiting Time) : 프로세스가 준비 큐 내에서 대기하는 시간의 총합.
  • 반환 시간(Turnaround Time) : 프로세스가 시작해서 끝날 때까지 걸리는 시간.

다단계 큐 스케줄링

커널 내의 준비 큐를 여러 개의 큐로 분리하여 큐 사이에도 우선순위를 부여하는 스케줄링 알고리즘.

다단계 피드백 큐 스케줄링

다단계 큐 스케줄링에서 한 단계 발전된 방식으로, 다단계 큐 스케줄링에서는 프로세스가 하나의 큐에 영구적으로 할당되지만, 다단계 피드백 큐 스케줄링에서는 프로세스들이 큐를 갈아 탈 수 있다. 또한 작업들이 서로 다른 유형의 작업들로 분류될 경우 사용한다.

설계 방침

  1. 짧은 작업에 우선권을 준다.
  2. 입출력 관련 프로세스에 우선권을 준다.
  3. 프로세서 사용량에 따라 프로세스를 분류한다.

FIFO, SJF, RR 스케줄링 특징과 문제점

  • FIFO
    • 장점
      • 단순하다
      • 구현하기 쉽다
    • 단점
      • Convoy effect
      • 긴 평균 응답시간 (response time)
  • SJF
    • 단점
      • FIFO와 같이 convoy effect 가 발생

  • STCF/PSJF (최소 잔여 시간 우선 / 선점형 최단 작업 우선)

  • RR
    • 작업이 끝날 때까지 기다리지 않고 일정 시간 이후 다음 작업으로 전환함. 작업이 실행되는 일정 시간을 타임 슬라이스 혹은 스케줄링 퀀텀 이라고 부른다. 타임 슬라이스의 길이는 타이머 인터럽트 주기의 배수여야 한다. 타임 슬라이스의 길이는 RR에게 매우 중요한 조건이다. 타임 슬라이스가 짧으면 문맥 교환 비용이 전체 성능에 큰 영향을 미치며, Convoy 문제가 발생한다.

MLFQ

해결하고자 하는 문제

  1. 짧은 작업을 먼저 실행시켜 반환 시간을 최적화 하고자 함
  2. MLFQ는 대화형 사용자에게 응답이 빠른 시스템이라는 느낌을 주고 싶었기 때문에 응답 시간을 최적화 함

여러 개의 큐로 구성되어 있고 각각 큐마다 다른 우선순위가 배정된다. 그리고 큐에는 프로세스가 배정되고 한 큐에 여러 개의 프로세스가 배정될 수 있다. 그리고 우선순위가 높은 큐에 있는 작업이 먼저 실행된다. 또한, 같은 큐에 있는 여러 작업은 RR 스케줄링을 적용하여 실행한다.

핵심은 우선 순위를 정하는 방식이다. 각 작업마다 고정된 우선 순위를 부여하는 것이 아니라 각 작업의 특성에 따라 “동적”으로 우선 순위를 부여하는 방식을 사용한다.

예시

어떤 작업이 키보드 입력을 기다리며 반복적으로 CPU를 양보하면 MLFQ는 해당 작업의 우선순위를 높게 유지한다. 반면, 한 작업이 긴 시간동안 CPU를 집중적으로 사용하면 MLFQ는 해당 작업의 우선 순위를 낮춘다. 이 처럼 작업이 진행되는 동안 해당 작업의 정보를 얻고 이 정보를 이용해서 미래 행동을 예측한다.

규칙 1 : Priority(A) > Priority(B) 이면 A가 실행 (B는 실행되지 않는다.)

규칙 2 : Priority(A) = Priority(B) 이면 A와 B는 RR 방식으로 실행된다.

우선 순위를 변경하는 규칙

규칙 3 : 작업이 시스템에 진입하면 가장 높은 우선 순위 즉 맨 위의 큐에 놓여진다.

규칙 4a : 주어진 타임 슬라이스를 모두 사용하면 우선 순위는 낮아진다. (한 단계 아래 큐로 이동한다.)

규칙 4b : 타임 슬라이스를 소진하기 전에 CPU를 양도하면 같은 우선 순위를 유지한다.

  1. 한개의 긴 작업이 존재하는 경우)
image
  1. 짧은 작업이 들어온 경우)
image
  1. 입출력 작업이 들어온 경우)
image

MLFQ의 타임 슬라이스 기준으로 짧은 작업부터 높은 우선 순위의 큐에 할당된다. 같은 우선 순위에 있는 작업들은 RR 로 동작하고, 타임 슬라이스를 모두 소진한 작업은 우선 순위를 1씩 감소 시킨다. 다른 작업이 없는 경우에는 긴 해당 작업을 계속해서 진행한다.

MLFQ 현재까지의 내용 중 문제점

기아 상태

시스템에 너무 많은 대화형 작업이 존재하면 그들이 모든 CPU 시간을 소모하게 되고 실행 시간 작업은 CPU 시간을 할당받지 못함으로써 계속 작업을 실행하지 못하고 기아 상태가 발생

스케줄러를 자신에게 유리하게 동작하도록 프로그램을 다시 작성할 수 있음

프로그램을 타임슬라이스가 다 끝나기 바로 직전에 짧은 입출력을 주도록 프로그램을 재작성하면 규칙 4b에 따라 해당 프로그램은 CPU 점유가 긴 작업임에도 높은 우선순위를 점유한다.

프로그램은 시간 흐름에 따라 특성이 변한다. CPU 위주 작업이 대화형 작업으로 바뀔 수 있다.

대화형 작업과 같은 우선 순위가 될 수 없는 문제로 반응 시간에 문제가 생긴다.

해결 방안

해결안 1 : 우선 순위의 상향 조정

규칙 5 : 일정기간 S가 지나면 시스템의 모든 작업을 최상위 큐로 이동시킨다.

image

기존의 스케줄러가 왼쪽, 규칙 5를 적용한 스케줄러가 오른쪽.

일정시간 S가 지나면 스케줄러는 모든 작업을 가장 우선 순위가 높은 큐로 이동 시킨다.

부두 상수 (voo-doo constants)라고 불리는 S의 길이에 따라 S길이가 너무 길 경우 긴 작업 시간을 가진 작업은 기아 상태에 빠지고 S길이가 너무 짧을 경우 짧은 입출력을 대응할 시간을 사용할 수 없게 된다.

해결안 2 : 더 나은 시간 측정

각 우선 순위 큐별 다른 타임 슬라이스 할당 및 관리.

우선 순위가 높은 큐는 보통 짧은 타임 슬라이스가 주어지고 이 큐는 대화형 작업으로 구성되며, 결국 이 작업들을 빠르게 교체하는 것이 의미가 있다. 반대로, CPU 중심의 오래 실행되는 작업들은 낮은 우선순위 작업들로 할당 되며 긴 타임 슬라이스가 적합하다.

FreeBSD의 스케줄러는 작업의 현재 우선 순위를 계산하기 위하여 프로세스가 사용한 CPU 시간을 기초로 한 공식을 사용한다.

CPU 사용은 시간이 지남에 따라 감쇠되어 이 장에서 설명한 방식과는 다른 방식으로 우선순위 상향을 제공한다.

View on GitHub