Self-checkedTier 1 13 min reados.critical-section

Critical section and race conditions

Why concurrent access to shared data goes wrong: race conditions and lost updates, the structure of a critical section (entry, exit, remainder), the three requirements of a solution (mutual exclusion, progress, bounded waiting), and counting the possible results of racing updates.

Why it exists

Processes and threads that share data can interfere with each other. The operating system's scheduler may switch from one to another at almost any moment, so the order in which their instructions interleave is not under the programmer's control. If the result of a computation depends on that order, the program has a race condition, and the result is sometimes wrong. Controlling access to shared data is the critical-section problem, and most of the rest of operating-system concurrency (semaphores, monitors, deadlock) is about solving it. GATE asks you to recognize the requirements of a solution, to say whether a given scheme meets them, and, very often, to count the possible final values of a shared variable.

Prerequisites

Process model and PCB

You need the process and thread picture from the process model and threads: threads of one process share memory, and processes can share memory too.

Precise definitions

Race condition. A situation in which several processes access and update shared data and the outcome depends on the particular order in which the accesses take place.

Why x = x + 1 is not atomic. On a typical machine it takes three instructions: load x into a register, add 1, store the register into x. A context switch (or another processor) can intervene between any two of them. If two threads execute the three steps and the second one loads x before the first has stored, both start from the same old value and one update is lost: x ends at 1 instead of 2.

Critical section. The part of a process's code that accesses shared data and must not be executed by more than one process at a time. A process is organised as

repeat
    entry section        (ask permission to enter)
    critical section     (touch the shared data)
    exit section         (announce that it has left)
    remainder section    (everything else)
forever

The critical-section problem is to design the entry and exit sections so that three requirements hold, without assumptions about the relative speeds or the number of processors (only that every process makes progress in the critical section and the remainder section may take any time, including for ever):

Mutual exclusion. If a process is executing in its critical section, no other process can be executing in its critical section.
Progress. If no process is in its critical section and some processes want to enter, then only processes that are not in their remainder sections may take part in deciding which enters next, and this decision cannot be postponed indefinitely. (A process in its remainder section must not prevent others from entering. No deadlock.)
Bounded waiting. After a process has made a request to enter, there is a bound on the number of times other processes are allowed to enter their critical sections before the request is granted. (No starvation.)

A solution that fails (1) is unsafe (data corruption), one that fails (2) can lock up or waste the critical section, and one that fails (3) can starve a process.

Where critical sections arise. In an operating-system kernel: shared kernel data structures (the ready queue, the process table, open-file tables) accessed by several processes or from interrupt handlers. In applications: threads sharing variables, and processes using shared memory or files. Read-only access to data that nobody modifies needs no protection.

Approaches to a solution.

