第七章虚拟存储器

第七章虚拟存储器*计算机操作系统7.1

虚拟存储器的基本概念7.2

请求分页存储器管理方式7.3

请求分段存储器管理方式7.4

操作系统软件*计算机操作系统7.1虚拟存储器的基本概念实存管理有两个明显的特性：

一次性：作业一次全部入主存；

驻留性：作业进入主存后一直驻留直到完成。实存管理的不足：一、虚拟存储器的定义

从用户角度，将系统可提供的比实际大很多的内存容量，称为虚拟存储器。二、局部性原理1、程序访问的局部性，总是局限在程序中某一个部分。2、局部性原理：描述了一个进程中程序和数据引用的集簇倾向。

虚存的4个特征三、虚存的2种实现方式请求分页系统和请求分段系统。1、硬件支持：页/段表扩充，缺页/段中断，地址变换2、操作系统必须有管理页或段在主存和辅存之间移动的软件。*计算机操作系统1、离散性：采用离散分配方式；2、多次性：一个作业分成多次调入主存运行；3、对换性：将得不到运行的程序、数据调至外存盘交换区；4、虚拟性：四、虚存的4个特征*计算机操作系统7.2请求分页存储器管理方式一、页表机制

页号，页框号，状态位P，访问位A，修改位M，外存地址二、缺页中断机构与一般中断的2点区别：

1、是在指令执行期间，发现指令/数据不在主存时产生并处理；

2、一条指令在执行期间，可能会产生多次缺页中断。要求系统能保存多次中断的状态。（例）地址变换*计算机操作系统3、多次缺页中断示例设：主存页框大小为128字，有128*128的数组；VarA:array[1..128]ofarray[1..128]ofinteger;程序段：fori:=1to128forj:=1to128A[i][j]:=0;数组元素的存放格式为以行为主序，问：执行时缺页次数为多少？A[1,1]A[1,2]A[1,3]...A[1,128]...A[128,1]A[128,2]A[128,3]...A[128,128]...1页1页82、逻辑地址结构和页表结构94、地址装换过程：*计算机操作系统三、页表组织方式页面分配1、放置页表需要大量的内存空间2、页表也可以存储在虚拟内存中3、当程序运行时，只需要访问页表的一部分。11举例：两极层次页表四、两级页表

12五反向页表：InvertedPageTable（1）、哈希表（2）、反向页表包含的内容PagenumberProcessidentifierControlbitsChainpointer133、使用链接技术解决哈希冲突问题4、反向页表中的第i项对应与第i帧。5、“反向”使用帧号而不是虚拟页号来索引页表项。1415六、转移后备缓冲区（1）TLB提出的必要性每个虚存可能引起两次物理内存访问：OnetofetchthepagetableOnetofetchthedata为了克服这个问题，为页表项使用一个特殊的高速缓存。CalledaTranslationLookasideBuffer(TLB)16给定一个虚拟地址，处理器首先检查TLB如果所需要的页表项在其中(TLBhit),检索帧号并形成实地址。

如果没有找到所需要的页表项(TLBmiss),处理器用页号检索进程页表，若“存在位”置位，更新TLB。如果“存在位”没有，将产生一次页错误，离开硬件作用范围，调用操作系统。（2）实现过程或者TLB的用法1718（3）TLB的组织19（4）虚存机制与主存中高速缓存的交互20七、页的大小（1）页越小：内部碎片总量少页越大：更有效的数据块传递（2）页尺寸对于也错误发生概率的影响。如下图所示（3）页尺寸的设计问题与物理主存大小和程序有关。主存变大，应用程序使用的地址空间增长。多线程应用/面向对象技术降低局部性。

TLB大小的确定：不能像主存增长那么快。解决方法：使用大小不等的多种页尺寸。2122ExamplePageSizes237.3请求式分段存储管理段的大小不相等，并且是动态的。优点：1、简化不断增长的数据结构处理。2、允许程序独立地改变或者重新编译。3、有助于进程间的共享。4、有助于保护。*计算机操作系统请求分段中的硬件支持一、段表机制

段名，段长，内存起址，状态位，存取方式，访问位，修改位，增补位，外存起址二、缺段中断

在一条指令的执行期间，产生并处理中断，且可能产生多次缺段中断。三、地址变换机构

分段的共享与保护25SegmentTableEntries263、分段系统中的地址转换*计算机操作系统

共享方式：每个共享进程段表中，在相应共享段表目中，指向共享段在内存的起址即可。系统实现：一、设置共享段表/现行分段表二、建立共享段分配、回收操作过程三、完善分段保护机制，有3种常用措施：

1、越界检查：

2、存取控制检查：

3、环保护机构：类似于软件的层次结构，每层有不同的优先数，0环为操作系统。2个访问规则：

A、一个程序可以访问同环或低优先权环中数据；

B、一个程序可以调用同环或高优先权环中的服务；分段的共享与保护*计算机操作系统共享段表说明：

1、共享段只有当所有共享进程都不再需要时(Count=0)，才会被释放；

2、对同一个共享段，不同进程可以使用不同的段号来共享该段。段名段长内存起址状态外存起址

