[Chapter 5. CPU 스케줄링] 실시간 시스템과 실시간 스케줄링 (RM, EDF)

본 정리는 운영체제(Operating System: Concepts) 9th edition과 22학년도 1학기 건국대학교 운영체제 수업을 바탕으로 하고 있습니다.

 

 

실시간 시스템 (Real-Time System)

---

실시간 시스템에서는 작업 수행이 요청되었을 때 이를 제한된 시간(엄격한 마감시간 즉, deadline) 안에 처리하여 결과를 내주어야 한다.

ex) 항공기 미사일 제어, 과학 실험, 로봇 등등

이는 연성 실시간 시스템과 경성 실시간 시스템으로 분류할 수 있다.

 

1. 연성 실시간 시스템 (Soft Real-Time System)

실시간 프로세스가 실시간이 아닌 프로세스들에 우선권을 가진다는 것만 보장하며,

이것이 스케줄 되는 시점에 관해서는 아무런 보장이 없다. (마감 시간(deadline)을 만족하는 것이 확률로만 존재)

 

2. 경성 실시간 시스템 (Hard Real-Time System)

태스크는 마감시간까지 반드시! 서비스를 받아야 한다.

마감 시간이 지난 이후에 서비스를 받는 것은 서비스를 전혀 받지 않는 것과 동일한 결과를 낳는다.

 

 

지연 시간 최소화 (Minimizing Latency)

시스템은 일반적으로 실시간으로 발생하는 사건(event)를 기다린다.

 

사건은 소프트웨어적으로 발생할 수 있으며, (ex. 타이머의 만료)

하드웨어적으로도 발생할 수 있다. (ex. 원격으로 제어되던 장치가 방해물을 만났을 경우)

 

사건 지연 시간(event latency)이란, 사건이 발생하여 그에 맞는 서비스가 수행될 때까지의 시간을 말한다.

 

 

시스템은 사건이 발생했다면 가능한 한 빨리 그에 응답을 하고 그에 맞는 동작을 수행해야 하는데

두 가지 유형의 지연시간이 실시간 시스템의 성능을 좌우한다.

 

 

1. 인터럽트 지연시간 (Interrupt Latency)

CPU에 인터럽트가 발생한 시점부터 해당 인터럽트 처리 루틴이 시작하기까지의 시간을 말한다.

 

인터럽트 발생 후 해당 인터럽트 서비스 루틴(ISR)을 사용하여 인터럽트를 처리하기 전까지 아래의 항목들을 전부 수행해야 하는데,

이들을 수행하는 데 걸리는 시간이 인터럽트 지연시간에 포함된다.

 

1. 수행 중인 명령어를 완수
2. 발생한 인터럽트의 종류를 결정
3. 현재 수행중인 프로세스의 상태를 저장

 

인터럽트 지연시간에 영향을 주는 요인 중 하나는 인터럽트 불능 시간으로, 커널 자료구조를 갱신하는 동안 인터럽트가 불능케 되는 시간이다.

이 시간을 얼마나 줄이느냐에 따라 인터럽트 지연시간이 줄어들게 된다.

 

 

2. 디스패치 지연시간 (Dispatch Latency)

하나의 프로세스를 중지시키고 다른 프로세스의 수행을 시작하는 데까지 걸리는 시간을 말한다.

 

디스패치 지연 시간에 영향을 주는 충돌(conflic) 요소는 다음의 두 가지이다.

 

1. 커널에서 수행 중인 프로세스를 선점할 수 없는 경우 (비선점 커널 사용 시)

    → 이는 선점형 커널을 사용하는 것을 통해 최소화 가능하다.

 

2. 높은 우선순위의 프로세스가 필요한 자원을 낮은 우선순위 프로세스 자원이 선점하는 경우

    → 프로세스가 자원 사용을 마치고 release 할 때까지 대기하는 수밖에 없다.

 

 

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

실시간 운영체제의 가장 중요한 기능은

디스패치 지연시간을 최소화하고, 실시간 프로세스가 CPU를 필요로 할 때 곧바로 할당해주는 것이다.

 

따라서 실시간 운영체제의 스케줄러는 선점을 이용한 우선순위 기반의 알고리즘을 지원하는 것이 기본이다.

 

하지만 경성 실시간 시스템의 경우, 이 조치 만으로는 부족하며

보다 엄격한 요구사항을 만족하는 것을 보장해주어야 하기 때문에 부가적인 스케줄링 기법이 필요하다.

 

 

실시간 스케줄링 알고리즘들에 대하여 알아보기 전에,

스케줄링의 대상이 되는 태스크(프로세스)들의 특징을 먼저 알아보자.

 

 

실시간 태스크

작업(job) : 태스크의 단위작업이다. (ex. 계산 수행, 입출력 실행, 메시지 송수신 등)

작업을 진행하기 위해 필요한 자원들(파일, 공유 변수, 동기화 요소 등)과 타이밍 파라미터를 속성을 갖는다.

 

실시간 태스크는 작업들의 연속을 말하며,

주기적(Periodic)이거나 비주기적(Aperiodic) 일 수 있다.

 

