A Case Study of Belady's Anomaly and the Binomial Distribution

In Operating Systems courses, instructors often assign case studies that involve programming to enhance course objectives. One topic that usually arouses students' interest is Belady's anomaly. In virtual memory systems with demand paging, the page fault rate of a process varies with the number of memory frames allocated to the process. When an increase in allocated frames leads to an increase in page faults, Belady's anomaly is said to occur. In this paper, we present a binomial probability model for Belady’s anomaly. In this case study, computer simulation was used to estimate the parameters of the model over a design region of process sizes and reference string lengths. The number of unshared pages in K vs. K+1 memory frames was determined and was used to compute the parameters N and P of a corresponding binomial distribution. A chi-square goodness-of-fit test was performed that related the binomial model to the occurrence of Belady’s anomaly in the simulation results.