Real-Time Scheduling – Formal Model

Real time system 모델의 기본 개념

 

실시간 시스템의 구성 요소로는 아래 세 가지가 있다.

 

- 실행해야 할 객체 (A workload model that describes applications supported by the system)

Job들과 task들이 여기에 속한다.

-  실행하기 위해 필요한 자원 (A resource model that describes the system resources available to applications)

processor들과 passive resource들이 여기에 속한다.

-  실행하기 위해 순서를 정하는 등의 역할을 하는 알고리즘 (Algorithms that define how the application uses the resources at all times)

scheduling과 resource에 접근하는 protocol들이 여기에 속한다.

 

기본 개념들을 가볍게 익히고 넘어가보자.

- Job

job은 시스템에 의해 스케줄링과 실행이 되는 work의 기본 유닛이다.

- Task

task는 일부 시스템 기능을 공동으로 제공하는 서로 관련성이 있는 작업 집합이다.

이렇게 말하면 복잡하게 느껴질 수 있는데, 비슷한 job들을 모아놓은 집합이라고 생각하면 된다.

- Processor

job을 실행시키는 주체이다. CPU가 될 수도 있고, 데이터 베이서 서버가 될수도 있다.

- Resource

file이나 database lock, 아니면 서로 공유해서 사용하는 변수 등이 될 수 있다.

 

---

Life Cycle of a Job

다음 그림을 보면 Job의 life cycle을 쉽게 이해할 수 있다.

그림에 대해 설명하기 전에, Preemption이라는 개념에 대해 집고 넘어가겠다.

Job들은 우선순위같은 기타 등등의 고려사항들에 의해 중간에 중지될 수도 있다.

예를들면, job1의 1/2까지 실행하다가 job2로 넘어가서 1/2를 실행하고 다시 job1로 넘어와 나머지를 실행할 수 있다는 것이다.

이렇게 중간에 끊었다가 다시 시작할 수 있음을 나타낼 때, Job is preemptive라고 표현 할 수 있다.

 

Job이 release(풀리면)되면 스케줄링 과정을 거치며 실행된다. 중간에 preemption이 걸려 완료되지 못하고 다시 대기상태로 들어갈 수 도 있다. 또한 CPU가 과부하 상태라던가 해당 job을 실행할 능력이 되지 않을 때는 WAITING상태로 들어갈 수 도 있다. Waiting과 preemption의 차이는, free resource 시그널을 받아야 재개할 수 있느냐, 아니냐의 차이로 생각할 수 있다.

이런 일련의 과정을 거치고 최종적으로 job의 실행을 완료하게 되면, completed 되었다고 표현한다.

---

Job Parameters

4개의 job parameter의 타입이 있다.

무슨 종류가 있고, 어떤 의미를 갖는지 가볍게 훑어보자.

Temporal

release time - 잡이 놓이는? 풀리는? 등장하게 되는 시간이라고 생각하면 된다

execution time - 잡의 실행이 끝났을 때의 시간이다.

deadline - 해당 잡이 언제까지는 끝나야 한다는 것을 나타내는 시간이다.

Funtional

Laxity type - 데드라인이 hard하냐, soft하냐의 종류이다. 데드라인이 hard하다는것은 데드라인을 무조건 지켜야 하는것이고 soft하다는 것은 데드라인을 필수적으로 지키지 않아도 된다는 것이다.

Preemptablility - 위에서 언급했듯이, 잡을 실행 도중에 중지하고 다른 잡으로 넘어갈 수 있느냐는 것이다.

Interconnection

precedence constraints - 잡의 선후관계가 정해져 있냐는 문제이다. 잡1을 완료해야만 잡2를 실행할 수 있다면, 잡은 서로에 대해 독립적이지 못한 것이다.

Resource

usage of processores and passive resources - 잡을 실행하는데 필요한 자원을 나타낸다.

 

이제 각 개념에 대하여 하나하나 자세하게 살펴보도록 할것이다.

 

---

Execution Time - ei

ei라고 표기하며, 잡 Ji가 단독으로 실행되고 필요한 모든 자원을 가지고 있을 때 Ji의 실행을 완료하는 데 필요한 시간을 의미한다.

이 값은 해당 job의 복잡도와 job을 처리하는 processor의 성능에 영향을 받는다.

따라서 여러가지 이유에 의해 값이 바뀔 수 있다.

 

Release time - ri

ri라고 표기하며, Ji가 실행 가능한 상태가 되는 시간을 말한다.

 

Completion time - Ci

Ci라고 표기하며, 잡의 실행이 끝났을 때의 시간이다.

 

Response time

따로 줄인 표기방법은 없고, 잡이 release 된 후로부터 complete 될 때까지 걸린 총 시간이다.

중간에 멈추었다 다시 실행되었을 때 그 간격도 포함하기 때문에 Execution time과는 다를 수 있다.

 

Absolute Deadline - di

잡이 끝나야 하는 시간을 나타내는 변수이다.

 

Relative Deadline - Di

잡이 끝나기까지 필요한 maximum response time을 뜻한다.

Di = di - ri로 표현할 수 있다.

 

아래 그림을 보면, di와 Di의 차이를 직관적으로 이해할 수 있을 것이다.

Hard Real - Time

