《逆袭进大厂》第六弹之操作系统汇总篇 | OS一次性更完

大家好，我是阿秀。

本期是操作系统午餐.....

算了吃啥午餐啊，我直接放大招，把我自己整理的所有操作系统八股文一次性放出来给大家好了！

也有小伙伴说 PC 端在线背看八股文感觉太难受，emmm 我思考了一下，那直接把 PDF 给大家吧，这样大家可以下载下来在本地看不是美滋滋

~

“本期八股文问题答案的 PDF 版本领取方式在文末。另外本期内容已同步至 github 仓库，欢迎大家 star。 仓库地址：https://github.com/forthespada/InterviewGuide

先把剩下的操作系统题目给大家看一下吧。大家不用担心质量硬不硬，质量跟前几篇一样硬，不信可以点击下方链接翻一下前面的几篇看一看

。

《逆袭进大厂全系列》

下面是剩下的 43 道操作系统常见问题，我挑其中的第57、可能是最全的页面置换算法总结了问题的整理出来给大家看一下吧。

22、操作系统经典问题之哲学家进餐问题

23、操作系统经典问题之读者-写者问题

24、介绍一下几种典型的锁

25、逻辑地址 VS 物理地址

26、怎么回收线程？有哪几种方法？

27、内存的覆盖是什么？有什么特点？

28、内存交换是什么？有什么特点？

29、什么时候会进行内存的交换？

30、终端退出，终端运行的进程会怎样

31、如何让进程后台运行

32、什么是快表，你知道多少关于快表的知识？

33、地址变换中，有快表和没快表，有什么区别？

35、 守护进程、僵尸进程和孤儿进程

36、如何避免僵尸进程？

37、局部性原理你知道吗？主要有哪两大局部性原理？各自是什么？

38、父进程、子进程、进程组、作业和会话

39、进程终止的几种方式

40、Linux中异常和中断的区别

41、Windows和Linux环境下内存分布情况

42、一个由C/C++编译的程序占用的内存分为哪几个部分？

43、一般情况下在Linux/windows平台下栈空间的大小

44、程序从堆中动态分配内存时，虚拟内存上怎么操作的

45、常见的几种磁盘调度算法

• 先来先服务
• 最短寻道时间优先
• 电梯扫描算法

46、交换空间与虚拟内存的关系

47、抖动你知道是什么吗？给你个提示它也叫颠簸现象

48、从堆和栈上建立对象哪个快？（考察堆和栈的分配效率比较）

49、常见内存分配方式有哪些？

50、常见内存分配内存错误

51、内存交换中，被换出的进程保存在哪里？

52、在发生内存交换时，有些进程是被优先考虑的？你可以说一说吗？

53、ASCII、Unicode和UTF-8编码的区别？

54、原子操作的是如何实现的

55、内存交换你知道有哪些需要注意的关键点吗？

56、系统并发和并行，分得清吗？

57、可能是最全的页面置换算法总结了

• 最佳置换法(OPT)
• 先进先出置换算法(FIFO)
• 最近最久未使用置换算法(LRU)
• 时钟置换算法(CLOCK)
• 改进型的时钟置换算法
• 总结

58、共享是什么？

59、死锁相关问题大总结，超全！

• 死锁产生原因
• 死锁演示
• 死锁的解决方案
• 死锁必要条件
• 处理方法
• 死锁恢复
• 死锁预防
• 死锁避免

60、为什么分段式存储管理有外部碎片而无内部碎片？为什么固定分区分配有内部碎片而不会有外部 碎片？

61、内部碎片与外部碎片

62、如何消除碎片文件

57、可能是最全的页面置换算法总结了

1、最佳置换法(OPT)

最佳置换算法(OPT，Optimal) :每次选择淘汰的页面将是以后永不使用，或者在最长时间内不再被访问的页面，这样可以保证最低的缺页率。

最佳置换算法可以保证最低的缺页率，但实际上，只有在进程执行的过程中才能知道接下来会访问到的是哪个页面。操作系统无法提前预判页面访问序列。因此，最佳置换算法是无法实现的

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

先进先出置换算法(FIFO) :每次选择淘汰的页面是最早进入内存的页面 实现方法:把调入内存的页面根据调入的先后顺序排成一个队列，需要换出页面时选择队头页面队列的最大长度取决于系统为进程分配了多少个内存块。

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

只有 FIFO 算法会产生 Belady 异常，而 LRU 和 OPT 算法永远不会出现Belady异常。另外，FIFO算法虽然实现简单，但是该算法与进程实际运行时的规律不适应，因为先进入的页面也有可能最经常被访问。因此，算法性能差

FIFO的性能较差，因为较早调入的页往往是经常被访问的页，这些页在 FIFO 算法下被反复调入和调出，并且有Belady现象。所谓Belady现象是指：采用 FIFO 算法时，如果对—个进程未分配它所要求的全部页面，有时就会出现分配的页面数增多但缺页率反而提高的异常现象。

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

