An optimal resource sharing protocol for generalized multiframe tasks

Abstract Many different task models of varying expressiveness have been proposed to capture the timing constraints of real-time workloads. However, techniques for optimal scheduling and exact feasibility analysis of systems with mutually-exclusive shared resources have been available only for relatively simple task models, such as the sporadic task model. We consider sharing of mutually-exclusive resources in task models that are more expressive in terms of the job-release patterns that can be modeled. We propose a new scheduling algorithm and show that it is optimal for scheduling generalized multiframe tasks with shared resources on uniprocessor systems. We also present an efficient feasibility test for such systems, and show that it is both sufficient and necessary.