操作系统虚拟存储器

操作系统虚拟存储，包含概述、请求分页存储方式、页面置换算法、请求分段存储方式、工作集、多道程序与抖动、访问内存有效时间等。

虚拟存储器

• 应用程序在运行之前没有必要把进程全部装入内存。将那些当前运行的少数页面装入内存，其他的放到辅存中。程序运行时，若需要的信息不在主存，则再调入。 实质：以时间换空间，但是时间的牺牲不大
• 概述
  • 局部性原理
    • 在一个较短的时间内，程序的执行仅限于某个部分。相应地，程序所访问的存储空间也局限于某个区域时间局限性：一条指令在短时间内多次被访问(存在大量的循环操作)空间局限性：某个存储单元在不久以后还会被访问
  • 优点(2条)
    • 用户编程序时可不必考虑内存容量的限制增加了系统的利用率和吞吐量。
  • 特征(4条)
    • 多次性：作业分多次调入内存对换性：作业可以按需要换进换出虚拟性：从逻辑上扩充内存，但是内存实际大小没变离散性：一页的方式换进换出虚拟性以多次性和对换性为基础，多次性和对换性以离散性为基础
  • 实现方法(2条)
    • 分页请求系统实现技术：分页、请求调页、页面置换硬件支持页表机制：数据结构缺页中断机构：请求OS调入缺页。地址变换机制：OS调入置换页软件支持实现调页和页面置换算法请求分段系统(类似于分页请求系统)
• 请求分页存储方式
  • 要解决的问题(3个)
    • 怎么知道当前页面不在主存缺页时，从哪里调入主存满了的时候，把什么旧页调出
  • 页表机制
    • 状态位：表示他在不在内存，外存地址就是他在外存的地址。访问字段：为访问次数(局部性原理)修改位：(是否修改)，若没有修改，就不需要再加入磁盘(外存就不用改)，直接覆盖就行了。
  • 缺页中断机构
    • 访问的页面不存在，产生缺页中断，请求OS将所缺页面调入内存。中断过程：保护CPU环境分析中断原因(页不在主存)转入缺页中断程序——处理中断、恢复CPU环境一条指令执行时会产生多次缺页中断。
  • 地址变换机构
  • 内存分配
    • 最小物理块数取决于指令格式、功能、寻址方式块数过小，缺页率较高块数过大，资源浪费较多内存的分配和置换策略内存分配固定分配(分配大小不变)可变分配策略(多了一个空闲物理块的链表，物理块少了，就将链表中的物理块分配它。多了就将其多的物理块放到空闲物理块链表里)置换全部置换局部置换组合后的策略固定分配局部置换：缺页时将内存中的其它页换出，再调入所需页，保证整体内存空间不变。可变分配全局置换：为每一个进程分配一定数量的物理块。缺页时OS从空闲物理块队列中取出一块给进程。物理块分配完后，从内存选择一个页调出可变分配局部置换：缺页时只允许从该进程在的页面选一页调出，不影响其他进程的运行。物理块的分配算法平均分配比例分配考虑优先权的分配
  • 页面调入策略
    • 从何处调入页面
      • 系统拥有足够的对换区空间(将进程有关文件拷贝到对换区中)系统缺少足够的对换区空间(对于未修改的则不必将他们换出，对于修改过的，在将它们换出时，需要将他们调到对换区)
    • 页面调入过程
      • 缺页时向CPU发送缺页中断。中断程序保留CPU环境，分析中断原因，转入缺页中断处理程序。中断程序查找页表，得到该页在外存中的物理块后。若内存中还能放得下，直接启动磁盘，将其调入内存若内存已满，则按照置换算法，将旧页换出。若旧页未被修改，则直接覆盖，若修改了，则将旧页写回磁盘。
    • 缺页率
      • 总访问次数A=S+F(S访问成功次数、F访问不成功次数)缺页率：f=F/A(不成功访问次数/总访问次数)
