Page 139 - DCAP403_Operating System

Operating System

Notes The modify flag indicates that the data on that page has been changed since it was brought into

memory. When a page is to be stolen, if the modify flag is set, a pageout call is made before
stealing the page. Pages that are part of working segments are written to paging space; persistent
segments are written to disk.
All paging algorithms function on three basic policies: a fetch policy, a replacement policy, and
a placement policy. In the case of static paging, describes the process with a shortcut: the page
that has been removed is always replaced by the incoming page; this means that the placement

policy is always fixed. Since you are also assuming demand paging, the fetch policy is also a
constant; the page fetched is that which has been requested by a page fault. This leaves only the
examination of replacement methods.

7.10.1 Static Page Replacement Algorithms

Optimal Replacement Theory

In a best case scenario the only pages replaced are those that will either never be needed again, or
have the longest number of page requests before they are referenced. This “perfect” scenario is
usually used only as a benchmark by which other algorithms can be judged, and is referred to as
either Belady’s Optimal Algorithm or Perfect Prediction (PP). Such a feat cannot be ccomplished
without full prior knowledge of the reference stream, or a record of past behavior that is incredibly
consistent. Although usually a pipe dream for system designers, suggests it can be seen in very
rare cases, such as large weather prediction programs that carry out the same operations on
consistently sized data.

Random Replacement

On the flip-side of complete optimization is the most basic approach to page replacement:

simply choosing the victim, or page to be removed, at random. Each page frame involved has an
equal chance of being chosen, without taking into consideration the reference stream or locality
principals. Due to its random nature, the behavior of this algorithm is quite obviously, random
and unreliable. With most reference streams this method produces an unacceptable number of
page faults, as well as victim pages being thrashed unnecessarily. A better performance can almost
always be achieved by employing a different algorithm. Most systems stopped experimenting
with this method as early as the 1960’s.

First-In, First-Out (FIFO)

First-in, first-out is as easy to implement as Random Replacement, and although its performance
is equally unreliable or worse, its behavior does follow a predictable pattern. Rather than choosing

a victim page at random, the oldest page (or first-in) is the first to be removed. Conceptually
compares FIFO to a limited size queue, with items being added to the queue at the tail. When the

queue fills (all of the physical memory has been allocated), the first page to enter is pushed out of
head of the queue. Similar to Random Replacement, FIFO blatantly ignores trends, and although
it produces less page faults, still does not take advantage of locality trends unless by coincidence

as pages move along the queue. A modification to FIFO that makes its operation much more
useful is First-In Not-Used First-Out (FINUFO). The only modification here is that a single bit

is used to identify whether or not a page has been referenced during its time in the FIFO queue.

This utility, or referenced bit, is then used to determine if a page is identified as a victim. If, since
it has been fetched, the page has been referenced at least once, its bit becomes set. When a page
must be swapped out, the first to enter the queue whose bit has not been set is removed; if every

active page has been referenced, a likely occurrence taking locality into consideration, all of the
bits are reset. In a worst-case scenario this could cause minor and temporary thrashing, but is
generally very effective given its low cost.
132 LOVELY PROFESSIONAL UNIVERSITY