操作系统(第四版)第04-2章

1、第四章之第四章之虚拟存储器4.6 虚拟存储器的基本概念4.6.1 虚拟存储器的引入问题的提出 :程序一次性全部装入主存（程序大于内存、内存的利用率） 程序暂时不执行或部分程序段已运行完还要占用内存局部性原理为解决问题提供了基础。一、局部性原理程序局部性原理 在一段时间内一个程序的执行往往呈现出高度的局部性，表现在时间与空间两方面时间局部性： 一条指令被执行了，则在不久的将来它可能再被执行空间局部性： 若某一存储单元被使用，则在一定时间内，与该存储单元相邻的单元可能被使用二、虚拟存储器基于局部性原理，一个作业在运行时，只将部分装入内存，其余部分暂时留在外存上。当执行到未在内存的部分时，再将相应部

2、分调入内存。对用户：指令地址部分所限定的比实存大得多的地址空间。对系统：借助于各种表格机构，实现内、外存的统一管理，体现虚拟空间。虚拟存储器（续）虚拟存储器是指具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的存储器系统。虚拟存储器就是一个地址空间（即由程序的相对地址所组成的地址空间），且具有比实存大得多的容量。4.6.2 虚拟存储器的实现方式虚拟存储器的实现必须建立在离散分配存储管理的基础之上。分页请求系统 调页功能和页面置换功能 需软件（OS）和硬件（页表机制、缺页中断机构、地址变换机构）的支持请求分段系统 调段功能和段的置换功能 需软、硬件的支持4.6.3 虚拟存储器的特征 连续

3、性离散性 驻留性交换性 一次性多次性虚拟性 以CPU时间和外存空间换取昂贵内存空间，这是操作系统中的资源转换技术最本质的特征虚拟存储器的容量一个虚拟存储器的最大容量是由计算机的地址结构确定的。如：若CPU的有效地址长度为32位，则程序可以寻址范围是0(232)-1 ，即虚存容量为 4GB。虚拟存储器的容量与主存的实际大小没有直接的关系，而是由主存与辅存的容量之和所确定。4.7 请求分页存储管理请求分页存储管理请求式分页也称虚拟页式存储管理 与纯分页存储管理不同，请求式分页管理系统在进程开始运行之前，不是装入全部页面，而是装入一个或零个页面，之后根据进程运行的需要，动态装入其它页面；当内存空间已

4、满，而又需要装入新的页面时，则根据某种算法淘汰某个页面，以便装入新的页面需要解决的问题将哪部分装入内存系统如何获知进程当前所需页面不在主存，何时将页面装入当发现缺页时，如何把所缺页面调入主存，装入内存的什么位置当内存没有空间时淘汰哪个页面（即当主存中没有空闲的页框时，为了要接受一个新页，需要把老的一页淘汰出去，根据什么策略选择欲淘汰的页面。 ）解决问题的三大策略拿来策略拿来策略就是缺哪页装哪页页面调入时机主要有两个策略：预调页策略和请求调页策略放置策略哪里有空放哪里4.7.1 请求分页中的硬件支持1、页表机制中断位：表示该页是在内存还是在外存访问位：表示该页最近被访问过，根据访问位来决定淘汰哪

5、页修改位：查看此页是否在内存中被修改过页号页号 中断位中断位内存块号内存块号 外存地址外存地址 访问位访问位修改位修改位2、缺页中断机构查页表时，当存在位指示该页不在主存时，则引起一个缺页中断发生，相应的中断处理程序把控制转向缺页中断子程序。执行此子程序，即把所缺页面装入主存。然后处理机重新执行缺页时打断的指令。这时，就将顺利形成物理地址。注意：缺页中断属于内中断，它与外中注意：缺页中断属于内中断，它与外中断的区别：断的区别：1)1)响应时间；响应时间；2)2)执行一条指执行一条指令期间，可能产生多次缺页中断。令期间，可能产生多次缺页中断。3、地址变换机构请求分页存储管理地址变换流程请求分页存

6、储管理地址变换流程4.7.2 页面分配需处理三个问题：确定最小物理块数；页面分配和置换策略；分配算法。1、最小物理块数保证进程能正常运行所需的最小物理块数。（即进程所分配的物理块数小于此值时将无法运行）该值的大小与计算机的硬件结构有关，取决于指令的格式、功能和寻址方式。2、页面分配和置换策略分配策略有固定分配策略和可变分配策略；置换策略有局部置换策略和全局置换策略。可有三种组合：固定分配局部置换进程分配一固定页数的内存空间，且该数一直保持不变。发生缺页时，只能从该进程在内存中的页中换出某页。页面分配和置换策略（续）可变分配全局置换创建进程时先为其分配一定数目的物理块，且内存中保留一定数目的空闲

