Feasibility Analysis of Fault-Tolerant Real-Time Task Sets

수식도 거의 없고 그래서 어렵지는 않았지만 어떤 얘기를 하고싶은 건지는 이해가 잘 안돼서 따라가기 힘들었다..

---

Introduction

• real time system은 fault가 났을때도 정확하고 시간내에 동작하도록 하기 위해서 많은 replication과 redundancy로 이루어져 있음
• 이렇게 redundancy가 있는 경우 feasibility test도 다르게 동작할 필요가 있음
• 이 논문에서는 다양한 failure hypothesis 내에서의 exact feasibility test를 제공한다.

Computation Model & Fault Model and Assumptions

• uniprocessor 가정하지만, task allocation이 statically 이루어지는 distributed/multiprocessor system으로도 확장가능함

• 각 task는 unique한 priority를 부여받고, 더 높은 priority의 task에게 preemption될 수 있음

• a set of $n$ tasks $(\tau_1, \ldots, \tau_n)$ where $1$ denotes highest priority and $n$ denotes lowest priority.

• $\tau_i$ → $(T_i, C_i, D_i)$

  • $T_i$ → minimum inter-arrival time
  • $C_i$ → worst case execution time (WCET)
  • $D_i$ → deadline

• worst case blocking by lower priority task를 $B_i$, interference by higher priority task를 $I_i$라고 했을 때, no failure hypothesis 가정 하에서 response time analysis

  • 다음 식을 만족하고 $R_i \in [0, D_i]$ 인 $R_i$가 존재하면 task $\tau_i$는 feasible함
  • $\displaystyle R_i = C_i + B_i + \sum_{j\in hp(i)} \lceil \frac{R_i}{T_j} \rceil \cdot C_j$
  • 해당 구간 내 모든 $R_i$의 값을 찾아볼 필요는 없고 recurrence relation을 이용해 minimum한 $R_i$의 값($r_i^{n+1}$이랑 $r_i^n$이 같아지는 시점)을 찾을 수 있다.
    • $\displaystyle r_i^{n+1} = C_i + B_i + \sum_{j \in hp(i)}\lceil \frac{r_i^n}{T_j} \rceil \cdot C_j$ where $R^0_i = C_i$

• 여기에서 다루는 hw+sw fault들은 해당 task를 다시 실행하거나 alternate action을 대신 실행하는 걸로 극복할 수 있다고 가정

• fault는 한번에 한 task에만 영향을 줄 수 있으며, 이는 해당 task의 실행이 모두 끝났을 때 발견

• 그리고 fault가 났을 때 이를 해결하기 위해서 inter-arrival time between faults 는 특정 값보다 커야한다.

  • 만약 어떤 task의 computation time보다 짧은 간격으로 fault가 들어오게 되면 task set은 non-schedulable하다.

Feasibility Analysis

• $F_i$를 fault로 인한 additional factor라고 한다면
  • $R_i = C_i + B_i + I_i + F_i$

✔ Re-execution

→ 문제가 생겼을 때 영향받은 task를 다시 재실행해서 fault 해결하는 방법

• fault들의 minimum inter-arrival time $T_F$가 주어졌을 때의 $R_i$ ?

  $\displaystyle R_i = C_i + B_i + \sum_{j \in hp(i)} \lceil \frac{R_i}{T_j} \rceil \cdot C_j + \lceil \frac{R_i}{T_F} \rceil \cdot \max_{j \in hp(i) \cup i}(C_j)$

  • task가 re-execute됐을 때 자기 자신의 priority에서 시작한다고 가정 - $B_i$ 변함없음

• 얘를 recurrence relation으로 바꾸면

  $\displaystyle r_i^{n+1} = C_i + B_i + \sum_{j \in hp(i)} \lceil \frac{r_i^{n}}{T_j} \rceil \cdot C_j + \lceil \frac{r_i^{n}}{T_F} \rceil \cdot \max_{j \in hp(i) \cup i}(C_j)$

✔ Forward error recovery

→ 전체를 다시 재실행하는게 아니라 exception handler같은 매커니즘이 error recover 해줌

• amount of computation time by exception handler를 $\bar C_i$라고 했을 때 ($\bar C_i \ll C_i$)

  $\displaystyle R_i = C_i + B_i + \sum_{j \in hp(i)} \lceil \frac{R_i}{T_j} \rceil \cdot C_j + \lceil \frac{R_i}{T_F} \rceil \cdot \max_{j \in hp(i) \cup i}(\bar C_j)$

• 당연히 re-execution 하는 것보다 task set이 schedulable해지지만 QoS는 re-execution하는게 훨씬 더 낫다..

✔ Recovery Blocks

→ error checking과 state restoration이 합쳐진 매커니즘

• 모든 recovery block은 primary module과 하나 이상의 alternate module, acceptance test를 가지고 있음

• primary module의 computation time을 $C_i^p$, alternate module의 computation time을 $C_i^a$라고 할 때 - alternate module의 실행시간이 더 길 수 있음 -

  $\displaystyle R_i = C_i^p+ B_i + \sum_{j \in hp(i)} \lceil \frac{R_i}{T_j} \rceil \cdot C_j^p+ \lceil \frac{R_i}{T_F} \rceil \cdot \max_{j \in hp(i) \cup i}(C_j^a)$

✔ Utilization Bounds

• 원래 RM에서 n→$\infty$일때 utilization bound?
  • $n(2^{1/n}-1)$ → .693
• 여기에서 single fault에 대처 가능하게끔 task execution time을 2배로 잡으면
  • $\frac n2(2^{1/n}-1)$ → 0.346

Checkpoints

• checkpoints?
  • 현재 task의 정보(data variable이나 레지스터 값)을 저장해둔 것
  • 저장하기 전에 acceptance test는 한번 해야함
• fault occurrence 상황에서 non-schedulable한 task set에서, additional computation time을 줄인다면 schedulable하게 될수도 있음
• $O_i$를 checkpoint하나 만드는데 걸리는 오버헤드 타임이라고 가정하고, task $\tau_i$를 $m_i$개의 segment로 나눠서 저장했다고 했을 때-깔끔하게 나눠떨어질 때-, 해당 execution에서 최대 하나의 fault가 발생했다면
  • $C_i^{m_i} = C_i +(m_i-1)O_i + \frac{C_i}{m_i}$
  • 원래 execution time + checkpoint overhead + recovery time
• 그런데 깔끔하게 나누어 떨어지지 않으면?
  • $\hat C_i$를 $\tau_i$의 가장 큰 checkpoint interval이라고 하고, $O$를 한 checkpoint만들 때 드는 overhead라고 할 때
  • $C_i^{m_i} = C_i +(m_i-1)O + \hat C_i$
  • 이 경우의 response time equations
    • $\displaystyle R_i = C_i + (m_i-1)O+ B_i + \sum_{j \in hp(i)} \lceil \frac{R_i}{T_j} \rceil \cdot (C_j+(m_j-1)O)+ \lceil \frac{R_i}{T_F} \rceil \cdot \hat C_i$