Optimal Fixed Priority Assignment with Limited Priority Levels

The schedulability utilization of fixed priority scheduling will be reduced greatly if priority levels of the system are insufficient. In this case, more than one task must be grouped into a same priority. This paper extends necessary and sufficient conditions for analyzing the schedulability of fixed priority algorithms on resources with limited priority levels. We develop an optimal fixed priority assignment algorithm (FPA) with limited priority levels. As it turns out, FPA is optimal in the sense that no other fixed priority rule can schedule a task set that can’t be scheduled by FPA and the priority levels required by FPA algorithm is minimum. Furthermore, in order to reduce its time complexity, an improved algorithm (OFPA) is presented. The simulation results show that the schedulability ratio of FPA and OFPA is much higher than that of Constant Ratio Grid algorithm.