Abstract | |
|
Back to Advance Program
Using Supertasks to Improve Processor Utilization in Multiprocessor Real-time SystemsPhilip Holman and James H. AndersonTo appear at Euromicro Conference on Real-Time Systems (ECRTS03), Porto, Portugal, 2-4 July 2003
AbstractWe revisit the problem of supertasking in Pfair-scheduled multiprocessor systems. In this approach, a set of tasks, called component tasks, is assigned to a server task, called a supertask, which is then scheduled as an ordinary Pfair task. Whenever a supertask is scheduled, its processor time is allocated to its component tasks according to an internal scheduling algorithm. In this paper, we present a generalized "reweighting" algorithm. The goal of reweighting is to assign a fraction of a processor to a given supertask so that all timing requirements of its component tasks are met. The generalized reweighting algorithm we present breaks new ground in three important ways. First, component tasks are permitted to have non-integer execution costs. Consequently, supertasking can now be used to ameliorate schedulability loss due to the integer-cost assumption of Pfair scheduling. Second, blocking terms are included in the analysis. Blocking terms are needed to account for a wide range of behaviors commonly found in actual systems. Finally, the scope of supertasking has been extended by employing a more flexible global-scheduling model that does not assume strict Pfairness. To demonstrate the efficacy of the supertasking approach, we present an experimental evaluation of our algorithm that suggests that reweighting may often result in almost no schedulability loss in practice.
10 Mar 2003 at 21:02:27 |