The Swapping Curve
Once the Least Recently Used replacement policy is viewed as a
stack, a swapping curve based on the number of pages can be developed.
A swapping curve relates the rate of page faults to the size of the
resident set of page frames (that is, the number of page frames
allotted to a process).
The rate of page faults can be determined by creating a histogram
of the occurances of the "distances" of page retrieval. The
"distance" is the depth at which the page resides in the stack when it
is referenced. The distance string is a list of the distances
for each reference in the reference string. Note that the first time a
page is referenced, the distance must be considered infinity because the
page must be accessed from secondary
storage and so a page fault will occur no matter how many page
frames are allotted to the process. The histogram is contructed by
counting the occurances for each distance.
The frames outlined in red depict page faults of first time page references. Their distances, shown below the grid of page frames, are given as infinity. There will always be as many occurances of infinity as there are different pages referenced. The darker page frames depict the location in the stack of page when referenced. Its row in the illustration is the distance it must be moved to put it on top of the stack. The distance histogram shows the number of occurances of each distance in the reference string. As an illustration, the 3 occurances of distance 5 are connected to show how they were obtained.
The SWAPPING CURVE is formed by using the histogram to
compute the number of page faults at each resident set size and map it
to the number of pages in that size. Notice that the bars of the
swapping graph represent accumulated number of page faults at each page
size on the histogram. The performance of a memory policy with respect
to a reference string can be expressed using the
FAULT RATE curve, the number of page faults divided by the total
number of page references which is mapped to the number of pages. The
fault rate curve is analogous to the swapping curve.
However, multiprogramming systems use the parameter PAGING RATE for evaluating performance which can be better determined by the inverse of the fault rate which is known as the lifetime function.
