计算机操作系统第四章-存储器管理要点

1、第四章存储器管理第0节存储管理概述一、存储器的层次结构 1、在现代计算机系统中，存储器是信息处理的 来源与归宿，占据重要 位置。但是，在现有技术条件下，任何一种存储装置，都无法从速度、 容量、是否需要电源维持等多方面，同时满足用户的需求。实际上它 们组成了一个速度由快到慢，容量由小到大的存储装置层次。图41计算机系统存储层次示意2、各种存储器?寄存器、高速缓存Cache：少量的、非常快速、昂贵、需要电源维 持、CPU可直接访问；?内存RAM :若干（千）兆字节、中等速度、中等价格、需要电源维持、 CPU可直接访问；?磁盘高速缓存：存在于主存中；?磁盘：数千兆或数万兆字节、低速、价廉、不需要电源

2、维持、CPU 不可直接访问；由操作系统协调这些存储器的使用。、存储管理的目的 1、尽可能地方便用户； 提高主存储器的使用效率， 使主存储器在成本、 速度和规模之间获得较好的权衡。 （注意 cpu 和主存储器，这两类资源 管理的区别 ）2、存储管理的主要功能：? 地址重定位? 主存空间的分配与回收? 主存空间的保护和共享? 主存空间的扩充三、逻辑地址与物理地址1、逻辑地址 （相对地址，虚地址）：用户源程序经过编译 /汇编、链接后， 程序内每条指令、每个数据等信息，都会生成自己的地址。一个用户程序的所有逻辑地址组成这个程序的逻辑地址空间（也称地址空间 ）。这个空间是 以 0 为基址、线性或多维编址

3、的。 2、物理地址 （绝对地址，实地址 ）：是一个实际内存单元 （字节 ）的地址。计算机内所有内存单元的物理地址组成 系统的物理地址空间， 它是 从 0 开始的、是一维的；将用户程序被装进内存， 一个程序所占有的所有内存单元的物理地 址组成该 程序的 物理地址空间 （也称存储空间 ）。四、地址映射 （变换、重定位 ） 当程序被装进内存时，通常每个信息的逻辑地址和它的物理地址 是不一致的，需要把逻辑地址转换为对应的物理地址 地址映射 ；地址映射分静态和动态两种方式。1、静态地址重定位是程序装入时集中一次进行的地址变换计算。物理地址 二重定位的首地址 +逻辑地址?优点：简单，不需要硬件支持；?缺点

4、：一个作业必须占据 连续的存储空间；装入内存的作业一般不 再移动；不能实现虚拟存储。2、动态地址重定位：在程序执行的过程中，每当 Cpu 访问一个内存地址之前对要访问 的地址进行地址变换计算。? 优点：一个作业可以使用 非连续 存储空间；能实现虚拟存储；有利 于程序段的共享。? 缺点：需要硬件支持。五、存储分配与回收在程序运行开始时、运行过程中， OS 根据一定的存储管理方法， 在内存中为程序及其数据找到合适的位置，将它们装入内存；程序运行结束后， OS 收回程序释放的内存资源，并进行适当的整 理，以便再分配给其他的程序使用。六、存储保护 为多道并发程序共享内存提供保障，使在内存中的各道程序“

5、 各 行其道 ”，只能访问属于自己的区域 （自己的物理地址空间 ），避免各道 程序间相互干扰，特别是当一道程序发生错误时，不致于影响其他程 序的运行。通常由硬件完成保护功能，由软件辅助实现。 存储保护可以实现：? 保护系统程序区不被用户侵犯 （ 有意或无意的 ） ；? 不允许用户程序读写不属于自己地址空间的数据 （ 系统区地址空间、 其他用户程序的地址空间 ）。存储保护的过程： 每个进程都有自己独立的进程空间。 如果 一个进程在运行时所产 生的要访问的地址在其地址空间之外，称为发生了 地址越界 。每当程序要访问某个内存单元时，由硬件检查是否允许，如果允许则执行， 否则产生地址越界 中断 ，由操

