存储器管理

《存储器管理》由会员分享，可在线阅读，更多相关《存储器管理（142页珍藏版）》请在金锄头文库上搜索。

1、第四章 存储器管理 4.1 程序的装入和链接 4.2 连续分配方式 4.3 基本分页存储管理方式 4.4 基本分段存储管理方式 4.5 虚拟存储器的基本概念 4.6 请求分页存储管理方式 4.7 页面置换算法 4.8 请求分段存储管理方式 4.1 程序的装入和链接 图 4-1 对用户程序的处理步骤 地址空间一个目标程序所限定的地址范围。 逻辑地址（相对地址）程序用来访问信息 所用的一系列的地址单元。 物理地址（绝对地址）主存中一系列存储物理单元。 地址空间是逻辑地址的集合。存储空间是物理地址的集合。一个是虚的概念，一个是实的物体。4.1.1 程序的装入1. 绝对装入方式(Absolute Lo

2、ading Mode) 绝对装入程序按照装入模块中的地址，将程序和数据装入内存。装入模块被装入内存后，由于程序中的逻辑地址和实际内存地址完全相同，故不需要对程序和数据的地址进行修改。2. 可重定位装入方式(Relocation Loading Mode) 图 4-2 作业装入内存时的情况 3. 动态运行时装入方式(Denamle Run-time Loading) 动态运行时的装入程序，在把装入模块装入内存后，并不立即把装入模块中的相对地址转换为绝对地址，而是把这种地址转换推迟到程序真正要执行时才进行。因此， 装入内存后的所有地址都仍是相对地址。 4.1.2 程序的链接 1. 静态链接方式(S

3、tatic Linking) 图 4-3 程序链接示意图 在将这几个目标模块装配成一个装入模块时，须解决以下两个问题： (1) 对相对地址进行修改。 (2) 变换外部调用符号。 2. 装入时动态链接(Load time Dynamic Linking) 装入时动态链接方式有以下优点：(1)便于修改和更新。 (2) 便于实现对目标模块的共享。 3. 运行时动态链接(Run-time Dynamic Linking) 加快程序的装入过程，可节省大量的内存空间。4.3 连续分配方式4.3.1 单一连续分配 只用于单用户、单任务的操作系统中。采用这种存储管理方式时，可把内存分为系统区和用户区两部分，系

4、统区仅提供给OS使用，通常是放在内存的低址部分；用户区是指除系统区以外的全部内存空间， 提供给用户使用。 4.3.2 固定分区分配 固定分区式分配是将内存用户空间划分为若干个固定大小的区域，在每个分区中只装入一道作业。它是一种最简单的可运行多道程序的存储管理方式。优点：易于实现，开销小。缺点：内碎片造成浪费；分区总数固定，限制了并发执行的程序数目。1. 划分分区的方法 (1)分区大小相等。(2)分区大小不等。 2. 内存分配 图 4-4 固定分区使用表 4.3.3 动态分区分配 1. 分区分配中的数据结构 (1) 空闲分区表。(2) 空闲分区链。 图 4-5 空闲链结构 2. 分区分配算法 (

5、1)首次适应算法FF空闲区链：首址递增排列；申请：按分区的先后次序，从头查找，找到符合 要求的第一个分区；优点：尽量使用低地址空间，高地址空间保持大的空闲区域。缺点：随着低地址分区不断划分而产生较多小分区（内存碎片），每次分配时查找时间开销会增大。(2) 循环首次适应算法空闲区链：首址递增排列；申请：从上次分配的分区起查找（到最后分区时再回到开头），找到符合要求的第一个分区，应设置一个查询指针。特点：空闲分区分布均匀；大的空闲分区不易保留；查找时间开销会减小。(3) 最佳适应算法空闲区链：分区容量递增排列；申请：找到符合要求的第一个分区。特点：碎片较小，但从整体来看，会形成较多的碎片。(4)