最近最久未使用置换算法(LRU，least recently used) :每次淘汰的页面是最近最久未使用的页面 实现方法:赋予每个页面对应的页表项中，用访问字段记录该页面自.上次被访问以来所经历的时间t(该算法的实现需要专门的硬件支持，虽然算法性能好，但是实现困难，开销大)。当需要淘汰一个页面时，选择现有页面中t值最大的，即最近最久未使用的页面。

LRU性能较好，但需要寄存器和栈的硬件支持。LRU是堆栈类算法，理论上可以证明，堆栈类算法不可能出现Belady异常。

在手动做题时，若需要淘汰页面，可以逆向检查此时在内存中的几个页面号。在逆向扫描过程中最后一个出现的页号就是要淘汰的页面。

4、时钟置换算法(CLOCK)

最佳置换算法性 OPT 能最好，但无法实现；先进先出置换算法实现简单，但算法性能差；最近最久未使用置换算法性能好，是最接近 OPT 算法性能的，但是实现起来需要专门的硬件支持，算法开销大。

所以操作系统的设计者尝试了很多算法，试图用比较小的开销接近 LRU 的性能，这类算法都是 CLOCK 算法的变体，因为算法要循环扫描缓冲区像时钟一样转动。所以叫clock算法。

时钟置换算法是一种性能和开销较均衡的算法，又称 CLOCK 算法，或最近未用算法(NRU，Not Recently Used)

简单的 CLOCK 算法实现方法:为每个页面设置一个访问位，再将内存中的页面都通过链接指针链接成一个循环队列。

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

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

简单的时钟置换算法仅考虑到一个页面最近是否被访问过。事实上，如果被淘汰的页面没有被修改过,就不需要执行I/O操作写回外存。只有被淘汰的页面被修改过时，才需要写回外存。

因此，除了考虑一个页面最近有没有被访问过之外，操作系统还应考虑页面有没有被修改过。在其他条件都相同时，应优先淘汰没有修改过的页面，避免I/O操作。这就是改进型的时钟置换算法的思想。修改位=0，表示页面没有被修改过;修改位=1，表示页面被修改过。

为方便讨论，用(访问位，修改位)的形式表示各页面状态。如(1, 1)表示一个页面近期被访问过，且被修改过。

改进型的Clock算法需要综合考虑某一内存页面的访问位和修改位来判断是否置换该页面。在实际编写算法过程中，同样可以用一个等长的整型数组来标识每个内存块的修改状态。访问位A和修改位M可以组成一下四种类型的页面。

算法规则:将所有可能被置换的页面排成一个循环队列

• 第一轮:从当前位置开始扫描到第一个(A =0, M = 0)的帧用于替换。表示该页面最近既未被访问，又未被修改，是最佳淘汰页
• 第二轮:若第一轮扫描失败，则重新扫描，查找第一个(A =0, M = 1)的帧用于替换。本轮将所有扫描过的帧访问位设为0。表示该页面最近未被访问，但已被修改，并不是很好的淘汰页。
• 第三轮:若第二轮扫描失败，则重新扫描，查找第一个(A =1, M = 0)的帧用于替换。本轮扫描不修改任何标志位。表示该页面最近已被访问，但未被修改，该页有可能再被访问。
• 第四轮:若第三轮扫描失败，则重新扫描，查找第一个A =1, M = 1)的帧用于替换。表示该页最近已被访问且被修改，该页可能再被访问。

由于第二轮已将所有帧的访问位设为0，因此经过第三轮、第四轮扫描一定会有一个帧被选中，因此改进型CLOCK置换算法选择- -个淘汰页面最多会进行四轮扫描

算法规则：将所有可能被置换的页面排成一个循环队列 第一轮:从当前位置开始扫描到第-一个(0, 0)的帧用于替换。本轮扫描不修改任何标志位。(第一优先级:最近没访问，且没修改的页面) 第二轮:若第一轮扫描失败，则重新扫描，查找第一个(0, 1)的帧用于替换。本轮将所有扫描过的帧访问位设为0 (第二优先级: 最近没访问，但修改过的页面) 第三轮:若第二轮扫描失败，则重新扫描，查找第一个(0, 0)的帧用于替换。本轮扫描不修改任何标志位(第三优先级:最近访问过，但没修改的页面) 第四轮:若第三轮扫描失败，则重新扫描，查找第一个(0, 1)的帧用于替换。(第四优先级:最近访问过，且修改过的页面) 由于第二轮已将所有帧的访问位设为0，因此经过第三轮、第四轮扫描一定会有一个帧被选中，因此改进型CLOCK置换算法选择一个淘汰页面最多会进行四轮扫描。

6、总结

公众号后台回复逆袭进大厂即可拿到最新版的 PDF 啦，我会不断坚持更新第 3 版、第 4 版，直到第 N 版的。

巨人的肩膀

1. https://www.baidu.com/
2. https://www.csdn.net/

往期推荐

1、《逆袭进大厂》第五弹之操作系统开胃菜(附前四期PDF下载方式)

2、《逆袭进大厂》第四弹之C++重头戏STL30问30答

—END—

小伙伴你好，我是阿秀，一个菜逼程序员

。公众号后台回复「宝贝」，送你一个宝贝！真的是宝贝！