（八）操作系统-虚拟存储管理

虚拟存储系统的基本概念

实存管理技术特点

在作业运行时，整个作业的逻辑地址空间必须全部装入主存；
当作业尺寸大于主存可用空间时，该作业就无法运行。

虚拟存储器

一种实际上并不以物理形式存在的虚假的存储器；

把被运行进程访问的地址同主存的物理地址区别开来；

一个程序被编译连接后产生目标程序，该目标程序所限定的地址的集合称为逻辑地址空间，目标程序中指令和数据放置的位置称相对地址或逻辑地址；

而CPU能直接访问的主存称为物理地址空间或实存地址空间；

虚拟地址

运行进程访问的地址；

实地址

处理器可直接访问的主存地址；

虚拟地址空间

运行进程可以访问的虚地址的集合；

实地址空间

计算机的主存；

由动态地址映象机构来完成虚地址到实地址的转换；

虚实地址的区分，为使进程的虚拟地址空间大于主存实地址空间创造了条件，也为作业大小可大于主存空间创造了条件。

虚存管理技术

在虚拟存储系统中，用户认为机器具有无穷大的存储空间，并且只有这一个用户在使用机器；

用户只使用了物理主存的很少部分；

原因：操作系统内核只把进程当前要用的部分放在主存中，不仅能减少进程启动和滚进滚出的开销，而且主存中也可以同时容纳大量的进程，提高了系统多道程度和并行性；

代价：

主存管理要为地址转换表和其他一些数据结构付出额外的主存开销；
地址转换增加了每条指令的执行时间。

常用虚存管理技术

分页技术（paging）
分段技术（segmentation）
分段加分页技术（segmentation with paging）

分页系统地址映象技术

分页系统主要目的：让程序能在它的虚拟地址空间中运行并实现由虚拟地址到主存物理地址的转换；

几种地址转换方法

直接映象的页地址转换
多级页表的地址转换
反向页表的地址转换
快表的地址转换

直接映象的页地址转换

实现过程

当进程被调度到处理器上运行时，操作系统自动将该进程的页表起始地址装入页表地址寄存器中；
当该进程要访问某个虚地址时，分页的地址映象硬件自动按页面大小将地址场从某位起截成页号和页内地址两部分；
以页号为索引查找页表（查找工作由硬件自动进行），得到页架号，进而得到实际主存的绝对地址。

该映象技术对系统效能的影响

影响了处理器执行指令的速度，使速度降低为原来的一半；
原因：CPU至少要访问两次主存才能存取到所要数据，第一次查页表以找出对应的页架号，第二次真正访问所需数据

多级页表的地址转换

因为大页表不能全放在主存中，所以对页表本身也采取分页措施，把页表本身按固定大小分成一个个页面；

通过二级页表的地址映射访问主存存取数据需要三次访问主存，所需时间是原来的三倍；

一次页目录
一次页表
数据所在的物理地址

反向页表的地址转换

实现过程

当给出进程的虚地址后，存储管理单元通过一个哈希定位表数据结构，把虚页号经哈希函数转换为一个哈希值；
以该哈希值为索引，它指向反向页表中的一个表目；
由该表目中的虚页号得到相应的页架号，再与偏移量拼接成物理地址，访问主存。

快表的地址转换

把一部分常用页表表目放入高速缓冲中，通过快表进行地址映射，快表中只包含一些最近使用的页表的表目；

快表的访问速度比主存的访问速度高一个数量级；

快表的表目中包含：虚页号以及该虚地址属于哪个进程、物理页架号、页面保护权限等。

Untitled (3)

当运行进程要访问虚地址v，于是硬件将地址v截成页号p和页内地址d；

地址转换机构首先以页号p和快表中各表目同时进行比较，以便确定该页是否在快表中；

若在其中，则快表即送出相应的页架号与页内地址一起拼接成绝对地址，并按此地址访问主存；

若该页不在快表中，则使用直接映象方法查找进程的页表，找出其页架号p’与页内地址拼接成绝对地址，并访问主存；同时将该页的页号及对应的页架号一起送入快表的空闲表目中去；若无空表目，通常把最先装入的那个页的有关信息淘汰掉，腾出表目位置。

实际上，直接映象和快表同时进行，当快表成功，就自动停止直接映象工作。

缺页中断处理流程

Untitled (4)

分段概述

虚拟分段的优点

分段技术简化了对可以任意增长和收缩的数据段的管理；
分别编译的段的连接十分简单；
如果一个段的过程被修改并重新编译，不会引起其他段修改，因为这些修改只涉及该段自己的地址空间；
分段机制便于在进程间共享过程和数据，只要把这些过程和数据，如同共享库一样，放在分别的段中，通过段表映射进行共享；
段是程序员可见的逻辑上的实体，如过程，数组和堆栈等，对不同段，程序员可以安排不同的保护类型。

虚拟分段的缺点

