Processes and Operations on Processes

An operating system executes many kinds of programs. On a batch system they are called jobs; on a time-shared system they are user programs or tasks. Many modern process concepts are still expressed in terms of jobs (for example job scheduling), and the two terms are used interchangeably. Whatever you call them, the OS needs one concept to manage them all: the process.

When the executable is loaded, the OS carves the process's memory into four sections. The picture on the slide shows them stacked from low address to high, with the heap growing upward and the stack growing downward into the gap between them.

Why two growing regions? The heap and the stack both have sizes the compiler cannot know in advance. Placing them at opposite ends of the free space and letting them grow toward each other means neither needs a fixed limit; the process only runs out when they meet. That event is a heap-stack collision, and it crashes the program.

As a process executes it changes state. The basic five-state model is new, ready, run, wait, terminate. These slides use a seven-state model that adds two suspended states for processes swapped out to disk when main memory is full. Learn all seven with their transitions.

Each process is represented in the OS by a process control block (PCB), also called a task control block. It is the kernel's record card for the process: when the scheduler switches processes, it saves the running one's CPU state into its PCB and loads the next one's state from its PCB. Without the PCB there is no way to resume a paused process.

The OS must provide mechanisms for process creation and process termination. During execution a process may create several new processes; this is called spawning. The creating process is the parent, the new ones are its children, and each child can create children of its own. The result is a tree of processes. Most operating systems, including UNIX, Linux and Windows, identify each process by a unique process identifier (pid), an integer that is used as an index to access the process's attributes within the kernel.

UNIX implements those choices with three system calls. fork() creates a child that is a duplicate of the parent (address space choice 1). exec() replaces the child's program with a new one (address space choice 2). wait() makes the parent wait for the child (execution choice 2). Not calling wait() is execution choice 1. Your shell does exactly this: it forks, the child execs ls, and the shell waits for ls to finish before printing the next prompt.

fork() creates a child process that runs concurrently with the process that called it (the parent). The child has the same environment as its parent: a copy of the code, data, heap and stack, the same program counter, the same CPU registers, and the same open files. Only the PID is different. After fork(), both processes execute the next instruction following the call.

1pid_t fork(void);

1#include <stdio.h>
2#include <sys/types.h>
3#include <unistd.h>
4int main()
5{
6  fork();
7  printf("Hello world!\n");
8  return 0;
9}

Hello world!
Hello world!

1int main()
2{
3  fork();
4  fork();
5  fork();
6  printf("hello\n");
7  return 0;
8}

hello printed 8 times. 7 child processes created.

fork() alone would only ever let you run copies of the same program. exec() is the other half. When a process calls exec(), the program named in the parameter replaces the entire process. The new program is loaded into the same process space. The PID does not change, and neither does the PPID. But the code, data, stack and heap are all replaced with those of the newly loaded program. No new process is created.

Because the old program is gone, any code after a successful `exec()` never runs. The only way to reach the line after exec() is if it fails (file not found, no permission), in which case it returns -1. In C, exec() is a family of six functions: execl(), execle(), execlp(), execv(), execve(), execvp(). The letters mean: l takes arguments as a list, v takes them as a vector (array), e lets you pass an environment, p searches the PATH.

1/* example.c */
2#include <stdio.h>
3#include <unistd.h>
4#include <stdlib.h>
5int main(int argc, char *argv[])
6{
7    printf("PID of example.c = %d\n", getpid());
8    char *args[] = {"Hello", "World", NULL};
9    execv("./hello", args);
10    printf("Back to example.c");
11    return 0;
12}
13
14/* hello.c */
15#include <stdio.h>
16#include <unistd.h>
17#include <stdlib.h>
18int main()
19{
20    printf("We are in hello.c\n");
21    printf("PID of hello.c is %d", getpid());
22    return 0;
23}

PID of example.c = 4733
We are in hello.c
PID of hello.c is 4733

A process terminates when it finishes its final statement and asks the OS to delete it with the exit() system call. It may return a status value (typically an integer) to its parent, which the parent collects with wait(). The OS then deallocates all the process's resources: physical and virtual memory, open files, and I/O buffers. Because the parent needs to know its children's identities, the PID of each new child is passed to the parent at creation (that positive return value of fork()).

1#include <sys/types.h>
2#include <sys/wait.h>
3
4pid_t wait(int *wstatus);
5/* Returns the PID of the child that terminated.
6   wstatus: where the child's exit status is stored; pass NULL if you do not care. */

