Part 2: Processes, Scheduling & Synchronization

1. The Critical Section Problem

When multiple processes/threads access shared data (like a bank balance or a global variable), the final outcome depends on the order of execution. This is a Race Condition.

• The Three Requirements for a Solution:

1. Mutual Exclusion: If process $P_1$ is executing in its critical section, no other process can be in its critical section.
2. Progress: If no process is in its critical section and some processes want to enter, only those not in their remainder section can participate in the decision, and this decision cannot be postponed indefinitely.
3. Bounded Waiting: There must be a limit on the number of times other processes are allowed to enter their critical sections after a process has made a request.

2. Mutex vs. Semaphore vs. Monitor vs. Spinlock

While these are all synchronization tools, they serve different design purposes:

• Mutex (Mutual Exclusion Object):

• Mechanism: Acts as a lock. A process must acquire the lock to enter the critical section and release it upon exiting.

• Key Property: Ownership. Only the process that locked the mutex can unlock it.

• Semaphore:

• Mechanism: Acts as a signaling mechanism using an integer variable (the “counter”). It supports two atomic operations: wait() (or $P$) and signal() (or $V$).

• Binary Semaphore: Functions similarly to a mutex (0 or 1).

• Counting Semaphore: The integer can range over an unrestricted domain. Used for Resource Pooling—if you have 5 printers, a counting semaphore initialized to 5 allows 5 processes to access printers simultaneously; the 6th process will be blocked.

• Mutex vs. Binary Semaphore (the interview difference): a mutex enforces ownership (only the locker can unlock — good for locking a resource); a binary semaphore is a signal and can be signaled by any thread (good for producer/consumer-style wakeups). Many interviewers accept “they’re basically the same for mutual exclusion” but credit the ownership distinction.

• Monitor: a high-level construct bundling shared variables, the operations on them, and mutual exclusion together — the compiler enforces that only one thread is inside at a time, using a condition variable (wait/signal) for blocking. Deadlock-free, easier to reason about than raw semaphores.

• Spinlock: busy-waits (loops) instead of sleeping. Best on multi-core for very short critical sections (no context-switch cost); wasteful on single-core and for long sections because it burns CPU while waiting.

3. The Deadlock Problem

A deadlock occurs when a set of processes are in a blocked state because each process is holding a resource and waiting for another resource held by another process in the set.

The Four Necessary Conditions (Coffman Conditions)

If all four exist, a deadlock occurs:

1. Mutual Exclusion: At least one resource must be held in non-sharable mode.
2. Hold and Wait: A process is holding at least one resource and waiting to acquire additional resources held by others.
3. No Preemption: Resources cannot be forcibly taken from a process; they must be released voluntarily.
4. Circular Wait: A set $\{P_0, P_1, ..., P_n\}$ exists such that $P_0$ waits for $P_1$, $P_1$ waits for $P_2$, …, and $P_n$ waits for $P_0$.

How to handle it:

• Prevention: Design the system to break one of the four conditions (e.g., force processes to request all resources at once — breaks Hold-and-Wait; order all resources — breaks Circular Wait).
• Avoidance (Banker’s Algorithm): The OS tracks the state of all resources and only grants a request if it leaves the system in a Safe State (where it is guaranteed that all processes can finish).
• Detection & Recovery: Let the deadlock happen, detect it via a Resource Allocation Graph (RAG) — a cycle in the RAG means deadlock (if each resource type has one instance) — and recover by killing processes or preempting resources.
• Ostrich Algorithm: ignore it (used by most desktop OSes because deadlocks are rare and recovery is costly).

4. CPU Scheduling: Concepts & Algorithms

The goal is to maximize throughput and minimize latency.

• Schedulers:

• Long-term: decides which jobs enter the ready queue (controls multiprogramming degree).

• Short-term (dispatcher): picks the next ready process to run — invoked very frequently.

• Medium-term: swaps processes in/out to manage memory.

• Preemptive vs. Non-Preemptive:

• Preemptive: The OS can interrupt a process (e.g., Round Robin, Shortest Remaining Time First). Necessary for responsive systems.

• Non-Preemptive: Once a process gets the CPU, it keeps it until it finishes or performs I/O (e.g., FCFS, SJF).

• Key Metrics:

• Turnaround Time: Completion time minus arrival time.

• Waiting Time: Total time spent in the “Ready” queue.

• Response Time: Time from submission until the first response (crucial for user-facing systems).

Common Algorithms

