Process states, fork and exec

Why it exists

A process is not always doing the same thing: it may be running on the CPU, waiting for the CPU, or waiting for a disk. The operating system tracks this with a state and moves the process between queues as events happen. It also needs a way to create processes: on Unix-like systems fork makes a copy of the caller and exec replaces the copy's program. GATE asks which transitions are possible, what causes each, which scheduler does what, and above all how many processes (or how many lines of output) a program with several fork() calls produces.

Prerequisites

You need the process and its PCB from the process model.

Precise definitions

The five-state model.

Transitions and their causes.

There is no Ready to Waiting transition (a process that is not running cannot issue a request) and no Waiting to Running (a process whose event has occurred must queue for the CPU again). With a non-preemptive scheduler Running to Ready does not happen except by a voluntary yield.

Suspended states (swapping). If memory is short, the medium-term scheduler can swap out a process to disk. The seven-state model adds Ready-suspended and Blocked-suspended (also "swapped out" states): a blocked-suspended process becomes ready-suspended when its event occurs, and the process is brought back in by swapping in.

Queues. The job queue (all processes of the system), the ready queue (processes in memory ready to run, usually a linked list of PCBs) and device queues (processes waiting for a particular device). A process moves between them as its state changes.

The three schedulers.

• Long-term (job) scheduler: chooses which processes to bring into memory; it controls the degree of multiprogramming and runs rarely.
• Short-term (CPU) scheduler: chooses which ready process runs next; runs very often (every few milliseconds), so it must be fast.
• Medium-term scheduler: swaps processes out and back in to reduce the degree of multiprogramming.

Process creation (Unix).

• fork() creates a child, a copy of the parent: same code, same next instruction, copies of the data, stack and heap (in practice copy-on-write), the same open files. It returns the child's pid in the parent, $0$ in the child, and $-1$ on error.
• exec...() replaces the calling process's program by a new one: same pid and PCB, but new code, data, heap and stack. It does not return unless it fails. The usual use is fork() followed by exec() in the child.
• wait() makes the parent block until a child terminates, then returns the child's pid and exit status. exit() terminates the calling process.
• The number of processes created by a program is found by following each fork(): every executed call doubles the number of processes that execute the code after it.

Zombie and orphan. A zombie is a process that has terminated but whose parent has not yet called wait; its PCB stays so that the exit status can be collected. An orphan is a process whose parent has terminated first; it is adopted by the init process, which collects it when it ends.

Termination. A process ends when it calls exit, returns from main, is killed by a signal or by its parent, or causes a fatal error. When a process ends, its resources (memory, open files) are released, and its parent is notified.

How it works

The first animation walks one process through the five states. Notice which transitions exist and which do not, and that a process whose I/O completes goes to Ready, not straight to Running.

The next animations interpret small programs. Each shows the C fragment every process runs (with the line each process will execute next), the process table drawn as a tree, and the output so far. First the simplest repeated case, three fork() calls in a row: the number of processes doubles at each call.

1int main(void) {
2    fork();P1
3    fork();
4    fork();
5    puts("hi");
6}

