操作系统原理课件 第七章 存储管理 3

第七章存储管理7.4页式存储管理7.4.1页式系统应解决的问题一、问题的提出分区存储管理的主要问题是碎片问题。在采用分区存储管理的系统中，会形成一些非常小的分区，最终这些非常小的分区不能被系统中的任何用户（程序）利用而浪费。造成这样问题的主要原因是用户程序装入内存时是整体装入的，为解决这个问题，提出了分页存储管理技术。7.4页式存储管理7.4.1页式系统应解决的问题二、分页的概念程序地址空间分成大小相等的页面，同时把内存也分成与页面大小相等的块，当一个用户程序装入内存时，以页面为单位进行分配。页面的大小是为2n,通常为1KB，2KB，nKB等。7.4页式存储管理7.4.1页式系统应解决的问题页式存储管理要解决如下问题：1、页式存储管理系统的地址映射；2、调入策略；3、淘汰策略；4、放置策略。7.4页式存储管理7.4.2页式地址变换一、页表页表是页式存储管理的数据结构，它包括用户程序空间的页面与内存块的对应关系、页面的存储保护和存取控制方面的信息。页号内存块号存取控制状态其它在实际的系统中，为了节省存储空间，在页表中可以省去页号这个表目。7.4页式存储管理7.4.2页式地址变换7.4页式存储管理7.4.2页式地址变换二、虚地址结构(程序字)虚地址是用户程序中的逻辑地址，它包括页号和页内地址（页内位移）。区分页号和页内地址的依椐是页的大小，页内地址占虚地址的低位部分，页号占虚地址的高位部分。假定页面大小1024字节，虚地址共占用2个字节(16位)页号页内地址（位移量）PW1510907.4页式存储管理7.4.2页式地址变换7.4页式存储管理7.4.2页式地址变换三、页式地址映射7.4页式存储管理7.4.2页式地址变换三、页式地址映射1、虚地址（逻辑地址、程序地址）以十六进制、八进制、二进制的形式给出A、将虚地址转换成二进制的数；B、按页的大小分离出页号和位移量（低位部分是位移量，高位部分是页号）；C、根据题意产生页表；D、将位移量直接复制到内存地址寄存器的低位部分；以页号查页表，得到对应页装入内存的块号，并将块号转换成二进制数填入地址寄存器的高位部分，从而形成内存地址。例：在页式存储管理系统中，逻辑地址长度为16位，页面大小为4096字节，现有一逻辑地址为2F6AH，且第0、1、2页依次存放在物理块5、10、11中，问相应的物理地址为多少？解：由题可知，本分页系统的逻辑地址结构如下图所示。逻辑地址2F6AH的二进制数表示如下：0010111101101010高位四位0010为页号，低位十二位为页内位移。即逻辑地址的页号为2，依题知该页存放在第11块中，用十六进制表示块号为B，故物理地址为BF6AH。页号P页内位移01112157.4页式存储管理7.4.2页式地址变换三、页式地址映射2、虚地址以十进制数给出页号＝虚地址/页大小位移量＝虚地址%页大小根据题意产生页表；以页号查页表，得到对应页装入内存的块号内存地址＝块号×页大小＋位移量7.4页式存储管理7.4.2页式地址变换三、页式地址映射例2：有一系统采用页式存储管理，有一作业大小是8KB，页大小为2KB，依次装入内存的第7、9、10、5块，试将虚地址7145，3412转换成内存地址。7.4页式存储管理7.4.2页式地址变换虚地址3412P＝3412/2048＝1W＝3412%2048＝1364MR=9*2048+1364=19796虚地址3412的内存地址是：197967.4页式存储管理7.4.2页式地址变换虚地址7145P＝7145/2048＝3W＝7145%2048＝1001MR=5*2048+1001=11241虚地址7145的内存地址是：112417.4页式存储管理7.4.2页式地址变换四、采用相应技术加快页表的查询速度在页式存储技术中，我们可看到每访问一次内存，就要做两次访问内存的工作，即，查页表时要作一次访问内存的工作，然后是访问程序要求访问的内存，这样，存取速度降低一倍，将会影响整个系统的使用效率。在早期的计算机系统中有的采用联想存储器的技术来加快查表的速度，有的采用寄存器做页表。7.4页式存储管理7.4.3请调策略一、问题的提出在页式存储管理提高了内存的利用效率，但并不为用户提供虚存，换句话说，当一个用户程序的页数大于当前总空闲内存块数时，系统就不能将该程序装入运行。即用户程序将受到物理内存大小的限制。为了解决这个问题，人们提出请求分页存储管理技术。7.4页式存储管理7.4.3请调策略二、请求分页概念请求分页技术当一个用户程序要调入内存时，不是将该程序全部装入内存，而是只装入部分页到内存，就可启动程序运行，在运行的过程中，如果发现要运行的程序或要访问数据不在内存，则向系统发出缺页中断请求，系统在处理这个中断时，将在外存相应的页调入内存，该程序继续运行。7.4页式存储管理7.4.3请调策略三、请求分页要解决的问题采用这种技术要解决以下问题：1、如何发现执行的程序或访问的数据不在内存；2、程序或数据什么时候调入内存，调入策略；3、当一些页调入内存时，内存没有空闲内存时，将淘汰哪些页，淘汰策略。7.4页式存储管理7.4.3请调策略四、数据结构为了实现请求分页技术，页表应增加相应的内容，反映该页是否在内存，在外存的位置，在内存的时间的长短等。中断位：0表示该页在内存，1示该页不在内存引用位：0表示最近没有进程访问1示最近有进程访问修改位：0该页调入内存后没有修改1页调入内存后修改过在请求分页技术中，页表中的页号是不能省略的。7.4页式存储管理7.4.3请调策略四、数据结构7.4页式存储管理7.4.3请调策略五.调入策略1、预调系统根据作业（进程）运行的情况，预测哪些页将要运行，在其运行之前先行调入内存，这样在程序运行的过程中就不会出现缺页中断。这样方法从表面上看起来很好，但系统无法预计系统中作业的运行情况，难以实现。2、请调进程在执行的过程中，发现要执行的程序或处理的数据不在内存，向系统提出调入相应程序的请求，系统响应用户的请求。7.4页式存储管理7.4.4淘汰策略一、置换算法当要把一页面并送入到全满的内存中时，必须把已在内存中的某一页淘汰掉。用来选择淘汰哪一页的规则叫做置换算法。二、颠簸（抖动）由于页面不停地调入与调出而出现的一种现象。一、最佳算法假定程序p共有n页，而系统分配给它的内存只有m块（1≤m≤n），并且以作业在执行的过程中页面置换的频率的高低来衡量算法的优劣。访问的页在内存，称访问成功，否则为失败。a=s+fa:访问的总次数s：访问成功的次数f：访问失败的次数7.4页式存储管理7.4.5几种置换算法7.4页式存储管理7.4.5几种置换算法缺页中断率f,=f/a则有：F’＝f(r,m,p）最佳算法是指对于任何m和p，r:调度算法有f’＝f(r,m,p）最小。最佳算法：当要调入一新页而必须淘汰一旧页时，所淘汰的页是以后不再使用的，或者是以后相当长的时间内不会使用的。显然，采用这种算法可以保证最低的缺页率，但这种算法是不可能实现的。7.4页式存储管理7.4.5几种置换算法二、先进先出算法先进入内存的页，先退出内存。实质上是淘汰在内存驻留时间最长的页。其理由是：最早调入内存的页，不再被使用的可能性比近期调入内存的大。这种算法简单，实现容易。但是这种算法的效率不高。另外该算法还存在一种称为Belady的异常现象：增加分配给进程的内在块数，而进程的缺页中断率反而会增高。例：进程的页面访问序列为1，2，3，4，1，2，5，1，2，3，4，5；分别计算分配给该进程3块内存和4块内存时的缺页中断率。7.4页式存储管理7.4.5几种置换算法三、最近最久未使用淘汰算法（LRU算法）这种算法的实质：当需要淘汰一页时，选择最长时间未使用的页。依据的理论是如果某页被访问，它可能马上还要被访问；相反，如果某页长时间未被访问，它可能最近也不可能被访问。算法的实现（软件）：设置一个活动页面栈，当访问某页时，将此页号压入栈顶，然后，考察栈内是否有与此页面相同的页号，若有则抽出。淘汰一页时，总是从栈底抽出一个页号，它就是最久未使用的。7.4页式存储管理7.4.5几种置换算法四、第二次机会置换算法(SecondChancePageReplacement，SCR)该算法是对FIFO算法的改进-----避免把经常使用的页面转换出去。当选择某一页置换时，就检查最老页面的引用位：如果是0，就立即淘汰该页；如果是1，就给它第二次机会，并将引用位清0，把它放入页面链表的末尾，把它的装入时间重置为当时时间（实际上是把该页看成是新装入的页），然后选择下一个FIFO页面。如果一个页面经常使用，它的引用位总保持为1，它就不会被淘汰。当所有的页面先前都被访问过时，该算法就降为纯粹的FIFO算法。（b）第二次机会法示例7.4页式存储管理7.4.5几种置换算法五、时钟置换法（Clock，简单时钟置换算法）该算法对第二次机会法进行了改进，避免在页面链表中移动页面所带来的效率问题。该算法也是LRU算法的近似算法。实现方法：所有的页面保存在一个类似钟表表盘的环状链中，由一个指针指向最老的页面。7.4页式存储管理7.4.5几种置换算法当发生缺页时，首先检查指针指向的页面，如果它的引用位是0就淘汰该页，且把新页面插入在这个位置，然后指针前移一个位置；如果引用位是1就清0，并把指针前移一个位置；重复这个过程，直至找到引用位为0的页面为止。由于该算法只用一个引用位来判定该页最近是否使用过，所以该算法又称为最近未使用置换算法（NotRecentlyUsed,NRU）时钟置换算法7.4页式存储管理7.4.6页式系统的存储保护页式系统的存储保护的方法类似于基址限长存储保护，当地址映射机构分离出页号和页内位移后。若0≤页号＜用户程序的总页数，则访问合法，否则访问越界。页式系统的存储保护还包括存取控制。在页表中增加存取控制位，表示该页的存取控制权限，如r表示可读，w表示可读可写，e表示可执行。当有一程序访问该页时，系统就按存取控制位设置的权限实施存取控制。习题：在页式存储管理系统中，逻辑地址长度为16位，页面大小2KB，一作业有7个页面，设0，1，2，3分别装入主存中的3，5，4，7物理块内。试问：1）语句MOVAX，[3200]，在执行过程中所执行的地址变换；2）若逻辑地址以十六进制形式给出，现有一逻辑地址为17FBH，试求其所对应的物理地址。3）若作业页面走向为0，1，2，3，2，4，3，1，2，5，2，3，1，6，2，1；分别采用先进先出算法和LRU算法来处理缺页中断，试计算缺页中断次数及缺页中断率。