Process Management

Process states, PCB, scheduling algorithms.

Scheduling algorithms

FCFS, SJF, RR, priority, multilevel queue.

CPU scheduling algorithms — when to use which

Notes

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:

Algorithm	Preemptive?	Optimizes	Starvation?
FCFS	No	Nothing specific	No
SJF	No	Avg waiting time	Yes (long jobs)
SRTF	Yes	Avg waiting time	Yes (long jobs)
Round Robin	Yes	Response time, fairness	No
Priority	Either	Custom criteria	Yes (low priority)

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.

Processes — states, PCB, context switch, IPC, threads vs processes

Notes

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:

Save current PCB.
Load next PCB.
Flush TLB (or selectively invalidate for some address spaces).
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

Feature	Process	Thread
Address space	Separate	Shared within process
Memory	Own heap, stack, code	Own stack; shared heap and code
Communication	IPC (slower)	Shared memory (fast)
Creation cost	High (fork+exec)	Lower
Context switch	Slower (TLB flush)	Faster
Crash impact	Isolated	Crashes whole process

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.

Process synchronization

Critical section, Peterson, semaphores.

Processes — states, PCB, context switch, IPC, threads vs processes

Notes

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:

Save current PCB.
Load next PCB.
Flush TLB (or selectively invalidate for some address spaces).
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

Feature	Process	Thread
Address space	Separate	Shared within process
Memory	Own heap, stack, code	Own stack; shared heap and code
Communication	IPC (slower)	Shared memory (fast)
Creation cost	High (fork+exec)	Lower
Context switch	Slower (TLB flush)	Faster
Crash impact	Isolated	Crashes whole process

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.