Page 189 - DCAP103_Principle of operating system

Principles of Operating Systems

Notes For example, if we trace a particular process, we might record the following address sequence:
0100, 0432, 0101, 0612, 0102, 0103, 0104, 0101, 0611, 0102, 0103,
0104, 0101, 0610, 0102, 0103, 0104, 0101, 0609, 0102, 0105,
which, at 100 bytes per page, is reduced to the following reference string.
1, 4, 1, 6, 1, 6, 1, 6, 1, 6, 1.
To determine the number of page faults for a particular reference string and page-replacement
algorithm, we also need to know the number of page frames available. Obviously, as the number
of frames available increases, the number of page faults decreases. For the reference string
considered previously, for example, if we had three or more frames, we would have only three
faults, one fault for the first reference to each page. On the other hand, with only one frame
available, we would have a replacement with every reference, resulting in 11 faults. As the
number of frames increases, the number of page faults drops to some minimal level. Of course,
adding physical memory increases the number of frames.
To illustrate the page-replacement algorithms, we shall use the reference string
7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1
for a memory with three frames.

Figure 5.29: Graph of Page Faults versus the Number of Frames

5.10.2 FIFO Page Replacement

The simplest page-replacement algorithm is a FIFO algorithm. A FIFO replacement algorithm
associates with each page the time when that page was brought into memory. When a page
must be replaced, the oldest page is chosen. Notice that it is not strictly necessary to record the
time when a page is brought in. We can create a FIFO queue to hold all pages in memory. We
replace the page at the head of the queue. When a page is brought into memory, we insert it
at the tail of the queue. For our example reference string, our three frames are initially empty.
The first three references (7, 0, 1) cause page faults, and are brought into these empty frames.
The next reference (2) replaces page 7, because page 7 was brought in first. Since 0 is the next
reference and 0 is already in memory, we have no fault for this reference. The first reference to
3 results in page 0 being replaced, since it was the first of the three pages in memory (0, 1, and
2) to be brought in. Because of this replacement, the next reference, to 0, will fault. Page 1 is then
replaced by page 0. Every time a fault occurs, we show which pages are in our three frames.
There are 15 faults altogether. The FIFO page-replacement algorithm is easy to understand and
program. However, its performance is not always good. The page replaced may be an initialization
module that was used a long time ago and is no longer needed. On the other hand, it could
contain a heavily used variable that was initialized early and is in constant use. Notice that,
even if we select for replacement a page that is in active use, everything still works correctly.
After we page out an active page to bring in a new one, a fault occurs almost immediately to

182 LOVELY PROFESSIONAL UNIVERSITY