操作系统页式存储管理PPT.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,6.4,页式存储管理,6.4.1,基本原理,6.4.2,管理,6.4.3,硬件支持,6.4.4,静态页式管理,6.4.5,请求页式管理,6.4.6,页式管理的优缺点,1,6.4.1,基本思想（工作原理）,用户程序划分,把用户程序按逻辑页划分成大小相等的部分，称为页。从,0,开始编制页号，页内地址是相对于,0,编址,逻辑地址,页号 页内地址,2,内存空间,按页的大小划分为大小相等的区域，称为内存块（物理页面）,内存分配,以页为单位进行分配，并按作业的页数多少来分配。逻辑上相邻的页，物理上不一定相邻,3,4,6.4.2,管理,页表：系统为每个进程建立一个页表，页表给出逻辑页号和具体内存块号相应的关系。,页号,页面号,0,2,1,3,2,8,5,6.4.3,硬件支持,p,页表,地址越界,l,比较,P=l,b,+,页号,p,页内地址,d,P,d,物理地址,页表地址寄存器,页表长度寄存器,逻辑地址,地址映射机制,二次访问内存,第一次取地址,第二次存取数据,效率较低,6,p,页表,地址越界,l,比较,P=l,p,p,.,.,.,快表,b,+,页号,p,页内地址,d,P,d,物理地址,页表地址寄存器,页表长度寄存器,逻辑地址,地址映射机制,高速,缓存,7,6.4.4,静态页式管理,将程序的逻辑地址空间和物理内存划分为固定大小的页或页面,(page or page frame),，程序加载时，分配其所需的所有页，这些页不必连续。,8,9,10,1.,简单页式管理的数据结构,页表：每个进程有一个页表，描述该进程占用的物理页面及逻辑排列顺序；,逻辑页号（本进程的地址空间）,物理页面号（实际内存空间）；,存储页面表：整个系统有一个存储页面表，描述物理内存空间的分配使用状况。,数据结构：位示图，空闲页面链表；,请求表：整个系统有一个请求表，描述系统内各个进程页表的位置和大小，用于地址转换，也可以结合到各进程的,PCB,里；,11,2.,分配算法,请求,n,个页面,存储页面表中有,n,个空闲页面吗,无法分配,返回,设置请求表，将页表,始址，页表长度置入,请求表中，置状态已分配,搜索存储页面表，分配,n,个页面，并将页面号,填入页表中,12,3.,简单页式管理的地址变换,指令所给出地址分为两部分：逻辑页号，页内偏移地址,查进程页表，得物理页号,物理地址,为缩短查找时间，引入快表，按内容查找,(associative mapping),，即逻辑页号,物理页号,13,14,页号,页面号,0,2,1,3,2,8,设每个页面长度为,1k,，指令,LOAD 1,2500,的虚地址为,100,，依据左图进行地址变换。,首先，需要有一个页表地址寄存器和页表长度寄存器。系统把所调度执行的进程页表始址和长度从请求表中取出置入寄存器,然后，找到页表。由虚地址,100,可知，指令在第,0,页的第,100,单元中，对应内存地址为,1024*2+100=2148,当,CPU,执行到第,2148,单元时，需要从虚地址,2500,中取数据，地址变换机构首先将,2500,的页号和页内位移求出：,2,；,452,由页表可知，对应内存,8,号，内存地址为,1024*8+452=8644,以上由硬件地址变换机构自动完成。,15,优点：,没有外碎片，每个内碎片不超过页大小。,一个程序不必连续存放。,便于改变程序占用空间的大小。即随着程序运行而动态生成的数据增多，地址空间可相应增长。,缺点：程序全部装入内存，受到内存可用页面数的限制。,16,6.4.5,动态（请求）页式管理,在进程开始运行之前，不是装入全部页面，而是装入部分页面，之后根据进程运行的需要，动态装入其它页面；当内存空间已满，而又需要装入新的页面时，则根据某种算法淘汰某个页面，以便装入新的页面。,17,请求页式的地址变换与静态页式的相同。,但是，由于只让部分页面驻留内存，如何发现那些不在内存的虚页以及如何处理是请求页式必须处理的问题。,第一个问题可以通过扩充页表的方法解决；第二个问题当内存没有空闲页面时即是页面置换算法的问题。,18,页表表项,页号、驻留位、内存块号、外存始址、访问位、修改位,驻留位（中断位）：表示该页是在内存还是在外存,访问位：根据访问位来决定淘汰哪页（由不同的算法决定）,修改位：查看此页是否在内存中被修改过,页号,中断位,内存块号,外存始址,访问位,修改位,19,缺页中断处理,在地址映射过程中，在页表中发现所要访问的页不在内存，则产生缺页中断。操作系统接到此中断信号后，就调出缺页中断处理程序，根据页表中给出的外存地址，将该页调入内存，使作业继续运行下去,如果内存中有空闲块，则分配一页，将新调入页装入内存，并修改页表中相应表项,若此时内存中没有空闲块，则要淘汰某页，若该页在内存期间被修改过，则要将其写回外存,20,查快表,有登记,无登记,查页表,登记入快表,发缺页中断,在主存,在辅存,形成绝对地址,继续执行指令,重新执行,被中断指令,恢复现场,调整页表和,主存分配表,装入所需页面,主存有空闲块,保护现场,有,选择调出页面,未修改,已修改,把该页写回,辅存相应位置,硬件完成,逻辑地址,无,该页修改过？,21,页面置换算法,随机置换算法,先进先出算法,(FIFO),最近最久未使用算法,(LRU,Least Recently Used),时钟页面替换算法,(Clock Policy),最佳置换算法,(OPT,optimal),22,1.,先进先出算法,(FIFO),选择建立最早的页面被置换。可以通过链表来表示各页的建立时间先后。性能较差。较早调入的页往往是经常被访问的页，这些页在,FIFO,算法下被反复调入和调出。并且有,Belady,现象。,23,Belady,现象：采用,FIFO,算法时，如果对一个进程未分配它所要求的全部页面，有时就会出现分配的页面数增多，缺页率反而提高的异常现象。,Belady,现象的描述：一个进程,P,要访问,M,个页，,OS,分配,N,个内存页面给进程,P,；对一个访问序列,S,，发生缺页次数为,PE,（,S,N,）。当,N,增大时，,PE(S,N),时而增大，时而减小。,Belady,现象的原因：,FIFO,算法的置换特征与进程访问内存的动态特征是矛盾的，即被置换的页面并不是进程不会访问的。,24,Belady,现象的例子,进程,P,有,5,页程序访问页的顺序为：,1,2,3,4,1,2,5,1,2,3,4,5,；,如果在内存中分配,3,个页面，则缺页情况如下：,12,次访问中有缺页,9,次；,1,2,3,4,1,2,5,1,2,3,4,5,1,1,1,4,4,4,5,5,5,5,5,5,2,2,2,1,1,1,1,1,3,3,3,3,3,3,2,2,2,2,2,4,4,25,如果在内存中分配,4,个页面，则缺页情况如下：,12,次访问中有缺页,10,次；,1,2,3,4,1,2,5,1,2,3,4,5,1,1,1,1,1,1,5,5,5,5,4,4,2,2,2,2,2,2,1,1,1,1,5,3,3,3,3,3,3,2,2,2,2,4,4,4,4,4,4,3,3,3,26,2.,最近最久未使用算法,(LRU),该算法淘汰的页面是在最近一段时间里较久未被访问的那一页。它是根据程序执行时所具有的局部性来考虑的，即那些刚被使用过的页面，可能马上还要被使用，而那些在较长时间里未被使用的页面，一般说可能不会马上使用到。,27,给某作业分配了三块主存，该作业依次访问的页号为：,4,，,3,，,0,，,4,，,1,，,1,，,2,，,3,，,2,。于是当访问这些页时，页面淘汰序列的变化情况如下：,4,3,0,4,1,1,2,3,2,4,4,4,4,4,4,4,3,3,3,3,3,1,1,1,1,1,0,0,0,0,2,2,2,4,3,0,4,1,1,2,3,2,4,3,0,4,1,1,2,3,2,4,3,0,4,4,1,2,3,4,3,0,0,4,1,1,28,3.,时钟页面替换算法,(Clock Policy),一个页面首次装入主存时，其”引用位”置,0,。,在主存中的任何一个页面被访问时,其”引用位”置,1,。,淘汰页面时,存储管理从指针当前指向的页面开始扫描循环队列，把所迁到的”引用位”是,1,的页面的”引用位”清成,0,并跳过这个页面,;,把所迁到的”引用位”是,0,的页面淘汰掉,指针推进一步。,它是,LRU(,最近最久未使用算法,),和,FIFO,的折衷。,29,Page9 use=1,Page19,Use=1,Page1,Use=0,Page45,Use=1,Page191,Use=1,Page556,Use=0,Page13,Use=0,Page67,Use=1,Page33,Use=1,Page222,Use=0,下一个帧指针,n,0,1,2,3,4,5,6,7,8,（,a,）一个页替换前的缓冲区状态,Page9 use=1,Page19,Use=1,Page1,Use=0,Page45,Use=0,Page191,Use=0,Page727,Use=1,Page13,Use=0,Page67,Use=1,Page33,Use=1,Page222,Use=0,n,0,1,2,3,4,5,6,7,8,（,b,）下一页替换后的缓冲区状态,1,第,1,页框,当发生缺页中断时，将要进入主存的页面是,page727,指针指向的是,page45(,在页框,2,中,),。,Clock,页面替换算法执行如下：,page45,的”引用位”是,1,故它不能被淘汰掉，仅把其”引用位”清,0,指针推进。同样道理，,page191(,在页框,3,中,),也不能被替换,把其”引用位”清,0,指针继续推进。在下一页即,page556(,在页框,4,中,),它的”引用位”是,0,于是,page556,被,page727,替换,并把,page727,的”引用位”置,1,指针前进到下一页,page13(,在页框,5,中,),。算法执行到此结束。,30,4.,最佳算法,(OPT,optimal),选择“未来不再使用的”或“在离当前最远位置上出现的”页面被置换。这是一种理想情况，是实际执行中无法预知的，因而不能实现。可用作性能评价的依据。,4,3,0,4,1,1,2,3,2,4,4,4,4,1,1,2,2,2,3,3,3,3,3,3,3,3,0,0,0,0,0,0,0,31,(1),分配给进程的物理页面数,(2),页面本身的大小,(3),程序的编制方法,(4),页面淘汰算法,影响缺页次数的因素,32,例子,3,：内存分配一页,初始时第一页在内存；页面大小为,128,个整数；矩阵,A,128X128,按行存放,程序编制方法,1,：,For j:=1 to 128,For i:=1 to 128,Ai,j:=0;,程序编制方法,2,：,For i:=1 to 128,For j:=1 to 128,Ai,j:=0;,33,6.4.6,页式管理的优缺点,相对于分区管理而言，静态页式有效的解决了外部碎片的问题（当然有少量的内部碎片）；,但是，静态页式要求全部装入，不支持虚拟存储，因而有了请求页式，允许部分装入；,显然地，请求页式更能有效利用有限的内存页面，不过，这种方式需要有效解决缺页率的问题，尤其是页面置换的问题；,不论是静态还是请求方式，更多地是从物理页面的角度考虑和解决问题，有的时候，需要从逻辑角度考虑问题，比如共享，这就引入了段式管理方法。,34,习题：某程序在内存中分配三个页面，初始为空，页面走向为,4,，,3,，,2,，,1,，,4,，,3,，,5,，,4,，,3,，,2,，,1,，,5,，计算采用,FIFO,LRU,OPT,进行页面置换时相应的缺页次数。,35,4,3,2,1,4,3,5,4,3,2,1,5,4,4,4,1,1,1,5,5,5,5,5,5,3,3,3,4,4,4,4,4,2,2,2,2,2,2,3,3,3,3,3,1,1,FIFO,：缺页,9,次,36,4,3,2,1,4,3,5,4,3,2,1,5,4,3,2,1,4,3,5,4,3,2,1,5,4,3,2,1,4,3,5,4,3,2,1,4,3,2,1,4,3,5,4,3,2,LRU,：缺页,10,次,37,4,3,2,1,4,3,5,4,3,2,1,5,4,4,4,4,4,4,4,4,4,2,1,1,3,3,3,3,3,3,3,3,3,3,3,2,1,1,1,5,5,5,5,5,5,OPT,：缺页,7,次,38,一程序在运行过程中所访问的页面流为,3,，,5,，,4,，,2,，,5,，,3,，,1,，,3,，,2,，,5,，,1,，,3,，,1,，,5,，,2,。若采用,OPT,算法，则为该程序分配多少个实页最为合理（要求给出分配过程）？为什么？,39,