Process Management

Process = program in execution. Active entity (with state, registers, memory).
Program = passive entity (file on disk).

PROCESS STATES (5-state model):

[New] → [Ready] ⇌ [Running] → [Terminated]
                  ↓ ↑
              [Waiting / Blocked]

• New: being created.
• Ready: waiting to be assigned to CPU.
• Running: instructions being executed.
• Waiting (Blocked): waiting for some event (I/O, signal, etc.).
• Terminated: finished execution.

Transitions:

• Ready → Running: scheduler dispatches.
• Running → Ready: time slice expires (preempted).
• Running → Waiting: requests I/O or waits for event.
• Waiting → Ready: I/O completes or event happens.
• Running → Terminated: process exits.

PROCESS CONTROL BLOCK (PCB) — kernel data structure storing all info about a process.

Contents:

• Process ID (PID).
• Process state.
• Program counter (PC).
• CPU registers (saved values).
• CPU scheduling info (priority, queue pointers).
• Memory management info (page tables).
• I/O status (open files, devices).
• Accounting info (CPU time used, etc.).

PCB is essentially the "snapshot" needed to resume a paused process.

CONTEXT SWITCH — saving state of current process and loading state of another.

• Pure overhead (no useful work during the switch).
• Cost: typically microseconds.
• Frequency: hundreds to thousands per second in modern OSes.

Context switch costs:

1. Save current PCB.
2. Load next PCB.
3. Flush TLB (or selectively invalidate for some address spaces).
4. Pipeline / branch predictor state may need reset.

PROCESS CREATION

fork() in Unix:

• Creates child process that is a copy of parent.
• Returns 0 in child, child's PID in parent, −1 on failure.
• Often followed by exec() to replace child's code with new program.

exec() family: replace process image with new program. Doesn't create a new process.

wait() / waitpid(): parent waits for child to terminate.

Zombie process: terminated child whose PCB not yet reaped.
Orphan process: child whose parent died before it. Adopted by init (PID 1).

THREADS vs PROCESSES

User-level threads (run by user-mode library, OS unaware): fast switch, but blocking syscall blocks all threads.

Kernel-level threads (OS aware): one thread can block while others run; expensive to create.

Modern OSes use 1:1 mapping (one user thread = one kernel thread) — Linux, Windows.

INTER-PROCESS COMMUNICATION (IPC)

Processes need to coordinate. IPC mechanisms:

1. Shared memory: fastest. Processes map a common memory region. Need synchronization.

2. Message passing (pipes, sockets):

• Pipes (unidirectional, parent-child).
• Named pipes / FIFOs (any unrelated processes).
• Message queues (POSIX).
• Sockets (across machines too).

3. Signals: asynchronous notifications. E.g., SIGKILL, SIGTERM, SIGINT (Ctrl-C), SIGSEGV.

4. Semaphores: synchronization (covered in Pack 4).

5. Files / shared databases: simplest persistent IPC.

SYNCHRONIZATION ISSUES

When multiple processes/threads access shared data:

• Race condition: outcome depends on order of execution.
• Critical section: code accessing shared resource. Must be mutual exclusive.
• See process synchronization note (Pack 4) for semaphores, mutex, deadlock conditions.

SCHEDULING — pick which ready process runs next.

Goals:

• Maximize CPU utilization.
• Minimize wait time + response time.
• Maximize throughput.
• Fairness.

(Detailed in Pack 2: FCFS, SJF, RR, priority, multilevel feedback queue.)

KEY METRICS FOR GATE:

• Turnaround time: completion time − arrival time.
• Waiting time: turnaround − burst (CPU) time.
• Response time: time from arrival to first CPU allocation.

For SJF over n jobs:
Avg waiting time = Σ (start_time − arrival_time) / n.

FCFS (First-Come-First-Served): non-preemptive, simple FIFO. Disadvantage: convoy effect — short jobs wait behind long ones.

SJF (Shortest Job First): picks job with shortest CPU burst. Optimal for average waiting time. Disadvantage: requires knowing burst time; can starve long jobs.

