操作系统原理第四章存储器管理

1、2007-8-15 15:26,操作系统|存储器管理,1,第四章存储器管理,存储管理的机制 分区管理 分页管理 分段管理 虚拟存储器的概念 请求页式管理 页面置换算法 请求段式管理,2007-8-15 15:26,操作系统|存储器管理,2,4.1 存储管理概述,存储管理的目的 主存的分配和回收 记住内存每个位置的状态。 在系统程序或用户作业提出申请时，实施分配，并修改分配记录。 接受系统或用户释放的存储区，或主动收回不再用的存储区，并相应地修改分配记录表。,2007-8-15 15:26,操作系统|存储器管理,3,提高内存利用率 “扩充”内存容量 信息保护,4.1 存储管理概述,2007-8-

2、15 15:26,操作系统|存储器管理,4,内外存数据传输的控制 用户程序控制 操作系统控制 交换（Swapping） ：由OS把那在内存中处于等待状态的进程换出内存，就绪进程换入内存。 请求调入（On demand）和预调入（On prefetch）,4.1 存储管理概述,2007-8-15 15:26,操作系统|存储器管理,5,内存管理的内容 分配结构： 放置策略： 交换策略： 调入策略： 回收策略：,4.1 存储管理概述,2007-8-15 15:26,操作系统|存储器管理,6,内存信息的共享与保护 上下界保护法 保护键法 为每个被保护存储块分配一个单独的保护键，在程序状态字中设置相应的

3、开关字段，不同的进程值不一样，匹配时，方可进行访问。 界限寄存器与CPU 的用户态和核心态工作方式相结合 用户态进程只能访问在界限寄存器所规定范围内的内存部分，而核心态进程则可访问整个内存地址空间。,4.1 存储管理概述,2007-8-15 15:26,操作系统|存储器管理,7,4.2 程序的装入和链接,2007-8-15 15:26,操作系统|存储器管理,8,程序的装入 绝对装入方式（Absolute Loading Mode） 编译程序产生绝对地址目标代码，由装入程序根据装入模块中的地址，将程序和数据装入内存。,2007-8-15 15:26,操作系统|存储器管理,9,2可重定位装入方式（

4、Relocatable Loading Mode） 重定位：在装入时对目标程序中的指令和数据地址的修改过程。,4.2 程序的装入和链接,Load 1,12500,2007-8-15 15:26,操作系统|存储器管理,10,静态地址重定位：是指作业在装入时随即进行的地址变换方式，这一工作由装配程序完成。 优点：无需增加硬件地址变换机构；实现简单。 缺点：程序经地址定位后就不能再移动了；程序在存储空间中只能连续分配；多个用户难以共享存于内存中的同一程序。,4.2 程序的装入和链接,2007-8-15 15:26,操作系统|存储器管理,11,3动态运行时装入方式（Dynamic Run-Time L

5、oading） 程序执行过程中，当访问指令或数据时，才进行的地址变换方法，称为动态重定位。 靠硬件地址变换机构实现的。 基地址寄存器（重定位寄存器） BR 程序虚地址寄存器VR 地址 MA=（BR）+（VR） 优点：可对内存进行非连续分配；提供了实现虚存的基础；有利于程序段的共享。,4.2 程序的装入和链接,2007-8-15 15:26,操作系统|存储器管理,12,4.2 程序的装入和链接,2007-8-15 15:26,操作系统|存储器管理,13,程序的链接 静态链接:将各模块及库函数链接成一个装配模块，以后不再拆开。 装入时动态链接:各目标模块装入内存时，边装入边链接。 运行时动态链接:

6、对模块的链接，是在程序执行中，才进行链接。,4.2 程序的装入和链接,2007-8-15 15:26,操作系统|存储器管理,14,4.3 连续分配存储管理方式,单一连续分配 存储区的分配 内存分配和回收策略 优点 管理简单，不要求专用的硬件支持；为防止破坏OS ，设置界限寄存器；易于实现。,2007-8-15 15:26,操作系统|存储器管理,15,缺点 存储器利用率低 缺乏灵活性，程序所需应小于内存，否则提供覆盖。 某些系统中安全性差。 信息不共享 CPU 利用率低，周转时间长。,4.3 连续分配存储管理方式,2007-8-15 15:26,操作系统|存储器管理,16,固定分区 工作原理 在

