操作系统原理 第八章 虚拟存储管理技术.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第八章 虚拟存储管理技术,实存储管理技术要求把进程全部装入内存才能运行，在运行过程中，会出现两种可能：,1,）,要求运行的进程所需的内存空间大于系统的内存空间，只有部分进程能够装入内存运行，而其他进程只有留在外存中等待。,2,）,逻辑地址空间大于存储空间的进程无法在系统中运行。,两种解决方案：从物理上增加内存容量或从逻辑上扩充内存容量（虚拟存储）,一、,虚拟存储器的概念,1,、局部性原理,局部性原理,(principle of locality),：指程序在执行过程中的一个较短时期，所执行的指令地址和指令的操作数地址，分别局限于一定区域。,时间局限性,空间局限性,局部性原理是实现虚拟存储器的理论基础。,2,、,虚拟存储器,在程序装入时，不必将其全部读入到内存，而只需将当前需要执行的部分页或段读入到内存，就可让程序开始执行。,在程序执行过程中，如果需执行的指令或访问的数据尚未在内存（称为缺页或缺段），则由处理器通知操作系统将相应的页或段调入到内存，然后继续执行程序。,另一方面，操作系统将内存中暂时不使用的页或段调出保存在外存上，从而腾出空间存放将要装入的程序以及将要调入的页或段。只需程序的一部分在内存就可执行。,所谓虚拟存储器，就是仅把进程的一部分装入内存便可运行的存储器系统，它具有请求调入功能和置换功能，是能从逻辑上对内存容量进行扩充的一种存储器系统。,虚拟存储器的逻辑容量由系统的寻址能力和外存容量之和所决定。,多次性：一个作业被分成多次调入内存运行；,对换性：允许在作业的运行过程中进行换进、换出；,虚拟性：能从逻辑上扩充内存容量，是用户,“,看到,”,的内存容量远大于实际大小。,该特征是以上两个特征为基础的。,二、,请求分页式存储管理方式,请求式分页也称虚拟页式存储管理，与纯分页存储管理不同，请求式分页管理系统在进程开始运行之前，不是装入全部页面，而是装入一个或零个页面，之后根据进程运行的需要，动态装入其它页面；当内存空间已满，而又需要装入新的页面时，则根据某种算法淘汰某个页面，以便装入新的页面,。,在分页式存储管理的基础上，增加了请求调页功能、页面置换功能而形成的页式虚拟存储系统。,系统需要解决下面三个问题：,1,）,系统如何获知进程当前所需页面不在主存。,2,）,当发现缺页时，如何把所缺页面调入主存。,3,）当主存中没有空闲的页框时，为了要接受一个新页，需要把老的一页淘汰出去，根据什么策略选择欲淘汰的页面。,1,、,请求分页式存储管理的基本概念,1,）基本原理,运行前将一部分页面装入内存，另外一部分页面则装入外存。在程序运行过程中，如果所访问的页面不再内存中，则发生缺页中断，操作系统进行页面动态调度：,a,）,找到被访问页面在外存中的地址。,b,）,在内存中找一个空闲块，如果没有，则按照淘汰算法选择一个内存块，将此块内容写回外存，修改页表。,c,）,读入所需得页面，修改页表。,d,）重新启动进程，执行被中断的指令。,2,）页表机制,页表中除了页号和物理块，增加若干项，以完成调入功能和置换功能,a,）状态位,P,：指示该页是否已经调入内存，,0,表示该页已在内存，,1,表示该页不再内存。,b,）访问位,A,：纪录该页在一段时间内被访问的次数，或最近已经有多少时间没有访问，供置换算法选择页面时参考。,c,）修改为,M,：纪录该页面在调入内存后是否被修改过。,d,）外存地址：指出该页在外存上的地址，通常是物理块号，供调入该页时使用。,3,）地址变换机构,图,8-2,2,、内存分配策略,1,）内存页面分配策略,a,）平均分配,b,）按进程大小比例分配,c,）,按进程优先级比例分配,d,）按进程长度和优先级比例分配,2,）外存块的分配策略,静态分配：一个进程在运行前，将所有页面全部装入外存。当一个外存页面被调入内存，所占用的外存页面不释放。,动态分配：一个进程运行前，仅将没有装入内存的部分装入外存，当某页面被调入内存时，释放所占用的外存空间。,3,、页面调入时机,1,）请求调页策略,发生缺页中断时进行页面调度,2,）预调页策略,每次调入若干个页面,4,、页面调度算法,1,）最佳置换算法（,OPT,）,选择,“,未来不再使用的,”,或,“,在离当前最远位置上出现的,”,页面被置换。这是一种理想情况，是实际执行中无法预知的，因而不能实现。可用作性能评价的依据。,假定系统为某进程分配了三个物理块，,并考虑有以下的页面号引用串：,7,，,0,，,1,，,2,，,0,，,3,，,0,，,4,，,2,，,3,，,0,，,3,，,2,，,1,，,2,，,0,，,1,，,7,，,0,，,1,2,）,先进先出置换算法（,FIFO,）,选择建立最早的页面被置换。可以通过链表来表示各页的建立时间先后。性能较差。较早调入的页往往是经常被访问的页，这些页在,FIFO,算法下被反复调入和调出。,Belady,现象：采用,FIFO,算法时，如果对一个进程未分配它所要求的全部页面，有时就会出现分配的页面数增多，缺页率反而提高的异常现象。,Belady,现象的描述：一个进程,P,要访问,M,个页，,OS,分配,N,个内存页面给进程,P,；对一个访问序列,S,，发生缺页次数为,PE,（,S,N,）。当,N,增大时，,PE(S,N),时而增大，时而减小。,Belady,现象的原因：,FIFO,算法的置换特征与进程访问内存的动态特征是矛盾的，即被置换的页面并不是进程不会访问的。,3,）,最近最久未使用置换算法（,LRU,）,选择内存中最久未使用的页面被置换。这是局部性原理的合理近似，性能接近最佳算法。但由于需要记录页面使用时间的先后关系，硬件开销太大。,硬件机构如：,1,）计时法,系统为每个页面增设一个计时器，页面被访问时，当时的绝对时钟内容被复制到对应的计时器中，这样系统记录了内存所有页面最后一次被访问的时候，淘汰时，选取计时器中最小的页面淘汰。,2,）堆栈法,按照页面最后一次访问的时间次序依次排列到堆栈中。进程访问某一页时，其对应的页面号由栈内取出压入栈顶，因此，栈顶始终是最新被访问页面的页面号，栈底则是最近最久没有使用的页面号。,4,）最近未使用置换算法（,NRU,）,近似于,LRU,算法，不但希望淘汰最近未使用的页面，还希望被挑选的页面在内存驻留期间，其页面内容没有给修改过，因此增加两个硬件位：访问位和修改位。,0,和,1,，,0,表示未访问或未修改。,由访问位,A,和修改位,M,可以组合成下面四种类型的页面：,1,类,(A=0,M=0):,表示该页最近既未被访问，,又未被修改，,是最佳淘汰页。,2,类,(A=0,M=1),：,表示该页最近未被访问，,但已被修改，,并不是很好的淘汰页。,3,类,(A=1,M=0),：,最近已被访问，,但未被修改，,该页有可能再被访问。,4,类,(A=1,M=1):,最近已被访问且被修改，,该页可能再被访问。,5,）,Clock,置换算法,将,NRU,算法改变实现方式，换成,clock,页面，如图,8-3,将所有的页面保存在一个类似时钟表面的环形链表中，用一个表指针指向可能淘汰的页面。,补充：影响缺页次数的因素,1,）分配给程序的物理页数目,分配给程序的物理页面数多，则同时装入内存的页面数就多，减少了缺页中断的次数，降低了缺页中断率。根据实验分析，对一共有,n,页的进程来说，只要能分到,n/2,块内存空间就可以使系统获得最高效率。,2,）页面大小,页面大小取决于内存快的大小，页面大每次装入一页的信息量就大，减少了缺页中断的次数。,3,）程序的编制方法,4,）页面置换算法,5,、,请求分页系统的性能分析,1,）,缺页率对有效访问时间的影响,对存贮器的访问时间,t,，缺页率为,p,，则有效访问时间,=,（,1-p,）,t+p*,缺页中断时间,缺页中断时间由三部分组成：缺页中断服务时间，将所缺的页读入的时间，进程重新执行时间，其中第二个所占的时间最长,2,）,工作集,图,8-4,工作集理论就其本质而言是最近最久未使用置换算法的发展。粗略的说，工作集就是进程在某个时间段内实际要访问的页面的集合。,具体的说，运行在,t-Tt,这个时间段内所访问的页面的集合称为该进程在时间,t,的工作集，记为,W(t,T),T,为工作集的窗口尺寸，把工作集中包含的页面数称为工作集尺寸。,工作集大小可粗略的看成图,8-4,种曲线拐点处的物理快数。,三、,请求分段式存储器管理方式,1,、,请求分段式存储管理的基本概念,1,）基本原理,2,）段表机制,原来段表中有段名、段长和段的基址，另外需要增加若干项：,a,）存取方式：存储属性（读、写、只读）,b,）访问字段：纪录该段在一段时间内被访问的次数，或最近多长时间未被访问，提供置换算法选择段使用。,c,）修改位：是否被修改过,d,）存在位：说明本段是否被调入内存,e,）增补位：表示本段是否在运行过程中，是否进行过动态增长,f,）外存地址：本段在外存上的起始地址，通常是物理快号，共调入该段时使用。,2,、,分段共享和保护,1,）,分段共享,系统中配置一张共享段表，所有共享段都在共享段表中有一个表项，还记录有共享此段的每个进程的情况，包括：,a,）共享进程数,b,）存取控制字段,2,）,分段保护,a,）越界保护,b,）存取控制检查,