Process Synchronization Questions in GATE CSE: Method and Traps

A synchronization question prints ten to fifteen lines of concurrent code and asks which properties hold. You cannot answer it by reading the code the way you read a program that runs once. The answer lives in an interleaving the listing does not show, and the setter picked that listing because one specific interleaving breaks something. The whole skill is finding that interleaving quickly.

Key takeaways

• A property is a claim about every possible interleaving. To break one you need a single bad schedule; to establish one you need an argument that covers all schedules.
• A plain increment is three machine steps: load, add, store. Every counter question is built on splitting those three.
• Mutual exclusion, progress and bounded waiting are independent. Check them one at a time, in that order.
• The order of the two wait calls in producer-consumer decides whether it deadlocks. The order of the two signal calls does not.
• With the standard semantics, a negative semaphore value is the count of processes blocked on it.

Where synchronization sits in the paper

The official 2027 syllabus text for Section 8 reads: system calls, processes, threads, inter-process communication, concurrency and synchronization, deadlock, CPU and I/O scheduling, memory management and virtual memory, file systems. Concurrency and synchronization is named directly, and it is unchanged from 2026.

Third-party analyst compilations place Operating Systems between 6 and 16 marks per paper across 2009 to 2026, with an average near 8.8. The 2009 figure of 16 comes from a 100-mark paper with no General Aptitude section, so it is not a trend. Splitting the series, 2009 to 2017 averages about 9.3 and 2018 to 2026 about 8.3, a mild decline. One analyst counted five Operating Systems questions in the 2026 shift-2 paper. These numbers are unofficial, and sources disagree by two or three marks because borderline questions get classified differently.

Inside the subject, the code-property question is one of the most reliable items there is: some form of it appears in essentially every paper. The full subject ranking sits in the Operating Systems important topics guide. The number of questions of each type and the marking scheme are fixed by the official notification, so check the current one rather than an old coaching PDF.

A counter is three instructions, not one

Write the increment the way the machine sees it:

LOAD  R, x
ADD   R, 1
STORE x, R

Between any two of those lines the scheduler can switch. That is the entire mechanism behind every "possible final values" question.

Take $n$ processes, each executing that increment $k$ times, with $x$ starting at $0$.

The maximum is $nk$. Run the processes one after another with no overlap and every increment sees the previous one.

The minimum is 2 whenever $k \ge 2$ and $n \ge 2$, not 1. Here is the argument, and it is worth memorising because the trap is the off-by-one. A store always writes a register value of at least 1, so from the first store onwards $x$ can never be 0 again. For the final value to be 1, the process that performs the last store must have read 0 during its own final increment. Reading 0 means no store had happened yet anywhere, including that process's own earlier increments, which contradicts $k \ge 2$. So 1 is unreachable and 2 is the floor.

Construct it for $n = 2$, $k = 2$ to see the shape: both processes load 0, the first finishes both of its increments while the second sits on a stale register, then the second stores 1 over everything, reloads, and the pair finish at 2. If each process increments exactly once, the minimum is 1 instead, because there are no earlier stores to contradict. Read the value of $k$ before answering.

The three requirements, checked separately

A correct solution must satisfy all three. Most flawed textbook attempts satisfy two, and the question asks which one is missing.

• Mutual exclusion. At most one process is inside the critical section at any instant.
• Progress. If no process is in the critical section and some processes want in, only those processes participate in choosing who goes next, and that choice cannot be postponed forever. A process sitting in its remainder section must not be able to block others.
• Bounded waiting. After a process requests entry, there is a finite bound on how many times others may enter before it does.

Two distinctions carry marks. First, progress is not the same as deadlock-freedom: strict alternation never deadlocks, yet it fails progress because an uninterested process holding the turn locks the other one out. Second, a test-and-set lock is perfectly safe but unfair, and a process can be overtaken any number of times, which is exactly where bounded waiting dies. Peterson's variants are built by moving one line, usually the flag assignment past the turn assignment, and the answer changes to "mutual exclusion fails".

Semaphores and what a negative value means

A binary semaphore takes only 0 and 1 and is used as a lock. A counting semaphore starts at any non-negative integer and represents available units of a resource.

Under the usual definition, wait decrements first and blocks the caller if the value has gone negative; signal increments and wakes one blocked process if the value is still at most 0. Two consequences get examined directly:

• After $m$ waits and $p$ signals on a semaphore initialised to $s$, the value is $s - m + p$.
• If that value is negative, its magnitude is the number of processes blocked on the semaphore. A value of $-4$ means four processes are queued.

Some books clamp the value at 0 and keep the queue separately. The two conventions give different numeric answers, so read the question's definition before computing anything. Ordering questions exploit the same machinery: a semaphore initialised to 0 is a one-shot permission slip that forces statement B to run after statement A.

Producer-consumer: which ordering kills it

The standard bounded buffer of size $N$ uses empty = N, full = 0, mutex = 1. The producer's entry looks like this:

wait(empty); wait(mutex);
  deposit item
signal(mutex); signal(full);

Swap the first two lines and the solution deadlocks. A producer takes the mutex, finds the buffer full, blocks on empty while still holding the mutex, and no consumer can get in to free a slot. The mirror bug on the consumer side deadlocks on an empty buffer. The rule is one line long: acquire the counting semaphore first, the mutex second. Reversing the two signals only delays a wakeup and is harmless, which is the option most candidates tick by mistake.

Readers-writers and who starves

In the readers-preference solution, readcount is guarded by its own mutex, the first reader performs wait on the writer semaphore and the last reader signals it. Mutual exclusion between a writer and everyone else holds, but a steady stream of readers keeps the writer semaphore permanently held and the writer starves. The writers-preference variant flips the problem and readers starve. Only the third variant, which forces everyone through a queue semaphore, is starvation-free. Questions ask which of the three suffers which starvation, and whether removing the mutex around readcount breaks correctness. It does: the increment is non-atomic, so two readers can both think they are first or both think they are last.

The procedure to run in the exam

1. List the shared state and its initial values: semaphores, flags, turn, counters. Write them at the top of your rough sheet.
2. Mark what is atomic. Each wait and signal is atomic. Every plain assignment, comparison and increment is not.
3. Build the worst case, not the average case. Freeze each process just before a store or just after a load, then resume them in the order that does the most damage. An average interleaving proves nothing.
4. Check the three requirements in order, and check each against its own definition rather than your memory of a similar problem.
5. Ask what happens at the boundaries: buffer exactly full, buffer exactly empty, both processes requesting at the same instant, one process never leaving its remainder section.

These items are increasingly set as multiple-select. There is no partial credit, so every option has to be decided on its own evidence. Tick an option only when you can name the interleaving that proves it or the argument that rules it out; a guessed tick loses the whole question rather than part of it. That discipline is covered further in the guide to MSQ, NAT and MCQ strategy.

How to practise

Build one page of skeletons: strict alternation, the two flag variants, Peterson's, a test-and-set lock, the bounded buffer, and readers-preference. For each one, write the single interleaving that breaks it, in load and store steps, not in prose. Once those six are in your hand you will recognise almost any printed listing as a mutation of one of them, and the mutation is the answer.

Then rehearse the counter argument with different values of $n$ and $k$ until the minimum of 2 stops feeling surprising. The error list that this topic shares with the rest of the paper is in common mistakes that cost marks, and the evidence-based view of which topics repay this level of drilling is in the guide to important questions for 2027. The Operating Systems chapter of the GATE CSE 2027 book carries a worked bank of synchronization items with full interleaving traces and a year-by-year map of which property was tested in which paper.