Preemption Threshold Scheduling: Stack Optimality, Enhancements and Analysis

Using preemption threshold scheduling (PTS) in a multi-threaded real-time embedded system reduces sys-tem preemptions and hence reduces run-time overhead while still ensuring real-time constraints are met. How-ever, PTS offers other valuable benefits. In this paper we investigate the use of PTS for hard real-time sys-tem with limited RAM. Our primary contribution is to prove the optimality of PTS among all preemption-limiting methods for minimizing a system’s total stack memory requirements. We then discuss characteristics of PTS and show how to reduce average worst-case re-sponse times. We also introduce a unified framework for using PTS with existing fixed-priority (e.g. rate-or deadline-monotonic), or dynamic-priority schedul-ing algorithms (e.g. earliest-deadline first). We evaluate the performance of PTS and our im-provements using synthetic workloads and a real-time workload. We show PTS is extremely effective at reduc-ing stack memory requirements. Our enhancements to PTS improve worst-case response-times as well. 1