学习笔记-操作系统虚拟内存篇

内存管理问题：

• 如何进行内存分配如何管理空闲内存
  • 如何找到合适的内存空闲块给进程使用？使用什么算法？
  • 使用合种方式对内存进行管理？
• 如何处理内存碎片
• 内存交换技术
  • 解决什么问题，很明显解决程序所需内存大于内存的大小
  • 优点，局部性，可以不需要一次把所有的程序load到内存
  • 缺点，很明显，由于磁盘的读写速度的限制，当程序增大时会整个交换技术会变的很慢
• 虚拟内存
  • 虚拟内存的概念，说直白点是对物理内存的一个管理
  • 解决什么问题
    • 多个进程在内存中共存的问题，因为采用虚拟化的技术，操作的不再是具体的物理内存。这样其实中间多了一层映射。如果两个进程中有操作同一个内存地址就变的容易。
  • MMU，内存管理单元
  • 缺页中断
    • • 为什么会发生缺页中断?
        • 由于虚拟内存往往会比实际的物理物理内存大，所以一定会有一部分的虚拟内存找不到物理内存的映射。这样当访问虚拟内存地址时就会找不到相应的物理内存地址，就发生了缺页中断。
  • 使得转换检测缓冲区（TLB）
    • 这种设计是基于怎么样的考虑
    • 如何提高TLB的命中率
      • 预装载
  • 虚拟内存的映射算法
    • 页框+偏移量
  • 对虚拟内存的散列
    • 这样维护一个虚拟内存到物理内存的映射表，通过查找虚拟内存就可以定位到物理内存
  • 对物理内存的散列
    • 当系统是64位的时候，虚拟地址空间是2⁶⁴,这样整个虚拟地址对应物理地址的映射表会变的很大。这个时候就需要使用倒排页表。不过问题很明显，需要搜索。
      
  • 页面转换算法
    • 这里有一些需要思考的点：1）具体的转换策略，当发生缺页中断时是采用何种置换。2）是转换进程本身的页面，还是可以转换其他进程的页面。
  • 具体的页面置换策略：
  • 最优页面置换算法：这种算法是是根据当前页面之后被访问的时间来判断频率来判断把哪些页面置换出，而现实情况是无法对将来进行判断，只能“机器学习”对过去的一些数据进行总结来作判断。所有这种置换算法并不实用。
  • 最近未使用页面算置换算法（NRU）：两个状态位，一个R位，一个M位。当页面被访问时设置R位，当页面被修改时设置M位。定期的对R位进行清零操作。
  • 先进先出（FIFO）算法：维护一个页面的链表。最新页面进入表尾，当链表满的时候淘汰表头的页面，这样链表是一个动态的，表尾的页面逐渐向表头移动。如果单纯采用这种算法，一些被常用的页面也同样很容易被淘汰。
  • 第二次机会页面置换算法：这上算法是对FIFO算法的一次改进，根据在一个时钟周期内是否有过访问（R位可以判断，前面NRU算法中有讲）来判断是否淘汰该页面。如果不淘汰该页面则把该页面放入表尾，并清除R位。这里非常有意思，为什么要清除R位，假设不清除R位，后果会是什么，如果链表中的页面在一个时钟周期内都被访问过，那么至少在下一个时钟周期之前会出现死循环。
  • 时钟页面置换算法：这个算法和第二次机会页面转换算法类似，只是有一些策略的实现不同，在第二次机会页面置换算法中会涉及到比较多的页表移动，这样相对会比较耗时。
  • 最近最少使用页面置换算法（LRU）：
    • 实现代价高昂，需要动态维护整个链表，在页表移动的过程中还是相当耗时的。
    • 硬件实现LRU算法
      
      • 有n个页框，n x n的矩阵（这里原理和上面所讲的置换算法类似），每个表格中用0或1填充，当访问第k个页框时，k行的位都置为1，而第k列都设为0。这里和上面说的设置R，M很类似。最后根据行的位二进制大小来排序。
    • 软件实现LRU算法（老化算法）
      • 用一个有限位的计数器记录，比如说8位计数，首先把计数器右移一位，然后把R值加到计数器的最高位。当发生缺页中断时只需要置换计数值最小的页。
      • 和LRU算法的算法的区别
        • 严格的来讲LRU算法是只需要有访问则其优先级就是最高。而老化算法则在一个时钟周期内无法判断哪个页面前被访问，哪个页面后被访问。但是其基本思想是一样的。
        • 另外一个区别是计数器的有限位限制了历史数据的保存，比如说8位计数器，在9个时钟周期之前被访问和1000个时钟周期之前被访问是无法被区分的。这里基本上会基于二八原则处理。
      工作集页面置换算法
      • 实现起来开销很大
    • 工作集时钟页面置换算法
      • 对工作集页面置换算法的改进