Process Management | Computer Science

flowchart TD
    A[2_Process Management] --> B[Key Concepts]
    A --> C[Core Principles]
    A --> D[Practical Applications]
    B --> E[Fundamental definitions]
    C --> F[Design patterns]
    D --> G[Real-world usage]

A process is a program in action — it’s the abstract entity that the OS manages, containing not just code but all the state needed to execute: memory, open files, registers, and more. The OS creates the illusion that each process has the entire computer to itself through virtual memory and time-sliced CPU access.

Scheduling intuition: The scheduler decides which process runs next. Round-robin gives each process a time slice. Priority scheduling favours important processes. The goal is to maximise throughput (jobs completed per unit time) while minimising response time (how long users wait). Context switching is expensive — saving and restoring all registers and TLB entries — so the scheduler must balance responsiveness against overhead.

Process states intuition: A process transitions between states: new (being created), ready (waiting for CPU), running (executing), waiting (blocked on I/O), and terminated. The key insight is that processes spend most of their time waiting for I/O, not running. This is why multiprogramming works — while one process waits, another runs.

A process is an instance of a program in execution. The OS maintains a process control block (PCB) for each process:

Process states. Processes transition through states:

$\mathrm{New} \to \mathrm{Ready} \to \mathrm{Running} \to \mathrm{Terminated}$

$\mathrm{Running} \to \mathrm{Blocked} \to \mathrm{Ready}$

The scheduler dispatches processes from ready to running. A running process may be preempted back to ready, or may block on I/O or a synchronisation event.

A thread is the fundamental unit of CPU execution. Multiple threads within a process share the Same address space, open files, and other resources, but each has its own program counter, Registers, and stack.

User-level threads. Managed entirely by a user-space library (e.g., POSIX pthread). The OS is Unaware of them.

• Advantage: Fast creation and switching (no kernel involvement).
• Disadvantage: One blocking system call blocks all threads in the process.

Kernel-level threads. Managed by the OS kernel (e.g., Linux clone()Windows threads).

• Advantage: True parallelism on multiprocessor systems; blocking one thread does not block others.
• Disadvantage: Slower creation and context switch (kernel trap required).

Thread models:

Linux uses a $1:1$ model by default.

The CPU scheduler decides which process runs next from the set of ready processes.

Scheduling criteria:

• CPU utilisation: Keep the CPU busy ($\mathrm{utilisation} = 1 - p$ where $p$ is the I/O wait probability).
• Throughput: Number of processes completed per time unit.
• Turnaround time: $T_{\mathrm{turnaround} = T_{\mathrm{completion} - T_{\mathrm{arrival}}}}$.
• Waiting time: Time spent in the ready queue.
• Response time: Time from submission to first response.

First-Come, First-Served (FCFS). Non-preemptive. Processes scheduled in arrival order. Suffers From the convoy effect: short processes waiting behind a long process.

Shortest Job First (SJF). Non-preemptive. Schedule the process with the shortest next CPU burst. Provably optimal for average waiting time. Requires burst length estimation via exponential Averaging: $\tau_{n+1} = \alpha t_n + (1 - \alpha) \tau_n$.

Shortest Remaining Time First (SRTF). Preemptive SJF. If a new process arrives with a shorter Remaining burst, preempt the current process.

Round Robin (RR). Each process gets a time quantum $q$. If not finished within $q$Preempted and Placed at the back of the ready queue. If $q$ is large, RR degenerates to FCFS. Typical $q$: $10\mathrm{--100}$ ms.

Priority Scheduling. Highest-priority ready process runs. Can be preemptive or non-preemptive. Risk of starvation; solved by aging (gradually increase priority of waiting processes).

Multilevel Feedback Queue (MLFQ). Partition the ready queue into multiple priority levels. Processes that use too much CPU are demoted; processes that wait are promoted. The most general and Widely used approach. Linux CFS uses a variant with red-black trees keyed on virtual runtime.

Theorem 2.1. SJF gives the minimum average waiting time for a given set of processes.

Proof. Consider any schedule that is not SJF. There exist consecutive processes $A$ and $B$ where $A$ has a longer burst than $B$ but is scheduled first. Swapping $A$ and $B$ reduces the waiting Time of $B$ by the burst time of $A$ and increases the waiting time of $A$ by the burst time of $B$. Since $B$“s burst is shorter, the net change reduces the average. $\blacksquare$

Worked Example 2.1 — FCFS vs SJF Comparison

Consider three processes, all arriving at time $t = 0$:

FCFS Gantt chart:

| P1 (24)      | P2 (3) | P3 (3) |
0              24       27      30

SJF Gantt chart:

| P2 (3) | P3 (3) | P1 (24)           |
0        3       6                  30

SJF reduces average waiting time from 17 to 3, illustrating the convoy effect in FCFS.

| P1(4) | P2(3) | P3(3) | P1(4) | P1(4) | P1(4) | P1(4) | P1(1) |
0       4       7       10     14     18     22     26     27

Round Robin Scheduling:

#define MAX_PROCESSES 128

typedef struct {
    int pid;
    int burst_remaining;
    int arrival_time;
    int priority;
} Process;

