Real-time systems are those which must execute all tasks within their timing constraints. Due to the catastrophic consequence of missing deadlines of some real-time tasks, fault tolerance is an essential component of such systems. This dissertation deals with fault tolerance techniques to cope with transient faults for real-time control systems. Three strategies utilizing time or spatial redundancy are considered: Triple Modular Redundancy (TMR), checkpointing and schedule control strategies.
First, to enhance fault tolerance capability of TMR real-time systems, new task allocation strategies are suggested. The strategies utilize both time and spatial redundancy to tolerate correlated and independent transient faults. Tasks are allocated in three processors not to execute the same task at any instant. To evaluate the proposed strategies, a control system model under transient faults is developed. The strategies are investigated through reliability evaluation using the model for various fault parameters.
Next, checkpointing strategy is investigated to tolerate transient faults in single and TMR processor systems. An analytic method is developed to determine an optimal checkpoint interval considering timing constraints of real-time systems. The method optimizes not the average execution time of task but the probability of successful task execution within the specified deadline, which is more important in real-time systems. The method is developed for single task, and then extended to include multiple tasks. For single task, the mission time reliability of real-time system is considered to select the optimal checkpoint interval. For multiple tasks, checkpoint intervals are selected task by task to minimize a failure probability over the specified interval. The method developed for single processor system is also extended to TMR systems.
Finally, to explore more realistic tasks that have deadlines which are consisted of several periods, the concept of schedule control is introduced. A schedule controller is suggested to control task schedules when some tasks are to miss their deadlines due to the extra time consumed to recover from faults. The schedule controller changes task schedules by skipping some non-urgent tasks to make room for urgent tasks that are near to deadline. The schedule controller does nothing when there is no fault or all tasks are to be finished within deadlines. Task model for schedule control is developed, and performance index for tasks for deadlines consisted of several periods is newly defined. Two simple onestep ahead schedule controllers are designed, which show the possibility of schedule control.
Overall, this dissertation demonstrates that the proposed strategies can tolerate transient faults effectively, and hence improve the reliability of real-time control systems.
실시간 시스템의 모든 태스크들은 각각의 시간 제한 조건(데드라인, deadline)이내에 수행이 끝나야만 한다. 어떤 실시간 태스크의 경우, 데드라인의 초과는 커다란 재난으로 이어질 수 있기 때문에, 실시간 시스템에서 내고장성은 아주 중요한 부분이 되고 있다. 본 논문은 이와 같은 실시간 제어 시스템에서 과도 고장(transient fault)을 극복하기 위한 내고장성 기법들을 다룬다. 특히 삼중화 구조(TMR), 체크 포인팅(checkpointing) 기법, 스케줄링 제어(schedule control)의 시간적 또는 공간적 여유를 이용한 내고장성 기법에 대하여 연구하였다.
먼저, 삼중화 구조 실시간 제어 시스템의 내고장성을 높이기 위하여 새로운 태스크 할당 방법이 제시 되었다. 제시된 기법은 독립적 고장(independent fault)과 의존적 고장(correlated fault)을 극복하기 위하여 시간적, 공간적 여유를 이용한다. 제시된 방법은 같은 시간에 같은 태스크를 세 프로세서에서 수행하지 않도록 태스크들을 할당하였다. 제시된 방법들의 성능을 해석하기 위하여 과도고장하의 실시간 제어 시스템 모델을 개발하였다. 이 모델을 사용하여 다양한 고장 파라메타(parameter)들에 대한 신뢰도 해석을 통하여 제시된 구조의 유용성을 입증하였다.
다음으로, 단일 또는 삼중화 구조에서 과도 고장을 극복하기 위한 체크포인팅 기법을 연구하였다. 실시간 태스크의 시간 제한을 고려하여 최적 체크포인팅 구간을 선정하기 위한 해석적 방법을 제시하였다. 이 방법은 태스크의 평균 수행시간을 최적화 하는 것이 아니라, 실시간 시스템에서 중요한 조건인 데드라인내에서 태스크가 성공적으로 수행될 확률을 최적화 한다. 단일 태스크 실시간 시스템에 대하여 최적 체크포인팅 구간을 구하는 기법을 개발하고, 이것을 다중 태스크 시스템으로 확장하였다. 단일 태스크의 경우는 미션 시간(mission time)동안의 신뢰도를 최대화 하는 체크 포인팅 구간을 구했으며, 다중 태스크의 경우는 주어진 구간 동안에 모든 태스크들이 성공적으로 수행될 확률을 최대화 하도록 각 태스크 별로 체크 포인팅 구간을 선정하였다. 단일 프로세서에서 적용된 이 기법은 삼중화 구조로 확장되었다.
마지막으로, 태스크의 데드라인이 수 개의 주기(period)로 이루어져 있는 실질적인 경우를 고려하기 위하여 스케줄 제어 개념이 도입되었다. 고장을 극복하기 위하여 소모된 시간 때문에 몇몇 태스크가 데드라인 이내에서 수행을 끝낼 수 없게 되었을 때, 스케줄 제어기는 기존의 태스크 스케줄을 변경함으로써 모든 태스크들이 자신의 데드라인 이내에서 수행을 끝마치도록 한다. 이 스케줄 제어기는 덜 급박한 태스크의 수행을 몇 주기동안 포기(skip) 함으로써 데드라인에 임박해 있는 급박한 태스크의 수행을 위한 시간을 제공한다. 고장이 없거나, 태스크들이 모두 자신의 데드라인 이내에서 수행이 끝날 수 있는 경우에는 스케줄 제어기는 아무런 동작도 하지 않는다. 이와 같은 스케줄 제어를 위한 태스크 모델을 개발 하였으며, 다중 실시간 태스크를 가진 시스템을 위한 성능함수를 새로이 정의 하였다. 간단한 스케줄 제어기를 설계함으로써 스케줄 제어를 통하여 과도 고장을 극복할 수 있음을 보였다.
결론적으로 본 논문에서는 과도 고장을 극복하기 위한 여러 가지 기법들을 제시하였고, 이 기법들을 통하여 실시간 제어 시스템의 신뢰도를 향상시킬 수 있음을 보였다.
