SOME COMPLEXITY RESULTS CONCERNING THE NON-PREEMPTIVE ‘THRIFT’ CYCLIC SCHEDULER

Michael Short

2009

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.

Download


Paper Citation


in Harvard Style

Short M. (2009). SOME COMPLEXITY RESULTS CONCERNING THE NON-PREEMPTIVE ‘THRIFT’ CYCLIC SCHEDULER . In Proceedings of the 6th International Conference on Informatics in Control, Automation and Robotics - Volume 3: ICINCO, ISBN 978-989-8111-99-9, pages 347-350. DOI: 10.5220/0002177603470350

in Bibtex Style

@conference{icinco09,
author={Michael Short},
title={SOME COMPLEXITY RESULTS CONCERNING THE NON-PREEMPTIVE ‘THRIFT’ CYCLIC SCHEDULER},
booktitle={Proceedings of the 6th International Conference on Informatics in Control, Automation and Robotics - Volume 3: ICINCO,},
year={2009},
pages={347-350},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0002177603470350},
isbn={978-989-8111-99-9},
}


in EndNote Style

TY - CONF
JO - Proceedings of the 6th International Conference on Informatics in Control, Automation and Robotics - Volume 3: ICINCO,
TI - SOME COMPLEXITY RESULTS CONCERNING THE NON-PREEMPTIVE ‘THRIFT’ CYCLIC SCHEDULER
SN - 978-989-8111-99-9
AU - Short M.
PY - 2009
SP - 347
EP - 350
DO - 10.5220/0002177603470350