6、作系统进行相应处理。七、存储共享? 内存共享：多道环境中，两个或多个并发进程共用内存中 相同区域 。 ? 目的：节省内存空间，提高内存利用率，实现进程通信 ( 数据共享 )。 ? 共享内容：代码共享 (要求代码为纯代码 )；数据共享。八、存储“扩充”为了给大作业提供方便， 由 OS 把内存和外存统一管理起来， 实现 自动覆盖。当一个大作业在执行时，有一部分逻辑地址空间的内容在 内存，另一部分在外存。当要访问的信息不在内存时，由OS(而不是程序员安排的 I/O 指令)自动把它们从外存调入内存。从效果上看，这样 的OS好象为这个用户作业提供了一个容量比实际内存大的存储器，从 而实现了存储“扩充”。

7、扩充后的存储器称为虚拟存储器。九、存储管理方法1、连续分配方式(1) 单一连续存储区管理 (单道环境下 )(2) 分区式存储管理2、离散分配方式(1) 分页式存储管理(2) 分段式存储管理（3）段页式存储管理3、实现虚拟存储的分配方式主要是一些请求式的分配方式，如请求分页式存储管理、请求分 段式存储管理等。对于以上每一种存储管理方法我们应该掌握：? 基本原理（思想方法）? 存储管理使用的数据结构? 逻辑地址的格式? 地址变换的方式? 存储的分配和回收过程? 特点（优、缺点） 第一节程序的装入（和链接）一、程序的装入就是OS的装入程序（Loader）将用户程序的装入模块装入内存。内存1*AA4链

8、接 程序装入模块A装入 程序4+1 i iiii i1 i1 i111S1111111J kJ库第一步第二步第三步编译程序 产生的目W 标模块图对用户程序的处理步骤1、绝对装入方式编译时产生绝对地址的目标代码。程序被装入内存后，逻辑地址与实际装入的内存地址完全相同 ，故执行过程中， 不需 对指令和数据 进行地址变换。程序中所使用的绝对地址，可在编译或汇编时给出，也可由程序 员直接赋予。 但在由程序员直接给出绝对地址时，不仅要求程序员熟 悉内存的使用情况，而且一旦程序或数据被修改后，可能要改变程序 中的所有地址。因此，通常是宁可在程序中采用符号地址，然后在编 译或汇编时，再将这些符号地址转换为绝

9、对地址。2、可重定位装入方式编译时产生相对地址的目标代码。程序被 装入内存时 ，进行地址 变换，然后在访问时直接取指令和数据。3、动态运行时装入方式编译时产生相对地址的目标代码。程序被装入内存后，并不立即把 装入模块中的相对地址转换为绝对地址，而是把这种地址转换推迟到 程序真正要执行时才进行。当要对一条指令或一个数据进行 访问时 ， 才对它的地址进行转换。因此，装入内存后的所有地址都仍是相对地 址。第二节 连续分配存储管理方式一、单一连续分配1、基本原理把内存分为系统区和用户区两部分，系统区提供给 OS 使用 （通常 是内存的低址部分 ）；用户区 （指除系统区以外的全部内存空间 ） 提供给用户

10、使用。用户区是一个连续的存储区，每次装入一道用户作业，整个系统的用户空间被一道用户作业独占用户程序于RAM中的嫌作换统ROM中的设备驱动程庁用户程序位于RAM屮的操作系统川户程序R J-RAXII1!操作系统单一连续区存储分配示意图2、存储分配和回收过程如下图所示的主存分配与回收法。并且由装入程序进行静态地址重定位，检查其绝对地址是否超越，即可达到保护系统的目的。工作 流程:入口HU-*本好法聞装入该作业一亠Yes凋业3、特点： ? 存储管理简单，只适用于 单道环境? 内存利用率很低? 程序的运行受主存容量限制? 基本不需要管理的数据结构二、固定分区分配固定分区式存储管理是满足 多道程序 的最

