W Code - Pattern-Based DSA Learning Platform

Bhanu Bisht

Back to Operating Systems

Process Management

Processes, Threads, Scheduling & Synchronization

Topics

Minutes

Important

For Interviews

Process vs Thread

Process: A program in execution. It has its own memory space, resources, and state.

Thread: A lightweight unit of execution within a process. Threads share the process's memory.

Comparison:

Aspect	Process	Thread
Memory	Separate memory space	Shares memory with other threads
Creation	Heavy (slow)	Light (fast)
Communication	IPC needed (pipes, sockets)	Direct (shared memory)
Context Switch	Expensive	Cheap
Crash Impact	Only that process	Entire process crashes

Process States (7-State Model):

Process Control Block (PCB): Contains: Process ID, State, CPU registers, Memory info, I/O status, Scheduling info

CPU Scheduling Algorithms

CPU Scheduler decides which process gets CPU time and for how long.

Key Terms: • Arrival Time (AT): When process enters ready queue • Burst Time (BT): CPU time needed • Completion Time (CT): When process finishes • Turnaround Time (TAT): CT - AT • Waiting Time (WT): TAT - BT

1. First Come First Serve (FCFS) • Non-preemptive • Simple, but causes Convoy Effect • Long processes block short ones

2. Shortest Job First (SJF) • Non-preemptive • Minimum average waiting time • Problem: Starvation of long processes

3. Shortest Remaining Time First (SRTF) • Preemptive version of SJF • If new process has shorter burst, preempt

4. Round Robin (RR) • Preemptive, uses time quantum (q) • Each process gets q time, then goes to back of queue • Good for time-sharing systems • If q too small → too many context switches • If q too large → becomes FCFS

5. Priority Scheduling • Higher priority runs first • Can be preemptive or non-preemptive • Problem: Starvation (low priority never runs) • Solution: Aging (increase priority over time)

6. Multilevel Queue • Multiple queues with different priorities • Each queue can have different algorithm • Example: Foreground (RR), Background (FCFS)

7. Multilevel Feedback Queue • Processes can move between queues • New processes start in high priority queue • If uses too much CPU, moved to lower queue

Process Synchronization

Race Condition: When multiple processes access shared data concurrently and result depends on execution order.

Critical Section: Code segment where shared resources are accessed.

Requirements for Critical Section Solution:

Mutual Exclusion: Only one process in critical section at a time
Progress: If no one in CS, a waiting process should enter
Bounded Waiting: Limit on how long a process waits

Peterson's Solution (for 2 processes):

flag[i] = true;        // I want to enter
turn = j;              // Give other process a chance
while (flag[j] && turn == j);  // Wait if other wants & it's their turn
// CRITICAL SECTION
flag[i] = false;       // I'm done

Semaphore: Integer variable for synchronization

Binary Semaphore (Mutex): • Value: 0 or 1 • Used for mutual exclusion

Counting Semaphore: • Value: 0 to N • Used for resource counting

Operations:

wait(S) / P(S) / down(S):
    while (S <= 0);  // busy wait
    S--;

signal(S) / V(S) / up(S):
    S++;

Producer-Consumer Problem:

// Shared: buffer[N], in, out
// Semaphores: empty=N, full=0, mutex=1

Producer:
    wait(empty);     // Wait for empty slot
    wait(mutex);     // Lock buffer
    // Add item to buffer
    signal(mutex);   // Unlock buffer
    signal(full);    // Signal item added

Consumer:
    wait(full);      // Wait for item
    wait(mutex);     // Lock buffer
    // Remove item from buffer
    signal(mutex);   // Unlock buffer
    signal(empty);   // Signal slot freed

Deadlock

Deadlock: A situation where processes are waiting for resources held by each other, creating a cycle with no progress.

Example:

Process P1: Has R1, Wants R2
Process P2: Has R2, Wants R1
→ Both waiting forever = DEADLOCK

Necessary Conditions (all 4 must hold):

Mutual Exclusion: Resource can be held by only one process
Hold and Wait: Process holding resources can request more
No Preemption: Resources can't be forcibly taken
Circular Wait: Circular chain of processes waiting

Handling Deadlock:

1. Prevention - Break one of the 4 conditions • No Hold & Wait: Request all resources at once • Preemption: Forcibly take resources • Ordered Resources: Request in fixed order (breaks circular wait)

2. Avoidance - Don't enter unsafe state • Banker's Algorithm: Check if request leaves system in safe state • Safe State: Can complete all processes with available resources

3. Detection & Recovery • Build Resource Allocation Graph • If cycle exists → deadlock • Recovery: Kill process or preempt resources

4. Ignore - Ostrich Algorithm • Hope it doesn't happen • Used in most OS (Windows, Linux)

Banker's Algorithm:

Need[i][j] = Max[i][j] - Allocation[i][j]

Safety Check:
1. Work = Available
2. Find process i where Need[i] <= Work
3. If found: Work += Allocation[i], mark finished
4. Repeat until all finished (SAFE) or stuck (UNSAFE)

Inter-Process Communication (IPC)

IPC allows processes to communicate and synchronize.

Types of IPC:

1. Shared Memory