SRTF (Shortest Remaining Time First): preemptive SJF. Preempts running job if a new shorter job arrives.

Round Robin (RR): each process gets a fixed time quantum. Fair, suitable for time-sharing systems. Performance depends on quantum size:

• Too small → high context-switch overhead
• Too large → degrades to FCFS

Priority Scheduling: each process has a priority; CPU goes to highest priority. Can be preemptive or non-preemptive. Problem: starvation of low-priority processes. Fix: aging — gradually raise priority of waiting processes.

Multilevel Queue: multiple queues with different scheduling policies (e.g. system processes RR, batch jobs FCFS). Fixed assignment.

Multilevel Feedback Queue: processes can move between queues based on behaviour. The general-purpose default in modern OSes.

Comparison summary:

Worked example. Three processes: P1 (burst 10), P2 (burst 5), P3 (burst 8) all arrive at time 0.

• FCFS order P1→P2→P3: waiting times 0, 10, 15. Avg = 8.33.
• SJF order P2→P3→P1: waiting times 0, 5, 13. Avg = 6.0. ← optimal.

A program is a passive entity (file on disk); a process is an active entity with a program counter, registers, stack, and resources. The Process Control Block (PCB) stores per-process info: PID, process state, program counter, CPU registers, scheduling info (priority), memory-management info (page/segment tables), accounting info, and I/O status (open files). Memory aid: 'PC RAMS-IO' (PID, Counter, Registers, Accounting, Memory, State, IO). The PCB is saved/restored during a context switch. A process address space has four regions: Text (code), Data (globals), Heap (dynamic, grows up), and Stack (grows down). Remember 'TDHS' bottom-to-top. Context switch overhead is pure scheduling cost; no useful work is done during it.

States: New, Ready, Running, Waiting (Blocked), Terminated. Valid transitions: New to Ready (admitted); Ready to Running (scheduler dispatch); Running to Ready (timer interrupt/preemption); Running to Waiting (I/O or event wait); Waiting to Ready (I/O completion); Running to Terminated (exit). KEY trap: there is NO direct Waiting to Running and NO direct Ready to Waiting transition. Only one process per CPU is in Running. A blocked process MUST pass through Ready before running again. Suspended states (swapped to disk) add Ready-Suspended and Blocked-Suspended in the 7-state model. The dispatcher performs Ready to Running; dispatch latency is the time to stop one process and start another.

A context switch saves the current process state into its PCB and loads the next process's state. Triggered by: interrupts, system calls causing blocking, or preemption (timer). Mode switch (user to kernel) is cheaper than a full context switch and does not necessarily change the running process. Example: if a context switch costs 2 ms and a time quantum is 8 ms, then for every 8 ms of useful work, 2 ms is overhead, giving CPU efficiency = 8/(8+2) = 80%. Smaller quanta increase responsiveness but raise context-switch overhead; larger quanta reduce overhead but approach FCFS behaviour. Saving/restoring registers is hardware-assisted on many architectures.

Process = program in execution. Active entity (with state, registers, memory).
Program = passive entity (file on disk).

PROCESS STATES (5-state model):

[New] → [Ready] ⇌ [Running] → [Terminated]
                  ↓ ↑
              [Waiting / Blocked]

• New: being created.
• Ready: waiting to be assigned to CPU.
• Running: instructions being executed.
• Waiting (Blocked): waiting for some event (I/O, signal, etc.).
• Terminated: finished execution.

Transitions:

• Ready → Running: scheduler dispatches.
• Running → Ready: time slice expires (preempted).
• Running → Waiting: requests I/O or waits for event.
• Waiting → Ready: I/O completes or event happens.
• Running → Terminated: process exits.

PROCESS CONTROL BLOCK (PCB) — kernel data structure storing all info about a process.

Contents:

• Process ID (PID).
• Process state.
• Program counter (PC).
• CPU registers (saved values).
• CPU scheduling info (priority, queue pointers).
• Memory management info (page tables).
• I/O status (open files, devices).
• Accounting info (CPU time used, etc.).

PCB is essentially the "snapshot" needed to resume a paused process.

