24, May, 2016 11:30-12:30 (1 hour)
CISTER, Porto, Portugal

ABSTRACT:
The Quasi-Partitioning Scheduling algorithm optimally solves the problem of scheduling a feasible set of independent implicit-deadline sporadic tasks on a symmetric multiprocessor. It iteratively combines bin-packing solutions to determine a feasible task-to-processor allocation, splitting task loads as needed along the way so that the excess computation on one processor is assigned to a paired processor. Though different in formulation, QPS belongs in the same family of schedulers as RUN, which achieve optimality using a relaxed (partitioned) version of proportionate fairness. Unlike RUN, QPS departs from the dual schedule equivalence, thus yielding a simpler implementation with less use of global data structures. One might therefore expect that QPS should outperform RUN in the general case. Surprisingly instead, our implementation of QPS on LITMUS^RT invalidates this conjecture, showing that the QPS offline decisions may have an important influence on run-time performance. In this work, we present an extensive comparison between RUN and QPS, looking at both the offline and the online phases, to highlight their relative strengths and weaknesses.

EVENT PHOTOS:
At CISTER's Facebook page / At CISTER's Instagram page

DOWNLOAD:
PDF Presentation (1.4 MB)

CISTER's main roles: