On the Processor Utilisation Bound of the C=D Scheduling Algorithm
Ref: CISTER-TR-141208 Publication Date: 13 to 15, Mar, 2013
On the Processor Utilisation Bound of the C=D Scheduling Algorithm
Ref: CISTER-TR-141208 Publication Date: 13 to 15, Mar, 2013Abstract:
Under semi-partitioned multiprocessor scheduling some (or most) tasks
are partitioned to the available processors while the rest may migrate between different
processors, under a carefully managed scheme. One of the best performing
and practical to implement EDF-based semi-partitioned algorithms is C=D splitting.
Under this algorithm, each migrating task always executes at the highestpriority
on all but one of the processors that it uses. This arrangement allows for
efficient processor utilisation in general, however no utilisation bound had been
published so far for this algorithm. We address this situation by deriving the utilisation
bound of 13/18 for a variant of C=D with the following constraint: at most
one migrating task may utilise each processor. We also draw additional conclusions
for the utilisation bound attainable under a C=D task splitting scheme in the
general case.
José Augusto Santos Jr
George Lima
Konstantinos BletsasDocument:
View
DownloadReal-time Systems Workshop.
York, United Kingdom.
Record Date: 22, Dec, 2014