Process model and PCB

Why it exists

A computer runs many activities at once, or seems to. The operating system needs one uniform thing to manage: something that owns memory, has a state, can be started, stopped and resumed, and can be protected from the others. That thing is the process. Every other topic in operating systems (scheduling, synchronization, memory management, deadlock) is about processes. GATE asks what is in a process and in the process control block, what information must be saved to resume a process, how processes relate to each other, and how many processes it takes to keep the CPU busy.

Prerequisites

The services a process requests from the kernel come through system calls, which is also how a process is created and destroyed.

Precise definitions

Program and process. A program is a passive file on disk: code and initial data. A process is a program in execution: an active entity with a program counter, registers, a stack and its own memory. One program can be several processes at once (two users running the same editor), each with its own state.

Process image (address space). The memory a process uses:

• text (code): the instructions, normally read-only and shareable;
• data: global and static variables (initialised data and uninitialised, the bss);
• heap: memory allocated at run time (malloc), growing upward;
• stack: activation records of function calls, growing downward.

The same layout appears in C memory layout. Besides memory, a process has CPU state (the program counter and registers) and resources (open files, for example).

Process control block (PCB), also task control block. The kernel data structure that represents a process. It holds everything the OS needs to manage it and to resume it later:

• process identifier (pid), the parent's pid and the user id;
• process state (new, ready, running, waiting, terminated);
• CPU registers and program counter (saved when the process is not running);
• CPU scheduling information: priority, pointers to scheduling queues, time used;
• memory-management information: base and limit registers or the page table pointer, segment tables;
• accounting information: CPU time used, time limits;
• I/O status information: open files, allocated devices.

The process table is the array (or list) of all PCBs. Ready and waiting processes are kept in queues made of PCBs.

Process identification and hierarchy. Every process has a unique pid. A process creates others, the children, with a system call (fork), forming a tree with the first user process as root (init or systemd on Unix-like systems). A process knows its parent's pid (ppid). Some systems, such as Windows, have no such strict tree.

Kinds of process. An I/O-bound process spends most of its time waiting for I/O and runs in short CPU bursts; a CPU-bound process spends most of its time computing, in few long bursts. A good mix keeps both the CPU and the devices busy.

Degree of multiprogramming. The number of processes in memory at the same time. More processes mean the CPU is more likely to have one to run while others wait for I/O.

CPU utilization model. If each process spends a fraction $p$ of its time waiting for I/O, and the $n$ processes in memory wait independently, the CPU is idle only if all $n$ wait at the same moment, which has probability $p^n$. So

$\text{CPU utilization} = 1 - p^n.$

The curve rises steeply for small $n$ and then flattens: each additional process helps less. It ignores the cost of context switching and the memory needed by each extra process.

How it works

The animation shows the process table of the smallest possible example: one process calls fork(). The kernel allocates a new PCB, gives it a new pid and records the parent, and the child starts as a copy of the parent: same code and the same next instruction, but its own data. The table shows each process's pid, its parent, its state and what it has printed.

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

Worked examples

#include <stdio.h>
 
int main(void) {
    /* a fraction p of a process's time is spent waiting for I/O; with n processes in memory the CPU is idle only if all of them wait at once */
    double p = 0.8;
    double prod = 1;
    for (int n = 1; n <= 8; n++) {
        prod *= p;
        printf("n = %d processes: CPU utilization = 1 - %.1f^%d = %5.1f%%\n", n, p, n, 100 * (1 - prod));
    }
    return 0;
}

n = 1 processes: CPU utilization = 1 - 0.8^1 =  20.0%
n = 2 processes: CPU utilization = 1 - 0.8^2 =  36.0%
n = 3 processes: CPU utilization = 1 - 0.8^3 =  48.8%
n = 4 processes: CPU utilization = 1 - 0.8^4 =  59.0%
n = 5 processes: CPU utilization = 1 - 0.8^5 =  67.2%
n = 6 processes: CPU utilization = 1 - 0.8^6 =  73.8%
n = 7 processes: CPU utilization = 1 - 0.8^7 =  79.0%
n = 8 processes: CPU utilization = 1 - 0.8^8 =  83.2%

Cheat box

Traps and GATE patterns

Connections

A process is created and destroyed through system calls and moves between the states shown on process states, fork and exec. Switching the CPU between processes saves and loads the PCB (context switching). A thread is a unit of execution inside a process that shares its address space. The memory layout is that of C memory layout.

PYQs

Consider the following code snippet using the
fork() and wait() system calls. Assume that the code
compiles and runs correctly, and that the system
calls run successfully without any errors.

int x = 3;

while (x > 0) {

  fork();

  printf("hello");

  wait(NULL);

  x--;

}

The total number of times the printf statement is

executed is ________.

Consider the following C program is executed on a
Unix/Linux system:

#include <unistd.h>

int main()

{

int i;

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

if(i % 2 == 0)

fork();

return 0;

}
The total number of child processes created is
__________.

A process executes the code

fork ();

fork ();

fork ();

The total number of child processes created is

A process executes the following code:

for(i=0;i<n;i++)
    fork();

The total number of child processes created is

Consider the following code fragment:

if (fork() == 0)

{

  a = a + 5;

 printf("%d, %p\n", a, &a);

}

else

{

a = a - 5;

 printf("%d, %p\n", a, &a);

}

Let u, v be the values printed by the parent process

and x, y be the values printed by the child process.

Which one of the following is TRUE?

Self-check

Revision card

References