Process Synchronization

CSS Optional — Paper-II, Section-A · P-II.III.III

1. Race Condition

A race condition occurs when two or more processes/threads access and manipulate shared data concurrently, and the final outcome depends on the unpredictable order in which their instructions happen to be interleaved by the scheduler — producing incorrect or inconsistent results.

Classic example: two processes both executing counter = counter + 1 can, if interleaved at the machine-instruction level, both read the same old value and each write back the same incremented value — one increment is silently lost.

2. The Critical-Section Problem

The segment of code where a process accesses shared data is its critical section. Any valid solution must satisfy three requirements:

1. Mutual Exclusion — no two processes may execute in their critical sections simultaneously.
2. Progress — if no process is in its critical section, a process wishing to enter must not be indefinitely delayed by processes not currently interested in entering.
3. Bounded Waiting — there must be a limit on how many times other processes are allowed to enter their critical section after a process has requested entry, before that request is granted (prevents starvation).

3. Solutions, from weakest to strongest

Semaphores in detail: a semaphore S is an integer manipulated only through two atomic operations — wait(S) (a.k.a. P): decrement S, block if S < 0; and signal(S) (a.k.a. V): increment S, wake a waiting process if any. A binary semaphore (0 or 1) gives plain mutual exclusion (equivalent to a mutex); a counting semaphore tracks how many units of a resource are available (used for producer-consumer below). If a semaphore's value is negative, its magnitude equals the number of processes currently blocked waiting on it — a frequently tested MCQ fact.

4. Classic Synchronization Problem: Producer-Consumer (Bounded Buffer)

A producer generates items into a fixed-size shared buffer; a consumer removes them. Without synchronization: the producer could overwrite an unread slot, or the consumer could read from an empty buffer — both are race conditions.

Standard solution — one mutex + two counting semaphores:

semaphore mutex = 1;   // mutual exclusion on the buffer itself
semaphore empty = N;   // N = buffer size; counts empty slots
semaphore full  = 0;   // counts filled slots

// Producer                          // Consumer
do {                                 do {
  produce an item;                     wait(full);     // wait for a filled slot
  wait(empty);   // wait for space      wait(mutex);
  wait(mutex);                         remove item from buffer;
  place item in buffer;                signal(mutex);
  signal(mutex);                       signal(empty);  // freed a slot
  signal(full);  // one more item      consume item;
} while(true);                       } while(true);

Note the order matters: the producer waits on empty (space) before mutex (exclusive access) — waiting on mutex first while the buffer is full would deadlock, since the consumer could never get mutex to free a slot.

5. Classic Synchronization Problem: Readers-Writers

Multiple processes share a data store; readers only read (many can proceed concurrently with no conflict), writers modify it (a writer needs exclusive access — no reader or other writer may touch the data simultaneously).

First (Readers-Preference) solution sketch: use a counter readcount (protected by a mutex) and a semaphore wrt guarding the resource itself.

// Reader                          // Writer
wait(mutex);                       wait(wrt);
readcount++;                       ... write to shared resource ...
if (readcount == 1) wait(wrt);     signal(wrt);
signal(mutex);
... read the shared resource ...
wait(mutex);
readcount--;
if (readcount == 0) signal(wrt);
signal(mutex);

Only the FIRST reader to arrive locks out writers (wait(wrt)); subsequent readers proceed freely; only the LAST reader to leave unlocks writers. Trade-off to name in an exam answer: this version can starve writers if readers keep arriving continuously (a "second" writers-preference variant exists that instead risks starving readers — examiners often ask you to identify which starvation risk a given solution has).

6. Classic Synchronization Problem: Dining Philosophers

Five philosophers sit at a round table with one fork between each adjacent pair (5 forks total); each philosopher alternately thinks and eats, needing BOTH their left and right fork to eat.

The problem this illustrates: if every philosopher simultaneously picks up their left fork first, all five now hold one fork each and wait forever for their right fork — a deadlock (see [Deadlocks]) arising purely from synchronization, illustrating the Circular Wait Coffman condition concretely.

