Program

Resource Sharing Protocols for Real-Time Task Graph Systems

Abstract

Previous work on real-time task graph models have ignored the crucial resource sharing problem. Due to the nondeterministic branching behavior, resource sharing in task graph systems is fundamentally different from, and significantly more difficult than in the simple periodic or sporadic models.
In this work we address this problem with several different scheduling strategies, and quantitatively evaluate their performance. We first show that a direct application of the well-known EDF+SRP strategy (which is optimal for sporadic models) to graph-based models leads to an unbounded speedup factor. By slightly modifying EDF+SRP, we obtain a new scheduling strategy, called EDF+saSRP, which has a speedup factor of 2. Then we propose a novel resource sharing protocol, called ACP, to better manage resource sharing in the presence of branching structures. The scheduling strategy EDF+ACP, which applies ACP to EDF scheduling, can achieve a speedup factor of 1.618, which is the famous constant commonly known as the golden ratio.