CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Fixed-Priority Preemptive Multiprocessor Scheduling: To Partition or not to Partition

Björn Andersson (Institutionen för datorteknik) ; Jan Jonsson (Institutionen för datorteknik)
Proceedings of the IEEE Conference on Real-Time Computing Systems and Applications, December 12−14, 2000, Cheju Island, South Korea (1530-1427). p. 337−346. (2000)
[Konferensbidrag, refereegranskat]

Traditional multiprocessor real-time scheduling partitions a task set and applies uniprocessor scheduling on each processor. For architectures where the penalty of migration is low, such as uniform-memory access shared-memory multiprocessors, the non-partitioned method becomes a viable alternative. By allowing a task to resume on another processor than the task was preempted on, some task sets can be scheduled where the partitioned method fails. We address fixed-priority scheduling of periodically arriving tasks on $m$ equally powerful processors having a non-partitioned ready queue. We propose a new priority-assignment scheme for the non-partitioned method. Using an extensive simulation study, we show that the priority-assignment scheme has equivalent performance to the best existing partitioning algorithms, and outperforms existing fixed-priority assignment schemes for the non-partitioned method. We also propose a dispatcher for the non-partitioned method which reduces the number of preemptions to levels below the best partitioning schemes.

Nyckelord: Real-time scheduling, non-partitioned method, dynamic binding, global scheduling, partitioning, bin-packing algorithms, fixed-priority scheduling, preemptive scheduling, multiprocessors, shared-memory multiprocessors

Den här publikationen ingår i följande styrkeområden:

Läs mer om Chalmers styrkeområden  

Denna post skapades 2009-06-02. Senast ändrad 2011-04-14.
CPL Pubid: 94584


Institutioner (Chalmers)

Institutionen för datorteknik (1985-2001)


Informations- och kommunikationsteknik
Datavetenskap (datalogi)

Chalmers infrastruktur