On the Processor Utilisation Bound of the C=D Scheduling Algorithm
José Santos Júnior, George Marconi de Araujo Lima, Konstantinos Bletsas · 2013
Under semi-partitioned multiprocessor scheduling some (or most) tasksare partitioned to the available processors while the rest may migrate between differentprocessors, under a carefully managed scheme. One of the best performingand practical to implement EDF-based semi-partitioned algorithms is C=D splitting.Under this algorithm, each migrating task always executes at the highestpriorityon all but one of the processors that it uses. This arrangement allows forefficient processor utilisation in general, however no utilisation bound had beenpublished so far for this algorithm. We address this situation by deriving the utilisationbound of 13/18 for a variant of C=D with the following constraint: at mostone migrating task may utilise each processor. We also draw additional conclusionsfor the utilisation bound attainable under a C=D task splitting scheme in thegeneral case. © CISTER Research Center www.cister.isep.ipp.pt 1 On the Processor Utilisation Bound of the C=D Scheduling Algorithm J. Augusto Santos-Jr∗, George Lima∗, and Konstantinos Bletsas+ ∗Federal University of Bahia, Salvador, Brazil +CISTER/INESC-TEC Research Centre, ISEP, Porto, Portugal Abstract. 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. 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.