Enhanced fixed-priority scheduling with (m,k)-firm guarantee
Gang Quan, Xiaobo Sharon Hu · 2002
Studies the problem of scheduling task sets with (m,k) constraints. In our approach, jobs of each task are partitioned into two sets: mandatory and optional. Mandatory jobs are scheduled according to their pre-defined priorities, while optional jobs are assigned to the lowest priority. We show that finding the optimal partition as well as determining the schedulability of the resultant task set are both NP-hard problems. A new technique, based on the general Chinese remainder theorem, is proposed to quantify the interference among tasks, which is then used to derive two partitioning approaches. Furthermore, a sufficient condition is presented to predict, in polynomial time, the schedulability of mandatory jobs. We prove that our partitions are never worse than those obtained in previous work. Experimental results also show significant improvement achieved by our approaches.