Scheduling of Reactive Systems

이 전 포스팅에서는 개별적인 잡들에 대한 스케줄을 다뤘다.

지금부터는 reactive system에 대한 스케줄링을 다뤄볼것이다.

이전에 task들의 종류에 대하여 다루었다.(Periodic, Aperiodic, Sporadic)

이런 task들의 대한 스케줄링은 개별적인 잡들의 스케줄링과는 다른 방법으로 접근해야한다.

---

Periodic Tasks

periodic task Ti는 일정한 간격을 두고 주기적으로 발생하는, 일정한 execution time과 relative deadline을 가진 잡들의 집합으로 볼 수 있다.

• Phase ϕi : Task Ti의 첫 번째 잡인 Ji,1의 release time ri,1. 즉 가장 처음 실행되어야 하는 잡이 등장하는 시간이다.
• Period pi : Task Ti에서 연속적으로 등장하는 잡들 사이의 일정한 간격.
• execution time ei : Task Ti에 속하는 모든 잡들의 공통적인 실행 시간.
• relative deadline Di : Task Ti에 속하는 모든 잡들의 공통적인 relative deadline.

Periodic task는 위와 같은 네 개의 요소들로 정의할 수 있다.

이를 간단하게 기호를 이용하여 나타낼 수 있다.

예를 들어 T1이란 task에 대하여,

T1 = (1,10,3,6)이라고 표현한다면,

이 테스크의 잡들은 1, 11, 21, ... 시간에 release되며,

각 잡들은 3의 execution time을 갖고,

각 잡들은 6초 안에 실행되어야 한다.(첫 번째 잡이 1에 등장한 7까지 실행이 완료되어야 하고, 두 번째 잡은 11에 등장하니 17까지 실행이 완료되어야 한다)

 

Ti의 디폴트 페이즈 ϕi는 0이며, 디폴트 relative deadline di = pi이다.

즉, 페이즈와 relative deadline에 대한 별도의 언급이 없으면, 디폴트 값을 갖는다고 보면 된다.

예를 들어,

T2 = (10, 3, 6) 로 표현된 task를 보자.

세 개의 수로 표현된 테스크는 phase가 생략된 것이다.

이럴 경우 Phase를 0으로 생각하면 된다. 즉 위 표현은 T2 = (0, 10, 3, 6)과 같은 표현이라 생각하면 된다.

 

T3 = (10, 3)로 표현된 task를 보자.

두 개의 수로 표현된 테스크는 phase와 relative deadline이 생략된 것이다.

phase는 0으로, relative deadline은 period인 10과 동일하게 생각하면 된다.

즉 T3 = (0, 10, 3, 10)과 동일한 표현인 것이다.

---

Aperiodic and Sporadic Tasks

많은 real time system들은 외부의 이벤트에 대한 대응이 필요하다.

스포라딕과 어피어리딕 테스크는, 이러한 이벤트를 처리하는 과정에서 생성된다고 보면 된다.

 

Sporadic task :

하드 데드라인을 가지는 잡들로 구성된다.

새로 등장한 잡이 기존의 잡들과 함께 스케줄링이 가능한지 결정하는 것이 목표이다.

가능하지 않다면, 해당 잡은 거절해야한다.

 

Aperiodic taske : 

소프트 데드라인을 가지는 잡들로 구성된다.

이 경우에는, 평균 응답시간을 최소하 하는 것이 목표가 된다.

 

 

---

스케줄링 알고리즘의 분류

스케줄링을 두 분류로 나누어 본다면 ,오프라인에서 스케줄링을 하는지, 온라인에서 스케줄링을 하는지에 따라 나누어 생각할 수 있다.

오프라인 스케줄링은 모든 테스크들에 대한 스케줄을 실행되기 전에 짜놓는 것이고,

온라인 스케줄링은 새로운 테스크가 등장(release) 될 때마다 런타임에 스케줄링이 지속적으로 업데이트 되는 것이다.

 

오프라인 스케줄링은 Clock - Driven,

온라인 스케줄링은 Priority - Driven을 이용한다.

 

Clock-Driven

어떤 잡을 언제 실행할건지에 대한 결정이 특정한 시간에 결정되는 스케줄링이다.

- 이 특정 시간이 언제가 될 지는 시스템이 실행되기 전에 결정된다.

- 보통 주기적으로 이 특정 시간이 분포되어있고, 주기적인 타이머 인터럽트를 이용한다.

- 각 인터럽트가 발생하면 스케줄러가 깨어나서 다음 피어리어드동안 실행될 잡들에 대한 스케줄을 짠 후, 다시 잠에 들어 다음 인터럽트를 기다는 형식이다.

 

보통,

- 각 잡들에 대한 모든 파라미터는 고정된 값이며 스케줄러가 미리 알고있어야 하고,

- 잡들에 대한 스케줄링은 오프라인에 완료되고, 저장되어 런타임에 사용한다.

- 따라서 런타임에서의 오버헤드를 최소화 할 수 있다는 장점을 갖는다.

- 단순하지만, flexible하지 못하다는 단점이 있다.

 

 

Priority-Driven

특정 알고리즘에 기반해서 잡들에게 우선순위(priority)를 부여한다.

어떤 잡이 release되거나 complete 되는 등의 event가 발생할 때 마다, 이 우선순위에 기반하여 스케줄링을 한다.

- 따라서이 알고리즘은 event-driven의 특징을갖는다.

- 각 잡들은 하나 이상의 큐에 들어가고, 각 이벤트마다 실행 준비가 된 잡 중 가장 높은 우선순위를 가진 잡이 실행된다.

 

보통,

- 잡들에 대한 파라미터가 고정된 값이거나, 미리 알려져 있을 필요가 없다.

- 온라인에서 스케줄이 계산된다 -> 클락 드라이븐 스케줄링에 비해 오버헤드가 크다.

- 잡들을 추가하거나 제거, 또는 파라미터들을 수정하기 쉽기 때문데 더 flexible하다 할 수 있다.

 

Priority driven 방식의 알고리즘과,

Clock driven 방식의 알고리즘에 대한 자세한 내용은 다음 포스팅에서 다뤄보겠다.