操作系统页式存储管理

6.4页式存储管理

6.4.1基本原理6.4.2管理6.4.3硬件支持6.4.4静态页式管理6.4.5请求页式管理6.4.6页式管理的优缺点2021/6/2716.4.1基本思想（工作原理）用户程序划分

把用户程序按逻辑页划分成大小相等的部分，称为页。从0开始编制页号，页内地址是相对于0编址逻辑地址页号页内地址2021/6/272内存空间按页的大小划分为大小相等的区域，称为内存块（物理页面）内存分配以页为单位进行分配，并按作业的页数多少来分配。逻辑上相邻的页，物理上不一定相邻2021/6/2732021/6/2746.4.2管理页表：系统为每个进程建立一个页表，页表给出逻辑页号和具体内存块号相应的关系。页号页面号0213282021/6/2756.4.3硬件支持p’页表地址越界

l比较P>=l

b+页号p页内地址dP’d物理地址页表地址寄存器页表长度寄存器逻辑地址地址映射机制二次访问内存第一次取地址第二次存取数据效率较低2021/6/276p’页表地址越界

l比较P>=lpp’...快表

b+页号p页内地址dP’d物理地址页表地址寄存器页表长度寄存器逻辑地址地址映射机制高速缓存2021/6/2776.4.4静态页式管理将程序的逻辑地址空间和物理内存划分为固定大小的页或页面(pageorpageframe)，程序加载时，分配其所需的所有页，这些页不必连续。2021/6/2782021/6/2792021/6/27101.简单页式管理的数据结构页表：每个进程有一个页表，描述该进程占用的物理页面及逻辑排列顺序；逻辑页号（本进程的地址空间）－>物理页面号（实际内存空间）；存储页面表：整个系统有一个存储页面表，描述物理内存空间的分配使用状况。数据结构：位示图，空闲页面链表；请求表：整个系统有一个请求表，描述系统内各个进程页表的位置和大小，用于地址转换，也可以结合到各进程的PCB里；2021/6/27112.分配算法请求n个页面存储页面表中有n个空闲页面吗无法分配返回设置请求表，将页表始址，页表长度置入请求表中，置状态已分配搜索存储页面表，分配n个页面，并将页面号填入页表中2021/6/27123.简单页式管理的地址变换指令所给出地址分为两部分：逻辑页号，页内偏移地址－>查进程页表，得物理页号－>物理地址为缩短查找时间，引入快表，按内容查找(associativemapping)，即逻辑页号－>物理页号2021/6/27132021/6/2714页号页面号021328设每个页面长度为1k，指令LOAD1,2500的虚地址为100，依据左图进行地址变换。首先，需要有一个页表地址寄存器和页表长度寄存器。系统把所调度执行的进程页表始址和长度从请求表中取出置入寄存器然后，找到页表。由虚地址100可知，指令在第0页的第100单元中，对应内存地址为1024*2+100=2148当CPU执行到第2148单元时，需要从虚地址2500中取数据，地址变换机构首先将2500的页号和页内位移求出：2；452由页表可知，对应内存8号，内存地址为1024*8+452=8644以上由硬件地址变换机构自动完成。2021/6/2715优点：没有外碎片，每个内碎片不超过页大小。一个程序不必连续存放。便于改变程序占用空间的大小。即随着程序运行而动态生成的数据增多，地址空间可相应增长。缺点：程序全部装入内存，受到内存可用页面数的限制。2021/6/27166.4.5动态（请求）页式管理在进程开始运行之前，不是装入全部页面，而是装入部分页面，之后根据进程运行的需要，动态装入其它页面；当内存空间已满，而又需要装入新的页面时，则根据某种算法淘汰某个页面，以便装入新的页面。2021/6/2717请求页式的地址变换与静态页式的相同。但是，由于只让部分页面驻留内存，如何发现那些不在内存的虚页以及如何处理是请求页式必须处理的问题。第一个问题可以通过扩充页表的方法解决；第二个问题当内存没有空闲页面时即是页面置换算法的问题。2021/6/2718※

页表表项页号、驻留位、内存块号、外存始址、访问位、修改位 驻留位（中断位）：表示该页是在内存还是在外存访问位：根据访问位来决定淘汰哪页（由不同的算法决定）修改位：查看此页是否在内存中被修改过页号中断位内存块号外存始址访问位修改位2021/6/2719※缺页中断处理在地址映射过程中，在页表中发现所要访问的页不在内存，则产生缺页中断。操作系统接到此中断信号后，就调出缺页中断处理程序，根据页表中给出的外存地址，将该页调入内存，使作业继续运行下去如果内存中有空闲块，则分配一页，将新调入页装入内存，并修改页表中相应表项若此时内存中没有空闲块，则要淘汰某页，若该页在内存期间被修改过，则要将其写回外存2021/6/2720查快表有登记无登记查页表登记入快表发缺页中断在主存在辅存形成绝对地址继续执行指令重新执行被中断指令恢复现场调整页表和主存分配表装入所需页面主存有空闲块保护现场有选择调出页面未修改已修改把该页写回辅存相应位置硬件完成逻辑地址无该页修改过？2021/6/2721※

