Information Technology Reference
In-Depth Information
the top page rectangle. The rectangles do not represent specific page frames as they
did in the FIFO diagram. Thus, each reference generating a page fault is now on the
top row. It should be noted that as more pages are allotted to the program the page
references in each row do not change. Only the number of page faults changes. This
will make the set of pages in memory for n page frames be a subset of the set of
pages for n
þ
1 page frames. In fact, the diagram could be considered a STACK
data structure with the depth of the stack representing the number of page frames.
If a page is not on the stack (i.e., is found at a depth greater than the number of
page frames), then a page fault occurs.
Example
8 array A. The array is
stored in row-major order. For THREE page frames, compute how many page
faults are generated by the following array-initialization loop. Assume that an
LRU replacement algorithm is used and that all frames are initially empty.
Assume that the page size is 16.
Consider the case of a two-dimensional 8
for I
¼
0to7do
for J
¼
0to7do
A[I, J]
¼
0;
End for
End for
The arrangement of the array elements in the secondary storage is shown in
Figure 7.15. The sequence of requests for the array elements in the first TWO
external loop executions is as follows:
I
0
J
¼
0, 1, 2, 3, 4, 5, 6, 7
a
00
, a
01
, a
02
, a
03
, a
04
, a
05
, a
06
, a
07
¼
The number of page faults (PFs)
1
¼
I
1
J
¼
0, 1, 2, 3, 4, 5, 6, 7
a
10
, a
11
, a
12
, a
13
, a
14
, a
15
, a
16
, a
17
¼
The number of page faults (PFs)
1
¼
From the above analysis, it is clear that there will be one PF in every external loop
execution. This makes the total number of PFs be 8. It should be noted that if the
array was stored column-major, then every internal loop execution would generate
eight page faults, thus causing the total number of PFs to become 64.
Clock Replacement Algorithm
This is a modified FIFO algorithm. It takes
into account both the time spent by a page residing in the main memory (similar
to the FIFO) and the pattern of usage of the page (similar to the LRU). The tech-
nique is therefore sometimes called the First-In-Not-Used-First-Out (FINUFO). In
keeping track of both the time and the usage, the technique uses a pointer to
Search WWH ::
Custom Search