| Name: | Description: | Size: | Format: | |
|---|---|---|---|---|
| 885.08 KB | Adobe PDF |
Advisor(s)
Abstract(s)
Dynamic parallel scheduling using work-stealing has gained popularity in academia and industry for its good
performance, ease of implementation and theoretical bounds on space and time. Cores treat their own double-ended
queues (deques) as a stack, pushing and popping threads from the bottom, but treat the deque of another randomly
selected busy core as a queue, stealing threads only from the top, whenever they are idle.
However, this standard approach cannot be directly applied to real-time systems, where the importance of parallelising
tasks is increasing due to the limitations of multiprocessor scheduling theory regarding parallelism. Using one deque per
core is obviously a source of priority inversion since high priority tasks may eventually be enqueued after lower priority
tasks, possibly leading to deadline misses as in this case the lower priority tasks are the candidates when a stealing
operation occurs.
Our proposal is to replace the single non-priority deque of work-stealing with ordered per-processor priority deques of
ready threads. The scheduling algorithm starts with a single deque per-core, but unlike traditional work-stealing, the
total number of deques in the system may now exceed the number of processors. Instead of stealing randomly, cores
steal from the highest priority deque.
Description
Keywords
Citation
Publisher
IPP Hurray! Research Group