7、系统生成时，将内存划分为若干各分区，每个分区的大小可以不等，一经划分，不能更改。 系统对内存的管理和控制通过分区说明表说明各区的区号，大小，起始地址及状态。 特点 可使多个作业共享内存，但管理简单，内存利用率太低，对工作负荷明确的作业比较合适。,4.3 连续分配存储管理方式,2007-8-15 15:26,操作系统|存储器管理,17,4.3 连续分配存储管理方式,2007-8-15 15:26,操作系统|存储器管理,18,4.3 连续分配存储管理方式,2007-8-15 15:26,操作系统|存储器管理,19,动态分区 工作原理 存储空间的划分是在装入作业时进行的，且使分区大小正好适应作业的需

8、要。 数据结构 空闲分区表：序号，大小，起址，状态 空闲分区链：在每个分区中附上一个表格信息，状态（0，1），大小，指针（空白分区才有）,4.3 连续分配存储管理方式,2007-8-15 15:26,操作系统|存储器管理,20,4.3 连续分配存储管理方式,2007-8-15 15:26,操作系统|存储器管理,21,4.3 连续分配存储管理方式,2007-8-15 15:26,操作系统|存储器管理,22,分区管理算法 首次适应算法（First Fit） 每个空白区按地址递增的顺序链接在一起。 特点：尽量使用低端地址，以保持高址部分的大空闲区；低址部分有很多小空白区，增加查找时间开销。 循环首次

9、适应算法 从上次查找的位置的下一个空闲空闲分区开始查找。 空闲分区分布均匀,查找时间缩短,但系统会缺少大的空闲分区。,4.3 连续分配存储管理方式,2007-8-15 15:26,操作系统|存储器管理,23,最佳适应算法 空白区按大小递增的顺序链在一起。变量FREE 中的始端指针总指向最小的空白区。 特点：平均而言，查找时间较少；选择最适合的空白区。形成很多小碎片；找一个大空白区时较慢；回收时费时；先拼接，再把该区插入适当位置。 最差适应算法 空白区按容量递减次序排列。 特点：分配时间快；剩下的空白分区仍可用；各空白区比较均匀地减少，工作一段时间后，就不能满足大空白区的要求；回收麻烦。,4.3

10、 连续分配存储管理方式,2007-8-15 15:26,操作系统|存储器管理,24,算法分析 特点：有助于多道程序设计；只需要界限地址寄存器，用于存储保护；算法简单，易于实现。但会产生碎片，降低存储器的利用效率；分区的大小，受内存容量限制。 几种算法比较：搜索速度，释放速度，空闲区的利用。,4.3 连续分配存储管理方式,2007-8-15 15:26,操作系统|存储器管理,25,分区的分配 在未分配表中找出一个足够大的空白分区； 如比进程要求的大，则分为两部分；,4.3 连续分配存储管理方式,2007-8-15 15:26,操作系统|存储器管理,26,分区的回收 检查回收的分区是否与空白区邻接

11、，如有则加以合并，上邻接，下邻接，上下邻接。,2007-8-15 15:26,操作系统|存储器管理,27,伙伴系统,4.3 连续分配存储管理方式,2007-8-15 15:26,操作系统|存储器管理,28,4.3 连续分配存储管理方式,2007-8-15 15:26,操作系统|存储器管理,29,可重定位分区分配,4.3 连续分配存储管理方式,2007-8-15 15:26,操作系统|存储器管理,30,原理：内存紧凑 地址映射 地址空间：在编译后，一个目标程序所限定的地址，即地址空间仅仅是指程序用来访问信息所用的一系列地址单元的集合，这些单元编号称为逻辑地址（相对地址）。 存储空间：指主存中一系

12、列存储信息的物理单元的集合，这些单元的编号称为物理地址或绝对地址。 实现 动态重定位技术：访问指令或数据时，通过重定位寄存器来自动修改访问存储器的地址。,2007-8-15 15:26,操作系统|存储器管理,31,2007-8-15 15:26,操作系统|存储器管理,32,动态重定位分区分配算法：,2007-8-15 15:26,操作系统|存储器管理,33,内存紧凑两种时机 在某个分区被回收时，如不与空白区邻接，则立即进行内存紧凑。 在为作业分配而找不到足够大的空白区时再进行内存紧凑。,4.3 连续分配存储管理方式,2007-8-15 15:26,操作系统|存储器管理,34,对换技术 对换（S

