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