Process Management: States, Control, Synchronization & Deadlocks

TAKEAWAYS:

• A process is an executing program with its own PCB (Process Control Block) tracking state, registers, and resources.
• Processes cycle through five states (new → ready → running → waiting → terminated) managed by the OS scheduler.
• Race conditions and critical sections require synchronization (semaphores, monitors) to avoid corruption.
• Deadlocks occur when four conditions (mutual exclusion, hold-and-wait, no preemption, circular wait) align; prevention or detection algorithms (e.g., Banker’s) resolve them.
• IPC mechanisms (shared memory, message passing) enable processes to communicate safely.
• Process creation (fork, exec) and termination (exit, abort) are core OS functions with parent-child relationships.

1. What is a Process?

A process is a program in execution, with its own:

• Program counter (PC): Tracks next instruction.
• Registers: CPU state (e.g., R1, SP).
• Memory space: Code, data, stack, heap.
• I/O resources: Files, devices.

Process vs. Program

2. Process States and Transitions

Processes transition between five states:

1. New: Process created (e.g., fork() in Linux).
2. Ready: Waiting for CPU (in ready queue).
3. Running: Executing on CPU.
4. Waiting/Blocked: Awaiting I/O or event (e.g., read() from disk).
5. Terminated: Execution complete (exit code stored in PCB).

stateDiagram-v2
    [*] --> New: Process Creation
    New --> Ready: Admitted to Ready Queue
    Ready --> Running: CPU Allocation
    Running --> Waiting: I/O Request
    Waiting --> Ready: I/O Complete
    Running --> Ready: Time Slice Expires
    Running --> Terminated: Exit/Abort
    Terminated --> [*]

Real-World Example: eSewa Payment Process When you pay a bill via eSewa:

1. New: Your payment request is created.
2. Ready: Waits in the bank’s transaction queue.
3. Running: Bank processes the deduction.
4. Waiting: Awaits SMS confirmation from Ncell/NTC.
5. Terminated: Payment completes (or fails).

3. Process Control Block (PCB)

The PCB is the process descriptor stored in memory. Key fields:

• Process ID (PID): Unique identifier (e.g., P1, P2).
• Process State: Current state (ready/running/waiting).
• Program Counter (PC): Next instruction address.
• CPU Registers: Saved state when process is preempted.
• CPU Scheduling Info: Priority, remaining time.
• Memory Limits: Base/limit registers for memory protection.
• I/O State: Open files, device status.
• Accounting Info: CPU time used, billing.

4. Process Scheduling

The short-term scheduler (CPU scheduler) selects a process from the ready queue to run. Criteria:

1. CPU Utilization: Keep CPU busy (e.g., 90%).
2. Throughput: Processes completed per unit time.
3. Turnaround Time: Time from submission to completion.
4. Waiting Time: Time spent in ready queue.
5. Response Time: Time from request to first response.

Worked Example: FCFS Scheduling Given processes with arrival time (AT) and burst time (BT):

Gantt Chart:

P1 (0-6) | P2 (6-10) | P3 (10-13)

• Turnaround Time (TAT) = Completion Time – Arrival Time
  • P1: 6 – 0 = 6
  • P2: 10 – 2 = 8
  • P3: 13 – 4 = 9
• Average TAT = (6 + 8 + 9) / 3 = 7.67
• Waiting Time (WT) = TAT – BT
  • P1: 6 – 6 = 0
  • P2: 8 – 4 = 4
  • P3: 9 – 3 = 6
• Average WT = (0 + 4 + 6) / 3 = 3.33

Exam Tip: Always draw the Gantt chart for scheduling questions!

5. Inter-Process Communication (IPC)

Processes communicate via:

1. Shared Memory: Fast, but requires synchronization (e.g., two processes reading/writing a shared buffer).
2. Message Passing: Slower but safer (e.g., send()/receive() in Linux).
   • Direct: Sender knows receiver’s PID.
   • Indirect: Uses a mailbox (e.g., WhatsApp messages via servers).

Real-World Example: Pathao Driver-Passenger Matching

• Shared Memory: Not used (security risk).
• Message Passing:
  1. Passenger sends request to Pathao server (message: "Need ride from X to Y").
  2. Server matches with nearest driver (message: "Driver D1 assigned").
  3. Driver accepts (message: "Accepted"), and both get real-time updates.

6. Synchronization: Race Conditions and Critical Sections

Problem: Two processes accessing shared data concurrently can corrupt it. Example: Two bank tellers updating the same account balance:

// Process P1
balance = balance - 100;  // Read, subtract, write
// Process P2
balance = balance - 200;  // Overwrites P1's changes!

Solution: Critical Section Problem requires:

1. Mutual Exclusion: Only one process in CS at a time.
2. Progress: No process waits indefinitely.
3. Bounded Waiting: No starvation.

Tools for Synchronization:

