4存储器管理

null计算机操作系统计算机操作系统liuyong@ustc.edu.cn 2007.9 null第四章 存储器管理 4.1 程序的装入和链接 4.2 连续分配方式 4.3 基本分页存储管理方式 4.4 基本分段存储管理方式 4.5 虚拟存储器的基本概念 4.6 请求分页存储管理方式 4.7 页面置换算法 4.8 请求分段存储管理方式 主存管理的功能 主存管理的功能 地址映射 主存分配 存储保护 主存扩充(虚拟内存) 一.地址映射(地址重定位)一.地址映射(地址重定位)内存的每个存储单元都有一个编号，这种编号称为内存地址（或称为物理地址，绝对地址）。 内存地址的集合称为内存空间（或物理地址空间）。 null要求用户用内存地址编程是非常困难的，尤其是在多道程序 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 的环境中。 用户编程所用的地址称为逻辑地址（或程序地址，或虚地址），由逻辑地址组成的空间称为逻辑地址空间（或程序地址空间）。 地址映射的方式地址映射的方式我们把用户程序装入内存时对有关指令的地址部分的修改定义为从程序地址到内存地址的地址映射，或称为地址重定位。 地址映射的方式： 1、静态地址映射 2、动态地址映射1、静态地址映射1、静态地址映射程序被装入内存时由操作系统的连接装入程序完成程序的逻辑地址到内存地址的转换。映射 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 映射方法假定程序装入内存的首地址为BR，程序地址为VR，内存地址为MR，则地址映射按下式进行：MR=BR+VR 。 例如，程序装入内存的首地址为1000，则装配程序就按MR=1000+VR对程序中所有地址部分进行修改，修改后指令Load A，200就变为Load A，1200 优缺点优缺点优点：不需要硬件的支持。 缺点：程序必须占用连续的内存空间；一旦程序装入后不能移动。 2、动态地址映射2、动态地址映射动态地址重定位是在程序执行的过程中，每次访问内存之前，将要访问的程序地址转换为内存地址。一般来说这种转换是由专门的硬件机构来完成的。 映射方法映射方法最简单的硬件机构是重定位寄存器。 在地址重定位机构中，有一个基地址寄存器BR和一个程序地址寄存器VR，一个内存地址寄存器MR。 地址映射的具体过程地址映射的具体过程程序装入内存后，它所占用的内存区的首地址由系统送入基地址寄存器BR中。 在程序执行的过程中，若要访问内存，将访问的逻辑地址送入VR中。 地址转换机构把VR和BR中的 内容 财务内部控制制度的内容财务内部控制制度的内容人员招聘与配置的内容项目成本控制的内容消防安全演练内容 相加，并将结果送入MR中，作为实际访问的地址。动态地址映射的优缺点动态地址映射的优缺点优点： 程序占用的内存空间是动态可变的，当程序从某个存储区移到另一个区域时，只需要修改相应的寄存器BR的内容即可。 一个程序不一定要求占用一个连续的内存空间。 可以部分地装入程序运行。 便于多个进程共享同一个程序的代码。 动态地址重定位的代价： 需要硬件的支持。 实现存储管理的软件算法较为复杂。 二. 主存分配与回收 二. 主存分配与回收 要完成内存的分配和回收工作，要求设计者选择和确定以下几种策略和结构： 调入策略 放置策略 置换策略 分配结构调入策略调入策略用户程序在何时调入内存的策略。 目前有请调和预调两种放置策略放置策略用户程序调入内存时，确定将其放置在何处的策略。置换策略置换策略当需要将某个用户程序调入内存而内存空间又不够时，就要确定哪个或哪些程序可以从内存中移走。分配结构分配结构分配结构是用来登记内存使用情况的数据结构。如空闲区表、空闲区队列等。 引起内存分配和回收的原因引起内存分配和回收的原因进程的开始和结束。 进程运行的过程中，它所占用的内存也可能发生变化。如栈的变化。 进程映像在内存和外存之间传递。由于内存有限，系统中不可能容纳所有进程，有些进程的映像可以存放在外存，当要运行这些进程时，必须把它们调入内存。 系统为了充分利用内存空间，有时可能对内存空间进行调整。三.存储保护三.存储保护 保证在内存中的多道程序只能在给定的存储区域内活动并互不产生干扰。 包括： 防止地址越界 防止越权(对共享区有访问权) 存储保护的硬件支持存储保护的硬件支持界地址寄存器（界限寄存器） 界地址寄存器（界限寄存器）界地址寄存器（界限寄存器）界地址寄存器被广泛使用的一种存储保护技术 机制比较简单，易于实现实现方法实现方法在CPU中设置一对下限寄存器和上限寄存器存放用户作业在主存中的下限和上限地址 也可将一个寄存器作为基址寄存器，另一寄存器作为限长寄存器（指示存储区长度） 每当CPU要访问主存，硬件自动将被访问的主存地址与界限寄存器的内容进行比较，以判断是否越界 如果未越界，则按此地址访问主存，否则将产生程序中断——越界中断（存储保护中断）图示图示四.主存扩充(虚拟内存)四.主存扩充(虚拟内存)为了使程序员在编程时不受内存的结构和容量的限制，系统为用户构造一种存储器，其结构可能与内存结构不同，容量可能远远超过内存的实际容量。这种面向编程的存储器称为虚拟存储器。由虚存构成的存储空间称为虚存空间。或称虚地址空间。实现虚拟内存的基本原理实现虚拟内存的基本原理将程序正在使用的部分内容放在内存，而暂时不用的部分放在外存，在需要时由系统调入内存，并将不需要（或暂不需要）的部分调出内存。 由于程序在执行时，在一段时间内一般仅使用它的程序的一部分（或一小部分），所以程序仅有部分装入内存完全能够正确执行。 要由操作系统结合相关硬件来完成上述工件，这样计算机好象为用户提供了一个容量远大于内存的存储器，这个存储器称为虚拟存储器。 null4.1 程序的装入和链接 图 4-1 对用户程序的处理步骤 null4.1.1 程序的装入1. 绝对装入方式(Absolute Loading Mode) 程序中所使用的绝对地址，既可在编译或汇编时给出， 也可由程序员直接赋予。 但在由程序员直接给出绝对地址时， 不仅要求程序员熟悉内存的使用情况，而且一旦程序或数据被修改后，可能要改变程序中的所有地址。因此，通常是宁可在程序中采用符号地址，然后在编译或汇编时，再将这些符号地址转换为绝对地址。 null2. 可重定位装入方式(Relocation Loading Mode) 图 4-2 作业装入内存时的情况 null3. 动态运行时装入方式(Denamle Run-time Loading) 动态运行时的装入程序，在把装入模块装入内存后，并不立即把装入模块中的相对地址转换为绝对地址，而是把这种地址转换推迟到程序真正要执行时才进行。因此， 装入内存后的所有地址都仍是相对地址。 null4.1.2 程序的链接 1. 静态链接方式(Static Linking) 图 4-3 程序链接示意图 null 在将这几个目标模块装配成一个装入模块时，须解决以下两个问题： (1) 对相对地址进行修改。 (2) 变换外部调用符号。 null2. 装入时动态链接(Loadtime Dynamic Linking) 装入时动态链接方式有以下优点：  便于修改和更新。 (2) 便于实现对目标模块的共享。 null3. 运行时动态链接(Run-time Dynamic Linking) 近几年流行起来的运行时动态链接方式，是对上述在装入时链接方式的一种改进。这种链接方式是将对某些模块的链接推迟到执行时才执行，亦即，在执行过程中，当发现一个被调用模块尚未装入内存时，立即由OS去找到该模块并将之装入内存， 把它链接到调用者模块上。凡在执行过程中未被用到的目标模块，都不会被调入内存和被链接到装入模块上，这样不仅可加快程序的装入过程，而且可节省大量的内存空间。 null4.2 连续分配方式4.2.1 单一连续分配 这是最简单的一种存储管理方式，但只能用于单用户、单任务的操作系统中。采用这种存储管理方式时，可把内存分为系统区和用户区两部分，系统区仅提供给OS使用，通常是放在内存的低址部分；用户区是指除系统区以外的全部内存空间， 提供给用户使用。 null4.2.2 固定分区分配 1. 划分分区的方法 分区大小相等， 即使所有的内存分区大小相等。 (2) 分区大小不等。 null2. 内存分配 图 4-4 固定分区使用表 null4.2.3 动态分区分配 1. 分区分配中的数据结构 空闲分区表。 (2) 空闲分区链。 图 4-5 空闲链结构 null2. 分区分配算法 首次适应算法FF。 (2) 循环首次适应算法，该算法是由首次适应算法演变而成的。 (3) 最佳适应算法。 (4) 最坏适应算法 。null3. 分区分配操作 1) 分配内存 图 4-6 内存分配流程null2) 回收内存 图 4-7 内存回收时的情况 null4.2.4 可重定位分区分配 1. 动态重定位的引入 图 4-8 紧凑的示意 null2. 动态重定位的实现 图 4-9 动态重定位示意图 null3. 动态重定位分区分配算法 图 4-10 动态分区分配算法流程图 首次适应法首次适应法要求空闲区按首址递增的次序组织空闲区表（队列）。 null分配：当进程申请大小为SIZE的内存时，系统从空闲区表的第一个表目开始查询，直到首次找到等于或大于SIZE的空闲区。从该区中划出大小为SIZE的分区分配给进程，余下的部分仍作为一个空闲区留在空闲区表中，但要修改其首址和大小。 null回收：按释放区的首址，查询空闲区表，若有与释放区相邻的空闲区，则合并到相邻的空闲区中，并修改该区的大小和首址，否则，把释放区作为一个空闲区，将其大小和首址按照首地址大小递增的顺序插入到空闲区表的适当位置。 分析分析注意：每次分配和回收后空闲区表或空闲区队列都要按首址递增的次序排序。 首次适应法的优点： 释放某一存储区时，若与空闲区相邻则合并到相邻空闲分区中去，这种情况并不改变该区在表中的位置，只要修改其大小或首址。 这种算法是尽可能地利用低地址空间，从而保证高地址空间有较大的空闲区。 最佳适应法最佳适应法要求按空闲区大小从小到大的次序组成空闲区表（队列）。 null分配：当进程申请一个存储区时，系统从表头开始查找，当找到第一个满足要求的空闲区时，停止查找，并且这个空闲区是最佳的空闲区。 所谓最佳即选中的空闲区是满足要求的最小空闲区。null回收：按释放区的首址，查询空闲区表（队列） ，若有与释放区相邻的空闲区，则合并到相邻的空闲区中，并修改该区的大小和首址，否则，把释放区作为一个空闲区插入空闲区表（队列） 。 分配和回收后要对空闲区表（队列）重新排序。分析分析优点： 在系统中若存在一个与申请分区大小相等的空闲区，必定会被选中，而首次适应法则不一定。 若系统中不存在与申请分区大小相等的空闲区，则选中的空闲区是满足要求的最小空闲区，而不致于毁掉较大的空闲区。 缺点： 空闲区的大小一般与申请分区大小不相等，因此将其一分为二，留下来的空闲区一般情况下是很小的，以致无法使用。随着时间的推移，系统中的小空闲区会越来越多，从而造成存储区的大量浪费。 最坏适应法最坏适应法要求空闲区按大小递减的顺序组织空闲区表（或队列）。 null分配：进程申请一个大小为SIZE的存储区时，总是检查空闲区表的第一个空闲区的大小是否大于或等于SIZE。若空闲区小于SIZE，则分配失败；否则从空闲区中分配SIZE的存储区给用户，然后修改和调整空闲区表。null回收：按释放区的首址，查询空闲区表（队列） ，若有与释放区相邻的空闲区，则合并到相邻的空闲区中，并修改该区的大小和首址，否则，把释放区作为一个空闲区插入空闲区表（队列） 。 分配和回收后要对空闲区表（队列）重新排序。分析分析最坏适应法看起来公似乎有些荒唐，但在更加严密地考察后，还是有它的优点： 当程序装入内存中最大的空闲区后，剩下的空闲区还可能相当大，还能装下较大的程序。 另一方面每次仅作一次查询工作。 三种策略比较三种策略比较上述三种放置策略各有利弊，到底哪种最好不能一概而论，而应针对具体作业序列来分析。 对于某一作业序列来说，某种算法能将该作业序列中所有作业安置完毕，那么我们说该算法对这一作业序列是合适的。 对于某一算法而言，如它不能立即满足某一要求，而其它算法却可以满足此要求，则这一算法对该作业序列是不合适的。 举例举例例1：有作业序列：作业A要求18K；作业B要求25K，作业C要求30K。系统中空闲区按三种算法组成的空闲区队列 经分析可知：最佳适应法对这个作业序列是合适的，而其它两种对该作业序列是不合适的。练习练习有作业序列：作业A要求21K；作业B要求30K，作业C要求25K。思考思考 用可变分区(动态重定位)方式管理主存时,假定主存中按地址顺序依次有5个空闲区,空闲区的大小依次为32K,10K,5K,228K和100K,现有5个作业A,B,C,D,E.它们各需主存1K,10K,108K,28K和115K.若采用最先适应算法能把这5个作业按顺序全部装入主存吗?你认为怎样的次序装入这5个作业可使主存的利用率最高?null4.2.5 对换(Swapping) 1. 对换的引入 所谓“对换”， 是指把内存中暂时不能运行的进程或者暂时不用的程序和数据，调出到外存上，以便腾出足够的内存空间，再把已具备运行条件的进程或进程所需要的程序和数据，调入内存。对换是提高内存利用率的有效 措施 《全国民用建筑工程设计技术措施》规划•建筑•景观全国民用建筑工程设计技术措施》规划•建筑•景观软件质量保证措施下载工地伤害及预防措施下载关于贯彻落实的具体措施 。 null2. 对换空间的管理 为了能对对换区中的空闲盘块进行管理，在系统中应配置相应的数据结构，以记录外存的使用情况。其形式与内存在动态分区分配方式中所用数据结构相似，即同样可以用空闲分区表或空闲分区链。在空闲分区表中的每个表目中应包含两项， 即对换区的首址及其大小，它们的单位是盘块号和盘块数。 null3. 进程的换出与换入 (1) 进程的换出。 每当一进程由于创建子进程而需要更多的内存空间，但又无足够的内存空间等情况发生时，系统应将某进程换出。 其过程是：系统首先选择处于阻塞状态且优先级最低的进程作为换出进程，然后启动盘块，将该进程的程序和数据传送到磁盘的对换区上。若传送过程未出现错误，便可回收该进程所占用的内存空间，并对该进程的进程控制块做相应的修改。 null (2) 进程的换入。 系统应定时地查看所有进程的状态，从中找出“就绪”状态但已换出的进程，将其中换出时间(换出到磁盘上)最久的进程作为换入进程，将之换入，直至已无可换入的进程或无可换出的进程为止。 null4.3 基本分页存储管理方式 4.3.1 页面与页表 1. 页面 1) 页面和物理块 分页存储管理，是将一个进程的逻辑地址空间分成若干个大小相等的片，称为页面或页，并为各页加以编号，从0开始，如第0页、第1页等。相应地，也把内存空间分成与页面相同大小的若干个存储块，称为(物理)块或页框(frame)， 也同样为它们加以编号，如0＃块、1＃块等等。在为进程分配内存时，以块为单位将进程中的若干个页分别装入到多个可以不相邻接的物理块中。由于进程的最后一页经常装不满一块而形成了不可利用的碎片，称之为“页内碎片”。 null 2) 页面大小 在分页系统中的页面其大小应适中。页面若太小，一方面虽然可使内存碎片减小，从而减少了内存碎片的总空间， 有利于提高内存利用率，但另一方面也会使每个进程占用较多的页面，从而导致进程的页表过长，占用大量内存； 此外，还会降低页面换进换出的效率。然而，如果选择的页面较大，虽然可以减少页表的长度，提高页面换进换出的速度，但却又会使页内碎片增大。因此，页面的大小应选择得适中，且页面大小应是2的幂，通常为512 B~8 KB。 null2. 地址结构 分页地址中的地址结构如下： 3112110 对某特定机器，其地址结构是一定的。若给定一个逻辑地址空间中的地址为A，页面的大小为L，则页号P和页内地址d可按下式求得： null3. 页表 图 4-11 页表的作用 null4.3.2 地址变换机构 1. 基本的地址变换机构 图 4-12 分页系统的地址变换机构 null2. 具有快表的地址变换机构 图 4-13 具有快表的地址变换机构 null4.3.3 两级和多级页表 现代的大多数计算机系统，都支持非常大的逻辑地址空间(232~264)。在这样的环境下，页表就变得非常大，要占用相当大的内存空间。例如，对于一个具有32位逻辑地址空间的分页系统，规定页面大小为4 KB即212 B，则在每个进程页表中的页表项可达1兆个之多。又因为每个页表项占用一个字节， 故每个进程仅仅其页表就要占用4 KB的内存空间，而且还要求是连续的。 可以采用这样两个方法来解决这一问题：① 采用离散分配方式来解决难以找到一块连续的大内存空间的问题：② 只将当前需要的部分页表项调入内存， 其余的页表项仍驻留在磁盘上，需要时再调入。 null1. 两级页表(Two-Level Page Table) 逻辑地址结构可描述如下： null图 4-14 两级页表结构 null图 4-15 具有两级页表的地址变换机构 null 2. 多级页表 对于32位的机器，采用两级页表结构是合适的；但对于64位的机器，如果页面大小仍采用4 KB即212 B，那么还剩下52位， 假定仍按物理块的大小(212位)来划分页表，则将余下的42位用于外层页号。此时在外层页表中可能有4096 G个页表项， 要占用16384 GB的连续内存空间。 必须采用多级页表，将外层页表再进行分页，也是将各分页离散地装入到不相邻接的物理块中，再利用第2级的外层页表来映射它们之间的关系。 对于64位的计算机，如果要求它能支持2６４(=1844744 TB)规模的物理存储空间，则即使是采用三级页表结构也是难以办到的；而在当前的实际应用中也无此必要。例例设页长为1K，程序地址字长为16位，用户程序空间和页表如图。 说明说明在执行指令MOV r1，[2500]时，地址转换步骤如下： 取出程序地址字2500送虚地址寄存器VR，然后由硬件分离出页号P和页内地址W，实际上分离出页号和页内地址是一件很简单的事，因为页长为1K，所以页内地址占10位（0-9位），页号占6位（10-15位），所以硬件只要简单地取出VR寄存器中的高6位即为页号，低10 位即为页内地址。 当然我们通过计算可以得到P=2，W=452。 null根据页号P=2，硬件自动查该进程的页表，找到第2页对应的块号为7，将块号送到内存地址寄存器MR的高10位中。 将VR中的W的值452复制到MR的低10位中，从而形成内存地址。系统就以MR中的地址访问内存 硬件能自动分离出页号和页内地址，但我们只能通过计算才能得到。null计算时要注意： 若给出的地址字为16进制，则将其转换为二进制，然后，根据页长及程序地址字的长度，分别取出程序地址字的高几位和低几位就得到页号及页内地址。如页长为2K，程序地址字为16位，则高5位为页号，低11位为页内地址。null若给出的地址字为10进制，则用公式： 程序地址字/页长 商为页号，余数为页内地址。 如程序地址为8457， 页长为4KB，则8457/4096可得：商为2，余数为256。 null例：设虚地址为(357101)8 每一块为128字节128＝27(357101)8＝(011, 101, 111, 00 1, 000, 001)21 6 7 4 1 0 1偏移为(101)8, 页号为(1674)8块号由页表指定，偏移不变null4.4 基本分段存储管理方式 4.4.1 分段存储管理方式的引入 引入分段存储管理方式， 主要是为了满足用户和程序员的下述一系列需要： 1) 方便编程 2) 信息共享 3) 信息保护 4) 动态增长 5) 动态链接 null4.4.2 分段系统的基本原理 1. 分段 分段地址中的地址具有如下结构： 31 16 15 02. 段表 null图 4-16 利用段表实现地址映射 null图 4-17 分段系统的地址变换过程 3. 地址变换机构 null4. 分页和分段的主要区别 (1) 页是信息的物理单位，分页是为实现离散分配方式，以消减内存的外零头， 提高内存的利用率。或者说， 分页仅仅是由于系统管理的需要而不是用户的需要。段则是信息的逻辑单位，它含有一组其意义相对完整的信息。 分段的目的是为了能更好地满足用户的需要。 null (2) 页的大小固定且由系统决定，由系统把逻辑地址划分为页号和页内地址两部分，是由机器硬件实现的，因而在系统中只能有一种大小的页面；而段的长度却不固定， 决定于用户所编写的程序，通常由编译程序在对源程序进行编译时，根据信息的性质来划分。 (3) 分页的作业地址空间是一维的，即单一的线性地址空间，程序员只需利用一个记忆符，即可表示一个地址； 而分段的作业地址空间则是二维的，程序员在标识一个地址时，既需给出段名， 又需给出段内地址。 null4.4.3 信息共享 图 4-18 分页系统中共享editor的示意图null图 4-19 分段系统中共享editor的示意图 null4.4.4 段页式存储管理方式 1. 基本原理 图 4-20 作业地址空间和地址结构 null图 4-21 利用段表和页表实现地址映射 null2. 地址变换过程 图 4-22 段页式系统中的地址变换机构 null例: 段表如下： 回答下列问题： 1．计算该作业访问 [0，432]，[1，10]，[2，500]，[3，400] 时的绝对地址 2． 总结 初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf 段式存储管理的地址转换过程。null4.5 虚拟存储器的基本概念 4.5.1 虚拟存储器的引入 1. 常规存储器管理方式的特征 一次性。 (2) 驻留性。 null2. 局部性原理 早在1968年， Denning.P就曾指出： (1) 程序执行时， 除了少部分的转移和过程调用指令外， 在大多数情况下仍是顺序执行的。 (2) 过程调用将会使程序的执行轨迹由一部分区域转至另一部分区域， 但经研究看出，过程调用的深度在大多数情况下都不超过5。 (3) 程序中存在许多循环结构， 这些虽然只由少数指令构成， 但是它们将多次执行。 (4) 程序中还包括许多对数据结构的处理， 如对数组进行操作， 它们往往都局限于很小的范围内。 null 局限性又表现在下述两个方面： (1) 时间局限性。如果程序中的某条指令一旦执行， 则不久以后该指令可能再次执行；如果某数据被访问过， 则不久以后该数据可能再次被访问。产生时间局限性的典型原因，是由于在程序中存在着大量的循环操作。 (2) 空间局限性。一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也将被访问，即程序在一段时间内所访问的地址，可能集中在一定的范围之内，其典型情况便是程序的顺序执行。 null3. 虚拟存储器定义 所谓虚拟存储器， 是指具有请求调入功能和置换功能， 能从逻辑上对内存容量加以扩充的一种存储器系统。其逻辑容量由内存容量和外存容量之和所决定，其运行速度接近于内存速度，而每位的成本却又接近于外存。可见，虚拟存储技术是一种性能非常优越的存储器管理技术，故被广泛地应用于大、 中、 小型机器和微型机中。  null4.5.2 虚拟存储器的实现方法 1. 分页请求系统 硬件支持。 ① 请求分页的页表机制，它是在纯分页的页表机制上增加若干项而形成的，作为请求分页的数据结构；② 缺页中断机构，即每当用户程序要访问的页面尚未调入内存时 便产生一缺页中断，以请求OS将所缺的页调入内存；③ 地址变换机构， 它同样是在纯分页地址变换机构的基础上发展形成的。 (2) 实现请求分页的软件。null4.5.3 虚拟存储器的特征 多次性  对换性 3. 虚拟性 null4.6 请求分页存储管理方式 4.6.1 请求分页中的硬件支持 1. 页表机制 null2. 缺页中断机构 图 4-23 涉及6次缺页中断的指令 null3. 地址变换机构 图 4-24 请求分页中的地址变换过程 null4.6.2 内存分配策略和分配算法 1. 最小物理块数的确定 是指能保证进程正常运行所需的最小物理块数。当系统为进程分配的物理块数少于此值时，进程将无法运行。进程应获得的最少物理块数与计算机的硬件结构有关，取决于指令的格式、 功能和寻址方式。对于某些简单的机器，若是单地址指令且采用直接寻址方式，则所需的最少物理块数为2。其中，一块是用于存放指令的页面，另一块则是用于存放数据的页面。如果该机器允许间接寻址时，则至少要求有三个物理块。对于某些功能较强的机器， 其指令长度可能是两个或多于两个字节，因而其指令本身有可能跨两个页面，且源地址和目标地址所涉及的区域也都可能跨两个页面。null2. 物理块的分配策略 在请求分页系统中，可采取两种内存分配策略，即固定和可变分配策略。在进行置换时， 也可采取两种策略，即全局置换和局部置换。于是可组合出以下三种适用的策略。 1) 固定分配局部置换(Fixed Allocation, Local Replacement) 2) 可变分配全局置换(Variable Allocation, Global Replacement) 3) 可变分配局部置换(Variable Allocation, Local Replacemen null3. 物理块分配算法 1) 平均分配算法 这是将系统中所有可供分配的物理块，平均分配给各个进程。 例如，当系统中有100个物理块，有5个进程在运行时，每个进程可分得20个物理块。这种方式貌似公平，但实际上是不公平的，因为它未考虑到各进程本身的大小。如有一个进程其大小为200页，只分配给它20个块，这样，它必然会有很高的缺页率；而另一个进程只有10页，却有10个物理块闲置未用。 null 2) 按比例分配算法 这是根据进程的大小按比例分配物理块的算法。如果系统中共有n个进程，每个进程的页面数为Si，则系统中各进程页面数的总和为： 又假定系统中可用的物理块总数为m，则每个进程所能分到的物理块数为bi，将有： b应该取整，它必须大于最小物理块数。 null 3) 考虑优先权的分配算法 在实际应用中，为了照顾到重要的、紧迫的作业能尽快地完成， 应为它分配较多的内存空间。通常采取的方法是把内存中可供分配的所有物理块分成两部分：一部分按比例地分配给各进程；另一部分则根据各进程的优先权，适当地增加其相应份额后，分配给各进程。在有的系统中，如重要的实时控制系统，则可能是完全按优先权来为各进程分配其物理块的。 null4.6.3 调页策略 1. 何时调入页面 预调页策略 2) 请求调页策略 null2. 从何处调入页面 在请求分页系统中的外存分为两部分：用于存放文件的文件区和用于存放对换页面的对换区。通常，由于对换区是采用连续分配方式，而事件是采用离散分配方式，故对换区的磁盘I/O速度比文件区的高。这样，每当发生缺页请求时，系统应从何处将缺页调入内存，可分成如下三种情况： (1) 系统拥有足够的对换区空间，这时可以全部从对换区调入所需页面，以提高调页速度。为此，在进程运行前， 便须将与该进程有关的文件，从文件区拷贝到对换区。 null (2) 系统缺少足够的对换区空间，这时凡是不会被修改的文件，都直接从文件区调入；而当换出这些页面时，由于它们未被修改而不必再将它们换出，以后再调入时，仍从文件区直接调入。但对于那些可能被修改的部分，在将它们换出时，便须调到对换区，以后需要时，再从对换区调入。 (3) UNIX方式。由于与进程有关的文件都放在文件区，故凡是未运行过的页面，都应从文件区调入。而对于曾经运行过但又被换出的页面，由于是被放在对换区，因此在下次调入时，应从对换区调入。由于UNIX系统允许页面共享，因此， 某进程所请求的页面有可能已被其它进程调入内存，此时也就无须再从对换区调入。 null 3. 页面调入过程 每当程序所要访问的页面未在内存时，便向CPU发出一缺页中断，中断处理程序首先保留CPU环境，分析中断原因后， 转入缺页中断处理程序。该程序通过查找页表，得到该页在外存的物理块后， 如果此时内存能容纳新页，则启动磁盘I/O将所缺之页调入内存，然后修改页表。如果内存已满，则须先按照某种置换算法从内存中选出一页准备换出；如果该页未被修改过，可不必将该页写回磁盘；但如果此页已被修改， 则必须将它写回磁盘，然后再把所缺的页调入内存， 并修改页表中的相应表项，置其存在位为“1”，并将此页表项写入快表中。在缺页调入内存后，利用修改后的页表， 去形成所要访问数据的物理地址，再去访问内存数据。 null4.7 页面置换算法 4.7.1 最佳置换算法和先进先出置换算法 1. 最佳(Optimal)置换算法 最佳置换算法是由Belady于1966年提出的一种理论上的算法。 其所选择的被淘汰页面，将是以后永不使用的， 或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。 null 假定系统为某进程分配了三个物理块， 并考虑有以下的页面号引用串： 7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1 进程运行时， 先将7，0，1三个页面装入内存。 以后， 当进程要访问页面2时， 将会产生缺页中断。此时OS根据最佳置换算法， 将选择页面7予以淘汰。 图 4-25 利用最佳页面置换算法时的置换图 null2. 先进先出(FIFO)页面置换算法 图 4-26 利用FIFO置换算法时的置换图 null4.7.2 最近最久未使用(LRU)置换算法 1. LRU(Least Recently Used)置换算法的描述 图 4-27 LRU页面置换算法 null2. LRU置换算法的硬件支持 1) 寄存器 为了记录某进程在内存中各页的使用情况，须为每个在内存中的页面配置一个移位寄存器，可表示为 R=Rn-1Rn-2Rn-3 … R2R1R0 null图 4-28 某进程具有8个页面时的LRU访问情况 null2) 栈 图 4-29 用栈保存当前使用页面时栈的变化情况 null4.7.3 Clock置换算法 1. 简单的Clock置换算法 图 4-30 简单Clock置换算法的流程和示例 null2. 改进型Clock置换算法 由访问位A和修改位M可以组合成下面四种类型的页面： 1类(A=0, M=0): 表示该页最近既未被访问， 又未被修改， 是最佳淘汰页。 2类(A=0, M=1)： 表示该页最近未被访问， 但已被修改， 并不是很好的淘汰页。 3类(A=1, M=0)： 最近已被访问， 但未被修改， 该页有可能再被访问。 4类(A=1, M=1): 最近已被访问且被修改， 该页可能再被访问。 null 其执行过程可分成以下三步： (1) 从指针所指示的当前位置开始， 扫描循环队列， 寻找A=0且M=0的第一类页面， 将所遇到的第一个页面作为所选中的淘汰页。 在第一次扫描期间不改变访问位A。 (2) 如果第一步失败，即查找一周后未遇到第一类页面， 则开始第二轮扫描，寻找A=0且M=1的第二类页面，将所遇到的第一个这类页面作为淘汰页。在第二轮扫描期间，将所有扫描过的页面的访问位都置0。 (3) 如果第二步也失败，亦即未找到第二类页面，则将指针返回到开始的位置，并将所有的访问位复0。 然后重复第一步，如果仍失败，必要时再重复第二步，此时就一定能找到被淘汰的页。 null4.7.4 其它置换算法 最少使用(LFU： Least Frequently Used)置换算法 2. 页面缓冲算法(PBA： Page Buffering Algorithm)  null4.8 请求分段存储管理方式 4.8.1 请求分段中的硬件支持 1. 段表机制 null 在段表项中， 除了段名(号)、 段长、 段在内存中的起始地址外， 还增加了以下诸项： (1) 存取方式。 (2) 访问字段A。 (3) 修改位M。 (4) 存在位P。 (5) 增补位。 (6) 外存始址。 null2. 缺段中断机构 图 4-31 请求分段系统中的中断处理过程null3. 地址变换机构 图 4-32 请求分段系统的地址变换过程null4.8.2 分段的共享与保护 1. 共享段表 图 4-33 共享段表项 null2. 共享段的分配与回收 1) 共享段的分配 在为共享段分配内存时，对第一个请求使用该共享段的进程，由系统为该共享段分配一物理区，再把共享段调入该区，同时将该区的始址填入请求进程的段表的相应项中，还须在共享段表中增加一表项，填写有关数据，把count置为1；之后，当又有其它进程需要调用该共享段时，由于该共享段已被调入内存，故此时无须再为该段分配内存，而只需在调用进程的段表中，增加一表项，填写该共享段的物理地址；在共享段的段表中，填上调用进程的进程名、存取控制等，再执行count∶=count+1操作，以表明有两个进程共享该段。 null 2) 共享段的回收 当共享此段的某进程不再需要该段时，应将该段释放， 包括撤在该进程段表中共享段所对应的表项，以及执行count∶=count-1操作。若结果为0，则须由系统回收该共享段的物理内存，以及取消在共享段表中该段所对应的表项， 表明此时已没有进程使用该段；否则(减1结果不为0)， 则只是取消调用者进程在共享段表中的有关记录。 null3. 分段保护 越界检查 2) 存取控制检查 只读 (2) 只执行 (3) 读/写 3) 环保护机构 一个程序可以访问驻留在相同环或较低特权环中的数据。 一个程序可以调用驻留在相同环或较高特权环中的服务。 null图 4-34 环保护机构