5.6 Real-Time CPU Scheduling

Info

해당 섹션에서는 RTOS(real-time operating system)에서 사용되는 ‘Soft Real-Time System’과 ‘Hard Real-Time System’ 두 가지 방식에 관련한 몇 가지 문제를 살펴본다.

Soft Real-Time System

해당 시스템은 ‘중요한(critical) 실시간 프로세스’의 실행 시기에 대한 엄격한 보장을 하지 않는다. 단지 중요하지 않은 프로세스보다 먼저 실행되는 것을 보장한다. 즉, 중요한 테스크(task)를 가능한 빨리 실행하려고 하지만, 정확한 실행시간을 보장하지는 않는다.

Hard Real-Time System

해당 시스템에서 각 테스크(task)는 명확한 데드라인(dead line)을 가지고 있고 해당 시간 내에 작업이 완료되어야 한다. 데드라인을 넘어간 테스크의 경우 시스템의 요구를 충족하지 못한 것으로 판단하고, 서비스가 완전히 실행되지 않은 것과 동일하게 동작한다.

여기서 말하는 RTOS는 window와 같은 GPOS(General-Purpose Operating System)와는 다른 운영체제 방식이다. RTOS는 주로 정해진 시간에 특정 작업을 완료하는 신뢰성이 높고 예측가능해야하는 시스템에 사용된다(주로 임베디드 시스템). 물론 GPOS가 RTOS에서 사용되는 일부 기능을 지원할 수 있다.

5.6.1 레이턴시(Latency) 최소화

실시간 시스템(real-time system)의 이벤트

일반적인 시스템은 실시간으로 발생하는 이벤트(event)를 감지한다.

이벤트는 크게 2가지 경우에서 발생한다.

• 소프트웨어(ex: 타이머 만료)
• 하드웨어(ex: 원격 제어 차량이 장애물에 접근하는 것을 감지할 때)

이벤트 레이턴시의 정의

이벤트가 발생한 때 부터 서비스가 동작할 때까지 시간의 경과를 ‘이벤트 레이턴시(event latency)’라고 한다.

일반적으로 이벤트가 다르면 레이턴시 역시 다르다.

인터럽트(interrupt) 레이턴시

인터럽트가 CPU에 도달한 시점부터 ‘ISR(interrupt service routine)’이 시작되는 시점까지의 시간을 의미한다.

인터럽트가 발생하면 운영체제는 수행중인 명령어를 완수하고 발생한 인터럽트의 종류를 결정한다. 그리고 해당 인터럽트에 해당하는 ‘ISR’(interrupt service routine)을 수행하게 된다.

조금 더 상세하게 과정을 보면, 받은 인터럽트를 ‘IVT(interrupt vector table)’를 통해서 확인하고, 여기에 매핑된 Interrupt handler(ISR)를 실행한다.

디스패치(dispatch) 레이턴시

스케줄링 디스패처(dispather)가 하나의 프로세스를 블록(block)시키고 다른 프로세스를 시작하는 데까지 걸리는 시간을 의미한다.

여기서 블록한다는 것은 다른 인터럽트를 차단한다는 의미이다.

디스패치 레이턴시는 총 2가지 과정으로 나누어 설명할 수 있다.

1. 충돌 단계(conflic phase)
2. 디스패치 단계(dispatch phase)

충돌 단계는 ’ISR’실행 이후 시스템이 다시 일반 태스크(프로세스)의 실행으로 돌아가기 전에, 스케줄러가 실행 대기 중인 태스크들의 우선순위를 평가하고, 어떤 태스크를 다음에 실행할지 결정하는 과정을 수행한다. 필요에 따라 낮은 우선 순위의 자원(resources)를 해제(Release)한다. 디스패치 단계는 이렇게 선택된 테스크로 전환하는 컨텍스트 스위칭을 수행한다.

Question

