Process Concept And State - Brooklyn College

CSc33200: Operating Systems, CS-CCNY, Fall 2003Jinzhong Niu September 24, 2003Process Concept and State1IntroductionProcess is one of the fundamental concepts in modern operating systems. It was first introduced by the designers of Multics in the 1960s. Many definitions have been given for thisterm since then, but the most common and simplest one is:A process is an execution of a program.Why do we need this concept and how this definition is obtained? The development of computer system made it introduced naturally. As we mentioned before, multiprogramming isdesigned to improve efficiency by keeping the processor and I/O devices, simultaneouslybusy. Due to the gap between the speed of processors and I/O devices, a program that performs I/O operations has to wait for the completion of the operations. To avoid the idle ofCPU, another program may be loaded into main memory and be given the control of CPU toexecute. Thus at some moment, we may have the main memory layout illustrated by Figure 1:ß¼¼ »--ðïððÓ¿·² Ó»³ §Ð ¹ ¿³ Ý «² » èððð {Ü·- ¿ ½ » ëðððÐ ½»-- ßèðððÐ ½»-- ÞïîðððÐ ½»-- ÝFigure 1: Main memory layout for multiprogrammingThe programs that reside in main memory are absolutely different from their counter-parts,1

the program files on hard disks or tapes. The former are dynamic in the sense that theyare running, while the latter are static. Thus we call processes these entities that have beenloaded into main memory and are able to run or already in execution. If this is not convincingenough, let’s consider an interesting case, suppose Process B and Process C in Figure 1 aredifferent executions of a same program, say nachos. Then obviously, to distinguish the twonachoses, we definitely need a new term, instead of program, so the term process comes.22.1Process stateTraces of processesFor better control of processes, operating systems need to consider their dynamic behaviors.Figure 2 shows the typical behavior of a process.Process0123-I/O ProgramI/O RequstInterrupt HandlerInterrupt SignalFigure 2: The typical dynamic behavior of a processA process consists of a set of instructions, which may include ones related to I/O operations.In Figure 2, suppose at Point 1 is an instruction that requests data from an I/O device. Thuswhen the processor executes to this point, the control is switched to the corresponding I/Oprogram, which first prepares parameters for I/O operation, and finally makes the request.For efficiency, the processor then switches to another process while the I/O operation is goingon. When the operation is finished, an interrupt signal will be generated. The processor thenstops running the active process, and invokes the corresponding interrupt handler. When theinterrupt handler routine is completed, the processor then may resume the execution of theprocess that has been inactive due to waiting for the completion of I/O operation.2

If the processes in Figure 1 are taken as an example, we may trace their behaviors over timeas illustrated in Figure 3. Solid line segments indicate that the corresponding processes s AProcess BProcess BtFigure 3: Traces of processes of Figure 1occupying the processor, and otherwise not. Part of CPU time is also spent to execute I/Oprograms and interrupt handlers, which are generally considered as part of the operatingsystem. Note that time sharing issue is not taken into account here, otherwise each processwill achieve a series of short CPU time periods, instead of a long run as in the figure.There is no magic when the switch of control happens from one process to another. Somefacility in OS is needed to be in charge of this, which is often called dispatcher, dispatching theresource of CPU time to processes, or scheduler, scheduling processes to occupy the processorand run.2.2A two-state process modelBy observing the above figure, we can come up with the simplest possible model of processbehavior. As Figure 4 (a) shows, a process may be in one of the two states: Running or NotRunning.When the operating system creates a new process, it enters that process into the system inthe Not Running state. From time to time, the currently running process will be interrupteddue to either I/O operations or the end of its time slice, and the dispatcher will select anotherprocess to run. The former process moves from the Running state to the Not Running state,while the latter moves to the Running state.To be scheduled by the dispatcher, each process should be represented in some way so that3

Ü·- ¿ ½ Û² » Ò Î«²²·²¹Î«²²·²¹Û · п«-»ø¿ Í ¿ » ¿²-· · ² ¼·¿¹ ¿³Ï«»«»Û² » Ü·- ¿ ½ Ð ½»-- Û · п«-»ø¾ Ï«»«·²¹ ¼·¿¹ ¿³Figure 4: Two-State process modelthe operating system can keep track of it. That is there must be some information relatingto each process, including current state and location in the memory. At any time, there is atmost one running process in an uni-processor system, but probably many processes that arenot running. They must be kept in some sort of data structures, waiting their turn to execute.Figure 4 (b) suggests a queue structure. There is a queue in which each entry is a data blockof some type including a pointer pointing to a particular process. When a process loses theprocessor for some reason, it is transferred to the queue and the dispatcher will then select aprocess from the queue.2.3The creation and termination of processesThrough the two-state process model, we have roughly discussed the trace of processes, butwe haven’t covered the two ends of a process’s life, i.e. the creation and termination of processes.Process creationWhen a new process is to be added, the operating system builds the date structuresthat are used to manage the process and allocates space in main memory to the process.4

There are several events leading to the creation of processes. In a batch environment,a process is created in response to a submission of a job; in an interactive environment,a process is created when a user types a command to execute. Users may also createsa process explicitly in a program by invoking a specific API. For example in Java,Process p Runtime.getRuntime().exec("md temp");And when one process spawns another, the former is referred to as the parent process,and the spawned process is referred to as the child process.Process terminationSimilarly, a process may terminate in all kinds of ways. You may press the crossbutton at the top right corner of a Windows application to close it; You may typeexit in a UNIX shell console to terminate the current session. Inside a program, itmay call exit(0) to terminate normally or exit(1) to indicate an abnormal finish.When a process finishes, the operating system will free the memory space it occupiesand remove the data structures it allocated to manage the process.2.4A five-state modelThe above two-state model, to some extent, reflects the behaviors of processes; however the real situation is much more complex. We cannot simply deal with all theprocesses that are not running in the same way. For example, in a time sharing system, a process may lose control of the processor just because of timeout, i.e. its timeslot is used up. Although it moves to the Not Running state, it is always ready to runright away. But some processes stopped running to wait for the completion of I/Ooperation. Before the interrupt signal notifies the completion, it cannot run and makeany progress, and have to wait. Thus it is not proper to use a single state and a singlequeue for all the not-running processes.Naturally, the Not Running state is to be split into two states: Ready and Blocked. Thusif the creation period and termination period of a process are also considered states,we will obtain a five-state model as depicted in Figure 5.The New state indicates a process has just been created but has not been admitted tothe pool of executable processes by the operating system. Typically, a new process hasnot yet been loaded into main memory. For example, the operating system may limitthe number of processes that may be in the system for reasons of performance or mainmemory limitation. Note that the data structures for managing the new processeshave already been allocated and maintained in main memory.5

Ò» ß¼³· Ü·- ¿ ½ λ¿¼§Î«²²·²¹Î» »¿-»Û · Ì·³» « Ûª»² ѽ½« -Ûª»² É¿· Þ ½µ»¼Figure 5: Five-State process modelThe Exit state indicates a process has been released from the pool of executable processes by the operating system, either because it halted or because it aborted fromsome reason. This state enables some accounting programs to record the processortime and other resources utilized by the process for billing purposes, or utility programs to extract the information about the history of the process for purposes relatedto performance or utilization analysis.Processes in the Blocked state cannot execute until some event occurs, such as thecompletion of I/O operation, while a ready process is always prepared to executewhen given the opportunity.Correspondingly, the queuing diagram in Figure 4 (b) may be extended to reflect thisfive-state model. Figure 6 (a) differentiates the blocked processes and the ones thatmay be dispatched again immediately by giving two paths from the Running stateto the Ready state. An additional queue is set up for blocked processes. It meansthat when an event occurs, the dispatcher will go all the way through the queue forthose processes waiting for that event. In some cases, there may be hundreds or evenmore processes in that queue, therefore it would be more efficient to have a numberof queues, one for each event. Thus Figure 6 (b) is obtained.2.5Process swappingThe five-state model provides a systematic way of modelling the behavior of processes. Many operation systems are indeed constructed using this model.However there are still problems. Recall that the reason for introducing the processconcept and process state transition model is that there is a huge gap between the6

ß¼³· λ¿¼§ Ï«»«»Ü·- ¿ ½ λ »¿-»Ð ½»-- Ì·³» « Þ ½µ»¼ Ï«»«»Ûª»² É¿· Ûª»² ѽ½« -ø¿ Í·²¹ » ¾ ½µ»¼ «»«»ß¼³· λ¿¼§ Ï«»«»Ü·- ¿ ½ λ »¿-»Ð ½»-- Ì·³» « Ûª»² ïѽ½« Ûª»² îѽ½« -Ûª»² ï Ï«»«»Ûª»² ï É¿· Ûª»² î Ï«»«»Ûª»² î É¿· {{{Ûª»² ²Ñ½½« -Ûª»² ² Ï«»«»Ûª»² ² É¿· ø¾ Ó« · » ¾ ½µ»¼ «»«»-Figure 6: Queuing model of Figure 5speed of CPU and I/O devices. When a process has to wait for the completion of I/Ooperation and thus gives up the processor, dispatching control to another processmay avoid the idle of the processor. But this arrangement does not entirely solve theproblem. The processor may be so much faster than I/O that all of the processes inmemory are waiting for I/O. Thus even with multiprogramming, a processor couldbe idle for a long time.Why not expand main memory so that more processes may be accommodated? It ispossible, but cannot be a once-for-all solution since more memory means higher costand with more memory the average size of programs is also likely to increase.A real solution is swapping, which involves moving part or all of a blocked processfrom main memory to disk. Thus memory space may be freed for the system to bringin new processes to run. With swapping, a new state, Suspend, must be added to theprocess behavior model, as depicted in Figure 7 (a).However a single Suspend state is still not enough, since the system needs to distinguish the suspended processes that remain blocked and those that are though sus7