CONTEXT SWITCH — saving state of current process and loading state of another.

• Pure overhead (no useful work during the switch).
• Cost: typically microseconds.
• Frequency: hundreds to thousands per second in modern OSes.

Context switch costs:

1. Save current PCB.
2. Load next PCB.
3. Flush TLB (or selectively invalidate for some address spaces).
4. Pipeline / branch predictor state may need reset.

PROCESS CREATION

fork() in Unix:

• Creates child process that is a copy of parent.
• Returns 0 in child, child's PID in parent, −1 on failure.
• Often followed by exec() to replace child's code with new program.

exec() family: replace process image with new program. Doesn't create a new process.

wait() / waitpid(): parent waits for child to terminate.

Zombie process: terminated child whose PCB not yet reaped.
Orphan process: child whose parent died before it. Adopted by init (PID 1).

THREADS vs PROCESSES

User-level threads (run by user-mode library, OS unaware): fast switch, but blocking syscall blocks all threads.

Kernel-level threads (OS aware): one thread can block while others run; expensive to create.

Modern OSes use 1:1 mapping (one user thread = one kernel thread) — Linux, Windows.

INTER-PROCESS COMMUNICATION (IPC)

Processes need to coordinate. IPC mechanisms:

1. Shared memory: fastest. Processes map a common memory region. Need synchronization.

2. Message passing (pipes, sockets):

• Pipes (unidirectional, parent-child).
• Named pipes / FIFOs (any unrelated processes).
• Message queues (POSIX).
• Sockets (across machines too).

3. Signals: asynchronous notifications. E.g., SIGKILL, SIGTERM, SIGINT (Ctrl-C), SIGSEGV.

4. Semaphores: synchronization (covered in Pack 4).

5. Files / shared databases: simplest persistent IPC.

SYNCHRONIZATION ISSUES

When multiple processes/threads access shared data:

• Race condition: outcome depends on order of execution.
• Critical section: code accessing shared resource. Must be mutual exclusive.
• See process synchronization note (Pack 4) for semaphores, mutex, deadlock conditions.

SCHEDULING — pick which ready process runs next.

Goals:

• Maximize CPU utilization.
• Minimize wait time + response time.
• Maximize throughput.
• Fairness.

(Detailed in Pack 2: FCFS, SJF, RR, priority, multilevel feedback queue.)

KEY METRICS FOR GATE:

• Turnaround time: completion time − arrival time.
• Waiting time: turnaround − burst (CPU) time.
• Response time: time from arrival to first CPU allocation.

For SJF over n jobs:
Avg waiting time = Σ (start_time − arrival_time) / n.

Key metrics: Turnaround Time (TAT) = Completion Time - Arrival Time; Waiting Time (WT) = TAT - Burst Time; Response Time = first CPU allocation time - Arrival Time. Average WT and average TAT are computed over all processes. Throughput = processes completed per unit time; CPU Utilization should be maximized. Memory aid: 'TAT = WT + BT' and 'WT = TAT - BT'. For non-preemptive algorithms, response time often equals waiting time. Goal: minimize WT, TAT, and response time; maximize throughput and utilization. Note arrival times carefully: idle CPU time before the first arrival is not counted as waiting for any process.

FCFS: non-preemptive, by arrival order; suffers convoy effect (short jobs wait behind long ones). SJF: non-preemptive, picks shortest burst; provably gives minimum average waiting time. SRTF: preemptive SJF; optimal preemptive WT but causes starvation of long jobs. Priority: highest priority first; starvation fixed by aging. Round Robin (RR): preemptive FCFS with time quantum q; if q is very large, RR to FCFS; if q to 0, overhead dominates. RR response time is good; it is fair. Memory aid: 'SJF/SRTF minimize average waiting time'. Both SJF and SRTF need burst-length knowledge (estimated via exponential averaging).