참고로 여기서 말하는 인터럽트는 우리가 일반적으로 아는 시그널과는 다르다. 먼저 시그널은 커널과 프로세스간에 일어나지만, 인터럽트는 CPU와 커널간에 발생한다. 또한 시그널은 ‘시그널 핸들러’를 통해서 개발자가 프로그램 내부에 정의하여 사용할 수 있지만, 인터럽트에서 사용되는 ISR의 경우에는 커널에 이를 직접 정의해야하기 때문에 커널 개발자가 아닌 이상, 정의하지 않는다. 위 설명에서 인터럽트의 종류를 결정한다고 했는데, 이는 CPU가 정해서 커널에 넘겨주는 동작을 의미한다. 그리고 설명대로 IVT은 해당 인터럽트에 따라서 ISR을 수행하게된다.

예시를 들어보면, 임의의 숫자를 0으로 나눈다면 ALU에서는 이를 수행하려다 실패하게 되고, 이를 커널에 보내게된다(인터럽트). 시그널은 파이프로 예시를 들어보면 SIGPIPE를 커널에 보내어 파이프 동작을 수행할 때, 프로세스에서 커널, 커널에서 다시 프로세스로 시그널이 보내지고 이를 처리함으로써 동작하게 된다.(시그널)

이러한 차이점으로 인해 인터럽트는 개념적으로 매우 중요한건 맞지만, 커널, 임베디드 개발자를 제외하고는 설계할 일이 거의 없을 것이다.

• https://en.wikipedia.org/wiki/Interrupt
• https://en.wikipedia.org/wiki/Interrupt_vector_table
• https://en.wikipedia.org/wiki/Interrupt_handler
• https://stackoverflow.com/questions/13341870/signals-and-interrupts-a-comparison

5.6.2 우선순위 기반 스케줄링(Priority-Based Scheduling)

실시간 운영 체제의 우선순위 기반 스케줄링

실시간 운영 체제에서는 프로세스가 CPU를 필요로 할 때 즉시 반응할 수 있어야한다.

이를 위해 우선순위 기반의 알고리즘을 사용하여 중요도에 따라 각 프로세스의 우선순위를 할당한다.

선점(preemption) 지원

운영체제에서 스케줄러가 선점 기능을 지원한다면, 더 높은 우선순위의 프로세스가 실행가능한 상태일 경우 현재 실행중인 프로세스는 선점됩니다.

여기서 선점(preemption)된다는 말은 실행중인 프로세스를 중단, 상태(state) 저장, 컨텍스트 스위칭(context switching), 우선순위와 실행주기 조정 등을 수행한 후에 즉각적으로 더 높은 우선순위의 프로세스를 실행시키는 일련의 과정을 의미한다.

Soft Real-Time vs Hard Real-Time

선점 가능한 우선순위 기반 스케줄링은 Soft Real-Time기능을 보장한다. 하지만 Hard Real-Time 시스템은 프로세스가 그들의 데드라인 요구를 충족하도록 추가적인 스케줄링 기능이 필요하다.

프로세스 특성 정의

실시간 시스템에서 스케줄링할 프로세스는 주기적이라고 간주된다. 이는 그들이 일정한 간격(주기)으로 CPU를 요구한다는 것을 의미한다. 그리고 각 프로세스는 고정된 처리 시간, 데드라인, 주기를 가진다.

$p$는 주기, $d$는 데드라인, $t$는 고정된 처리 시간을 의미한다. 테스크의 주기성은 $\frac{1}{p}$​를 가진다.

변동성이 적은 테스크의 경우 작업이 고정된 처리시간이 일정 구간에 수렴한다고 할 수 있으므로 고정된 시간이라고 하는 것 같다.

admission-control 알고리즘

프로세스는 스케줄러에게 자신의 ‘데드라인 요구 사항(deadline requirements)’을 알릴 수 있어야 한다.

스케줄러는 admission-control 알고리즘을 사용하여 프로세스가 시간 내에 완료될 수 있도록 승인하거나 데드라인을 충족할 수 없다고 판단되면 요청을 거절한다.

