Abstract
We consider a characterization of a real time system consisting as a set of sporadic tasks that share a set of serially reusable, single unit resources. Sporadic tasks are a generalization of periodic tasks and are well- suited for representing even driven processes. Resources are shared software objects, such as data structures. Tasks are composed of a sequence of phases. Each phase is a contiguous sequence of statements that require exclusive access to a resource. For an arbitrary instance of the model the goal is to determine if it is possible to schedule the tasks on a single processor such 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. Our work makes two contributions to the theory of real-time scheduling and resource allocation. The first is the development of an on line algorithm for sequencing a set of sporadic tasks on a uniprocessor such that the above criteria are met. The second contribution is a derivation of a set of relations on task parameters that are necessary and sufficient for a set of tasks to be schedulable.