주기적인 태스크일 경우, 프로세스들은 일정한 간격으로 CPU를 필요로 한다는 것이다.

각각의 주기 태스크들은 CPU 사용권을 얻었을 때마다 아래의 항목들이 정해져 있다.

 

1. 주기(Period) p (0 < p)

2. CPU로부터 반드시 서비스를 받아야 하는 마감 시간(Deadline) d

3. 고정된 수행 시간 = 최대 수행 시간(Execution time = CPU Burst Time) t (0 ≤ t ≤ d ≤ p)

 

 

CPU 이용률 (Utilization) U = t/p

빈도 (Rate) = 1/p

 

스케줄러는 주기, 마감시간, 수행시간 사이의 관계를 이용하여

마감시간과 주기적 프로세스의 실행 빈도에 따라 우선순위를 정하게 된다.

 

실시간 스케줄링 알고리즘

---

실시간 스케줄링은 동시에 여러 개의 실시간 태스크들이 존재할 경우, 각 태스크 간의 작업의 수행 순서를 정하는 것이다.

 

정적 우선순위 스케줄링(Static-priority scheduling) 방법에는 RM(Rate-Monotonic) 스케줄링이 존재하고,

동적 우선순위 스케줄링(Dynamic-priority scheduling) 방법에는 EDF(Earliest Deadline First) 스케줄링이 존재한다.

 

 

RM(Rate-Monotonic) 스케줄링

선점 가능한 정적 우선순위 스케줄링 방법이다.

주기적 태스크들에 대하여 주기를 기준으로 우선순위를 결정한다. → 더 짧은 주기의 태스크에게 높은 우선순위를 부여한다.

 

예를 들어, P1프로세스가 50의 주기 20의 burst time / P2프로세스가 100의 주기 35의 burst time을 갖는다고 해보자.

 

그렇다면 RM 스케줄링에 의하면 무조건 짧은 주기의 태스크에 높은 우선순위를 부여하므로, P1이 높은 우선순위를 갖고 먼저 수행되게 될것이다.

 

아래 그림처럼 수행되게 된다.

그림에서 볼 수 있듯이 P2가 실행되다가도 선점 가능하기 때문에 P1프로세스의 주기가 되면 P1 프로세스가 CPU를 선점하여 우선 실행하는 것을 볼 수 있다.

 

RM을 사용하는 실시간 시스템은 유틸리티가 아래의 관계를 만족해야만 스케줄링이 가능하다.

∑U (CPU 이용률의 합) ≤ n (2^(1/n)-1)

위 유틸리티를 만족하지 않는 예를 한번 보자.

 

P1프로세스가 50의 주기 25의 burst time / P2프로세스가 80의 주기 35의 burst time을 갖는다고 해보자.

 

∑U = 25/50 + 35/80 = 0.9375

2 (2^(1/2)-1) ≈ 0.8284

위 예시와 같이 p2가 전부 수행되기도 전에 p1이 CPU를 선점해버리고, p2에서는 데드라인 80을 지킬 수 없게 된다.

 

이를 deadline missing이라고 한다.

 

 

 

EDF(Earliest-Deadline First) 스케줄링

선점형 동적 우선순위 스케줄링 방법이다.

Deadline까지 남은 시간이 짧은 태스크의 작업(job)이 높은 우선순위를 갖는다.

 

위 RM에서 Deadline Missing이 일어난 예시를 그대로, P1프로세스가 50의 주기 20의 burst time / P2프로세스가 80의 주기 35의 burst time을 갖는다고 해보자.

P1이 다시 실행되는 시점인 50에서 P1은 Deadline까지 50의 시간이 남았고, P2는 Deadline까지 30의 시간만 남았으므로, P2가 더 높은 우선순위를 갖고 실행된다.

 

EDF를 사용하는 실시간 시스템은 유틸리티가 아래의 관계를 만족하면 스케쥴링이 가능하다.

∑U(CPU 이용률) ≤ 1

 

이론적으로 CPU 이용률이 100프로이기 때문에 최적의 알고리즘이다.

 

당연한 이야기지만 CPU 이용률이 100프로가 넘으면  Domino effect라 불리는 과부하가 걸린다.

* 도미노 현상 : 주기의 길이 차이가 작은 경우 연속해서 deadline missing이 발생하는 것이다.

 

ex. T1(4, 3), T2(5, 3), T3(6, 3), T4(7, 3) 이렇게 4가지의 태스크가 존재할 경우 - 태스크(주기, 수행 시간)

총 CPU 이용률 = 3/4 + 3/5 + 3/6 + 3/7 = 1.25 > 1

 

 

RM 스케줄링 vs. EDF 스케줄링

1. RM 스케줄링

 

• 구현이 상대적으로 단순하다.
• 우선순위가 고정되기 때문에, 우선순위가 높은 태스크의 예측성(Predictability)이 좋다.
• CPU 이용률(Utilization)이 높지 않다.

 

2. EDF 스케줄링

 

• CPU 이용률이 이론적으로는 100%가 가능하여 최적의 스케줄링이다.
• 과부하 시에 도미노 현상 문제가 발생한다.