[운영체제] Chapter5.6 Real-Time CPU Scheduling

실시간 운영체제의 CPU 스케줄링은 특정 문제를 포함한다. 일반적으로, soft 실시간 시스템과 hard 실시간 시스템을 구분할 수 있다.

• Soft real-time system
  중요한 실시간 프로세스가 언제 스케줄링될지 보장하지 않고, 그 프로세스가 중요하지 않은 프로세스보다 우선적으로 처리될 것이라는 것만 보장.

• Hard real-time system
  더 엄격한 요구 사항을 가짐. task는 deadline까지 처리되어야 하며, 데드라인이 지난 후의 서비스는 서비스가 전혀 없는 것과 같음.

이 섹션에서는 소프트 및 하드 실시간 운영체제에서 프로세스 스케줄링과 관련된 여러 가지 문제를 살펴본다.

5.6.1 Minimizing Latency

실시간 시스템의 이벤트 기반 특성을 고려하자. 시스템은 일반적으로 실시간으로 이벤트가 발생하는 것을 기다린다. 이벤트는 타이머가 만료될 때와 같이 소프트웨어에서 발생하거나 원격 제어 차량이 장애물에 접근하는 것을 감지할 때와 같이 하드웨어에서 발생할 수 있다. 이벤트가 발생하면, 시스템은 가능한 빨리 응답하고 서비스해야 한다. event latency(이벤트 발생시간)은 이벤트가 발생한 후 서비스될 때까지 걸리는 시간이다. (그림 5.17) 일반적으로, 다른 이벤트는 다른 지연 시간 요구 사항을 가진다.

실시간 시스템의 성능에 영향을 미치는 지연 시간에는 두 가지 유형이 있다.

1. Interrupt Latency
   CPU에 인터럽트가 도착한 후부터 인터럽트를 서비스하는 루틴이 시작될 때까지의 시간.

인터럽트가 발생하면, 운영 체제는 먼저 실행 중인 명령을 완료하고 발생한 인터럽트의 유형을 확인해야 한다. 그 다음 특정 인터럽트 서비스 루틴(ISR, Interrupt Service Routine)을 사용하여 인터럽트를 서비스하기 전에 현재 프로세스의 상태를 저장해야 한다. 이러한 task를 수행하는 데 필요한 총 시간이 인터럽트 지연 시간이다.(그림 5.18)

실시간 운영 체제에서 인터럽트 지연시간을 최소화하여 실시간 task가 즉각적인 처리를 받는 것이 중요하다. 실제로, 하드 실시간 시스템의 경우, 인터럽트 지연 시간을 단순히 최소화하는 것이 아니라 이러한 시스템의 엄격한 요구 사항을 충족하도록 제한해야 한다.

인터럽트 지연에 기여하는 한 가지 중요한 요소는 커널 데이터 구조가 업데이트 되는 동안 인터럽트가 비활성화될 수 있는 시간이다. 실시간 운영 체제는 인터럽트가 매우 짧은 시간 동안만 비활성화되어야 한다.

2. Dispatch latency
   스케줄링 디스패처가 한 프로세스를 중지하고 다른 프로세스를 시작하는 데 필요한 시간

실시간 task를 제공하고 CPU에 즉시 엑세스하려면 실시간 운영 체제가 이 지연 시간을 최소화해야 한다. 디스페치 지연 시간을 낮게 유지하는 가장 효과적인 기술은 선점형 커널을 제공하는 것이다. 하드 실시간 시스템의 경우, 디스패치 지연 시간은 일반적으로 수 마이크로초 단위로 측정된다.

그림 5.19에서 디스패치 지연 시간의 구성을 보여준다.

conflict phase(충돌 단계)에는 두 가지 구성 요소가 있다.

1. 커널에서 실행 중인 모든 프로세스의 선점
2. 높은 우선순위 프로세스에 필요한 리소스를 낮은 우선순위 프로제스에서 해제

충돌 단계 이후, 디스패치 단계에서는 우선순위가 높은 프로세스를 사용가능한 CPU로 스케줄링한다.

5.6.2 Priority-Based Scheduling

실시간 운영 체제의 가장 중요한 특징은 프로세스가 CPU를 필요로 하는 즉시 실시간 프로세스에 응답하는 것이다. 결과적으로, 실시간 운영 체제의 스케줄러는 선점을 통한 우선순위 기반 알고리즘을 지원해야 한다. 우선순위 기반 스케줄링 알고리즘은 각 프로세스에 중요도에 따라 우선순위를 할당한다. 더 중요한 것은 task는 덜 중요하다고 여겨지는 task보다 더 높은 우선순위가 할당된다. 스케줄러가 선점을 지원하면, 더 높은 우선순위의 프로세스가 실행 가능해지면 현재 CPU에서 실행 중인 프로세스가 선점될 것이다.