Standard fixes (any one is an acceptable exam answer, but name which condition it denies):

1. Allow at most 4 philosophers to sit at the table simultaneously (denies the resource-count symmetry that causes the cycle).
2. Require a philosopher to pick up both forks only if both are available simultaneously, inside a critical section (denies Hold-and-Wait).
3. Use an asymmetric rule: odd-numbered philosophers pick up their left fork first, even-numbered philosophers pick up their right fork first (denies Circular Wait by breaking the symmetric ordering).

7. Monitors — Concrete Syntax (beyond the earlier conceptual mention)

A monitor is a language construct bundling shared data + procedures that operate on it, with the compiler/runtime automatically ensuring only one process executes inside the monitor at a time. Condition variables (x.wait(), x.signal()) let a process inside the monitor voluntarily block until some condition holds — unlike semaphore wait/signal, a condition variable has no "value" to increment/decrement; signal() on a condition variable with no one waiting simply has no effect (unlike a semaphore's signal(), which always increments).

monitor BoundedBuffer {
  condition full, empty;
  int count = 0;
  procedure insert(item) {
    if (count == N) wait(full);
    ... add item ...
    count++;
    if (count == 1) signal(empty);
  }
  procedure remove() {
    if (count == 0) wait(empty);
    ... remove item ...
    count--;
    if (count == N-1) signal(full);
  }
}

---

🧮 Solved Problem — Full Producer-Consumer Question (CSS 2025, 10 marks)

Given the unsynchronized producer/consumer pseudocode:

(i) What is a race condition? — See definition above (2 marks).

(ii) Is a race condition possible here? Yes — both threads access the same shared buffer with no mutual exclusion; if their checks/updates to a shared count or index overlap, updates can be lost, the consumer could remove from an empty buffer, or the producer could overwrite an unread slot.

(iii) Add synchronization — apply the mutex + empty/full semaphore solution shown in section 4 above.

(iv) 10 user threads on 2 kernel threads, 8-core system — max threads running in parallel? Answer: 2. Only kernel threads are schedulable onto physical cores; the M:N (10:2) mapping caps this process's true parallelism at 2 regardless of free cores. (This part is really a Process-Management thread-model question bolted onto a synchronization scenario — a common CSS trick of combining two subtopics in one question.)

---

🎯 CSS Exam Angle

"Which technique is optimal?" questions (asked in 2021, 10 marks) expect you to rank the table in section 3 and justify the top choice: semaphores/monitors are optimal for real OSes because they block instead of busy-waiting (no wasted CPU cycles), and they generalize beyond plain mutual exclusion to producer-consumer-style coordination. Always name this reasoning explicitly rather than just picking "semaphore" as the answer.

📌 Past CSS Paper Frequency

⚠️ MCQ Traps

• A negative semaphore value's magnitude is the wait-queue length — not "invalid" and not "no further operations allowed" (both are common wrong distractors).
• wait(empty) must precede wait(mutex) in the producer — reversing the order is a classic exam trap that causes deadlock when the buffer is full.
• Peterson's Algorithm still busy-waits — it is a correct software solution but not an efficient one; don't call it deadlock-free-and-efficient in the same breath as semaphores.
• Monitors ≠ semaphores — a monitor automatically enforces mutual exclusion on its own procedures (the programmer cannot forget to lock), whereas a semaphore's wait/signal calls must be placed correctly by the programmer every time.
• Readers-Writers has two variants with opposite starvation risks — readers-preference (above) can starve writers; writers-preference can starve readers. Name which one a given solution is before claiming it's "fair."
• Dining Philosophers deadlocks even though every philosopher follows correct-looking local logic — it's the symmetric global pattern (all grab left first) that causes Circular Wait, not a bug in any one philosopher's code.

📜 Past-Paper Questions & MCQs (CSS 2016–2026)

2021 · Paper-II · Q4(d) · 10 marks

Q. What is a race condition? What are the different techniques to avoid race conditions in processes? Which one is optimal and why?

Ans.

• Race condition: two or more processes or threads access shared data at the same time, and the result depends on the order of execution. Example: two threads execute counter++ (load, add, store). If both load 5 before either stores, both store 6 and one update is lost.
• Techniques to avoid it (mutual exclusion in the critical section):
  • Disabling interrupts: simple, but only works on a single CPU and is unsafe for user programs.
  • Lock variables, Peterson's algorithm: software solutions, which are error-prone and busy-wait.
  • Hardware atomic instructions (test-and-set, compare-and-swap): the basis of locks.
  • Mutex locks and spinlocks: only one thread holds the lock.
  • Semaphores: counters with atomic wait() and signal(). Binary semaphores are mutexes, and counting semaphores control pools of resources.
  • Monitors: a language construct that gives automatic mutual exclusion with condition variables.
• Optimal choice: semaphores or mutexes (and monitors in high-level languages). They are built on hardware atomic operations, work on multiprocessors, and block the waiting process instead of wasting CPU in busy waiting. Spinlocks are better only for very short critical sections.

2022 · Paper-II · Q2(c) · 4 marks

Q. What design and management issues are raised by the existence of concurrency?

Ans.

• Communication among processes (IPC) must be provided.
• Sharing and competing for resources: the OS must allocate and protect memory, files and devices.
• Synchronisation: activities must be coordinated, which needs mutual exclusion in critical sections and correct ordering.
• Allocation of processor time among active processes (scheduling).
• Problems to prevent: race conditions, deadlock and starvation.
• Also: protecting each process's data from others, and recovering from failure.

2025 · Paper-II · Q5(a) · 10 marks

Q. Consider the producer and consumer pseudo-code (producer: produce an item, place it in the buffer; consumer: remove an item from the buffer, consume it; both loop forever). (i) What is a race condition? (ii) Can a race condition occur if the two threads execute simultaneously? (iii) Add the necessary synchronisation. (iv) A process spawns 10 user-level threads mapped onto 2 kernel threads on an 8-core system. What is the maximum number of the process's threads that can execute in parallel?

Ans.

• (i) Race condition: the outcome depends on the unpredictable order in which threads access shared data.
• (ii) Yes. Both threads read and update the shared buffer (and its item counter or indexes) with no protection. If the consumer removes an item while the producer is adding one, items can be lost or the counter corrupted. The producer can also overwrite a full buffer, and the consumer can read from an empty one.
• (iii) Synchronisation with semaphores (mutex = 1, empty = N, full = 0):

producer:                      consumer:
  do {                           do {
    produce item                   wait(full)       // wait for an item
    wait(empty)   // free slot     wait(mutex)      // lock buffer
    wait(mutex)   // lock buffer   remove item from buffer
    place item in buffer           signal(mutex)
    signal(mutex)                  signal(empty)    // slot is free
    signal(full)  // item ready     consume item
  } while (true)                 } while (true)

• (iv) Answer: 2. User-level threads are scheduled onto kernel threads, and only kernel threads run on cores. With 2 kernel threads at most 2 of the process's threads run in parallel, even though 8 cores exist.

MCQs

2025 P-II · Q11. Process synchronisation can be done on:

• (A) Hardware level
• (B) Software level
• (C) Both (A) and (B) ✅
• (D) None of these
• Answer: (C).
• Why: hardware gives atomic instructions (test-and-set, compare-and-swap), and software builds on them with mutexes, semaphores and monitors. So both levels are used.

2025 P-II · Q13. If the semaphore value is negative:

• (A) Its magnitude is the number of processes waiting on that semaphore ✅
• (B) It is invalid
• (C) No operation can be further performed on it until a signal operation is performed on it
• (D) None of these
• Answer: (A).
• Why: in the classic counting-semaphore implementation, wait() decrements the value. A negative value means that |value| processes are blocked in the semaphore's queue. A signal() wakes one of them. The state is valid, and operations can continue.