Fault-tolerance as well as timeliness is an important requirement in safty-critical real-time systems such as nuclear-reactor control and aircraft navigation system. But providing fault-tolerance often requires additional time for the recovery operation, which may cause real-time tasks to miss deadline. Recently a responsiveness measure has been proposed to combine the traditional measures of fault-tolerance and real-time with the objective of cooptimizing these dependent system qualities, and it has been applied to the real-time system which provides recovery blocks. A scheduling algorithm which can efficiently manage the additional processing time caused by the recovery operation can improves this measure.
In this thesis, a real-time fixed priority scheduling algorithm providing recovery blocks is proposed and its performance is compared with previous algorithms by responsiveness. The proposed algorithm uses rate-monotonic assignments as its base, but considers the characteristics of recovery blocks and assigns proper priorities to them so that each recovery block has its own priority which may be different from the one of its primary task.
To use the responsiveness as a performance metric, the complexity problem of evaluating responsiveness is also considered. Evaluation of responsiveness has computational complexity of O(Mㆍ$2^M$), where M is the number of task instances in a major cycle. A method which evaluates an approximated value of responsiveness with high exactness and low complexity is proposed. The proposed method guarantees the lower bound of approximation within given complexity.
