Exact and heuristic algorithms for thrift cyclic scheduling (Q1662520)

Summary: Non-preemptive schedulers, despite their many discussed drawbacks, remain a very popular choice for practitioners of real-time and embedded systems. The non-preemptive `thrift' cyclic scheduler -- variations of which can be found in other application areas -- has recently received considerable attention for the implementation of such embedded systems. A thrift scheduler provides a flexible and compact implementation model for periodic task sets with comparatively small overheads; additionally, it can overcome several of the problems associated with traditional `cyclic executives'. However, severe computational difficulties can still arise when designing schedules for non-trivial task sets. This paper is concerned with an optimization version of the offset-assignment problem, in which the objective is to assign task offsets such that the required CPU clock speed is minimized whilst ensuring that task overruns do not occur; it is known that the decision version of this problem is complete for \(\Sigma_2^{\mathrm p}\). The paper first considers the problem of candidate solution verification -- itself strongly coNP-complete -- and a fast, exact algorithm for this problem is proposed; it is shown that for any \textit{fixed} number of tasks, its execution time is polynomial. The paper then proposes two heuristic algorithms of pseudopolynomial complexity for solving the offset-assignment problem, and considers how redundant choices of offset combinations can be eliminated to help speed up the search. The performance of these algorithms is then experimentally evaluated, before conclusions are drawn.