스케줄러가 프로세스에게 데드라인을 받고, 해당 알고리즘을 사용하여 프로세스를 스케줄 할지, 거절할기를 정하는 것 같다.

5.6.3 Rate-Monotonic Scheduling(RMS)

RMS 알고리즘의 정의

Rate-Monotonic Scheduling은 ‘주기적인 작업(periodic tasks)’을 ‘선점(preemption)’ 가능한 ‘정적 우선순위 정책(static priority policy)’을 사용하여 스케줄링하는 알고리즘이다.

작업의 우선순위는 그 주기의 역수에 기반하여 할당되며, 주기가 짧을수록 우선순위가 높아진다.

쉽게 말해서 고정적으로 프로세스 우선순위를 지정하는 방식이다. 주기가 짧을 수록 우선순위가 높고, 길수록 낮다. 이는 스케줄러에 의해서 자동으로 배정되며 할당 된 후에는 바뀌지 않는다.

스케줄링과 선점

낮은 우선순위의 작업이 실행 중일 때 더 높은 우선순위의 작업이 실행 가능해지면, RMS는 낮은 우선순위의 작업을 ‘선점’하고 높은 우선순위의 작업을 실행시킨다.

예시 - 1

$t$는 처리시간, $p$는 주기를 의미한다.

$p_1$의 CPU 사용량은 $\frac{t_1}{p_1}$로 $40$%, $p_2$는 $\frac{t_2}{p_2}$로 $35$% 를 가지게 된다. 총 $75$%의 사용량으로 넉넉하게 작업을 수행할 수 있을 것으로 기대된다.

하지만 $p_1$이 $50$의 주기를 가짐에 따라서 데드라인이 $50$으로 지정되고 $p_1$은 데드라인을 넘기게 된다.

예시일 뿐이지만 데드라인이 넘어갈 경우의 처리는 다양하다. soft real-time system에서 라면 어느정도 용인하고 넘어간 후, 주기를 조정할 수도 있다. 물론 용인하지 않을 수도 있다. 즉, 시스템이나 개발자의 설정에 따라서 다르다(설정할 수 있는 경우). 당연하게도 hard real-time system에서는 용인하지 않고 admission-control 알고리즘이 동작하여 스케줄 조차 되지 않을 것이다. 물론 admission-control 알고리즘이 동작하여 스케줄을 하지도 않을지 또한 모두 다르다.

하지만 위 예시에서 RMS 알고리즘을 사용할 경우 데드라인을 넘기지 않고 스케줄링 할 수 있다.

예시 - 2

위 예시에 대한 CPU 이용률은 $\frac{25}{50}+\frac{35}{80}=94$% 가 되어 모두 스케줄 할 수 있을 것으로 기대할 수 있지만, 그렇지 못하고 데드라인을 조금 넘기게 된다.

결론

예시들을 통해서 살펴보았듯 RMS는 최적의 기법이기는 하지만 많은 제약과 이용률에 한계가 있기 때문에 CPU 자원을 최대화하여 사용하는 것은 불가능하다.

RMS 알고리즘을 통해 $N$개의 프로세스를 스케줄 하는 데 있어 최악의 경우 CPU 이용률은 다음과 같다.

$$N(2^{\frac{1}{N}}-1)$$

해당 알고리즘은 RTOS에서 사용되기 때문에 ‘비실시간 프로세스’의 스케줄링과는 별개로 동작한다. 즉, GPOS에서는 지원하지 않는다.

5.6.4 Earliest-Deadline-First Scheduling(EDF)

정의

EDF 스케줄링 기법은 마감시간에 따라서 우선순위를 동적으로 부여한다. 마감시간이 빠를 수록 우선순위는 높아지고, 늦을수록 낮아진다.

RMS 와 달리 프로세스가 실행가능하게 되면 자신의 마감 시간을 알리고 스케줄러는 이를 토대로 우선순위를 재조정 한다.

장점

