Process synchronization

When you run a program, the file on disk does nothing by itself — the operating system must breathe life into it as a process, manage its journey through states, and orchestrate dozens of such processes apparently simultaneously on a single CPU. Understanding how processes live, switch, communicate and compare to threads is core OS material and a GATE staple.

Definition: A process is a program in execution — an active entity with its own address space, state, registers and open resources. A program is the passive instruction file sitting on disk; the same program binary can spawn many independent processes simultaneously.

The process in memory

A running process occupies four logical regions:

Region	Contents
Text (code) segment	Machine instructions; typically read-only
Data segment	Global and static variables; two parts: initialised (BSS) and uninitialised
Heap	Dynamically allocated memory (malloc/new); grows upward
Stack	Function call frames, local variables, return addresses; grows downward

Process states — the 5-state model

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

• New: being created; resources are being allocated.
• Ready: in memory, waiting in the ready queue for CPU time.
• Running: the CPU is executing its instructions (on a single-core system, exactly one process is Running at any instant).
• Waiting (Blocked): paused, waiting for an external event (I/O completion, signal, resource availability).
• Terminated: execution complete; PCB not yet freed (zombie state until parent reads exit status).

State transitions:

• Ready → Running: scheduler dispatches the process (long-term, medium-term, short-term schedulers).
• Running → Ready: time-slice expires (preemption), or higher-priority process arrives.
• Running → Waiting: process requests I/O or waits for a resource.
• Waiting → Ready: the awaited event (e.g., I/O completion) occurs.
• Running → Terminated: process calls exit() or is killed.

Process Control Block (PCB)

Definition: The PCB (also called Task Control Block) is the kernel data structure that represents a process — the snapshot the OS needs to pause and resume it.

A PCB contains:

Field	Purpose
Process ID (PID)	Unique identifier
Process state	New / Ready / Running / Waiting / Terminated
Program counter (PC)	Address of the next instruction to execute
CPU registers	All general-purpose, index and stack pointer values
CPU scheduling info	Priority, pointers to scheduling queues
Memory management info	Page/segment tables, base and limit registers
I/O status info	List of open files, pending I/O requests
Accounting info	CPU time used, wall-clock time, process number

PCBs are stored in a process table in kernel memory and chained into ready/wait queues.

Context switch — the cost of multitasking

A context switch is the mechanism by which the CPU switches from one process to another: the OS saves the currently running process's CPU state into its PCB, then loads the saved state of the next process from its PCB.

Why it is pure overhead: While the OS is saving and loading PCBs, no user process is making progress. On a modern system running hundreds of processes, context switches happen thousands of times per second; each switch costs:

1. Saving the current PCB.
2. Loading the next PCB.
3. Flushing or selectively invalidating the TLB (Translation Lookaside Buffer) — if the new process has a different address space, cached virtual-to-physical mappings are stale.
4. Resetting pipeline and branch-predictor state on some architectures.

Typical duration: a few microseconds; on modern hardware with hardware-tagged TLBs (e.g., ARM with ASID) the TLB flush can be skipped for the same process, reducing cost.

Process creation in Unix/Linux

fork(): creates a child process that is a copy-on-write (COW) clone of the parent.

• Returns 0 in the child, child's PID in the parent, and −1 on error.
• The child inherits open file descriptors, signal handlers, environment variables, and the program counter (it continues from the instruction after fork()).
• Modern implementations use COW: both processes share the same physical pages until one writes, at which point a private copy is made — so fork is cheap even for large processes.

exec() family (execve, execl, execvp, …): replaces the calling process's memory image with a new program. It does not create a new process — the PID remains the same; only the code, data and stack change.

Typical pattern: fork() to create a child, then exec() in the child to load a new program (e.g., how a shell runs a command).

wait() / waitpid(): the parent calls wait() to block until a child terminates and to reap its exit status from the PCB.

Zombie process: a terminated child whose exit status has not yet been wait()-ed by the parent. Its PCB remains in the process table — consuming a small amount of memory — until reaped.

Orphan process: a child whose parent terminates first. Linux automatically re-parents orphans to PID 1 (init / systemd), which periodically calls wait().

Threads vs processes — why threads exist

Threads ("lightweight processes") were introduced so that related tasks within one application could share memory efficiently without the overhead of full process creation.

User-level threads (ULT): managed by a user-space threading library (e.g., POSIX pthreads in user mode, early Java green threads). Context switch is very fast; but if one ULT makes a blocking system call, the kernel blocks the entire process — all threads stall.

Kernel-level threads (KLT): the kernel knows about each thread and can schedule them independently. One thread can block on I/O while others continue. Slightly more expensive to create and switch. All modern OS (Linux, Windows, macOS) use KLT.

Threading models:

• M:1 (many-to-one): all ULTs mapped to one KLT. Fast switch; blocks whole process.
• 1:1 (one-to-one): one KLT per ULT. Most common (Linux pthreads, Windows threads). Best concurrency; small overhead per thread.
• M:N (many-to-many): M ULTs mapped to ≤ M KLTs. Flexible; complex to implement (Solaris, early Go runtime).