共享进程计数Count状态进程名进程号段号存取控制......

*计算机操作系统共享段的分配、回收分配：

第一个请求使用共享段的进程申请内存分区，调入，修改共享段表相应内容；以后其它进程使用该共享段时，首先在本进程段表中填入该共享段的物理地址；然后在共享段表中增加一表目，填入进程名，存取控制等信息，并完成Count+1。回收：

执行Count-1，取消共享段表中的表目

307.4请求式段页式管理

CombinedPagingandSegmentation1、基本概念分页对程序员是透明的，消除外部碎片，有效使用主存Pagingistransparenttotheprogrammer分段对程序员是可见的。处理不断增长的数据结构能力，支持共享和保护。Segmentationisvisibletotheprogrammer用户地址空间被程序员划分为多个段，每个段划分为多个固定大小的页。Eachsegmentisbrokenintofixed-sizepages311、CombinedSegmentationandPaging322、段页式系统中的地址转换333、保护与共享7.4操作系统软件

一、读取策略

1、读策略确定一页合适取入主存请求式分页：只有当访问到某一页的一个单元时才将该页取入主存。预约式分页：读取的页并不是页错误请求的页。适应于：进程第一次启动和发生页错误时。与交换的区别：交换以作业为单位。二、放置策略决定进程块驻留在主存什么位置。分段：最佳适配，首次适配。分页：如何放置没有关系。非一致存储访问多处理器：机器中分布的共享内存可以被机器的任何处理器访问。访问特定物理单元所需要的时间随着处理器和内存之间的距离而变化。依赖于驻留集的位置与使用数据处理器间的距离。因此，希望把页分配到能够提供最佳性能的内存。三、替换策略

“抖动”(Thrashing)：刚刚被换出的页很快又被访问，需再次调入。使进程花费大部分时间进行页面的置换，称进程发生了“抖动”。1、帧锁定2、基本算法（1）最佳算法OPT选择替换下次访问距当前时间最长的那些页。最少的页错误不可能实现，作为一种标准来衡量其他算法。（2）最近最少使用LRU替换主存中上次使用距当前最远的页。（3）先进先出FIFO替换主存中时间最长的页。三种算法比较：LRU效果好，但需要大量的开销（时间标签，维护访问页的栈）FIFO实现简单但性能差。OPT只能作为衡量依据。（4）时钟策略

a、某一页首次装入主存中的某一帧时，使用位为1，指针下移。

b、该页随后被访问到时，它的使用位为1。指针不移动。

c、替换时，查找使用位为0的帧，若找到，发生页面替换后，指针下移，每遇到使用位为1的帧重新置0，指针后移。

d、若所有位为1，把所有位置0，并且指针停留下最初位置，替换该帧的页，替换后，指针后移。*计算机操作系统

为避免抖动的发生，应选择合适的置换算法。一、最佳置换算法二、先进先出置换算法（FIFO）（例）三、最近最久未使用置换算法(LeastRecentlyUsed)

思想：记录页面上次被访问的时间，选择最近最久未使用的页面淘汰。（例）

比较FIFO与LRU得出何结论？

页面置换算法（续1）404142434、ComparisonofPlacementAlgorithms四、驻留集管理驻留集：进程执行中的任何时候在主存中那部分集合。固定分配：为一个进程分配固定数目的帧。可变分配：分配给一个进程的页帧在进程的生命周期中不断发生变化。*计算机操作系统分配算法分配：固定/可变；置换：局部/全局。

1、固定分配，局部置换；

2、可变分配，全局置换；先分配一定数额，OS保留一个空闲页框队列。进程缺页时，申请新页框：有，追加分配；无，全局置换。

3、可变分配，局部置换；先分配一定数额，OS保留一个空闲页框队列。进程缺页时，申请新页框：有，追加分配；无，局部置换。*计算机操作系统进程缺页率高，不仅会使其运行进度减慢，而且增加了CPU开销和通道及外设的负担。1968年，Denning根据程序的局部性理论(进程对页的访问不是均匀的，而是集中的。进程访问页面集合的变化，从一个时间段到另一个时间段是缓慢过渡的)，提出了工作集理论(属LRU算法的发展)。

工作集：进程在某段时间内实际访问页的集合。

五、工作集/驻留集(WorkingSet)具体表述*计算机操作系统

设进程在t-到t时间段内访问页的工作集记为：W(t,)（为工作集窗口尺寸）则：|W(t,)|为工作集中包含的页面数工作集W是二元函数：

1、W是t的函数，随时间不同，工作集不同；2、W是的非降函数。若过大，甚至将整个作业地址空间包含在内，则失去虚存意义；过小，会导致频繁缺页。

工作集的具体表述抖动的产生和预防WorkingSetTheworkingsetwithparameterforaprocessatvirtualtimet,W(t，),isthesetofpagesofthatprocessthathavebeenreferencedinthelastvirtualtimeunits0,1,0,1,0,2,3,4,1,3,/……/4,2,5,3,4,5,3,4,2,0,/……/1,0,1,1,1,2,1,1,0,2,/……/1,1,2,1,2,0,0,1,2,/