CPU 스케줄링

CPU를 효율적으로 사용하는 방법

Intro

CPU 스케줄링은 CPU를 효율적으로 사용하기 위한 방법이다. CPU 스케줄링 알고리즘은 다음과 같은 요소를 고려해야 한다.

1. CPU Utilization

   • CPU 이용률은 가능한 최대로 유지해야 한다.
   • 이론상 0% ~ 100% 사이의 값을 가진다. 실제로는 40% ~ 90% 사이의 값을 가진다.

2. Throughput

   • 단위 시간 당 완료된 프로세스의 수
   • 긴 프로세스의 경우 특정 시간 동안 하나의 프로세스만 완료될 것이고, 짧은 프로세스의 경우 특정 시간 동안 더 많은 프로세스가 완료될 것이다.

3. Turnaround Time

   • 프로세스 실행에 소요되는 시간
   • 프로세스가 생성된 시간부터 완료되기까지의 시간이다.
   • Turnaround Time = Completion Time - Arrival Time

4. Waiting time

   • Ready 큐에서 프로세스가 대기한 총 시간
   • 스케줄링 알고리즘은 이 값에 영향을 미친다.

5. Response time

   • 첫 응답이 시작되는 데까지 걸리는 시간
   • 반응속도가 중요한 어플리케이션에서 중요하게 측정된다.

CPU 스케줄링 알고리즘은, CPU 이용률, 단위 시간 당 완료된 프로세스 수를 최대화하며, 프로세스 실행에 소요되는 시간, 기다리는 시간, 첫 응답까지의 시간을 최소화하는 방향으로 설계되어야 한다.

Preemptive vs Non-preemptive

CPU 스케줄링에는 선점 스케줄링과 비선점 스케줄링이 있다.

선점 스케줄링 (Preemptive)

선점 스케줄링은 현재 CPU 코어에서 실행중인 프로세스가 다른 높은 우선순위를 가진 프로세스에 의해 중단될 수 있는 방식이다. 스케줄러가 주기적으로 타이머 인터럽트 등의 방식을 사용하여 현재 실행중인 프로세스를 중단시키고 다른 프로세스를 실행시킨다.

선점 스케줄링은 응답 시간을 예측 가능하게 한다. 하지만 프로세스가 자주 전환되며 오버헤드가 발생할 수 있다.

비선점 스케줄링 (Non-preemptive)

비선점 스케줄링은 현재 실행중인 프로세스가 자발적으로 종료하거나 I/O 작업 등으로 대기할 때까지 실행되는 방식이다. 다른 프로세스가 강제로 CPU를 점유할 수 없다.

구현이 단순하고 오버헤드가 적으며, 한 번 CPU를 할당 받은 프로세스가 일관되게 실행된다는 장점이 있다. 하지만 긴급한 작업을 바로 처리할 수 없으며, CPU 자원을 효율적으로 사용하지 못하는 경우가 있다.

CPU scheduling algorithms

먼저 CPU 스케줄링으로 해결하려는 문제는 ready 큐 내의 어떤 프로세스에게 CPU 코어를 할당할 것인가이다. 아래에서는 CPU 스케줄링 알고리즘을 싱글 코어 CPU임을 가정하고 평균 대기 시간을 비교해본다.

평균 대기 시간은 각 프로세스의 (큐 도착 시간 - 시작 시간)을 모두 더해 평균 낸 값이다.

1) First-Come, First-Served (FCFS)

First-come, First-served 알고리즘은 ready 큐에 도착한 순서대로 CPU를 할당하는 방법이다. 식당에서 먼저 온 손님에게 먼저 음식을 제공하는 것과 같다.

이러한 특성 때문에 FIFO(First-in, First-out) 큐로 구현된다.

구현이 쉽지만, 평균 대기 시간이 길어지는 단점이 있다. 이유는 호위 효과 때문인데, 먼저 도착한 프로세스의 실행 시간이 긴 경우 다른 모든 프로세스가 대기해야 하기 때문이다. 이로 인해 평균 대기 시간은 늘어난다.

