포스트

운영체제 14. 실시간 스케쥴링이 무엇일까

게시
By 신희곤
12 분읽는 시간
운영체제 14. 실시간 스케쥴링이 무엇일까

실시간 스케쥴링이 언제 필요한가?

미사일 제어 시스템과 같이 계산 시간을 엄격하게 지켜야 하는 시스템에서 실시간 스케쥴링이 필요하다. 그러나 일반 OS에서도 적당한 실시간 스케쥴링이 필요할 때도 있다.

따라서 실시간 시스템을 연성 실시간 시스템, 경성 실시간 시스템으로 분류한다. 연성 실시간 시스템(Soft real-time system)은 실시간 프로세스는 우선권 정도만 부여받고, 제한시간 내에 실행해준다는 보장을 해주지 않는다. 평범한 OS에 해당한다. 경성 실시간 시스템(Hard real-time system)은 실시간 프로세스의 제한 시간을 엄격히 지키는 것을 보장한다.

실시간 태스크의 스케쥴링 시간을 제한 시간 내에 끝내도록 어떻게 보장해주는가?

실시간 시스템이란 미사일이나 시뮬레이션과 같이 현실세계와 상호작용하는 시스템에서 주로 사용된다.

Pasted image 20250428152737.png

이런 시스템에선 센서를 통해 외부 정보를 입력받고, 그 정보를 프로세스(태스크)에서 처리하여 외부 환경과 연결된 기계 장치 등을 동작시킨다. 이것이 한번의 루프로 동작한다. 매 루프당 처리하는 단위작업을 Job이라 한다. Job은 작업을 수행하기 위해 필요한 자원(파일, 공유 변수, 동기화 요소 등)과 타이밍 파라미터를 속성으로 갖는다.

즉, 실시간 태스크란 매 루프마다 Job을 계속 반복하는 것과 같다. Task는 주기적인 Task와, 주기적이지 않은 Task로 나뉜다. 주기적인 Task \((p,t)\)는 다음과 같은 속성을 가진다.

  • 주기(period): \(p\)
  • 수행 시간(execution time): \(t\)
  • 데드라인(deadline): \(d\)
  • 이용율(Utilization): 한 주기에서 사용하는 비율. \(U\equiv\frac{t}{p}\)
  • 빈도(Rate): 단위 시간당 실행되는 Job의 빈도. 주기의 역수와 같다. \(R \equiv \frac{1}{p}\)

Job은 Deadline 전까지 또는 다음 주기가 오기 전까지 반드시 끝내야한다. 그리고 각 Job은 Deadline, 수행 시간이 제각각 다르다. 즉 Job의 Deadline, 수행 시간을 고려하여 동일 시간 가장 많은 Job을 처리해야 한다. 이것이 실시간 스케쥴링의 목적이다.

실시간 스케쥴링 알고리즘으로 무엇이 있을까?

RM (Rate Monotonic) Scheduling

주기가 짧은 순서대로 Job을 처리하는 방법이다. 즉, Period가 짧은 Job일 수록 높은 우선순위를 갖는다.

선점을 허용한다. 즉, 주기가 긴 Task의 Job을 돌리다가, 주기가 짧은 Task의 Job이 생긴다면 선점하여 먼저 처리한다.

[!example] \(P_{1}(p=50, t=20)\), \(P_{2}(p=100, t=35)\)인 프로세스를 RM 돌리면 다음과 같이 수행된다.{title}

Pasted image 20250428154524.png

[!question] 만약 Gantt Chart로 보이라 하면 어떻게 그리지?{title}

Pasted image 20250620190814.png

칸이 주어진 표를 그리고, CPU를 부여한 Task의 칸을 색칠하면 된다.

EDF(Earliest Deadline First) Scheduling

Deadline이 가장 가까운 Task에게 우선순위를 주는 방법이다. Deadline은 동적으로 달라질 수 있으므로, 동적 우선순위 스케쥴링 방법으로 분류된다.

선점을 허용한다. 태스크 주기가 다시 도래했거나, 새로운 프로세스가 진입한 경우에 선점이 발생할 수 있다.

[!example] \(P_{1}(p=50, t=25)\), \(P_{2}(p=80, t=35)\)인 프로세스를 EDF 돌리면 다음과 같이 수행된다.{title}

Pasted image 20250428155620.png

데드라인이 명시되어있지 않으므로, \(\text{(주기 시작 시간 + 주기)}\)가 곧 데드라인이다.

\(T=0\)일 때 P1과 P2의 \(d\)는 각각 50, 80이다. 따라서 P1이 먼저 수행된다. \(T=25\)일 때 P1이 종료되었으므로 남은 P2를 수행하면 된다. \(T=50\)일 때 P1의 주기가 도래했다. 선점되는가? P1과 P2의 \(d\)는 각각 \(100\), \(80\)이다. 따라서 P2가 계속 실행되어야 한다. P2가 끝나고, P1이 수행된다. \(T=80\)일 때 P2의 주기가 도래했다. 선점되는가? P1과 P2의 \(d\)는 각각 \(100, 160\)이다. 따라서 P1이 계속 실행된다. \(T=100\)일 때 P2가 실행되다 P1의 주기가 도래했다. 선점되는가? P1과 P2의 d는 각각 \(150, 160\)이다. 따라서 P1에 의해 선점된다.

