5.6 Real-Time CPU Scheduling

실시간 운영 체제에서 CPU 스케줄링을 보자. 기본적으로 실시간 아키텍처는 soft real-time system과 hard real-time system으로 구분하며, 소프트는 실시간 프로세스가 언제 스케줄링 될지에 대한 보장을 제공하지 않지만, hard는 실시간 프로세스가 언제 스케줄링될 지에 대해 엄격하게 지킨다. 따라서 작업이 반드시 정해진 시간안에 서비스 되어야 하는 것이다.

 

5.6.1 Minimizing Latency

 실시간 시스템에서 이벤트 기반의 특성을 고려해보면 시스템은 일반적으로 실시간 이벤트가 발생하기를 기다린다. 이벤트는 소프트웨어에서 발생할 수도 있고, 하드웨어에서도 발생할 수 있다. 원격 제어 차량이 장애물에 접근하고 있음을 감지하는 경우처럼 이벤트가 발생하면 시스템은 가능한 한 빨리 이에 응답하고 처리해야 한다. 이벤트가 발생하는 시점부터 이를 처리하는 시점까지의 경과시간을 event latency라고 부른다.

 보통 서로 다른 이벤트들은 서로 다른 latency 요구사항을 가지고 있다. 예를 들어, Antilock Brake System의 지연 시간 요구사항은 3에서 5 milliseconds로 바퀴가 미끄럼을 감지한 시점부터 ABS를 제어하는 시스템이 상황에 응답하고 제어가 완료될때까지 3-5 milliseconds가 주어지는 것이다. 실시간 시스템 성능에 영향을 미치는 이런 event latency는 두 가지가 있다.

1. Interrupt Latency
2. Dispatch Latency

 Interrupt Latency는 인터럽트가 CPU에 도착한 순간부터 그 인터럽트를 처리하는 루틴이 시작될 때까지의 기간을 의미한다. 인터럽트가 발생하면 운영 체제는 먼저 실행중인 명령어를 완료하고, 어떤 유형의 인터럽트가 발생했는지 확인한 후에 현재 프로세스의 상태(PCB)를 저장한 후에 특정 인터럽트 서비스 루틴(Interrupt Service Routine, ISR)을 사용하여 인터럽트를 처리한다. 이 모든 작업을 수행하는데 필요한 총 시간이 Interrupt Latency이다.

 실시간 운영 체제는 실시간 작업이 즉시적으로 주의를 받을 수 있도록 인터럽트 지연 시간을 최소화하는 것이 매우 중요하다. 인터럽트 지연에 영향을 미치는 것중 하나인 커널 데이터 구조가 업데이트 되는 동안 인터럽트가 비활성화될 수 있는 시간(intr_disable() 같은 것)이다. 실시간 운영 체제는 인터럽트가 매우 짧은 시간동안만 비활성화되도록 요구를 한다.

 이렇듯 스케줄링 디스패처가 하나의 프로세스를 멈추고 다른 프로세스를 시작하는 데 필요한 시간을 Dispatch Latency라고 한다. 실시간 작업에서 CPU를 즉시 접근을 할 수 있도록 실시간 운영체제는 이 지연시간을 최소로 해야 한다. 그러기 위해선 선점형 커널을 제공하는 것인데 hard real-time system에서는 dispatch latency가 일반적으로 몇 마이크로 초로 측정된다.

 dispatch latency의 conflict 가 발생하는 단계로는 두 가지가 있는데,

1. 커널에서의 어떤 프로세스의 선점
2. 낮은 우선순위의 프로세스가 높은 우선순위 프로세스에 의해 필요한 자원을 해제

 이런 conflict phase 후에 디스패치 단계에서 높은 우선순위 프로세스를 사용 가능한 CPU 스케줄링을 한다.

 