FCFS 알고리즘은 비선점 방식의 알고리즘이다. 빠르고 일관성 있는 응답이 중요한 경우에는 적합하지 않을 수 있다.

2) Shortest-Job-First (SJF)

Shortest-Job-First 알고리즘은 실행 시간이 가장 짧은 프로세스에게 CPU를 할당하는 방식이다. 만약 두 프로세스의 실행 시간이 같다면 FCFS 방식으로 처리한다.

프로세스가 다음과 같은 순서로 도착했다고 가정해보자. 괄호 안 숫자는 실행 시간이다. P1(6), P2(8), P3(7), P4(3)

SJF 알고리즘은 다음과 같이 실행된다.

1. P4(3)이 먼저 실행된다.
2. P1(6)이 실행된다.
3. P3(7)이 실행된다.
4. P2(8)이 실행된다.

평균 대기 시간은 (0 + 3 + 9 + 16) / 4 = 7이다.

만약 FCFS 방식으로 실행한다면

1. P1(6)이 먼저 실행된다.
2. P2(8)이 실행된다.
3. P3(7)이 실행된다.
4. P4(3)이 실행된다.

평균 대기 시간은 (0 + 6 + 14 + 21) / 4 = 10.25이다.

이처럼 SJF 방식은 평균 대기 시간을 줄일 수 있다. 하지만 실제 시스템에서는 프로세스의 실행 시간을 정확히 예측하기 어렵기 때문에 사용하기 어렵다.

따라서 근사치를 예측해 수정하는 방식으로 구현되기도 한다. 측정한 이전 실행 시간을 지수평균하여 예측하는 것이다.

SJF 알고리즘 스케줄링은 선점, 비선점 모두 가능하다. 선점 방식에서는 이전 프로세스가 실행되는 동안 더 짧은 실행 시간의 프로세스가 ready 큐에 도착하면 선점된다. 선점 방식의 SJF 알고리즘의 경우 shortest-remaining-time-first 알고리즘이라고도 한다.

선점 방식의 SJF 알고리즘으로 실행해보자. 괄호 안은 각각 (도착시간, 실행시간)이다. P1(0, 8), P2(1, 4), P3(2, 9), P4(3, 5)

1. 다른 프로세스가 없어서 P1(0, 8)이 먼저 실행된다.
2. P2(1, 4)가 도착했다. P1(0, 8)의 남은 실행 시간은 7이다. P2(1, 4)의 실행 시간은 4이다. P2(1, 4)가 실행된다.
3. P3(2, 9)가 도착했다. 남은 시간은 각각 P1 = 7, P2 = 3, P3 = 9이다. P2(1, 4)가 실행된다.
4. P4(3, 5)가 도착했다. 남은 시간은 각각 P1 = 7, P2 = 2, P3 = 9, P4 = 5이다. P2(1, 4)가 실행된다.
5. P2(1, 4)가 계속 실행되다가 t_5에 종료됐다.
6. 남은 시간은 각각 P1 = 7, P3 = 9, P4 = 5이다. P4(3, 5)가 실행된다.
7. P4(3, 5)가 계속 실행되다가 t_10에 종료됐다.
8. 남은 시간은 각각 P1 = 7, P3 = 9이다. P1(0, 8)이 실행된다.
9. P1(0, 8)이 계속 실행되다가 t_17에 종료됐다.
10. 남은 시간은 각각 P3 = 9이다. P3(2, 9)가 실행된다.

평균 대기 시간은 [(10 - 1) + (1 - 1) + (17 - 2) + (5 - 3)] / 4 = 6.5이다.

3) Round Robin (RR)

RR 알고리즘은 FCFS에 선점이 추가된 방식이다. time quantum 혹은 time slice라고도 하는 시간 단위로 프로세스를 실행한다. 보통 10 ~ 100ms 정도의 시간 단위를 사용한다. FIFO 큐를 이용하고, 새로운 프로세스가 ready 큐에 도착하면 큐의 끝에 추가된다.

