Process Concepts:Process Management

Process Management

As the operating system interleaves the execution of its processes, it must carefully manage them to ensure that no errors occur as the processes are interrupted and resumed. Processes should be able to communicate with the operating system to perform simple tasks such as starting a new process or signaling the end of process execution. In this section, we discuss how operating systems provide certain fundamental services to processes—these include creating processes, destroying processes, suspending processes, resuming processes, changing a process’s priority, blocking processes, waking up processes, dispatching processes, enabling processes to interact via interprocess communication (IPC) and more. We also discuss how operating systems manage process resources to allow multiple processes to actively contend for processor time at once.

Process States and State Transitions

When a user runs a program, processes are created and inserted into the ready list. A process moves toward the head of the list as other processes complete their turns using a processor. When a process reaches the head of the list, and when a processor becomes available, that process is given a processor and is said to make a state transition from the ready state to the running state (Fig. 3.1). The act of assigning a processor to the first process on the ready list is called dispatching and is performed by a system entity called the dispatcher. Processes that are in the ready or running states are said to be awake, because they are actively contending for processor time. The operating system manages state transitions to best serve processes in the system. To prevent any one process from monopolizing the system, either accidentally or maliciously, the operating system sets a hardware interrupting clock (also called an inter- val timer) to allow a process to run for a specific time interval or quantum. If the process does not voluntarily yield the processor before the time interval expires, the interrupting clock generates an interrupt, causing the operating system to gain control of the processor (see Section 3.4, Interrupts). The operating system then changes the state of the previously running process to ready and dispatches the first process on the ready list, changing its state from ready to running. If a running process initiates an input/output operation before its quantum expires, and therefore must wait for the I/O operation to complete before it can use a processor again, the running process voluntarily relinquishes the processor. In this case, the process

is said to block itself, pending the completion of the I/O operation. Processes in the blocked state are said to be asleep, because they cannot execute even if a processor becomes available. The only other allowable state transition in our three-state model occurs when an I/O operation (or some other event the process is waiting for) completes. In this case, the operating system transitions the process from the blocked to the ready state.

We have defined four possible state transitions. When a process is dispatched, it transitions from ready to running. When a process’s quantum expires, it transitions from running to ready. When a process blocks, it transitions from running to blocked. Finally, when a process wakes up because of the completion of some event it is awaiting, it transitions from blocked to ready. Note that the only state transition initiated by the user process itself is block—the other three transitions are initiated by the operating system.

In this section, we have assumed that the operating system assigns each process a quantum. Some early operating systems that ran on processors without interrupting clocks employed cooperative multitasking, meaning that each process must voluntarily yield the processor on which it is running before another process can execute. Cooperative multitasking is rarely used in today’s systems, however, because it allows processes to accidentally or maliciously monopolize a processor (e.g., by entering an infinite loop or simply refusing to yield the processor in a timely fashion).

Self Review

1. How does the operating system prevent a process from monopolizing a processor?

2. What is the difference between processes that are awake and those that are asleep?

Ans: 1) An interrupting clock generates an interrupt after a specified time quantum, and the operating system dispatches another process to execute. The interrupted process will run again when it gets to the head of the ready list and a processor again becomes available. 2) A process that is awake is in active contention for a processor; a process that is asleep cannot use a processor even if one becomes available.

Process Control Blocks (PCBs)/Process Descriptors

The operating system typically performs several operations when it creates a process. First, it must be able to identify each process; therefore, it assigns a process identification number (PID) to the process. Next, the operating system creates a process control block (PCB), also called a process descriptor, which maintains information that the operating system needs to manage the process. PCBs typically include information such as:

• PID

• process state (e.g., running, ready or blocked)

• program counter (i.e., a value that determines which instruction the processor should execute next)

• scheduling priority

• credentials (i.e., data that determines the resources this process can access)

• a pointer to the process’s parent process (i.e., the process that created this process)

• pointers to the process’s child processes (i.e., processes created by this process) if any

• pointers to locate the process’s data and instructions in memory

• pointers to allocated resources (such as files).

