--- title: "Race condition example; Peterson's algorithm" subject: "Operating System" chapter: 3 key: "semester_6/operating_system:race-condition-example-peterson" source: https://www.bctengineer.com/q/semester_6/operating_system/race-condition-example-peterson site: BCT Engineering --- # Race condition example; Peterson's algorithm Operating System · Chapter 3: Process Communication and Synchronization - Asked in: 2071 Bhadra, 3+7 marks - Video: [Race Condition & Peterson's Solution](https://www.youtube.com/watch?v=6XOqigf2tCU) — Computer Dove - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_6/operating_system/race-condition-example-peterson - Whole chapter: https://www.bctengineer.com/md/semester_6/operating_system/chapter-3 ## Question Define race condition with example. Explain Peterson's Algorithm. ## Short answer A race condition is when the final result of shared-data access depends on the order of process scheduling, for example count++ and count-- interleaving gives an incorrect count. Peterson's algorithm uses shared variables turn and interested to allow two processes into a critical section with mutual exclusion, progress and bounded waiting, but it busy waits. ## Answer #### Race condition A **race condition** is a situation where two or more processes (or threads) read and write shared data, and the final result depends on the exact order in which the processes are scheduled. **Example**: a shared counter `count = 5`. Process P1 executes `count++` and process P2 executes `count--`. In machine code each is three steps: load into register, change the register, store back. ```text P1: R1 = count (R1 = 5) P1: R1 = R1 + 1 (R1 = 6) -- context switch -- P2: R2 = count (R2 = 5) P2: R2 = R2 - 1 (R2 = 4) P2: count = R2 (count = 4) -- context switch -- P1: count = R1 (count = 6) ``` The correct final value is 5, but here it is 6 (or 4 with another order). Another example is the print spooler, where two processes pick the same slot `in` and one file is overwritten. #### Peterson's algorithm Peterson's algorithm (1981) is a software solution of the mutual exclusion problem for **two processes** (0 and 1), which uses two shared variables: `turn` (whose turn it is to enter) and `interested[2]` (flags showing who wants to enter). ```c #define N 2 int turn; /* whose turn is it? */ int interested[N]; /* all values initially FALSE */ void enter_region(int process) { /* process is 0 or 1 */ int other = 1 - process; /* the other process */ interested[process] = TRUE; /* show interest */ turn = process; /* set the flag */ while (turn == process && interested[other] == TRUE) ; /* busy wait */ } void leave_region(int process) { interested[process] = FALSE; /* departure from region */ } ``` **Working**: before entering its critical region, a process calls `enter_region` with its number. It sets its interested flag and sets `turn` to itself. If the other process is not interested, the loop condition is false and it enters at once. If both call at the same time, both set `turn`, but only the last store survives; the process whose store came first sees `turn` != itself and enters, while the last one loops until the first calls `leave_region`. **Properties**: it guarantees mutual exclusion, progress and bounded waiting, and needs no special hardware. Disadvantages: it works for two processes only, and it uses **busy waiting** (wasting CPU, and risking priority inversion). ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. With count = 5, P1 doing count++ and P2 doing count-- interleaved as shown, what final value can result? A. Always 5 B. Always 4 C. 6 or 4 depending on the order, not the correct 5 D. 0 Answer: C. Whichever process stores last overwrites the other's update, giving 6 or 4 instead of 5. (Key point: Race condition example result) 2. Which shared variables does Peterson's algorithm use? A. A semaphore and a mutex B. turn and interested[] C. lock and count D. A queue and a counter Answer: B. turn says whose turn it is and interested[] flags show which process wants to enter. (Key point: Peterson variables) 3. If both processes call enter_region at the same time, who enters first? A. The one whose store to turn came last B. Both enter C. The process that set turn first (the last writer waits) D. Neither; deadlock results Answer: C. Only the last store to turn survives; the earlier process sees turn != itself and enters, while the last one loops. (Key point: Simultaneous entry) 4. What are the disadvantages of Peterson's algorithm? A. It needs special hardware B. It breaks mutual exclusion C. It allows starvation D. It works for only two processes and uses busy waiting Answer: D. It guarantees mutual exclusion, progress and bounded waiting but only for two processes and it wastes CPU spinning. (Key point: Peterson limitations) ## Related in Operating System - [Race condition; optimal page replacement limits](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Arace-condition-optimal-limitation) — Operating System, chapter 3 - [Race condition; critical section approaches](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Arace-condition-critical-section-approaches) — Operating System, chapter 3 - [Race condition; sleep() and wakeup()](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Arace-sleep-wakeup) — Operating System, chapter 3 - [Race condition; mutual exclusion requirements](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Arace-mutual-exclusion-requirements) — Operating System, chapter 3 - [TSL instruction and Peterson's algorithm](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Atsl-peterson-algorithm) — Operating System, chapter 3 ## Related in other subjects - [Race around condition; JK to SR conversion](https://www.bctengineer.com/question.md?key=semester_3%2Fdigital_logic%3Arace-around-jk-to-sr) — Digital Logic, chapter 6 - [Second region condition, ellipse midpoint](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_graphics%3Aellipse-second-region-condition) — Computer Graphics, chapter 2 - [Circular queue algorithm with conditions](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Acircular-queue-algorithm-conditions) — Data Structure and Algorithm, chapter 2