十可利用空间表及分配方法 第八章动态存储管理 结构形式二:建立若干个可利用空间表,同一链表中的结点大小 相同。。不同链表中的结点大小,一般成倍数关系。 根据用户请求空间的大小,到相应的空闲表中取结 分配过程?3点。若该空闲表为空,则到较大结点的链表中取 结点,把它一分为二,一部分分配给用户,另部分 插入到结点较小的空闲表中 生什么结果?3结点较大链表中的结点,不断一分为二,很容 易用完,所以回收时,必须有“紧缩聚合”的 过程。 第1页
第八章 动态存储管理 第11页 结构形式二：建立若干个可利用空间表，同一链表中的结点大小 相同。不同链表中的结点大小，一般成倍数关系。 可利用空间表及分配方法 分配过程？ 根据用户请求空间的大小，到相应的空闲表中取结 点。若该空闲表为空，则到较大结点的链表中取一 结点，把它一分为二，一部分分配给用户，另部分 插入到结点较小的空闲表中。 产生什么结果？ 结点较大链表中的结点，不断一分为二，很容 易用完，所以回收时，必须有“紧缩聚合”的 过程
十可利用空间表及分配方法 第八章动态存储管理 结构形式三:结点所包含空闲块的大小可随请求而变 通常,操作系统中的可利用空间表属于这种类型。 结点结构的一般形式 tag size link 图84空闲块的大 space 其中 小随意的结点结构 tag:标志位,如g=0表示空闲块,tag=1表示用块 size:空闲块的存储容量 ik:链接下一个结点的指针域、 如何分配? spack:一片地址连续的内存区域 若用户需求量为n,链表中仅有一块其容量mn,则分割出大 小为n的部分分配给用户,剩余大小为mn的部分作为一个结点留 在链表中(只要把size改小就行)。 问,若空闲块链表中有若干个大小不小于n的结点,该分配哪一 个?分配策略? 种分配策略:首次拟合法;最佳拟合法;最差拟合法。第12页
第八章 动态存储管理 第12页 如何分配？ 结构形式三：结点所包含空闲块的大小可随请求而变。 通常，操作系统中的可利用空间表属于这种类型。 其中 tag：标志位，tag=0表示空闲块，tag=1表示占用块 size：空闲块的存储容量 link：链接下一个结点的指针域、 spack：一片地址连续的内存区域 可利用空间表及分配方法 tag size link space 结点结构的一般形式 图8.4 空闲块的大 小随意的结点结构 若用户需求量为n，链表中仅有一块其容量m≥n，则分割出大 小为n的部分分配给用户，剩余大小为m-n的部分作为一个结点留 在链表中（只要把size改小就行）。 问题：若空闲块链表中有若干个大小不小于n的结点，该分配哪一 个？分配策略？ 三种分配策略：首次拟合法；最佳拟合法；最差拟合法
分配策略一:首次拟合法 第八章动态存储管理 从空闲块链表的表头指针开始查找,找出苴先,足请求容量 的存储块,将其中一部分分配给用户。可利用空间表本身既不按结 点的初始地址有序,也不按结点的大小有序。在回收时,只要将释 放的空闲块插入在链表的表头即可。 这种方法需对空闲块链表的结点检测的平均次数从n不等。 所以,首次拟合法为/满足一次请示平均检测次数小m2 云例就示例1的可利用空间表(链表),设有用户U进入系统并 申请7千字内存,则按首次拟合法,有 av10.000 31000 59000 08,000 0|80000410024 图8.5结点大小随意的可利用空间表 队高位开始分首次拟合原则进行分配 18000 一分配给用户的占用块700 第13页
第八章 动态存储管理 第13页 分配策略一：首次拟合法 从空闲块链表的表头指针开始查找，找出首先能满足请求容量 的存储块，将其中一部分分配给用户。可利用空间表本身既不按结 点的初始地址有序，也不按结点的大小有序。在回收时，只要将释 放的空闲块插入在链表的表头即可。 分配给用户的占用块 1 7,000 18,000 这种方法需对空闲块链表的结点检测的平均次数从1—n不等。 所以，首次拟合法为了满足一次请示其平均检测次数小于n/2。 示例3 就示例1的可利用空间表（链表），设有用户U9进入系统并 申请7千字内存，则按首次拟合法，有 0 15,000 0 8,000 0 41,000 ∧ av 10,000 31,000 59,000 图8.5 结点大小随意的可利用空间表 从高位开始分(a)按首次拟合原则进行分配 8,000
分配策略二:最佳拟合法 第八章动态存储管理 从空闲块链表中找出能满足用户请求容量的最小空原块。显 然这是一种较好的方法,但为了满足某个请示分配,需要对空闲块 链表从头至尾扫描,时间开销大 最佳空闲块 示例5上例,若采用最佳拟合法,则可得 31,000 ay015000100104102N 从高位开始分 32000 分配给用户的占用块70图85结点大小随意的可利用空间表 (b)按最佳拟合原则进行分配 优点,尽可能保证较大的空闲块不被细分。以满足较大的空间请求 缺点;有可能使剩余的空闲块容量变得太小,以至于不能满足任何 请求 第14页
第八章 动态存储管理 第14页 分配策略二：最佳拟合法 从空闲块链表中找出能满足用户请求容 量的最小空闲块。显 然这是一种较好的方法，但为了满足某个请示分配，需要对空闲块 链表从头至尾扫描，时间开销大。 分配给用户的占用块 1 7,000 32,000 图8.5 结点大小随意的可利用空间表 (b)按最佳拟合原则进行分配 0 15,000 0 8,000 0 41,000 ∧ 31,000 59,000 av 10,000 示例5 上例，若采用最佳拟合法，则可得 最佳空闲块 从高位开始分 1,000 优点：尽可能保证较大的空闲块不被细分。以满足较大的空间请求。 缺点：有可能使剩余的空闲块容 量变得太小，以至于不能满足任何 请求
分配策略二:最佳拟合法 第八章动态存储管理 为了避免每次分配都要扫视整个链表,可以改造空 闲块链表的结点排列顺序,即以结点的容量由小到大推 烈。这样为了满足某个请求分配,则平均检测结点的数 目只是链表结点个数一半即可。然而在这种情况下,将 任一空闲块插入至空闲块链表的一半位置也需要平均检 测链表的一半结点。而不按块容量大小排列的空闲块链 表,回收算法中不需要做检测工作 第15页
第八章 动态存储管理 第15页 为了避免每次分配都要扫视整个链表，可以改造空 闲块链表的结点排列顺序，即以结点的容量由小到大排 列。这样为了满足某个请求分配，则平均检测结点的数 目只是链表结点个数一半即可。然而在这种情况下，将 任一空闲块插入至空闲块链表的一半位置也需要平均检 测链表的一半结点。而不按块容量大小排列的空闲块链 表，回收算法中不需要做检测工作。 分配策略二：最佳拟合法