Volume 8

12 pages 829 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.)