13、wapping） 把内存中的暂不运行的进程或暂不使用的数据，换出到外存，把已具备运行条件的进程、或进程所需要的数据和程序，换入内存，并将控制转给它。 整体对换（进程对换）：用于分时系统，解决内存紧张问题。 部份对换（页面对换、分段对换）：以请求分页和请求分段存储管理为基础，用于支持虚拟存储系统。,4.3 连续分配存储管理方式,2007-8-15 15:26,操作系统|存储器管理,35,交换空间的管理 文件区：离散分配，提高存储空间的利用率； 对换区：连续分配，提高交换速度。 对换空间的分配与回收：注意空闲区的拼接 交换区分配算法：首次适应算法、循环适应算法和最佳适应算法。,2007-8-15

14、15:26,操作系统|存储器管理,36,换入和换出 消息m 中有：分区号i，基址basei，长度sizei，方向和外存交换区中分区始址。 SWAPIN Begin local m m.base = basei;m.ceiling = basei + sizei; m.direction = “in” ; m.source = backupstorebasei ; send (m,i),device queue ) ; end,4.3 连续分配存储管理方式,2007-8-15 15:26,操作系统|存储器管理,37,SWAPOUT （i） Begin local m m.base = basei

15、; m.ceiling = basei + sizei; m.direction = “out” ; m.destination = base of free area on swap area ; backupstorebasei = m.destination ;send (m,i),device queue ) ; end,4.3 连续分配存储管理方式,2007-8-15 15:26,操作系统|存储器管理,38,4. 4 基本分页存储管理,基本原理 实现方法 各进程的地址空间分成大小相等的页，把内存的存储空间也分成与页大小相同的片，称为物理块。在分配存储空间时，以块为单位来分配。 页面大

16、小：2 i (1K，2K，4K 等),2007-8-15 15:26,操作系统|存储器管理,39,2007-8-15 15:26,操作系统|存储器管理,40,分页管理存储地址结构,页号P,位移量W,0,12,11,31,若逻辑空间地址为A，页面大小为L，则：,页号P：,页内地址d：,2007-8-15 15:26,操作系统|存储器管理,41,4. 4基本分页存储管理,2007-8-15 15:26,操作系统|存储器管理,42,4. 4基本分页存储管理,2007-8-15 15:26,操作系统|存储器管理,43,4. 4基本分页存储管理,2007-8-15 15:26,操作系统|存储器管理,44

17、,2007-8-15 15:26,操作系统|存储器管理,45,地址变换 页表 采用动态重定位技术，为作业的每页设置一个重定位寄存器，这些寄存器组成一组，称为页表。其中一个表目为该页在主存中的块号。 在主存中专门分配一些存储单元来存放页表。页表始址和长度存放在控制寄存器中。 页表的大小 页表始址的选择 为了快速地根据页表始址和页号找到所需相应表目，页表的始址应为2 的幂。,4. 4基本分页存储管理,2007-8-15 15:26,操作系统|存储器管理,46,地址变换 页号P页内地址W 31 12 11 0 找到 地址变换 （P，W）（B，W ） （实际地址） 在开始执行（或恢复执行）一个作业时，

18、由系统把页表始址和页表长度放入控制寄存器中。,4. 4基本分页存储管理,2007-8-15 15:26,操作系统|存储器管理,47,地址映射机制,页号 块号 存取控制,页描述符,+,如果页号页表 长度，则中断， 否则继续.,如果访问非法， 则中断，否则 继续。,页 号 位移量,虚拟地址 LA,块 号 位移量,物理地址,页表始址 长度,页表寄存器PTR,页 表,块号 存取控制,页描述子,页 号 0 1 . . .,块 号,位移量,2007-8-15 15:26,操作系统|存储器管理,48,根据页表的得到逻辑地址100的物理地址: 该指令地址=2*1024+100 = 2148 执行： 2500

19、= 2048+452 P=2 W=452 B= 8 2500单元的物理地址=1024*8+452 = 8644,4.4请求分页存储管理,例：一个三页长的进程，每页长1K。 页号页框号（块号） 0 2 1 3 2 8 指令： 100 LOAD 1，2500 的地址变换过程为：,2007-8-15 15:26,操作系统|存储器管理,49,快表-采用联想存储器加快查表速度 在地址变换机构中，加入一个高速，小容量、具有并行查询能力的联想存储器，构成快表,存放正运行的进程的当前页号和块号。 在快表中找到，直接进行地址转换；未找到，则在主存页表继续查找，并把查到的页号和块号放入联想存储器的空闲单元中，如没

