操作系统 第5章 虚拟存储器

第五章　虚拟存储器5.1　虚拟存储器概述5.2　请求分页存储管理方式5.3　页面置换算法5.4　“抖动”与工作集5.5　请求分段存储管理方式5.1　虚拟存储器概述常规存储管理方式的特征和局部性原理常规存储管理方式的特征一次性进程要一次性全部装入内存才可以运行引发两个问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 1）若进程对内存的要求超出物理内存总容量，则无法运行2）内存由于容量的限制，只能装入少量进程运行，限制了并发度5.1　虚拟存储器概述驻留性进程在其运行期间，始终“驻留”在内存暂时不用的程序和数据部分也占据内存空间，造成内存空间的浪费5.1　虚拟存储器概述局部性原理在一段时间内一个程序的执行往往呈现出高度的局部性， 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 现在时间与空间两方面时间局部性一条指令被执行了，则在不久的将来它可能再被执行空间局部性若某一存储单元被使用，则在一定时间内，与该存储单元相邻的单元可能被使用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　请求分页存储管理方式地址变换机构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：访问页面失败的次数）影响缺页率的因素页面大小进程所得物理块的数目页面置换算法程序固有特性5.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选择“未来不再使用的”或“在最远的将来被使用的”页面来置换。理论上最优，但是无法实现（由于一般程序的行为难以预料）可以作为评估其它页面置换算法的 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 5.3　页面置换算法例，假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1缺页中断次数=9缺页率=9/20=45%页面置换次数=65.3　页面置换算法先进先出（FIFO）页面置换算法系统将所有页面排入一个FIFO队列按各页进入内存的时间顺序排在FIFO队列队首的页面先被淘汰缺点先进入主存的页可能将被高频率反复使用而导致内外存置换次数增加存在Belady异常：有时分配给进程的物理块增加时，缺页中断次数也增加5.3　页面置换算法同例缺页中断次数=15缺页率=15/20=75%页面置换次数=125.3　页面置换算法再例5.3　页面置换算法最近最久未使用（LRU）置换算法选择最近最久未使用的页面予以淘汰该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t，当须淘汰一个页面时，选择现有页面中其t值最大的，即最近最久未使用的页面予以淘汰理论上可行，但实现代价很高5.3　页面置换算法同例缺页中断次数=12缺页率=12/20=60%页面置换次数=95.3　页面置换算法硬件支持寄存器每个页面设立移位寄存器，被访问时左边最高位置1，定期右移并且最高位补0，于是寄存器数值最小的是最久未使用页面。5.3　页面置换算法栈把被访问的页面移到栈顶，于是栈底的是最久未使用页面例，假定现有一进程所访问的页面的页面号序列为：　4，7，0，7，1，0，1，2，1，2，65.3　页面置换算法最少使用（LFU）置换算法为在内存中的每个页面设置一个移位寄存器，用来记录该页面被访问的频率每次访问某页时，便将该移位寄存器的最高位置1，再每隔一定时间右移一次在最近一段时间使用最少的页面将是∑Ri最小的页5.3　页面置换算法Clock置换算法简单的Clock置换算法也称最近未使用算法NRU，是LRU和FIFO的折衷内存中所有页面通过链接指针形成一个循环队列每页有一个访问位，某页被访问则其访问位置1在选择一页淘汰时，只需检查页的访问位。如果是0，就选择该页换出；若为1，则重新将它置0，暂不换出，而给该页第二次驻留内存的机会，再按照FIFO算法检查下一个页面。当检查到队列中的最后一个页面时，若其访问位仍为1，则再返回到队首去检查第一个页面。5.3　页面置换算法简单Clock置换算法的 流程 快递问题件怎么处理流程河南自建厂房流程下载关于规范招聘需求审批流程制作流程表下载邮件下载流程设计 和示例5.3　页面置换算法改进型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　页面置换算法算法：（1）指针从当前位置开始，开始第一轮扫描循环队列，寻找未使用且没有修改过的页面（第1类页面），找到则可换出。（2）如果找不到，则开始第二轮扫描，寻找未使用但修改过的页面（第2类页面），并且每经过一个页面时，将其访问位A设置为0。如果找到一个第2类页面，则可换出。（3）如果仍旧未找到合适的换出页面，则此时指针回到初始位置，且所有页面其访问位A为0。再转回（1）继续工作。5.3　页面置换算法页面缓冲算法（PBA）是对FIFO算法的发展，通过被置换页面的缓冲，有机会找回刚被置换的页面被置换页面的选择和处理：由操作系统中专门的页面置换进程，用FIFO算法选择被置换页，把被置换的页面放入两个链表（空闲页面链表和已修改页面链表）之一如果页面未被修改，就将其归入到空闲页面链表的末尾否则将其归入到已修改页面链表5.3　页面置换算法访问内存的有效时间t—访问一次内存的时间；—查找快表的时间；a—快表的命中率；f—缺页率；—缺页中断处理时间被访问页在内存，且其对应的页表项在快表中EAT=+t被访问页在内存，且其对应的不页表项在快表中EAT=2×(+t)被访问页不在内存EAT=+2×(+t)加入快表命中率和缺页率等因素EAT=+a×t+(1-a)×[t+f×(++t)+(1-f)×(+t)]5.4　“抖动”与工作集多道程序度与“抖动”多道程序度与处理机的利用率5.4　“抖动”与工作集产生“抖动”的原因在虚存中，页面在内存与外存之间频繁调度，以至于调度页面所需时间比进程实际运行的时间还多，此时系统效率急剧下降，甚至导致系统崩溃，这种现象称为“颠簸”或“抖动”产生原因分配给进程的物理页面数太少页面置换算法不合理5.4　“抖动”与工作集工作集工作集的基本概念1968年由Denning提出并推广基本思想：根据程序的局部性原理，一般情况下，进程在一段时间内总是集中访问一些页面，这些页面称为活跃页面，如果分配给一个进程的物理块数太少，使该进程所需的活跃页面不能全部装入内存，则进程在运行过程中将频繁发生缺页中断如果能为进程提供与活跃页面数相等的物理块数，则可减少缺页中断次数5.4　“抖动”与工作集工作集的定义指在某段时间间隔△里，进程实际所要访问的页面集合内容取决于三个因素访页序列特性时间t窗口尺寸(△)5.4　“抖动”与工作集“抖动”的预防方法采取局部置换策略把工作集算法融入到处理机调度中利用“L=S”准则调节缺页率选择暂停的进程5.5　请求分段存储管理方式请求分页系统建立的虚拟存储器，是以页面为单位进行换入、换出操作的。在请求分段系统中实现的虚拟存储器，以分段为单位进行换入和换出。程序在运行之前，只需要装入必要的若干个分段即可运行。当访问的分段不在内存时，可由OS将所缺少的段调入内存。5.5　请求分段存储管理方式请求分段中的硬件支持段表机制存取方式：标记本段存取属性，如读R，写W，执行X访问字段A：记录本段使用的频繁程度修改位：是否在调入内存后做过修改存在位：本段是否装入内存增补位：该段是否动态增长过，在请求页式中没有该位外存地址：段号段长段的基址存取方式访问字段A修改位M存在位p增补位外存起址5.5　请求分段存储管理方式缺段中断机构要有专门的缺段中断处理程序特点指令和操作数必定不会跨越在段边界上由于段的长度是不固定的，处理比缺页系统复杂调入一个段可能要淘汰几个内存中的段中断处理过程请参看P174图5-125.5　请求分段存储管理方式地址变换请求分段系统的地址变换机构，是在分段系统的地址变换机构基础上形成的由于分段可能不在内存，因此会引起缺段中断。先将需要的段调入内存，修改段表，然后再利用段表进行地址变换地址变换过程请参看P174图5-135.5　请求分段存储管理方式分段保护与共享在多道程序系统中，尤其在分时系统中，数据共享是很重要的，在分段系统中，各共享进程应能访问被共享的段，所以共享的方法是使这些共享用户的逻辑空间中的段指向相同的段号，在共享中必须小心处理的一个问题是共享段的保护问题。5.5　请求分段存储管理方式共享段表为了实现共享，可在系统中配置一张段表，所有的共享段都在共享段表中占有一表项。表项中记录了共享段的段号、段长、内存始址、存在位等信息，并记录有共享此分段的每个进程的情况。作业1的段表作业2的段表共享段5.5　请求分段存储管理方式共享进程计数记录了多少个进程在共享该分段存取控制字段对于共享段的不同进程，应该赋予不同的存取权限段号不同的进程可以使用不同的段号来访问相同的共享段5.5　请求分段存储管理方式共享段的分配和回收分配第一个请求的进程，由系统分配一物理块，调入共享段，设置相关表项信息，并置count=1以后的进程，在自己段表中增加一项，添入共享段信息；在共享段表项中做count=count+1，填写进程相关信息回收做count=count–1如果count=0，则将该共享段回收5.5　请求分段存储管理方式分段保护越界检查在进行存储访问时，要将逻辑地址的段号与段表长度进行比较，如果超出则发生越界中断信号；其次，将段内地址与段表中该段的长度进行比较，如果有效才进行转换，否则产生越界中断信号5.5　请求分段存储管理方式存取控制检查：用于规定对该段的访问权限。通常的访问方式有：读：允许用户对该段/页内任何信息或其副本进行读操作。写：允许用户修改该段/页内任何信息直至撤消整个段/页。执行：用户可以执行该段/页程序，数据段/页除外。增加：用户可在段/页的末尾添加信息，但不允许修改已存在于段/页中的信息。5.5　请求分段存储管理方式环保护检查是一种功能较完善的保护机制思想：将所有的程序分成不同的级别，分别放置在不同的环上。内环（编号小，在内侧）的程序具有高优先权，外环的程序优先权低操作系统核心安排在0环内；重要程序和操作系统服务安排在中间环；一般应用程序安排在外环一个程序可以直接访问在相同环或低优先级环（比自身相对靠外的环）上的数据一个程序访问高优先级（比自己靠内的环）时，通过系统调用方式实现作业P177：13（取M=4，采用FIFO和LRU）