Skip to content

Latest commit

 

History

History
70 lines (38 loc) · 2.71 KB

04-2-spoc-discussion.md

File metadata and controls

70 lines (38 loc) · 2.71 KB

#lec9: 虚存置换算法spoc练习

视频相关思考题

9.1 页面置换算法的概念

  1. 设计置换算法时需要考虑哪些影响因素？如何评判的好坏？

  2. 全局和局部置换算法的不同？

9.2 最优算法、先进先出算法和最近最久未使用算法

  1. 最优算法、先进先出算法和LRU算法的思路？

9.3 时钟置换算法和最不常用算法

  1. 时钟置换算法的思路？

  2. 改进的时钟置换算法与时钟置换算法有什么不同？

  3. LFU算法的思路？

9.4 Belady现象和局部置换算法比较

  1. 什么是Belady现象？如何判断一种置换算法是否存在Belady现象？

  2. 请证明LRU算法不存在Belady现象。

9.5 工作集置换算法

  1. CPU利用率与并发进程数的关系是什么？

  2. 什么是工作集？

  3. 什么是常驻集？

  4. 工作集算法的思路？

9.6 缺页率置换算法

  1. 缺页率算法的思路？

9.7 抖动和负载控制

  1. 什么是虚拟内存管理的抖动现象？

  2. 操作系统负载控制的最佳状态是什么状态？

  3. 局部置换算法（如FIFO, LRU等）是否能作为全局置换算法来使用？为什么？

扩展思考题

  1. 改进时钟置换算法的极端情况: 如果所有的页面都被修改过了，这时需要分配新的页面时，算法的performance会如何？能否改进在保证正确的前提下提高缺页中断的处理时间？

  2. 如何设计改进时钟算法的写回策略?

  3. （spoc）根据你的学号 mod 4的结果值，确定选择四种页面置换算法（0：LRU置换算法，1:改进的clock 页置换算法，2：工作集页置换算法，3：缺页率置换算法）中的一种来设计一个应用程序（可基于python, ruby, C, C++，LISP等）模拟实现，并给出测试用例和测试结果。请参考如python代码或独自实现。

  1. 请判断OPT、LRU、FIFO、Clock和LFU等各页面置换算法是否存在Belady现象？如果存在，给出实例；如果不存在，给出证明。

  2. 了解LIRS页置换算法的设计思路，尝试用高级语言实现其基本思路。此算法是江松博士（导师：张晓东博士）设计完成的，非常不错！