The PCB also stores the register contents, called the execution context, of the processor on which the process was last running when it transitioned out of the running state. The execution context of a process is architecture specific but typically includes the contents of general-purpose registers (which contain process data that the processor can directly access) in addition to process management registers, such as registers that store pointers to a process’s address space. This enables the operating system to restore a process’s execution context when the process returns to the running state.

When a process transitions from one state to another, the operating system must update information in the process’s PCB. The operating system typically maintains pointers to each process’s PCB in a systemwide or per-user process table so that it can access the PCB quickly (Fig. 3.2). The process table is one of many oper- ating system data structures we discuss in this text (see the Operating Systems Thinking feature, Data Structures in Operating Systems). When a process is termi-

nated (either voluntarily or by the operating system), the operating system frees the process’s memory and other resources, removes the process from the process table and makes its memory and other resources available to other processes. We discuss other process manipulation functions momentarily.19

Self Review

1. What is the purpose of the process table?

2. (T/F) The structure of a PCB is dependent on the operating system implementation.

Ans: 1) The process table enables the operating system to locate each process’s PCB. 2) True.

Process Operations

Operating systems must be able to perform certain process operations, including:

• create a process

• destroy a process

• suspend a process

• resume a process

• change a process’s priority

• block a process

• wake up a process

• dispatch a process

• enable a process to communicate with another process (this is called inter- process communication).

Operating Systems Thinking

Data Structures in Operating Systems

Computer science students generally study data structures, both those on the main topic of a full course and as portions of many upper-level courses, such as compilers, databases, networking and operating systems. Data structures are used abundantly in operating systems. Queues are used wherever entities need to wait—processes waiting for a processor, I/O requests waiting for devices to become available, processes wait- ing for access to their critical sections and so on. Stacks are used for supporting the function call return mechanism. Trees are used to represent file system directory structures, to keep track of the allocation of disk space to files, to build hierarchical page directory structures in support of virtual address translation, and so on. Graphs are used when studying networking arrangements, dead- lock resource allocation graphs, and the like. Hash tables are used to access PCBs quickly (using a PID as the key).

A process may spawn a new process. If it does, the creating process is called the parent process and the created process is called the child process. Each child process is created by exactly one parent process. Such creation yields a hierarchical process structure similar to Fig. 3.3, in which each child has only one parent (e.g., A is the one parent of C; H is the one parent of I), but each parent may have many children (e.g., B, C, and D are the children of A; F and G are the children of C).In UNIX-based systems, such as Linux, many processes are spawned from the init process, which is created when the kernel loads (Fig. 3.4). In Linux, such processes include kswapd, xfs and khubd—these processes perform memory, file system and device management operations, respectively. Many of these processes are discussed further in Chapter 20, Case Study: Linux. The login process authenticates users to the operating system. This is typically accomplished by requiring a user to enter a valid username and corresponding password. We discuss other means of authentica- tion in Chapter 19, Security. Once the login process authenticates the user, it spawns a shell, such as bash (Bourne-again shell), that allows the user to interact with the operating system (Fig. 3.4). The user may then issue commands to the shell to execute programs such as vi (a text editor) and finger (a utility that displays user information). Destroying a process involves obliterating it from the system. Its memory and other resources are returned to the system, it is purged from any sys- tem lists or tables and its process control block is erased, i.e., the PCB’s memory space is made available to other processes in the system. Destruction of a process is more complicated when the process has spawned other processes. In some operating systems, each spawned process is destroyed automatically when its parent is destroyed; in others, spawned processes proceed independently of their parents, and the destruction of a parent has no effect on its children.

Changing the priority of a process normally involves modifying the priority value in the process’s control block. Depending on how the operating system implements process scheduling, it may need to place a pointer to the PCB in a different priority queue (see Chapter 8, Processor Scheduling). The other operations listed in this section are explained in subsequent sections.

Self Review

1. (T/F) A process may have zero parent processes.

2. Why is it advantageous to create a hierarchy of processes as opposed to a linked list?

Ans: 1) True. The first process that is created, often called init in UNIX systems, does not have a parent. Also, in some systems, when a parent process is destroyed, its children proceed independently without their parent. 2) A hierarchy of processes allows the operating system to track parent/child relationships between processes. This simplifies operations such as locating all the child processes of a particular parent process when that parent terminates.

Suspend and Resume