Inter-Process Communication (IPC)

Separate processes have separate address spaces; to exchange data, they need IPC mechanisms:

1. Shared memory (fastest): the kernel maps a common physical memory region into both processes' virtual address spaces. Data is passed by writing to this region. Requires synchronisation (mutexes, semaphores) to prevent race conditions. shmget() / shmat() in System V; mmap() with MAP_SHARED in POSIX.

2. Message passing (cleaner isolation):

• Pipes: unidirectional, anonymous; kernel buffer; typically parent-child.
• Named pipes (FIFOs): like pipes but accessible by any processes via a file-system path.
• Message queues: messages stored in the kernel; processes send/receive; allows priority ordering.
• Sockets: full-duplex; can cross machine boundaries (network sockets) or stay local (Unix domain sockets); used by browsers, databases, etc.

3. Signals: asynchronous notifications sent to a process. Examples: SIGKILL (uncatchable terminate), SIGTERM (polite terminate), SIGINT (Ctrl+C), SIGSEGV (segmentation fault), SIGCHLD (child terminated). A process installs a signal handler or leaves the default action.

4. Files: simplest form of IPC; persistent; used for logging and configuration sharing.

Synchronisation issues (overview)

When multiple processes or threads access shared data without coordination:

• Race condition: the outcome depends on the exact interleaving of instructions — non-deterministic, hard to debug.
• Critical section: the code region accessing shared data; must have mutual exclusion (only one thread at a time), progress (not blocked when no one is in), and bounded waiting (not starved forever).
• Solutions: mutexes, semaphores, monitors, condition variables — detailed in the OS Synchronisation lesson.

Key scheduling metrics (GATE numericals)

• Turnaround time = completion time − arrival time.
• Waiting time = turnaround time − burst (CPU) time.
• Response time = first time on CPU − arrival time.
• CPU utilisation = useful CPU time / total time × 100%.
• Throughput = number of processes completed per unit time.

Worked example

Question: Three processes: P1 (arrival 0, burst 5), P2 (arrival 1, burst 3), P3 (arrival 2, burst 2). FCFS scheduling. Find average waiting time.

Solution:

Step 1: FCFS order of execution: P1 at time 0–5, P2 at 5–8, P3 at 8–10.

Step 2: Waiting times — P1: 0 − 0 = 0; P2: 5 − 1 = 4; P3: 8 − 2 = 6.

Step 3: Average waiting time = (0 + 4 + 6) / 3 = 10/3 ≈ 3.33 ms.

Conclusion: Under FCFS the average wait is 3.33 ms; SJF would serve P3 first after P1, reducing this — illustrating why scheduling algorithm choice matters.

Why it matters: These concepts explain how a single CPU appears to run dozens of applications simultaneously, why a crashed browser tab can (or cannot) take down others, and how scheduling metrics are computed for GATE numerical questions.

Real-world example: Open several browser tabs — Chrome deliberately runs each tab as a separate process (with shared code libraries, but separate heaps/stacks). When a tab crashes, it is isolated: the main browser process reparents it, shows an error page, and other tabs continue. Within a single tab, multiple threads share memory to render HTML, run JavaScript, handle network requests and manage the UI simultaneously — exactly the threads-within-process model this lesson describes.

Common misconception: Many students believe fork() returns the same value to both parent and child. It does not — fork() returns 0 to the child and the child's PID to the parent (−1 on any error). This asymmetric return value is the standard Unix idiom for a single function that creates two execution paths, and it is a direct GATE question.

Cover the answer, recall, then check. 12 cards on synchronization fundamentals for GATE OS.

Q1. What is a race condition?
A1. When two or more processes access shared data concurrently and the final result depends on the order of execution (interleaving). Prevented by ensuring mutually exclusive access to the critical section.

Q2. State the three requirements a valid critical-section solution must satisfy.
A2. (1) Mutual Exclusion — at most one process in the CS. (2) Progress — if no process is in the CS, selection of the next entrant cannot be postponed indefinitely by processes not wanting to enter. (3) Bounded Waiting — a bound exists on how many times others enter after a process requests entry.

Q3. Why does simply disabling interrupts fail as a general CS solution?
A3. It works on a uniprocessor but not on multiprocessors (other CPUs still run), and disabling interrupts system-wide is unsafe/inefficient. So it is not a general software solution.

Q4. Peterson's solution — what two shared variables does it use and for how many processes?
A4. For 2 processes: a boolean array flag[2] (intent) and an int turn. Entry: flag[i]=true; turn=j; wait while (flag[j] && turn==j). It satisfies all three requirements assuming atomic loads/stores.

Q5. Does Peterson's solution work on modern hardware with instruction reordering?
A5. Not reliably — out-of-order/relaxed memory models can break it without memory barriers. It is correct only under sequential consistency, which is why hardware atomics are used in practice.