6、最差适应算法空闲区链：分区容量递减排列；申请：找到符合要求的第一个分区。特点：大的空闲分区不易保留。3. 分区分配操作 1) 分配内存 图 4-6 内存分配流程2) 回收内存 图 4-7 内存回收时的情况 系统回收分区的主要步骤：1 检查回收分 区是否与空闲区邻接，如邻接则加以合并 ；2 修改说明表 释放区邻接的分区情况可能是：释放区 邻接的是另一进程的已分配区，或者是空 闲区。 下面以首次适应法说明了系统回收该进 程占用区存在的四种可能情况。设进程的 释放区为R，与R相邻的两个空闲区分别为 F1和F2。R的首地址送LOC，R的尾地址送 LOC1，R的大小送SIZE。(a)若释放区R与F1相邻

7、接，即其低地址部分邻接一 空闲区。将R与F1合并，合并后的空闲区仍记为F1 。空闲区 F1 进程 R低地址 高地址占用区2低地址 高地址占用区2空闲区 F1(a)合并后 如何判断释放区R 是否与某个空闲区相 邻呢？只要从链首开始查找即可：若F1的 首地址+F1的大小=R的首地址，说明R与F1 相邻接。只要修改F1的大小= F1的大小 +LOC，其它参数不变, 在链中的位置不变 。 (b)若释放区R与F2相邻接，即其高地 址部分邻接一空闲区。将R与F2合并，合 并后的空闲区记仍记为F2。 判断释放区R 是否与F2空闲区相邻 ，只要从链首开始查找。若LOC+SIZE=F2的首地址，说明R与F2相邻

8、接 。需修改F2的首地址=LOC，F2的大小= F2+SIZE。占用区1进程R空闲区F2空闲区F2占用区1低地址 高地址低地址 高地址(b)合并后 (c) 若释放区R的高、低地址部分都邻接 一个空闲区。应将三个分区合并为一个大 空闲区，并记为F1。 先将R与F2合并，记 为F2。再将F 2与F1合并，并将F2从链中 删除。 (d)若释放区R上下都不邻接空闲区，将 其插入空闲区链的适当位置即可。 空闲区F1 释放区R空闲区F2空闲区F1合并后某系统采用动态分区分配方式管理内存, 内存空间为640K,高端40K用来存放操作系统。 在内存分配时，系统优先使用空闲区低端的空 间。对下列请求序列：作业1

9、申请130K、作业2 申请60K、作业3申请100K、作业2释放60K、作 业4申请200K、作业3释放100K、作业1释放 130K、作业5申请140K、作业6申请60K、作业7 申请50K、作业6释放60K，请分别画图表示出 使用首次适应算法和最佳适应算法进行内存分 配和回收后内存的实际使用情况。4.3.4 可重定位分区分配 1. 动态重定位的引入 图 4-8 紧凑的示意 2. 动态重定位的实现 图 4-9 动态重定位示意图 3. 动态重定位分区分配算法 图 4-10 动态分区分配算法流程图 4.3.5 对换(Swapping) 1. 对换的引入 在多道程序环境下，可以将暂时不能执行的程序

10、送到外存中，从而获得空闲内存空间来装入新程序。所谓“对换”， 是指把内存中暂时不能运行的进程或者暂时不用的程序和数据，调出到外存上，以便腾出足够的内存空间，再把已具备运行条件的进程或进程所需要的程序和数据，调入内存。对换是提高内存利用率的有效措施。 交换的基本单位为整个进程的地址空间。覆盖的基本单位为一个程序的几个代码段或数据段。优点：增加并发运行的程序数目，并且给用户提供适当的响应时间；编写程序时不影响程序结构。缺点：对换入和换出的控制增加处理机开销；2. 对换空间的管理把外存分为文件区和对换区。对换区用来存放从内存换出的进程。主要目标是提高进程换入和换出的速度。为了能对对换区中的空闲盘块进

11、行管理，在系统中应配置相应的数据结构，以记录外存的使用情况。其形式与内存在动态分区分配方式中所用数据结构相似，即同样可以用空闲分区表或空闲分区链。在空闲分区表中的每个表目中应包含两项， 即对换区的首址及其大小，它们的单位是盘块号和盘块数。 3. 进程的换出与换入 (1) 进程的换出。 每当一进程由于创建子进程而需要更多的内存空间，但又无足够的内存空间等情况发生时，系统应将某进程换出。 其过程是：系统首先选择处于阻塞状态且优先级最低的进程作为换出进程，然后启动盘块，将该进程的程序和数据传送到磁盘的对换区上。若传送过程未出现错误，便可回收该进程所占用的内存空间，并对该进程的进程控制块做相应的修改。

