스케줄링_Real-Time Scheduling

Real Time System

 

Real Time System은 주로 임베디드 장치 안에서 주기적으로 반복되는 작업을 처리할 때 사용됩니다.

Real Time System의  3요소는 Running time(t), Deadline(d), Period(p)이며, Deadline을 꼭 지켜야 하는지 여부에 따라 다음과 같이 구분할 수 있습니다.

 

1) Hard real-time system: Deadline을 꼭 지켜야 하는 real-time system

2) Soft real-time system: Deadline을 지키지 않아도 치명적이지 않은 real-time system

 

 

그렇다면, 주기적으로 반복되는 프로세스를 스케줄링 하는 알고리즘들을 알아봅시다.

 

 

Static Priority Scheduling(Rate-Monotonic algorithm)

Static Priority. 정적인 우선순위가 무슨 말일까요? 프로세스들에게 바뀌지 않는 우선순위를 부여한다는 뜻입니다. 그럼 어떠한 기준으로 우선순위를 부여하는데?! Rate-Monotonic algorithm에서는 Rate(주기의 역수)를 기준으로 우선순위를 부여합니다.

 

예를 들어, P1의 주기와 실행시간이 각각 50, 20 / P2의 주기와 실행시간이 각각 100, 38 이라고 할 때, 

Rate(주기의 역수)는 p1이 더 크므로 항상 P1이 P2보다 먼저 스케줄링 됩니다.

 

가장 처음 P1이 들어와 20만큼의 시간동안 실행되고 이후 P2가 38만큼 실행되어야 하는데,

t = 50 일 때 P1이 선점하여 다시 스케줄링 되기 때문에 P2는 30만큼만 수행이 되고 P1이 끝난 뒤 나머지 8만큼 수행이 됩니다.

 

 

 

 

Static Priority의 경우 구현이 쉽지만 프로세스의 주기와 실행시간에 따라 Deadline miss가 발생한다는 단점이 있습니다.

 

예를 들어, P1의 주기와 실행시간이 각각 50, 25 / P2의 주기와 실행시간이 80, 35 라고 할 때,

P2는 남은 10만큼의 수행을 다음 주기(Deadline)이 돌아올 때까지 끝낼 수 없게 됩니다.

 

 

 

 

Dynamic Priority Scheduling(Earliest Deadline First algorithm)

Dynamic Priority. 동적인 우선순위. 프로세스들의 우선순위가 계속 바뀔 수 있다는 이야기입니다. EDF(Earliest Deadline First) algorithm은 지금 시점으로 부터 Deadline이 빠를 수록 높은 우선순위를 부여합니다.

 

예를 들어, P1의 주기와 실행시간이 각각 50, 25 / P2의 주기와 실행시간이 80, 35 라고 할 때,

처음 스케줄링 되는 시점에서 P1의 Deadline은 50만큼 남았고 P2의 Deadline은 80만큼 남았으므로 더 빠른 P1을 스케줄링 합니다. 

이후 P2를 스케줄링하여 수행하다가, P1의 주기가 다시 돌아오는 시점에 P1의 Deadline은 50만큼 남았고, P2의 Deadline은 30만큼 남았으므로 더 빠른 P2를 스케줄링 합니다. 

이후 P1를 스케줄링하여 수행하다가, P2의 주기가 다시 돌아오는 시점에 P1의 Deadline은 20만큼 남았고, P2의 Deadline은 80만큼 남았으므로 더 빠른 P1을 스케줄링 합니다.

 

 

 

 

이와 같이, Deadline이 더 앞에 있는 프로세스를 우선순위로 선점하여 스케줄링 하는 방식은 Deadline miss를 방지할 수 있습니다.