《4第四章存储器管理(1)pptConvertor》由会员分享，可在线阅读，更多相关《4第四章存储器管理(1)pptConvertor（11页珍藏版）》请在金锄头文库上搜索。
1、第四章 存储器管理（1） 张 琦 内容 4.1 存储器的层次结构 4.2 程序的装入和链接 4.3 连续分配方式 4.4 基本分页存储管理方式 4.5 基本分段存储管理方式 4.6 虚拟存储器的基本概念 4.7 请求分页存储管理方式 4.8 页面置换算法 4.9 请求分段存储管理方式 4.1 存 储 器 的 层 次 结 构 4.1.1 多级存储器结构 对于通用计算机而言，存储层次至少应具有三级：最高层为 CPU 寄存器，中间为主存，最 底层是辅存。在较高档的计算机中，还可以根据具体的功能分工细划为寄存器、高速缓存、主存储器、 磁盘缓存、固定磁盘、可移动存储介质等 6 层。 计算机系统存储层次
2、示意 在存储层次中越往上，存储 介质的访问速度越快，价格也 越高，相对存储容量也越小。 CPU 寄存器 主存 辅存 4.1 存 储 器 的 层 次 结 构 一般来说，容量越大的存储介质，访问速度会越慢， 但单位存储的成本越低。反过来说，如果存储介质的访问速度越高，则它的成本也 会越高，例如寄存器。 4.1 存 储 器 的 层 次 结 构 4.1.2 主存储器与寄存器 1主存储器 主存储器(简称内存或主存)用于保存进程运行时的 程序和数据。 由于主存储器的访问速度远低于 CPU 执行指令的 速度，为缓和这一矛盾，在计算机系统中引入了寄存 器和高速缓存。 2. 寄存器 寄存器访问速度最快,用于加速
3、存储器的访问速度， 协调 CPU 工作，但价格却十分昂贵，因此容量不可能 做得很大。 4.1 存 储 器 的 层 次 结 构4.1.3 高速缓存和磁盘缓存 1高速缓存 高速缓存容量大于或远大于寄存器, 访问速度快于主 存储器。将主存中一些经常访问的信息存放在高速缓存 中，减少访问主存储器的次数，可大幅度提高程序执行 速度。 2磁盘缓存 磁盘缓存本身并不是一种实际存在的存储介质，它依 托于固定磁盘，提供对主存储器存储空间的扩充，即利 用主存中的存储空间，来暂存从磁盘中读出(或写入)的 信息。 4.2 程 序 的 装 入 和 链 接 如何将一个用户源程序变为一个可在内存中执行的程 序，通常都要经过
4、以下几个步骤：是要编译，由编译程序(Compiler)将用户源代码编译成若干个目标模块(Object Module)；是链接，由链接程序(Linker)将编译后形成的一组目标模块，以及它们所需要的 库函数链接在一起，形成一个完整的装入模块(Load Module)；最后是装入，由装入程序(Loader)将装入模块装入内存。 编译程序 产生的目 标模块 库 内存 装入模块 4.2 程 序 的 装 入 和 链 接 4.2.1 程序的装入 1. 绝对装入方式(Absolute Loading Mode) 装入程序按照装入模块中的绝对地址将程序和数据 装入内存。 2可重定位装入方式(Relocatio
5、n Loading Mode) 装入模块为相对地址（逻辑地址） ，装入程序按照当 前内存使用的情况，将装入模块装入内存的某个物理地址。 3动态运行时装入方式(Dynamic Run-time Loading) 将装入模块装入内存后，运行时才进行地址变换，又称 为动态重定位。 只适用于单道程序环境。 装入后不能改变，是一种静态重定位。 4.2 程 序 的 装 入 和 链 接 4.2.2 程序的链接 根据链接时间的不同，可把链接分成如下三种：(1) 静态链接事先将所需目标模块链接生成一个完整的装入模块(. exe)运行时直接装入内存。 (2) 装入时动态链接指将用户源程序编译后所得到的一组目标模块
6、，在装入内存时，采用边装入边 链接的链接方式。 (3) 运行时动态链接延迟到运行时，才将当前被调用的目标模块装入，并链接。 4.3 连 续 分 配 方 式 4.3.1 单一连续分配 这是最简单的一种存储管理方式，但只能用于单用户、 单任务的操作系统中。采用这种存储管理方式时，可把内存 分为系统区和用户区两部分。 1划分分区的方法 (1) 分区大小相等，即所有的内存分区大小相等。 (2) 分区大小不等。 4.3.2 固定分区分配 这是最简单的可运行多道程序的存储管理方式。将内存用 户空间划分为若干个固定大小的区域，在每个分区中装入一 道作业，允许几道作业并发运行。 4.3 连 续 分 配 方 式
7、 2内存分配 将内存固定划分为相等或不等的区域，称为分区， 分区一旦划定，在执行过程中分区长度和个数将不再变 化。建立内存分配表记录分区分配的情况。 简单、可靠，但产生分区“内零头” ，内存利用效低。区号/键大小起址状态18 KB512K已分配232 KB520K已分配332 KB552K未分配4 128 KB584K未分配5 512 KB712K已分配4.3 连 续 分 配 方 式 4.3.3 动态分区分配 动态分区分配是根据进程的实际需要，动态地为之分 配内存空间。 1分区分配中的数据结构 用来描述空闲分区和已分配分区的情况，为分配提供证 据。常用的数据结构有以下两种形式： 空闲分区表在系
8、统中设置一张空闲分区表，用于记录每个空闲 分区的情况。 (2) 空闲分区链 为了实现对空闲分区的分配和链接，设置前向指针和后 向指针，将所有的空闲分区链接成一个双向链。 4.3 连 续 分 配 方 式 空闲链结构 在每个分区的起始部分，设 置一些用于控制分区分配的信 息，以及用于链接各分区所用 的前向指针；在分区尾部则设 置一后向指针，通过前、后向 链接指针，可将所有的空闲分 区链接成一个双向链。当分区被分配出去以后，把 状态位由“0”改为“1” ，此时， 前、后向指针已无意义。 4.3 连 续 分 配 方 式 Job1 Job2 Job3 Job4 Job5 Job6Job6 4.3 连 续
9、 分 配 方 式 2分区分配算法 1) 首次适应算法(first fit) FF 算法要求空闲分区链以地址递增的次序链接。在分配内存 时，从链首开始顺序查找，直至找到一个大小能满足要求的空闲 分区为止；然后再按照作业的大小，从该分区中划出一块内存空 间分配给请求者，余下的空闲分区仍留在空闲链中。该算法的优缺点：为大作业分配大的内存空间创造了条件。 低址部分不断被划分，会留下许多难以利用的、很小的空闲 分区。 当一个新作业装入内存时，须按照一定的分配算法，从 空闲分区表或空闲分区链中选出一分区分配给该作业。目前常用的有以下五种分配算法： 4.3 连 续 分 配 方 式 2) 循环首次适应算法(n
10、ext fit) 将所有的空闲分区构成一个循环链表。采用循环查找 方式，设置一个起始查寻指针，用于指示下一次起始查 寻的空闲分区。该算法的优缺点：能使内存中的空闲分区分布得更均 匀，从而减少了查找空闲分区时的开销，但这样会缺乏 大的空闲分区。 在为进程分配内存时，不再是每次都从链首开始查找， 而是从上次找到空闲分区的下一个空闲分区开始查找，直 到找到一个能满足要求的空闲分区。 4.3 连 续 分 配 方 式 3) 最佳适应算法(best fit) 该算法要求将所有的空闲分区按其容量以从小到大的顺 序形成一空闲分区链。该算法的优缺点：为大作业分配大的内存空间创造了条 件。每次分配后所切割下来的剩
11、余部分总是最小的，这样， 在存储器中会留下许多难以利用的小空闲区。 “最佳”是指每次为作业分配内存时，总是把能满足要求、 又是最小的空闲分区分配给作业，避免“大材小用” 。 4.3 连 续 分 配 方 式 4) 最坏适应算法(worst fit)该算法要扫描整个空闲分区表或链表，总是挑选一个最大的空闲区分割给作业使用，其 优点是可使剩下的空闲区不至于太小，产生碎片的几率最小，但查找效率很高。该算法要求将所有的空闲分区按其容量以从大到小的顺序形成一空闲分区链，查找时只 要看第一个分区能否满足作业要求。该算法的缺点是它会使存储器中缺乏大的空闲分区。最坏适应算法与前面所述的首次适应算法、循环首次适应
12、算法、最佳适应算法一起，也称为顺序搜索法。 4.3 连 续 分 配 方 式 5) 快速适应算法(quick fit) 该算法又称为分类搜索法，是将空闲分区根据其容量大 小进行分类，对于每一类具有相同容量的所有空闲分区， 单独设立一个空闲分区链表，这样，系统中存在多个空闲 分区链表，同时在内存中设立一张管理索引表。 该算法的优点是查找效率高，仅需要根据进程的长度， 找到能容纳它的最小空闲区链表即可；另外不会对任何分 区产生分割，满足对大空间的需求，不会产生内存碎片。缺点是在分区归还主存时算法复杂，系统开销较大。 首次适应算法 循环首次适应算法 最佳适应算法 最坏适应算法 快速适应算法 要求空闲分
13、区链以容量从小到大递增的次序链接； 第一次找到的能满足要求的空闲区，必然是最佳的； 在存储器中会留下许多难以利用的小空闲区。 要求空闲分区链以容量从大到小次序链接； 查看第一个能满足要求的分区。 在存储器中会缺乏大的空闲分区。 根据容量大小进行分类； 对于每一类具有相同容量的空闲分区，设立一个空闲分区链表。 查找效率高，但归还算法复杂。 4.3 连 续 分 配 方 式 要求空闲分区链以地址递增的次序链接； 从低地址端开始查找空闲分区，会在低地址端留下许多难以利用的、小的空闲分区； 会增加查找可用空闲分区时的开销。 仍要求空闲分区链以地址递增的次序链接； 从上一次找到的空闲分区的下一个空闲分区开始查找，为此需增设一个起始查寻指针； 使得内存中的空闲分区分布得比较均匀，但会缺乏大的空闲分区。 4.3 连 续 分 配 方 式 3分区分配操作 1) 分配内存 系统应利用某种分配算法，从空闲分区链(表)中找到所 需大小的分区。 2) 回收内存 当进程运行完毕释放内存时，系统根据回收区的首址，从 空闲区链(表)中找到相应的插入点，此时可能出现以下四种 情况之一： 设请求的分区为 u.size，表中每个空闲分区的大小可表示 为 m.size。4.3 连 续 分 配 方 式 内存分配流程 比较每个空闲 分区与请求分 区的大小 Size 是事先规 定的不再切割 的剩余分区的 大小 4.3 连