20、有，淘汰最先装入的页号。,4. 4基本分页存储管理,2007-8-15 15:26,操作系统|存储器管理,50,在缓存中查找页 描述子，找到了 则提取。,快表的命中率可高达80%90%。,利用页描述子和位移量计算物理地址,2,在缓存中未找到，从页表中读取，并存入缓存。,利用页描述子和位移量计算物理地址,页号 位移量,虚拟地址,2 7 5 3 8 2 。 。 。,超高速缓存,页表,0 1 2 3 4 . . .,首先访问高速缓存，确定需要的页描述子是否在其中，如果没有发现，再访问存储器中的页表。同时将从页表中读出的页描述子更新高速缓存中旧的页描述子。,具有超高速缓冲存储器的地址变换过程,4. 4

21、基本分页存储管理,2007-8-15 15:26,操作系统|存储器管理,51,分页存储管理算法 管理表目 作业表（ JT） 整个系统一张，每个进程对应一个表目 内容：页表长度，页表始址，状态 存储分块表（MBT） 整个系统一张 表示方式：链表，位示图 页表（PT）每个进程一张 分页存储分配算法,4. 4基本分页存储管理,2007-8-15 15:26,操作系统|存储器管理,52,多级页表 两级页表 引入 两级页表的结构 外层页号P1 内层页号P2 页内地址D 22 21 12 11 0 地址变换 多级页表结构,4. 4基本分页存储管理,2007-8-15 15:26,操作系统|存储器管理,53

22、,4. 4基本分页存储管理,2007-8-15 15:26,操作系统|存储器管理,54,假设一分页存储系统的页面大小为4K，页表结构如下：外层页号10位,外层页内地址10位,页内地址12位。 在逻辑地址空间中，有逻辑单元的地址为0 x7FFFFFFB，请给出该地址的外层页号、内层页内地址，页内地址（十进制表示）：,页内地址：=（0 x7FFFFFFB MOD 0 x1000)=FFB=4091 内层页内地址：=(0 x7FFFF MOD 0 x400)=3FF=1023 外层页号:= INT(0 x7FFFF / 0 x400)=1FF=511,2007-8-15 15:26,操作系统|存储器

23、管理,55,分页存储管理方案的评价 优点 有效解决存储器的零头问题，能在更高的程度上进行多道程序设计，从而相应提高了存储器和CPU 的利用率。 缺点 采用动态地址变换为增加计算机成本和降低CPU 的速度。 表格占内存空间，管理表格要付出时间。 存在页内碎片。 作业动态的地址空间受内存容量限制。,2007-8-15 15:26,操作系统|存储器管理,56,46 分段存储管理,分段存储管理：方便编程、分段共享、分段保护、动态增长和动态链接。 基本思想 把程序按内容或过程（函数）关系分成段，每段有自己的名字。段式管理程序以段为单位分配内存，然后通过地址映射机构把段式虚地址转换成实际的内存物理地址。,

24、2007-8-15 15:26,操作系统|存储器管理,57,实现原理 段式虚存空间 进程的虚地址空间为二维的，段长不固定，每个段定义一组逻辑上完整的程序或数据。 段号S 段内地址W 31 16 15 0 例： CALL X | LOAD 1，A | STORE 1，B | ,2007-8-15 15:26,操作系统|存储器管理,58,2007-8-15 15:26,操作系统|存储器管理,59,内存的分配和回收 内存的分配 内存中有足够的空闲区满足该段的要求 分配算法：最先适应算法；最佳适应；最差适应算法。 不满足 所有空闲区之和是否满足，如满足则合并。 内存的回收,2007-8-15 15:2

25、6,操作系统|存储器管理,60,段式管理的地址变换 段表（Segment Mapping Table） 段号始址长度存取方式 动态地址变换 当进程执行时，管理程序把其段表始址和段表长度放入段表控制寄存器中，以段号为索引，查段表。 对内存二次以上访问，可采用高速联想寄存器，加快查找速度。,2007-8-15 15:26,操作系统|存储器管理,61,分段系统的地址变换过程,2007-8-15 15:26,操作系统|存储器管理,62,分段与分页的区别: 页是信息的物理单位,分页是为了提高内存的利用率;段是信息的逻辑单位,分段是为了更好满足用户的需要。 页的大小固定，逻辑地址的划分由机器硬件实现；段的

