OS之页面置换算法

目录

 

一、最佳置换算法(OPT)

定义

案例

二、先进先出置换算法(FIFO)

定义

案例

FIFO特有的异常

三、最近最久未使用置换算法(LRU)

定义

案例

四、时钟置换算法(CLOCK)

定义

案例

五、改进型的时钟置换算法

定义

案例

---

 

一、最佳置换算法(OPT)

定义

每次选择淘汰的页面将是以后永不使用，或者在最长时间内不再被访问的页面，这样可以保证最低的缺页率

案例

 过程中缺页中断发生了9次，页面置换发生了6次。

注:缺页时未必发生页面置换。若还有可用的空闲内存块，就不用进行页面置换。

优缺点:性能好，但无法实现

二、先进先出置换算法(FIFO)

定义

每次选择淘汰的页面是最早进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰

案例

过程中缺页中断发生了9次，页面置换发生了6次

FIFO特有的异常

Belady异常:当为进程分配的物理块数增大时，缺页次数不减反增的异常现象

优缺点

算法实现简单，但算法性能差

三、最近最久未使用置换算法(LRU)

定义

每次淘汰的页面是最近最久未使用的页面

案例

 优缺点

算法性能好，但实现起来需要专门的硬件设备，算法开销大

四、时钟置换算法(CLOCK)

定义

当某页被访问时，其访问位置为1。当需要淘汰一个页面时，只需检查页的访问位。如果是0，就选择该页换出:如果是1，则将它置为0，暂不换出，继续检查下一个页面，若第一轮扫描中所有页面都是1，则将这些页面的访问位依次置为0后，再进行第二轮扫描(第二轮扫描中一定会有访问位为0的页面，因此简单的CLOCK 算法选择一个淘汰页面最多会经过两轮扫描)

案例

 

 

 

 

五、改进型的时钟置换算法

定义

在简单的时钟置换算法的基础上，增加一个修改位(修改位为0，代表页面没有被修改过；修改位为1，代表页面被修改过)，淘汰一个页面最多会进行四轮扫描

案例