7、块。当发生缺页时，先判断还有无空闲块，有则再为该进程分配一个物理块将所缺页调入，无则换出某页。（换出的页肯能是系统中其它进程的页）页面分配和置换策略（续）可变分配局部置换先为进程分配一定数目的内存空间。发生缺页时，只能从该进程在内存中的页中换出某页。但若该进程频繁发生缺页中断，则再为该进程分配若干物理块。3、分配算法平均分配算法将系统中所有可供分配的物理块平均分配给各个进程。（未考虑各进程大小不同）按比例分配算法按照进程页数与所有进程页数之和的比例关系分配内存空间。但注意分配的数目必须大于最小物理块数考虑优先权的分配算法4.7.3 页面调入策略1、调入时机预调页策略请求调页策略2、从何处调入从

8、对换区调入（需先从文件区复制到对换区）不会修改的文件从文件区调入（不必换出），可能会修改的文件首次调入从文件区，换出时存入对换区，再次调入时从对换区。UNIX方式：首次调入从文件区，换出时只将运行过的页换出到对换区，再次需要时从对换区调入。3、页面调入过程（见地址变换机构的过程图）4.8 页面置换算法当要放一页面到全满的主存块时，系统需淘汰一页。用来选取淘汰哪一页的规则，叫置换算法。最佳置换算法 先进先出置换算法 最近最久未用置换算法（LRU算法）近似的LRU算法（NRU算法）1.最佳置换算法最佳置换算法是由Belady于1966年提出的一种理论上的算法。 其所选择的被淘汰页面，将是以后永不使

9、用的， 或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。由于无法预计进程将来的执行情况，即无法得知哪页才是在最长(未来)时间内不再被访问的页面，因此此算法在实际系统中无法实现。但我们可以利用该算法去评价其它算法的优劣。 假定系统为某进程分配了三个物理块， 并考虑有以下的页面号引用串：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1 利用最佳页面置换算法时的置换图 采用该算法，只发生了采用该算法，只发生了6次缺页中断。次缺页中断。2. 先进先出(FIFO)页面置换算法 置换时 选择在内存中驻留时间最长的页并淘汰之 利用FIF

10、O置换算法时的置换图采用该算法，要发生了采用该算法，要发生了12次缺页中断。该算法性能最次缺页中断。该算法性能最差，实际极少使用。差，实际极少使用。3. 最近最久未使用(LRU)置换算法 选择最后一次访问时间距离当前时间最长的一页并淘汰之。即淘汰没有使用的时间最长的页。 LRU页面置换算法 LRU置换算法（续）由于需要记录内存中各个页未被进程访问的时间长短以及得知哪页是最近最久未使用的页，必须使用寄存器组和栈。算法实现代价很高，系统开销非常大。因此实际应用不多。在实际应用中，大多采用近似的LRU置换算法。近似的LRU置换算法在页表中设置“访问位”。当某页被访问时，该页相应的访问位由硬件自动置1

11、。而当需要进行页面置换时，将访问位为0的页换出。该算法需要解决的问题是：访问位要周期性的刷新（清0），以及刷新周期的长短设置。4. Clock置换算法1) 简单的简单的Clock置换算法置换算法(近似的近似的LRULRU算法）算法） 简单Clock置换算法的流程和示例 2) 改进型Clock置换算法由访问位A和修改位M可以组合成下面四种类型的页面： 1类(A=0, M=0): 表示该页最近既未被访问， 又未被修改， 是最佳淘汰页。 2类(A=0, M=1)： 表示该页最近未被访问， 但已被修改， 并不是很好的淘汰页。 3类(A=1, M=0)： 最近已被访问， 但未被修改， 该页有可能再被访问。 4类(A=1, M=1): 最近已被访问且被修改， 该页可能再被访问。 影响缺页次数的因素缺页率的大小会影响系统的运行速度以及系统性能。而影响缺页次数的因素有：(1) 分配给进程的物理页面数(2) 页面本身的大小(3) 程序的编制方法(4) 页面淘汰算法性能问题抖动: 在虚存中，页面在内存与外存之间频繁调度，以至于调度页面所需时间比进程实际运行的时间还多，此时系统效率急剧下降，甚至导致系统崩溃。这种现象称为抖动（或称颠簸）原因：页面淘汰算法不合理分配给进程的物理页面数太少4.9 4.9.1 请求分段中的硬件支持1、段表机制段号 段长 段始址 存取方式 存在位 访