页面置换算法

旧城等待， 2023-02-16 06:35 1阅读 0赞

视频链接：

[https://www.bilibili.com/video/BV1YE411D7nH?p=45][https_www.bilibili.com_video_BV1YE411D7nH_p_45]

**请求分页与基本分页的区别：**

在程序执行过程中，但所访问的信息不再内存时，由操作系统负责将所需信息从外存调入内存，任何执行程序，如果内存空间不足，由操作系统（页面置换算法）负责将内存中暂时用不到的信息换到外存中。

注：好的页面算法追求更少的缺页率。

**一，最佳置换算法（OPT）：**

优先淘汰最长时间内不会被访问的页面，缺页率小，性能最好，但无法实现

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDg0MTMxMg_size_16_color_FFFFFF_t_70][]

**二，先进先出置换算法（FIFO）：**

优先淘汰最先进入内存的页面，实现简单，性能最差，可能出现Belady异常

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDg0MTMxMg_size_16_color_FFFFFF_t_70 1][]

**三，最近最久未使用置换算法（LRU）：**

优先淘汰最久没访问的页面，性能很好，但需要硬件支持，算法开销大

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDg0MTMxMg_size_16_color_FFFFFF_t_70 2][]

**四，时钟置换算法（CLOCK）：**

循环扫描各个页面，第一轮淘汰访问位位0的，并将扫描后的页面访问位改为1 ，如果第一轮没选中，就进行第二轮扫描。实现简单，算法开销小，但未考虑页面是否修改过

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDg0MTMxMg_size_16_color_FFFFFF_t_70 3][]

**五，改进型的时钟置换算法：**

如果用（访问位，修改位）表示，则第一轮淘汰（0,0），第二轮淘汰（0,1），并将扫描过的页面访问位都至于0，第三轮淘汰（0,0），第四轮淘汰（0,1）。算法开销小，性能也不错。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDg0MTMxMg_size_16_color_FFFFFF_t_70 4][]

[https_www.bilibili.com_video_BV1YE411D7nH_p_45]: https://www.bilibili.com/video/BV1YE411D7nH?p=45
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDg0MTMxMg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200608234151102.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDg0MTMxMg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDg0MTMxMg_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200608234218551.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDg0MTMxMg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDg0MTMxMg_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200608234228699.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDg0MTMxMg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDg0MTMxMg_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200608234237777.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDg0MTMxMg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDg0MTMxMg_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200608234250693.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDg0MTMxMg==,size_16,color_FFFFFF,t_70