만약 해당 프로세스의 CPU 이용률이 1 단위 시간보다 작은 경우, 해당 프로세스는 자발적으로 CPU를 반납한다. 반대로 1 단위 시간보다 큰 경우, 해당 프로세스는 interrupt되고, ready 큐의 끝에 추가된다.

n개의 프로세스가 있고, q만큼의 단위 시간이 있으면 각 프로세스는 q만큼의 시간을 할당받는다. 최대 대기 시간은 (n - 1) * q를 넘지 않기 때문에 일관된 응답 시간을 확보할 수 있다.

RR 방식의 평균 대기 시간은 주로 긴 편이고, 1 단위 시간 이상으로 연속으로 할당받는 프로세스는 없기 때문에 RR 알고리즘은 선점 알고리즘이다. 만약 단위 시간이 너무 크면 FCFS와 유사한 결과를 보인다. 반대로 단위 시간이 너무 작으면 프로세스를 전환하는 비용이 증가한다. 따라서 적절한 단위 시간을 선택하는 것이 중요하다.

이를 위해 RR 알고리즘에서는 프로세스 전환 시간보다 시간 할당량이 더 커야 한다. 보통 10 ~ 100ms 정도의 단위 시간과 10ms 정도의 프로세스 전환 시간을 사용한다.

처리 시간 역시 시간 할당량의 크기에 좌우된다. 시간 단위가 충분히 커서 한 프로세스가 한 단위 시간 내 종료될 수 있는 경우 처리시간은 줄어든다. 반대로 시간 단위가 작으면 프로세스 전환이 더 많이 필요하고, 평균 처리 시간은 증가한다. 단 시간 단위가 증가해도 항상 평균 처리 시간이 감소하는 것은 아니다. (너무 크면 FCFS로 퇴보)

지금까지의 best practice로는 프로세스의 80%가 시간 단위 내에 끝내도록 단위를 설정하는 것이다.

4) Priority

자체적으로 설정한 우선순위에 따라 프로세스를 실행하는 방식이다. 우선순위는 정수로 표현되며, 작은 숫자가 더 높은 우선순위를 의미한다. 우선순위가 같은 경우 FCFS 방식으로 처리한다.

SJF 방식도 우선순위 스케줄링의 일종으로 볼 수 있다. 실행 시간이 짧은 프로세스에게 더 높은 우선순위를 부여하는 것이다.

우선순위는 내/외부적으로 정의한다.

• 내부 기준

  • 시간 제한
  • 메모리 요구량
  • 사용한 파일 수
  • IO대 CPU 비율

• 외부 기준 (OS 외부에서 기준이 정해짐)

  • 프로세스 중요도
  • 비용
  • 작업 후원 부서
  • 정치적 요인

우선순위 스케줄링도 SJF처럼 선점일수도 비선점일수도 있다. 선점 방식의 경우 우선순위가 높은 프로세스가 ready 큐에 도착하면 현재 실행중인 프로세스를 중단시키고, 비선점의 경우 현재 프로세스를 종료하지는 않고 도착한 프로세스를 ready 큐의 가장 앞에 위치시킨다.

5) Multilevel Queue

멀티레벨 큐는 우선순위마다 다른 큐를 운영하는 방식이다. 만약 같은 우선순위의 여러 프로세스가 있다면 RR 방식으로 처리한다. 이 방식은 프로세스를 타입에 따라 개별 큐로 운영하기 위해 사용할 수 있다. 실시간 성이 중요한 프로세스, 시스템의 프로세스 등 우선순위가 다른 프로세스를 구분하여 운영할 수 있다.

이로 인해 큐마다 다른 스케줄링 알고리즘을 운영할 수 있다. 예를 들어 사용자 상호작용 프로세스는 RR 방식을, 시스템 프로세스는 FCFS 방식을 사용할 수 있다.