11、简单的存储管理方案。 它的基本思想是：将内存的用户区划分成若干个 固定 的空间，称为分 区。当程序到达时，由系统给它分配一个适当大小的分区，将程序和 数据连续存入，使进程得以并发执行。每个分区只能存储一个程序，而且程序也只能在它所驻留的分区 中运行；作业的逻辑地址空间是线性的，物理地址空间是连续的；主 要采用静态地址重定位方式进行地址变换。1、基本原理 系统生成时，把可分配的主存储器空间分割成若干个区域，每个 区域称为一个分区 （每个分区的内部是连续的 ）。每个分区的大小可以相 同也可以不同，但 分区大小固定不变 ，每个分区能装一个且只能装一 个作业。 P27-282、管理使用的数据结构 分区

12、说明表：记录系统中的现有内存 分区及其使用状态。分区号大小ZKB起址ZKB状态11220已分配23232已分配36464己分配斗128128未分配(a)分区说明表(b)存储空间分配情况3、存储分配与回收过程当有一个用户作业要装入时，由OS检索分区说明表，从中找一个 大小能满足要求的、空闲的分区，将用户作业装入，并在分区说明表 中将该分区的状态置为“已分配”；若没有找到大小足够的分区，则拒 绝为该程序分配内存。当一个用户作业完成后，由OS将其占有的分区收回，将该分区的 状态改为“未分配”。4、特点?可以支持多道程序运行?程序的运行受主存容量和分区大小限制?内存利用率仍很低三、动态分区分配1、基本

13、思想系统在启动时，除了 OS常驻内存部分占用的内存空间外，系统中 只有一个空闲分区；当有作业要装入内存时，检索空闲分区表，找一个能满足作业要求的空闲分区，从中 划出一个大小正好满足要装入作业要求的存储区，分配给这一作业， 剩下的部分被作为一个新的空闲分区记录在空闲分区表中 2、存储管理的数据结构(二选一)(1) 空闲区表-记录目前系统中每个空闲区的起始地址和长度;0K15K38K48K68KSOK110K120K始址长度标志15K23K未分配48K20K未分配80K30K未分配空空空闲区表始址长度标志0K15KJ138K10KJ268K12KJ3110K10KJ4空空已分配区表分区分配表 空闲

14、分区链-将目前系统中的空闲分区按一定的顺序链接起来。在 每个分区的头、尾设置指向前后分区的指针，并记录本分区的一些分 配控制信息。系统设立一个链首指针，指向第一个空闲块。扌旨Z个丰节口丁用FrJ 扌旨1STZ+工2O图4-5空闲琏结构3、存储分配与回收过程（1）分配6内存分配流程从头开始查表检索完否？継续检索下一个表项m.stze u.siziize?从该分区中划出 u-size大小的分区将该分区从诜中移出将该分区分配给请求者修改有关数据结构（2）回收-会出现四种情况(&)图4-7内存回收时的情况? 回收区与它前面的一个空闲区相邻 (a)? 回收区与它后面的一个空闲区相邻 (b)? 回收区与它

15、前、后的两个空闲区相邻 (c)? 回收区前后都没有相邻的空闲区 当某一块归还后，要根据不同的情况，前后空间合并，再分别 处 理存储管理的数据结构 。4、存储分配的算法 空闲分区表或空闲分区链中分区排列顺序的组织 方法(1) 首次适应算法：按空闲区首 地址从低到高来组织空闲分区表或空闲 分区链；每次分区时，总是从表头或链首开始扫描，找到第一个足够 大的空白区分配。(2) 循环首次适应算法 (下次适应算法 )：类似首次适应法的数据组织。 每次分区时，总是从上次查找结束的地方开始扫描，找到一个足够大 的空白区分配，并循环查找。(3) 最佳适应算法：按空闲区 容量大小从小到大来组织组织空闲分区表 或空

