搜索
第五章虚拟存储器5.1虚拟存储器概述5.2请求分页存储管理方式5.3页面置换算法5.4“抖动”与工作集5.5请求分段存储管理方式5.1虚拟存储器概述常规存储管理方式的特征和局部性原理常规存储管理方式的特征一次性进程要一次性全部装入内存才可以运行引发两个问题1）若进程对内存的要求超出物理内存总容量，则无法运行2）内存由于容量的限制，只能装入少量进程运行，限制了并发度5.1虚拟存储器概述驻留性进程在其运行期间，始终“驻留”在内存暂时不用的程序和数据部分也占据内存空间，造成内存空间的浪费5.1虚拟存储器概述局部性原理在一段时间内一个程序的执行往往呈现出高度的局部性，表现在时间与空间两方面时间局部性一条指令被执行了，则在不久的将来它可能再被执行空间局部性若某一存储单元被使用，则在一定时间内，与该存储单元相邻的单元可能被使用5.1虚拟存储器概述虚拟存储器的基本工作情况在程序装入时，不必将其全部读入到内存，而只需将当前需要执行的部分页或段读入到内存，就可让程序开始执行在程序执行过程中，如果需执行的指令或访问的数据尚未在内存（称为缺页或缺段），则由处理器通知操作系统，将相应的页或段调入到内存，然后继续执行程序5.1虚拟存储器概述虚拟存储器的定义和特征虚拟存储器的定义虚拟存储器是指具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储系统其逻辑容量之和由内、外存容量之和决定5.1虚拟存储器概述虚拟存储器的特征多次性－－一次性一个作业被分成多次地调入内存运行对换性－－驻留性允许作业在运行过程中换进、换出虚拟性从逻辑上扩充内存容量，使用户可使用的内存空间大于实际物理内存5.1虚拟存储器概述虚拟存储器的实现方法技术难点如何确定和记录当前哪些部分在内存中执行中要执行的指令或访问的数据不在内存时，如何处理将所需部分从外存调入内存时，内存空间不够，如何处理有两种典型的虚拟存储器实现方式请求分页系统请求分段系统5.1虚拟存储器概述以CPU时间和外存空间换取昂贵内存空间，这是操作系统中的资源转换技术优点内存利用率高方便用户对多道程序运行有较强的支持5.2请求分页存储管理方式基本思想进程开始运行之前，不是装入全部页面，而是装入一个或零个页面，之后根据进程运行的需要，动态装入其它页面5.2请求分页存储管理方式技术难点如何确定和记录当前哪些部分在内存中执行中要执行的指令或访问的数据不在内存时，如何处理将所需部分从外存调入内存时，内存空间不够，如何处理——页表——缺页中断处理——页面置换5.2请求分页存储管理方式请求分页中的硬件支持页表机制状态位（存在位）P：表示该页是否调入内存访问字段A：用于记录该页在某段时间内被访问的次数修改位M：表示该页在调入内存后是否被修改过外存地址：该页在外存上的地址，通常是物理块号页号物理块号状态位P访问字段A存取控制修改位M外存地址5.2请求分页存储管理方式缺页中断机构在地址映射过程中，在页表中发现所要访问的页不在内存，则产生缺页中断。操作系统接到此中断信号后，调出缺页中断处理程序，根据页表中给出的外存地址，将该页Q调入内存，使进程继续运行下去。如果内存中有空闲物理块，则分配一页，将页Q装入内存，并修改页表。若此时内存中没有空闲物理块，则发生页面置换。5.2请求分页存储管理方式地址变换机构缺页中断处理保留CPU现场从外存中找到缺页内存满否？选择一页换出该页被修改否？将该页写回外存OS命令CPU从外存读缺页启动I/O硬件将一页从外存换入内存修改页表否是是否页表项在快表中？CPU检索快表访问页表否页在内存？修改访问位和修改位形成物理地址地址变换结束否页号＞页表长度?开始程序请求访问一页产生缺页中断请求调页修改快表是越界中断是是5.2请求分页存储管理方式请求分页中的内存分配最小物理块数的确定指能保证进程正常运行所需的最小物理块数进程应获得的最少物理块数与计算机的硬件机构有关，取决于指令的格式、功能和寻址方式5.2请求分页存储管理方式内存分配策略分配策略固定分配策略可变分配策略页面置换策略全局置换局部置换5.2请求分页存储管理方式三种组合固定分配局部置换思路：分配固定数目的内存空间，在整个运行期间都不改变策略：如果缺页，则先从该进程在内存的页面中选中一页，进行换出操作，然后再调入一页。特点：为每个进程分配多少页是合适的值难以确定。此外，在对换时会浪费比较多的时间。5.2请求分页存储管理方式可变分配全局置换思路：每个进程预先分配一定数目的物理块，同时OS也保持一个空闲物理块队列。策略：当缺页时，首先将对OS所占有的空闲块进行分配，从而增加了各进程的物理块数。当OS的空闲块全部用完，将引起换出操作。可变分配局部置换思路：系统根据缺页率动态调整各进程占有的物理块数目，使其保持在一个比较低的缺页率状态下。特点：使大部分进程可以达到比较近似的性能。5.2请求分页存储管理方式物理块分配算法在采用固定分配策略时，可使用下列方法平均分配算法：将系统中所有可供分配的物理块平均分配给各个进程按比例分配算法：根据进程的大小按比例分配物理块的算法考虑优先权的分配算法：为重要的、紧迫的作业分配较多的内存空间。通常采取的方法是把内存中可供分配的所有物理块分成两部分：一部分按比例地分配给各进程；另一部分则根据各进程的优先权，适当地增加其相应份额后，分配给各进程5.2请求分页存储管理方式页面调入策略何时调入页面预调页策略将预计在不久之后会被访问的页面预先调入内存目前预调页的成功率仅约50%主要用于进程的首次调入请求调页策略进程运行中发现要访问的页面不在内存，便立即提出请求，由OS将其所需页面调入内存。目前的虚拟存储器中大多采用此策略5.2请求分页存储管理方式从何处调入页面外存有两个部分：文件区和对换区。对换区I/O操作速度比文件区相对快一些，因此一般应当尽量使用对换区来调入页面对于不同情况，采用不同的策略系统有足够的对换区空间系统缺少足够的对换区空间UNIX方式5.2请求分页存储管理方式页面调入过程1、进程需要的页面不在内存，引起缺页中断2、中断处理程序保留现场环境，转入缺页中断处理程序3、中断处理程序查找页表，得到对应的外存物理块号。如果内存有空闲，则启动磁盘操作，将所缺的页面读入，并修改页表。否则，到4。4、执行置换算法，选出要换出的页面，如果该页修改过，应将其写入磁盘，然后将所缺页调入内存，修改相应表项，将其存在位置为‘1’，并放入快表。5、利用修改后的页表，形成物理地址，访问内存数据。5.2请求分页存储管理方式缺页率（A：总的访页次数）（F：访问页面失败的次数）影响缺页率的因素页面大小进程所得物理块的数目页面置换算法程序固有特性AFf5.2请求分页存储管理方式影响缺页率的因素（续）进程所得物理块的数目5.2请求分页存储管理方式影响缺页率的因素（续）程序固有特性例：内存分配一块，初始时第一页在内存；页面大小为128个整数；矩阵A128X128按行存放程序编制方法2：Forj:=1to128Fori:=1to128A[i,j]:=0;程序编制方法1：Fori:=1to128Forj:=1to128A[i,j]:=0;5.2请求分页存储管理方式优点作业的地址空间不再受主存大小的限制主存利用率大大提高能实现多道作业同时运行方便用户缺点缺页中断处理增加系统开销页面的调入调出增加I/O系统的负担页表等占用空间且需要管理，存在内碎片5.3页面置换算法进程在较少的内存物理块中运行，发生缺页中断时，可能会遇到内存中无空闲物理块可提供，此时应：选择一个已经在内存中的页面淘汰将新装入页放入刚淘汰页面所在的物理块选择哪个已经在内存中的页面淘汰?内存中被修改过的页面应优先保留不被淘汰最好不要选择使用频率高的页面淘汰，否则将导致使用频繁的页被多次调入调出5.3页面置换算法最佳（Optimal）置换算法1966年Belady选择“未来不再使用的”或“在最远的将来被使用的”页面来置换。理论上最优，但是无法实现（由于一般程序的行为难以预料）可以作为评估其它页面置换算法的标准5.3页面置换算法例，假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1引用率70770170122010320304243230321201201770101页框(物理块）243缺页中断次数=9缺页率=9/20=45%页面置换次数=65.3页面置换算法先进先出（FIFO）页面置换算法系统将所有页面排入一个FIFO队列按各页进入内存的时间顺序排在FIFO队列队首的页面先被淘汰缺点先进入主存的页可能将被高频率反复使用而导致内外存置换次数增加存在Belady异常：有时分配给进程的物理块增加时，缺页中断次数也增加5.3页面置换算法同例引用率70770170122010323104430230321013201770201页框230420423023012712701缺页中断次数=15缺页率=15/20=75%页面置换次数=125.3页面置换算法再例页面访问序列012301401234012301444233012301114220123000144+++++++++缺页次数=9；缺页率f=9/12=75%页面访问序列012301401234012333401234012223401230111234012000123401++++++++++缺页次数=10；缺页率f=10/12=83%5.3页面置换算法最近最久未使用（LRU）置换算法选择最近最久未使用的页面予以淘汰该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t，当须淘汰一个页面时，选择现有页面中其t值最大的，即最近最久未使用的页面予以淘汰理论上可行，但实现代价很高5.3页面置换算法同例引用率70770170122010320304403230321132201770101页框402432032102缺页中断次数=12缺页率=12/20=60%页面置换次数=95.3页面置换算法硬件支持寄存器每个页面设立移位寄存器，被访问时左边最高位置1，定期右移并且最高位补0，于是寄存器数值最小的是最久未使用页面。R实页R7R6R5R4R3R2R1R01010100102101011003000001004011010115110101106001010117000001118011011015.3页面置换算法栈把被访问的页面移到栈顶，于是栈底的是最久未使用页面例，假定现有一进程所访问的页面的页面号序列为：4，7，0，7，1，0，1，2，1，2，644747074070471704101740107412107421207412107426210765.3页面置换算法最少使用（LFU）置换算法为在内存中的每个页面设置一个移位寄存器，用来记录该页面被访问的频率每次访问某页时，便将该移位寄存器的最高位置1，再每隔一定时间右移一次在最近一段时间使用最少的页面将是∑Ri最小的页5.3页面置换算法Clock置换算法简单的Clock置换算法也称最近未使用算法NRU，是LRU和FIFO的折衷内存中所有页面通过链接指针形成一个循环队列每页有一个访问位，某页被访问则其访问位置1在选择一页淘汰时，只需检查页的访问位。如果是0，就选择该页换出；若为1，则重新将它置0，暂不换出，而给该页第二次驻留内存的机会，再按照FIFO算法检查下一个页面。当检查到队列中的最后一个页面时，若其访问位仍为1，则再返回到队首去检查第一个页面。5.3页面置换算法简单Clock置换算法的流程和示例入口查寻指针前进一步，指向下一个表目页面访问位＝0?选择该页面淘汰是返回置页面访问位＝“0”否块号页号访问位指针0124034