Real-time systems are those which must execute all tasks within their timing constraints. Especially, the increased use of computer systems in many vital aspects of every life, and the growing dependence on these systems, make fault tolerant computing essential in many systems. On the other hand, recent progress on hardware technology for VLSI make tendencies that faults of hardware itself are decreased and instant malfunction of controller by transient faults constitutes a majority of system failure. In addition, recent development of microprocessors and DSPs provided enormous capacity with reasonably low cost. Therefore, to impose fault tolerance to a system, hardware and temporal redundancy are usually used.
In this dissertation, we study fault tolerance methodologies of real-time control systems using modular and temporal redundancy in the presence of transient faults. We propose the DMTR (Dual-Modular Temporal Redundancy) with checkpointing strategy for temporal redundancy and dual-modular redundancy structure for hardware redundancy.
First, we introduce the basic concept of DMTR system and describe the DMTR strategy. Using discrete Markov model, we formulate the STPMs (State Transition Probability Matrices) for given single task and parameters of environments, model and analyze the reliability of DMTR system for concerning write back and/or update-with-communication overhead time in presence of transient faults such as independent and correlated faults. Also, we find optimal number of subslots (concerned to checkpointing interval) for maximum reliability through numerical evaluation of our formulated system model.
Second, we formulate a reliability model of DMTR system with harmonic multiple tasks. For this analysis, we consider the hyper-period in which all multiple tasks are executed an integral number of times, calculate the various STPMs for each task, and formulate the reliability model for the DMTR system based on these STPMs. Since this formulation requires many iterations and a long computation time, we formulate a recursive form by finding and reflecting the repeated elements. In addition, considering constant checkpointing-overhead to simplify analysis and varying parameters, we find optimal number of subslots for maximum reliability via numerical evaluation of formulated model. Also, we evaluate and compare reliabilities of DMTR using RM scheduling algorithm, DMTR using GCDP algorithm, and conventional DMR.
Third, we extend analysis for multi-tasks DMTR system with general periods. For a task set with general periods, RM scheduling and EDF scheduling are shown to different task-executing forms. We investigate characteristics of period-edge-interval of the given task set, formulate reliability models of DMTR systems for multiple tasks with general periods using RM scheduling and EDF scheduling, respectively. Then, we evaluate reliabilities of the system for various task set and parameters, and find optimal number of subslots for the systems according to the given parameters.
Finally, we summarize the above evaluation results for various viewpoints and propose design guides for DMTR systems.
Overall, this dissertation demonstrates that the DMTR system can tolerate transient faults effectively, and hence improve the reliability of real-time control systems.
실시간 제어 시스템은 모든 태스크들이 각각 정해진 시간 제한 조건 이내에 수행이 완료되어야만 한다. 특히, 인간의 생활에서 생명과 관련된 부분에 컴퓨터 시스템의 사용 증가는 많은 시스템이 내고장성 설계를 요구하게 되고 있는 실정이다. 한편, 오늘날 집적 회로 설계 기술의 개발로 하드웨어 자체를 결함에 의한 영구 고장 (permanent fault)보다는 시스템이 점점 복잡해지고 시스템이 동작하는 환경 조건에 따라 발생하는 과도 고장 (transient fault)에 의한 일시적인 기능 장애로 시스템이 고장을 일으키는 경우가 더 중요한 문제로 대두되고 있다. 최근 개발되고 있는 마이크로프로세서들은 낮은 비용이면서도 상당히 좋은 성능을 가지고 있다. 따라서, 이러한 경향으로부터 시스템의 내고장성을 향상시키기 위해 여러 개의 하드웨어를 사용하거나 태스크를 수행하고 남는 시간을 이용하는 기법들이 많이 사용되고 있다.
본 논문에서는 과도 고장 하에서 모듈 및 시간 여유를 이용하여 내고장성 실시간 제어 시스템을 연구하였다. 모듈 여유로는 이중화 구조를 시간 여유로는 체크 포인팅 (checkpointing) 기법을 사용한 DMTR 시스템을 제안하여 이 시스템에 대한 연구를 수행하였다.
첫 번째로, DMTR 시스템의 기본적인 개념과 DMTR 시스템의 내고장 전략에 대해 기술하였다. 이산 Markov 모델 (discrete Markov model)을 사용하여 주어진 하나의 태스크와 환경 파라메터 (parameter)에 대한 상태천이확률행렬 (STPM: State Transition Probability Matrix)들을 구하고, 이를 이용하여 독립적 고장 (independent fault)과 의존적 고장 (correlated fault)와 같은 과도 고장 하에서 DMTR 시스템의 구현상 존재하는 오버헤드 (overhead) 시간을 고려한 DMTR 시스템의 신뢰도 모델을 구하였다. 이렇게 구한 시스템 모델의 수치적 시뮬레이션을 통하여 주어진 환경과 태스크를 가진 DMTR 시스템의 최대 신뢰도를 가지는 subslot의 개수를 구하였다.
두 번째로, 최근에는 점점 다양한 기능을 가진 시스템이 필요해짐에 따라 멀티 태스크 시스템에 대한 해석이 필요하게 되었다. 먼저, 간단하면서도 명료한 해석을 위해 조화된 주기 (harmonic period)를 가진 멀티 태스크에 대하여 DMTR 시스템의 신뢰도 모델을 구하였다. 이를 위해, 하나의 최소 주기를 단위로 각 태스크들에 대한 상태천이확률행렬들을 구하고, 이를 이용하여 하나의 하이퍼 주기 (hyper-period)동안의 상태천이확률행렬을 구하여 DMTR 시스템의 신뢰도 모델을 구하였다. 이렇게 구해진 신뢰도 모델로부터 신뢰도를 구하는 과정에 상당히 많은 반복 계산으로 인해 계산 시간이 너무 오래 걸리는 것을 개선하기 위해, 구한 신뢰도 모델 식의 반복되는 부분을 찾아 성질을 조사하여 재귀적인 형태로 재구성함으로써, 계산 시간을 상당히 단축시킬 수 있었다. 이렇게 구한 DMTR 시스템의 모델을 이용하여 일정한 오버헤드 시간을 고려하여 다양한 파라메터의 변화와 subslot의 개수의 변화에 따른 신뢰도 변화의 경향을 수치적 시뮬레이션을 통해 조사해 보았다. 또한, 주어진 환경과 태스크들에 대한 DMTR 시스템이 최대 신뢰도를 가지는 subslot의 개수도 구하였다. 더 나아가서, 기존의 DMR 시스템, GCDP 스케줄 기법을 적용한 DMTR 시스템 및 RM 스케줄 기법을 적용한 DMTR 시스템의 신뢰도를 비교 분석하였다.
세 번째로, 조화된 주기를 가진 멀티 태스크를 가진 시스템은 일반 주기 (general period)를 가진 멀티 태스크의 특수한 형태로 실제로는 일반 주기를 가진 멀티 태스크가 더 많다. 따라서, 본 논문에서는 일반 주기를 가진 멀티 태스크 DMTR 시스템에 대한 신뢰도 모델의 구하였다. 일반 주기를 가진 멀티 태스크 시스템인 경우에는 적용되는 스케줄 기법에 따라 다른 태스크 수행 결과를 보이는데, 본 연구에서는 현재 가장 널리 연구되고 사용되고 있는 RM (Rate Monotonic) 스케줄 기법과 EDF (Earliest Deadline First) 스케줄 기법을 적용하여 일반 주기를 가진 멀티 태스크 DMTR 시스템의 신뢰도 모델을 각각 구하였다. 일반 주기를 가진 멀티 태스크에 대한 해석의 어려운 점은 어떤 시점에서 어떤 태스크에 대한 여유 시간을 구하기 어렵고, EDF의 경우에는 태스크의 우선순위가 바뀌는 것을 수식에 적용하기가 불가능하다는 점이다. 본 논문에서는 period-edge-interval을 정의하고, 성질을 조사하여 신뢰도 해석에 반영함으로써 이를 해결할 수 있었다. 일반 주기를 가진 멀티 태스크 DMTR 시스템에 대해서도 주어진 환경 파라메터와 태스크들에 대하여 subslot의 개수 변화에 따른 신뢰도 변화 경향을 조사 분석하였다.
끝으로, 본 연구에서는 지금까지 구한 다양한 경우에 대한 DMTR 시스템의 모델 및 수치적 시뮬레이션 결과를 종합 정리하여 앞으로 DMTR 시스템을 구현하고자 하는 사람들에게 고신뢰도의 시스템 구현을 위한 설계 지침을 제안하였다.
