A Time-Driven Scheduling Model for Real-Time Operating Systems.

E. Douglas Jensen, C. Douglass Locke, Hideyuki Tokuda

Real-Time Systems Symposium · 1985 · 424 citations · 3 references

Concepts

TL;DR

Process scheduling in real‑time systems typically relies on fixed priority, FIFO, or round robin algorithms, chosen for their simplicity and speed, yet the effects of these choices on reliability and maintainability have not been systematically assessed. The study seeks to quantify the value of completing processes over time, using this metric to evaluate and ultimately improve real‑time schedulers. To this end, the authors present a time‑driven scheduling model, implement it in a multiprocessor simulator, and apply it to common algorithms—SPT, Deadline, Shortest Slack Time, FIFO, and fixed priority—to measure total system value and guide the design of schedulers that maximize collective value.

Abstract

Process scheduling in real-time systems has almost invariably used one or more of three algorithms: fixed priority, FIFO, or round robin. The reasons for these choices are simplicity and speed in the operating system, but the cost to the system in terms of reliability and maintainability have not generally been assessed. This paper originates from the notion that the primary distinguishing characteristic of a real-time system is the concept that completion of a process or a set of processes has a value to the system which can be expressed as a function of time. This notion is described in terms of a time-driven scheduling model for real-time operating systems and provides a tool for measuring the effectiveness of most of the currently used process schedulers in real-time systems. Applying this model, we have constructed a multiprocessor real-time system simulator with which we measure a number of well-known scheduling algorithms such as Shortest Process Time (SPT), Deadline, Shortest Slack Time, FIFO, and a fixed priority scheduler, with respect to the resulting total system values. This approach to measuring the process scheduling effectiveness is a first step in our longer term effort to produce a scheduler which will explicitly schedule real-time processes in such a way that their execution times maximize their collective value to the system, either in a shared memory multiprocessing environment or in multiple nodes of a distributed processing environment.

References

3