큐의 우선순의에 따른 고정적 우선권을 부여할 수도 있고, 큐 별로 시간을 배분해 운영할 수도 있다.

6) Multilevel Feedback Queue

실행시간 동안 하나의 큐에만 위치하는 멀티레벨 큐 알고리즘과 다르게 멀티레벨 피드백 큐 알고리즘에서는 프로세스의 큐 간 이동이 가능하다. CPU burst의 특성에 따라 프로세스를 구분하며, 적은 CPU time을 갖는 프로세스가 더 높은 우선순위로 배정된다. 이때도 aging 기법을 통해 큐에서 너무 오래 대기한 프로세스의 우선순위를 높여준다.

예시로, 0 ~ 2의 큐가 있다. 낮은 숫자일수록 우선순위가 높다.

1. 가장 먼저 큐0에 있는 프로세스가 RR 방식으로 실행된다.
2. 큐0의 프로세스가 모두 실행되거나, 주어진 time quantum 내에 모두 실행되지 못하면 실행 흐름은 큐1로 넘어간다.
3. 큐1이나 큐2에서 실행되고 있어도 큐0에 새로운 프로세스가 도착하면 선점된다.

보통 8ms 이하의 CPU burst를 갖는 프로세스가 높은 우선순위를 가진다.

Thread scheduling

보통의 현대 OS가 스케줄링하는 것은 프로세스가 아닌 커널 레벨 스레드다. 유저 레벨 스레드는 스레드 라이브러리에 의해 관리되며, 커널은 그 존재를 알지 못한다. 유저 레벨 스레드가 CPU에서 실행되기 위해서는 LWP를 통해 커널 레벨 스레드와 매핑되어야 한다.

Process contention scope (PCS)

PCS는 유저 레벨 스레드를 스케줄한 프로세스 내 스레드 간 CPU core 경쟁이다. Many-to-one이나 many-to-many 모델을 구현한 시스템에서는 스레드 라이브러리가 유저 레벨 스레드를 가용 LWP에 스케줄한다.

높은 우선순위를 가진 스레드가 먼저 스케줄링 되며, 실행중인 스레드에 대한 선점이 이루어질 수 있다.

System contention scope (SCS)

SCS는 시스템 내 전체 스레드 간 CPU core 경쟁이다. 스레드 라이브러리가 유저 레벨 스레드를 LWP에 스케줄 했다면, OS는 LWP의 커널 레벨 스레드를 물리적인 CPU core에 스케줄해야 한다. One-to-one 모델을 사용하는 시스템에서는 SCS만을 사용한다.

Multi-Processor Scheduling

Multiple Processor Scheduling Approaches

만약 여러 CPU가 가용하다면, 각 CPU가 감당하는 부하를 공유할 수 있지만 스케줄링은 더 복잡해질 것이다. 다음은 멀티프로세서 시스템에서의 CPU 스케줄링 접근법이다.

Asymmetric Multiprocessing

프로세서가 비대칭적으로 Master / Others로 나뉜다. 모든 스케줄링에 대한 결정은 마스터 서버라 불리는 하나의 프로세서에서 내린다. 나머지는 유저 코드만 실행한다.

Symmetric Multiprocessing (SMP)

각 프로세서가 스스로 스케줄링한다. 스레드를 관리하기 위해 공통의 ready 큐를 사용할 수도 있고, 프로세서 별로 하나의 ready 큐를 가질 수도 있다.

1. 공통의 ready 큐

   • 같은 큐를 공유하기 때문에 Race condition이 발생할 수 있다.
   • 서로 다른 프로세서가 하나의 스레드를 스케줄하지 않아야 하고, 큐에서 스레드가 없어지지 않도록 보장해야 한다.
   • 일종의 locking을 통해 race condition을 예방할 수 있다.

2. 프로세서별 ready 큐

   • SMP를 지원하는 대부분의 시스템의 접근 방식이다.
   • 캐시 메모리를 더 효율적으로 사용할 수 있다.
   • 작업 부하가 큐마다 다를 수 있다는 문제가 있어서 균형을 맞추는 알고리즘이 사용된다.

