Chapter 16. OS: Processes

16.1. Process table

Today's sophisticated operating systems support the concept of a process, an instance of a program running on the computer. Processes don't really exist — you won't find them hiding out inside the computer somewhere — but they are a useful abstraction for the operating system to provide.

The CPU has only one thread of execution — it does only one thing at once. [In fact, modern CPUs can execute instructions simultaneously, as in pipelined, superscalar, and especially multicore chips. However, the instruction set layer provides the illusion that the computer does one instruction at a time, and the CPU works hard to provide the appearance of sequential instruction completion. The operating system, built using the instruction set, is grounded on this behavior.] The OS must provide to each process the illusion that it owns the computer. Thus, the OS will switch processes on and off the CPU. Because the OS wants each process to believe that it has sole control over the CPU, it must ensure that this switching is transparent. For example, each process believes that it has sole control over the CPU's registers. Thus, the OS must record each process's registers when switching it off the CPU, and it must restore the registers when it returns the process to the CPU.

To store information like this, the OS maintains a process table internally. The process table stores what the OS needs to remember for each process. In Unix, each process gets a process ID. This is the index into the process table, which is an array of structures. Each process table entry contains the following information (among other things):

the process's status.
the process's last observed program counter value, so the operating system knows from where it should continue when the program begins running on the CPU next time.
the process's last observed register values, so they can be restored when the process is to run again.
the process's file descriptor table.
a pointer to the next process in line.

16.2. Context switching

During a process's life, it goes through three states: It can be running on the CPU, it can be ready for the CPU, or it can be blocked.

Suppose, for example, that the currently running device requests that the operating system get some data from an I/O device like the disk. In this case, the operating system will move it from the running state to the blocked state, and promote some ready process into the running state instead. This is called a context switch, and it proceeds as follows.

The running process sends a system call via an interrupt.
The CPU jumps into the operating system's interrupt handler.
The interrupt handler saves all the registers of the running process into that process's entry of the process table.
If another process is already waiting for the device to respond, the interrupt handler places the process into a waiting queue for that device. Otherwise, the process's request is sent to the device.
The interrupt handler selects the next process to execute from the queue of those processes in the ready state. This is called the ready queue.
The interrupt handler restores the registers to the values saved in the next process's entry of the process table.
The interrupt handler returns to the program counter value stored in the next process's entry of the process table.

This whole sequence corresponds to the arrow from the Running state to the Blocked state for the requesting process, plus the arrow from the Ready state to the Running state for the selected next process.

Much later, when its response is prepared, the device will send an interrupt. This transfers control to the OS's handler for this interrupt. The handler proceeds as follows.

The interrupt handler saves the device's response in memory for the requesting process to use when it gets the CPU again.
The interrupt handler moves the blocked process into the ready queue.
If there are processes waiting for the device, the interrupt handler sends the next request to the device.
The interrupt handler returns back to the process that was running at the time the interrupt occurred.

This process corresponds to the arrow from the Blocked state to the Ready state.

16.3. Preemption

Operating systems today usually support the concept of preemption, where the operating system will cut off a process after it uses the CPU for a certain amount of time (called its time slice) and put it back into the ready queue. This is represented by the arrow from the Running state to the Ready state in the state diagram.

Accomplishing this isn't completely straightforward. The CPU can run only one thing — if one process is running, then this means that the OS can't and so it can't take any actions, including the action of removing the running process from the CPU. The OS needs some way of regaining control.

To permit this, computer systems incorporate a clock device, a device with which the OS can schedule an interrupt to occur after a certain amount of time. The OS may tell the clock device to send an interrupt to occur every, say, 10 ms; this interrupt will transfer the CPU into the interrupt handler, which is part of the operating system, and the handler can take the currently running process off the ready queue.

It's important to remember that context switching isn't a quick job for the CPU. It takes time to go through the context switching process. Thus, preempting processes actually makes the system complete jobs more slowly.

Operating systems tend to find preemption worthwhile anyway because of the convenience to the user of seeing all processes making progress at all time, and because processes that take a lot of CPU time are generally less urgent: If a process runs for a long time, the user is already obligated to wait, so a few more seconds won't hurt. Spending time to delay such a process is worthwhile if it means running another process requiring less computation, for which the user may well be waiting.

16.4. Process scheduling

When the ready queue contains many processes, and it's time to choose one to start running, the OS is in a dilemma: Which one to select? This selection process is called process scheduling, and researchers have given it much attention.

The simplest process scheduling algorithm is round robin, in which each process is treated equally. When one process runs its time slice out, it is simply placed at the end of the ready queue, and the next process in line begins.

