Multiprogramming enables the OS to make efficient use of hardware resources. For example, when a process running on the CPU needs to access data that are currently on disk, rather than have the CPU sit idle waiting for the data to be read into memory, the OS can give the CPU to another process and let it run while the read operation for the original process is being handled by the disk. By using multiprogramming, the OS can mitigate some of the effects of the memory hierarchy on its program workload by keeping the CPU busy executing some processes while other processes are waiting to access data in the lower levels of the memory hierarchy.

General-purpose operating systems often implement timesharing, which is multiprogramming wherein the OS schedules each process to take turns executing on the CPU for short time durations (known as a time slice or quantum). When a process completes its time slice on the CPU, the OS removes the process from the CPU and lets another run. Most systems define time slices to be a few milliseconds (10^-3 seconds), which is a long time in terms of CPU cycles but is not noticeable to a human.

Timesharing systems further support the "lone view" of the computer system to the user; because each process frequently executes on the CPU for short bursts of time, the fact that they are all sharing the CPU is usually imperceptible to the user. Only when the system is very heavily loaded might a user notice the effects of other processes in the system. The Unix command ps -A lists all the processes running in the system — you may be surprised by how many there are. The top command is also useful for seeing the state of the system as it runs by displaying the set of processes that currently use the most system resources (such as CPU time and memory space).

In multiprogrammed and timeshared systems, processes run concurrently, meaning that their executions overlap in time. For example, the OS may start running process A on the CPU, and then switch to running process B for a while, and later switch back to running process A some more. In this scenario, processes A and B run concurrently because their execution on the CPU overlaps due to the OS switching between the two.

In multiprogrammed systems, the OS must track and manage the multiple processes existing in the system at any given time. The OS maintains information about each process, including:

Over the course of its lifetime, a process moves through several states, which correspond to different categories of process execution eligibility. One way that the OS uses process state is to identify the set of processes that are candidates for being scheduled on the CPU.

The set of process execution states are:

Figure 1 shows the lifetime of a process in the system, illustrating how it moves between different states. Note the transitions (arrows) from one state to another. For example, a process can enter the Ready state in one of three ways: first, if it is newly created by the OS; second, if it was blocked waiting for some event and the event occurs; and third, if it was running on the CPU and its time slice is over and the OS context switches it off to give another Ready process its turn on the CPU.

An OS creates a new process when an existing process makes a system call requesting it to do so. In Unix, the fork system call creates a new process. The process calling fork is the parent process and the new process it creates is its child process. For example, if you run a.out in a shell, the shell process calls the fork system call to request that the OS create a new child process that will be used to run the a.out program. Another example is a web browser process that calls fork to create child processes to handle different browsing events. A web browser may create a child process to handle communication with a web server when a user loads a web page. It may create another process to handle user mouse input, and other processes to handle separate browser windows or tabs. A multiple-process web browser like this is able to continue handling user requests through some of its child browser processes, while at the same time some of its other child browser processes may be blocked waiting for remote web server responses or for user mouse clicks.

A process hierarchy of parent-child relationships exists between the set of processes active in the system. For example, if process A makes two calls to fork, two new child processes are created, B and C_. If process C then calls fork, another new process, D, will be created. Process C is the child of A, and the parent of D. Processes B and C are siblings (they share a common parent process, process A). Process A is the ancestor of B, C, and D. This example is illustrated in Figure 2.

Since existing processes trigger process creation, a system needs at least one process to create any new processes. At boot time, the OS creates the first user-level process in the system. This special process, named init, sits at the very top of the process hierarchy as the ancestor of all other processes in the system.

Usually a new process is created to execute a program that is different from that of its parent process. This means that fork is often called to create a process with the intention of running a new program from its starting point (that is starting its execution from its first instruction). For example, if a user types ./a.out in a shell, the shell process forks a new child process to run a.out. As two separate processes, the shell and the a.out process are protected from each other; they cannot interfere with each other’s execution state.

While fork creates the new child process, it does not cause the child to run a.out. To initialize the child process to run a new program, the child process calls one of the exec system calls. Unix provides a family of exec system calls that trigger the OS to overlay the calling process’s image with a new image from a binary executable file. In other words, an exec system call tells the OS to overwrite the calling process’s address space contents with the specified a.out and to reinitialize its execution state to start executing the very first instruction in the a.out program.

One example of an exec system call is execvp, whose function prototype is as follows:

The filename parameter specifies the name of a binary executable program to initialize the process’s image, and argv contains the command line arguments to pass into the main function of the program when it starts executing.

Here’s an example code snippet that, when executed, creates a new child process to run a.out:

The argv variable is initialized to the value of the argv argument that is passed to the main function of a.out:

