Exact and heuristic algorithms for thrift cyclic scheduling

DOI10.3390/A2041449MaRDI QIDQ1662520zbMATH OpenOpenAlexFDO

Authors Michael J. Short

Publication date 20 August 2018

Published in Algorithms (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.3390/a2041449

zbMATH Keywords

complexityheuristicsnon-preemptive schedulingoffset-assignment

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Deterministic scheduling theory in operations research (90B35)

Review text

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.

Recommendations

• Scheduling of offset free systems
• Scheduling Periodic Tasks
• Scheduling cyclic tasks with binary periods
• Nonpreemptive scheduling of periodic tasks in uni- and multiprocessor systems
• A new algorithm for scheduling periodic, real-time tasks

Cites work

• A note on `Efficient scheduling of periodic information monitoring requests'
• An Application of Bin-Packing to Multiprocessor Scheduling
• Bounds on Multiprocessing Timing Anomalies
• Efficient scheduling of periodic information monitoring requests
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2153624 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• Scheduling of offset free systems
• Vehicle minimization for periodic deliveries

Cited in

(2)

• Scheduling of offset free systems
• On fixed priority scheduling, offsets and co-prime task periods

This page was built for publication: Exact and heuristic algorithms for thrift cyclic scheduling

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1662520)