실시간시스템
monolithic -> task based design
Priority-Drivien Scheduling
Periodic Task Model
review
- phase: $\theta$
- Period: $p_i$
- Execution time: $e_i$
- Relative deadline: $D_i$, from the beginning of the period
*가정
- 태스크는 독립적이다 (ch8에서 리소스 공유를)
- 비주기적이고 때때로 일어나는 (ch7에서 통합된 방법을)
- 언제나 선점 가능하다
- 문맥 교체 비용이 무시 가능하다
우선성 대 임계성
우선성: 준비된 작업의 실행 순서
임계성(중요성): 작업이 임계점(deadline)을 넘겼을때 패널티
=> 더 중요한 작업이 우선순위를 가질 필요는 없다
동적 우선순위 대 고정 우선순위
$T_n = (p_n, e_n)$
T1 = (10, 4)
T2 = (15, 8) *임계점이 15s
T3 = (30, 2)
<그림>
고정 우선순위: RM(Rate Monotonic)
=> 수행 주기가 짧은게 먼저 수행(높은 우선순위)
동적 우선순위: EDF(Earliest Deadline First)
우선순위 기반 스케줄링 장점
이론
- Utilization < $n(2^{1/n}-1)$은 RM에 스케줄 가능하다
- U < 1이면 EDF 스케줄 가능하다 => 그러나 이론이 다 적용가능한것이 아님
고정 순위 스케줄링
schedulability: 임계점 만족을 하는가
*우선순위 할당
- Random
- 기능 임계성(의미적 중요성)
- Urgency
고정 순위 알고리즘
- (주기가 임계점인)RM이 최적의 고정 순위 알고리즘 => 최적(optimal)이란, 어떤 다른 고정순위 알고리즘이 적용 가능하면 RM도 가능하다는 뜻
*Rate monotonic은 작업(빠른 주기)이 데드라인을 만족 (e<=R<=P) R=Response Time, P=Period *그러나 상위의 우선순위 작업이 데드라인을 불만족한다고, 하위 우선순위 작업이 스케줄 불가능한것이 아님(더 긴 주기로)
- (임의의 임계점에서)DM이 최적의 고정 순위 알고리즘
*증명하는 법
임의의 (주기가 임계점인)고정 순위 스케줄을 그리고(최소공배수까지), RM 스케줄로 바꿀 수 있음을 보임
Critical Instant Theorem
높은 우선 순위 작업을 먼저 실행(RM과 다르게 주기가 더 긴 작업에 우선순위) RM으로 바꾸기?
Schedulability Check
오프라인 디자인 단계
- 우선순위 선택
- 알고리즘 선택
- 모듈이 최적인지 증명 온라인 단계
- 외부 이벤트로 주기적인 작업이 생김
- 주기와 알고리즘의 타협(e.g. 저화질로 변환)
*어떻게 스케줄 가능하게 체크 가능한가?
$R^0_3 = \lceil {P_3 \over P_1} \rceil * e_1 + \lceil {P_2 \over P_1} \rceil * e_2$
그러나 이건 항상 passover estimation이다. (항상 최악의 경우, 즉 높은 우선순위에 preemption 당한 경우를 가정)
*두번째 시도
$R_i=e_i + \sum^{i-1}_{j=1}(\lceil {R_i \over P_j} \rceil e_j)$
(나보다) 높은 우선순위에 반응시간(R)을 주기(P)로 나누었을 때의 합
=> 재귀적으로 정의되는 것을 어떻게 계산할 것인가
*세번째 시도
Critical Instance Theorem
R^0_k, R^1_k, ... R^i_k가 주기를 만족하면, 그 이후도 만족
*Exact analysis formulation for non RM static priority scheduling non Rate Monotonic가능, 더 엄격한 조건이여서?
*Task with deadline is smaller than period 주기 대신 relative deadline 사용시 확장 가능
*Critical instance가 발생하지 않는 곳에 적용 가능? 충분한(sufficient) 조건이 지만 not necessary, 이걸 만족시키지 못해도 가능할 수 있음
Exact Test 정리
- 무거운 계산
- 실행시간, 주기를 미리 알아야 함
- 주기가 서로 연결되어 불분명할경우 계산 불가능