Task Set의 모든 Task의 데드라인을 지킬 수 있을지 말지 미리 알 수 있을까?

임의의 Task Set이 주어지면, 항상 모든 Task의 마감기한을 지킬 순 없다. 그 여부를 미리 알 수 있을까? 알 수 있다. 그 조건을 Utilization Bound라고 한다.

RM의 Utilization Bound
\[\sum_{i} U_{i} \leq n (2^{1/n}-1)\]

\(U_{i}\)는 Task \(i\)의 이용율 \(\frac{t}{p}\)와 같다. \(n\)은 총 Task 개수와 같다. 위 조건이 만족되지 않으면 Deadline Missing이 발생한다.

if \(n\to \infty\)라면, 우변은 \(0.693147\dots\)와 같다.

[!example] \(T_{1}(4,1)\), \(T_{2}(5,1)\), \(T_{3}(10,1)\){title}

\[\sum_{i}U_{i} = \frac{1}{4} + \frac{1}{5} + \frac{1}{10} = 0.55\] \[n(2^{1/n} - 1) = 3(2^{1/3} - 1) \simeq 0.78\]

\(0.55 \leq 0.78\)을 만족하므로, RM으로 스케쥴링 가능하다.

EDF의 Utilization Bound
\[\sum U_{i} \leq 1\]

이때 \(p_{i}\)와 \(d_{i}\)가 같다고 가정한다. 주기와 데드라인이 같은 경우.

과부화되면 Domino Effect (도미노 효과)가 발생할 수 있다. 한번 미싱되기 시작하면 연쇄적으로 Deadline missing가 일어나며, 최종적으로 아무 Task도 완수할 수 없게 된다. 따라서 이를 해결하려면 제일 안 중요한 Task를 하나 제외하는게 낫다.

[!question] RM도 도미노 이펙트가 발생할 수 있지 않은가?{title} 그렇지 않다. 주기가 짧은 Task는 계속 선점되어 반드시 완수되기 때문이다.

RM과 EDF 중 무엇이 더 좋은가?

Utilization Bound가 EDF가 더 널널하니 EDF가 무조건 더 좋은 것 아닌가?

RM은 구현이 단순하다. 주기가 고정되어 있어 예측이 용이하고, 예상 결과가 정확하다. 따라서 무기쪽에서 RM을 더 선호한다. 다만 CPU 이용률이 높지 않다.

EDF는 동적 우선순위 스케쥴링이기 때문에, 예측하기가 어렵다. 과부하시 도미노 현상이 발생한다. 그러나 CPU 이용률이 높다. 현실적으로 딜레이 때문에 100%는 못씀

[!NOTE] TMI{title} 제일 많이 쓰는 경성 실시간 운영체제는 VxWorks라고 한다. (8~90%) 리눅스에선 POSIX로 연성 실시간 스케쥴링을 지원한다.

실시간 시스템의 최적화 방법

시스템은 일반적으로 실시간으로 발생하는 Event를 기다린다. Event가 발생하면, 시스템은 가능한 빨리 응답하고 그에 맞는 동작을 수행해야 한다.

event가 발생해서, 그에 맞는 서비스가 수행될 때까지의 시간을 event latency라고 한다. event latency는 interrupt latency와 dispatch latency 두가지가 존재한다.

(1) interrupt latency

Pasted image 20250428151929.png

event가 발생하는 것은 interrupt로 알아챌 수 있다. CPU에 interrupt가 들어온 시점부터 ISR이 실행되기 전까지의 delay가 interrupt latency라고 한다. 이는 사실상 고정값이다.

(2) dispatch latency

Pasted image 20250428152142.png

기존의 프로세스를 중지시키고 다른 프로세스를 실행시키는데 걸리는 시간이 dispatch latency이다.

dispatch latency는 충돌과 dispatch에 의해 결정한다. 충돌이란, 비선점 커널에서 발생한다. 실시간 프로세스에게 선점하여 바로 실행할 수 없기 떄문에,

dispatch는 무엇인가? 스케쥴링을 통해 제어권을 넘겨주는 것을 의미한다. 이때 충돌로 인해 dispatch latency가 길어질 수 있다. 충돌은 두가지 요소가 존재한다.

먼저 비선점 커널인 경우, 선점하지 못한다. 따라서 기존의 프로세스가 끝날 때까지 기다려야 한다. 그만큼 latency이 발생한다. 이는 선점형 커널로 최소화 가능하다.

또는 우선순위가 낮은 프로세스가 자원(뮤텍스, 세마포어)을 선점하고 있으면, 우선순위가 높은 프로세스는 자원이 낮은 프로세스가 반환할 때까지 대기해야 한다. 그 대기시간 만큼 latency가 발생한다.

IT, 운영체제