26、大小取决于用户，由编译程序进行划分。 分页的作业地址空间是一维的；分段是二维的，标识一个地址时，要同时给出段名（段号）和段内地址。,2007-8-15 15:26,操作系统|存储器管理,63,信息共享：分页系统中的共享:,2007-8-15 15:26,操作系统|存储器管理,64,分段系统中的共享:,2007-8-15 15:26,操作系统|存储器管理,65,性能评价 优点 便于程序模块化处理和处理变化的数据结构。 便于共享分段 便于动态链接。 缺点 地址变换费时，管理表格，硬件支持，使OS 复杂。 为满足段的动态增长和减少碎片，要用拼接技术。 段长不定，管理困难；段长受内存可用区的限制。,2

27、007-8-15 15:26,操作系统|存储器管理,66,基本思想 将用户程序分成若干段，再用分页方法对每一段进行分配和管理 实现原理 地址构成 段号S 段内页号P 页内地址W 有效地址长度决定作业地址空间的范围 程序的分段，由程序员或编译程序按信息的逻辑结构划分，分页由OS 自动完成。,47段页式存储管理,2007-8-15 15:26,操作系统|存储器管理,67,2007-8-15 15:26,操作系统|存储器管理,68,2007-8-15 15:26,操作系统|存储器管理,69,段表和页表 段表：每个进程一张。管理内存分配与释放，存储保护和地址变换等。 页表：每个段一张。管理页面保护，页

28、表始址，页表长度。 段表与页表的关系 动态地址变换过程 三次访问内存：1、利用段获得页表始址，2、利用页表获得物理块地址，3、根据物理地址真正获得指令或数据。 为提高地址转换速度，设置快速联想寄存器，存放当前最常用的段号，页号和对应的内存页面与其它控制用栏目。,2007-8-15 15:26,操作系统|存储器管理,70,评价 优点 保留了请求页式和分段存储管理的全部优点，有效利用内存，为组织多道程序运行提供了方便。 缺点 增加硬件成本，系统的复杂性和管理上的开销。仍有碎片，各种表格要占用内存。,2007-8-15 15:26,操作系统|存储器管理,71,4. 6 虚拟存储器的基本概念,虚拟存储

29、器的引入 程序的分段执行 局部性原理 在执行中的程序，某一段时间内，CPU 总是集中地访问程序中的某一部分。 时间局限性:指令在一段时间内的多次执行。产生的原因是程序中存在大量的循环操作。 空间局限性:程序在一定时间所访问的地址可能集中在某一段指令范围内。,2007-8-15 15:26,操作系统|存储器管理,72,虚拟存储器的定义 在程序运行之前，仅将那些当前要运行的页（或段）先装入内存，其余暂留外存；在运行过程中，利用请求调入和交换技术，将内存中暂时不用的页调至外存上,将要访问的页调入内存,使大的程序可在较小的内存中运行. 虚拟存储器:具有请求调入和置换功能，能从逻辑上对内存容量进行扩充的

30、一种存储系统，其逻辑容量为内存和外存（对换区）容量之和。,2007-8-15 15:26,操作系统|存储器管理,73,虚存容量 在多道程序环境下，系统可分为每个用户建一个虚存。 其容量可为内存与外存的容量之和，或由计算机地址结构和寻址方式确定。 基础条件 有相当容量的外存。 要有一定容量的内存。 地址变换机构。,4.6虚拟存储器的基本概念,2007-8-15 15:26,操作系统|存储器管理,74,虚拟存储器的实现方式 请求分页系统 在分页系统的基础上，增加了请求调页和页面置换功能所形成的页式虚拟存储系统。 请求分页的页表机制 缺页中断机构 地址变换机构 请求分段系统 请求分段的段表机制 缺段

31、中断机构 地址变换机构,4.6虚拟存储器的基本概念,2007-8-15 15:26,操作系统|存储器管理,75,虚拟存储器的特征 离散性 多次性 对换性 虚拟性,4.6虚拟存储器的基本概念,2007-8-15 15:26,操作系统|存储器管理,76,4.7 请求分页存储管理,请求页式管理和预调入页式管理 请求页式管理 当需要执行的指令或访问的数据不在内存时，产生缺页中断，系统将外存中相应的页面调入内存。 预调入页式管理 系统对那些在外存中的页进行调入顺序计算，估计出这些页中的指令和数据的执行和被访问的顺序，并按此顺序将它们调入和调出内存。,2007-8-15 15:26,操作系统|存储器管理,

