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

《操作系统页式存储管理.ppt》由会员分享，可在线阅读，更多相关《操作系统页式存储管理.ppt（39页珍藏版）》请在装配图网上搜索。

1、6.4 页式存储管理 6.4.1 基本原理 6.4.2 管理 6.4.3 硬件支持 6.4.4 静态页式管理 6.4.5 请求页式管理 6.4.6 页式管理的优缺点 6.4.1 基本思想（工作原理） 用户程序划分 把用户程序按逻辑页划分成大小相等的 部分 ， 称为页 。 从 0开始编制页号 ， 页内 地址是相对于 0编址 逻辑地址 页号 页内地址 内存空间 按页的大小划分为大小相等的区域，称 为内存块（物理页面） 内存分配 以页为单位进行分配，并按作业的页数 多少来分配。逻辑上相邻的页，物理上 不一定相邻 . . . 0 1 2 3 4 5 6 0 1 2 3 4 5 6 作业的 地址空间 页

2、框 （物理块） 页号 页表 主存中页框 （物理块） . . . . . . . 6.4.2 管理 页表：系统为每个进程建立一个页表， 页表给出逻辑页号和具体内存块号相应 的关系。 页号 页面号 0 2 1 3 2 8 6.4.3 硬件支持 p 页表 地址越界 l 比较 P=l b + 页号 p 页内地址 d P d 物理地址 页表地址寄存器 页表长度寄存器 逻辑地址 地址映射机制 二次访问内存 第一次取地址 第二次存取数据 效率较低 p 页表 地址越界 l 比较 P=l p p . . . 快表 b + 页号 p 页内地址 d P d 物理地址 页表地址寄存器 页表长度寄存器 逻辑地址 地址映

3、射机制 高速 缓存 6.4.4 静态页式管理 将程序的逻辑地址空间和物理内存划分 为固定大小的页或页面 (page or page frame)，程序加载时，分配其所需的所有 页，这些页不必连续。 Fram e N umbe r 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 A .0 A .1 A .2 A .3 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 A .0 A .1 A .2 A .3 B.0 B.1 B.2 0 1 2 3 4 5 6 7 8 9 10 11 12

4、 13 14 A.0 A.1 A.2 A.3 B.0 B.1 B.2 C.0 C.1 C.2 C.3 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 A.0 A.1 A.2 A.3 C.0 C.1 C.2 C.3 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 A.0 A.1 A.2 A.3 C.0 C.1 C.2 C.3 D.0 D.1 D.2 D.3 D.4 1. 简单页式管理的数据结构 页表：每个进程有一个页表，描述该进程占用 的物理页面及逻辑排列顺序； 逻辑页号（本进程的地址空间） 物理页面号 （实际内存空间）； 存储页面表：整个系统有一个存

5、储页面表，描 述物理内存空间的分配使用状况。 数据结构：位示图，空闲页面链表； 请求表：整个系统有一个请求表，描述系统内 各个进程页表的位置和大小，用于地址转换， 也可以结合到各进程的 PCB里； 2. 分配算法 请求 n个页面 存储页面表中有 n个空闲页面吗 无法分配 返回 设置请求表，将页表 始址，页表长度置入 请求表中，置状态已分配 搜索存储页面表，分配 n个页面，并将页面号 填入页表中 3. 简单页式管理的地址变换 指令所给出地址分为两部分：逻辑页号， 页内偏移地址 查进程页表，得物理页 号 物理地址 为缩短查找时间，引入快表，按内容查找 (associative mapping)，即

6、逻辑页号 物理 页号 P rogr am P agin g Main Me mory Vir tual Ad dre ss Regi ster P age Tabl e P age F r ame O f f se t P# Fr am e # Page T ab l e Ptr Pa ge # O f f se t Fr am e # O f f se t + 页号 页面号 0 2 1 3 2 8 设每个页面长度为 1k，指令 LOAD 1,2500 的虚地址为 100，依据左图进 行地址变换。 首先，需要有一个页表地址寄存器和页表 长度寄存器。系统把所调度执行的进程页 表始址和长度从请求表

7、中取出置入寄存器 然后，找到页表。由虚地址 100可知，指令 在第 0页的第 100单元中，对应内存地址为 1024*2+100=2148 当 CPU执行到第 2148单元时，需要从虚地 址 2500中取数据，地址变换机构首先将 2500的页号和页内位移求出： 2； 452 由页表可知，对应内存 8号，内存地址为 1024*8+452=8644 以上由硬件地址变换机构自动完成。 优点： 没有外碎片，每个内碎片不超过页大小。 一个程序不必连续存放。 便于改变程序占用空间的大小。即随着程序运 行而动态生成的数据增多，地址空间可相应增 长。 缺点：程序全部装入内存，受到内存可用 页面数的限制。 6.

8、4.5 动态（请求）页式管理 在进程开始运行之前，不是装入全部页 面，而是装入部分页面，之后根据进程 运行的需要，动态装入其它页面；当内 存空间已满，而又需要装入新的页面时， 则根据某种算法淘汰某个页面，以便装 入新的页面。 请求页式的地址变换与静态页式的相同。 但是，由于只让部分页面驻留内存，如 何发现那些不在内存的虚页以及如何处 理是请求页式必须处理的问题。 第一个问题可以通过扩充页表的方法解 决；第二个问题当内存没有空闲页面时 即是页面置换算法的问题。 页表表项 页号、驻留位、内存块号、外存始址、访 问位、修改位 驻留位（中断位）：表示该页是在内存还 是在外存 访问位：根据访问位来决定淘

