Accession Number:

ADA461102

Title:

Scheduling Dependent Real-Time Activities

Descriptive Note:

Doctoral thesis

Corporate Author:

CARNEGIE-MELLON UNIV PITTSBURGH PA SCHOOL OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

1990-08-01

Pagination or Media Count:

259.0

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.

Subject Categories:

  • Numerical Mathematics
  • Computer Systems
  • Command, Control and Communications Systems

Distribution Statement:

APPROVED FOR PUBLIC RELEASE