--- title: "Process synchronization, Peterson, TSL" subject: "Operating System" chapter: 3 key: "semester_6/operating_system:why-synchronize-peterson-tsl" source: https://www.bctengineer.com/q/semester_6/operating_system/why-synchronize-peterson-tsl site: BCT Engineering --- # Process synchronization, Peterson, TSL Operating System · Chapter 3: Process Communication and Synchronization - Asked in: 2072 Magh, 2+4+4 marks - Video: [Peterson's Solution (Peterson's Algorithm) ll Operating System ll Two Process Synchronization](https://www.youtube.com/watch?v=7_h04U_VU5w) — 5 Minutes Engineering - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_6/operating_system/why-synchronize-peterson-tsl - Whole chapter: https://www.bctengineer.com/md/semester_6/operating_system/chapter-3 ## Question Why do processes need to be synchronized? Explain Peterson's Solution and TSL instruction approaches used in mutual exclusion with busy waiting. ## Short answer To prevent race conditions, processes synchronize. Peterson’s solution uses turn and interested flags; a process sets turn to itself and yields if the other is interested, ensuring mutual exclusion with busy waiting. TSL is an atomic read-and-set hardware instruction that implements a spin lock; it copies lock to register and sets lock to 1, looping until it finds lock zero. ## Answer #### Why synchronization is needed Processes that share data (a variable, file or buffer) must be synchronized because the result of their execution would otherwise depend on the exact order in which the CPU schedules them. - **Avoid race conditions:** if two processes read-modify-write the same shared variable at the same time, one update can be lost and the data becomes inconsistent. - **Mutual exclusion:** only one process may be inside its critical section (the code that touches shared data) at a time. - **Ordering and cooperation:** a consumer must wait until the producer has put data in the buffer; a producer must wait when the buffer is full. - **Avoid deadlock and starvation** while sharing resources. Example: two processes execute `counter++`. Each loads counter (5) into a register, adds 1 and stores back. If a switch occurs after the load, both store 6 and one increment is lost (expected 7). #### Peterson's solution Peterson's algorithm is a software solution for two processes (P0, P1) using busy waiting. It uses two shared variables: `turn` (whose turn it is to enter) and `interested[2]` (a flag per process). ```c #define N 2 /* two processes: 0 and 1 */ int turn; /* whose turn is it? */ int interested[N]; /* all FALSE at start */ void enter_region(int process) { int other = 1 - process; interested[process] = TRUE; /* I want to enter */ turn = process; /* but let the other go first if it wants */ while (turn == process && interested[other] == TRUE) ; /* busy wait */ } void leave_region(int process) { interested[process] = FALSE; /* I have left the critical region */ } ``` How it works: 1. A process sets its flag and writes its own number in `turn` (politely offering the other process priority). It then waits only while the other process is interested **and** `turn` still holds its own number. 2. If only one process wants to enter, the other flag is FALSE, so it enters at once. 3. If both arrive together, both set `turn`; the one that wrote `turn` last is the one whose condition stays true, so it waits and the other enters. Then the waiting process enters after `leave_region`. It satisfies mutual exclusion, progress and bounded waiting, without special hardware. Its drawbacks are busy waiting (wasted CPU) and that it works for two processes only. #### TSL (Test and Set Lock) instruction TSL is a hardware instruction `TSL RX, LOCK`. It reads the memory word LOCK into register RX and stores a non-zero value in LOCK, as one **indivisible (atomic)** operation; the memory bus is locked for other CPUs meanwhile. ```text enter_region: TSL REGISTER, LOCK | copy LOCK to REGISTER, set LOCK = 1 CMP REGISTER, #0 | was LOCK zero? JNE enter_region | if not zero, lock was set: loop again RET | LOCK was 0, now 1: enter critical region leave_region: MOVE LOCK, #0 | store 0 in LOCK RET | return to caller ``` - LOCK = 0 means the critical region is free; any process may enter by executing TSL. - If TSL returns 0, the caller has acquired the lock (LOCK is now 1) and enters. If it returns 1, someone else holds it and the caller loops (spin lock). - Works for any number of processes and on multiprocessors, but it also wastes CPU in busy waiting and may suffer priority inversion. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. Two processes run counter++ on a shared counter = 5. A context switch occurs after the first process loads the value but before it stores. What can happen? A. The second process is blocked automatically B. Both store 6, so one increment is lost C. The counter becomes 7 as expected D. The counter becomes 4 Answer: B. Both processes work on the old value 5 and store 6, so the result depends on scheduling order: a race condition. (Key point: Race condition) 2. Why must processes be synchronized when sharing data? A. To increase the number of CPUs used B. To ensure only one process is in its critical section at a time and results do not depend on scheduling order C. To make every process run at the same speed D. To give each process its own private copy of the data Answer: B. Synchronization gives mutual exclusion and ordering so shared data stays consistent. (Key point: Critical section) 3. In Peterson's enter_region, when does a process busy-wait? A. Only when both flags are FALSE B. While the other process is not interested C. While turn equals its own number and the other process is interested D. While turn is the other process's number Answer: C. The loop is while (turn == process && interested[other]); the process that wrote turn last waits. (Key point: Peterson's entry condition) 4. If both processes try to enter at the same time in Peterson's solution, which one enters first? A. The one that wrote turn last B. Neither; deadlock occurs C. The one with the lower process number always D. The one that wrote turn first, because the later write makes the other's wait-condition true Answer: D. The last writer of turn keeps turn == itself and waits; the earlier writer sees turn changed and enters. (Key point: Peterson with both arriving) ## Related in Operating System - [TSL instruction and Peterson's algorithm](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Atsl-peterson-algorithm) — 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 - [Critical section; mutual exclusion](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Acritical-section-mutual-exclusion-pc) — Operating System, chapter 3 - [Semaphore for mutual exclusion](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Asemaphore-enforce-mutual-exclusion) — Operating System, chapter 3 - [TSL; producer-consumer using monitors](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Apc-monitors-tsl) — 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 ## Related in other subjects - [Ricart-Agrawala mutual exclusion](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Aricart-agrawala) — Distributed System, chapter 6, asked 2× - [Mutual exclusion via sleep and wake](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3Amutual-exclusion-sleep-wake) — Embedded System, chapter 6 - [Task synchronization using busy/wait](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3Atask-sync-busy-wait) — Embedded System, chapter 6 - [Token ring mutual exclusion](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Atoken-ring-mutex) — Distributed System, chapter 6, asked 3×