주기 태스크 모델(periodic task model)은 실시간 시스템이 하는 일을, 요청이 일정한 간격으로 되풀이되는 태스크의 집합으로 나타내는 모델이다. Liu와 Layland는 1973년 논문에서 이 모델로 고정 우선순위 스케줄링과, 마감 시한에 따라 우선순위를 동적으로 주는 deadline driven 스케줄링을 분석했다.[1] 태스크는 끝없이 되풀이해 요청될 수 있다.[2]
파라미터
태스크가 한 번 요청될 때마다 실행되는 단위를 job이라 부른다.[3]
Liu와 Layland의 모델에서 태스크 의 요청 주기 는 이웃한 두 요청 사이의 일정한 간격이고, 실행 시간 는 프로세서가 태스크를 중단 없이 실행하는 데 드는 시간이다. 실행 시간은 태스크의 최대 처리 시간으로 해석할 수 있고, 그러면 다음 요청을 준비하는 비용과 선점 비용도 넣을 수 있다.[1] Tindell의 1992년 응답 시간 분석은 를 WCET로 두고, context switch 비용을 여기에 넣는다.[4]
상대 마감 시한 는 태스크가 요청된 시각부터, 그 요청이 끝나야 하는 시각까지의 길이다.[2][4] 마감 시한은 마감 시한에서 다룬다.
Audsley의 1993년 분석에서는 태스크가 처음 시작하는 시각을 시스템 실행이 시작된 시각에서 떨어뜨릴 수 있고, 이 시작 시각을 offset이라 한다. 태스크 의 offset이 면 태스크는 , , , …에 요청된다.[5]
모든 태스크가 함께 도착하는 시점이 있는 주기 태스크 집합을 synchronous 태스크 집합이라 부르고, 태스크의 도착 시각이 고정된 offset만큼 떨어져 있어 함께 도착하는 시점이 없는 주기 태스크 집합을 asynchronous 태스크 집합이라 부른다. 태스크 집합의 주기들의 최소공배수를 그 태스크 집합의 hyperperiod라 부른다. 태스크 의 최악 실행 시간을 상대 마감 시한과 주기 가운데 작은 값으로 나눈 를 그 태스크의 밀도(density)라 부른다.[3]
Liu와 Layland의 가정
Liu와 Layland는 1973년 논문에서 아래 다섯 가지를 가정했고, 이 가정 아래에서 태스크는 요청 주기와 실행 시간 두 값으로 모두 정해진다.[1]
- hard 마감 시한이 있는 태스크의 요청은 주기적이고, 요청 사이의 간격이 일정하다.
- 각 요청은 같은 태스크의 다음 요청이 오기 전에 끝나야 한다.
- 태스크는 서로 독립이다. 한 태스크의 요청은 다른 태스크의 요청이 시작되거나 끝나는 것에 기대지 않는다.
- 태스크마다 실행 시간이 일정하고, 시간에 따라 바뀌지 않는다.
- 주기적이지 않은 태스크는 초기화나 failure 복구 루틴 같은 특별한 경우다. 이런 태스크는 실행되는 동안 주기 태스크를 밀어내고, hard 마감 시한이 없다.[1]
Liu와 Layland는 다섯 가정 가운데 요청이 주기적이라는 가정과 실행 시간이 일정하다는 가정이 가장 중요하면서도 가장 방어하기 어렵다고 보았다. 또 이용률로 스케줄 가능성을 따질 때도, 태스크 사이를 전환하는 실제 비용은 따로 따져야 한다고 했다.[1]
실제 태스크는 다른 태스크와 자원을 함께 쓰기도 한다.[6][7] OSEK OS에서는 extended 태스크가 다른 태스크가 설정하는 이벤트를 기다릴 수 있다.[6] 실행 시간은 입력 매개변수와 소프트웨어 상태 같은 논리적 맥락에 따라 달라진다.[8]
우선순위 상한 프로토콜 같은 우선순위 상속 계열 프로토콜로 공유 자원을 다루면 태스크 가 블록되는 최악 시간 가 묶이고, 스케줄 가능성 판정 조건에 를 항으로 더해 자원 공유에서 오는 지연을 넣는다.[5][9]
주기 태스크와 sporadic 태스크
- 주기 태스크(periodic task): 일정한 주기마다 요청된다.[1]
- sporadic 태스크: 아무 때나 요청될 수 있지만, 이웃한 두 요청은 정해진 최소 간격 이상 떨어져 있다.[2]
- aperiodic job: 아무 때나 도착할 수 있다.[10]
Mok은 1983년 박사 학위논문에서 주기 프로세스와 함께 sporadic 프로세스를 모델링했다. 최소 간격은 sporadic 프로세스가 시스템 자원을 독점하지 못하게 하려고 둔다.[2]
주기적이지 않은 태스크를 aperiodic 태스크라 부르고, aperiodic 태스크 가운데 시스템에 줄 수 있는 부하에 상한이 있는 것을 sporadic 태스크라 부르는 쓰임도 있다. 이 쓰임에서 sporadic 태스크는 길이 인 어느 구간에서든 release되는 job들의 계산 시간의 합이 이하다. 한 가지 중요한 경우로 는 job 하나의 계산 시간 상한이고, 는 release 사이의 최소 간격이다. aperiodic server는 aperiodic 태스크를 엄격한 주기 태스크 모델 안에 받아들이게 했다.[11]
Release와 jitter
Tindell의 1992년 분석에서는 도착한 태스크가 우선순위 순 실행 대기열에 놓이는 것을 release라 하며, 태스크가 도착하는 시각과 release되는 시각은 다를 수 있다. 도착과 release 사이에 늦어질 수 있는 최대 시간이 release jitter다. release jitter는 틱 스케줄러의 폴링이나 메시지 대기 때문에 생긴다.[4]
Tindell은 1992년 고정 우선순위 선점 스케줄링의 응답 시간 분석을 넓혀, 임의 마감 시한, release jitter, 버스트형 sporadic 태스크를 다뤘다.[4]
AUTOSAR Classic Platform R25-11의 Timing Extensions 명세는 주기적으로 일어나는 이벤트의 타이밍 제약(PeriodicEventTriggering)에 주기, jitter, 최소 발생 간격을 둔다. 이 명세는 jitter를 주기적 이벤트의 발생이 주기에서 벗어날 수 있는 최대 폭으로 정의한다.[12]