8.1概述(4) 8.1概述(5) M不N 下☐ 10000 2000 39000 59000 99999 当有新的用户进入系统请求分配内存，系统将如何做呢？ 3100 。策略一：从高地址的空闲块中进行分配，当分配无法进 (a)内存状态 行时，系统回收所有用户不再使用的空闲块，并量新组 忽始地址内存块大小使用情况 织内存，将所有空闲的内存区连接在一起成为一个大的 10,00015,000 空用 空闲块。 31,000 8,000 。策略二：从所有空闲块中找出一个“合适”的空闲块分配 空用 0150007 080002 041.0002 之 59,000 41,000 空用 系统需要建立一张记录所有空闲块的“可利用空间麦”， (b)目录表 (c)能表 它可以是目录表，也可以是“能表。 回 8/35 图 8.2可利用空间表及分配方法 8.2可利用空间表及分配方法(1) 。可利用空间表的表示一链表 。一个空闲块)一个结点 讨论利用可利用空间表进行动态 ·用户请求分配时，系统从表中剩除一个结点分配之 存储分配的方法， ·用户释放所占内存时，系统即回收并将它插入到表中 ■目录表简单，将在操作系统课程中介 。可利用空间表的结构 绍 。系统运行期间所有用户请求分配的存储量大小相同 。这里仅就链表的情况进行讨论 ·由于表中结点大小相同，则分配时无需查找 。可以用链找实现 —操作系统中的固定分区管理 9/35 图 10/35 图 8.2可利用空间表及分配方法(2) 8.2可利用空间表及分配方法(3) 系统运行期间用户请求分配的 tag type link ·系统运行期间用户请求分配的存储量有若干种 存储量有若干种大小的规格 value 大小的规格 。建立若干个可利用空间 a2口 ·分配 表，同一链表中的结点大 o000 ·从结点大小和请求分配的量相同的链表中查找 小相同 a4 结点并分配之 。每个结点的第一个字设有 01 01G 01a ·若没有，则从结点较大的链表中查找结点，将 链城(ink):指向同一蛙 其中一部分分配给用户，剩余的播入到相应大 表中下一结点的指针 av8口 小的链表中 标志城(tag上0-空厢 0202 02N 若各链表都没有合适的结点，则要执行“存情紧 块、1-占用换 缩”将小块合并 结点类型城(ype):区 回收 分大小不同的德点 ·将释放的空闲块插入到相应大小的链表的表头 11/35 图 12/35 22 7/35 8.1 概述(4) „ 当有新的用户进入系统请求分配内存，系统将如何做呢？ „ 策略一：从高地址的空闲块中进行分配，当分配无法进 行时，系统回收所有用户不再使用的空闲块，并重新组 织内存，将所有空闲的内存区连接在一起成为一个大的 空闲块。 „ 策略二：从所有空闲块中找出一个“合适”的空闲块分配 之。 系统需要建立一张记录所有空闲块的“可利用空间表”， 它可以是“目录表”，也可以是“链表”。 U1 U3 U4 U6 U8 8/35 8.1 概述(5) U6 0 10000 25000 31000 39000 59000 99999 (a) 内存状态 59,000 41,000 空闲 31,000 8,000 空闲 10,000 15,000 空闲 起始地址 内存块大小 使用情况 (b) 目录表 0 15,000 av (c) 链表 0 8,000 0 41,000 ^ 9/35 8.2 可利用空间表及分配方法 讨论利用可利用空间表进行动态 存储分配的方法. „ 目录表简单，将在操作系统课程中介 绍 „ 这里仅就链表的情况进行讨论 10/35 8.2 可利用空间表及分配方法(1) „ 可利用空间表的表示——链表 „ 一个空闲块Æ一个结点 „ 用户请求分配时，系统从表中删除一个结点分配之 „ 用户释放所占内存时，系统即回收并将它插入到表中 „ 可利用空间表的结构 „ 系统运行期间所有用户请求分配的存储量大小相同 „ 由于表中结点大小相同，则分配时无需查找 „ 可以用链栈实现 ——操作系统中的固定分区管理 11/35 8.2 可利用空间表及分配方法(2) „ 系统运行期间用户请求分配的 存储量有若干种大小的规格 „ 建立若干个可利用空间 表，同一链表中的结点大 小相同 „ 每个结点的第一个字设有 链域(link)：指向同一链 表中下一结点的指针 标志域(tag)：0-空闲 块、1-占用块 结点类型域(type)：区 分大小不同的结点 tag type link value 0 0 av2 0 0 0 0 ^ 0 1 av4 0 1 0 1 ^ 0 2 av8 0 2 0 2 ^ 12/35 8.2 可利用空间表及分配方法(3) „ 系统运行期间用户请求分配的存储量有若干种 大小的规格 „ 分配 „ 从结点大小和请求分配的量相同的链表中查找 结点并分配之 „ 若没有，则从结点较大的链表中查找结点，将 其中一部分分配给用户，剩余的插入到相应大 小的链表中 „ 若各链表都没有合适的结点，则要执行“存储紧 缩”将小块合并 „ 回收 „ 将释放的空闲块插入到相应大小的链表的表头