Static Approximation Algorithms for Regularity-based Resource Partitioning

As a hierarchical real-time system framework, the Regularity-based Resource Partition Model allocates physical resources in time intervals determined by integral numbers of a time unit to tasks in different applications. A Regularity-based Resource Partition is characterized by its regularity and availability factor. An important problem is how to schedule a group of resource partitions with the specification of their regularities and availability factors. Mok and Feng have provided the AAF-Single algorithm which works only on a single-resource platform. Li and Cheng have recently extended AAF-Single to AAF-Multi for multiresource platforms without violating the schedulability bound given by Feng. However, the resource utilization of these two algorithms could be significantly improved. This paper is dedicated to developing optimized resource partitioning algorithms for the Regularity-base Resource Partition Model. We first decompose the resource partitioning problem into two sub problems, and invoke the Pfair algorithm to solve the first sub problem. Then we introduce a category of approximation algorithms called Static Approximation Algorithms (SAA) to solve the second sub problem. An SAA adjusts the availability factors of the resource partitions with a specific boundary sequence. We prove that the schedulability bound of any feasible SAA is at most 0.5. Furthermore, we develop an optimal SAA called Magic7. Simulation shows that Magic7-enhanced algorithms improve the resource utilization by 10% or more.