Analyzing Fixed Priority Global Multiprocessor Scheduling.

Document type: Conference Papers
Peer reviewed: Yes
Author(s): Lars Lundberg
Title: Analyzing Fixed Priority Global Multiprocessor Scheduling.
Conference name: 8th IEEE Real-Time and Embedded Technology and Applications Symposium
Year: 2002
Pagination: 145-153
ISBN: 0-7695-1739-0
Publisher: IEEE COMPUTER SOC
City: SAN JOSE, CA
ISI number: 000178662300014
Organization: Blekinge Institute of Technology
Department: Department of Software Engineering and Computer Science (Institutionen för programvaruteknik och datavetenskap)
Dept. of Software Engineering and Computer Science S-372 25 Ronneby
+46 455 38 50 00
http://www.bth.se/eng/ipd/
Authors e-mail: lars.lundberg@bth.se
Language: English
Abstract: We consider a multiprocessor where hard real-time tasks are scheduled globally on m 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] [1], where US-LIMIT is a parameter to the RM-US algorithm. The challenge is to find the US-LIMIT that can gaurantee schedulability for as high utilization as possible. The previously best known US-LIMIT value could guarantee schedulability as long the multiprocessor utilization is below m/(3m-2), i.e. 0.33333 when m --> infinity. In this paper we define a new equation for US-LIMIT which quarantees schedulability for higher utilization values than the previous result. When m --> infinity 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.
Subject: Computer Science\Computersystems
Edit