5.5 Time-Shared and Real-Time Scheduling Classes

I l @ ve RuBoard

In addition to the contention scopes and threading models described in Section 5.4, OS platforms often define policies and priority levels that further influence scheduling behavior [But97]. These capabilities enable modern operating systems to run a mix of applications with a range of general-purpose and real-time scheduling needs. OS kernels can assign threads to different scheduling classes and schedule these threads using several criteria, such as their priority and their resource usage. The different scheduling class strategies described below trade off fairness for increased predictability and control.

Time-shared scheduling class. General-purpose OS schedulers target traditional time-sharing, interactive environments. Schedulers for these operating systems are typically

Priority-based ” the highest-priority runnable thread is the next one scheduled for execution.
Fair ” the priority of threads in a time-shared scheduler can be varied as a function of their CPU usage. For example, as a long-running compute-bound thread uses more CPU time, a time-shared scheduler can decrease its priority progressively until a lower limit is reached.
Preemptive ” if a lower-priority thread is executing when a higher-priority thread becomes runnable, the scheduler should preempt the lower-priority thread and allow the higher-priority thread to run.
Time-sliced, which is used to cycle among threads with the same priority. With this technique, each thread runs for up to a finite period of time (e.g., 10 milliseconds ). After the time slice of the currently running thread has elapsed, the scheduler selects another available thread, performs a context switch, and places the preempted thread onto a queue.

Real-time scheduling class. Although time-shared schedulers are suitable for conventional networked applications, they rarely satisfy the needs of applications with real-time requirements. For example, there's usually no fixed order of execution for threads in a time-shared scheduler class since the scheduler can vary thread priorities over time. Moreover, time-shared schedulers don't try to bound the amount of time needed to preempt a lower-priority thread when a higher-priority thread becomes ready to run.

Therefore, real-time operating systems (such as VxWorks or LynxOS) and some general-purpose operating systems (such as Solaris and Windows NT) provide a real-time scheduling class [Kha92] that bounds the worst-case time required to dispatch user threads or kernel threads. An OS with a real-time scheduling class often supports one or both of the following scheduling policies [Gal95]:

Round- robin , where a time quantum specifies the maximum time a thread can run before it's preempted by another real-time thread with the same priority.
First-in, first-out (FIFO), where the highest-priority thread can run for as long as it chooses, until it voluntarily yields control or is preempted by a real-time thread with an even higher priority.

When an OS supports both time-shared and real-time scheduling classes, the real-time threads always run at a higher priority than any time-shared threads.

A CPU-bound real-time program can take over the system and starve all other system activities. Most general-purpose operating systems therefore regulate this undesirable situation by restricting the use of the real-time scheduling class to applications running with superuser privileges.

Logging service Since a logging service isn't usually time critical, most of our examples in this book simply use the default OS time-shared scheduling class. For completeness, however, the networked logging server example on page 200 in Section 9.3 shows how to use ACE to write a portable logging server that runs in the real-time scheduling class.

I l @ ve RuBoard