操作系统第5章讲存储管理1连续分配讲解.ppt

（3）多道固定划分法的作业调度技术 OS 4kB 6kB 12kB ... 3kB 4kB 1kB 2kB ... 5kB 6kB ... 7kB 10kB 11kB 8kB （1）多队列法 OS 4kB 6kB 12kB ... 7kB 3kB 4kB 5kB （2）单队列法 （4）固定分区法存在碎片问题 内部碎片：内存某存储区间大于其存放作 业空间的部分。如：作业只有3KB时，而某内存固定分区有4KB。有1KB内部碎片。 OS 12KB 固定4KB 3KB 内部碎片 外部碎片：内存某存储区间容不下要运行 的作业时。 如：作业长度为：5KB，8KB，12KB时，若内存固定分区只剩下4KB，则存在外部碎片。 OS 4KB 6KB 12KB 外部碎片 一、管理方法 5.2.3 多道连续可变划分法 特点：多道、连续、但不固定划分内存。 系统设置一个空闲块队列，初始状态时队列中只有一个连续的空闲块。作业到达后，作业有多大就分配多大的空间。作业撤离时，将释放的空间加入空闲队列。 例题1：有以下4个作业，采用多道连续分配技术 作业1-20KB 作业2-40KB 作业3-50KB 作业4-60KB 0 20K 40K 0 50K 60K 0 0 操作系统-50KB 空闲区 0 50K 70K 110K 160K 256K 作业1-20KB 作业2-40KB 作业3-50KB 作业4-60KB 220K 例题2：有以下5个作业，假设任一时间段内，内存中每一作业的运行时间相等，采用FCFS作业调度方法。 作业到来次序 所需存储量 运行时间 J1 60KB 10s J2 100KB 5s J3 30KB 20s J4 70KB 8s J5 50KB 15s OS 0 40K 256K J1 J2 J3 J4 J5 共190K 二、可变分区中的数据结构 常用的数据结构有两种：空闲分区表和空闲分区链。 (1)空闲分区表。为内存中每个尚未分配出去的分区设置一个表项，每个表项包含分区序号、分区起始地址和分区的大小。 例：根据右图的内存使用情况填写空闲分区表。 操作系统 空闲区1(26KB) 已使用 空闲区2(14KB) 已使用 空闲区3(5KB) 已使用 空闲区4(30KB) 已使用 0k 40k 66k 70k 84k 100k 105k 150k 180k 256k 空闲分区表 分区序号 分区起始地址 分区大小 1 40k 26kB 2 70k 14kB 3 100k 5kB 4 150k 30kB … … … (2)空闲分区链。在每个空闲分区中设置用于控制分区分配的信息及用于链接各个分区的指针，将内存中的空闲分区链接成一个链表。不同的分配算法链表的组织方式不同。 三、可变分区分配算法 (一)首次适应(First Fit)算法。 该算法要求空闲分区以地址递增的次序排序。 如果采用的是链表结构，分配时则从链表的开始顺序进行查找，直到找到一个能够满足进程大小要求的空闲分区为止。然后，按进程的大小，从分区中“切出”一块内存空间分配给请求者，余下的空闲分区仍然留在链表中。 例1：根据右图的内存使用情况画出首次适应算法的链表组织形式及分配一个10KB的作业后的情况。 操作系统 空闲区1(26KB) 已使用 空闲区2(14KB) 已使用 空闲区3(5KB) 已使用 空闲区4(30KB) 已使用 0k 40k 66k 70k 84k 100k 105k 150k 180k 256k 1解：（1）分配一个10KB的作业前的链表组织形式。 40k 26kB 70k 14kB 100k 5kB 150k 30kB ∧ 70k 100k 150k （2）分配一个10KB的作业后的链表组织形式。 50k 16kB 70k 14kB 100k 5kB 150k 30kB ∧ 70k 100k 150k 操作系统 空闲区1(26kB) 已使用 空闲区2(14kB) 已使用 空闲区3(5kB) 已使用 空闲区4(30kB) 已使用 0k 40k 66k 70k