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

* 본 글은 '운영체제(Operating System: Concepts) 9th edition'의 내용과 2021학년도 1학기에 수강한 '운영체제' 과목 강의 내용을 함께 정리하여 작성하였습니다.

 

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

---

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

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

 

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. 계산 수행, 입출력 실행, 메시지 송수신 등)

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

 

실시간 태스크는 작업들의 연속을 말하며, (a sequence of similar jobs)

주기적(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) 스케줄링이 존재한다.

 

Rate-Monotonic(RM) 스케줄링

선점 가능한 정적 우선순위 정책을 이용하여 주기 태스크들을 스케줄 하는 방식이다.

 

기준 : 주기

각각의 주기 태스크들은 시스템에 진입하게 되면 주기에 따라서 우선순위가 정해지는데,

주기가 짧은 태스크에게는 높은 우선순위, 주기가 긴 태스크에게는 낮은 우선순위를 부여한다.

 

CPU를 더 자주 필요로 하는 태스크에게 더 높은 우선순위를 주는 것이고

이 우선순위는 변화하지 않고 고정된다. (정적 우선순위 스케줄링)

 

---

[ 예시 ]

 

두 프로세스 P1과 P2가 있다고 하자.

각 프로세스의 마감시간은 다음 주기가 시작하기 전까지이다.

 

	P1	P2
주기	p1 = 50	p2 = 100
수행시간	t1 = 20	t2 = 35

 

먼저 두 프로세스 모두가 마감시간을 충족하도록 스케줄링이 가능한 지부터 확인해야 한다.

 

P1의 CPU 이용률 = 20/50 = 0.40

P2의 CPU 이용률 = 35/100 = 0.35

* CPU 이용률 = t/p

 

총 CPU 이용률은 0.40 + 0.35 = 75%가 되므로 두 프로세스 모두 마감시간을 충족시키는 것이 가능하다.

 

 

1. P2의 우선순위가 P1보다 높다고 가정할 경우

 

P1은 시간 35에 시작하여 55에 수행이 끝나는데, 마감시간은 50이다.

해당 스케줄러는 P1의 마감시간을 만족시키지 못했다.

 

 

2. RM 스케줄링을 사용할 경우

P1의 주기가 P2보다 짧기 때문에 P1의 우선순위가 P2보다 높다.

 

 

P1과 P2의 마감시간이 모두 지켜지는 것을 볼 수 있다.

 

---

하지만 CPU 이용률에는 한계가 있기 때문에 CPU 자원을 최대화해서 사용하는 것은 불가능하다.

 

RM 스케줄링에서 n개의 프로세스를 스케줄 하는 데 있어서 아래의 관계를 만족하면 스케줄링이 가능한 것이다.

 

CPU 이용률의 상한 값은 약 69%가 되며,

 

 

위에서의 예시를 확인해보면 해당 관계를 만족하는 것을 볼 수 있다.

 

 

---

아래는 RM 스케줄링에서 스케줄링을 보장할 수 없는 경우(deadline missing)에 대한 예시이다.

 

	P1	P2
주기	p1 = 50	p2 = 80
수행시간	t1 = 25	t2 = 35

 

P1의 주기가 P2보다 작으므로, 우선순위는 P1이 P2보다 높다.

 

하지만 총 CPU 이용률을 계산해보았을 때는 약 94%이다.

CPU 이용률의 상한값 83%를 넘기 때문에 두 태스크 모두 마감시간을 지킬 수 있을지는 보장할 수가 없다.

 

 

아래 그림에서 시간 80을 확인해보면, P2가 마감시간을 지키지 못했음을 확인할 수 있다.

 



 

Earliest-Deadline-First(EDF) 스케줄링

선점 가능한 동적 우선순위 정책을 이용하여 주기 태스크들을 스케줄 하는 방식이다.

 

기준 : 마감시간

마감시간까지 남은 시간이 짧은 태스크의 작업이 높은 우선순위를 가지며,

우선순위는 새로 실행 가능하게 된 프로세스의 마감시간에 맞춰서 동적으로 조정된다.

 

RM 스케줄링과는 다르게 프로세스들이 주기적일 필요가 없으며 CPU 할당 시간도 상수값으로 정해질 필요가 없다.

단, 프로세스가 실행 가능해질 때 자신의 마감시간을 스케줄러에게 반드시 알려주어야 한다.

 

 

단점 : 과부하 시, 도미노 현상(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

 

 

---

[ 예시 ]

 

두 프로세스 P1과 P2가 있다고 하자.

각 프로세스의 마감시간은 다음 주기가 시작하기 전까지이다.

 

	P1	P2
주기	p1 = 50	p2 = 80
수행시간	t1 = 25	t2 = 35

 

EDF 스케줄링의 수행은 다음과 같이 이루어진다.

 

 

---

EDF 스케줄링에서 n개의 프로세스를 스케줄 하는 데 있어서 아래의 관계를 만족하면 스케줄링이 가능한 것이다.

즉, EDF 스케줄링에서는 이론적으로 CPU 이용률이 100%가 될 수 있어 최적의 스케줄링이라는 것이다.

하지만 실제로는 프로세스 사이 또는 인터럽트 핸들링 때의 문맥 교환 비용 때문에 100%의 CPU 이용은 어렵다.

 

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

1. RM 스케줄링

 

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

 

2. EDF 스케줄링

 

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