Multicore Processors

SMP를 지원하는 시스템은 여러 물리 프로세서를 제공하여 여러 프로세스가 병렬로 실행될 수 있게 한다.

대부분의 현대 컴퓨터 하드웨어에서는 하나의 칩에 여러 개의 코어를 장착하며, 각 코어는 독립적으로 구조적 상태를 갖기 때문에 OS 입장에서 여러 개의 논리적인 CPU가 있는 것처럼 보인다.

Memory stall

프로세서가 메모리에 접근할 때에는 data를 받을 때까지 많은 시간을 낭비한다. 최대 50%의 시간을 대기에만 낭비한다. 이 상황을 타개하기 위해 현대 하드웨어는 Multithreaded processing core로 디자인된다.

위와 같이 둘 이상의 하드웨어 스레드를 운영하면 한 스레드가 메모리를 기다리는 동안 다른 스레드로 전환하여 작업을 처리할 수 있다. OS는 하드웨어 스레드를 소프트웨어 스레드를 실행하는 논리적인 CPU로 간주하고 스케줄링한다.

이것을 Chip Multithreading (CMT) 라고 한다. 만약 프로세서에 4개의 컴퓨팅 코어가 있고, 각 코어에 2개의 하드웨어 스레드가 있으면 OS 입장에서는 8개의 논리적 CPU가 있는 것과 같다.

Context Switching

1. Coarse-grained Multithreading
   • Memory stall과 같은 긴 이벤트 발생 전까지는 한 코어에서 실행한다.
   • 스레드를 전환하는 데 비용이 들기 때문에 이 방법을 선택한다.
2. Fine-grained Multithreading
   • 세밀한 단위로 전환한다.
   • 구조적 설계에 스레드 교환 회로를 포함하기 때문에 비용이 적다.

스케줄링의 두 단계

CMT를 구현해도 프로세싱 코어는 하나의 하드웨어 스레드만 실행할 수 있다. 캐시/파이프라인과 같은 물리적 자원이 하드웨어 스레드 간 공유되어야 하기 때문이다. 따라서 멀티스레드와 멀티코어 프로세서 모델에서는 두 단계의 서로 다른 스케줄링이 필요하다.

1. Software thread 선택
   • OS가 각 하드웨어 스레드에서 어떤 소프트웨어 스레드가 실행될지 결정한다.
   • OS가 스케줄링 알고리즘을 선택한다.
2. Hardware thread 선택
   • 각 코어에서 어떤 하드웨어 스레드가 실행될지 결정한다.
   • 간단한 RR 방식으로 스케줄링할 수도 있고,
   • 이벤트 발생에 따른 urgency 값을 고려해 스케줄링할 수도 있다.

1단계의 OS 스케줄러가 프로세서의 자원공유 정보를 안다면 효과적으로 스케줄링할 수 있다. 만약 자원을 공유하는 두 소프트웨어 스레드가 다른 코어에서 실행된다면 자원 공유로 인해 실행이 느려질 수 있다.

Load Balancing

SMP 시스템에서는 여러 개의 프로세서를 사용하는 이점이 극대화 될 수 있도록 작업 부하를 적절히 배분해야 한다. 그렇지 않으면 하나 이상의 프로세서가 유휴 상태일 때 다른 프로세서는 부하가 클 수 있다.

로드 밸런싱을 통해 작업부하가 균등배분되도록 할 수 있다. 이는 각 프로세서별로 자신의 ready 큐를 갖는 시스템에서만 필요하다. 공통의 ready 큐를 운영하는 시스템에서는 불필요하다.

다음과 같은 기준으로 부하가 균등배분 되었는지 판단한다.

1. 큐 내 스레드의 개수
2. 큐 내 스레드의 우선순위 분포

Load Balancing Approaches