But systems frequently do something more complex. For example, many have some concept of priorities assigned to processes. In some systems, a process with a higher priority is always chosen over a process with a lower priority, but this situation can easily starve out the low-priority jobs. To avoid this, a system might assign longer time slices to higher-priority jobs, but otherwise follow a round-robin strategy. Or a system might choose jobs probabilistically, where higher-priority jobs have a higher priority of being selected.

16.5. Managing processes under Linux

The operating system must provide some support for managing processes. We'll look at the system calls supported by Linux toward this purpose.

One of them we have already seen: the exit system call, which allows a process to request that it be killed.

void exit(int exit_code)

16.5.1. Creating processes

But there should also be some way for a process to start new processes. In Linux, this is accomplished with the fork system call.

int fork()

The fork system call creates a duplicate of the currently running process. It is a complete clone — it has a new process ID, but the process table entry is copied into the table entry of the clone. It has its own memory space, but all the memory of the previous process is copied into the clone's memory also. Thus, the old parent process and the new child process are indistinguishible, except for the process IDs. They both continue from the fork system call. The fork system call returns different numbers to the two processes. It returns 0 to the child process, and it return the child process's process ID to the parent process.

It sounds a bit confusing. Let's look at an example program that illustrates the fork system call.

#include <stdio.h> #include <unistd.h> int main(int argc, char **argv) { int remaining = 4; int child_pid; /* spawn off children */ while(remaining > 0) { child_pid = fork(); if(child_pid == 0) break; remaining--; } printf("hello\n"); return 0; }

What this program does is create four child processes, and the parent process and all four child processes each prints the word hello to the screen. (Creating processes to do this job is a bit contrived. But we need a simple example to examine.)

When this process begins, it sets the remaining variable at 4, and it gets to the fork system call. At this point, there are two identical processes. In the child process, the fork system call returns 0, and so child_pid is 0, and the process breaks out of the loop and prints hello. In the parent process, the fork system call returns a process ID, which is not 0, and so it continues through the loop and executes the fork system call again, spawning another child, and again, spawning another child, and so on.

If you were to run this program, it would print hello five times. All the five processes would be vying to print to the screen virtually simultaneously, however, and so you might see the following under some systems.

hehelllho
leo
lhlelolho

ello

16.5.2. Running programs

Sometimes, we might want a process to run a different program entirely. For this, you can use the execvp system call.

int execvp(char *file, char **args)

The first parameter to execvp is a filename of the executable file that the operating system is to execute. The second parameter should contain a pointer to an array of pointers to the various command-line arguments to be passed into it (via the main function, for example). The last element of the array should be NULL, so that the system can determine how many command-line arguments there are.

When the system executes the execvp system call, it replaces the program run by the current process with the requested program. Thus, execvp, when it is working correctly, does not return. Instead, the process's execution thread is transferred to the beginning of the requested program.

16.5.3. A simple shell

Under Unix systems, the program that reads user commands and starts programs is not really part of the operating system. It is called the shell, and it runs as a regular user program. In fact, there is no reason that you can't write your own and run it. In fact, the below program does that, illustrating how the process management system calls combine together to get a genuinely useful program.

1 #include <unistd.h> 2 #include <sys/wait.h> 3 4 #define CMD_LEN 120 5 6 int main(int argc, char **argv) { 7 char cmd[CMD_LEN]; 8 char *cmd_args[2]; 9 int n; 10 int child_pid; 11 12 while(1) { 13 /* read command from user */ 14 write(1, "% ", 2); 15 n = read(0, cmd, CMD_LEN); 16 if(n == 0) break; /* EOF reached; exit program */ 17 cmd[n - 1] = '\0'; /* replace '\n' with '\0' */ 18 19 /* fork off child to execute command */ 20 child_pid = fork(); 21 if(child_pid == 0) { 22 cmd_args[0] = cmd; 23 cmd_args[1] = NULL; 24 execvp(cmd, cmd_args); 25 /* If execvp returns, the command is bad. */ 26 write(1, "Command not found\n", 19); 27 exit(-1); 28 } 29 30 /* wait for child to exit before continuing */ 31 waitpid(child_pid, &n, 0); 32 } 33 return 0; 34 }

This program uses another system call called waitpid, which a program can use to wait until a process completes its task. The waitpid system call requires three parameters, one to specify which process to wait for; another is an int* saying where to store the process's exit code; and the last parameter is for options (0 is fine here).

int waitpid(int pid, int *status, int options)

This program is an infinite loop. Each iteration begins by reading a command from the user in lines 14 to 17 In line 20, the shell forks off a process. Two processes continue to line 21. For the child process, the fork system call returns 0, and so the child process executes lines 22 to 27, which execute the execvp system call to replace the child process with the program given by the user's command. For the parent process, the fork system call returns the created child's process ID. The parent process executes the waitpid system call in line 31, which will stall the parent until the child completes running, whereupon the parent will continue to the next iteration, which reads and processes the next command from the user.