Scheduling Issues in Real-Time Systems

Abstract

The most important objective of real-time systems is to fulfill time-critical missions in satisfying their application requirements and timing constraints. Software utilities can analyze real-time tasks and extract their characteristics and requirements for assisting the systems to guarantee schedulability. Real- time scheduling is the core of the real-time system design. It should allow real-time systems to exhibit predictable timing correctness regardless of possible uncertainty in run-time environments. In this dissertation, we study the problem of scheduling real-time tasks with resource and fault-tolerance requirements. For tasks with resource requirements, two types of platforms are examined: multiprocessor hard real-time systems and real-time database systems; for task with fault-tolerance requirements, we focus on hard real-time systems. We investigate preemptive priority-based scheduling for tasks with resource requirements in context of hard real-time systems. Rate-monotonic and earliest deadline first priority assignment strategies can meet deadlines if the schedulability conditions are satisfied. We propose resource control protocols, for these scheduling strategies, based on the concepts of priority inheritance and priority ceiling and describe schedulability conditions for meeting deadlines. Real-time database systems have different objectives for transaction scheduling. Minimizing miss ratio usually is the major concern. We study the significance of the knowledge of execution time in system performance and propose a class of optimistic concurrency control protocols using the knowledge of execution time. Our simulation results indicate that the knowledge of execution time substantially improve system performance. Fault-tolerance is an ability to maintain system in a safe and stable state such that the real-time application functions correctly and its timing constraints are satisfied even in the presence of faults. We develop a scheduling algorithm which attempts to build as many fault-tolerant tasks as possible into a schedule. We approximate system reliability by Markov chain models and illustrate the applicability of the proposed reliability models. We compare the proposed fault-tolerance scheduling approach with the basic fault-tolerance scheduling schemes and the simulation results show that our method provides better reliability than the basic scheduling schemes. (Also cross-referenced as UMIACS-TR-95-73)