32、77,实现原理 要访问的虚页在不在内存 扩充页表功能 由动态地址变换机构产生缺页中断。 页面的调入调出 调入：有无空白页，是否淘汰一页，修改页表。 调出（淘汰） 处理过程:当传输进程某页时，阻塞，系统调度另一进程。,4.7请求分页存储管理,2007-8-15 15:26,操作系统|存储器管理,78,请求分页中的硬件支持 页表机制 缺页中断机构 处理过程：保护CPU现场、分析中断原因和转入中断处理程序。 特点,页面访问位 A ,0页面不在内存 1页面在内存,0页面未被访问 1页面已被访问,0页面未被修改 1页面已被修改,判断缺页中断,影响页面 置换策略,是否重写外存,页面存在位 P ,页面修改位

33、 M ,4.7请求分页存储管理,地址变换过程,缺页中断处理,有空页框吗,Y,1,4.7请求分页存储管理,装入新页,地址变换过程,2007-8-15 15:26,操作系统|存储器管理,80,例.某操作系统采用请求页式存储管理机制,用户进程有7个页面,系统为其分配了5个物理块,每页大小为1K,页表和快表如下表所示,分别对三个虚地址说明系统处理过程:0X5C,0X85C,0X185C。,2007-8-15 15:26,操作系统|存储器管理,81,解 答 0X5C的地址转换过程： 逻辑地址=(5C)H=(0101,1100)B 页号=(0 ) B 快表没有命中,查页表, P=1表示在内存, 得到物理块

34、号=(1000 ) B 物理地址= (10,0000,0101,1100)B=(205C)H 2. 0X85C的地址转换过程： 逻辑地址=(85C)H=(1000,0101,1100)B 页号=(10 ) B 查快表命中,得到物理块号=(100 ) B 物理地址= (1,0000,0101,1100)B=(105C)H 3. 0X185C的地址转换过程： 逻辑地址=(185C)H=(1,1000,0101,1100)B 页号=(110 ) B 查快表没有命中,查页表, P=0,表示不在内存,产生缺页中断。,2007-8-15 15:26,操作系统|存储器管理,82,页面分配 最小物理块数：能保

35、证一个进程正常运行所需的最小物理块数。 页面分配和置换策略 分配策略：固定和可变 置换策略：全局和局部 固定分配局部置换 可变分配全局置换 可变分配局部置换,4.7请求分页存储管理,2007-8-15 15:26,操作系统|存储器管理,83,分配算法 平均分配算法 按比例分配算法 考虑优先权的分配算法 将内存分为两部分：一部分按比例分配；另一部分根据优先级增加分配的物理块。,4.7请求分页存储管理,2007-8-15 15:26,操作系统|存储器管理,84,对换区的管理 对换空间充足：全部从对换区换入。 对换空间不够：分为修改和不修改两种方法。 UNIX方式：未运行过的，从文件区调入；运行过并

36、被换出的，从交换区调入。,4.7请求分页存储管理,2007-8-15 15:26,操作系统|存储器管理,85,性能评价 优点 有效地解决了碎片问题 虚存的实现 缺点 要求相应的硬件支持 增加系统开销 请求调页的算法选择不当，可能产生抖动现象。 没有彻底消除碎片问题。,4.7请求分页存储管理,2007-8-15 15:26,操作系统|存储器管理,86,思考与作业 请求分页存储管理需要怎样的硬件支持？ 讨论三种页面分配和置换策略的优缺点？ 作业 Page 142 : 2、6、12 、14,4.7请求分页存储管理,2007-8-15 15:26,操作系统|存储器管理,87,内容回顾 虚拟存储器管理概

37、念 请求页式存储管理的原理 缺页中断的过程及特点 请求页式存储管理的地址变换过程,2007-8-15 15:26,操作系统|存储器管理,88,4.8 页面置换算法,一个置换算法的效能是和作业运行过程中访问地址空间的变化规律（即程序的动态特征）紧密相关的，而这个变化规律是难以预测的。 最佳置换算法OPT（Optimal Replacement Algorithm） 被淘汰的页面是永远不使用的页面，或是在最长时间内不再被访问的页面。,2007-8-15 15:26,操作系统|存储器管理,89,例：一个有5个页面的进程，在内存为它分配3个物理块，其页面访问顺序如下：,OTP算法：页面置换次数=3,4

