Scheduling in Real-Time Systems

Scheduling in Real-Time Systems

A real-time system is one in which time plays an important role. Normally, one or more physical devices external to the computer produce stimuli, and the computer must react properly to them within a fixed amount of time. For instance, the computer in a compact disc player gets the bits as they come off the drive and must convert them into music within a very tight time interval. If the calculation takes too long, the music will sound odd. Other real-time systems are patient monitoring in a hospital intensive-care unit, the autopilot in an aircraft, and robot control in an automated factory. In all these cases, having the right answer but having it too late is sometimes just as bad as  not having it at all.

Real-time systems are usually categorized as hard real time, meaning there are absolute deadlines that must be met, or else, and soft real time, meaning that missing an occasional deadline is unwanted, but however tolerable. In both cases, real-time behavior is attained by dividing the program into a number of processes, each of whose behavior is predictable and known in advance. These processes are usually short lived and can run to completion in well under a second. When an external event is detected, it is the job of the scheduler to schedule the processes in such a way that all deadlines are met.

The events that a real-time system may have to respond to can be further categorized as periodic (occurring at regular intervals) or aperiodic (occurring unpredictably). A system may have to respond to multiple periodic event streams. Depending on how much time each event requires for processing, it may not even be possible to handle them all. For instance, if there are m periodic events and event i occurs with period Pi and requires Ci seconds of CPU time to handle each event, then the load can only be handled if

A real-time system that meets this criterion is said to be schedulable.

As an example, consider a soft real-time system with three periodic events, with periods of 100, 200, and 500 msec, respectively. If these events require 50, 30, and 100 msec of CPU time per event, respectively, the system is schedulable because 0.5 + 0.15 + 0.2 < 1. If a  fourth event with a period of 1 sec is added, the system will remain schedulable as long as this event does not need more than 150 msec of CPU time per event. Implicit in this calculation is the assumption that the context-switching overhead is so small that it can be ignored.

Real-time scheduling algorithms can be static or dynamic. The former make their scheduling decisions before the system starts running. The latter make their scheduling decisions at run time. Static scheduling only works when there is perfect information available in advance about the work to be done and the deadlines that have to be met. Dynamic scheduling algorithms do not have these restrictions. We will postpone our study of particular algorithms until we treat real-time multimedia systems in "MULTIMEDIA OPERATING SYSTEMS".

Policy versus Mechanism

So far, we have tacitly assumed that all the processes in the system belong to different users and are therefore competing for the CPU. While this is sometimes true, sometimes it happens that one process has many children running under its control. For instance, a database management system process may have many children. Each child might be working on a different request, or each one might have some particular function to perform (query parsing, disk access, etc.). It is completely possible that the main process has an excellent idea of which of its children are the most important (or time critical) and which the least. Unluckily, none of the schedulers discussed above accept any input from user processes about scheduling decisions. As a result, the scheduler rarely makes the best choice.

The solution to this problem is to separate the scheduling mechanism from the scheduling policy, a long-established principle (Levin et al., 1975). What this means is that the scheduling algorithm is parameterized in some way, but the parameters can be filled in by user processes. Let us look at the database example once again. Assume that the kernel uses a priority-scheduling algorithm but provides a system call by which a process can set (and change) the priorities of its children. Thus the parent can control in detail how its children are scheduled, even though it itself does not do the scheduling. Here the mechanism is in the kernel but policy is set by a user process.


scheduling mechanism, scheduling policy, scheduling algorithm