《计算机操作系统-第四版-汤小丹-梁红兵-哲凤屏-第5章(2016-2017-1)培训资料.ppt》由会员分享，可在线阅读，更多相关《计算机操作系统-第四版-汤小丹-梁红兵-哲凤屏-第5章(2016-2017-1)培训资料.ppt（50页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第五章虚拟存储器计算机操作系算机操作系统-第四版第四版-汤小丹小丹-梁梁红兵兵-哲哲凤屏屏-第第5 5章章(2016-(2016-2017-1)2017-1)第五章虚拟存储器1.1.常规存储器管理方式的特征常规存储器管理方式的特征(1)一次性。常规存储管理方式都要求将作业全部装入内存后方能运行。然而，许多作业在每次运行时，并非其全部程序和数据都要用到。5.1.1常规存储管理方式的特征和局部性原理常规存储管理方式的特征和局部性原理(2)驻留性。作业装入内存后，便一直驻留在内存中，直至作业运行结束。然而，有的程序模块在运行过一次后就不再需要(运行)了。问题：一次性及驻留性在程序运行时是否是必需的问
2、题：一次性及驻留性在程序运行时是否是必需的?第五章虚拟存储器2 2局部性原理局部性原理Denning.P在1968指出：程序在执行时将呈现出局部性规律，即在一较短的时间内，程序的执行仅局限于某个部分；相应地，它所访问的存储空间也局限于某个区域。他提出了下述几个论点：(1)程序执行时，除了少部分的转移和过程调用指令外，在大多数情况下仍是顺序执行的;(2)在过程调用中，程序将会在一段时间内都局限在这些过程的范围内运行；(3)程序中存在许多循环结构；(4)程序中许多对数据结构的处理，往往都局限于很小的范围内。5.1.1常规存储管理方式的特征和局部性原理常规存储管理方式的特征和局部性原理第五章虚拟存储
3、器3.3.虚拟存储器的基本工作情况虚拟存储器的基本工作情况基于局部性原理，应用程序在运行之前，仅须将那些当前要运行的少数页面或段先装入内存便可运行，其余部分暂留在盘上。程序在运行时，如果程序所要访问的页(段)尚未调入内存，此时程序应利用OS所提供的请求调页(段)功能，将它们调入内存，以使进程能继续执行下去。如果此时内存已满，则须再利用页(段)的置换功能，将内存中暂时不用的页(段)调至盘上，再将要访问的页(段)调入内存，使程序继续执行下去。5.1.1常规存储管理方式的特征和局部性原理常规存储管理方式的特征和局部性原理第五章虚拟存储器5.1.2虚拟存储器的定义和特征虚拟存储器的定义和特征 具有请求
4、调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储系统。其逻辑容量是内存容量和外存容量之和，其运行速度接近于内存速度。1.1.虚拟存储器的定义虚拟存储器的定义2.2.虚拟存储器的特征虚拟存储器的特征1)多次性.一个作业被分成多次调入内存运行2)对换性.作业的运行过程中进行换进、换出3)虚拟性.能够从逻辑上扩充内存容量，使用户所看到的内存容量远大于实际内存容量。第五章虚拟存储器1.1.分页请求系统分页请求系统在分页系统的基础上增加了请求调页功能和页面置换功能。它允许只装入少数页面的程序(及数据)，便启动运行。以后，再通过调页功能及页面置换功能，陆续地把即将要运行的页面调入内存，同时把暂不
5、运行的页面换出到外存上。置换时以页面为单位。为了能实现请求调页和置换功能，系统必须提供必要的硬件支持和相应的软件。5.1.3虚拟存储器的实现方法虚拟存储器的实现方法虚拟存储器建立在离散分配存储管理方式第五章虚拟存储器2.请求分段系统请求分段系统在分段系统的基础上，增加了请求调段及分段置换功能后所形成的段式虚拟存储系统。它允许只装入少数段(而非所有的段)的用户程序和数据，即可启动运行。以后再通过调段功能和段的置换功能将暂不运行的段调出，同时调入即将运行的段。置换是以段为单位进行的。5.1.3虚拟存储器的实现方法虚拟存储器的实现方法第五章虚拟存储器5.2请求分页存储管理方式请求分页存储管理方式 5
6、.2.1请求分页中的硬件支持请求分页中的硬件支持1.1.请求页表机制请求页表机制在请求分页系统中所需要的主要数据结构是页表。其基本作用仍然是将逻辑地址变换为物理地址。请求分页系统建立在基本分页基础上，增加了请求调页功能和页面置换功能。请求分页系统中的页表请求分页系统中的页表第五章虚拟存储器在请求分页系统中，每当所要访问的页面不在内存时，便产生一缺页中断，请求OS将所缺之页调入内存。缺页中断是一种特殊的中断，主要表现在下面两个方面：(1)在指令执行期间产生和处理中断信号。(2)一条指令在执行期间可能产生多次缺页中断。基于这些特征，系统中的硬件机构应能保存多次中断时的状态，并保证最后能返回到中断前
7、产生缺页中断的指令处继续执行。5.2.1请求分页中的硬件支持请求分页中的硬件支持2.2.缺页中断机构缺页中断机构第五章虚拟存储器图图 5-2请求分页中的地址变换过程请求分页中的地址变换过程 5.2.1请请求求分分页页中的硬件支持中的硬件支持3 3地址变换机构地址变换机构1111月月1111日日第五章虚拟存储器1 1最小物理块数的确定最小物理块数的确定最小物理块数是指能保证进程正常运行所需的最小物理块数。当系统为进程分配的物理块数少于此值时，进程将无法运行。进程应获得的最少物理块数与计算机的硬件结构有关，取决于指令的格式、功能和寻址方式。5.2.2请求分页中的内存分配请求分页中的内存分配第五章虚
8、拟存储器2.2.内存分配策略内存分配策略 1)固定分配局部置换(Fixed Allocation，Local Replacement)基于进程的类型，或根据程序员、程序管理员的建议，为每个进程分配一定数目的物理块，在整个运行期间都不再改变。如果进程在运行中发现缺页，则从该进程在内存的n个页面中选出一个页换出，然后再调入一页。5.2.2请求分页中的内存分配请求分页中的内存分配第五章虚拟存储器2)可变分配全局置换(Variable Allocation，Global Replacement)2.2.内存分配策略内存分配策略 先为系统中的每个进程分配一定数目的物理块，而OS自身也保持一个空闲物理块队
9、列。当某进程发现缺页时，由系统从空闲物理块队列中取出一个物理块分配给该进程，并将欲调入的(缺)页装入其中。这样，凡产生缺页(中断)的进程，都将获得新的物理块。当空闲物理块用完时，OS才能从内存中选择一页调出，被选择调出的页可能试系统中的任何一页。5.2.2请求分页中的内存分配请求分页中的内存分配第五章虚拟存储器 3)3)可可 变变 分分 配配 局局 部部 置置 换换(Variable Allocation，Local Replacement)5.2.2请求分页中的内存分配请求分页中的内存分配先为每个进程分配一定数目的物理块，但当某进程发现缺页时，只允许从该进程在内存的页面中选出一页换出，这样就
10、不会影响其它进程的运行。如果进程在运行中频繁地发生缺页中断，则系统须再为该进程分配若干附加的物理块，直至该进程的缺页率减少到适当程度为止；反之，若一个进程在运行过程中的缺页率特别低，则此时可适当减少分配给该进程的物理块数。2.2.内存分配策略内存分配策略第五章虚拟存储器3.3.物理块分配算法物理块分配算法1)平均分配算法将系统中所有可供分配的物理块平均分配给各个进程。5.2.2请求分页中的内存分配请求分页中的内存分配2)按比例分配算法 根据进程的大小按比例分配物理块的算法。系统中共有n个进程，每个进程的页面数为Si,可用的物理块总数为m，则每个进程所能分到的物理块数为bi。第五章虚拟存储器3)
11、考虑优先权的分配算法考虑优先权的分配算法在实际应用中，为了照顾到重要的、紧迫的作业能尽快地完成，应为它分配较多的内存空间。通常采取的方法是把内存中可供分配的所有物理块分成两部分：一部分按比例地分配给各进程；另一部分则根据各进程的优先权，适当地增加其相应份额后，分配给各进程。5.2.2请求分页中的内存分配请求分页中的内存分配3.3.物理块分配算法物理块分配算法第五章虚拟存储器5.2.3页面调入策略页面调入策略1)预调页策略预调页策略采用一种以预测为基础的预调页策略，将那些预计在不久之后便会被访问的页面预先调入内存。这种策略主要用于进程的首次调入时，由程序员指出应该先调入哪些页。2)请求调页策略请
12、求调页策略 当进程在运行中需要访问某部分程序和数据时，若发现其所在的页面不在内存，便立即提出请求，由OS将其所需页面调入内存。每次仅调入一页，目前虚拟存储器大多采用此策略。1.何时调入页面何时调入页面第五章虚拟存储器2从何处调入页面从何处调入页面请求分页系统中的外存分为文件区和对换区。当发生缺页请求时，有三种情况将缺页调入内存：(1)系统拥有足够的对换区空间，这时可以全部从对换区调入所需页面，以提高调页速度。(2)系统缺少足够的对换区空间，凡不会被修改的文件都直接从文件区调入。对于那些可能被修改的部分，将它们换出时须调到对换区。(3)UNIX方式。与进程有关的文件都放在文件区，故凡是未运行过的
13、页面，都应从文件区调入；对于曾经运行过但又被换出的页面，放在对换区。第五章虚拟存储器3.页面调入过程页面调入过程每当程序所要访问的页面未在内存时，便向CPU发出一缺页中断，中断处理程序首先保留CPU环境，分析中断原因后转入缺页中断处理程序。在缺页调入内存后，利用修改后的页表，形成所要访问数据的物理地址，再去访问内存数据。整个页面的调入过程对用户是透明的。5.2.3页面调入策略页面调入策略第五章虚拟存储器5.2.3页面调入策略页面调入策略4.缺页率缺页率 假设一个进程的逻辑空间为n页，系统为其分配的内存物理块数为m(mn)。如果在进程的运行过程中，访问页面成功的次数为S，访问页面失败的次数为F。
14、则该进程在运行过程中的缺页率为：f=F/(S+F)第五章虚拟存储器5.3页面置换算法页面置换算法 5.3.1最佳置换算法和先进先出置换算法最佳置换算法和先进先出置换算法1.1.最佳最佳(Optimal)置换算法置换算法由Belady于1966年提出的一种理论上的算法。其所选择的被淘汰页面，将是以后永不使用的，或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。页面置换算法是指选择换出页面的算法。不适当的算法可能会导致进程发生“抖动”。第五章虚拟存储器u例例：假定系统为某进程分配了三个物理块，考虑有以下的页面号引用串：7,0,1,2,0,3,0,4,2,3,
15、0,3,2,1,2,0,1,7,0,1进程运行时，先将7，0，1三个页面装入内存。图图 5-3利用最佳页面置换算法时的置换图利用最佳页面置换算法时的置换图 1.1.最佳最佳(Optimal)置换算法置换算法第五章虚拟存储器 2.2.先进先出先进先出(FIFO)页面置换算法页面置换算法该算法淘汰最先进入内存的页面。5.3.1最佳置换算法和先进先出置换算法最佳置换算法和先进先出置换算法u例：页面号引用串：7 7，0 0，1 1，2 2，0 0，3 3，0 0，4 4，2 2，3 3，0 0，3 3，2 2，1 1，2 2，0 0，1 1，7 7，0 0，1.1.进程运行时，先将7，0，1三个页面装
16、入内存。FIFO算法时进行了算法时进行了12次页面置换次页面置换第五章虚拟存储器1.LRU(Least Recently Used)置换算法置换算法选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t，当须淘汰一个页面时，选择t值最大的页面.5.3.2最近最久未使用和最少使用置换算法最近最久未使用和最少使用置换算法LRU页面置换算法页面置换算法 第五章虚拟存储器2 2LRU置换算法的硬件支持置换算法的硬件支持 1)寄存器移位寄存器，记录某进程在内存中各页的使用情况。R=Rn-1Rn-2Rn-3 R2R1R0 5.3.2最近最久未使用和
17、最少使用置换算法最近最久未使用和最少使用置换算法图图5-6某进程具有某进程具有8个页面时的个页面时的LRU访问情况访问情况 第五章虚拟存储器2)2)栈栈可利用一个特殊的栈来保存当前使用的各个页面的页面号。每当进程访问某页面时，便将该页面的页面号从栈中移出，将它压入栈顶。假定现有一进程所访问的页面号序列为：4，7，0，7，1，0，1，2，1，2，6.随着进程的访问，栈中页面号的变化情况如图所示。2 2LRU置换算法的硬件支持置换算法的硬件支持第五章虚拟存储器5.3.2最近最久未使用和最少使用置换算法最近最久未使用和最少使用置换算法3.最少使用最少使用(Least Frequently Used,
18、LFU)置换算法置换算法该置换算法选择在最近时期使用最少的页面作为淘汰页。在采用LFU算法时，应为在内存中的每个页面设置一个移位寄存器，用来记录该页面被访问的频率。第五章虚拟存储器 1 1简单的简单的Clock置换算法置换算法又称为最近未用(Not Recently Used，NRU)算法，该算法为每页设置一位访问位，再将内存中的所有页面都通过链接指针链接成一个循环队列。5.3.3Clock置换算法置换算法 置换算法在选择一页淘汰时，只需检查页的访问位。如果是0，就选择该页换出；若为1，则重新将它置0，暂不换出，给予该页第二次驻留内存的机会，再按照FIFO算法检查下一个页面。11.16第五章虚
19、拟存储器图图5-8简单简单Clock置换算法的流程和示例置换算法的流程和示例 第五章虚拟存储器 2.2.改进型改进型ClockClock置换算法置换算法在改进型Clock算法中，须考虑页面的使用情况、置置换换代代价价。在选择页面换出时，既要是未使用过的页面，又要是未被修改过的页面。由访问位A和修改位M组合成下面四种类型的页面：1类(A=0,M=0)该页最近既未被访问，又未被修改过。2类(A=0,M=1)该页最近既未被访问，但已被修改。3类(A=1,M=0)4类(A=1,M=1)5.3.3Clock置换算法置换算法第五章虚拟存储器该算法须同时检查访问位与修改位，以确定该页是四类页面中的哪一种。其
20、执行过程可分成以下三步：(1)从指针所指示的当前位置开始，扫描循环队列，寻找A=0且M=0的第一类页面。在第一次扫描期间不改变访问位A。2.2.改进型改进型Clock置换算法置换算法(2)如果第一步失败，则开始第二轮扫描寻找A=0且M=1的第二类页面。在第二轮，将所有扫描过的页面的访问位都置0。(3)如果第二步失败，将所有的访问位复0。然后重复第一步，必要时再重复第二步。5.3.3Clock置换算法置换算法第五章虚拟存储器 5.3.4 页面缓冲算法页面缓冲算法(Page Buffering Algorithm,PBA)1.1.影响页面换进换出效率的若干因素影响页面换进换出效率的若干因素(1)页
21、面置换算法。影响页面换进换出效率最重要的因素(2)写回磁盘的频率。对于已经被修改过的页面，在将其换出时，应写回磁盘。减少已修改页面换出的开销。(3)读入内存的频率。减少将页面从磁盘读入内存的频率，减少页面换进的开销。第五章虚拟存储器lVAX/VMS操作系统中所使用的PBA：采用可变分配和局部置换方式，置换算法采用FIFO。PBA算法的实现需要内存中设置的两个链表：空闲页面链表、修改页面链表。该算法规定将一个被淘汰的页放入两个链表中的一个，即如果页面未被修改，就将它直接放入空闲链表中；否则，便放入修改页面链表中。l须注意，这时页面在内存中并不做物理上的移动，而只是将页表中的表项移到上述两个链表之
22、一中。l采用PBA算法时，被换出的页面仍留在内存的空闲块中，所有的空闲块形成一个空闲页面缓冲池。5.3.4 页面缓冲算法页面缓冲算法(Page Buffering Algorithm,PBA)第五章虚拟存储器思考一思考一 在一采取局部置换策略的请求分页系统中，分配给某个作业的内存块数为4，其中存放的四个页面的情况如下表：物理块 虚页号 装入时间 最后一次访问时间 访问位 修改位 0 2 60 157 0 1 1 1 160 161 1 0 2 0 26 158 0 0 3 3 20 163 1 1 表中的所有数字均为十进制数，所有时间都是从进程开始运行时，从0开始计数的时钟数。请问，如果系统采
23、用下列置换算法，将选择哪一页进行换出？(1)FIFO算法；(2)LRU算法；(3)改进的Clock算法.第五章虚拟存储器思考二思考二 在一个请求分页系统中，假如一个作业的页面走向为4，3，2，1，4，3，5，4，3，2，1，5，目前它还没有任何页装入内存，当分配给该作业的物理块数目M分别为3和4时，请分别计算采用LRU和FIFO页面淘汰算法时，访问过程中所发生的缺页次数和缺页率，并比较所得的结果。第五章虚拟存储器思思考考三三 某虚拟存储器的用户空间共有32个页面，每页1KB，主存16KB。假定某时刻系统为用户的第0、1、2、3页分配的物理块号为5、10、4、7，而该用户作业的长度为6页，试将十
24、六进制的虚拟地址0A5C、103C、1A5C转换成物理地址。第五章虚拟存储器5.4“抖动抖动”与工作集与工作集5.4.1 多道程序度与多道程序度与“抖动抖动”u“抖动”：系统中运行的进程太多，由此分配给每一个进程的物理块太少，不能满足进程正常运行的基本要求，致使每个进程在运行时频繁地出现缺页。第五章虚拟存储器 工作集是指在某段时间间隔内，进程要访问的页面集合。经常被使用的页面需要在工作集中，而长期不被使用的页面要从工作集中被丢弃。5.4.2 工作集工作集 工作集模型的原理是：操作系统跟踪每个进程的工作集，并为进程分配大于其工作集的物理块。如果还有空闲物理块，则可以再调一个进程到内存以增加多道程
25、序数。如果所有工作集之和增加以至于超过了可用物理块的总数，那么操作系统会暂停一个进程，将其页面调出并且将其物理块分配给其他进程，防止出现抖动现象。第五章虚拟存储器5.4.3 “抖动抖动”的预防方法的预防方法1.采用局部置换策略采用局部置换策略 页面分配采用可变分配方式，置换采用局部置换策略。当某进程发生缺页时，只能在分配给自己的内存空间内进行置换，不允许从其他进程去获得新的物理块。2.把工作集算法融入到处理机调度中把工作集算法融入到处理机调度中 当调度程序试图从外存调入一个新作业到内存，必须先检查每个进程在内存的驻留页面是否足够多。如果足够多，此时便可以从外存调入新作业。第五章虚拟存储器5.4
26、.3 “抖动抖动”的预防方法的预防方法3.利用利用“L=S”准则调节缺页率准则调节缺页率4.选择暂停的进程选择暂停的进程 L是缺页之间的平均时间，S是平均缺页服务时间，即用于置换一个页面所需的时间。当L远比S大，说明很少发生缺页；反之，如果L比S小，则说明频繁发生缺页，缺页的速度已超过磁盘的处理能力。当L与S接近时，磁盘和处理机都达到它们的最大利用率。当多道程序度偏高时，为了防止发生“抖动”，系统必须减少多道程序的数目。因此暂停某些当前活动的进程。第五章虚拟存储器5.5请求分段存储管理方式请求分段存储管理方式 1 1请求段表机制请求段表机制在请求分段式管理中所需的主要数据结构是请求段表。程序运
27、行之前，只需先调入调入少数几个分段便可启动。当所访问的段不再内存中，可请求OS将所缺的段调入内存。5.5.1请求分段中的硬件支持请求分段中的硬件支持11.23？第五章虚拟存储器2.缺段中断机构缺段中断机构在请求分段系统中，每当发现运行进程所要访问的段尚未调入内存时，便由缺段中断机构产生一缺段中断信号，进入OS后由缺段中断处理程序将所需的段调入内存。缺段中断机构与缺页中断机构类似，它同样需要在一条指令的执行期间，产生和处理中断，以及在一条指令执行期间，可能产生多次缺段中断。缺段中断的处理过程如图所示。由于段不是定长的，这使对缺段中断的处理要比对缺页中断的处理复杂。5.5.1请求分段中的硬件支持请
28、求分段中的硬件支持第五章虚拟存储器图图5-12请求分段系统中的中断处理过程请求分段系统中的中断处理过程 第五章虚拟存储器 3.3.地址变换机构地址变换机构因为被访问的段并非全在内存，所以在地址变换时，若发现所要访问的段不在内存，必须先将所缺的段调入内存，并修改段表，然后才能再利用段表进行地址变换。5.5.1请求分段中的硬件支持请求分段中的硬件支持图图5-13请求分段系统的地址变换过程请求分段系统的地址变换过程 第五章虚拟存储器1.1.共享段表共享段表所有各共享段都在共享段表中占有一表项.5.5.2分段的共享与保护分段的共享与保护整型变量整型变量countcount记录有多少个进程需要共享该分段
29、记录有多少个进程需要共享该分段第五章虚拟存储器2.2.共享段的分配与回收共享段的分配与回收1)1)共享段的分配共享段的分配对第一个请求使用该共享段的进程，由系统为该共享段分配一物理区，再把共享段调入该区，同时将该区的始址填入请求进程的段表的相应项中，还须在共享段表中增加一表项，填写有关数据，把count置为1；之后，当又有其它进程需要调用该共享段时，只需在调用进程的段表中增加一表项，填写该共享段的物理地址；在共享段的段表中，填 上 调 用 进 程 的 进 程 名、存 取 控 制 等，再 执 行count=count+1操作。5.5.2分段的共享与保护分段的共享与保护第五章虚拟存储器 2)共享段
30、的回收共享段的回收当共享此段的某进程不再需要该段时，应将该段释放，包括撤消在该进程段表中共享段所对应的表项，以及执行count=count-1操作。若结果为0，则须由系统回收该共享段的物理内存，以及取消在共享段表中该段所对应的表项，表明此时已没有进程使用该段；否则(减1结果不为0)，只是取消调用者进程在共享段表中的有关记录。5.5.2分段的共享与保护分段的共享与保护2.2.共享段的分配与回收共享段的分配与回收第五章虚拟存储器3 3分段保护分段保护目前，常采用以下几种措施来确保信息的安全。1)越界检查5.5.2分段的共享与保护分段的共享与保护2)存取控制检查在段表的每个表项中设置了“存取控制”字
31、段,通常的访问方式有：(1)只读;(2)只执行，即只允许进程调用该段去执行;(3)读/写，即允许进程对该段进行读/写访问。第五章虚拟存储器思思考考四四 假如一个程序的段表如下表所示，其中存在位为1标识段在内存，存取控制字段中W表示可写，R表示可读，E表示可执行。对下面的指令，在执行时会产生什么样的结果？(1)STORE R1,0,70 (2)STORE R1,1,20 (3)LOAD R1,3,20 (4)LOAD R1,3,100 (5)JMP 2,100 段段 表表 段号 存在位 内存始址 段长 存取控制 其它信息 0 0 500 100 W 1 1 1000 30 R 2 1 3000 200 E 3 1 8000 80 R 4 0 5000 40 R第五章虚拟存储器此课件下载可自行编辑修改，仅供参考！此课件下载可自行编辑修改，仅供参考！感谢您的支持，我们努力做得更好！谢谢感谢您的支持，我们努力做得更好！谢谢