Scheduling Issues in Real-Time Systems
Scheduling Issues in Real-Time Systems
Files
Publication or External Link
Date
1998-10-15
Authors
Chen, Chia-Mei
Advisor
Citation
DRUM DOI
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)