Then the two short-circuit forms. In fork() && fork() only the parent evaluates the second fork (the child's value is 0, which already decides &&); in fork() || fork() only the child does.

1int main(void) {
2    fork() && fork();P1
3    puts("hi");
4}

1int main(void) {
2    fork() || fork();P1
3    puts("hi");
4}

When the child is distinguished by the return value, as in if (fork() == 0), the two sides run different code.

1int main(void) {
2    if (fork() == 0) {P1
3        fork();
4        puts("child side");
5    } else {
6        puts("parent side");
7    }
8}

And with wait() the parent blocks until its child has finished, which is the one case in which the output order is forced.

1int main(void) {
2    if (fork() == 0) {P1
3        puts("child");
4    } else {
5        while (wait(NULL) > 0) { }
6        puts("parent after wait");
7    }
8}

Worked examples

#define _POSIX_C_SOURCE 200809L
#include <stdio.h>
#include <stdlib.h>
#include <sys/wait.h>
#include <unistd.h>
 
/* Runs `pattern` in a fresh subtree of processes and counts how many processes executed the code after it:
   every process, when it is done with its own children, writes one byte into a pipe; the number of bytes is the number of processes. */
static int count_processes(void (*pattern)(void)) {
    int fd[2];
    if (pipe(fd) != 0) return -1;
    pid_t root = fork();
    if (root < 0) return -1;
    if (root == 0) {
        pattern();
        while (wait(NULL) > 0) { }
        if (write(fd[1], "x", 1) != 1) _exit(1);
        _exit(0);
    }
    close(fd[1]);
    int status;
    waitpid(root, &status, 0);
    char c;
    int n = 0;
    while (read(fd[0], &c, 1) == 1) n++;
    close(fd[0]);
    return n;
}
 
static void three_forks(void) { fork(); fork(); fork(); }
static void and_fork(void) { fork() && fork(); }
static void or_fork(void) { fork() || fork(); }
static void child_forks(void) { if (fork() == 0) { fork(); } }
static void loop_forks(void) { for (int i = 0; i < 4; i++) fork(); }
static void two_blocks(void) { fork() && fork(); fork() && fork(); }
static void mixed(void) { (fork() && fork()) || fork(); }
 
int main(void) {
    printf("fork(); fork(); fork();            -> %d processes\n", count_processes(three_forks));
    printf("fork() && fork();                  -> %d processes\n", count_processes(and_fork));
    printf("fork() || fork();                  -> %d processes\n", count_processes(or_fork));
    printf("if (fork() == 0) { fork(); }       -> %d processes\n", count_processes(child_forks));
    printf("for (i = 0; i < 4; i++) fork();    -> %d processes\n", count_processes(loop_forks));
    printf("fork() && fork(); (twice)          -> %d processes\n", count_processes(two_blocks));
    printf("(fork() && fork()) || fork();  -> %d processes\n", count_processes(mixed));
    return 0;
}

fork(); fork(); fork();            -> 8 processes
fork() && fork();                  -> 3 processes
fork() || fork();                  -> 3 processes
if (fork() == 0) { fork(); }       -> 3 processes
for (i = 0; i < 4; i++) fork();    -> 16 processes
fork() && fork(); (twice)          -> 9 processes
(fork() && fork()) || fork();  -> 5 processes

Cheat box

Traps and GATE patterns

Connections

The PCB that each state refers to is described in the process model. Moving the CPU from the running process to a ready one is the context switch, and the short-term scheduler's choice is the subject of CPU scheduling. fork, exec, wait and exit are system calls. A thread is created far more cheaply than a forked process.

PYQs

Consider a process P running on a CPU. Which one
or more of the following events will always trigger a
context switch by the OS that results in process P
moving to a non-running state (e.g., ready, blocked)?

Which of the following process state transition(s)
is/are NOT possible?

Consider the following statements about process state
transitions for a system using preemptive scheduling.

I. A running process can move to ready state.

II. A ready process can move to running state.

III. A blocked process can move to running state.

IV. A blocked process can move to ready state.

Which of the above statements are TRUE?

The maximum number of processes that can be in
Ready state for a computer system with n CPUs is

In the following process state transition diagram for
a uniprocessor system, assume that there are always
some processes in the ready state :

Now consider the following statements :
I. If a process makes a transition D, it would result
in
another
process
making
transition
A
immediately.
II. A process P2 in a blocked state can make
transition E while another process P1 is in running
state.

III. The OS uses preemptive scheduling.

IV. The OS uses non-preemptive scheduling.

Which of the above statements are TRUE ?

Suppose in a multiprogramming environment, the
following C program segment is executed. A process
goes into I/O queue whenever an I/O related
operation is performed. Assume that there will always
be a context switch whenever a process requests for
an I/O, and also whenever the process returns from an
I/O. The number of times the process will enter the
ready queue during its lifetime (not counting the time
the process enters the ready queue when it is run
initially) is ______

Int main()
{

int x = 0, i = 0;

 scanf("%d", &x);

 for(i = 0; i < 20; i++)

 {

x = x + 20;

printf("%d\n", x);

 }

return 0;
}

OPERATING SYSTEMS

Self-check

Revision card

References