Processes (Arrival, Burst): P1(0,8), P2(1,4), P3(2,9), P4(3,5). SRTF (preemptive): At t=0 run P1 (rem 8). At t=1, P2 arrives (4) < P1 rem(7), so P2 runs. At t=2 P3(9) vs P2 rem(3): P2 continues. At t=3 P4(5) vs P2 rem(2): P2 continues, finishes t=5. Then choose smallest among P1(7), P4(5): P4 runs to t=10. Then P1(7) to t=17, then P3(9) to t=26. Completion: P1=17, P2=5, P3=26, P4=10. TAT = C - A: P1=17, P2=4, P3=24, P4=7. WT = TAT - BT: P1=9, P2=0, P3=15, P4=2. Average WT = (9+0+15+2)/4 = 6.5.

A thread is a lightweight unit of execution within a process. Threads of the same process SHARE: code/text, data (globals), heap, and open files/signals. Each thread has PRIVATE: program counter, registers, and its own stack. Memory aid: 'Stack and Registers are Selfish; Code, Data, Heap, Files are Shared' (SR-private, CDHF-shared). Thread creation and context switching are cheaper than process creation because the address space is shared (no page-table switch, no TLB flush in many cases). Benefits: responsiveness, resource sharing, economy, scalability on multiprocessors. Risk: lack of isolation; one thread's bad pointer can corrupt the whole process.

Mapping user threads to kernel threads: Many-to-One (all user threads to one kernel thread; one blocking call blocks all; no true parallelism), One-to-One (each user thread to a kernel thread; true parallelism but costly; used by Linux/Windows), Many-to-Many (m user threads to n kernel threads; flexible). User-level threads are fast to manage but the kernel sees only one schedulable entity; kernel-level threads allow blocking one without blocking others and enable multiprocessor parallelism. Memory aid: 'Many-to-One blocks all'. POSIX Pthreads is a specification; implementations may be user or kernel level.

fork() creates a child process duplicating the parent's address space (copy-on-write). It returns the child PID to the parent and 0 to the child. Counting trick: n consecutive fork() calls create 2^n - 1 child processes (total 2^n processes including the original). Example: code with three fork() calls in sequence yields 2^3 = 8 total processes, hence 7 children. With branching/conditionals, draw the process tree. After fork(), parent and child have separate copies of variables; changes in one do not affect the other. exec() replaces the process image; wait() lets a parent block until a child terminates, reaping zombies.

Two fundamental IPC models. Shared Memory: processes share a region of memory; fast (after setup) since no kernel involvement per access, but requires explicit synchronization to avoid race conditions. Message Passing: processes exchange messages via send/receive; easier for distributed systems, no shared variables, but slower due to kernel involvement and copying. Message passing can be blocking (synchronous) or non-blocking (asynchronous), with direct or indirect (mailbox/port) addressing. Memory aid: 'Shared memory = fast but you synchronize; Message passing = safe but slow'. Pipes, sockets, and message queues are common implementations; named pipes (FIFOs) persist and work between unrelated processes.

A race condition occurs when the outcome depends on the non-deterministic ordering of concurrent accesses to shared data. The critical section (CS) is the code segment accessing shared resources. Any correct CS solution must satisfy THREE requirements: (1) Mutual Exclusion - at most one process in the CS at a time; (2) Progress - if no process is in the CS, selection of the next entrant cannot be postponed indefinitely and only contenders decide; (3) Bounded Waiting - a bound exists on how many times others enter before a waiting process is granted entry. Memory aid: 'ME, Progress, Bounded Wait' = 'MPB'. Note: assumptions about relative process speeds or number of CPUs must NOT be made.

Peterson's algorithm solves the two-process critical section problem in software using two shared variables: boolean flag[2] (intent to enter) and int turn (whose turn it is). Entry for process i: flag[i]=true; turn=j; while(flag[j] && turn==j) wait; ... Exit: flag[i]=false. It satisfies all three requirements: mutual exclusion, progress, and bounded waiting. Caveat for GATE: Peterson's solution assumes atomic load/store and sequentially consistent memory; on modern CPUs with instruction reordering it may fail without memory barriers. It works for only TWO processes. Memory aid: 'set flag, give turn away, then wait'. Strict alternation (turn only) violates progress; flags only can deadlock.