An embedded real-time system, as its name implies, possesses the characteristics of both an embedded system and a real-time system. An embedded system is one that is of special purpose, often a uniprocessor system, and generally is not user-programmable. In addition, a real-time system is one that must perform operations within rigid timing constraints. In many cases, embedded real-time systems must provide long period of uninterrupted service in harsh and dynamic environments. The importance of reliability in embedded real-time systems will increase dramatically as future computers take a more active role in everyday life and industrial sectors. In addition, transient faults in semiconductor devices are becoming more significant because of increased density, low supply voltage, and fast switching signals.
This thesis deals with fault tolerance technique to cope with transient faults for embedded real-time systems. Transient faults are usually overcome using time redundancy, and a typical implementation of time redundancy is checkpointing. Thus, checkpointing problems in embedded real-time systems are explored from a reliability point of view.
A reliability model of a static equidistant checkpointing scheme with non-concurrent fault detection mechanisms is derived. With non-concurrent fault detection mechanisms, faults are detected by some check mechanisms which are performed regularly. Therefore, the latency in detection is inevitable. In deriving the reliability model, the average life time of transient faults is considered, and the derived reliability model is verified by simulations. Based on the reliability model, some sufficient conditions under which a static equidistant checkpointing scheme works positively are discussed. In addition, an optimal strategy which maximizes the system reliability is proposed.
Concurrent fault detection mechanisms can detect faults with significantly less detection latency than non-concurrent mechanisms do. Accordingly, a system with concurrent fault detection capability may suffer from less time loss caused by transient faults than a system with non-concurrent detection capability does. A reliability model for a static equidistant checkpointing scheme with concurrent fault detection capability is derived. In addition, some sufficient conditions and an optimal strategy from a reliability point of view are discussed.
Based on the results from the aforementioned static checkpointing schemes, dynamic checkpointing schemes for reliability are derived. Although these dynamic schemes need a little more computational overhead than the static schemes, they outperform the static schemes.
In most embedded systems, the program codes for tasks reside in RAMs (random access memory) while the systems are operating. Checkpointing schemes can not tolerate transient faults which cause bit errors in the code area of RAMs. When program codes for tasks are damaged by transient faults, they can not be recovered using checkpoints because checkpoints contain only the states of tasks. Memory scrubbing can be a solution to this problem. A new memory scrubbing technique for embedded systems is proposed, which exploits the in-formation stored in ROMs (read only memory). With the proposed memory scrubbing technique, the reliability of the code area in RAMs against transient faults can be improved without additional overhead.
내장형 실시간 시스템 (embedded real-time system)은 내장형 시스템 (embedded system)과 실시간 시스템 (real-time system)의 특성을 모두 갖고 있다. 내장형 시스템은 주로 특수 목적에 사용되는 단일 프로세서 (processor) 컴퓨터로서 사용자가 실행되는 프로그램을 변경할 수 없는 경우가 대부분이며, 범용 컴퓨터 시스템과 달리 소비 전력, 크기, 제작 비용, 계산 성능, 저장 장치 등에 상당한 제한이 따르게 된다. 그리고 실시간 시스템은 요구되는 작업을 주어진 엄격한 시간 조건을 만족하며 완수하여 하는 시스템을 말한다. 많은 경우에, 내장형 실시간 시스템은 열악하고 급변하는 환경 속에서 중단 없이 오랜 시간 동작하여야 한다. 일상 생활 및 산업 부문에 있어서 컴퓨터의 활용 범위 및 영향이 급격히 확대되어 감에 따라 내장형 실시간 시스템의 신뢰성에 대한 요구는 갈수록 늘어갈 것이다. 또한, 반도체 소자의 급격한 집적도 증가, 사용 전압 감소, 동작 속도 증대 등에 따라 일시적 결함 (transient faults)의 영향이 매우 증대될 것이다.
본 연구는 내장형 실시간 시스템에서 발생 가능한 일시적 결함을 극복하기 위한 내고장성 (fault tolerance) 기법을 다루었다. 일시적 결함은 주로 시간 여유 (time redundancy) 기법을 이용하여 극복되며, 그 대표적인 예가 Checkpointing 기법이다. 따라서, 내장형 실시간 시스템의 신뢰도 향상을 위한 Checkpointing 기법에 관한 문제들을 다루었고, Checkpointing 기법의 약점을 보완해 줄 수 있는 새로운 메모리 세정 (memory scrubbing) 방안이 제안되었다.
우선, 비병행 (non-concurrent) 결함 검출 기능이 있는 시스템에서의 정적 등간격 (static equidistant) Checkpointing 기법에 대한 신뢰도 모델을 유도하였다. 비병행 결함 검출 기능이 적용되면, 결함 발생에 대한 검사 작업이 일정 주기로 실행된다. 따라서, 결함의 발생과 검출에 상당한 시간차가 존재하게 된다. 발생한 결함은 무작위적인 시간 동안 시스템에 영향을 주게되는데, 문제의 복잡도를 낮추기 위하여 결함의 평균 수명을 고려하여 신뢰도 모델을 유도하였다. 모의 실험을 위하여 정적 등간격 Checkpointing 기법이 적용되는 시스템을 Discrete Event System Specification (DEVS) 형식론을 이용하여 모델링하였으며, 이를 이용한 모의 실험을 통하여 유도된 신뢰도 모델을 검증하였다. 또한, 신뢰도 모델을 이용하여 동적 등간격 Checkpointing 기법이 시스템의 신뢰도를 개선할 수 있는 충분 조건들을 유도하고, 주워진 상황에서 시스템의 신뢰도를 최대화할 수 있는 최적 기법이 제안되었다.
비병행 결함 검출 방법과 달리, 병행 (concurrent) 결함 검출 방법은 결함의 발생과 검출 사이에 시간 지연이 거의 없다. 따라서, 병행 결함 검출기능이 있는 시스템은 결함 발생 시, 이로 인해 손실되는 시간이 비병행 결함 검출 기능을 갖춘 시스템에 비해 상당히 작다. 이러한 병행 결함 검출 기능이 구현된 시스템에 대해, 정적 등간격 Checkpointing 기법의 신뢰도 모델을 유도하고, 이를 바탕으로 정적 등간격 Checkpointing 기법이 시스템의 신뢰도를 개선할 수 있는 충분 조건과 최적 기법을 논의하였다.
앞서 언급된 정적 Checkpointing 기법에 대한 결과를 이용하여, 시스템의 신뢰도를 고려한 동적 Checkpointing 기법을 소개하였다. 동적 Checkpointing 기법에서는 다음 Checkpointing 동작을 실행할 시간이 앞으로 Task가 성공적으로 실행될 가능성을 최대화하도록 정해진다. 따라서, Checkpoint들 사이의 간격이 일정하지 않게 되며, 약간의 계산량 부담이 발생한다. 비병행 결함 검출 기능을 갖춘 시스템에서의 동적 Checkpointing 기법에 대한 신뢰도 모델을 재귀적인 방법을 이용하여 유도하였으며, 이를 모의 실험을 통하여 검증하였다. 그러나, 병행 결함 검출 기능을 갖춘 시스템에 대해서는 모의 실험 결과만 논의되었다. 신뢰도 해석 및 모의 실험을 통하여 동적 Checkpointing 기법이 정적 Checkpointing 기법보다 성능면에서 우세함을 보였다.
대부분의 내장형 시스템의 프로그램 코드와 데이타는 시스템 가동 시 RAM (random access memory)에 존재하게된다. 각각은 RAM의 주소 공간 중 코드 영역과 데이터 영역에 존재하며, 일시적 결함으로 인해 일시적 비트 오류 (transient bit error)를 겪을 수 있다. RAM의 데이터 영역에서 발생하는 일시적 비트 오류는 Checkpointing 기법을 이용해 극복이 가능하지만, 코드 영역에 발생한 오류에 대해서는 Checkpointing 기법을 적용할 수 없다. 코드 영역에서 발생한 오류는 해당 코드에 대한 올바른 값을 다시 기입해주어야만 복구될 수 있으며, RAM과 같은 휘발성 기억 소자에서 발생할 수 있는 일시적 비트 오류를 대응할 수 있는 방법으로 메모리 세정이 주로 사용되고 있다. 본 연구는 대부분의 내장형 시스템의 프로그램 코드가 ROM (read only memory)에 저장되어 있는 점을 이용한 메모리 세정 기법을 소개하였다. 이 기법을 적용하면 추가의 메모리 세정 부담 없이 RAM에 저장되어 있는 정보의 신뢰도를 개선할 수 있으며, 코드 영역의 비트 오류에 대응할 수 없는 Checkpointing 기법의 약점을 보완하여 시스템 전체의 신뢰도를 개선할 수 있다.
더욱 정확한 Checkpointing 기법의 신뢰도 모델 유도를 위해서는 일시적 결함의 지속 시간에 대한 분포와 Task의 실행 시간의 분포를 고려할 필요가 있다.
