next up previous contents Back to Operating Systems Home Page
Next: File Management - I Up: CPU scheduling in UNIX Previous: Scheduling in the 4.2BSD

Priority classes in System V R4

UNIX SVR4 introduces the notion of priority classes and supports two types of them, although the design is flexible enough to incorporate new priority classes into the scheme as they become available. The user priority classes officially supported, along with the System-class for system kernel processes only, provide support for time sharing-processes (similarly to all previous releases of UNIX), and for real-time processes. A dynamic process selection scheme is used to determine which process will get the CPU next.

All processes in the SVR4 belong to a particular process priority class. Each class supported by the system has an associated set of class dependent routines to calculate the priority level of a process and determine on which priority queue it is to be placed. These routines decide how a process is scheduled to run. Instead of a single run queue (a.k.a. ready queue), like in older UNIX implementations, there are now multiple priority queues, one for each priority value used by the system. The kernel then makes use of class independent routines to select a process from the highest valued priority queue, as opposed to the lowest used in previous implementations.

In general, a process in the time-shared priority class is subject to a round-robin approach similar to the one of previous implementations: every process is eventually given use of the CPU, although some processes may get it before others, depending on their operating characteristics. However, a real-time process is given a higher precedence and is guaranteed to be selected to run before any time-sharing process. To this aim many preemption points are placed throughout the kernel, which can thus be interrupted. This is a very remarkable difference with respect to the older, time-sharing only, implementation, in which a process might never be preempted while operating in kernel mode.

The kernel maintains a priority dispatch queue for each priority value in the system (all integer values in a pre-defined range) and they are held together in an array of dispatch queues. A scheme of this arrangement is shown in fig. 12. Each element of a queue is a proc structure, i.e. the part of the process control block (the ``user area'', in UNIX parlance, as we saw previously) that contains the scheduling-related information. The queues in the array are sorted by priority value, while the element of each queue are managed in round-robin fashion.

  
Figure 12: Priority queues data structure. Priority class data are represented within each proc structure, and proc structures themselves change queue dynamically.

The scheduling algorithm is then simply to always select the first process of the dispatch queue with highest priority. However, processes in the time-shared priority class have variable priorities computed at runtime (similarly to 4.2BSD), hence ``move'' from queue to queue, while real-time (and system) processes have fixed priorities (unless the user changes them explicitly).

A real-time process can literally take-over the machine: while there's a real-time process on a dispatch queue no other system or time-shared process is scheduled. Thus, a real time process always has a higher priority than a system or time-shared process. Hence it is the programmer's responsibility to configure them so that the kernel is given the time it needs for normal system operation (i.e. paging, swapping, servicing time-shared processes,...)


next up previous contents Back to Operating Systems Home Page
Next: File Management - I Up: CPU scheduling in UNIX Previous: Scheduling in the 4.2BSD

Franco Callari