hard real time 제약은 해당 잡이 절대로 데드라인을 놓치지 않아야 함을 뜻한다.

비행기 컨드롤을 예시로 들어보자.

착륙시에 렌딩 기어를 피는 버튼을 눌렀고, 착륙 전까지는 바퀴가 나와야한다.

이런 상황에서는 데드라인을 절대 놓쳐선 안된다.

 

Soft Real - Time

soft real - time 제약은 잡이 때때로 데드라인을 놓칠 수도 있음을 의미한다.

롤을 실행시켰다고 생각해보자.

바탕화면에 있는 바로가기 아이콘을 클릭하여 롤을 실행시켰다.

개발자가 설계 당시 부팅 시간을 5초로 설정해놓았다 쳐보자.

5초 이내에 게임이 실행되어야 클라이언트의 니즈에 충족한다고 판단한 것이다.

하지만 부팅시간이 5초가 넘어간다고 해서 서버가 다운된다거나 컴퓨터가 강제종료된다거나 하는 일은 없다.

이런 경우를 soft real - time이라 볼 수 있다.

 

Preemptability

잡들은 더 높은 우선순위를 가진 다른 잡에 의해서 interrupt될 수 있다.

만약에 잡이 실행 도중에 중지되고 다른 잡으로 넘어갈 수 있다면, 그 잡은 preemptable(선점 가능한)하다고 볼 수 있다.

만약 non - preemptable하다면 중간에 멈추는 일 없이 한번 시작한 잡을 끝날때 까지 해야한다는 것을 의미한다.

context switch time은 실행되는 잡을 변경하는 시간인데, 보통은 매우 짧아서 무시할 수 있다.

 

Preemptability라는 개념을 사용하는 이유에는,

잡들의 중요도가 서로 다를 수 있을 수 있고(브레이크와 라디오 튜닝중에 뭐가 더 중요할까?? 히히)

Priorites들을 이용한 알고리즘도 존재하기 때문이다.

 

Precedence Constraints

잡들이 특정한 순서로 실행되어야 한다는 제약이 있을 수 있다.

제약에 따라 predecessor, successor 등의 용어가 존재하는데, 별로 중요도가 높은 내용은 아니니 그냥 가볍게 훑어보면 충분하다.

Precedence Constraints(우선순위제약)이 존재하는 잡의 경우에는, 해당 잡의 release time이 지난 후 뿐만아니라, predecessor들이 complete 된 후 라는 조건이 추가되어야 실행 준비(ready for execution)가 된다.

 

---

Task

Task는 Reactive System들을 모델링 하기 위해 사용된다.

 

Reactive system이란, 제한되지 않은 시간동안 동작하는 시스템을 말한다.

테스크의 종류를 세 가지로 분류할 수 있는데,

1) Periodic : Hard deadline을 가진 잡들이 규칙적인 간격을 두고, 실행되는 테스크이다. 

2) Aperiodic : Soft deadline을 가진 잡들이 랜덤 간으로 실행되는 테스크이다.

3) Sporadic : Hard deadline을 가진 잡들이 랜덤 간격으로 실행되는 테스크이다.

 

자세한 내용은 다음에 다루도록 하겠다.

 

Processeor

프로세서는 job들을 스케줄하는 동적인 구성요소다.

멀티 프로세싱과 싱글 프로세싱이 있지만,

앞으로 싱글 프로세서를 더 자세히 다뤄볼 예정이다. 멀티 프로세서는 복잡하기 때문에, 간단하게만 다루겠다.

 

Resource

리소스는 잡들이 필요로 하는 수동적인 구성요소다.

만약 잡이 어떤 리소스를 사용한다면, 그 리소스는 다른 잡들이 이용하지 못한다.

만약 어떤 잡이 리소스를 사용해야하는데, 그 리소스가 바쁘게 일하고 있으면, 그 리소스가 release되기를 기다려야 한다.

 

Scheduling

스케줄은 매 시간 단위마다 프로세서와 자원을 잡에게 할당한다.

 

스케줄이 다음 조건들을 만족시키는 경우, 유효한(valid) 스케줄이라 할 수 있다.

- 모든 프로세서는 각각 최대 한 개의 jod에만 할당될 수 있다.

- 모든 잡은 각각 동시간에 한 개의 프로세서에만 할당될 수 있다.

- 잡에게 할당된 프로세서 타임은 그 잡의 실제 실행 시간과 같다.

- 주어진 우선순위 제약과 리소스 사용제약을 만족해야한다.

 

이 조건을 만족시키면서, 모든 잡들을 hard real-time constraints를 지키며 그들의 deadline전에 완료할 수 있으면,

그 스케줄을 피저블(feasible)하다고 한다.

그리고 이러한 잡들을 스케줄러블 하다고 한다.

 

Algorithm

스케줄링 알고리즘은 잡들의 set을 위한 스케줄을 계산한다.

만약 set of jobs가 스케줄링 알고리즘에 의해 스케줄러블하다면, 

그 알고리즘은 피저블한 스케줄을 만들어낸다고 할 수 있다.

만약 스케줄링 알고리즘이 항상 피저블한 스케줄을 만들어 낸다면, 그 스케줄링 알고리즘은 Optimal 하다고 한다.

(물론 스케줄링이 불가능한 경우는 제외한다)