贝拉迪的异常

2021-01-15 20:31:02

跳转至导航跳转至搜索贝拉迪异常的一个例子。使用三个页面框架,将发生九个页面故障。增加到四个页面框架会导致十个页面错误发生。页面错误显示为红色。可以认为这是" Penny Wise,Pound Foolish"行为。

在计算机存储中,贝拉迪的异常是一种现象,其中增加页帧数导致某些内存访问模式的页错误数增加。使用先进先出(FIFO)页面替换算法时,通常会遇到这种现象。在FIFO中,页面错误可能会随着页面帧的增加而增加,也可能不会增加,但是在最优和基于堆栈的算法(如LRU)中,随着页面帧的增加,页面错误会减少。拉斯洛·贝拉迪(LaszlóBélády)在1969年证明了这一点。[1]

在常见的计算机内存管理中,信息以特定大小的块加载。每个块称为页面。主内存一次只能容纳有限数量的页面。可以加载的每个页面都需要一个框架。当找不到页面时发生页面错误,可能需要将其从磁盘加载到内存中。

当发生页面错误并且所有框架都在使用中时,必须清除一个框架以为新页面腾出空间。 FIFO是一种简单的算法:帧中的哪一页最长,就是被清除的那一页。在证明贝拉迪(Bélády)异常之前,人们认为页面框架数量的增加将始终导致相同数量或更少的页面错误。

Bélády,Nelson和Shedler构建了参考字符串,对于这些参考字符串,FIFO页面替换算法在较大的内存中产生的页面错误几乎是较小内存中的两倍,并且他们推测2是一般界限。

在2010年,Fornai和Iványi证明了该异常实际上是不受限制的,并且可以为任何任意页面错误率构造一个参考字符串。

^克里斯托弗·克鲁格(2012年12月3日)。 "操作系统(CS170-08课程)" (PDF)。 cs.UCSB.edu。 (原始内容存档于(PDF)2016年8月10日)。