next up previous contents Back to Operating Systems Home Page
Next: Priority classes in System Up: CPU scheduling in UNIX Previous: CPU scheduling in UNIX

Scheduling in the 4.2BSD Unix OS

Short term scheduling in UNIXgif is designed to benefit interactive jobs. Processes are given small CPU time slices by an algorithm that reduces to round robin for CPU-bound jobs, although there is a priority scheme. There's no preemption of one process by another when running in kernel mode. A process may relinquish the CPU because it's waiting for I/O (including I/O due to page faults) or because its time slice has expired.

Every process has a scheduling priority associated with it; the lower the numerical priority, the more likely is the process to rungif. System processes doing disk I/O and other important tasks have negative priorities and cannot be interrupted. Ordinary user processes have positive priorities and thus are less likely to be run than any system process, although user processes may have precedence over one another. the nice command may be used to affect this precedence according to its numerical priority argument.

The more CPU time a process accumulates, the lower (more positive) its priority becomes. The reverse is also true (process aging is employed to prevent starvation). Thus there is negative feedback in CPU scheduling, and its difficult for a single process to take CPU all time.

Old UNIX systems used a 1 sec. quantum for the round-robin scheduling algorithm. Later 4.2BSD did rescheduling every 0.1 seconds, and priority re-computation every second. The round-robin scheduling is accomplished by the timeout mechanism, which tells the clock interrupt driver to call a certain system routine after a specified interval. The subroutine to be called in this case causes the rescheduling and then resubmits a timeout to call itself again 0.1 sec later. The priority re-computation is also timed by a subroutine that resubmits a timeout for itself.

When a process chooses to relinquish the CPU (voluntarily, in a user program, or because this decision is to be made in the kernel context for a process executing that program) it sleep on an even. The system call used for this is called sleep (not to be confused with the C library routine with the same name, sleep(3)). It takes an argument that is by convention the address of a kernel data structure related to an event the process wants to occur before it is awakened. When the event occurs, the system process that knows about it calls wakeup with the address corresponding to the event, and all processes that had done a sleep on the same address are put in the ready queue.

For example, a process waiting for disk I/O to complete will sleep on the address of the buffer corresponding to the data being transferred. When the interrupt routine for the disk driver notes that the transfer is complete, it calls wakeup on that buffer, causing all processes waiting for that buffer to be awakened. Which process among those actually does run is chosen by the scheduler effectively at random. Sleep, however, also takes a second argument, which is the scheduling priority to be used for this purpose.


next up previous contents Back to Operating Systems Home Page
Next: Priority classes in System Up: CPU scheduling in UNIX Previous: CPU scheduling in UNIX

Franco Callari