[06] Mixed-Criticality Scheduling

Uniprocessor(가정)에서 하나의 system 내에 서로 다른 중요도를 가진 system이 있을 때, 스케쥴링하는 방법에 대한 설명이다.

 

가령 자율주행 차량의 ABS와 스테레오 음향 시스템을 생각해 보면, ABS가 훨씬 중요함을 알 수 있다. WCET에 대한 정의도 다를 수 있다. Certification requirements가 다를 경우, 동시에 진행되는 task임에도 다른 WCET 측정 방법이 진행된다.

 

현재 주로 사용 중인 방법은 space-time partitioning으로 각 서브시스템 마다 time slot을 할당해 관리하고 있다. (Isolation을 통한 분석이 진행되었다.) 다만, High criticality system의 경우, 너무 보수적으로 WCET를 측정하다 보니, WCET보다 빠르게 종료되어 resource utilization이 많이 감소할 수 있다. 

 

1. Mixed criticalities

두 가지 측면에서 서브 시스템의 criticalities가 평가된다. 서브시스템 자체의 중요도와 발생 빈도수이다. 이를 기반으로 스케쥴링하기 위해, 1) Job의 criticality를 평가하고 2) 여러 criticality level에서의 WCET를 계산한다. 당연히 criticality level이 높을수록 WCET 예상값은 크다.

Execution time for detemining WCET of job with the $j^{th}$ criticality level

 

다음과 같은 set of jobs이 있다고 가정해 보자.

 

Job이 low criticality로 동작한다고 가정하면 EDF로 스케쥴링 가능하며, high ciriticality로 동작하면 $J_3, J_4$만 동작 가능하다. 다만 앞서 설명했듯이 $C_i(HI)$는 보수적으로 설정된 경우가 있어, 2초보다 빠르게 1초만에 종료할 수 있다. 이런 특징을 반영하여 스케쥴링하면 모든 Job을 스케쥴링할 수도 있다.

 

방법은 간단하다.

1. High criticality job을 EDF로 우선 시행
   
   1. 생각보다 빨리 끝나면, low criticality job EDF로 수행
   2. WCET 걸렸으면, pass
2. Next high criticality job 수행
   1. 반복

 

Mixed criticality jobs에 대해서 적절하게 수행할 job을 선택하는 것은 NP-hard 문제이다. 심지어 두 개의 criticality level만 있거나 모든 job이 동시에 arrive해 불가능하다.

 

현재 연구는 어떻게든 해결해 보고자, dual criticality instances(low, high)에 대한 스케쥴링 방법을 연구하고 있다.

 

2. Audsley's algorithm

Dual criticality instance $I=\{J_1,J_2,...,J_3\}$에 대해서, Lawler's technique (=Audsley's algorithm)으로 priority를 결정한다.

Recursively find a lowest-priority job

 

$J_i$가 lowest-priority가 되는 조건은, priority level of $J_i$로 다른 친구들과 함께 스케쥴링했을 때, $J_i$가 lowest prioirty로 deadline을 만족하는 경우이다. 가령 다음과 같은 job이 있다.

 

• $J_1$은 LO priority이고 C(LO)로 스케쥴링해보면, deadline miss가 난다.
• 반면, $J_2$는 HI priority이고, C(HI)로 스케쥴링해보면, deadline을 충족한다.
• 따라서 priority는 $J_1 > J_2$이다.

위의 priority로 job scheduling을 하면, LO-criticality certification이나 HI-criticality certification 모두 충족하는 것을 알 수 있다.

 

3. OCBP : Own Criticality-Based Priorities

Audsley's algorithm을 이용해 job의 priority를 결정하고 스케쥴링하는 방법이다.

• Runtime : $O(n^3logn)$
• Quantitative performance bound
  • System load 파라미터 기반의 run-time supprot 가정

 

4. The load parameter

LO-criticality job의 경우 "$C_i(HI)>>C_i(LO)$" 의 관계를 가지고 있다. 만약 run-time system이 실행 예산을 강제할 수 있다면, 이들의 WCET를 $C_i(LO) = C_i(HI)$로 설정한다. (*policing, budgeting은 overhead cost가 크며 HI-criticality job으로서 동작한다)

 

WCET 설정을 마치고, load parameter를 측정한다. 구간은 release time to deadline이다.

• $load_{LO}(I)$ : 모든 job을 LO-criticality WCET로 스케쥴링
• $load_{HI}(I)$ : HI-criticality job만 HI-criticality WCET로 스케쥴링
• $load_{HI}(I) + load_{LO}(I)^2 \leq 1$이면 스케쥴링 가능 (중요)

 

예시는 다음과 같다.

$load_{LO}(I)$ 계산, 여러개면 max 값을 취한다

$load_{HI}(I)$ 계산

$load_{LO}(I)=1$, $load_{HI}(I)=0.75$임으로 합이 1보다 커 스케쥴링 불가능하다는 것을 알 수 있다.

 

Preemptive unit-speed procecssor에 대한 OCBP의 스케쥴 가능 곡선 그래프는 다음과 같다.

파란 영역은 속도가 1인 프로세서에서 OCBP를 사용하여 스케쥴링 가능함을 의미

 

이 영역을 활용할 수 있는 processor 최대 speed는 1.618(=황금비율)이다. (왜 나왔는지 모르겠다)

 

5. COPA : Criticality Optimal Priority Assignment

Dual-criticality를 가지는 sporadic tasks에 대해서 스케쥴링하는 방법이다. 이런 반복적인 작업에 대해 TFP(DM), JFP(EDF), JDP(Least Laxity) 등 많은 방법이 있지만, 이는 mixed criticality를 가지는 tasks에 대해서는 optimal이 아니다. COPA는 Lawler's technique의 application으로 2010년 제안되어 optimal priority 할당하며 budget enforcement를 통한 quantitative gurantee를 한다.

 

스케쥴링 조건은 다음과 같다.

 

Unit-speed processor에 대한 그래프는 다음과 같다.

 

또한, 최대 활용 가능 processor의 speed는 3.414(원주율)이다.

 

COPA는 dual-criticality sporadic task system에 optimal TFP algorithm이다.

 

6. 정리

Platform-sharing이 진행되면서 서로 다른 시스템에 대해 서로 다른 certification criteria가 사용된다. 현재 사용하고 있는 방법은 space-time partitioning인데, resource usage(Size, Weight, and Power; SWaP)와 certification effort 측면에서 비효율적이다. 

 

Recurrent task에 의해 생성되는 mixed criticality system을 위한 certifiably correct 기술이 필요하다.