Volume 8

Volume 8, Number 43

July 5, 2010

12 pages829 K bytes

A Probability Model for Belady's Anomaly

Kirby McMaster
St. Mary's College of Maryland
St. Mary's City, MD 20686

Samuel E. Sambasivam
Azusa Pacific University
Azusa, CA 91702

Nicole Anderson
Winona State University
Winona, MN 55987

Abstract: In demand paging virtual memory systems, the page fault rate of a process varies with the number of memory frames allocated to the process. When an increase in the number of allocated frames leads to an increase in the number of page faults, Belady's anomaly is said to occur. In this paper, we present a probability model for Belady’s anomaly. We describe the use of computer simulation to estimate the parameters of the model over a design region of process sizes and reference string lengths. We then relate our probability model to the occurrence rate of Belady’s anomaly in the simulation results.

Keywords: Belady's anomaly, virtual memory, demand paging, page replacement, FIFO, Random Page, probability model, simulation

Download this issue:   ISEDJ.8(43).McMaster.pdf   (Adobe PDF, 12 pages, 829 K bytes)

Preview the contents:   McMaster.j.txt   (ASCII txt, 25 K bytes)

Recommended Citation: McMaster, Sambasivam, and Anderson (2010). A Probability Model for Belady's Anomaly. Information Systems Education Journal, 8 (43). http://isedj.org/8/43/. ISSN: 1545-679X. (A preliminary version appears in The Proceedings of ISECON 2009: §3522. ISSN: 1542-7382.)