┌─────────────┐     ┌─────────────┐
│  Process A  │     │  Process B  │
└──────┬──────┘     └──────┬──────┘
       │                   │
       └───────┬───────────┘
               │
    ┌──────────▼──────────┐
    │   Shared Memory     │
    └─────────────────────┘

• Fast (no kernel involvement after setup) • Needs synchronization (semaphores) • Example: shmget(), shmat() in Unix

2. Message Passing

Process A ──send(msg)──► Kernel ──receive()──► Process B

• Slower (kernel involved) • Built-in synchronization • Good for distributed systems

3. Pipes • Unidirectional communication • Used between related processes (parent-child) • Anonymous pipes: pipe() • Named pipes (FIFO): exist in file system

4. Sockets • Network communication • Can be on same or different machines • TCP (reliable) or UDP (fast)

5. Signals • Notify process of events • Examples: SIGKILL, SIGTERM, SIGINT (Ctrl+C) • Limited information (just signal number)

Message Passing Types:

Type	Sender	Receiver
Blocking Send	Waits until received	-
Non-blocking Send	Returns immediately	-
Blocking Receive	-	Waits until message
Non-blocking Receive	-	Returns NULL if no message

Classic Synchronization Problems

1. Producer-Consumer Problem • Producer creates items, puts in buffer • Consumer takes items from buffer • Buffer has limited size • Solution: Use semaphores (empty, full, mutex)

2. Readers-Writers Problem • Multiple readers can read simultaneously • Writers need exclusive access • Variants: Reader-priority, Writer-priority

Reader-Writer Solution:

// Semaphores: rw_mutex=1, mutex=1
// Variable: read_count=0

Reader:
    wait(mutex);
    read_count++;
    if (read_count == 1) wait(rw_mutex);  // First reader locks
    signal(mutex);
    // READ
    wait(mutex);
    read_count--;
    if (read_count == 0) signal(rw_mutex);  // Last reader unlocks
    signal(mutex);

Writer:
    wait(rw_mutex);
    // WRITE
    signal(rw_mutex);

3. Dining Philosophers Problem • 5 philosophers, 5 forks, circular table • Need 2 forks to eat • Problem: Deadlock if all pick left fork

Solutions: • Allow only 4 philosophers at table • Pick both forks atomically • Odd picks left first, even picks right first

4. Sleeping Barber Problem • Barber sleeps if no customer • Customer waits if barber busy • Limited waiting chairs • Uses semaphores for coordination

Monitor: • High-level synchronization construct • Only one process can be active inside • Has condition variables (wait, signal) • Easier than semaphores, less error-prone

Aspect

Process

Thread

Memory

Separate memory space

Shares memory with other threads

Creation

Heavy (slow)

Light (fast)

Communication

IPC needed (pipes, sockets)

Direct (shared memory)

Context Switch

Expensive

Cheap

Crash Impact

Only that process

Entire process crashes

CPU Scheduler decides which process gets CPU time and for how long.

1. First Come First Serve (FCFS) • Non-preemptive • Simple, but causes Convoy Effect • Long processes block short ones

2. Shortest Job First (SJF) • Non-preemptive • Minimum average waiting time • Problem: Starvation of long processes

3. Shortest Remaining Time First (SRTF) • Preemptive version of SJF • If new process has shorter burst, preempt

6. Multilevel Queue • Multiple queues with different priorities • Each queue can have different algorithm • Example: Foreground (RR), Background (FCFS)

7. Multilevel Feedback Queue • Processes can move between queues • New processes start in high priority queue • If uses too much CPU, moved to lower queue

flag[i] = true; // I want to enter turn = j; // Give other process a chance while (flag[j] && turn == j); // Wait if other wants & it's their turn // CRITICAL SECTION flag[i] = false; // I'm done

// Shared: buffer[N], in, out // Semaphores: empty=N, full=0, mutex=1 Producer: wait(empty); // Wait for empty slot wait(mutex); // Lock buffer // Add item to buffer signal(mutex); // Unlock buffer signal(full); // Signal item added Consumer: wait(full); // Wait for item wait(mutex); // Lock buffer // Remove item from buffer signal(mutex); // Unlock buffer signal(empty); // Signal slot freed

Need[i][j] = Max[i][j] - Allocation[i][j] Safety Check: 1. Work = Available 2. Find process i where Need[i] <= Work 3. If found: Work += Allocation[i], mark finished 4. Repeat until all finished (SAFE) or stuck (UNSAFE)

┌─────────────┐ ┌─────────────┐ │ Process A │ │ Process B │ └──────┬──────┘ └──────┬──────┘ │ │ └───────┬───────────┘ │ ┌──────────▼──────────┐ │ Shared Memory │ └─────────────────────┘

Type

Sender

Receiver

Blocking Send

Waits until received

Non-blocking Send

Returns immediately

Blocking Receive

Waits until message

Non-blocking Receive

Returns NULL if no message

// Semaphores: rw_mutex=1, mutex=1 // Variable: read_count=0 Reader: wait(mutex); read_count++; if (read_count == 1) wait(rw_mutex); // First reader locks signal(mutex); // READ wait(mutex); read_count--; if (read_count == 0) signal(rw_mutex); // Last reader unlocks signal(mutex); Writer: wait(rw_mutex); // WRITE signal(rw_mutex);