Reducing Queue Lock Pessimism in Multiprocessor Schedulability Analysis

Y. Chang; R. I. Davis; A. J. Wellings

Reducing Queue Lock Pessimism in Multiprocessor Schedulability Analysis

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

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.

Original language	English
Title of host publication	International conference on Real-Time and Network Systems
Pages	99-108
Publication status	Published - Nov 2010
Event	18th International Conference on Real-Time and Network Systems (RTNS 2010) - Toulouse, France Duration: 4 Nov 2010 → 5 Nov 2010

Conference

Conference	18th International Conference on Real-Time and Network Systems (RTNS 2010)
Country/Territory	France
City	Toulouse
Period	4/11/10 → 5/11/10

Keywords

real-time
multiprocessor
blocking
scheduling
schedulability analysis

Access to Document

Cite this

@inproceedings{702d70bd7d2c45af9c61a5835a068b00,

title = "Reducing Queue Lock Pessimism in Multiprocessor Schedulability Analysis",

abstract = "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.",

keywords = "real-time, multiprocessor, blocking, scheduling, schedulability analysis",

author = "Y. Chang and Davis, {R. I.} and Wellings, {A. J.}",

year = "2010",

month = nov,

language = "English",

pages = "99--108",

booktitle = "International conference on Real-Time and Network Systems",

note = "18th International Conference on Real-Time and Network Systems (RTNS 2010) ; Conference date: 04-11-2010 Through 05-11-2010",

}

TY - GEN

T1 - Reducing Queue Lock Pessimism in Multiprocessor Schedulability Analysis

AU - Chang, Y.

AU - Davis, R. I.

AU - Wellings, A. J.

PY - 2010/11

Y1 - 2010/11

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

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

KW - real-time

KW - multiprocessor

KW - blocking

KW - scheduling

KW - schedulability analysis

M3 - Conference contribution

SP - 99

EP - 108

BT - International conference on Real-Time and Network Systems

T2 - 18th International Conference on Real-Time and Network Systems (RTNS 2010)

Y2 - 4 November 2010 through 5 November 2010

ER -