Optimal utilization bounds for the fixed-priority scheduling of periodic task systems on identical multiprocessors

In fixed-priority scheduling, the priority of a job, once assigned, may not change. A new fixed-priority algorithm for scheduling systems of periodic tasks upon identical multiprocessors is proposed. This algorithm has an achievable utilization of (m + 1)/2 upon m unit-capacity processors. It is proven that this algorithm is optimal from the perspective of achievable utilization in the sense that no fixed-priority algorithm for scheduling periodic task systems upon identical multiprocessors may have an achievable utilization greater than (m + 1)/2.