SEMAPHORE QUEUE PRIORITY ASSIGNMENT FOR REAL-TIME MULTIPROCESSOR SYNCHRONIZATION

Prior work on real-time scheduling with global shared resources in multiprocessor systems assigns as much blocking as possible to the lowest-priority tasks. In this paper, we show that better schedulability can be achieved if global blocking is distributed according to the blocking tolerance of tasks rather than their execution priorities. We describe an algorithm that assigns global semaphore queue priorities according to blocking tolerance, and we present simulation results demonstrating the advantages of this approach with rate monotonic scheduling. Our simulations also show that a simple FIFO usually provides better real-time schedulability with global semaphores than priority queues that use task execution priorities.