Scalable real-time system design using preemption thresholds

Abstract

The maturity of schedulability analysis techniques for fixed-priority preemptive scheduling has enabled the consideration of timing issues at design time using a specification of the tasking architecture and estimates of execution times for tasks. While successful, this approach has limitations since the preemptive multi-tasking model does not scale well for a large number of tasks, and the fixed-priority scheduling theory does not work well with many object-oriented design methods. In this paper, we present an approach that scales well even when the design consists of a large number of concurrent jobs. The approach avoids any unnecessary preemptability in the system, thereby resulting in reduced run-time overheads from preemptions and associated context switches. It also allows significant memory savings by grouping jobs into non-preemptive groups and then sharing the stack space between them. Our approach is based on our earlier work on scheduling using preemption thresholds that allows parametric control over preemptability in a priority-based system. We show that our approach provides significant advantages over one using a fixed-priority preemptive scheduling architecture. The benefits include higher schedulability for small numbers of tasks and lower run-time overheads, and hence better scalability. We develop algorithms that allow design-time consideration of schedulability and automatic synthesis of an implementation model to minimize run-time overheads.