Some complexity results concerning the non-preemptive 'thrift' cyclic scheduler

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Citations (Scopus)

Abstract

Non-preemptive schedulers, despite their many perceived drawbacks, remain a very popular choice for practitioners of real-time and embedded systems. Although feasibility conditions for non-preemptive scheduling models have previously been considered in the literature, to date little attention has been paid to the non-preemptive 'thrift' (or 'TTC') cyclic scheduler. This type of scheduler differs from a standard 'cyclic executive' in that it does not allow the use of inserted idle-time, and it does not require a lookup table of task executions over the major cycle of the schedule; a feasible schedule is effectively created by assigning release times ('offsets') to the tasks. To this end, this paper seeks to address the complexity of generating a feasible cyclic schedule for such a scheduler. It will be shown that when a single set of release times is assigned to the tasks, deciding feasibility of the resulting schedule is coNP-Complete (in the strong sense); and the release time assignment problem for such a scheduler is complete for Σ2P.

Original languageEnglish
Title of host publicationICINCO 2009 - 6th International Conference on Informatics in Control, Automation and Robotics, Proceedings
Pages347-350
Number of pages4
Publication statusPublished - 1 Dec 2009
Event6th International Conference on Informatics in Control, Automation and Robotics - Milan, Italy
Duration: 2 Jul 20095 Jul 2009

Conference

Conference6th International Conference on Informatics in Control, Automation and Robotics
Abbreviated titleICINCO 2009
CountryItaly
CityMilan
Period2/07/095/07/09

Cite this

Short, M. (2009). Some complexity results concerning the non-preemptive 'thrift' cyclic scheduler. In ICINCO 2009 - 6th International Conference on Informatics in Control, Automation and Robotics, Proceedings (pp. 347-350)