38、.8页面置换算法,特点:高效但不可行,2007-8-15 15:26,操作系统|存储器管理,90,先进先出算法（FIFO ） 原理：选择在内存驻留时间最长的一页将其淘汰。 实现方法 按页调入内存顺序建立一队列表Q （0）-Q（m1）和一替换指针，指针指向最早调入内存的一页。 把这个队列表建立在存储分块表中。,4.8 页面置换算法,2007-8-15 15:26,操作系统|存储器管理,91,例：一个有5个页面的进程，在内存为它分配3个物理块，其页面访问顺序如下：,FIFO算法：页面置换次数=6,4.8 页面置换算法,2007-8-15 15:26,操作系统|存储器管理,92,算法效率 这种算法只

39、有在按线性顺序访问地址空间时才理想，否则效率不高。 Belady 现象 在使用FIFO 算法时，未给进程或作业分配足够的页面数时，有时会出现分配的页面数增多，缺页次数反而增加。 原因在于它根本没考虑程序执行的动态特征。,4.8 页面置换算法,2007-8-15 15:26,操作系统|存储器管理,93,最近最久未用页面置换算法LRU（Least Recently Used） 原理：当需要置换一页时，选择在最近一段时间内最久未用的页予以淘汰 实现 通过周期性地对“引用位”进行检查，并利用它来记录一个页面自上次被访问以来所经历的时间T；淘汰时，选择T 为最大的页。,4.8 页面置换算法,2007-8

40、-15 15:26,操作系统|存储器管理,94,例：一个有5个页面的进程，在内存为它分配3个物理块，其页面访问顺序如下：,LRU算法：页面置换次数=4,4.8 页面置换算法,2007-8-15 15:26,操作系统|存储器管理,95,硬件支持 寄存器法 为每个页面配置一个移位寄存器，当访问到某物理块时，将相应寄存器的RN-1位置成1。每隔一段时间将寄存器右移一位。淘汰寄存器值最小的页面。,R 实页,R7 R6 R5 R4 R3 R2 R1 R0,1 1 0 1 0 0 0 0 0 2 0 0 0 0 1 0 0 0 3 1 0 0 0 0 0 0 0 4 0 1 0 0 0 0 0 0,1 0

41、 1 0 1 0 0 0 0 2 1 0 0 0 1 0 0 0 3 0 1 0 0 0 0 0 0 4 0 0 1 0 0 0 0 0,1 1 0 1 0 1 0 0 0 2 0 1 0 0 0 1 0 0 3 0 0 1 0 0 0 0 0 4 0 0 0 1 0 0 0 0,1 0 1 0 1 0 1 0 0 2 1 0 1 0 0 0 1 0 3 0 0 0 1 0 0 0 0 4 0 0 0 0 1 0 0 0,4.8 页面置换算法,例:页面访问顺序为2125,2007-8-15 15:26,操作系统|存储器管理,96,栈 利用一个特殊的栈来保存当前使用的各个页面的页面号，每当进程访

42、问某页面时，便将该页面的页面号从栈中移出，将它压入栈顶。则栈底为最近最久为使用页面的页面号。,4.8 页面置换算法,2007-8-15 15:26,操作系统|存储器管理,97,Clock置换算法 最近没使用算法NRU 原理：淘汰最近一段时间内未被访问的一页。 实现：设置访问位 A=0最近未被访问 A=1最近被访问 步骤： 特点：简单，实现容易；但时间周期T 选择不易确定。,4.8 页面置换算法,2007-8-15 15:26,操作系统|存储器管理,98,2007-8-15 15:26,操作系统|存储器管理,99,2007-8-15 15:26,操作系统|存储器管理,100,例：一个有5个页面的

43、进程，在内存为它分配3个物理块，其页面访问顺序如下：,Clock算法：页面置换次数=5,4.8 页面置换算法,2007-8-15 15:26,操作系统|存储器管理,101,NRU 改进算法 A ：访问位 M：修改位 1类（A=0，M=0） 最近既未被访问，又未被修改；,4.8 页面置换算法,2类（A=0，M=1） 最近既未被访问，但已被修改；,3类（A=1，M=0） 最近被访问，未被修改；,4类（A=1，M=1） 最近被访问，且被修改。,2007-8-15 15:26,操作系统|存储器管理,102,步骤： 扫描循环队列，找出一类页面，找到则淘汰该页。 未找到，开始第二轮扫描，找第二类页面，找到

