Computation of Page Fault Probability from Program Transition Diagram

An algorithm is given for calculating page fault
probability in a virtual memory system operating 
under demand paging with various memory sizes and replacement
rules.  A first order Markov model of program 
behavior is assumed, and a representation of the system
based on memory states, control states, and memory 
substates is presented.  The algorithm is general in
the sense that the page fault probabilities can 
be calculated for nonpredictive replacement rules applied
to any program represented by a one-step Markov 
chain.  A detailed example is given to illustrate the
algorithm for Random and Least Recently Used (LRU) 
replacement rules.

CACM April, 1974

Franklin, M. A.
Gupta, R. K.

virtual memory, demand paging, replacement rule,
program model, program behavior, Markov model, 
page fault, page fault probability

4.30 6.20

CA740402 JB January 18, 1978  10:31 AM

1533	4	2668
1892	4	2668
1924	4	2668
1951	4	2668
2095	4	2668
2218	4	2668
2297	4	2668
2374	4	2668
2526	4	2668
2667	4	2668
2667	4	2668
2667	4	2668
2668	4	2668
2668	4	2668
2668	4	2668
2668	4	2668
2668	4	2668
2862	4	2668
2863	4	2668
1604	5	2668
1728	5	2668
1761	5	2668
1827	5	2668
2668	5	2668
2668	5	2668
2668	5	2668
2677	5	2668