• 页面置换算法
  • 使用页面置换算法的原因
    • 减少对换量，提高系统性能。抖动现象：进程频繁换页(刚换出就换入)
  • 最佳置换法
    • 将永久不再使用/较长时间内不再使用的页面置换出去。此算法，缺页率低。理论上的，不能实现，但可以将其作为置换算的的衡量标准。 页面置换次数：6。缺页数为6，缺页率为6/20。
  • 先进先出FIFO
    • 使用队列页面调入的先后并不能反映实际的情况。(有些先进入的可能之后马上又要访问)。所以缺页率较高，性能较差 缺页次数：12
  • 最近最久未使用LRU
    • 利用最近的过去，作为最近的将来的近似。最近使用的在一段时间内还可能使用。性能较好。选择最近最久未使用的作为淘汰。缺页次数：9 所需要的硬件支持：寄存器：用数值的大小作为标准(如进程1就为81，进程3为6)，把数值小的换出(将进程3换出去)。每隔一段时间就往右移动一个(高位R7就补0)。刚访问完一个进程的就将其最高为置为1。栈：
  • 最少使用LFU
    • 一段时间内的使用频率最小的换出去(如将LRU的寄存器那个图中1最少的进程移出去)。但是有些最近才访问过但是它的频率最低(如R7为1，其它都为0)，也要被换出，不符合局部性原理(最近使用的在将来还可能使用)。
  • clock置换算法
    • LRU近似算法，硬件消耗少。所用的是一个循环链表(含有页号、块号、访问位、指针),如果当前位置的访问位为1，则将其设为0，再访问下一位。直到找到一个访问位为0 的将其移出。例如链表：1——1——1——1。第一个为1，说明最近访问过，然后将其访问为设为0，再向后寻找，又为1，将其设为0，寻找下一位，直至寻找到最后一位都没有找到访问位置为0的。(找完一次之后链表变为0——0——0——0)。因为是循环链表，访问完最后一个，就开始访问第一个，第一个的访问位在之前被设置为0，所以将其移出。但是有些页面是修改过的，移出之后还要访问磁盘(刷新那个值)。而这个方法没有注意到修改的这一情况。
  • 改进的clock置换算法
    • 添加一个修改位。则就有四种情况：访问位：0，修改位：0访问位：0，修改位：1访问位：1，修改位：0访问位：1，修改位：1第一轮先找访问位为0，修改位为0的。此轮不修改访问位。第二轮寻找访问位为0，修改位为1的。此轮将所有访问位为1的置为0。之后所有的三四类(访问位=1)就转变为一二类。这样最多还要经过两轮才找到可置换的页。可能经过几轮扫描(最多四次)，才找到可置换的页，算法本身开销增加。
  • 页面缓冲置换算法PBA
    • 系统设立空闲页面链表(空闲物理块)和已修改页面链表。被淘汰的页先不做物理移动，而是将其挂在空闲页面链表(未修改的)或已修改页面链表(已修改的)的末尾。当已修改的页面链表到达一定长度的时候就将其一起写回磁盘。故减少了写回磁盘的频率。当又要读的时候，直接在之前两个链表中寻找，找到之后就直接读入。降低了读入内存的频率。
  • 影响页面换进换出效率的因素(3个)
    • 页面置换算法写回磁盘的频率读入内存的频率减少写回磁盘的频率和读入内存的频率
• 访问内存有效时间
  • 有效时间=(1-p)* 访存时间+p *缺页中断时间p为缺页率。缺页中断时间：缺页中断服务时间+缺页读入时间+进程重执行时间
• 多道程序与抖动
  • 当进程增加，CPU饱和度增加。增加到一定程度的时候CPU利用率到达最大值。然后再增加进程，因为进程数增多，所以CPU分配给每一个进程的页面减少，进程的缺页率增加，缺页的进程就被阻塞，等待资源的分配。部分CPU就空闲了，CPU的利用率就下降了。
• 工作集
  • 引入：如果能预知程序在某段时间间隔内要访问哪些页面，并将其调入内存，就会大大降低缺页率。工作集：某段时间间隔里，进程实际所要访问页面的集合。把进程再某段时间间隔Δ里，再时间t的工作集记为w(t,Δ)，Δ为窗口尺寸。
• 预防抖动的方法(4个)
  • 采用局部置换策略从自身进程获取物理块，即使发生抖动也不影响其它进程把工作集算法融入到处理机调入中利用“L=S”准则调入算法L为缺页之间的平均时间s为平均缺页服务时间L>>S时很少缺页，磁盘没有充分利用。L<<S时频繁缺页，磁盘负荷太重。L=S时处于最佳位置选择暂停某些进程。
• 请求分段存储方式
  • 段表机制
  • 缺段中断机制
    • 需要判断空间容量总和是否满足
  • 地址变换机构
  • 共享段表
  • 共享段的分配与回收
    • 第一次调用的段为共享段分配物理区将段调入内存将始址填入段表count=1第二次调用的段调用进程的段表中增加一个表项在表项中填写共享段的物理地址在共享段的段表中填入进程名、存取控制count=count+1回收count=count-1将进程段表中的表项删除最后一个进程都不再使用该共享段，则将物理区回收