页面置换算法随机置换算法

先进先出算法(FIFO)最近最久未使用算法(LRU,LeastRecentlyUsed)时钟页面替换算法(ClockPolicy)最佳置换算法(OPT,optimal)2021/6/27221.先进先出算法(FIFO)

选择建立最早的页面被置换。可以通过链表来表示各页的建立时间先后。性能较差。较早调入的页往往是经常被访问的页，这些页在FIFO算法下被反复调入和调出。并且有Belady现象。2021/6/2723Belady现象：采用FIFO算法时，如果对一个进程未分配它所要求的全部页面，有时就会出现分配的页面数增多，缺页率反而提高的异常现象。Belady现象的描述：一个进程P要访问M个页，OS分配N个内存页面给进程P；对一个访问序列S，发生缺页次数为PE（S,N）。当N增大时，PE(S,N)时而增大，时而减小。Belady现象的原因：FIFO算法的置换特征与进程访问内存的动态特征是矛盾的，即被置换的页面并不是进程不会访问的。2021/6/2724Belady现象的例子进程P有5页程序访问页的顺序为：1,2,3,4,1,2,5,1,2,3,4,5；如果在内存中分配3个页面，则缺页情况如下：12次访问中有缺页9次；123412512345111444555555222111113333332222244×××××××√√××√2021/6/2725如果在内存中分配4个页面，则缺页情况如下：12次访问中有缺页10次；123412512345111111555544222222111153333332222444444333××××√√××××××2021/6/27262.最近最久未使用算法(LRU)

该算法淘汰的页面是在最近一段时间里较久未被访问的那一页。它是根据程序执行时所具有的局部性来考虑的，即那些刚被使用过的页面，可能马上还要被使用，而那些在较长时间里未被使用的页面，一般说可能不会马上使用到。

2021/6/2727给某作业分配了三块主存，该作业依次访问的页号为：4，3，0，4，1，1，2，3，2。于是当访问这些页时，页面淘汰序列的变化情况如下：430411232444444433333111110000222×××√×√××√430411232430411232430441234300411×××√×√××√2021/6/27283.时钟页面替换算法(ClockPolicy)＊一个页面首次装入主存时，其”引用位”置0。＊在主存中的任何一个页面被访问时,其”引用位”置1。＊淘汰页面时,存储管理从指针当前指向的页面开始扫描循环队列，把所迁到的”引用位”是1的页面的”引用位”清成0,并跳过这个页面;把所迁到的”引用位”是0的页面淘汰掉,指针推进一步。＊它是LRU(最近最久未使用算法)和FIFO的折衷。2021/6/2729Page9use=1Page19Use=1Page1Use=0Page45Use=1Page191Use=1Page556Use=0Page13Use=0Page67Use=1Page33Use=1Page222Use=0

下一个帧指针n012345678（a）一个页替换前的缓冲区状态Page9use=1Page19Use=1Page1Use=0Page45Use=0Page191Use=0Page727Use=1Page13Use=0Page67Use=1Page33Use=1Page222Use=0

n012345678（b）下一页替换后的缓冲区状态1第1页框当发生缺页中断时，将要进入主存的页面是page727,指针指向的是page45(在页框2中)。Clock页面替换算法执行如下：page45的”引用位”是1,故它不能被淘汰掉，仅把其”引用位”清0,指针推进。同样道理，page191(在页框3中)也不能被替换,把其”引用位”清0,指针继续推进。在下一页即page556(在页框4中),它的”引用位”是0,于是,page556被page727替换,并把page727的”引用位”置1,指针前进到下一页page13(在页框5中)。算法执行到此结束。2021/6/27304.最佳算法(OPT,optimal)选择“未来不再使用的”或“在离当前最远位置上出现的”页面被置换。这是一种理想情况，是实际执行中无法预知的，因而不能实现。可用作性能评价的依据。430411232444411222333333330000000×××√×√×√√2021/6/2731(1)分配给进程的物理页面数(2)页面本身的大小(3)程序的编制方法(4)页面淘汰算法※影响缺页次数的因素2021/6/2732例子3：内存分配一页,初始时第一页在内存；页面大小为128个整数；矩阵A128X128按行存放程序编制方法1：

Forj:=1to128Fori:=1to128A[i,j]:=0;程序编制方法2：

Fori:=1to128Forj:=1to128A[i,j]:=0;2021/6/27336.4.6页式管理的优缺点相对于分区管理而言，静态页式有效的解决了外部碎片的问题（当然有少量的内部碎片）；但是，静态页式要求全部装入，不支持虚拟存储，因而有了请求页式，允许部分装入；显然地，请求页式更能有效利用有限的内存页面，不过，这种方式需要有效解决缺页率的问题，尤其是页面置换的问题；不论是静态还是请求方式，更多地是从物理页面的角度考虑和解决问题，有的时候，需要从逻辑角度考虑问题，比如共享，这就引入了段式管理方法。2021/6/2734

习题：某程序在内存中分配三个页面，初始为空，页面走向为4，3，2，1，4，3，5，4，3，2，