Belady现象演示

Belady现象演示

引用

CSDN

1.

https://blog.csdn.net/maligebazi/article/details/120584381

Belady现象（Bélády’s anomaly）是指：当给一个进程增加页帧数分配时，在FIFO替换算法策略下可能会出现缺页率增加的异常现象。本文通过一个具体的访问序列示例，详细解释了这一现象，并对比了在不同页帧数情况下的缺页率。

假定给某进程分为5页（page），但是它在内存中只分配到3个页帧（page frame），现在有一访问串：
1,2,3,4,1,2,5,1,2,3,4,5
，表示依次访问第1页、第2页……

1. 刚开始时，进程页还在虚存（磁盘）中，尚未缓存到内存中，所以第一次要访问第1页时发生一次缺页故障，此时调入第1页到内存中，占一个页帧
2. 此时还剩下两个页帧未分配，由于接下来依次访问第2、3页，同理会触发两次缺页故障，在此之后，第1、2、3页都已经缓存在内存中
3. 接下来要访问第四页，由于在此之前第1,2,3页已经缓存在内存中，该进程所分配到的3个页帧已满，为此必须替换掉一页，才能把第四页加载进来，此时又发生一次缺页故障。由于采用FIFO替换算法，因为第一页是最先进来，所以它会被替换出去
4. 接下来又要访问第一页，由于当前缓存页时第4、2、3页，从而根据FIFO，要将第2页替换为第1页，这就又发生一次缺页中断，调入第1页后，此时存在于内存中的是第4、1、3页。同理，接下来要访问第2页，发生一次缺页中断，将第3页替换为第2页，此时存在于内存中的是第4、1、2页。
5. 在接下来的访问中，如果第K页已经存在内存中，则直接使用，所以此时不会发生缺页故障，重复按照上述过程，我们可以得到如下示例图表

红色标识出的是发生缺页故障后调入的页，可以看见共发生9次缺页异常，而从访问串可知访问12次，所以缺页率为9/12=0.75。

现在，该进程在上述3页帧的基础上多分配一页帧，也就是变成四页帧，则仿照上述分析过程，可画出如下图表

红色标识出的是发生缺页故障后调入的页，蓝色标识的是之前调入的页面，可以看见共发生10次缺页异常，而从访问串可知访问12次，所以缺页率为10/12=0.833。

FIFO替换算法产生该现象的原因是它没有考虑到程序执行的动态特征。

本文原文来自CSDN