Race condition; optimal page replacement limits

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").