9、汰哪页（由 不同的算法决定） 修改位：查看此页是否在内存中被修改过 页号 中断位 内存块号 外存始址 访问位 修改位 缺页中断处理 在地址映射过程中，在页表中发现所要访问的 页不在内存，则产生缺页中断。操作系统接到 此中断信号后，就调出缺页中断处理程序，根 据页表中给出的外存地址，将该页调入内存， 使作业继续运行下去 如果内存中有空闲块，则分配一页，将新调入 页装入内存，并修改页表中相应表项 若此时内存中没有空闲块，则要淘汰某页，若 该页在内存期间被修改过，则要将其写回外存 查快表 有登记 无登记 查页表 登记入快表 发缺页中断 在主存 在辅存 形成绝对地址 继续执行指令 重新执行 被中断指令

10、 恢复现场 调整页表和 主存分配表 装入所需页面 主存有空闲块 保护现场 有 选择调出页面 未修改 已修改 把该页写回 辅存相应位置 硬件完成 逻辑地址 无 该页修改过？ 页面置换算法 随机置换算法 先进先出算法 (FIFO) 最近最久未使用算法 (LRU, Least Recently Used) 时钟页面替换算法 (Clock Policy) 最佳置换算法 (OPT, optimal) 1. 先进先出算法 (FIFO) 选择建立最早的页面被置换。可以通过链表来 表示各页的建立时间先后。性能较差。较早调入的 页往往是经常被访问的页，这些页在 FIFO算法下 被反复调入和调出。并且有 Bela

11、dy现象。 Belady现象：采用 FIFO算法时，如果对一个进程未 分配它所要求的全部页面，有时就会出现分配的页 面数增多，缺页率反而提高的异常现象。 Belady现象的描述：一个进程 P要访问 M个页， OS 分配 N个内存页面给进程 P；对一个访问序列 S，发 生缺页次数为 PE（ S,N）。当 N增大时， PE(S, N)时 而增大，时而减小。 Belady现象的原因： FIFO算法的置换特征与进程访 问内存的动态特征是矛盾的，即被置换的页面并不 是进程不会访问的。 Belady现象的例子 进程 P有 5页程序访问页的顺序为： 1, 2, 3, 4, 1, 2, 5, 1, 2, 3,

12、 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 如果在内存中分配 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 2.最近最久未使用算法 (LRU) 该算

13、法淘汰的页面是在最近一段时间里较久未 被访问的那一页。它是根据程序执行时所具有的局 部性来考虑的，即那些刚被使用过的页面，可能马 上还要被使用，而那些在较长时间里未被使用的页 面，一般说可能不会马上使用到。 给某作业分配了三块主存，该作业依次访问的页号为： 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

14、 3 0 0 4 1 1 3.时钟页面替换算法 (Clock Policy) 一个页面首次装入主存时，其”引用位”置 0。 在主存中的任何一个页面被访问时 , 其”引用位” 置 1。 淘汰页面时 ,存储管理从指针当前指向的页面开 始扫描循环队列，把所迁到的”引用位”是 1的页 面的”引用位”清成 0,并跳过这个页面 ; 把所迁到 的”引用位”是 0的页面淘汰掉 ,指针推进一步。 它是 LRU(最近最久未使用算法 )和 FIFO的折衷。 Page9 use=1 Page19 Use=1 Page1 Use=0 Page45 Use=1 Page191 Use=1 Page556 Use=0 Pa

15、ge13 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

16、,指针指向的是 page45(在页框 2中 )。 Clock页 面替换算法执行如下： page45的”引用位”是 1,故它不能被淘汰掉，仅把其”引用位”清 0,指 针推进。同样道理， page191(在页框 3中 )也不能被替换 , 把其”引用位”清 0,指针继续推进。在 下一页即 page556(在页框 4中 ),它的”引用位”是 0,于是 ,page556被 page727替换 ,并把 page727的” 引用位”置 1,指针前进到下一页 page13(在页框 5中 )。算法执行到此结束。 4. 最佳算法 (OPT, optimal) 选择“未来不再使用的”或“在离当前最远位置上 出现的”

17、页面被置换。这是一种理想情况，是实际 执行中无法预知的，因而不能实现。可用作性能评 价的依据。 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 (1) 分配给进程的物理页面数 (2) 页面本身的大小 (3) 程序的编制方法 (4) 页面淘汰算法 影响缺页次数的因素 例子 3：内存分配一页 ,初始时第一页在内存； 页面大小为 128个整数；矩阵 A128X128按行存 放 程序编制方法 1： For j:=1 to 128 For i:=1 to 128 Ai,j:=0; 程序编制方法 2： For i:=1 t

18、o 128 For j:=1 to 128 Ai,j:=0; 6.4.6 页式管理的优缺点 相对于分区管理而言，静态页式有效的解决了 外部碎片的问题（当然有少量的内部碎片）； 但是，静态页式要求全部装入，不支持虚拟存 储，因而有了请求页式，允许部分装入； 显然地，请求页式更能有效利用有限的内存页 面，不过，这种方式需要有效解决缺页率的问 题，尤其是页面置换的问题； 不论是静态还是请求方式，更多地是从物理页 面的角度考虑和解决问题，有的时候，需要从 逻辑角度考虑问题，比如共享，这就引入了段 式管理方法。 习题：某程序在内存中分配三个页面， 初始为空，页面走向为 4， 3， 2， 1， 4， 3，

19、 5， 4， 3， 2， 1， 5，计算采用 FIFO , LRU , OPT进行页面置换时相应的缺页次 数。 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次 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次 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次 一程序在运行过程中所访问的页面流 为 3， 5， 4， 2， 5， 3， 1， 3， 2， 5， 1， 3， 1， 5， 2。若采用 OPT算法，则为 该程序分配多少个实页最为合理（要 求给出分配过程）？为什么？