선점형, 우선순위 기반 스케줄링 알고리즘은 섹션 5.3.4에서 자세히 설명되었고, 섹션 5.7에서는 Linux, Windows 및 Solaris 운영 체제의 소프트 실시간 스케줄링 예시를 나타낸다. 각 시스템은 실시간 프로세스에 가장 높은 스케줄링 우선순위를 할당한다.

선점적이고, 우선순위 기반 스케줄러를 제공하는 것은 소프트 실시간 기능만 보장한다는 것을 유의해야한다. 하드 실시간 시스템은 실시간 task가 데드라인 요구 사항에 따라 서비스 될 것임을 추가로 보장해야 하며, 추가 스케줄링 기능이 필요하다. 이 섹션의 나머지 부분에서, 하드 실시간 시스템에 적합한 스케줄링 알고리즘을 다룬다.

개별 스케줄러의 디테일을 살펴보기 전에, 스케줄링할 프로세스의 특정 특성을 정의해야 한다. 프로세스는 주기적이라고 간주된다. 즉, 일정한 간격(주기)로 CPU를 필요로 한다. 주기적 프로세스가 CPU를 얻으면, 고정된 처리 시간 t, CPU에서 서비스해야하는 데드라인 d, 주기 p가 있다. 세 가지의 관계는 0≥t≥d≥p로 포현할 수 있다. 주기적 task의 비율은 1/p이다. 그림 5.20은 시간에 따른 주기적 프로세스의 실행을 보여준다.

이 형태의 스케줄링에서 일반적이지 않은 점은 프로세스가 스케줄러 데드라인 요구 사항을 스케줄러에 알려야 한다는 것이다. 그런 다음, admission-control 알고리즘 기술을 사용하여, 스케줄러는 두 가지 중 하나를 수행한다. 프로세스를 허용하여 프로세스가 제 시간에 완료되도록 보장하거나, task가 데드라인까지 처리될 것이라고 보장할 수 없으면 요청을 불가능하다고 거부한다.

5.6.3 Rate-Monotonic Scheduling

rate-monotonic 스케줄링 알고리즘은 선점 기능이 있는 정적 우선순위 정책을 사용하여 주기적 task를 스케줄링한다. 우선순위가 낮은 프로세스가 실행 중이고, 우선순위가 높은 프로세스가 실행 가능해지면 우선순위가 낮은 프로세스를 선점한다. 시스템에 들어가면, 각 주기적 task는 주기에 따라서 역으로 우선순위가 할당된다. 주기가 짧을수록 우선순위가 높고, 주기가 길수록 우선순위가 낮다. 이 정책의 근거는 CPU를 더 자주 필요로 하는 작업에 더 높은 우선순위를 지정하기 위한 것이다. 또한, rate-monitonic 스케줄링은 주기적 프로세스의 처리 시간이 각 CPU 버스트에 대해 동일하다고 가정한다. 즉, 프로세스가 CPU를 얻을 때마가 CPU 버스트의 지속시간은 동일하다.

EX. 두 프로세스 P1과 P2
P1 : p1 = 50(주기), t1 = 20(처리시간)
P2: p2 = 100, t2 = 35

각 프로세스의 데드라인은 다음 주기가 시작되기 전에 CPU 버스트를 완료해야 한다.

프로세스의 CPU 사용률
Pi = ti / pi
P1 = 20 / 50 = 0.40
P2 = 35 / 100 = 0.35
total = 75%

따라서, 데드라인을 충족시키고 CPU에 사용 가능한 사이클을 남겨두는 방식으로 task를 스케줄링할 수 있을 것 같다.

P2에 P1 보다 더 높은 우선순위를 할당한다고 가정하면(그림 5.21), P2가 먼저 실행을 시작하고 시간 35에 완료된다. 이 시점에서 P1이 시작되고 시간 55에 CPU 버스트를 완료한다. 그러나 P1의 첫 번째 데드라인은 시간 50이었으므로 스케줄러는 P1이 데드라인을 놓치게 했다.