5.6.2 Priority-Based Scheduling

 실시간 운영체제의 가장 중요한 기능은 실시간 프로세스가 CPU를 필요로 할 때 즉시 응답하는 것이다. 따라서 실시간 운영 체제의 스케줄러는 선점 기능이 있는 우선순위 기반 알고리즘을 써야하며, 중요도에 따라 코어에 할당될 것이다. 더 중요한 작업은 덜 중요한 작업보다 더 높은 우선순위의 프로세스가 실행 가능해지면 선점될 것이다. 우선순위 레벨은 운영체제마다 나뉘어지는 정도가 다르기 때문에 설명은 생략한다.

 선점형 우선순위 스케줄링 만으로도 soft real-time system이 된다. 하지만 hard real-time system은 실시간 작업이 마감 기한에 맞춰서 서비스 되어야 하기 때문에, 추가적인 스케줄링이 필요하다.

 우선순위를 정하기 전에는 스케줄링 될 프로세스의 특성 정의가 필요한데, 프로세스는 주기적인 것으로 관리되어야 일정한 주기동안 CPU를 선점하게 되며, 다른 프로세스에게도 기회가 가게 된다. 여기서 주기는 고정 처리 시간 t, CPU에 의해 서비스되어야 하는 마감 기한 d, 그리고 주기 p를 가지게 된다. 보통 이 관계는 0 ≤ t ≤ d ≤ p로 표현되며, 주기적인 작업의 비율은 1/p로 나타낸다(밑 그림 참고).

 이 스케줄링 특징은 프로세스가 스케줄러에게 자신의 마감 기한을 요구사항으로 알려줄 수 있다는 것이다. 그 다음 수락 제어 알고리즘(admission-control algorithm)의 방법을 사용하여 스케줄러는 프로세스를 받아들여 다음 작업을 수행한다.

1. 해당 프로세스가 제시간에 완료될 것을 보장한다.
2. 해당 작업이 마감 기한에 맞춰 서비스 될 수 없다고 판단되면 요청을 거부하는 작업을 수행한다.

 

5.6.3 Rate-Monotonic Scheduling

 Rate-Monotonic Scheduling은 정적 우선순위 정책과 선점을 사용하여 주기적인 작업을 스케줄링한다. 낮은 주기를 갖는 작업일수록 더 높은 우선순위를 부여받으며, CPU burst 프로세스 일수록 더 높은 우선순위를 가진다는 것이다. 여기서 주기적인 프로세스의 처리 시간이 각 CPU 버스트마다 동일하다고 가정한다.

 위의 예시에서는 두 개의 프로세스 P1, P2 가 있는데, 두 프로세스의 주기는 각각 d1 = 50, d2 = 100이다. 처리 시간은 t1 = 20, t2 = 35 이며, 이는 모든 프로세스가 다음 주기가 시작되기 전에 CPU 활용을 끝내야 한다는 것이다. 프로세스들의 활용률을 해당 버스트와 주기의 비율인 t_i / p_i로 측정하게 되면 P1의 CPU 활용률은 20 / 50 = 0.4, P2는 35/100 = 0.35 이다. 총 CPU 활용률은 75% 이며, 이 수치는 모두 데드라인을 준수하면서도 CPU에 사용 가능한 사이클을 남길 수 있다는 뜻이다.

그럼에도 위의 사진은 P1의 데드라인을 놓치기 때문에 다른 스케줄링이 필요하다.

 Rate-Monotonic Scheduling을 사용해보자. P1의 주기가 P2보다 짧기 때문에 P1에게 더 높은 우선순위를 할당하는 비율-단조 스케줄링은 P1이 먼저 시작되고 처리시간이 20이므로 20에 끝이 나게 되며, 이때 P2는 자기의 처리시간인 35만큼 하게 되는데, 5를 다 못채우고 P1의 데드라인이 끝나고, P1이 더 우선순위가 높기 때문에 P1이 이를 선점하여서 다시 20의 처리를 하게 된다. 다 끝나면 다시 P2가 CPU를 사용하여 5만큼의 처리시간을 받아서 이용하게 된다.

 Rate-Monotonic Scheduling은 우선순위가 고정되어있는(상수인) 우선순위를 할당하기 때문에 주기적인 작업에 대해서만 우선순위가 할당되어서 작업의 주기가 짧을수록 해당 작업에게 더 높은 우선순위가 할당된다. 이 알고리즘으로 안되는 스케줄링은 다른 정적 알고리즘을 써도 스케줄링 할 수 없다. 따라서 효율적이며 매우 유용하다.

하지만 이도 예외가 있다. p1 = 50, t1 = 25, p2 = 80, t2 = 35라고 하자. 25/50 + 35/80 = 0.94 이고, 두 프로세스를 잘 스케줄링 하면 6%의 사용가능한 시간을 남길 수 있을 것이다. 하지만 위의 그림처럼 P2는 데드라인에 맞춰지지 않게 된다. 이는 이 다음 알고리즘 EDF에서 다시 다루자.

 비율-단조 스케줄링은 좋지만, CPU 활용률에 제한이 있다. N개의 프로세스를 스케줄링할 때 최악의 경우에는 CPU 활용률이 N(2^(1/N) - 1)을 가지게 된다. CPU 활용률은 100% 이지만, 프로세스 수가 무한대로 접근할수록 CPU 활용률은 약 69%로 감소하게 된다. 두 개의 프로세스의 경우 CPU 활용률은 약 83%로 제한된다.

 

