第四章—A存储的层次结构.ppt

* 主存空间的利用率 提高主存空间利用率的方法: (1)根据经常出现的作业的大小和频率划分分区,尽可能提高各个分区的利用率。 (2)划分分区时按分区大小顺序排列。 (3)按作业对主存空间的需求量排成多个作业队列,规定每个作业队列中的各作业只能依次装入对应的分区中; 分区2 0 a b c d …….. 作业对列1 …….. …….. 作业对列2 作业对列3 OS 分区1 分区3 L1 L2 L3 * 4.3.3 动态分区分配 1.动态分区分配的基本概念 因为固定分区主存利用率不高，使用起来不灵活，所以出现了动态分区的管理技术。 动态分区原则：存储空间的划分是在装作业时进行的。从可用的自由存储空间内，划出一个大小正好等于作业大小的存储区，并分配给这一作业。 OS 进程A 进程B 进程C 进程D OS 进程A 进程B 进程C OS 进程A 进程B OS 进程A 进程 A（8K） 进程 D（124K） 进程 B（16K） 进程 C（64K） … * 1.) 空间的分配和去配 当有作业完成后释放所占用的存储区。 在系统运行的过程中，系统中形成多个空闲的不连续的存储区，称主空闲。 * 采用动态分区存储管理方式管理存储空间时,主存中已占用分区和空闲区的数目和大小都是可变的。为了实现可变分区存储管理,系统必须设置相应的数据结构,用来描述空闲分区和已分配分区的情况,为系统空间分配提供依据。常用的数据结构有以下两种形式: (1)空闲分区表 (2)空闲分区链 * (1)空闲分区表 系统设置空闲分区表和已分配分区表,用来描述空闲分区和已分配分区的情况,为系统空间分配提供依据。 ……. 空 作业E 14KB 140KB 作业C 10KB 105KB 作业F 32KB 55KB 作业A 15KB 40 标志 长度 始址 已分配分区表 …… 空 未分配 102KB 154KB 未分配 25KB 115KB 未分配 18KB 87 标志 长度 始址 空闲分区表 * (2)空闲分区链 为了实现对空闲分区的分配和链接,在每个分区的起始部分设置一些用于控制分区分配的信息以及用于链接前一个分区的前向指针;在分区的尾部则设置一后向指针,通过前、后向链接指针,可以将所有的空闲分区连接成一个双向链。 0 0 N+2 N+2 后向指针 N个字节可用 前向指针 * 2 分区分配算法 分区分配和回收是对空闲区表（或空闲区队列）数据结构进行操作，空闲区表的组织有两种方法： 1、按空闲区大小的升序（降序）组织； 2、按空闲区首地址升序（降序）组织。 根据空闲区表组织的方法的不同，有不同的放置策略，它们是首次适应算法、循环首次适应算法、最佳适应算法、最坏适应算法和快速适应算法。 * A 首次适应分配算法 首次适应分配算法的表是按空闲区首地址升序的（即空闲区表是按空闲区首址从小到大）方法组织的。 * 从该空闲区中截取所需 大小，修改调整可用表 从空闲区表第一 表目顺序查找 从可用表中移去该 表目，调整可用表 取下一表项 无法分配 该 空闲区 长度≥SIZE？ 该 空闲区 长度=SIZE？ 表目查完？ 返回分配起始地址 否 否 否 是 是 是 首次适应分配算法 * 优点： 1.可以在释放分区时很容易合并相邻的空白区，从而形成较大的空白区； 2.尽可能地利用存储器的低地址部分而保留高地址部分。 缺点： 1、搜索次数较大，影响工作效率。 2、低地址部分不断被划分 B 循环首次适应算法 * C 最佳(又称最优)适应分配算法 最佳适应分配算法是将申请者放入与其大小最接近的空闲区中。切割后的空闲区最小，若系统中有与申请区大小相等的空闲区，这种算法肯定能将这种空闲区分配给申请者。（首次适应法则不一定）。 * 最佳适应算法的空闲区表按空闲区容量大小升序方法组织。 分配时，按申请的大小逐个与空闲区大小进行比较，找到一个满足要求的空闲区，就说明它是最适合的（即最佳的）。 优点： 1.如果有一个空白区的容量正好满足要求，则它必被选中； 2.每次都是选择一个容量最接近的空白区，而使较大的空白区保留。 缺点：产生非常小的空白区（碎片） * D 最坏(也称最差)适应分配算法 为了克服最佳适应分配算法把空闲区切割得太小的缺点，人们提出了一种最坏适应分配算法，即每次分配时，总是将最大的空闲区切去一部分分配给请求者，其依据是当一个很大的空闲区被切割了一部分后可能仍是一个较大的空闲区。避免了空闲区越分越小的问题。 * 最坏