操作系统笔记9

虚拟内存

虚拟内存允许程序执行时只将一部分程序放入内存中，因此程序允许比物理内存大

虚拟内存的优点

  1. 程序可以比物理内存大
  2. 程序员不必担心内存的限制
  3. 每个程序使用了更少的物理内存，因此更多的程序可以同时执行，CPU利用率也增加

页式虚存

一个页面在被访问时，才调入内存

页表表目扩充时的有效位：

  1. 先全设置成无效（i），调入页面时设置成有效
  2. v：有效，页面在内存中
  3. i：无效，欲访问的位置是无效位，或者页面有效但不在内存中，引发缺页中断。

页表表目扩充：修改位和访问位：

  1. 页面置换时，被置换出去的内存要写回硬盘中
  2. 修改位为0：页面没有被修改，可以直接撤销而无需回写
  3. 修改位为1：页面被修改过，撤销的时候需要回写
  4. 访问位：记录上次访问该页面的时钟值

页面的置换

  1. 缺页中断
  2. 从磁盘找到对应页的位置
  3. 在内存中找一个页框：
    • 有空闲的，直接使用
    • 无空闲的，利用页面置换算法找一个页面撤销
  4. 写入，然后重新回到程序

页面置换算法（针对局部置换）

局部置换和全局置换

  • 局部置换：每个进程在页面置换时仅仅能从自己分配到的页框中选择位置
  • 全局置换：可以从其他的进程拿到页框

FIFO，先进先出算法

哪个页面最先进来，就最先把它置换掉

可以用队列来实现

考察以下情况：

  • 优点：简单，容易实现
  • 缺点：效率低，而且随着可用页框增多，缺页次数可能会增多（称Belady异常）

最优置换

将不再使用的，或者最长时间不会使用的页置换掉，确保了缺页次数是最低的

无法实现，该算法作为一个指标，提供了比较依据

最近最少使用算法 LRU

选择最长时间没有使用的页置换掉

访问位构建：

  1. counter计数器：优点：精确得知最晚访问的时间 缺点：密集访问(每次访问都要改)，谁是最老需要遍历
  2. 堆栈：其实是双向链表（下图），顶部最新鲜，底下LRU，但可能每次要更新多个指针

近似LRU算法

很少有计算机能提供足够的硬件来支持LRU算法，因此要采用近似LRU算法

附加引用位算法：

可以在位于内存的页中保留一个8字节，每隔一定的时间间隔，把引用位移动到8字节的高位，其他位向右移动一位，抛弃最低位。这样，8字节就记录了最近8个时间周期内页的访问情况，置换时，把8字节当成无符号整数，取最小的置换即可

二次机会算法

当要置换一个页时，检查其引用位，如果为1，那么给它第二次机会，并将引用位置0，如果为0，直接置换。

页框的分配

  1. 平均分配：每个作业获得的页框数一样多
  2. 按比例分配：
    • si：第i个进程所需的页数
    • S：si求和
    • m：内存的总页框数
    • ai=（si/S ）X m，分配到的数量，最后在分配时可能有一定的调整

系统抖动/颠簸

当一个进程拿到的页框数不足时：

  1. 缺页率较高
  2. CPU利用率降低：缺页—>自陷—>入Waiting等待I/O从外存拿页—>回Ready
  3. 系统认为需要增加道数
  4. 出现更多的缺页错误，形成抖动