--- title: "Race condition; optimal page replacement limits" subject: "Operating System" chapter: 3 key: "semester_6/operating_system:race-condition-optimal-limitation" source: https://www.bctengineer.com/q/semester_6/operating_system/race-condition-optimal-limitation site: BCT Engineering --- # Race condition; optimal page replacement limits Operating System · Chapter 3: Process Communication and Synchronization - Asked in: 2068 Bhadra, 4+4 marks - Video: [L-3.1: Process Synchronization | Process Types | Race Condition | Operating System-1](https://www.youtube.com/watch?v=3Eaw1SSIqRg) — Gate Smashers - 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-optimal-limitation - Whole chapter: https://www.bctengineer.com/md/semester_6/operating_system/chapter-3 ## Question What is a critical reason and race condition? What are the limitations of the optimal page replacement algorithm? ## Short answer A critical region is code that accesses shared resources; a race condition arises when the outcome depends on the order of execution. The optimal page replacement algorithm cannot be implemented because it requires knowledge of the future reference string and is only used as a theoretical benchmark to evaluate other algorithms. ## Answer #### Critical region (critical section) and race condition The question's "critical reason" is read as **critical region**. A **critical region (critical section)** is the part of a program in which a process accesses shared memory, files or other shared resources. If two processes are inside their critical regions for the same resource at the same time, errors occur. A **race condition** is a situation in which two or more processes read or write shared data and the final outcome depends on the precise order in which they are scheduled. Example: two processes add an item to a shared print-spooler queue; both read `in = 7`, both store a file name in slot 7, and one of the files is lost. To avoid races, **mutual exclusion** must be enforced: while one process is in its critical region, no other may enter its own critical region for the same resource (using semaphores, mutexes, monitors, Peterson's algorithm). #### Limitations of the optimal page replacement algorithm The optimal (OPT or Belady's MIN) algorithm replaces the page that will **not be used for the longest time in the future**. It gives the lowest possible page-fault rate and never suffers Belady's anomaly, but: 1. **Not implementable**: the OS cannot know when each page will be referenced next; this requires knowledge of the future reference string. 2. **Needs prior run**: the reference string could be recorded in a first run and used in a second run, but the behaviour of a program changes with input, so it is not repeatable for general programs. 3. **High overhead**: even if the future were known, finding the farthest-used page for each fault is expensive. 4. **Unsuitable for interactive or multiprogrammed systems**, where behaviour depends on user input and other processes. 5. Therefore it is only used as a **benchmark** to compare practical algorithms such as LRU, FIFO and Clock (for example, LRU is "within X% of optimal"). ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. What is a critical region? A. A part of a program that is too slow B. A part of memory reserved for the kernel C. The part of a program where shared resources are accessed D. The code run at boot time Answer: C. It is the section where a process accesses shared memory or files; simultaneous execution by two processes causes errors. (Key point: Critical region) 2. In the print spooler example, why is a file lost? A. The printer fails B. Both processes read in = 7 and write their file name to slot 7 C. The queue is full D. The spooler deletes old files Answer: B. Both read the same value of in before either updates it, so the second write overwrites the first. (Key point: Race condition example) 3. Which page does the optimal algorithm replace? A. The least recently used page B. The oldest page C. The page that will not be used for the longest time in the future D. The page loaded most recently Answer: C. OPT replaces the page whose next use is farthest in the future. (Key point: Optimal algorithm rule) 4. What is the main reason OPT cannot be used in real systems? A. It suffers from Belady's anomaly B. It gives high page-fault rates C. It needs too little memory D. It requires knowledge of the future reference string Answer: D. The OS cannot know future references, so OPT is used only as a benchmark for algorithms like LRU, FIFO and Clock. (Key point: Main limitation of OPT) ## Related in Operating System - [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 example; Peterson's algorithm](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Arace-condition-example-peterson) — Operating System, chapter 3 - [Optimal replacement; fragmentation, utilization](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Aoptimal-fragmentation-utilization) — Operating System, chapter 4 - [Page faults: FIFO, Optimal, LFU, LRU](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Apage-faults-fifo-optimal-lfu-lru-5frames) — Operating System, chapter 4, asked 2× - [Race condition; sleep() and wakeup()](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Arace-sleep-wakeup) — Operating System, chapter 3 - [Page fault; allocation and replacement](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Apage-fault-allocation-replacement) — Operating System, chapter 4 ## 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 - [Optimal equalizer weights using MSE algorithm](https://www.bctengineer.com/question.md?key=semester_7%2Fwireless_communication%3Amse-optimal-weights) — Wireless Communication, chapter 5, asked 3× - [Mapping function and replacement algorithm](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_organization_and_architecture%3Amapping-replacement) — Computer Organization and Architecture, chapter 6 - [Replacement algorithm in associative mapping](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_organization_and_architecture%3Areplacement-assoc) — Computer Organization and Architecture, chapter 6