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

• 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.

Ämnesord

NATURVETENSKAP  -- Data- och informationsvetenskap -- Datorteknik (hsv//swe)

NATURAL SCIENCES  -- Computer and Information Sciences -- Computer Engineering (hsv//eng)

NATURVETENSKAP  -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)

NATURAL SCIENCES  -- Computer and Information Sciences -- Computer Sciences (hsv//eng)

Nyckelord

partitioning

shared-memory multiprocessors

bin-packing algorithms

preemptive scheduling

fixed-priority scheduling

dynamic binding

multiprocessors

non-partitioned method

global scheduling

Real-time scheduling

Publikations- och innehållstyp

kon (ämneskategori)

ref (ämneskategori)