Q6. What does the TestAndSet (TSL) instruction do, and why is it useful?
A6. Atomically returns the old value of a lock and sets it to true. Atomicity lets it implement mutual exclusion (spin-lock) that ordinary loads/stores cannot guarantee.

Q7. Give the Swap/Exchange-based lock idea.
A7. key=true; do { Swap(&lock,&key); } while(key==true); critical section; lock=false. Swap atomically exchanges two variables; the process that reads lock as false enters.

Q8. Do TestAndSet / Swap spinlocks guarantee bounded waiting by themselves?
A8. No. They guarantee mutual exclusion and progress but not bounded waiting; extra bookkeeping (e.g., a waiting[] array and round-robin handoff) is needed for bounded waiting.

Q9. Busy waiting (spinlock) — cost and when acceptable?
A9. It wastes CPU cycles polling. Acceptable when the expected wait is shorter than the cost of blocking/context-switching (short critical sections, multiprocessors).

Q10. What is priority inversion?
A10. A high-priority process waits on a lock held by a low-priority process, which itself is preempted by medium-priority processes. Fix: priority inheritance (holder temporarily inherits the waiter's priority).

Q11. Difference between deadlock and starvation in synchronization?
A11. Deadlock: a set of processes are all blocked, each waiting for a resource held by another (no progress ever). Starvation: a process waits indefinitely though the system as a whole progresses.

Q12. Why must the entry/exit protocol operations be atomic?
A12. If checking and setting the lock are not atomic, two processes can both observe the lock free and both enter the CS — the exact race condition synchronization aims to prevent.

Process synchronization coordinates concurrent processes that share data so that outcomes stay correct regardless of interleaving. GATE tests this both conceptually (requirements, hardware primitives) and via reasoning about whether a given code snippet satisfies mutual exclusion.

The critical-section problem

Each process has an entry section, critical section (CS), exit section and remainder. A correct solution must meet three requirements:

Requirement	Meaning
Mutual Exclusion	At most one process in the CS at any time
Progress	Only processes wanting entry decide who enters; decision cannot be postponed indefinitely
Bounded Waiting	A finite bound on how many others enter after a process requests

Software and hardware solutions

Peterson's solution (2 processes) uses flag[2] and turn; it meets all three requirements only under a sequentially consistent memory model. Hardware primitives — TestAndSet and Swap/Exchange — provide the atomic read-modify-write that plain loads/stores lack, and are used to build spinlocks. Note: raw TSL/Swap locks guarantee mutual exclusion and progress but not bounded waiting.

Exam Tricks & Tips

• 🎯 Memorise the three requirements verbatim — many MCQs ask which requirement a given snippet violates; bounded waiting is the most commonly failed one.
• 🎯 TestAndSet and Swap by themselves do NOT ensure bounded waiting — a favourite trap; extra waiting[] bookkeeping is required.
• 🎯 Peterson needs atomic, ordered memory access — on relaxed memory models it can break; disabling interrupts only works on uniprocessors.
• 🎯 Race condition ⇒ result depends on interleaving. If a question shows two threads incrementing a shared counter, the "lost update" is the classic race.
• 🎯 Priority inversion is fixed by priority inheritance — a one-line high-yield fact.
• ❌ Common mistake: assuming mutual exclusion implies deadlock-freedom or bounded waiting — the three properties are independent; a solution can give ME yet starve a process.

Expected exam pattern

1–2 mark MCQs: identify which of the three requirements a code fragment fails; state what an atomic instruction guarantees; distinguish deadlock vs starvation; or reason about Peterson-style two-process logic.

Quick recap

Race conditions arise from unsynchronised shared access. A valid CS solution needs mutual exclusion, progress and bounded waiting. Peterson (software) works under sequential consistency; TestAndSet/Swap (hardware) give atomicity but not bounded waiting on their own. Know the deadlock-vs-starvation and priority-inversion facts.

Worked Example

Problem: A counting semaphore S is initialized to 3 (three identical resource units). Processes issue the operation sequence: wait, wait, wait, wait, wait, signal, signal. Track the value of S and the number of blocked processes after the waits and after the signals.

Solution:
Recall the semaphore operations:
wait(S): S = S − 1; if S < 0 the calling process blocks.
signal(S): S = S + 1; if S ≤ 0 one blocked process is woken.
A negative value of S indicates that |S| processes are blocked waiting.

Start S = 3. Apply the five wait operations:
after 1st wait: S = 2 (acquired)
2nd: S = 1, 3rd: S = 0 (three units all in use)
4th wait: S = −1 → 1 process blocked
5th wait: S = −2 → 2 processes blocked.
So after five waits, S = −2 and 2 processes are blocked.

Now apply the two signal operations:
1st signal: S = −1 → wakes one blocked process (1 still blocked)
2nd signal: S = 0 → wakes the other (0 blocked).
After the signals, S = 0 and no processes are blocked.

Answer: After the five waits, S = −2 with 2 blocked processes; after the two signals, S = 0 with 0 blocked.