Many operating systems allow administrators, users or processes to suspend a process. A suspended process is indefinitely removed from contention for time on a processor without being destroyed. Historically, this operation allowed a system operator to manually adjust the system load and/or respond to threats of system failure. Most of today’s computers execute too quickly to permit such manual adjustments. However, an administrator or a user suspicious of the partial results of a process may suspend it (rather than aborting it) until the user can ascertain whether the process is functioning correctly. This is useful for detecting security threats (such as malicious code execution) and for software debugging purposes.

Figure 3.5 displays the process state-transition diagram of Fig. 3.1 modified to include suspend and resume transitions. Two new states have been added, suspendedready and suspendedblocked. Above the dashed line in the figure are the active states; below it are the suspended states.

A suspension may be initiated by the process being suspended or by another process. On a uniprocessor system a running process may suspend itself, indicated by Fig. 3.5(a); no other process could be running at the same moment to issue the suspend. A running process may also suspend a ready process or a blocked process, depicted in Fig. 3.5(b) and (c). On a multiprocessor system, a running process may be suspended by another process running at that moment on a different processor.

Clearly,a process suspends itself only when it is in the running state. In such a situation, the process makes the transition from running to suspendedready. When a process suspends a ready process, the ready process transitions from ready to suspendedready.A suspendedready process may be made ready, or resumed, by another process, causing the first process to transition from suspendedready to ready.A blocked process will make the transition from blocked to suspendedblocked when it is suspended by another process.A suspendedblocked process may be resumed by another process and make the transition from suspendedblocked to blocked.

One could argue that instead of suspending a blocked process, it is better to wait until the I/O completion or event completion occurs and the process becomes ready; then the process could be suspended to the suspendedready state. Unfortunately, the completion may never come, or it may be delayed indefinitely. The designer must choose between performing the suspension of the blocked process or creating a mechanism by which the suspension will be made from the ready state when the I/O or event completes. Because suspension is typically a high-priority activity, it is performed immediately. When the I/O or event completion finally occurs (if indeed it does), the suspendedblocked process makes the transition from suspendedblocked to suspendedready.

Self Review

1. In what three ways can a process get to the suspendedready state?

2. In what scenario is it best to suspend a process rather than abort it?

Ans: 1) A process can get to the suspendedready state if it is suspended from the running state, if it is suspended from the ready state by a running process or if it is in the suspended- blocked state and the I/O completion or event completion it is waiting for occurs. 2) When a user or system administrator is suspicious of a process’s behavior but does not want to lose the work performed by the process, it is better to suspend the process so that it can be inspected.

Context Switching

The operating system performs a context switch to stop executing a running process and begin executing a previously ready process.20 To perform a context switch, the kernel must first save the execution context of the running process to its PCB, then load the ready process’s previous execution context from its PCB (Fig. 3.6).

Context switches, which are essential in a multiprogrammed environment, introduce several operating system design challenges. For one, context switches must be essentially transparent to processes, meaning that the processes are unaware they have been removed from the processor. During a context switch a processor cannot perform any “useful” computation—i.e., it performs tasks that are essential to operating systems but does not execute instructions on behalf of any given process. Context switching is pure overhead and occurs so frequently that operating systems must minimize context-switching time.

The operating system accesses PCBs often. As a result, many processors con- tain a hardware register that points to the PCB of the currently executing process to facilitate context switching. When the operating system initiates a context switch, the processor safely stores the currently executing process’s execution context in the PCB. This prevents the operating system (or other processes) from overwriting the process’s register values. Processors further simplify and speed context switch- ing by providing instructions that save and restore a process’s execution context to and from its PCB, respectively.

In the IA-32 architecture, the operating system dispatches a new process by specifying the location of its PCB in memory. The processor then performs a con- text switch by saving the execution context of the previously running process. The IA-32 architecture does not provide instructions to save and restore a process’s execution context, because the processor performs these operations without software intervention.21

Self Review

1. From where does an operating system load the execution context for the process to be dis- patched during a context switch?

2. Why should an operating system minimize the time required to perform a context switch?

Ans: 1) The process to be dispatched has its context information stored in its PCB. 2) During a context switch, a processor cannot perform instructions on behalf of processes, which can reduce throughput.