P1에 P2 보다 더 높은 우선순위를 할당하는 rate-monotonic 스케줄링을 사용한다고 가정한다. P1이 P2보다 주기가 짧기 때문이다. 그림 5.22에 나와 있듯이, P1이 먼저 시작해서 시간 20에 CPU 버스트를 완료하여 첫 번째 데드라인을 충족한다. P2가 이 지점에서 실행을 시작해서 시간 50까지 실행한다. 이때, CPU 버스트에 5밀리초가 남았지만, P1에 의해 선점된다. P1은 시간 75에서 CPU 버스트를 완료하고, 이 시점에서 스케줄러는 P2를 재개한다. P2는 시간 75에 CPU 버스트를 완료하고 첫 번째 데드라인도 충족한다. 시스템은 시간 100까지 유휴 상태이고, P1이 다시 스케줄링된다.

rate-monotonic 스케줄링은 최적으로 간주된다 프로세스 집합이 이 알고리즘에 의해 스케줄링될 수 없다면, 정적 우선순위를 할당하는 다른 알고리즘으로도 스케줄링될 수 없다는 점에서.

다음으로 rate-monotonic 알고리즘을 사용하여 스케줄링할 수 없는 프로세스 집합을 살펴본다.

EX. 두 프로세스 P1과 P2
P1 : p1 = 50(주기), t1 = 25(처리시간)
P2: p2 = 80, t2 = 35

rate-monotonic 스케줄링은 P1이 더 짧은 주기를 가지므로 더 높은 우선순위를 할당한다.

두 프로세스의 total CPU 사용률
(25/50) + (35/80) = 0.94

따라서 두 프로세스를 스케줄링해도 CPU에 6%의 사용 가능한 시간이 남는 것이 논리적으로 보인다. (그림 5.23)

처음에 P1이 시간 25에 CPU 버스트를 완료할 때까지 실행된다. 그런 다음 프로세스 P2가 실행을 시작하여 시간 50까지 실행되고, 이때 P1에 의해 선점된다. 이 시점에서 P2의 CPU 버스트에는 아직 10밀리초가 남는다. 프로세스 P1은 시간 75까지 실행된다. 결과적으로 P2는 시간 80에서 CPU 버스트를 완료해야하는 데드라인을 지난 시간 85에서 버스트를 완료한다.

최적임에도 불구하고, rate-monotonic 스케줄링에는 한계가 있다. CPU 사용률은 제한되어 있고, 항상 CPU 리소스를 완전히 최대화할 수 있는 것은 아니다. N개의 프로세스를 스케줄링하는 최악의 CPU 사용률은 N(21/N - 1)이다. 시스템에 프로세스가 하나 있을 때 CPU 사용률은 100%이지만 프로세스 수가 무한에 가까워질 수록 약 69%로 떨어진다. 프로세스가 두 개일때 CPU 사용률은 약 83%로 제한된다. 그림 5.21과 5.22에 스케줄링된 두 프로세스의 CPU 사용률을 합친 값은 75%이다. 따라서 rate-monotonic 스케줄링 알고리즘은 두 프로세스가 데드라인을 충족하도록 스케줄링하는 것이 보장된다. 그림 5.23에 스케줄링된 두 프로세스의 CPU 사용률을 합친 값은 약 94%이기 때문에, rate-monotonic 스케줄링은 두 프로세스가 데드라인을 충족하도록 스케줄링할 수 있음을 보장할 수 없다.

5.6.4 Earliest-Deadline-First Scheduling

Earliest-Deadline-First(EDF) 스케줄링은 데드라인에 따라 동적으로 우선순위를 할당한다. 데드라인이 빠를수록 우선순위가 높고, 데드라인이 늦을수록 우선순위가 낮다. EDF 정첵에 따라 프로세스가 실행 가능해지면 시스템에 데드라인 요구 사항을 알려야한다. 우선순위는 새로 실행 가능한 프로세스의 데드라인을 반영하도록 조정해야 할 수 있다.

EDF 스케줄링을 설명하기 위해, 다시 그림 5.23의 프로세스를 스케줄링한다. 이 프로세스는 rate-monotonic 스케줄링에서 데드라인 요구 사항을 충족하지 못했다. 이 프로세스의 EDF 스케줄링은 그림 5.24에 나타난다.