1int main() {
2    pid_t p1, p2;
3    int status;
4
5    p1 = fork();
6    if (p1 == 0) {
7        sleep(2);
8        return 1;
9    }
10
11    p2 = fork();
12    if (p2 == 0) {
13        sleep(1);
14        return 2;
15    }
16
17    // Parent
18    pid_t pid = wait(&status);
19    printf("Child with PID %d terminated\n", pid);
20
21    pid = wait(&status);
22    printf("Child with PID %d terminated\n", pid);
23
24    return 0;
25}

Child with PID <p2> terminated      (after about 1 second)
Child with PID <p1> terminated      (after about 2 seconds)

The second child sleeps for 1 second and the first for 2, so the second child terminates first and the first wait() returns p2. wait() does not wait for a particular child; it returns whichever child finishes first. If you need a specific child, use waitpid().

1#include <stdio.h>
2#include <unistd.h>
3#include <stdlib.h>
4#include <sys/wait.h>
5
6int main() {
7    int num = 8;
8    int status;
9
10    if (fork() == 0) {
11        // Child
12        int square = num * num;
13        exit(square);      // Return square
14    }
15    else {
16        // Parent
17        wait(&status);
18
19        if (WIFEXITED(status)) {
20            printf("Square = %d\n", WEXITSTATUS(status));
21        }
22    }
23    return 0;
24}

Square = 64

1#include <stdio.h>
2#include <unistd.h>
3#include <signal.h>
4#include <sys/wait.h>
5
6int main() {
7    pid_t pid = fork();
8
9    if (pid == 0) {
10        // Child process
11        while (1) {
12            printf("Child is running...\n");
13            sleep(1);
14        }
15    } else {
16        // Parent process
17        sleep(5);
18        printf("Parent terminating child...\n");
19        kill(pid, SIGKILL);
20        wait(NULL);
21        printf("Child terminated.\n");
22    }
23    return 0;
24}

Child is running...
Child is running...
Child is running...
Child is running...
Child is running...
Parent terminating child...
Child terminated.

The child loops forever, printing once a second. After five prints the parent wakes from its sleep(5), sends SIGKILL with the child's PID, and then calls wait(NULL) to collect the corpse. That wait() matters: without it, the killed child would linger as a zombie, which is the next section.

One more rule from the slides: in UNIX, if the parent terminates, all its children are assigned `init` as their new parent. The children still have a parent to collect their status and execution statistics. That is UNIX's answer to the cascading termination policy: instead of killing orphans, adopt them.

When a child exits, some process must `wait()` on it to read its exit code. Until that happens the exit code is kept in the process table. Reading it is called reaping the child. Between the moment a child exits and the moment it is reaped, the child is a zombie. A zombie has already released its memory and files. It occupies only a slot in the process table and takes no memory and no CPU. Its only job is to hold that exit status until the parent asks.

1/* Child becomes a zombie because the parent is sleeping
2   when the child exits and has not called wait(). */
3#include <stdlib.h>
4#include <sys/types.h>
5#include <unistd.h>
6int main()
7{
8    // fork returns the child's pid in the parent
9    pid_t child_pid = fork();
10
11    // Parent process
12    if (child_pid > 0)
13        sleep(50);
14
15    // Child process
16    else
17        exit(0);
18
19    return 0;
20}

(no output) For 50 seconds, `ps -el` shows the child with state Z and the label <defunct>.
When the parent exits, init adopts and reaps the zombie.

An orphan is the mirror image. If a process exits while its children are still running, those children are orphans. Orphaned children are immediately adopted by `init` (pid 1). The slides also phrase it as: if the parent terminates without invoking wait(), the process is an orphan. init periodically calls wait(), so an orphan that later exits is reaped promptly and never becomes a long-lived zombie.

1/* Parent finishes execution while the child is running.
2   The child becomes an orphan and is adopted by init. */
3#include <stdio.h>
4#include <sys/types.h>
5#include <unistd.h>
6int main()
7{
8    // Create a child process
9    int pid = fork();
10
11    if (pid > 0)
12        printf("in parent process");
13
14    else if (pid == 0)
15    {
16        sleep(30);
17        printf("in child process");
18    }
19
20    return 0;
21}

in parent process
(the shell prompt returns; 30 seconds later, from the orphan now owned by init:)
in child process