Scheduling Dependent Real-Time Activities
Abstract
A real-time application is typically composed of a number of cooperating activities that must execute within specific time intervals. Since there are usually more activities to be executed than there are processors on which to execute them, several activities must share a single processor. Necessarily, satisfying the activities timing constraints is a prime concern in making the scheduling decisions for that processor. Unfortunately, the activities are not independent. Rather, they share data and devices, observe concurrency constraints on code execution and send signals to one another. These interactions can be modeled as contention for shared resources that must be used by one activity at a time. An activity awaiting access to a resource currently held by another activity is said to depend on that activity, and a dependency relationship is said to exist between them. Dependency relationships may encompass both precedence constraints and resource conflicts. No algorithm solves the problem of scheduling activities with dynamic dependency relationships in a way that is suitable for all real-time systems. This thesis provides an algorithm, called DASA, that is effective for scheduling the class of real-time systems known as supervisory control systems. Simulation experiments that account for the time required to make scheduling decisions demonstrate that DASA provides equivalent or superior performance to other scheduling algorithms of interest under a wide range of conditions for parameterized. synthetic workloads. DASA performs particularly well during overloads. when it is impossible to complete all of the activities. This research makes a number of contributions to the field of computer science, including: a formal model for analyzing scheduling algorithms; the DASA scheduling algorithm, which integrates resource management with standard scheduling functions; results that demonstrate the efficacy of DASA in a variety of situations, and simulator.
Document Details
- Document Type
- Technical Report
- Publication Date
- Aug 01, 1990
- Accession Number
- ADA461102
Entities
People
- Raymond K. Clark
Organizations
- Carnegie Mellon University