Analyzing fixed-priority global multiprocessor scheduling

We consider a multiprocessor where hard real-time tasks are scheduled globally on in processors. Each task has a fixed priority and tasks are executed using preemptive scheduling. The state-of-the-art priority assignment scheme in such cases is called RM-US[US-LIMIT], where US-LIMIT is a parameter to the RM-US algorithm. The challenge is to find the US-LIMIT that can guarantee schedulability for as high utilization as possible. The previously best known US-LIMIT value could guarantee schedulability as long as the multiprocessor utilization is below m/(3m-2), i.e. 0.33333 when m→∞. In this paper we define a new equation for US-LIMIT which guarantees schedulability for higher utilization values than the previous result. When m→∞ we can now guarantee schedulability, for all tasks sets when the multiprocessor utilization is below 0.37482. We also show that our US-LIMIT values are optimal, i.e. we show that there is no room for further improvement of this state-of-the-art priority assignment scheme.