프로세스 P1은 가장 빠른 데드라인을 가지고 있으므로, 초기 우선순위가 P2 보다 높다. 프로세스 P2는 P1의 CPU 버스트가 끝날 때 실행을 시작한다. 그러나, rate-monitonic 스케줄링은 P1이 P2를 다음 주기 시작 시점인 50에서 선점할 수 있게 해주는 반면, EDF 스케줄링은 프로세스 P2를 계속 실행할 수 있게 해준다. P2는 다음 데드라인(시간 80)이 P1 (시간 100)보다 빠르기 때문에 P1보다 우선순위가 높다. 따라서 P1과 P2 모두 첫 번째 데드라인을 충족한다. 프로세스 P1은 다시 시간 60에서 실행을 시작하고 시간 85에서 두 번째 CPU 버스트를 완료하여 두 번째 데드라인 시간 100을 충족한다. P2는 이 시점에서 실행을 시작하지만 시간 100에서 다음 주기의 P1에 의해 선점된다. P2는 P1의 데드라인(시간 150)이 P2(시간 160)보다 빠르기 때문에 선점된다. 시간 125에서 P1은 CPU 버스트를 완료하고 P2는 실행을 재개하여 시간 145에서 완료하고 데드라인도 충족한다. 시스템은 시간 150까지 유휴 상태이며, 이때 P1 다시 한 번 실행되도록 스케줄링된다.

rate-monitonic과 달리 EDF 스케줄링은 프로세스가 주기적일 것을 요구하지 않으며, 프로세스가 버스트당 일정한 양의 CPU 시간을 요구할 필요도 없다. 유일한 요구 사항은 프로세스가 실행 가능해질 때 스케줄러에 데드라인을 알리는 것이다. EDF 스케줄링의 매력은 이론적으로 최적이라는 것이다. 이론적으로 각 프로세스가 데드라인을 충족하고 CPU 사용률이 100%가 되도록 프로세스를 스케줄링할 수 있다. 그러나 실제로, 프로세스 간 컨텍스트 스위칭 비용과 인터럽트 처리로 인해 이 수준의 CPU 사용률을 달성하는 것은 불가능하다.

5.6.5 Proportional Share Scheduling

Proportional share 스케줄러는 모든 애플리케이션에 T 공유를 할당하여 작동한다. 애플리케이션은 N 공유 시간을 받을 수 있으므로 총 프로세서 시간의 N/T를 갖게된다. 예를 들어, 총 T=100 공유를 세 프로세스 A, B, C에 분배한다고 가정한다. A는 공유 50, B는 공유 15, C는 공유 20을 할당받는다. 이 방식을 사용하면 A는 전체 프로세서 시간의 50%, B는 15%, C는 20%를 차지하게 된다.

Proportional share 스케줄러는 애플리케이션이 할당된 시간 공유를 받도록 보장하기 위해 admission-control 정책과 함계 작동해야 한다. admission-control 정책은 충분한 공유가 있는 경우에만 특정 수의 공유를 요청하는 클라이언트를 허용한다. 이 예시에서 총 100개의 공유 중 50+15+20=85개의 공유를 할당했다. 새로운 프로세스 D가 30개의 공유를 요청하면 admission controller는 D가 시스템에 진입하는 것을 거부한다.

5.6.6 POSIX Real-Time Scheduling

POSIX 표준은 실시간 컴퓨팅을 위한 확장인 POSIX.1b를 제공한다. 여기서, 실시간 스테드 스케줄링과 관련된 POSIX API 중 일부만 다룬다. POSIX는 실시간 스레드에 대한 두 가지 스케줄링 클래스를 정의한다.

• SCHED_FIFO
  FIFO 큐를 사용하여 선착순 정책에 따라 스레드를 스케줄링한다. 그러나, 우선순위가 같은 스레드 간에는 time slicing이 없다. 따라서 FIFO 큐의 앞에 있는 가장 우선순위가 높은 실시간 스레드가 종료되거나 차단될 때까지 CPU를 부여받는다.

• SCHED_RR
  라운드 로빈 정책을 사용한다. 우선순위가 같은 스레드 간에 time slicing을 제공한다는 점을 제외하고 SCHED_FIFO와 유사하다.

POSIX는 추가 스케줄링 클래스인 SCHED_OTHER를 제공하지만, 구현은 정의되지 않았고 시스템마다 다르게 동작할 수 있다.

POSIX API는 스케줄링 정책을 getting과 setting하기 위해 다음 두 함수를 지정한다.

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

두 함수의 첫 번째 매개변수는 스레드 속성 집합에 대한 포인터 이다. 두 번째 매개변수는 (1) 현재 스케줄링 정책으로 설정된 정수에 대한 포인터이거나 (2) pthread_attr_setschedpolicy
() 함수의 정수 값(SCHED_FIFO, SCHED_RR, SCHED_OTHER)이다. 두 함수 모두 오류가 발생하면 0이 아닌 값을 반환한다.

그림 5.25에서 이 API를 사용하는 POSIX Pthread 프로그램을 설명한다. 이 프로그램은 먼저 현재 스케줄링 정책을 결정한 다음 스케줄링 알고리즘을 SCHED_FIFO로 설정한다.