An optimal resource sharing protocol for generalized multiframe tasks

• We propose a scheduling algorithm for GMF tasks with shared resources.
• We prove that this algorithm is optimal, deadlock-free and enables stack sharing.
• We construct a feasibility test for GMF task sets with shared resources.
• The test is shown to be efficient, necessary and sufficient.

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.