Reducing Queue Lock Pessimism in Multiprocessor Schedulability Analysis

Although many multiprocessor resource sharing protocols have been proposed, their impacts on the schedulability of real-time tasks are largely ignored in most of the existing literature. Recently, work has been done to integrate queue locks (FIFO-queue-based non-preemptive spin locks) with multiprocessor schedulability analysis but the techniques used introduce a substantial amount of pessimism. For global fixed task priority preemptive multiprocessor systems, this pessimism impacts low priority tasks, greatly reducing the number of tasksets that can be recognised as schedulable. A new schedulability analysis lp-CDW is designed specifically for analyzing low priority tasks much more accurately. However, this analysis cannot retain its accuracy when it is used to analyze high priority tasks. Existing techniques outperform lp-CDW in such cases. By combing lp-CDW with existing techniques, we get a hybrid analysis, which performs well at all priorities and therefore significantly increases the number of tasksets that can be recognised as schedulable.