段大小不一致，段外碎片使存储利用率下降。

分段的实现

每个虚拟地址由一个数对（段号，段内偏移量）两部分组成，每个进程一个段表；

实现过程：

当进程访问某虚拟地址（s,w）时，内核将段表地址寄存器中内容b与段号同段表表目长的乘积相加后，得到该段的表目入口地址；
由此表目中查得段s在主存中的起始地址s’；
再将s’与段内地址w相加，而得到欲访问单元的主存物理地址，并进行访问。

段页式存储管理的基本概念

等分主存

把整个主存分成大小相等的存储块，即页架；

进程的地址空间采用分段的方式

按程序的自然逻辑关系把进程的地址空间分成若干段，每一段有自己的外部段名和内部段号；

进程的每一段又采用分页方法

按主存页架大小把每一段划分成若干页，每段从零开始为自己段的各页依次编页号；

逻辑地址结构

一个逻辑地址用三个参数表示，段号s，页号p，页内地址偏移量d，记为v=(s,p,d)；

主存分配

主存以页架为单位分配给每个进程；

段表、页表、段表地址寄存器

段页式存储管理的优缺点

优点

提供了虚拟存储器的功能；
因为以页架为单位分配主存，所以无紧缩问题，也没有页外的碎片存在；
便于处理变化的数据结构，段可动态增长；
便于共享，只要欲共享作业的段表中有相应表目指向该共享段在主存中的页表地址；
便于控制存取访问。

缺点

增加了硬件成本，因为需要更多的硬件支持；
增加了软件复杂性和管理开销；
同分页系统一样仍然存在页内碎片。

页面置换算法

算法的引出

当系统中没有空闲页时，就要进行页面置换，即挑选一个页面淘汰出去，并把此页架分给进程使用；

问题

挑选什么样的页面来淘汰？
从该进程已有页面集中还是在全体页面集中选择淘汰页，即局部置换还是全局置换？

最佳置换算法

淘汰在将来再也不被访问，或者是在最远的将来才被访问的页。

最近未使用置换算法

不但希望淘汰的页是最近未使用的页，而且还希望被挑选的页在主存驻留其间，其页面内的数据未被修改过。

先进先出置换算法

选择最早进入主存的页面淘汰，理由是其不再使用的可能性比最近调入的页面要大；

但只是在按线性顺序访问地址空间时，才是理想的，否则效率不高；

随着分给的页架数增加，缺页频率也增加。

二次机会置换算法

把先进先出算法与使用页表中的访问位结合起来；

首先检查先进先出链上的最前面（最早进入）的页，如果它的访问位为0，则选择该页淘汰；如果它的访问位为1，则把该页移到FIFO的链尾，即把它作为新调入的页；

继续查找链上的下一页并检查它们的访问页，直到遇到访问位为0的那些较先进入的页，把它选择为被淘汰的页。

时钟页面置换算法

把进程所访问的页构成一个象时钟那样的环形链表；

产生缺页中断时，先检测指针所指的页，如果它的引用位为0，则淘汰该页；新装入的页插入到这个位置，然后指针向前进一个位置；如果它的访问位为1，则清除为0，并将指针再前进一个位置，继续检查访问位；重复此过程，直到找到访问位为0的页为止。

最近最少使用置换算法

选择最近一段时间内最长时间没有被访问过的页淘汰；

理由是认为过去一段时间里不曾被访问过的页，在最近的将来也可能不再会被访问。

分页环境中程序的行为特性

局部性的概念

进程对主存的访问并不是均匀的，而是高度地表现出局部性；
时间局部性：某个位置最近被访问了，那么往往很快又要被再次访问，如程序中的循环、常用子程序、堆栈、常用变量等；
空间局部性：一旦某个位置最近被访问了，那么它附近的位置也要被访问，如数组的处理、顺序代码的执行等。

例题

例题一

下表给出了某系统中的空闲分区表，系统采用可变式分区存储管理策略。现有以下作业序列：96K、20K、200K。若用首次适应算法和最佳适应算法来处理这些作业序列，试问哪一种算法可以满足该作业序列的请求，为什么？

Untitled (5)

解答：

若采用首次适应算法，在申请96K存储区时，选中的是4号分区，进行分配后4号分区还剩下122K；接着申请20K，选中1号分区，分配后剩下12K；最后申请200K，现有的5个分区都无法满足要求，该作业等待。显然采用首次适应算法进行内存分配，无法满足该作业序列的需求。这时的空闲分区表如下所示：
若采用最佳适应算法，在申请96K存储区时，选中的是5号分区，5号分区大小与申请空间大小一致，应从空闲分区表中删去该表项；接着申请20K时，选中1号分区，分配后1号分区还剩下12K；最后申请200K，选中4号分区，分配后剩下18K。显然采用最佳适应算法进行内存分配，可以满足该作业序列的需求。为作业序列分配了内存空间后，空闲分区表如下所示：