In nearly every computer, the resource that is most often requested is the CPU or processor. Many computers have only one processor, so this processor must be shared via time-multiplexing among all the programs that need to execute on the computer. Here we need to make an important distinction between a program and an executing program. Brookshear [1997] explains:

"One of the most fundamental concepts of modern operating systems is the distinction between a program and the activity of executing a program. The former is merely a static set of directions, the latter is a dynamic activity whose properties change as time progresses. This activity is knows as a process. A process encompasses the current status of the activity, called the process state. This state includes the current position in the program being executed (the value of the program counter) as well as the values in the other CPU registers and the associated memory cells. Roughly speaking, the process state is a snapshot of the machine at that time. At different times during the execution of a program(at different times in a process) different snapshots (different process states) will be observed."

The operating system is responsible for managing all the processes that are running on a computer and allocated each process a certain amount of time to use the processor. In addition, the operating system also allocates various other resources that processes will need such as computer memory or disks. To keep track of the state of all the processes, the operating system maintains a table known as the process table. Inside this table, every process is listed along with the resources the processes is using and the current state of the process. Processes can be in one of three states: running, ready, or waiting. The running state means that the process has all the resources it need for execution and it has been given permission by the operating system to use the processor. Only one process can be in the running state at any given time. The remaining processes are either in a waiting state (i.e., waiting for some external event to occur such as user input or a disk access) or a ready state (i.e., waiting for permission to use the processor). In a real operating system, the waiting and ready states are implemented as queues which hold the processes in these states. The animation below shows a simple representation of the life cycle of a process.


[Linux Logo courtesy Larry Ewing]

The responsibility of determining how to allocate processor time among all the ready processes is known as scheduling. Brookshear [1997] describes one approach to scheduling known as preemptive scheduling: "this task is accomplished by dividing time into short segments, each called a time slice or quantum (typically about 50 milliseconds), and then switching the CPU's attention among the processes as each is allowed to execute for no longer than one time slice." This procedure of swapping processes is called a process switch or a context switch.

Another approach to scheduling is non-preemptive scheduling. In this approach, processes are give control of the processor until they complete execution or voluntarily move themselves to a different state. Employing this type of scheduling poses a potential problem, however, since "processes may not voluntarily cooperate with one another. This problem is especially serious if the running process happens to be executing an infinite loop containing no resource requests. The process will never give up the processor, so all ready processes will wait forever" [Nutt 1997]. For this reason, few systems today use non-preemptive scheduling.

Three strategies for process scheduling are First Come First Serve, Round Robin, and Shortest Process Next. Each of these strategies is described below.

First Come First Serve Scheduling

This non-preemptive scheduling algorithm follows the first-in, first-out (FIFO) policy. As each process becomes ready, it joins the ready queue. When the current running process finishes execution, the oldest process in the ready queue is selected to run next.

Round Robin Scheduling

This scheduling policy gives each process a slice of time (i.e., one quantum) before being preempted. As each process becomes ready, it joins the ready queue. A clock interrupt is generated at periodic intervals. When the interrupt occurs, the currently running process is preempted, and the oldest process in the ready queue is selected to run next. The time interval between each interrupt may vary.

Shortest Process Next

This non-preemptive scheduling algorithm favors processes with the shortest expected execution time. As each process becomes ready, it joins the ready queue. When the current running process finishes execution, the process in the ready queue with the shortest expected execution time is selected to run next.

The applet below [Tran 1998] visually illustrates these three scheduling algorithms. Click the "Launch Simulation" button to open the instruction window and start the simulation applet.

References