1. Push migration

   • 특정 태스크가 주기적으로 프로세서별 부하를 검사한다.
   • 균등배분 상태가 아니라면 스레드를 이동(move, push)시켜 부하를 분산시킨다.

2. Pull migration

   • 유휴 상태의 프로세서가 부하가 많이 걸린 프로세서로부터 태스크를 가져온다(pull).

Push, pull migration은 상호 배타적이지 않으며, 두 방법이 주로 동시에 구현된다.

Processor affinity (선호도)

스레드가 특정 프로세서에서 실행될 때 연속적인 메모리 접근은 캐시 메모리에서 처리된다. 이는 warm cache라고도 한다.

만약 로드 밸런싱으로 인해 스레드가 다른 프로세서로 이동한다면 이전 프로세서의 캐시 메모리는 invalidate되고, 새 프로세서의 캐시가 채워진다. 캐시를 무효화/재생성하는 연산은 많은 비용이 들기 때문에 대부분의 SMP를 지원하는 OS가 스레드 이전을 최소화한다.

스레드 큐의 구성도 프로세서 선호도에 영향을 준다.

1. 공통의 ready 큐
   • 스레드는 임의의 프로세서에서 실행될 수 있기 때문에 새로운 프로세서에 스케줄 될 때 캐시가 지워진다.
2. 프로세서별 ready 큐
   • 스레드는 항상 같은 프로세서에서 실행되기 때문에 warm cache의 내용을 활용한다.

프로세서 선호도는 soft/hard affinity로 나뉘며, 많은 시스템이 두 방식을 모두 지원한다.

1. Soft affinity
   • OS가 한 프로세스가 한 프로세서에서 실행되도록 노력한다. 하지만 로드 밸런싱 등으로 스레드가 이동할 가능성이 있다.
2. Hard affinity
   • system call을 통해 프로세스가 실행될 수 있는 프로세서의 집합을 지정한다. 특정 프로세서에서 실행되도록 보장한다.

Heterogeneous Multiprocessing (HMP)

지금까지는 모든 코어가 기능 면에서 동일한 예시만을 살펴보았지만, HMP에서는 각 코어가 기능적으로 다를 수 있으며, 스레드가 특정 목적으로 특정 코어에서 실행될 수 있다.

HMP의 의도는 작업의 특정 요구에 기반해 코어를 할당함으로써 전력 소비를 더 잘 관리할 수 있도록 하는 것이다. 실제 예시로 큰 코어와 작은 코어를 모두 운영하는 방법이 있다. 작은 코어는 고성능을 요구하지 않지만 오래 실행해야 하는 태스크를 담당하고, 큰 코어는 고성능이 요구되지만 짧은 시간 실행해야 하는 태스크를 담당한다.

Real-time CPU Scheduling

실시간 시스템의 스케줄링은 크게 soft/hard 로 나뉜다.

Soft

• 실시간 프로세스가 언제 스케줄 되는지 보장하지 않는다.
• 우선순위 기반으로 스케줄 된다는 것만 보장한다.

Hard

• 작업의 데드라인 내 서비스를 보장한다
• 데드라인 이후의 서비스는 서비스 받지 않은 것과 같다.

Minmizing Latency

실시간 시스템은 이벤트를 중심으로 운영된다. 시스템은 이벤트가 발생하는 것을 기다리며, 이벤트는 HW와 SW 모두에서 발생한다.

• SW 예시: 타이머 만료
• HW 예시: 원격제어차량의 장애물 감지

시스템은 최대한 빨리 이벤트에 응답해야 하며, 이벤트 발생 시점과 시스템의 응답 시점 간 차이를 Event latency라고 한다.

각 이벤트는 서로 다른 지연시간 요구사항이 있다. 어떤 이벤트는 약간의 지연을 허용하지만, 어떤 이벤트는 즉각적인 응답이 중요하다. 자동차 ABS는 즉각 응답이 중요한 예시다. 몇 ms만 늦어도 자동차는 통제 불능 상태가 된다. 반면 비행기 레이더 제어는 몇 초 정도의 지연을 허용한다.