Algorithm	Type	Strength	Weakness
FCFS	Non-Preemptive	Simple to implement.	Convoy Effect: Long processes delay short ones.
SJF	Non-Preemptive	Optimal average waiting time.	Hard to predict future CPU burst times.
SRTF	Preemptive	Optimal average waiting time (SJF’s preemptive version).	Starvation of long processes; burst prediction needed.
Round Robin	Preemptive	Fair; great for time-sharing.	Performance depends heavily on the Time Quantum.
Priority	Both	Important tasks go first.	Starvation: Low-priority tasks may never run (fix: aging).
MLQ / MLFQ	Preemptive	Multiple queues by priority; MLFQ boosts aging tasks.	Complex to tune.

• Priority inversion: a low-priority process holds a lock a high-priority process needs, so a medium-priority process runs while high waits. Solved via priority inheritance.

5. Worked Example — FCFS / SJF / Round Robin

Given: P1 (burst 5), P2 (burst 3), P3 (burst 8), all arriving at time 0.

FCFS (order P1 → P2 → P3):

Gantt: |  P1  |  P2  |      P3      |
       0      5      8             16

• P1: TAT 5, wait 0 · P2: TAT 8, wait 5 · P3: TAT 16, wait 8
• Average TAT = (5+8+16)/3 = 9.67 · Average wait = (0+5+8)/3 = 4.33

SJF (order P2 → P1 → P3):

Gantt: |  P2  |  P1  |      P3      |
       0      3      8             16

• P2: TAT 3 · P1: TAT 8 · P3: TAT 16
• Average TAT = (3+8+16)/3 = 9 · Average wait = (0+3+8)/3 = 3.67 (better than FCFS — SJF minimizes waiting)

Round Robin (quantum = 3):

Gantt: | P1 | P2 | P3 | P1 | P3 |
       0   3    6    9   12   16

• P1: completes at 12 · P2: completes at 6 · P3: completes at 16
• Average TAT = (12+6+16)/3 = 11.33 · Average wait = (7+3+8)/3 = 6
• TAT is worse than SJF, but response time is best — every process responds by time 3.

Method (applies to any algorithm): draw the Gantt chart → TAT = completion − arrival → waiting = TAT − burst → average.

6. IPC — Inter-Process Communication

Ways processes exchange data:

• Shared Memory: processes map the same physical region into their address spaces and read/write directly. Fastest (no kernel involvement after setup) but the OS must coordinate access (often via a semaphore) to avoid races.

• Message Passing: processes exchange messages through the kernel (send/receive).

• Synchronous (blocking): both must rendezvous — like a phone call.

• Asynchronous (non-blocking): sender continues immediately — like email.

• Pipes: a unidirectional byte stream; pipe() in Linux. A pipe connecting a parent and its child is the classic “filter” pattern (e.g., ls | grep foo).

• Others: message queues, sockets (network + local), signals (asynchronous notifications).

• Rule of thumb: shared memory = fastest but error-prone; message passing = safer, slower. Interview favorite: “which IPC is fastest?” → shared memory.

7. Multithreading Models

How user threads map onto kernel threads:

• Many-to-One: many user threads → one kernel thread. Cheap, portable, but one blocking call blocks the whole process and no parallelism.
• One-to-One: each user thread → its own kernel thread. True parallelism and a blocked thread doesn’t block others; costly (thread-per-thread).
• Many-to-Many: many user threads multiplexed onto several kernel threads. Combines parallelism with lower overhead; complex to implement.

8. Worked Example — Banker’s Algorithm (Safe State)

Given: 3 processes, 3 resource types, total instances A=3, B=3, C=2:

Process	Allocation (A B C)	Max (A B C)
P0	1 0 0	2 1 1
P1	0 1 0	1 2 1
P2	0 0 1	1 1 2

• Available = Total − ΣAllocation = (3,3,2) − (1,1,1) = (2,2,1)
• Need = Max − Allocation: P0 (1,1,1), P1 (1,1,1), P2 (1,1,1)

Run the safety check:

1. P0’s need (1,1,1) ≤ (2,2,1) ✔ → P0 runs, frees (1,0,0) → Available (3,2,1).
2. P1’s need (1,1,1) ≤ (3,2,1) ✔ → frees (0,1,0) → Available (3,3,1).
3. P2’s need (1,1,1) ≤ (3,3,1) ✔ → done.

Result: a safe sequence <P0, P1, P2> exists → the initial state is SAFE. If no process can run (all needs > available), the state is unsafe — deadlock is possible, so the Banker’s Algorithm denies the request that would create it.

• Key distinction: safe ≠ deadlock-free — an unsafe state may lead to deadlock; the Banker’s Algorithm refuses to enter unsafe states proactively (avoidance).