计算机操作系统第四章.ppt

第四章 存储器管理,存储器的层次结构 程序的装入和链接 连续分配方式 基本分页存储管理方式 基本分段存储管理方式 虚拟存储器 请求分页存储管理方式 页面置换算法 请求分段存储管理方式,目的： 内存有限，有效地对内存进行管理,4.1 存储器的层次结构,一 多级存储器结构,二 寄存器与主存 1 寄存器 寄存器是CPU的组成部分，可用来暂存指令、数据和地址。容量小，价格十分昂贵。 在CPU的控制部件中，包含的寄存器有指令寄存器和程序计数器；在中央处理器的算术及逻辑部件中，包含的寄存器有累加器。 寄存器是内存阶层中的最顶端，也是系统获得操作资料的最快速途径，完全能与CPU协调工作。寄存器的长度通常以“字”作为单位。,2 主存储器,内存指的就是主板上的存储部件，用于保存进程运行时的程序和数据。 CPU直接与之通信，从中读数据送入寄存器，或将寄存器的数据写入内存， 内存的访问速度远低于CPU的指令执行速度，为缓和这一矛盾，引入了高速缓存。,三 高速缓存和磁盘缓存,一 高速缓存 在CPU和主存之间增加的用于提高系统执行效率的存储器，即Cache。速度比内存快，容量介于寄存器与内存之间。 根据程序执行的局部性原理，将主存中经常被访问的信息存放在Cache中。CPU取数据时，先从Cache中寻找，若没有，再去内存寻找。 高速缓存可有多级，一级高速缓存紧靠内存，速度最快，容量最小；二级高速缓存容量稍大，速度稍低。,二 磁盘缓存,由于磁盘的I/O速度远低于对内存的访问速度，因此将频繁使用的一部分磁盘数据和信息，暂时存放在磁盘缓存中，以提高访问速度。 磁盘缓存并不实际存在，依托于固定磁盘，提供对主存空间的扩充。 它的原理是：将一段时间内常用的磁盘数据放在内存的某个区域；或将CPU处理完后需要输出的数据暂存于内存的某个区域。,4.2 程序的装入和链接,从源程序到程序执行 地址空间的概念 重定位的概念 程序的装入 程序的链接,一 从源程序到程序执行,编译：编译程序 由编译程序（Compiler）将用户源代码编译成若干个目标模块。 链接：链接程序 由链接程序（Linker）将编译后形成的一组目标模块，以及它们所需要的库函数链接在一起，形成装入模块。 装入：装入程序 由装入程序（Loader）将装入模块复制到内存中。,库,二 地址空间,物理（绝对）地址程序执行 每个内存单元的固定顺序地址（编号）。 由物理地址组成的空间集合称为物理空间。 逻辑（相对）地址装入（汇编编译） 被链接装配（或汇编、编译）后的目标模块所限定的地址的集合； 相对于某个基准量（通常为：0）的编址。 由逻辑地址构成的空间集合称为逻辑空间。,三 重定位,重定位 概念：把程序装入内存时，修改程序中所有与地址有关的项。 逻辑地址变换为物理地址。 重定位的类型 静态重定位：程序执行前，一次性地变换地址并装入内存。 动态重定位：处理机每次访问内存时，由动态地址变换机构（硬件）自动执行地址变换。,内存地址空间,四 程序的装入,就是把链接好的装入模块装入“内存”。 装入方式 绝对装入 可重定位装入（静态重定位） 动态运行时装入（动态重定位）,绝对装入方式,要求：事先清楚程序将驻留在内存的什么位置 该内存地址可由程序员给出，也可由编译程序申请。 概念：装入程序直接按照装入模块中的地址，将程序和数据装入内存。逻辑地址与内存地址相同，无须进行地址变换。 局限：仅可应用于单道程序环境中,静态重定位,在装入程序将装入模块装入内存时，进行逻辑地址到物理地址的转换 数据地址和指令地址都要做相应修改 地址变换在程序装入内存时一次完成，一旦程序装入内存，不允许它在内存空间移动。,动态重定位,装入程序将装入模块装入内存后，并不立即将相对地址转换为绝对地址，而是将地址转换推迟到程序执行时才进行。 为避免程序运行时，进行地址转换影响指令执行的速度，需要重定位寄存器的支持,五 程序的链接,链接： 把一个程序相关的一组目标模块和系统调用模块（库函数）链接形成一个整体装入模块的过程。 具体工作： 对相对地址的修改；变换外部调用符号。 链接方式： 静态链接 装入时动态链接：便于修改和更新；便于共享。 运行时动态链接：最小化快速装入，节省内存。,静态链接方式,程序运行前，先将各目标模块及它们所需要的库函数，链接成一个完成的可装入模块，以后不再拆开。 要做的两项工作： 1 修改相对地址 2 将外部调用符号修改成相对地址,装入时动态链接,并不事先链接成一个可装入模块 源程序经过编译得到的目标模块，在装入内存时边装入边链接。 即在装入一个目标模块时，若发生外部调用事件，则由装入程序找出相应的外部目标模块，进行链接并装入内存。此时，也应修改目标模块中的相对地址。 优点：便于修改、更新和共享,将对某些模块的链接推迟到程序执行时进行。 即，在程序执行过程中，发现一个被调用模块尚未调入内存，立即由OS去找到该模块，并将其装入内存，链接到调用者模块上。 优点：程序执行时，未用到的模块，都不进入内存，不进行链接。加快了程序的装入过程，节省了内存空间。,运行时动态链接,4.3 连续分配方式,单一连续分配 固定分区分配 动态分区分配 可重定位分区分配 对换,连续分配方式： 为用户程序分配一个连续的内存空间。曾在20世纪60-70年代被广泛应用，至今仍在内存分配方式中占有一席之地。,一 单一连续分配,单一连续分配的基本思想 把内存分为系统区和用户区，系统区供OS使用，通常放在低址部分；系统区以外的全部内存空间是用户区。 单一连续分配的特点 只能用于单用户、单任务的OS中。 软件简单，硬件要求低（无需存储保护） 实例 CP/M，MS-DOS，RT-11,二 固定分区分配,基本思想 将内存的用户空间划分成若干个固定大小的区域，在每个分区中只允许装入一道作业。 特点： 有几个分区，则允许几道作业并发执行 当有空闲分区时，则从外存后备队列选择一个适当大小的作业进入该分区。,划分分区的方法 分区大小相等 分区大小不相等,缺乏灵活性：作业小，造成内存空间的浪费； 作业大，一个分区装不下，作业无法运行。因 此，常用于工控系统中。,将用户区划分成具有多个较小的分区、适量的 中等分区及少量的大分区，以满足不同作业的 需求,内存分配管理 分区使用表（MBT） 分区按大小排队 由内存分配程序检索分区使用表，找到符合要求的分区。,存储保护与重定位（地址转换） 每个分区（一道程序）对应一对界地址寄存器：上/下限寄存器。 采用静态重定位方式，即由链接/装入程序完成。 优缺点 优点：简单，要求的硬件支持少（一对R）； 缺点：存在大的碎片（内碎片），主存利用率低。,碎片很多小的内存空间 内碎片碎片处于分区内部 外碎片碎片处于分区与分区之间,三 动态分区分配,思想 位置和大小都不固定，根据进程的实际需要，动态分配内存空间，又称可变分区分配。,例子：一计算机系统有2560KB内存，采用可变分区模式管理，OS占低地址的400KB空间，用户内存为2160KB。 如图所示：,注意,1.可变分区模式下，刚开始，OS就绪，但任何用户程序未进入内存前整个用户内存区是一大空间。已占用区和空闲分区并不是绝对的。 2.必须用某种数据结构来记录分区的情况。 3.程序进入内存时的例行工作就是分配空闲区和装入程序，并修改相应的数据结构。 4.一旦一个内存分区被分配给一个进程，该进程被装入时需重定位。,数据结构的两种形式 空闲分区表 空闲分区链,空闲分区表用于记录每个空闲分区的情况， 每个空闲分区占一个表目，表目中包括分 区序号、分区始址、分区大小等项目,利用双向链表形式，记录空闲分区的使用 情况。 每个空闲分区除记录该分区的基本情况外， 还要在头部和尾部分别增加前向指针和后向 指针，以实现对分区的双向链接，便于检索。,存储分配算法 首次适应算法 循环首次适应算法 最佳适应算法 最快适应算法 快速适应算法,首次适应算法,数据结构 -空闲分区链，按照地址递增的次序链接 算法 -从链首开始顺序查找，把找到的第一个能满足申请者要求的空闲区分配给申请者。若空闲区比作业长度大，则分割该空闲区：一部分分配给作业，剩余部分空闲。 若找不到，则内存分配失败，返回。,特点 -优先利用内存中低址部分的空闲分区 优点 -保留了高址部分的大空闲区，留给以后到达的大作业。 缺点 -低址部分不断被划分，留下很多难以利用的小碎片 -每次查找都是从低址开始，增加了查找的开销,循环首次适应算法,改进算法 -分配内存空间时，不再是从链首开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找，直到找到一个能满足要求的空闲分区，然后从中划出与请求大小相等的内存空间分配给作业。 -采用循环查找方式，如果找到链尾仍未找到合适的分区，则返回链首继续查找。,改进数据结构 -增加一起始查询指针，指示下一次起始查询的空闲分区。 优点 -内存的空闲分区分布更均匀，减少了查找空闲分区的时间开销 缺点 -缺乏大的空闲分区,最佳适应算法,数据结构 -空闲分区链，空闲分区按容量由小到大排列 算法 -为作业分配内存时，把能满足要求的最小的空闲分区分配给作业 缺点 -每次分配后剩余部分都是最小的，因此会留下许多难以利用的小碎片,最坏适应算法,数据结构 -空闲分区链，空闲分区按容量由大到小排列 算法 -为作业分配内存时，扫描空闲分区链表，挑选最大的空闲分区分割给作业。,缺点 -缺乏大的空闲分区 优点 -每次分配后剩下的空闲区不会太小，产生碎片的几率小 -只要看第一个分区是否满足需要即可，查找效率很高,快速适应算法,数据结构 1 多个空闲分区链表 空闲分区按容量大小分类，每类对应一个链表。 2 管理索引表 每个表项对应一个分区类型，并记录该链表的表头指针,算法 根据进程长度，寻找到能容纳它们的最小空闲区链表，取下第一块进行分配即可。 优点： 1）查找效率高 2）分配空闲分区时，不对分区进行分割，能保留大的分区，不会产生外部碎片 缺点： 1）归还分区时算法复杂，系统开销大 2）分配给进程的分区与进程要求的大小不完全一致，产生内碎片。,内存分配 1检查分区大小与所需空间大小是否“匹配”： M.sizeU.size M.Size - U.Size Size （不再分割的小分区的尺寸） 2剩余部分挂接到空闲分区链表上。,回收内存 回收区与插入点的前一个空闲分区相邻接； 回收区与插入点的后一个空闲分区相邻接； 回收区与插入点的前后两个空闲分区相邻接； 回收区不与任何一个空闲分区相邻接；,合并，修改前一分区的大小,合并，修改首地址和大小,合并，首地址为前一分区首地址， 修改大小，去掉后一分区表项,增加新的表项，填写首地址和大小，插入链表中的合适位置,Job7,Job6,四 可重定位分区分配,动态重定位的引入 随着系统接收的作业的增加，内存中连续的大块分区不复存在，产生了大量的“碎片”。 新的作业无法装入到每个“碎片”小分区上运行，但所有碎片的空间总和可能大于需求。 通过“拼接”/“紧凑”/“紧缩”/“”澄清“来实现”程序的浮动“/” 动态重定位“。,紧凑 通过移动内存中作业的位置，以把原来多个分散的小分区拼接成一个大分区的方法，称为“拼接”或“紧凑”。,动态重定位的实现 必须由硬件地址变换机构支持实现重定位R 重定位寄存器：存放程序存放的起始地址。 当系统对内存进行了“紧凑”而使若干程序在内存发生移动后，不需要对程序做任何修改，只要用该程序在内存的新起始地址，去置换原来的起始地址即可。,可重定位分区分配示意图,优缺点分析 优点：消除了“碎片”，提高了内存利用率，同时提高了系统效率。 缺点：需要动态重定位“硬件”机构支持，增加了系统成本，并轻度降低了程序执行速度，“紧凑”处理增加了系统开销。,五 对换,引入原因： 内存中的某些进程由于等待事件发生而阻塞，但占用了大量的内存空间；外存上有许多作业等待调度，因无内存而不能运行。 为解决这一矛盾，避免系统资源的浪费，引入了“对换”机制。,对换的概念 把内存中暂时不能运行的进程或者暂时不用的程序和数据调出到外存上，以便腾出足够的内存空间，把已具备运行条件的进程或进程所需要的程序和数据调入内存。 对换是提高内存使用率的有效手段。 实现方法 通过外存缓冲，以进程为单位“滚进滚出” 。一个作业的所有进程不必同时位于内存中。,对换空间的管理 把内存分成文件区和对换区。前者用来存放文件，后者用来存放兑换出来的进程。 对换区采用连续分配方式，空闲盘块的组织、分配和回收与动态分区方式中内存空间的分配与回收方式基本相同。,进程的换出与换入,对换的时机：创建新进程而内存不足时。 进程的换出 选择处于阻塞状态且优先级最低的进程作为换出进程，启动磁盘，将该进程的程序和数据送到磁盘的对换区上，回收该进程占用的内存空间。 进程的换入 系统定时查看所有进程的状态，从中找出“就绪”状态但已换出的进程，将其中换出时间最久的进程作为换入进程，将其换入。,4.4 基本分页存储管理方式,有碎片,系统开销大,页面与页表 地址变换机构 两级和多级页表 基本分页的特点,一 页面与页表,页面 页面：逻辑地址空间分成大小相同的页 块（页框）：内存空间分成与页面大小相同的块 页面和物理块按顺序编号 页面大小：2n Bytes 一般在：512B 8/32K,页面过小，页数过多，页表过长，占用大量内存； 页面过大，内碎片增大，浪费内存,地址结构 逻辑地址 物理地址 页表 数据结构：页号、块号、存取控制项 页表的作用：实现从页号到物理块号的地址映射。,位移量d,物理块号P,位移量W,页号P,11,12,31,P=INT(A/L) w=A mod L,二 地址变换机构,基本的地址变换机构 页表存放在内存系统区的一个连续空间中； PCB和页表寄存器PTR中存有页表的首地址和页表长度； 查询页表：页表首地址+页号x表项长度； 地址映射从逻辑地址到物理地址的变换过程。,具有快表的地址变换机构 引入:CPU存取数据需要两次访问内存,降低 了CPU的处理速度 联想寄存器 Cache； 空间大小： 几K到几百K ，部分表项（16512个）； 原则:先查快表,再查页表； 地址映射过程。,当进程访问一页时，系统将页号与快表中的所有项进行并行比较。若访问的页在快表中，即可立即进行地址转换。 当被访问的页不在快表中时，就要将由慢表找到的内存块号与页号填入快表中，若快表已满，则置换其中最近未被访问的项。,另外，在设置快表的情况下，硬件地址转换机构在进行地址变换时，同时开始两个变换过程。 一个是利用主存页表进行的正常变换过程，另一个是利用快表进行的快速变换过程。一旦快表中有与查找的页号相符合时，则立即停止正常的访主存页表过程。并将快表中的块号与CPU给出的页内位移相拼接，得到访问主存的绝对地址,从而结束了快表的查找工作。,三 两级和多级页表,两级页表 解决大页表占用大的连续存储空间的问题； 关于“页表”的分页存放“页表”外层页表； 逻辑地址： 外层页号+外层页内地址+页内地址 多级页表,四 基本分页的特点,优点： 存在页内碎片，但碎片相对较小，内存利用率较高； 实现了离散分配，消除了程序浮动； 缺点： 需要专门的硬件支持，尤其“快表”； 内存访问的效率下降。 不足： 不能实现真正的共享，不支持动态链接。,4.4 基本分段存储管理方式,基本分段管理思想的引入 基本原理 地址变换 分段与分页的主要区别 段页式存储管理方式,1 基本分段管理思想的引入,为用户提供一个方便灵活的程序设计环境而提出来的。 页式管理中，一个页面中可能装有2个不同的子程序段的指令代码，不能通过页面共享来达到共享一个逻辑上完整的子程序或数据块,程序通过分段(segmentation)划分为多个模块，如代码段、数据段。 可以分别编写和编译 可以针对不同类型的段采取不同的保护 可以按段为单位来进行共享，包括通过动态链接进行代码共享,2 分段系统的基本原理,将进程的逻辑地址空间按内容或函数关系划分为若干个段(segment) ，每个段定义一组逻辑上完整的程序或数据，如一个进程可以被划分为主程序段、子程序段、数据段、堆栈段等。 程序加载时，以段为单位分配其所需的内存（内存分区）,每个段分得一个连续的分区。所有段都被装入到存储器的可用区域中，并建立一个段表 每个段是一个首地址为0的，连续的一维线性空间，段长可以动态增长。段的大小不需要相等。,基本原理,段表 段号、段基地址、段的长度、段状态等 段表寄存器（段表始址和段表长度） 利用段表实现地址映射,地址变换及变换机构,基本分段管理的地址变换 与基本分页管理的变换机构和过程类似。 段表寄存器 存放段表的起始地址和段表长度； 越界访问控制 逻辑地址的段号与段表长度比较； 段内地址与段表中保存的段长比较；,问题：每次访问数据，都要两次访问内存，降低了计算机的速率。 解决的办法：增加联想寄存器。,分段与分页的主要区别,页是信息的物理单位，段是信息的逻辑单位； 页的大小固定，段的大小动态变化； 分页系统中的逻辑地址空间是一维的，分段系统中的是二维的。 分页系统中不易实现“共享”和“动态链接” ，分段则很容易。,5 段页式存储管理方式,分页：提高内存利用率 分段：更好的满足用户需要 分页+分段？,段页式存储管理方式,基本思想 结合分页和分段技术； 发挥出分页和分段管理方式各自的优点。 原理 对内存进行分页（物理块/页架）； 对用户作业先分段，各段再分页。 地址结构与地址变换 段号、段内页号、页内地址三部分 段表和页表,利用段表和页表实现地址映射,段页式系统中的地址变换机构,段页式存储管理的优缺点 同时具备分段和分页管理的优点：分散存储，内存利用率较高；便于代码或数据共享，支持动态链接等。 访问效率下降：一次访问转换成了三次访问。,4.5 虚拟存储器,虚拟存储器的引入 虚拟存储器的实现方法 虚拟存储器的特征,1 虚拟存储器的引入,内存空间的限制与内存的扩充方法 内存空间装不下的大作业如何运行？ 作业量大时，如何允许更多的作业并发？ 物理扩充：增加硬件投入； 虚拟存储器技术：利用海量外存的内存“空间”扩展。,常规存储器管理方式的特征,一次性 驻留性,程序执行的局部性原理 程序在执行时将呈现局部性规律，即在一较短的时间内，程序的执行仅局限于某个部分；相应地，它所访问的存储空间也局限于某个区域。,局限性表现在下述两个方面,时间局部性：一条指令的一次执行和下次执行，一个数据的一次访问和下次访问都集中在一个较短时期内； 空间局部性：当前指令和邻近的几条指令，当前访问的数据和邻近的数据都集中在一个较小区域内。,局部性的具体表现,程序在执行时，大部分是顺序执行的指令，少部分是转移和过程调用指令。 过程调用的嵌套深度一般不超过5，因此执行的范围不超过这组嵌套的过程。 程序中存在相当多的循环结构，它们由少量指令组成，而被多次执行。 程序中存在相当多对一定数据结构的操作，如数组操作，往往局限在较小范围内。,虚拟存储器的定义 虚拟存储器是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。,物理上不存在，但可以使用（访问）； 允许作业部分装入，需要时再临时装入所需的部分，直到作业退出，某些部分也有可能没被装入过。,虚拟存储器的实现方法,必须建立在离散分配的内存管理技术基础上。,分页请求系统 基本分页系统 + 请求分页功能 + 页面置换功能 硬/软件支持：请求分页的页表机制、缺页中断机构、动态地址变换机构,请求分段系统 基本分段系统 + 请求分段功能 + 分段置换功能； 硬/软件支持：请求分段的段表机制、缺段中断机构、动态地址变换机构。,虚拟存储器的特征,多次性 一个作业被分成多次调入内存运行； 对换性 允许在作业的运行过程中进行换进、换出； 虚拟性 能从逻辑上扩充内存容量，是用户“看到”的内存容量远大于实际大小。 该特征是以上两个特征为基础的。,4.6 请求分页存储管理方式,请求分页中的硬件支持 内存分配策略和分配算法 调页策略,请求分页存储管理的基本原理,系统自动地将作业的地址空间分页，将系统的主存空间分块，页与块等大小。 在作业运行前，只把初始需要的一部分页面装入内存块里，运行中需要访问自己地址空间中的但当前不在内存的页面时产生缺页中断，由缺页中断服务程序将所需的页面调入内存。 若此时内存中没有空闲物理块安置请求调入的新页面，则系统按预定的置换策略自动选择一个或一些在内存的页面，把它们换出到外存。,这里的请求调入和置换功能都是比实分页存储管理增加的内容，是实现虚拟存储的主要功能,请求分页中的硬件支持,页表机制 用于地址转换； 页表表目需要增加外存块号、状态位、访问位或访问字段、修改位、存取控制字段等。 外存块号指出该页在外存的地址，供调入该页时用； 状态位指示该页是否在内存，供程序访问时用，也是检查是否缺页的标志位； 访问位或访问字段则是该页被访问过的标志或该页被访问过的次数； 修改位表示该页是否被修改过； 存取控制字段则是用来限制页面被安全共享的。,缺页中断机构 所要访问的页不在内存时，便引发一次缺页中断； 与常规中断的不同之处： 在指令执行期间产生和处理中断信号； 一条指令在执行期间，可能产生多次缺页中断。,地址变换机构 首先检索快表，若找到，修改表项中的访问位，然后利用表项中给出的页架号和页内地址，形成物理地址。 如果在快表中未找到相应的页表项， 检索内存中的页表，察看页表中的状态位，若该页已经调入内存，填写快表，当快表满时，应淘汰一个页表项；若该页尚未调入内存，产生缺页中断，请求OS把该页调入。,内存分配策略和分配算法,最小物理块（页架）数的确定 保证进程正常运行所需的最少物理块数； 与指令的格式、功能和寻址方式有关。,页架的分配策略 固定分配局部置换 1为进程分配固定数目的物理块，并在进程运行期间保持不变； 2发生缺页时，从该进程在内存的页面中选择一个页面换出。 3难点：难于确定某个进程的物理块数。,可变分配全局置换 1 系统中的每个进程占有一定数量的物理块 2 OS保持一个空闲物理块队列 3 发生缺页时，从系统空闲物理块队列中，分配给请求进程 4 当空闲队列空时，从内存中选择一页调出，该页可能是系统中任一进程的页。,可变分配局部置换 1 进程缺页时，只能从该进程在内存的页面中选择一页调出，不会影响其它进程 2 当进程缺页率较高或较低时，能由OS对其占据的物理块数加以调整。,物理块分配算法 平均分配算法 将系统中所有可供分配的页架，平均分配给各个进程。 按比例分配算法 根据进程的大小按比例分配页架的算法。 考虑优先权的分配算法 将物理块分成两部分，一部分按比例分配，另一部分按优先权高低进行分配。,Bi=(si/s)*m,调页策略,何时调入页面的问题 预调页策略：首次调入内存时 请求调页策略：运行中的发生缺页现象时,预调页策略,也称先行调度，即一页面被访问前就已经预先置入内存，以减少今后的缺页率。 主要适于进程的许多页存放在外存的连续区域中的情况。有的系统结合请求调入使用，即每次缺页时装入多个页面。 优点：提高调页的I/O效率。 缺点：基于预测，若调入的页在以后很少被访 问，则效率低。常用于程序首次装入时的调页。,请求调页策略,当发生页面故障时进行调度，即当进程访问不在内存的页面引发缺页中断时，由系统根据这种访问请求把所缺页面装入内存。 优点：由请求调入策略装入的页一定会被访问，比较容易实现。在目前的虚拟存储器中，大多采用此策略。 缺点：每次仅调入一页，增加了磁盘I/O的启动频率。,从何处调入页面的问题 1 对换区空间足够大，则全部从对换区调入所需要的页面 2 缺少足够的对换区空间，则不会被修改的文件从文件区调入；被修改的文件从对换区调入。,页面的调入过程 响应中断 保存CPU环境 查找页表（快表），得到该页在外存中的块号，启动磁盘I/O读入 如果内存已满，先置换，再调入 最后修改页表（快表）对应项的内容。,4.7 页面置换算法,最佳置换算法（Optimal） 先进先出置换算法(FIFO) 最近最久未使用（LRU）置换算法 Clock置换算法 最少使用（LFU）置换算法 页面缓冲置换算法(PBA),选择换出页面的算法,一 最佳淘汰算法OPT,这是Belady于1966年提出的一种理论上的算法。该算法每次都淘汰以后永不使用的，或者过最长的时间后才会被访问的页面。 显然，采用这种算法会保证最低的缺页率，但它是无法实现的，因为它必须知道页面“将来”的访问情况。不过，该算法仍有一定意义，可作为衡量其他算法优劣的一个标准。,假定系统为某个进程分配了三个物理块，进程的访问顺序为7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0,采用OPT淘汰算法：,7 7 2 2 2 2 2 2 2 2 2 2 2 2 2 0 0 0 0 0 0 4 4 4 0 0 0 0 0 0 1 1 1 3 3 3 3 3 3 3 3 1 1 1,7，0，1，2，0，3，0，4，2，3，0 ，3，2，1，2，0,二 先进先出淘汰算法FIFO,这是最早出现的淘汰算法。 总是淘汰最先进入内存的页面。它实现简单，只需把进程中已调入内存的页面，按先后次序链成一个队列，并设置一个所谓的替换指针，使它总是指向内存中最老的页面。 缺点：效率不高，因为它与进程实际的运行规律不相适应，比如常用的全局变量所在的页面或者循环体所在页面都可能被它选为淘汰对象。出现bleady现象。,采用FIFO淘汰算法,7 7 2 2 2 2 4 4 4 0 0 0 0 0 0 0 0 0 0 3 3 3 2 2 2 2 2 1 1 1 1 1 1 1 0 0 0 3 3 3 3 3 2 2,7，0，1，2，0，3，0，4，2，3，0 ，3，2，1，2，0,Belady现象：采用FIFO算法时，如果对一个进程未分配它所要求的全部页面，有时就会出现分配的页面数增多，缺页率反而提高的异常现象。 Belady现象的描述：一个进程P要访问M个页，OS分配N个内存页面给进程P；对一个访问序列S，发生缺页次数为PE（S,N）。当N增大时，PE(S, N)时而增大，时而减小。 Belady现象的原因：FIFO算法的置换特征与进程访问内存的动态特征是矛盾的，即被置换的页面并不是进程不会访问的。,三 最近最久未使用算法(LRU）,根据页面调入内存后的使用情况，选择内存中最久未使用的页面被置换。利用“最近的过去”作为“最近的将来”的近似，性能接近最佳算法。 OPT算法使用页面将要被访问的时间，LRU算法使用页面最后一次被访问的时间。二者唯一的差别是：OPT是向后看的，而LRU是向前看的。,7 7 2 2 2 2 4 4 4 0 0 0 1 1 1 0 0 0 0 0 0 0 0 3 3 3 3 3 3 0 1 1 1 3 3 3 2 2 2 2 2 2 2 2,7，0，1，2，0，3，0，4，2，3，0 ，3，2，1，2，0,LRU的两个实现算法：,计时法：对于每一页面增设一个访问时间计时器，每当一个页面被访问时，当时的绝对时钟内容被拷贝到对应的访问时间计时器中，这样系统记录了内存中所有页面最后一次被访问的时间。淘汰时，选取访问时间计时器的值最小的页面。（书中是移位寄存器）,为了记录进程在内存中各页的使用情况，为每个页面配置一个移位寄存器 R=Rn-1Rn-2Rn-3R2R1R0 当进程访问某个物理块时，要将相应寄存器的最高位置成1。然后，定时信号每隔一定时间将寄存器右移一位。 将寄存器的值看成一个整数，那么具有最小值的寄存器所对应的页面，就是最近最久未使用的页面。,堆栈法：每当进程访问某页面时，便将该页面的页号从栈中移出，将它压入栈顶。栈顶始终是最新被访问的页面的编号。栈底则是最近最久未被使用的页面的页面号。,假定现有一进程所访问的页面的页面号序列为： 4，8，0，8，1，0，2，1，2，6,随着进程的访问，栈中页面号的变化情况：,2 1 2 6 1 0 1 1 2 1 2 0 8 8 1 0 0 0 0 1 8 8 0 0 8 8 8 8 8 0 4 4 4 4 4 4 4 4 4 4 8,4，8，0，8，1，0，1，2，1，2，6,LRU的开销是很大的，必须有硬件的支持。完全由软件实现其速度至少会减少10倍，因此LRU近似算法更实用些。,四 时钟(Clock)淘汰算法,内存中所有页面通过指针链接成一个循环队列；每页增设一访问位，当某页被访问时，访问位置1。 选择淘汰页面时，只需要检查替换指针所指页面的访问位，如果它的访问位为0，则淘汰该页，新装入的页插入到此位置，然后指针前进一个位置；如果它的访问位为1，则清除为0，并将指针前进一个位置，继续检查后续页面。重复此过程，直到找到访问位为0的页面为止。,考虑置换代价，利用访问位A、修改位M共同表示一个页面的状态 四种状态：00 01 10 11 三轮扫描： 第一轮：查找00页面，找到后直接淘汰，不修改访问位。未找到，下一步； 第二轮：查找01页面，找到后先写回外存再淘汰，所有访问到的页面访问位复位为“0”。未找到，下一步； 第三轮：查找10页面，找到后直接淘汰，所有访问到的页面访问位复位为“0”。未找到，重复第一步。,改进型Clock置换算法,五 最少使用（LFU）置换算法,选择在最近时期使用最少的页面淘汰。 需要为内存中的每个页面设置一个移位寄存器，用来记录该页面被访问的频率。 每次访问某页时，便将该移位寄存器的最高位置1，此后每隔一定时间自动右移一位。,六 页面缓冲置换算法,消除频繁的磁盘I/O 被淘汰的页面未被修改，则挂到空闲页面链表上，不需写回磁盘。装入新页面时，在该链表中选择一个空闲物理块。 被淘汰的页面已被修改，则挂到已修改页面链表上，该链表中的页面数达到一定数目时，才集中写回到磁盘上。,影响缺页中断率的因素,（1）页面调度算法不合理 抖动又叫颠簸，是指一段时间里，页面在内存与外存之间频繁地调度或换入换出，以至于系统用于调度页面所需要的时间比进程实际运行所占用的时间还要多。 显然，抖动是由于缺页中断率很高而引起的一种坏现象，它将严重影响系统的效率，甚至可能使系统全面崩溃。,（2）分配给作业的内存块数太少,作业的缺页中断率与作业所占内存块数成反比。分配给作业的内存块数太少是导致抖动现象发生的最主要的原因，实验分析表明：对所有的程序来说，要使其有效地工作，它在内存中的页面数不应少于它的总页面数的一半。,（3）页面大小的选择不合理,虽然缺页中断率与页面尺寸成反比，但页面尺寸却不能一味地求大，它一般在0.5KB4KB之间，是个实验统计值。因为页面大时，页表较小，占空间少，查表速度快，缺页中断次数少，但页面调度时间长，页内碎片较大。页面小时，恰恰相反。,（4）用户程序编制的方法不合适,作业的缺页中断率与程序的局部化（包括时间局部化和空间 局部化）程度成反比。用户程序编制的方法不合适可能导致 程序运行的时空复杂度高，缺页次数多。,4.8 请求分段存储管理方式,以基本分段内存管理为基础，程序运行前，只需先调入部分分段，便启动执行。其它分段在需要时，通过缺段中断处理程序临时调入。 请求分段中的硬件支持 请求分段中的分段共享 请求分段中的分段保护,请求分段中的硬件支持,段表机制 段号（名）、段长、段的基址、外存始址 存取方式、访问字段A、修改位M、存在位P、增补位 缺段中断机构 以信息分段为单位操作。由于分段不定长，处理较缺页中断复杂。 地址变换机构 在基本分段系统地址变换机构的基础上形成，增加了分段不在内存时的缺段中断请求。,请求分段中的分段共享,共享段表 共享段的段名/号、段长、内存始址、存在位、共享进程计数器 共享此分段的各进程信息：进程名/号、段号、存取控制 共享段的分配与回收 填写共享段表 首个进程 后续进程 仅当共享进程数Count=0时，才回收,请求分段中的分段保护,越界检查 段表寄存器：段表始址、段表长度 段号段表长度、段长段内地址 存取控制检查 存取控制字段（用户级别） 只读、只执行、读/写 环保护机构 可以访问驻留在相同环或较低特权环中的数据； 可以调用驻留在相同环或较高特权环中的服务。,习题四,1 在一系统中采取分页存储管理，页的大小为4KB，允许用户进程的存储映