44、淘汰该页，并将所有经过的页面的访问位置0。 都失败，重复（1），（2），直到找到淘汰页面。,4.8 页面置换算法,2007-8-15 15:26,操作系统|存储器管理,103,2007-8-15 15:26,操作系统|存储器管理,104,其它置换算法 最少使用（Least Frequently Used）置换算法 淘汰访问次数最少的一页。在页表中增加访问计数。 设置移位寄存器（每一页）：高位置1，定时右移。 页面缓冲算法（Page Buffering Algorithm） 置换算法采用FIFO，淘汰的页面挂在下列两个链表的尾部：空闲页面链表和已修改页面链表。当修改页面达到一定数量，再写回磁盘。

45、,4.8 页面置换算法,2007-8-15 15:26,操作系统|存储器管理,105,例. 一个进程的大小为5个页面，为它分配了四个物理块。当前每个块的情况如下表所示（都为十进制数，且从0开始计数。时间单位为“秒”）。当虚页4发生缺页时，使用下列的页面置换算法，哪一个物理块将被换出？并解释原因若每块的大小为1K,请计算100F单元的物理地址。 页号块号加载时刻访问时刻 访问位R 修改位M 206016101 1113016000 022616210 352016311 1）FIFO算法2) LRU算法 3) CLOCK算法,2007-8-15 15:26,操作系统|存储器管理,106,解 答

46、逻辑地址=(100F)H=(1000000001111)B 1. FIFO算法：第5号物理块将被换出，因为最早被装入； 页号=(100 ) B 块号=(101 ) B 物理地址= (1010000001111)B=(140F)H 2. LRU算法：第1号物理块将被换出，因为最久没被访问； 页号=(100) B 块号=(001) B 物理地址= (0010000001111)B=(40F)H CLOCK算法：第1号物理块将被换出，因为最近既没被访问又没被修改过。 页号=(100) B 块号=(001) B 物理地址= (0010000001111)B=(40F)H,2007-8-15 15:26

47、,操作系统|存储器管理,107,linux的页面置换机制 Linux描述页面的数据结构page linux使用LRU算法作为其页面交换的核心算法。 linux所使用的LRU交换算法已经与存储管理、进程管理、文件系统有关机制结合成一个整体。 定期地，特别是在系统相对空闲的时候，挑选一些页面预先换出，使系统始终维持一定的空闲页面供应量。,4.11 Linux存储管理,2007-8-15 15:26,操作系统|存储器管理,108,空闲页面,活跃页面,不活跃且修改的页面,不活跃且没修改的页面,页面状态和实现方法,内 存 空 间,4.11 Linux存储管理,2007-8-15 15:26,操作系统|存

48、储器管理,109,思考与作业 思考题一:一个进程的大小占5个页面，每页的大小为1K，系统为它分配了3个物理块。当前进程的页表如图所示： 块号存在位P 访问位R 修改位M,1、有那些页面不在内存？ 2、请分别计算进程中虚地址为0 x3B7、0 x12A5、0 x1432单元的物理地址（用十六进制表示） 思考题二：比较各种页面置换算法的性能和实现代价。 思考题三：想一想是否还有其它的页面置换算法。 作业 Page 142 : 23、27,2007-8-15 15:26,操作系统|存储器管理,110,4.9系统抖动,抖动现象 指系统页面置换频繁，大量CPU 时间花在来回进行页的调度上，小部分时间用于

49、实际运算。 一个较优的算法应尽可能避免出现抖动现象。一旦引起了这种局面，系统应能立即采取措施加以排除。,2007-8-15 15:26,操作系统|存储器管理,111,预防抖动问题（减少缺页中断次数） 程序设计质量：程序的局部化程度 分配适当的内存 工作集：在某段时间内，进程实际访问的页面的集合。 实验证明：对所有的程序来说，要使其有效的工作，它在内存中的页面数应不低于总页面数的一半。 L = S 准则 产生缺页的平均时间等于系统处理进程缺页的平均时间。,4.9 系统抖动,2007-8-15 15:26,操作系统|存储器管理,112,4.9 系统抖动,2007-8-15 15:26,操作系统|存储器管理,113,解决抖动问题的办法 改进算法 在进行淘汰或置换时，一般总是把缺页进程锁住不让其换出，而调入的页或段总是占据那些暂时得不到执行的进程所占有的内存区域，从而扩大缺页进程的工作集 挂起若干进程,4.9 系统抖动,4.10 请求分段存储管理,硬件支持 地址及段表,其中：增补位 ,0 该段未增长过 1 该段进行过动态增长,段表结构