16、闲分区链。每次分区时，总是从表头或链首开始扫描。所以，接 到内存申请时，会在空闲区中找到一个满足要求的最小空闲区进行分 配。(4) 最坏适应算法：与最佳适应法相反，它在作业选择存储块时，总是 寻找一个满足要求的最大的空闲分区。讨论以上算法的优缺点.6、动态分区方式中的“碎片”问题经过一段时间的分配回收后，内存中会出现很多很小的空闲块。 它们每一块都较小，不足以满足一般作业的分配要求；但其容量总和 却有着相当的规模。这些空闲块被称为 碎片。碎片的存在造成了存储 资源的浪费。解决办法：碎片整理，通过在内存移动程序，将所有小的空闲区 域合并为大的空闲区域。问题：系统开销大（？）。操作系统操作系统用户

17、程序L用户程序1用户程帛用户程E用户程序5用户程序用户程序514 KB80 KB用户程删3）紧凄前）紧凑后图4-8碎片整理的示意四、可重定位分区1、动态重定位引入的原因在动态分区分配中，“碎片”整理，是定时进行或在存储回收时进 行的，所有用户程序的存储分区都要进行改动，并重新进行静态地址 重定位。这样的“碎片”整理工作将花费较多的系统开销。2、动态重定位分区分配处理流程可重定位分区分配，与动态分区方法基本相同，但它的碎片拼接是在存储分配时进行的，以满足新作业需求为目的，并采用动态地址 重定位图4-10动态重定位分区分配算法流程图五、对换（交换）技术“对换”引入的原因：P58所谓“对换”，是指系

18、统允许在一个作业已经进入内存执行的过程中，仍能把它调出内存、再调入内存。把内存中暂时不能运行的进程 或者暂时不用的程序和数据，调出到外存上，以便腾出足够的内存空 间，再把已具备运行条件的进程或进程所需要的程序和数据，调入内 存。对换是提高内存利用率的有效措施。可以将整个进程换入、换出，也可以将进程的一部分（页、段）换入、 换出。前者主要用于缓解目前系统中内存的不足，后者主要用于实现 虚拟存储。P59对换空间的管理：在具有对换功能的OS中，通常把外存分为文件 区和对换区。前者用于存放文件，后者用于存放从内存换出的进程。P60-61进程的换出： 系统首先选择处于阻塞状态且优先级最低的进程作为换出进

19、程， 然后启动磁盘，将该进程的程序和数据传送到磁盘的 对换区 上。若传 送过程未出现错误，便可回收该进程所占用的内存空间，并对该进程 的 PCB 做相应的 修改 。当目前没有阻塞进程时，也可将优先级低的就绪进程换出。 进程的换入：系统定时查看 所有进程的状态，从中找出“就绪”状态但已换出的 进程，将其中换出时间 （换出到磁盘上 ）最久的进程作为换入进程， 将之 换入，直至已无可换入的进程或无可换出的进程为止。以上谈到的是整体交换，部分交换在虚拟存储中介绍。六、动态分区式存储管理特点的讨论1、作业连续存放 （作业的逻辑地址空间和物理地址空间都是一维的 ） 2、有限的虚拟存储分区式管理不能实现那种

20、用户进程所需空间只受内外存容量之和 限制的虚拟存储，只能使用覆盖和交换等存储扩充技术，实现进程 挂 起，这是一种有限的虚拟存储 并发进程的总容量可以大于内存容量，但每一个进程的容量小于内存。3、存储保护：使用界限寄存器。一般由硬件提供一对寄存器：基址寄 存器：存放起始地址，限长寄存器：存放长度 （或上界寄存器 /下界寄存器）4、主要优缺点：?实现了多进程对内存的共享，支持多道程序设计;?要求较少的硬件支持，管理方法简单，容易实现。?内存利用率仍不高（碎片问题）；?用户作业的大小受分区大小的限制；?不能实现信息的共享。第三节 基本（静态）分页存储管理方式 一、基本原理Ilk12k13k14k15

21、k将系统的物理地址空间划分成大小相同的 片，称为块;将作业的逻辑地址空间划分成和块大小一样的片，称为页（最后不 足一页的也算一页）；给作业进行存储分配时，将作业的一页存入存储器的一块中。逻辑上相邻的页，物理上可以不相邻。块的大小与页的大小一致，与系统内存的大小以及内、外存间数 据的传输速度相关，通常是2nB。二、逻辑地址的格式作业的逻辑地址空间是 一维的，每个逻辑地址由 页号和页内地址 组成，见下图左；对某特定机器，其地址结构是一定的，页的大小固定为L。若给定一个逻辑地址A，则页号P和页内地址d可按下式求得，见下图右页内地址dP = INT Fy-1d = J MOD L三、存储管理的数据结构