12、 (2) 进程的换入。 系统应定时地查看所有进程的状态，从中找出“就绪”状态但已换出的进程，将其中换出时间(换出到磁盘上)最久的进程作为换入进程，将之换入，直至已无可换入的进程或无可换出的进程为止。 覆盖覆盖与交换是解决大作业 与小主存矛盾的两种存贮管理技 术，它们实质上是对主存进行了 逻辑扩充。 一、 覆盖(overlay) 所谓覆盖，是指同一主存区可以被不 同的程序段重复使用。通常一个作业由若 干个功能上相互独立的程序段组成，作业 在一次运行时，也只用到其中的几段，利 用这样一个事实，我们就可以让那些不会 同时执行的程序段共用同一个主存区。因 此，我们把可以相互覆盖的程序段叫做覆 盖。而把

13、可共享的主存区叫做覆盖区。 为此，我们把程序执行时并不要求 同时装入主存的覆盖组成一组，叫 覆盖段，并分配同一个主存区。 这样，覆盖段与覆盖区一一对立。 覆盖的基本原理可用图4.13例子说明 。作业J由六段组成。图中的(a)给出 了各段之间的逻辑调用关系。 为了实现覆盖管理，系统必须提供相应 的覆盖管理控制程序。当作业装入运行时 ，由系统根据用户提供的覆盖结构进行覆 盖处理。当程序中引用当前尚未装入覆盖 区的覆盖中的例程时，则调用覆盖管理控 制程序，请求将所需的覆盖装入覆盖区中 ，系统响应请求，并自动将所需覆盖装入 主存覆盖区中。 例如，设某进程的程序正文段由A，B，C，D ，E和F等6个程序

14、段组成。它们之间的调用关 系如图5.13(a)所示，程序段A调用程序段B和C ，程序段B又调用程序段F,程序段C调用程序 段D和E。 由图5.13(a)可以看出，程序段B不会调用C， 程序段C也不会调用B。因此，程序段B和C无 需同时驻留在内存，它们可以共享同一内存区 。同理，程序段D、E、F也可共享同一内存区 。其覆盖结构如图5.13(b)所示。覆盖示例在图5.13(b)中,整个程序正文段被分为两个部分。一 个是常驻内存部分，该部分与所有的被调用程序段有 关，因而不能被覆盖。这一部分称为根程序。图 5.13(b)中，程序段A是根程序。另一部分是覆盖部分 ，图中被分为两个覆盖区。其中，一个覆盖

15、区由程序 段B，C共享。其大小为B，C中所要求容量大者。另 一个覆盖区为程序段F，D，E共享。两个覆盖区的大 小分别为50 K与40 K。这样，虽然该进程正文段所要 求的内存空间是 A(20K)+B(50K)+F(30K)+C(30K)+D(20K)+E(40K)=1 90K，但由于采用了覆盖技术，只需110 K的内存空 间即可开始执行。覆盖技术的关键是提供正确的覆 盖结构。通常，一个作业的覆盖结构要求编程 人员事先给出。对于一个规模较大或比较复杂的 程序来说是难以分析和建立它的覆盖结构的。因 此，通常覆盖技术主要用于系统程序的主存管理 上。例如，磁盘操作系统分为两部分，一部分是 操作系统中经常用到的基本部分，它们常驻主存 且占有固定区域。 另一部分是不经常用的部分，它们 放在磁盘上，当调用时才被装入主存 覆盖区中运行。 覆盖技术的主要特点是打破了必须 将一个作业的全部信息装入主存后才 能运行的限制。在一定程度上解决了 小主存运行大作业的矛盾。1、设基址寄存器内容为1000，在采用 动态重定位的系统中，当执行指令 “LOAD A，2000”时，操作数的实际地 址是（ ）A 1000 B 2000 C 3000 D 4000答案：C2、在可变式分区存储管理中的拼接技 术可以（ ）。A 集中空闲区 B 增加主存容量C 缩短访问周期 D 加速地址