프로세스가 주기적일 필요가 없고, 실행 시간 또한 고정적일 필요가 없다.

또한 이론적으로 최적이라는 점이다. 모든 프로세스가 마감시간을 만족시키도록 스케줄 할 수 있고, CPU 이용률 또한 $100$%에 다다를 수 있다. (오버헤드 때문에 완전한 $100$%는 불가능하다)

이렇게 보면 EDF만 쓰면 될 것 같지만, 주기적이고 예측가능한 방식을 원할 경우에 RMS가 유용할 수 있다. 구현 또한 RMS가 더욱 간단하다고 한다.

5.6.5 Proportional Share Scheduling

비례(Proportional) 공유 스케줄링의 기본 원리

시스템은 T Time Share를 전체 응용 프로그램 사이에 할당한다.

각 응용 프로그램은 N 개의 Time Share를 받아, 전체 프로세서 시간의 N/T 비율을 가지게 된다.

시간 분할 할당 예시

총 T = 100개의 Time Share이 , A, B, C 세 프로세스에 각각 50, 15, 20개의 시간 분할이 할당된다면, T가 100 이므로 전체 프로세서 시간의 50%, B는 15%, C는 20%의 처리 시간을 보장받는다.

입장 제어 정책(Admission-Control Policy)

Proportional Share 스케줄러는 할당된 Time Share를 보장하기 위해 admission-control 정책과 함께 작동한다.

이 정책은 충분한 Time Share가 남아 있을 때만 특정 개수의 Time Share를 요청하는 클라이언트의 시스템 입장(entry)을 허용한다.

admission-control 예시

위의 예시에서 이미 85개(50 + 15 + 20)의 시간 분할이 할당되어 있다.

만약 새로운 프로세스 D가 30개의 Time Share를 요청할 경우, 총 할당 가능한 100개를 넘어서므로, 입장 제어자는 D의 요청을 거부한다.

미리 $T$라는 시간을 모둔 프로세스들에게 $N$개 만큼 나눠주고, 해당 비율에 맞는 처리 시간을 보장하는 개념이다. 이미 나눠준 것을 넘는 처리시간이 필요할 경우 admission-control 정책에 의해서 스케줄을 거부할 수 있도록 설계해야한다.

5.6.6 POSIX Real-Time Scheduling

Note

POSIX는 실시간 컴퓨팅용으로 POSIX.1b라는 확장을 제공한다. 해당 파트에서는 실시간 스레드 스케줄링과 관련한 POSIX API에 관해서 알아본다.

SCHED_FIFO

스레드를 선입 선출(FIFO) 큐를 사용하여, 먼저 온 순서대로 스케줄하는 정책이다.

가장 높은 우선순위를 가진 실시간 스레드가 CPU를 할당받아 실행을 마치거나 블록될 때까지 계속해서 CPU를 사용한다.

SCHED_RR

라운드 로빈(Round-Robin) 정책을 사용합니다. SCHED_FIFO와 유사하지만, 같은 우선순위를 가진 스레드들 사이에 시간 분할을 제공한다.

FIFO는 같은 우선순위여도 먼저 준비되어 실행된 스레드가 끝날 때 까지 블록하고, RR은 같은 우선순위가 준비될 경우 돌아가면서 스케줄한다. 물론 높은 우선순위의 스레드가 생길 경우 preemption한다.

이 외의 스케줄링 클래스

SCHED_OTHER라는 추가 스케줄링 클래스를 제공하지만, 이는 구현이 정의되지 않았으며 시스템별로 동작이 달라질 수 있다.

POSIX API의 스케줄링 관련 함수

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

1. 스레드의 속성 집합에 대한 포인터를 첫 번째 파라미터로 받는다.
2. 현재 스케줄링 정책을 나타내는 정수의 포인터를 두 번째 파라미터로 받는다. (정책을 받거나, 얻음)

두 함수 모두 에러가 발생하면 0이 아닌 값을 반환한다.