실시간 시스템의 성능에는 두 가지 지연시간이 영향을 준다.

1. Interrupt latency
2. Dispatch latency

1. Interrupt latency

Interrupt latency는 interrupt 발생 시점과 Interrupt Service Routine (ISR) 실행 시점의 차이다. Interrupt가 발생하면 OS는 실행 중이던 명령을 완료하고 interrupt type을 결정한다. 또 현재 프로세스의 상태를 저장하고, ISR을 이용해 interrupt를 처리한다. 이 과정에서 Interrupt latency가 발생한다.

Interrupt latency에 큰 영향을 주는 것은, 커널 데이터가 업데이트 되는 동안 interrupt가 비활성화되는 시간이다. 따라서 실시간 시스템에서는 interrupt가 비활성화 되는 시간이 짧아야 한다.

2. Dispatch latency

Dispatch latency는 dispatcher가 한 프로세스를 멈추고 다른 프로세스를 시작하기까지 걸리는 시간이다. 이는 Context-switch time이기도 하다. Hard 실시간 시스템인 경우 dispatch latency가 몇 ms 이내이며, dispatch latency를 최소화하는 효과적인 방법은 선점형 커널을 사용하는 것이다.

Dispatch latency는 confilct phase와 dispatch phase로 나뉜다. Conflict phase에서는 기존 프로세스에 대한 선점과 자원해제가 이루어지며, dispatch phase에서는 우선순위가 높은 프로세스를 CPU에 스케줄한다.

Priority-based Scheduling

선점 및 우선순위 기반 스케줄링은 soft real-time을 제공한다. 데드라인 내에 서비스를 제공하려면 추가적인 스케줄링 기법이 필요하다. 우선순위 기반 스케줄링을 위해 실시간 프로세스는 다음과 같은 특성을 지닌다.

1. Periodic
   • 프로세스는 일정 주기로 CPU를 요구한다.
2. Announce deadline
   • 프로세스는 스케줄러에게 자신의 데드라인 요구사항을 알려야 한다.

스케줄러는 다음과 같은 승인 제어 알고리즘을 통해 스케줄링 한다.

1. 프로세스가 시간 내에 완료할 수 있다면 승인한다.
2. 시간 내에 완료할 수 없다면 거절한다.

Rate-monotonic (RM) Scheduling

RM 알고리즘은 정적 우선순위 정책 기반의 선점 알고리즘이다. 우선순위는 주기 길이의 역으로 산정된다. 주기가 짧을수록 우선순위가 높아진다 ( 1 / period ).

RM 예제

주기적 프로세스 처리 시간은 각 CPU burst 시간과 같다고 가정하고, CPU를 차지한 시간은 프로세스의 CPU burst 시간과 같다고 가정해보자.

프로세스 P1과 P2가 있다.
주기 p1 = 50, p2 = 100.
처리시간 t1 = 20, t2 = 35이다.

이때 CPU 이용률은 P1 = 20/50 = 0.40, P2 = 35/100 = 0.35로 총 75%이다.

P1의 주기가 50으로 더 짧기 때문에 높은 우선순위를 가진다. P1이 높은 우선순위를 가짐에도 P2가 먼저 시작하면 어떻게 될까?

P2는 0부터 t2(35)만큼 실행된다. 이후 P1가 35부터 t1(20)만큼 실행된다. P1의 데드라인은 다음 주기 시작 전까지이기 때문에 P1은 데드라인을 맞추지 못한다 (55에 종료).

다시 P1이 먼저 시작하는 경우를 살펴보자.

P1은 0부터 t1(20)만큼 실행된다. P2는 20부터 t2(35)만큼 실행된다. 하지만 50에 P1의 주기가 돌아오기 때문에 P2의 실행은 5만큼을 남긴 채 P1에게 선점된다. P1이 다시 t1(20)만큼 실행된다. 시간은 70이고, P2의 데드라인인 100에 도달하지 않았다. P2의 남은 5가 실행된다. 75에 모든 실행이 완료된다. P1과 P2가 공통으로 시작하는 다음 주기인 100에 실행이 재개된다.

