How to achieve timing guarantee?
어떤 시스템이 정상적으로 돌아가기 위해, 총 4초 안에 계산이 끝나야 한다고 합니다.
그 시스템에 대한 Task는 5초마다 한번씩 스케줄되고,
계산 시간은 2초라고 하네요.
뭐 지금은 잘 돌아가겠죠?
근데, 하나의 프로세서가 이런 Task를 16개를 관리한다면 어떻게 될까요?
조금만 Scheduling을 실수해도 deadline miss가 발생하는 task가 생길겁니다.
Task를 T(task schedule period, computing time)로 적습니다.
Schedulable
모든 real-time task를 deadline miss 없이 스케줄 할 수 있는 경우
task set을 Schedulable하다라고 정의합니다.
대체 어떻게 Schedulable함을 확인할 수 있을까요?
Task set이 2개정도 되면 직접 해볼 수도 있지만,
Task set이 500개면 그 task들의 schedulable 여부를 어떻게 확인할 수 있을까요?
저 Task Set들의 경우, 각 4초, 5초, 7초마다 schedule되니까,
4 x 5 x 7 = 140초동안만 제대로 schedule됨이 보장되면,
아마 schedulable여부를 확인할 수 있겠죠.
그러면,
- Task set 시작시간이 Synchronize 되지 않는다면요?
- Execution time이 줄어들면요?
- task 수가 많아지면요?
- 최소공배수가 140^10초여서 그때까지 정상적으로 도는지 확인이 불가능하면요?
이 내용은 곧 배웁니다!
기차는 obstacle을 발견하면 멈추는 task를 실행합니다.
distribution unit에 빨간 등이 들어오면 인간이 브레이크를 밟죠.
- 센서는 주기적으로 object를 탐지합니다.
- object가 탐지되면 emergency stop을 겁니다.
sensor를 무한정 감지시킬 수는 없습니다.
CPU를 sensor가 99% 먹으면 나머지 시스템을 못 사용할테니까요.
그러면, 얼마나 자주 sensor가 탐지를 시도해야 충돌하지 않을 수 있을까요?
Task를 너무 자주 실행시키면 load가 너무 커집니다.
Task를 너무 덜 실행시키면 deadline을 지키지 못해 performance가 뚝 떨어지죠.
Task를 Rate Monotonic으로 스케줄했구요. (주기가 짧을 수록 우선순위가 높음)
이런 3개의 스케줄이 있다면,
각각의 Utilization (task가 얼마나 용량을 차지하는가)를 계산해 더합니다.
만약 Utilization을 더해서 1.0이 넘는다면?
컴퓨팅 시스템의 100% 이상을 task들이 사용한다는 뜻이죠. (말이 안 됩니다.)
Liu-Layland Test
전체 시스템 Utilization의 합이 0.69보다 작다면,
수학적으로 Schedule 가능함이 보장됩니다.
(주의! Rate Monotonic Schedule에서만 Liu-Layland 한계가 성립합니다.)
이 때의 0.69를 Liu-Layland 한계라고 합니다.
s는 sample task로, schedule이 가능한지 확인하고 싶은 task를 의미합니다.
즉, 이 task의 utilization과 다른 task들의 utilization을 더해서,
0.69 (RM Bound)보다 작다면,
Task가 schedulable하다고 정의합니다.
(Rate-monotonic schedule 방식으로)
이 식의 의미가 뭘까요?
Task의 schedule 주기를 확 짧게 해버리면 기차가 부딪히지 않겠죠.
1ms마다 계속 obstacle을 체크하는 겁니다.
단, 그런 경우 Overload가 발생해서 schedule이 불가할 수 있고,
그 overload 여부를 확인할 수 있는 방법이 Liu-layland 한계를 이용하는 것이었습니다.
그러면, 넉넉하게 period를 잡고 싶을 때, 얼마나 넉넉하게 잡아야 schedulable해질까요?
1000ms마다 한번씩 obstacle을 검사한다면
기차가 부딪힐 수도 있겠죠?
최악의 경우를 상정해야 합니다.
이전 detecting task가 끝난 직후에,
센서가 감지할만한 거리에 obstacle이 발견되었고,
그 다음 detecting task에서 감지가 되겠죠.
obstacle detected 시점부터 brake를 누르는 시점까지 사람이 반응하는 시간이 있을거고,
누른 후에 기차가 등속운동 하여 정지할겁니다.
평범한 등속운동 방정식을 이용하여 기차가 움직한 거리를 계산할 수 있겠죠.
obstacle 발견부터 정지 시점까지 이동한 거리가 obstacle까지의 거리보다 짧아야겠죠.
식이 어려워보여도, 그냥
감지 이후에 멈출 때까지의 거리가 obstacle까지의 거리보다 짧으면 됩니다.
그걸 계산하면 최후의 최대 task period까지 구할 수 있겠네요.