Worked Example: Dining Philosophers (Semaphore Solution)

stateDiagram-v2
    [*] --> Thinking: Philosopher thinks
    Thinking --> Hungry: Picks up fork
    Hungry --> Wait: Tests semaphore
    Wait --> Eat: If fork available
    Eat --> PutDown: Releases fork
    PutDown --> Thinking

Real-World Example: Kathmandu Traffic Lights

• Race Condition: Two cars at an intersection without synchronization → collision.
• Solution: Traffic lights act as semaphores:
  • semaphore = 0 (red light): No cars allowed.
  • semaphore = 1 (green light): One direction proceeds.

7. Deadlocks: Conditions and Prevention

A deadlock occurs when processes are blocked forever, waiting for resources held by each other.

Four Necessary Conditions:

1. Mutual Exclusion: Only one process can use a resource at a time (e.g., printer).
2. Hold and Wait: Process holds a resource while waiting for another.
3. No Preemption: Resources cannot be forcibly taken (e.g., CPU time slices can be preempted, but a printer job cannot).
4. Circular Wait: A circular chain of processes waiting for each other (e.g., P1 → R1 → P2 → R2 → P1).

Example Scenario:

Graph Representation:

graph TD
    P1["P1"] -->|"Holds"| R1["R1"]
    P1 -->|"Waits"| R2["R2"]
    P2["P2"] -->|"Holds"| R2
    P2 -->|"Waits"| R1

Prevention Strategies:

Banker’s Algorithm Worked Example: Given:

• Available: [1, 0, 2]
• Max Need:

  Process	A	B	C
  P0	7	5	3
  P1	3	2	2
  P2	9	0	2
  P3	2	2	2

• Allocation:

  Process	A	B	C
  P0	0	1	2
  P1	1	0	0
  P2	1	0	2
  P3	0	1	0

Step 1: Calculate Need = Max – Allocation. Step 2: Check if Available ≥ Need[P0]? No → Skip P0. Step 3: P1’s Need = [2, 2, 2] ≤ Available? No. Step 4: P3’s Need = [2, 1, 2] ≤ Available? No. Step 5: P2’s Need = [8, 0, 0] ≤ Available? No. Conclusion: No safe sequence → Deadlock possible.

8. Process Creation and Termination

Process Creation:

• Parent Process: Creates child via fork() (copy of parent) or exec() (load new program).
• Child Process: Inherits parent’s resources (e.g., file descriptors) unless modified.

Example:

# Parent (PID 1234) creates child
fork();  // Child gets PID 5678
exec("ls");  // Child replaces itself with 'ls' command

Termination:

• Normal Exit: Process calls exit() (returns status to parent).
• Abnormal Exit: Killed by kill() or OS (e.g., segmentation fault).
• Zombie Process: Terminated but not reaped by parent (use wait() to clean up).

Real-World Example: WhatsApp Message Delivery

1. Parent: Your phone (PID 1000).
2. Child: Message delivery process (PID 1001) created when you send a message.
   • If delivery fails (e.g., no internet), child terminates abnormally.
   • Parent (WhatsApp app) reaps the child to free resources.

In the Real World

1. eSewa Payments

   • Process States: Your payment request moves from New (created) → Ready (queued) → Running (processing) → Terminated (completed or failed).
   • Synchronization: Bank uses semaphores to ensure only one transaction modifies your account at a time.
   • Deadlock Prevention: If eSewa hangs, it uses timeouts to cancel pending transactions.

2. Pathao Ride Allocation

   • IPC: Driver and passenger processes communicate via message passing (server acts as mailbox).
   • Scheduling: Pathao’s algorithm (like SJF) assigns the nearest available driver to minimize waiting time.

3. NTC Electricity Billing System

   • Processes: Meter reading → Billing → Payment processing.
   • Deadlock Risk: If two processes lock the same customer record, the system uses resource ordering (e.g., always lock by customer ID ascending).

Exam Tip

1. Process States: Always draw the state transition diagram (5 states + arrows). Examiners love this!
2. Scheduling: For Gantt charts, label time intervals clearly and calculate TAT/WT step-by-step.
3. Deadlocks:
   • Define the 4 conditions and give an example (e.g., two processes waiting for each other’s printers).
   • For Banker’s Algorithm, show the Need matrix and explain why a sequence is safe/unsafe.
4. Synchronization:
   • For race conditions, write a code snippet showing the problem (e.g., two processes incrementing a counter).
   • For semaphores, describe wait() and signal() and give a real-world analogy (e.g., traffic lights).
5. IPC: Compare shared memory vs. message passing in a table (speed vs. safety).

Common Pitfalls:

• Forgetting to include arrival times in scheduling questions.
• Not checking all processes in Banker’s Algorithm (missing one can lead to wrong conclusions).
• Drawing a deadlock graph incorrectly (e.g., missing arrows for "waiting for").