5.6.4 Earliest-Deadline-First Scheduling

 Earliest-Deadline-First Scheduling은 데드라인에 따라 동적으로 우선순위를 할당한다. 데드라인이 더 이른 경우 우선순위가 높고, 늦은 경우 우선순위가 낮다. EDF에서는 프로세스가 실행 가능하면 시스템에 데드라인 요구사항을 알려줘야 한다. 새롭게 실행 가능해진 프로세스의 데드라인을 반영 하기 위해 우선순위를 조정해야 할 수 있다. 우선순위가 고정되어 있는 rate-monotonic과는 다르다.

 이전에 데드라인 요구사항을 충족시키지 못한 프로세스가 있었다. p1=50, t1 = 25, p2 = 80, t2 = 35이었다. P1의 데드라인이 가장 빠르기 때문에 1이 먼저 실행되고, P1의 CPU 버스트가 끝나면 그 뒤에 P2가 실행된다. P2가 실행되는 동안에 P1의 주기가 다 되어도 P2의 데드라인이 P1의 데드라인보다 더 빠르기 때문에 P2가 계속 선점을 하게 된다. P2의 CPU 버스트가 끝나면 P1이 실행되게 된다.

 rate-monotonic 알고리즘과 달리 EDF 는 주기적이거나 CPU 버스트 당 일정한 양의 CPU 시간을 필요로 하지 않아도 되며, 프로세스가 실행 가능해질 때 데드라인을 스케줄러에게 알리기만 하면 된다. EDF는 이론적으로는 최적이고, CPU 사용률이 100%가 될 수 있다는 장점이 있지만, 프로세스 간의 context switching과 interrupt latency로 인해 이러한 CPU 사용률 수준을 달성하는 것이 거의 불가능하다.

 

5.6.5 Proportional Share Scheduling

Proportional Share Scheduling은 모든 응용 프로그램 사이에 T 개의 share을 할당함으로써 작동하는데, 응용 프로그램은 N 개의 share을 할당받을 수 있고, 전체 프로세스 시간의 N / T의 비율을 확보할 수 있다. 예를들어서 T = 100개의 share가 3개의 프로세스 A, B, C 사이에 분배되는 경우를 보자. A는 50개의 쉐어를 할당받고, B는 15개, C는 20개를 할당받는다. 이 방식은 A가 50%, B가 15%, C가 20%를 사용할 수 있도록 보장한다.

 Proportional Share Scheduling은 모든 응용 프로그램이 할당된 시간 쉐어를 받도록 보장하기 위해 입장 제어 정책과 함께 작동한다. 입장 제어 정책은 요청된 특정 쉐어 수가 충분히 사용 가능한 경우에만 클라이언트를 입장시킨다. 예제에서는 총 100개의 쉐어 중 50+15+20 = 85의 쉐어를 할당했다. 새로운 프로세스 D가 30개의 쉐어를 요청하는 경우에는 입장을 거부하게 된다.

 

5.6.6 POSIX Real-Time Scheduling

 POSIX 표준에서 실시간 컴퓨팅을 위한 확장 기능인 POSIX.1b를 제공하며 실시간 스레드 스케줄링과 관련된 POSIX API를 다룬다. POSIX는 두 가지 스케줄링 클래스를 정의한다.

• SCHED_FIFO
• SCHED_RR

 SCHED_FIFO는 FIFO queue를 사용하여 선입선출 정책에 따라서 스레드를 스케줄링 한다. SCHED_RR은 라운드로빈 방식을 통해 동일한 우선순위에 대한 스레드간에 시간 분할을 제공한다.

• pthread_attr_getschedpolicy(pthread_attr_t *attr, int *policy)
• pthread_attr_setschedpolicy(pthread_attr_t *attr, int policy)

 두 함수를 통해 스케줄링 정책을 가져올 수 있고, 두번째 함수의 인자로 policy에 SCHED_FIFO, SCHED_RR, SCHED_OTHER 등을 사용할 수 있다.

 

 실제로 위 스케줄링들을 pintOS에서 나중에 해볼 것이다.