Process States

Process States

Although each process is an independent entity, with its own program counter and internal state, processes sometimes have to interact with other processes. One process may produce some output that another process uses as input. In the shell command

cat chapter1 chapter2 chapter3 I grep tree

the first process, running cat, concatenates and outputs three files. The second process, running grep, selects all lines containing the word "tree".  Depending on the relative speeds of the two processes (which depends on both the relative complexity of the programs and how much CPU time  each one has had), it may happen that grep is ready to run, but there is no input waiting for it. It must then block until some input is available.

When a process blocks, it does so because logically it cannot continue, usually because it is waiting for input that is not yet available. It is also possible for a process that is conceptually ready and able to run to be stopped because the operating system has decided to assign the CPU to another process for a while. These two conditions are totally different. In the first case, the suspension is inherent in the problem (you cannot process the user's command line until it has been typed). In the second case, it is a technicality of the system (not enough CPUs to give each process its own private processor). In the following figure we see a state diagram showing the three states a process may be in:

1. Running (actually using the CPU at that instant).
2. Ready (runnable; temporarily stopped to let another process run).
3. Blocked (unable to run until some external event happens).

Logically, the first two states are alike. In both cases the process is willing to run, only in the second one, there is temporarily no CPU available for it. The third state is different from the first two in that the process cannot run, even if the CPU has nothing else to do.

A process can be in running, blocked

Four transitions are possible among these three states, as shown. Transition 1 takes place when the operating system discovers that a process cannot continue right now. In some systems the process can carry out a system call, such as pause, to get into blocked state. In other systems, including UNIX, when a process reads from a pipe or special file (e.g., a terminal) and there is no input available, the process is automatically blocked.

Transitions 2 and 3 are caused by the process scheduler, a part of the operating system, without the process even knowing about them.  Transition 2 takes place when the scheduler decides that the running process has run long enough, and it is time to let another process have some CPU time. Transition 3 takes place when all the other processes have had their fair share and it is time for the first process to get the CPU to run again. The subject of scheduling, that is, deciding which process should run when and for how long, is an important one; we will look at it later in this section. Many algorithms have been planned to try to balance the competing demands of efficiency for the system as a whole and fairness to individual processes. We will study some of them later in this section.

Transition 4 takes place when the external event for which a process was waiting (such as the arrival of some input) happens. If no other process is running at that moment, transition 3 will be triggered and the process will start running. Otherwise it may have to wait in ready state for a little while until the CPU is available and its turn comes.

Using the process model, it becomes much easier to think about what is going on inside the system. Some of the processes run programs that execute commands typed in by a user. Other processes are part of the system and manage tasks such as carrying out requests for file services or managing the details of running a disk or a tape drive. When a disk interrupt occurs, the system makes a decision to stop running the current process and run the disk process, which was blocked waiting for that interrupt. Therefore, instead of thinking about interrupts, we can think about user processes, disk processes, terminal processes, and so on, which block when they are waiting for something to take place. When the disk has been read or the character typed, the process waiting for it is unblocked and is eligible to run again.

This view gives rise to the model shown in "Implementation of Processes" Figure (a). Here the lowest level of the operating system is the scheduler, with a variety of processes on top of it. All the interrupt handling and details of actually starting and stopping processes are hidden away in what is here called the scheduler, which is actually not much code. The rest of the operating system is nicely structured in process form. Few real systems are as nicely structured as this, however.



Tags

process, operating system, unix