Scheduling Sporadic Tasks with Shared Resources in Hard-Real-Time Systems

K. Jeffay
Proc. 13th IEEE Real-Time Systems Symposium
Phoenix, AZ, December 1992
pp. 89-99.

Abstract: The problem of scheduling a set of sporadic tasks that share a set of serially reusable, single unit software resources on a single processor is considered. The correctness conditions are that (1) each invocation of each task completes execution at or before a well-defined deadline, and (2) a resource is never accessed by more than one task simultaneously. We present an optimal on- line algorithm for scheduling a set of sporadic tasks. The algorithm results from the integration of a synchron- ization scheme for access to shared resources with the earliest deadline first algorithm. A set of relations on task parameters that are necessary and sufficient for a set of tasks to be schedulable is also derived. Our model for the analysis of processor scheduling policies is novel in that it incorporates minimum as well as maximum processing time requirements of tasks. The scheduling algorithm and the sporadic tasking model have been incorporated into an operating system kernel and used to implement several real-time systems.

Get a PostScript - or - PDF copy of this paper.

Back to Real-Time Systems Research at UNC page.