execvp will figure out the value to pass to argc based on this argv value (in this case 1).

Figure 5 shows what the process hierarchy would look like after executing this code:

Something to note in the example code shown above is its seemingly odd error message after the call to execvp: why would returning from an exec system call be an error? If the exec system call is successful, then the error detection and handling code immediately following it will never be executed because the process will now be executing code in the a.out program instead of this code (the process’s address space contents have been changed by exec). That is, when a call to an exec function is successful, the process doesn’t continue its execution at the return of the exec call. Because of this behavior, the following code snippet is equivalent to the one shown above (however, the one above is typically easier to understand):

To terminate, a process calls the exit system call, which triggers the OS to clean up most of the process’s state. After running the exit code, a process notifies its parent process that it has exited. The parent is responsible for cleaning up the exited child’s remaining state from the system.

Processes can be triggered to exit in several ways. First, a process may complete all of its application code. Returning from its main function leads to a process invoking the exit system call. Second, a process can perform an invalid action, such as dividing by zero or dereferencing a null pointer, that results in its exiting. Finally, a process can receive a signal from the OS or another process, telling it to exit (in fact, dividing by zero and NULL pointer dereferences result in the OS sending the process SIGFPE and SIGSEGV signals telling it to exit).

If a shell process wants to terminate its child process running a.out, it can send the child a SIGKILL signal. When the child process receives the signal, it runs signal handler code for SIGKILL that calls exit, terminating the child process. If a user types CTRL-C in a Unix shell that is currently running a program, the child process receives a SIGINT signal. The default signal handler for SIGINT also calls exit, resulting in the child process exiting.

After executing the exit system call, the OS delivers a SIGCHLD signal to the process’s parent process to notify it that its child has exited. The child becomes a zombie process; it moves to the Exited state and can no longer run on the CPU. The execution state of a zombie process is partially cleaned up, but the OS still maintains a little information about it, including about how it terminated.

A parent process reaps its zombie child (cleans up the rest of its state from the system) by calling the wait system call. If the parent process calls wait before its child process exits, the parent process blocks until it receives a SIGCHLD signal from the child. The waitpid system call is a version of wait that takes a PID argument, allowing a parent to block while waiting for the termination of a specific child process.

Figure 6 shows the sequence of events that occur when a process exits.

Because the parent and child processes execute concurrently, the parent may call wait before its child exits, or the child can exit before the parent calls wait. If the child is still executing when the parent process calls wait, the parent blocks until the child exits (the parent enters the Blocked state waiting for the SIGCHLD signal event to happen). The blocking behavior of the parent can be seen if you run a program (a.out) in the foreground of a shell — the shell program doesn’t print out a shell prompt until a.out terminates, indicating that the shell parent process is blocked on a call to wait, waiting until it receives a SIGCHLD from its child process running a.out.

A programmer can also design the parent process code so that it will never block waiting for a child process to exit. If the parent implements a SIGCHLD signal handler that contains the call to wait, then the parent only calls wait when there is an exited child process to reap, and thus it doesn’t block on a wait call. This behavior can be seen by running a program in the background in a shell (a.out &). The shell program will continue executing, print out a prompt, and execute another command as its child runs a.out. Here’s an example of how you might see the difference between a parent blocking on wait vs. a nonblocking parent that only calls wait inside a SIGCHLD signal handler (make sure you execute a program that runs for long enough to notice the difference):

Below is an example code snippet containing fork, exec, exit, and wait system calls (with error handling removed for readability). This example is designed to test your understanding of these system calls and their effects on the execution of the processes. In this example, the parent process creates a child process and waits for it to exit. The child then forks another child to run the a.out program (the first child is the parent of the second child). It then waits for its child to exit.

Figure 7 illustrates the execution time line of process create/running/blocked/exit events from executing the above example. The dotted lines represent times when a process’s execution overlaps with its child or descendants: the processes are concurrent and can be scheduled on the CPU in any order. Solid lines represent dependencies on the execution of the processes. For example, Child 1 cannot call exit until it has reaped its exited child process, Child 2. When a process calls wait, it blocks until its child exits. When a process calls exit, it never runs again. The program’s output is annotated along each process’s execution time line at points in its execution when the corresponding printf statement can occur.

After the calls to fork are made in this program, the parent process and first child process run concurrently, thus the call to wait in the parent could be interleaved with any instruction of its child. For example, the parent process could call wait and block before its child process calls fork to create its child process. Table 2 lists all possible outputs from running the example program.

The program outputs in Table 2 are all possible because the parent runs concurrently with its descendant processes until it calls wait. Thus, the parent’s call to printf("E\n") can be interleaved at any point between the start and the exit of its descendant processes.