22、1、页表:内存用户程序页表图4-11页表的作用012345678910每个进程一张，在初次为进程分配内存时建立进程的页表。一个 进程分为多少页，它的页表就有多少行（表目）。每一行中记录着进程的 一页对应的块。另外，页表的每一个表目还包括一个 存取控制字段。 页表用于进行地址变换。2、存储分块表：整个系统一张，每一项对应一个内存存储块，记录该 存储块的使用状态：已分配或空闲。通常用 位示图来表示存储分块表。031四、地址变换进程的页表一般是常驻内存、连续存放的，页表的首地址和长度 存在进程的PCB中。系统为执行态的用户进程提供了一个页表寄存器，用来存放这个 进程的页表首地址和长度。采用动态地址重

23、定位。1、基本的地址变换过程:页表寄存器越界中断逻辑地址L页表例：0100: LOAD 2452, A(1)指令的逻辑地址0100,它存在0页，第100号单元中；查页表：0页T 10块T 算出指令的物理地址：10100-到内存单元10100 中取指令 LOAD 2452 , ； 目的操作数的逻辑地址2452,它排在2页第452号单元中； 查页表：2页-8块-算出操作数的物理地址：08452-将I送入 08452号内存单元。2、引入快表：由于页表也存放在主存中，这样，每读写一个内存单元，首先必 须读内存一次，访问页表，之后根据形成的实际地址再访问内存，这 样使访问主存的次数加倍，因而使总的处理速

24、度明显下降。为了解决这个问题人们 采用一组寄存器，存放最近访问过的页的 页表表项-引入“快表”每次地址变换时，首先查找快表，若找到所需页的表项，则快速 形成物理地址。否则，再去页表中查找后形成物理地址，同时把该页的表项写入快表。如果设计得当，快表的命中率可以很高頁表寄存器页表始址页表长度页号页内地址逻辑地址页表输入寄存器b快表bd物理地址图4-13具有快表的地址变换机构五、存储的分配和回收1、存储分配?计算一个作业所需要的总块数N?查位示图，看看是否还有 N+1个空闲块，如果不够，就拒绝分配?如果有足够的空闲块，则首先申请一块，为作业建立页表，将页表的首地址和长度N存入进程的PCB中?分配N个

25、空闲块给该作业，依次装入作业的N个页，将页号和对应的块号填入页表?修改位示图2、存储回收进程执行结束，系统对照页表，依次收回分给它的N个块，修改 位示图；撤消它的页表，收回页表所占块， 修改位示图六、两级和多级页表现代的大多数计算机系统，都支持非常大的逻辑地址空间(232264)。页表就变得非常大，超过了 1页可以容纳的范围。可采用两个方法来解决这问题： 米用离散分配方式来解决难以找到一块连续的大内存空间的问题； 只将当前需要的部分页表项调入内存，其 余的页表项仍驻留在磁盘上，需要时再调入。1、两级页表o121 141 15I46S图4-14两级页表结构外层页号外层页内地址页内地址P1Pzd逻

26、辑地址的格式为:3122 2112 110P1d逻辑地址图4-15具有两级页表的地址变换机构2、多级页表字长32位的计算机，进程页表多大？用户逻辑地址空间最大 232=4GB设：页面大小为212=4KB则：一个进程最多220页设：页表的每个表项占4B则：进程页表最长为 4BX 220=210X 212B = 1024页外页表最长1024X 4B=4KB，正好一页。当计算机的字长增加到64位时，如果仍以4KB为一页，一个作 业可以有252页。页表与外页表的长度将是 。此时，必须采用多级页表，将外层页表再进行分页，再将各分页 离散地装入到不相邻接的物理块中，再利用第2级的外层页表来映射它们之间的关