Software solutions in the processes themselves (Peterson's algorithm and others) using only ordinary memory reads and writes.
Hardware support: atomic instructions such as test-and-set and compare-and-swap, and (on one processor) disabling interrupts while the shared data are touched. Disabling interrupts is simple, but it only works on a single processor, is dangerous to give to user programs, and delays interrupt handling.
Operating-system primitives built on those: semaphores and monitors.
A non-preemptive kernel never preempts a process in kernel mode, so kernel data structures are protected on a single processor; a preemptive kernel must protect them explicitly.

Atomic operation. An operation that appears to execute as one indivisible step: no other process can see it half done. All the solutions above ultimately rest on a few hardware operations that are atomic.

How it works

The animation shows the shortest schedule, found by exhaustively searching every interleaving, in which two threads each add 1 to x (starting at 0) and the final value of x is 1. T1 loads 0 and computes 1; T2 loads x before T1 has stored, so it also sees 0; then both store 1. The search covered all interleavings; this one is the shortest of the bad ones, and there are good ones as well (x = 2 when one thread completes its three steps before the other starts).

A race: two threads each add 1 to x: start

Interleaving found by search, not typed

▶r1 = x
r1 = r1 + 1
x = r1

▶r2 = x
r2 = r2 + 1
x = r2

Step 0

x is 0. Each thread does x = x + 1 as three separate instructions: load into a register, add, store. The scheduler may interleave them arbitrarily. This is the SHORTEST schedule that ends with x = 1 instead of 2 (a lost update).

0 / 6

computed by script: exhaustive search of the interleavings of a small concurrent program. python3 scripts/gen-os-sync-traces.py

Worked examples

EX 1Which final values are possible?

Easy

Two threads each execute x = x + 1 once (x starts at 0), each as load, add, store. If the threads run one after the other, $x = 2$ . If both load before either stores, $x = 1$ . No schedule gives 0 or 3. So the possible results are 1 and 2. For $k$ threads that each add 1 once, the possible final values are $1, 2, \ldots, k$ (the maximum when they run one at a time, the minimum when all load before any stores). This was confirmed by trying every interleaving.

EX 2The program that tries every interleaving

Medium

Thread 1 adds 1 to x $n$ times and thread 2 adds 1 $m$ times, each addition being load, add, store. A depth-first search over every interleaving of the steps lists the reachable final values of x.

#include <stdio.h>
 
/* Two threads add 1 to a shared x, n1 and n2 times. Each addition is three separate steps: load, add, store.
   Depth-first search over EVERY interleaving of the steps; record which final values of x are reachable. */
static int n_steps[2];
static int reachable[64];
 
static void dfs(int pc0, int pc1, int x, int r0, int r1) {
    if (pc0 == n_steps[0] && pc1 == n_steps[1]) { reachable[x] = 1; return; }
    if (pc0 < n_steps[0]) {
        int k = pc0 % 3;
        if (k == 0) dfs(pc0 + 1, pc1, x, x, r1);
        else if (k == 1) dfs(pc0 + 1, pc1, x, r0 + 1, r1);
        else dfs(pc0 + 1, pc1, r0, r0, r1);
    }
    if (pc1 < n_steps[1]) {
        int k = pc1 % 3;
        if (k == 0) dfs(pc0, pc1 + 1, x, r0, x);
        else if (k == 1) dfs(pc0, pc1 + 1, x, r0, r1 + 1);
        else dfs(pc0, pc1 + 1, r1, r0, r1);
    }
}
 
int main(void) {
    for (int n = 1; n <= 3; n++) {
        for (int m = 1; m <= 3; m++) {
            for (int i = 0; i < 64; i++) reachable[i] = 0;
            n_steps[0] = 3 * n; n_steps[1] = 3 * m;
            dfs(0, 0, 0, 0, 0);
            printf("%d and %d increments: x can end as", n, m);
            for (int v = 0; v < 64; v++) if (reachable[v]) printf(" %d", v);
            printf("\n");
        }
    }
    return 0;
}

1 and 1 increments: x can end as 1 2
1 and 2 increments: x can end as 1 2 3
1 and 3 increments: x can end as 1 2 3 4
2 and 1 increments: x can end as 1 2 3
2 and 2 increments: x can end as 2 3 4
2 and 3 increments: x can end as 2 3 4 5
3 and 1 increments: x can end as 1 2 3 4
3 and 2 increments: x can end as 2 3 4 5
3 and 3 increments: x can end as 2 3 4 5 6

Reading it. The largest value is always $n + m$ (no update lost). The smallest is 1 if either thread adds only once, and 2 if both add at least twice. Every value in between is reachable. Why 2 and not 1 when both threads add at least twice: once any thread has stored, x is at least 1 for the rest of the run (every stored value is at least 1). Whichever thread makes the very last store computed it from its own last load, and that load came after that thread's own earlier store, so it saw at least 1 and stores at least 2. A thread with only one increment can store 1 as the last store (it loaded 0 early and stored late), which is why the minimum is 1 if either thread adds just once.

EX 3Which requirement fails?

Medium

Three proposals for protecting a critical section shared by two processes, with the requirement each breaks:

"A process may enter whenever it likes." No protection at all: mutual exclusion fails.
"Process 1 may enter only on odd turns and process 2 only on even turns, and a turn passes when a process leaves." Mutual exclusion holds, but if process 2 never wants to enter again, process 1 waits for ever for a turn that does not come: progress fails (a process in its remainder section blocks the other).
"The entry section picks the lowest-numbered waiting process every time." Mutual exclusion and progress hold, but process 2 may wait for ever if process 1 keeps coming back: bounded waiting fails.

The next page analyses these ideas, and Peterson's algorithm, which satisfies all three.

EX 4Many racing threads

GATE level

$N$ threads each execute x = x + 1 once on a shared x that starts at 0. The final value is at most $N$ (all updates survive) and at least 1 (every thread loads 0, then all store 1), and every value from 1 to $N$ can occur. Always do the enumeration on the actual machine-level steps rather than the source line. A question with x = x + 1 repeated $k$ times in each of two loops has maximum $2k$ and minimum $2$ (for $k \ge 2$ ), as the table shows.

EX 5Does it need protection?

GATE level

Two threads only read a global table that nobody writes: no critical section needed. One thread appends to a list and another removes from it: both need protection, since a half-finished append may be seen by the remover. A counter incremented by threads on a single processor with a non-preemptive scheduler that never switches inside the increment: safe in practice on that system, but not portable. The same code on a multiprocessor: two processors really can execute the three steps at the same time, so protection is needed even without preemption. A solution that "disables interrupts" prevents a context switch on one processor but does nothing against another processor.

Cheat box

Race condition: the result depends on the order of accesses to shared data. x = x + 1 is load, add, store: not atomic.
Critical section: code touching shared data. Structure: entry, critical section, exit, remainder.
Requirements: mutual exclusion, progress (a process in its remainder section must not block others; no deadlock), bounded waiting (no starvation). No assumption about speeds.
Two threads, $n$ and $m$ increments: max $n + m$ ; min 1 if either does 1 increment, else 2; all values between occur. $k$ threads, one increment each: $1 \ldots k$ .
Disabling interrupts: works only on one processor; not for user programs.
Atomic instruction: indivisible; the base of all solutions.

Traps and GATE patterns

Connections

Builds on

Process model and PCB

Unlocks

Threads and multithreading modelsuses Priority and round robin schedulinguses Peterson, Dekker and software solutionsPrerequisite of Peterson, Dekker and software solutionsuses SemaphoresPrerequisite of Semaphoresuses Inter-process communicationuses Test-and-set, swap and atomic instructionsPrerequisite of Test-and-set, swap and atomic instructionsuses Multilevel queues and real-time schedulinguses

Across subjects

Interrupts and vectoringuses

Within this subject

Process model and PCBuses Threads and multithreading modelsuses Peterson, Dekker and software solutionsuses Semaphoresuses

Threads of one process share memory, which is where most races occur. The simplest software answer is Peterson's algorithm; the standard operating-system tool is the semaphore. Disabling interrupts relies on the interrupt mechanism: a context switch is triggered by the timer interrupt, so no interrupt means no switch.

PYQs

8 previous year questions from your book. I re-solved each one myself (6 by running or simulating, 2 by reasoning only); the book's key is shown next to my answer. All PYQs

GATE 2024 · MCQQ10 · page 296 of the book

Consider the following two threads T1 and T2 that
update two shared variables a and b. Assume that
initially a = b = 1. Though context switching between
threads can happen at any time, each statement of T1
or T2 is executed atomically without interruption.

T1                            T2
          a = a + 1;                 b = 2 * b;
          b = b + 1;                 a = 2 * a;

Which one of the following options lists all the
possible combinations of values of a and b after both
T1 and T2 finish execution?

(a)(a = 4, b = 4); (a = 3, b = 3); (a = 4, b = 3)
(b)(a = 3, b = 4); (a = 4, b = 3); (a = 3, b = 3)
(c)(a = 4, b = 4); (a = 4, b = 3); (a = 3, b = 4)
(d)(a = 2, b = 2); (a = 2, b = 3); (a = 3, b = 4)

GATE 2021 · MSQQ18 · page 298 of the book

Consider the following multi-threaded code
segment (in a mix of C and pseudocode), invoked
by two processes P1 and P2, and each of the
processes spawns two threads T1 and T2:

int x = 0;   // global

Lock L1;    // global

main() {

create a thread to execute foo();  // Thread T1

create a thread to execute foo();  // Thread T2

wait for the two threads to finish execution;

print (x);}

foo () {

 int y = 0;

Acquire L1;

x = x + 1;

 y = y + 1;

Release L1;

print (y);}

Which of the following statement(s) is / are correct?

(a)At least one of P1 and P2 will print the value of x as 4.
(b)At least one of the threads will print the value of y as 2.
(c)Both T1 and T2, in both the processes, will print the value of y as 1.
(d)Both P1 and P2 will print the value of x as 2.

GATE 2023 · MCQQ3 · page 317 of the book

Consider the two functions incr and decr shown
below.

          incr(){
                     wait(s);

                     X = X+1;
                      signal(s);
         }
         decr(){
                     wait(s);

                     X = X-1;
                      signal(s);
         }

There are 5 threads each invoking incr once, and 3
threads each invoking decor once, on the same
shared variable X. The initial value of X is 10.

Suppose there are two implementations of the
semaphore s, as follows:

I-1: s is a binary semaphore initialized to 1.
I-2: s is a counting semaphore initialized to 2.

Let V1, and V2 be the values of X at the end of the
execution of all the threads with implementations I-
1, and I-2, respectively.

Which one of the following choices corresponds to
the minimum possible values of V1, V2,
respectively?

(a)15,7
(b)7,7
(c)12,7
(d)12,8

GATE 2021 · MSQQ5 · page 318 of the book

Consider the following pseudocode, where S is a
semaphore initialized to 5 in line #2 and counter is
a shared variable initialized to 0 in line#1. Assume
that the increment operation in line#7 is not atomic.

1. int counter = 0

2. Semaphore S = init(5);

3. void parop(void)

4. {

5.

wait(S);

6.

 wait(S);

7.

  counter++;

8.
        signal(S);

9.                signal(S);

10.}

If five threads execute the function parop
concurrently, which of the following program
behavior(s) is/are possible?

(a)The value of counter is 5 after all the threads successfully complete the execution of parop.
(b)The value of counter is 1 after all the threads successfully complete execution of parop.
(c)The value of counter is 0 after all the threads successfully complete the execution of parop.
(d)There is a deadlock involving all the threads.

GATE 2021 · MSQQ6 · page 318 of the book

Consider a computer system with multiple shared
resource types, with one instance per resource type.
Each instance can be owned by only one process at
a time. Owning and freeing of resources are done
by holding a global lock (L). The following scheme
is used to own a resource instance:

function OWNRESOURCE(Resource R)

Acquire lock L // a global lock

if R is available then

Acquire R

Release lock L

else

if R is owned by another process P then
           Terminate P, after releasing all resources
owned by P

Acquire R

Restart P

Release lock L

end if
         end if

end if

end function

Which of the following choice(s) about the above
scheme is/are correct?

(a)The scheme violates the mutual exclusion property.
(b)The scheme ensures that deadlocks will not occur.
(c)The scheme may lead to starvation.
(d)The scheme may lead to live-lock.

year not read yetQ8 · page 319 of the book

Consider three concurrent processes P1, P2 and P3
as shown below, which access a shared variable

D initialized to 100.
P1: D = D + 20
P2: D = D - 50
P3: D = D + 10
The processes are executed on a uniprocessor
system running a time-shared operating system. If
the minimum and maximum possible values of D
after the three processes have completed
execution are X and Y respectively, then the value
of Y - X is ______

GATE 2015 · MCQQ13 · page 320 of the book

The following two functions P1 and P2 that share a
variable B with an initial value of 2 execute
concurrently.

P1()

{

   C = B – 1;

   B = 2*C;

}

P2()

{

  D = 2 * B;

 B = D - 1;

}

The number of distinct values that B can possibly
take after the execution is?

(a)3
(b)4
(c)5
(d)6

GATE 2013 · MCQQ17 · page 321 of the book

A shared variable x, initialized to zero, is operated on
by four concurrent processes W, X, Y, Z as follows.
Each of the processes W and X reads x from memory,
increments by one, stores it to memory, and then
terminates. Each of the processes Y and Z reads x
from memory, decrements by two, stores it to
memory, and then terminates. Each process before
reading x invokes the P operation (i.e. wait) on a
counting semaphore S and invokes the V operation
(i.e., signal) on the semaphore S after storing x to

OPERATING SYSTEMS
memory. Semaphore S is initialized to two. What is
the maximum possible value of x after all processes
complete execution?

(a)-2
(b)-1
(c)1
(d)2

Self-check

Question 1

Two threads each execute x = x + 1 three times (as load, add, store) on x starting at 0. What are the smallest and largest possible final values?

Show answer

Largest 6. Smallest 2 (the table: 3 and 3 increments gives 2 to 6).

Question 2

Which of the three requirements does "a thread that finishes its critical section must wait for the other thread to run its critical section before it can enter again" violate?

Show answer

Progress: if the other thread never wants to enter, the first is blocked by a thread in its remainder section (strict alternation).

Question 3

Four threads each add 1 to x once (x starts at 0). What values can x end with?

Show answer

1, 2, 3 or 4.

Question 4

Why does disabling interrupts not protect a critical section on a multiprocessor?

Show answer

It only prevents a context switch on the processor that disabled them. Another processor can still execute the same critical section at the same time.

Revision card

One-screen revision

Race condition: outcome depends on interleaving. Update = load, add, store, not atomic.
Entry, critical, exit, remainder. Mutual exclusion, progress, bounded waiting.
Two threads, $n$ and $m$ increments: $\max = n + m$ , $\min = 1$ if either is 1 else 2.
Disabling interrupts: single processor only.

References

·Silberschatz, Galvin, Gagne, Operating System Concepts, Chapter 6 Synchronization Tools (background, the critical-section problem)
·Tanenbaum and Bos, Modern Operating Systems, Chapter 2 Processes and Threads (interprocess communication, race conditions, critical regions)
·Stallings, Operating Systems: Internals and Design Principles, Chapter 5 Concurrency: Mutual Exclusion and Synchronization

Verification

The possible final values of racing increments are found three ways that must agree: a brute-force enumeration of every interleaving in Python (scripts/enum-checks/os_sync.py, for up to four increments in each of two threads and for up to four threads with one increment each), the exhaustive state-space search of the generic model checker in scripts/gen-os-sync-traces.py, and the depth-first search in the C program on this page (npm run verify:c). The animation shows the shortest schedule found by the search that ends with a lost update; tests/os-sync-traces.test.ts rechecks the trace. The model treats each load, add and store as one atomic step (sequentially consistent memory); real processors and compilers can reorder memory accesses, which makes things worse, not better. Textbook chapter titles are from memory. SECOND PASS (2026-11-02, done by the assistant, not a human check): every Self-check question was solved before the printed answer was read and all agreed; the definitions, worked examples, cheat box and traps were read claim by claim and the numbers re-derived by hand. No defect found. Status raised to self-checked; verified needs a textbook or human check.

last verified: never

My notes (saved in this browser)

Disk scheduling

Peterson, Dekker and software solutions