void round_robin(Process processes[], int n, int quantum) {
    Queue ready_queue;
    int current_time = 0;
    int completed = 0;

    while (completed < n) {
        for (int i = 0; i < n; i++) {
            if (processes[i].arrival_time <= current_time
                && processes[i].burst_remaining > 0
                && !is_in_queue(&ready_queue, processes[i].pid)) {
                enqueue(&ready_queue, &processes[i]);
            }
        }
        if (is_empty(&ready_queue)) {
            current_time++;
            continue;
        }
        Process *p = dequeue(&ready_queue);
        int exec_time = min(p->burst_remaining, quantum);
        p->burst_remaining -= exec_time;
        current_time += exec_time;
        if (p->burst_remaining > 0) {
            enqueue(&ready_queue, p);
        } else {
            completed++;
            record_turnaround(p->pid, current_time - p->arrival_time);
        }
    }
}

Priority Scheduling (preemptive):

void priority_schedule(Process processes[], int n) {
    int current_time = 0;
    int completed = 0;
    int shortest_priority = INT_MAX;
    int idx = -1;

    while (completed < n) {
        shortest_priority = INT_MAX;
        idx = -1;
        for (int i = 0; i < n; i++) {
            if (processes[i].arrival_time <= current_time
                && processes[i].burst_remaining > 0
                && processes[i].priority < shortest_priority) {
                shortest_priority = processes[i].priority;
                idx = i;
            }
        }
        if (idx == -1) {
            current_time++;
            continue;
        }
        processes[idx].burst_remaining--;
        current_time++;
        if (processes[idx].burst_remaining == 0) {
            completed++;
            record_turnaround(processes[idx].pid,
                              current_time - processes[idx].arrival_time);
        }
    }
}

Multilevel Feedback Queue:

#define NUM_LEVELS 3
#define QUANTUMS {8, 16, 32}

void mlfq_schedule(Process processes[], int n, int quantums[]) {
    Queue queues[NUM_LEVELS];
    int current_time = 0;
    int completed = 0;

    while (completed < n) {
        for (int i = 0; i < n; i++) {
            if (processes[i].arrival_time <= current_time
                && processes[i].burst_remaining > 0
                && !is_any_queue(&queues, processes[i].pid)) {
                enqueue(&queues[0], &processes[i]);
            }
        }
        int level;
        for (level = 0; level < NUM_LEVELS; level++) {
            if (!is_empty(&queues[level])) break;
        }
        if (level == NUM_LEVELS) {
            current_time++;
            continue;
        }
        Process *p = dequeue(&queues[level]);
        int exec_time = min(p->burst_remaining, quantums[level]);
        p->burst_remaining -= exec_time;
        current_time += exec_time;
        if (p->burst_remaining > 0 && level + 1 < NUM_LEVELS) {
            enqueue(&queues[level + 1], p);
        } else if (p->burst_remaining > 0) {
            enqueue(&queues[level], p);
        } else {
            completed++;
            record_turnaround(p->pid, current_time - p->arrival_time);
        }
    }
}

Processes may need to communicate and synchronise. IPC mechanisms:

Shared memory. A region of memory mapped into multiple address spaces. Fast, but requires Explicit synchronisation.

int shmid = shmget(SHM_KEY, SHM_SIZE, IPC_CREAT | 0666);
char *shm_ptr = (char *)shmat(shmid, NULL, 0);
shm_ptr[offset] = data;
shmdt(shm_ptr);

Message passing. Processes exchange messages through the OS. Operations: send(dest, msg) and receive(src, msg). Can be direct (named processes) or indirect (via mailboxes/ports).

Pipes. Unidirectional data channel. pipe() creates a pipe; fork() inherits file descriptors. Named pipes (mkfifo) allow unrelated processes to communicate.

Signals. Asynchronous notifications (integer payload only). Common: SIGTERM``SIGKILL SIGSEGV``SIGCHLD.

• Discrete Mathematics
• Algorithm Implementation

1. Assuming fork() copies the entire address space. Modern systems use copy-on-write (COW) for fork(). Pages are shared between parent and child until one writes, at which point a copy is made. This makes fork() nearly O(1), but the cost is paid at write time, not at fork time.

2. Confusing zombie processes with orphan processes. A zombie process has finished executing but its entry remains in the process table because the parent has not called wait(). An orphan process is still running but its parent has exited. Zombies are cleaned up by wait(); orphans are adopted by init.

3. Using SIGKILL as a first resort. SIGKILL cannot be caught or handled — the process has no chance to clean up resources, flush buffers, or release locks. Always try SIGTERM first, which allows the process to shut down gracefully, and only escalate to SIGKILL if it does not respond.

4. Ignoring race conditions in shared memory IPC. Shared memory provides no built-in synchronisation. Without explicit locks (mutexes, semaphores), concurrent reads and writes to the same region cause data races and undefined behaviour. Message passing is safer when synchronisation is difficult to implement correctly.

5. Assuming process priorities are static. Most schedulers dynamically adjust priorities based on behaviour. A process that uses too much CPU time is penalised (lowered priority), while I/O-bound processes are boosted. This means short-lived, interactive processes get better response times, but CPU-bound batch jobs may be starved without explicit nice values or cgroup limits.