The Proceedings of the Information Systems Education Conference 2009: §3522    Home    Papers/Indices    prev (§3514)    Next (§3524)
Sat, Nov 7, 2:00 - 2:25, Ballroom C     Paper (refereed)
Recommended Citation: McMaster, K, S E Sambasivam, and N Anderson.  A Probability Model for Belady's Anomaly.  In The Proceedings of the Information Systems Education Conference 2009, v 26 (Washington DC): §3522. ISSN: 1542-7382. (A later version appears in Information Systems Education Journal 8(43). ISSN: 1545-679X.)

A Probability Model for Belady's Anomaly

Refereed10 pages
Kirby McMaster    [a1] [a2]
Computer Science Department
St. Mary's College of Maryland    [u1] [u2]
St. Mary's City, Maryland, USA    [c1] [c2]

Samuel E. Sambasivam    [a1] [a2]
Computer Science Department
Azusa Pacific University    [u1] [u2]
Azusa, California, USA    [c1] [c2]

Nicole Anderson    [a1] [a2]
Computer Science Department
Winona State University    [u1] [u2]
Winona, Minnesota, USA    [c1] [c2]

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

Read this refereed paper in Adobe Portable Document (PDF) format. (10 pages, 763 K bytes)
Preview this refereed paper in Plain Text (TXT) format. (25 K bytes)

Comments and corrections to