27、系。此即多级页表。七、基本（静态）页式存储管理的特点 1、作业的逻辑地址空间是一维的2、是一种离散分配的存储管理方法， 用户作业 不要求连续的存储空间， 碎片的规模小于 1 页，而且数量很少3、要求进程在执行前全部装入内存，所以进程的大小仍受内存空间的 限制4、“页”是存储的单位，在逻辑上没有意义， 很难实现 信息共享和存 储保护第四节 基本 (静态)分段存储管理方式一、分段式存储管理的引入 在分页式存储管理中：? 进程的逻辑地址空间是连续的。 一个进程 ( 程序与数据 ) 是一个整体；? “页”是一个存储的单位，在逻辑上没有意义，不便进行程序段或 数据段的共享；? 进程所需的存储块是一次性、

28、静态分配的，程序和数据都不能动态 增长。引入分段存储管理方式，主要是为了满足用户和程序员的下述一 系列需要： P84-87(1) 方便编程(2) 信息共享(3) 信息保护(4) 动态增长(5) 动态链接二、基本原理一个 用户作业的程序和数据按其逻辑结构可以 分为若干段 ，每一 段在逻辑上都是完整的， 每段内有从 0开始的、连续的逻辑地址空间。在存储分配时，系统为每一段分配一个 连续 的存储区，而不同段之间的存放的空间可以是不连续的主程序段M了程序段X子程序段Y116N数组A工作区段B三、逻辑地址格式分段式存储管理中，用户作业的逻辑地址空间是二维的（可能不连续），一个单元的逻辑地址格式为:段号段

29、内地址每一个段号和一个逻辑段的名称对应 四、存储管理的数据结构段表：每个进程设置一个，属于进程的现场信息。段表的格式:段号段基址段长度存取控制0a. B a. B1段表中的每一行对应一个逻辑段。作业有几逻辑段，段表的长度就有几行。段表中最重要的信息是它的前三项，依靠它进行地址重定位。030K020K015K010K作业空间(MAIN)=030K40K120K80K15K120Ky10K150KX内存空间段表段号段长基址20K(S)=310K40K80K120K150K图416逻辑地址空间、段表、物理地址空间的关系五、地址变换控制寄存器段表始段表艮度2100有效地址越界段号S位移那段号段长基址0

30、1 K6 K16004 K2*500S K -320092008292 物理地址图4J7分段系统的地址变换过程8K主存82928692进程的段表一般是常驻内存、连续存放的，段表的首地址和长度存在进程的PCB中系统为执行态的用户进程提供了段表寄存器，用来存放这个进程 的段表首地址和长度。段表始址寄存器段表长度寄存器逻辑地址段表段号S 段内地址d地址越界地址越界物理地址地址鷺引入快表的地址映射及存储保护机制六、存储分配与回收在段式存储管理中，内存的 空闲空间，采用类似动态分区式存储 管理的方式组织、分配和回收。只是在这里，存放的对象是进程的一 个逻辑段，而不是整个进程1、存储分配首先，程序开始的若

31、干逻辑段，按照类似动态分区分配的方法被 逐一放入内存程序开始的若干段装入内存并建立段表读需要访问的指令（数据）的逻辑地址地址*换I访问计算段号S和段内地址B段s在内存中吗？段中断在访问之内吗？旦存储保护中断y !置该段的访问位为1（若是写访问，则置保护位为1） 2、存储回收当作业执行完毕时，系统将段表中各行记录的分区，采用类似动 态分区分配的回收方法进行 逐一回收，然后撤消段表，回收段表占用 的分区。七、分页和分段的主要区别1、页是信息的物理（存储）单位，分页是为实现离散分配方式，以消减 内存的零头，提高内存的利用率。或者说，分页仅仅是由于系统管理 的需要而不是用户的需要。 段则是信息的逻辑单位，它含有一组其意 义相对完整的信息。分段的目的是为了能更好地满足用户的需要。2、页的大小固定且由系统决定，由系统把逻辑地址划分为页号和页内地址两部分，是由机器硬件实现的，因而在系统中只能有一种大小的 页面；而段