A New Scheduling Scheme in Responsive Systems

Seongbae EUN  Seung Ryoul MAENG  Jung Wan CHO  

IEICE TRANSACTIONS on Information and Systems   Vol.E78-D   No.10   pp.1282-1287
Publication Date: 1995/10/25
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Fault Tolerant Computing
real-time systems,  fault-tolerant computing,  responsive systems,  responsive scheduling,  responsiveness,  earliest deadline first,  

Full Text: PDF>>
Buy this Article

The integration of both real-time systems and fault-tolerant systems has been emerged as one of the greatest challenges of this decade. It is called a responsive system, which has the objective to optimeze both timeliness and reliability. The performance measure in responsive systems is responsiveness that tells how probable a system executes correctly on time with faults occurred. While there have been some achievements in communication protocols and specification, we believe that scheduling problems in responsive systems are not understood deeply and sufficiently, yet. In this paper, we discuss the scheduling problem in responsive systems. At first, we investigate the issues in the scheduling and propose the precise definition of the responsiveness. We also suggest a scheduling algorithm called Responsive Earliest Deadline First (REDF) for preemptive aperiodic tasks in a uniprocessor system. We show that REDF is optimal to obtain the maximum responsiveness, and the time complexity is analyzed to be (N 2N). By illustrating a contradictory example, it is shown that REDF can be enhanced if a constraint on tasks is released.