RM 결론

RM 스케줄링은 최적의 솔루션이다. 즉 프로세스 집합을 RM 알고리즘으로 스케줄 할 수 없다면 정적 우선순위를 부여하는 다른 어떤 알고리즘으로도 스케줄 할 수 없다. 그러나 RM 알고리즘에는 다음과 같은 한계가 존재한다.

1. CPU 이용률의 한계로 CPU 자원을 항상 최대화 할 수 없다.
2. 최악의 경우 N개의 프로세스를 스케줄링 할 때 CPU 이용률은 N(2^(1/2) - 1)이다.

Earliest-Deadline-First (EDF) Scheduling

EDF 알고리즘은 동적 우선순위 정책 기반 선점 알고리즘이다. 프로세스의 데드라인에 따라 동적으로 우선순위가 부여된다. 데드라인이 이르면 우선순위가 높아진다.

프로세스는 실행 가능한 상태가 되면 시스템에 데드라인을 알려야 한다. 이때 프로세스의 우선순위가 데드라인 기반으로 조정된다.

EDF 예제

프로세스 P1과 P2가 있다.
주기 p1 = 50, p2 = 80.
처리시간 t1 = 25, t2 = 35이다.

P1의 데드라인은 50, 100, 150, 200, ... P2의 데드라인은 80, 160, 240, 320, ...이다.

P1이 먼저 실행되는 상황을 살펴보자. P1은 0부터 t1(25)만큼 실행된다. P2는 25부터 t2(35)만큼 실행된다. RM 방식에서는 50 시간에 P1이 P2를 선점하지만, EDF에서는 50 시간에 P2의 데드라인은 80, P1의 데드라인은 100으로 데드라인이 임박한 P2가 계속 실행된다.

P2는 60에 실행이 완료되고, P1이 t1(25)만큼 실행된다. 80 시간에 P2의 주기가 돌아왔다. 하지만 P1의 데드라인은 100, P2의 데드라인은 160으로 데드라인이 임박한 P1의 실행이 이어진다.

P1은 85에 실행이 완료되고 P2가 t2(35)만큼 실행된다. 100 시간에 P1의 주기가 돌아왔다. P1의 데드라인은 150이고, P2의 데드라인은 160이기 때문에 P2의 실행은 P1에게 선점된다.

100부터 125까지 P1이 실행되고, 이후 P2가 남은 20만큼 실행되어 145에 실행이 완료된다. P1의 다음 주기인 150까지 10 시간 만큼은 유휴 상태가 된다.

EDF 결론

EDF 스케줄링은 프로세스가 주기를 갖거나 CPU burst 시간이 상수일 필요가 없다. 단지 실행 가능할 때 스케줄러에게 데드라인을 알리는 것이 중요하다. 이 알고리즘은 이론적으로 각 프로세스의 데드라인을 만족시키므로 최적의 솔루션이다. 하지만 실제로는 프로세스 간 context-switching, interrupt 처리로 인해 CPU 이용률 100%는 불가능하다.

Proportional Share Scheduling

Proportional Share 알고리즘에서는 모든 응용이 총 시간 T를 할당받아 실행된다. 하나의 응용이 N 시간을 할당받으면 N/T 시간이다.

Proportional Share 예제

총 시간 T는 100이다. P1 = 50, P2 = 15, P3 = 20 시간을 할당받았다. P1 = 50%, P2 = 15%, P3 = 20%의 CPU 이용률이 보장한다.

Proportional Share 결론

이 알고리즘도 우선순위 기반 알고리즘처럼 승인 제어 정책을 적용한다. 만약 요청한 프로세스에게 가용 시간이 남아있으면 승인하고, 그렇지 않다면 거절한다.