分配策略三—最差拟合法 第八章动态存储管理 其指导思想是每次都用空闲块链表中最大的空国块去满足请求 分配,所以若链表中诸结点不是按容量大小排列的话,则每次分配 都扫描整个链表,即检测n次。但是,如果将链表结点按空闲块容 量的不增次序排列,则满足一次请求分配仅需检测一次即可。而回 收一个空闲块将其插入空闲块链表时,同样需平均检测n/2次 若按结点容量自大至小有序链接诸空闲块,则分配时仅需删除 第一个结点,并将其中一部分分配给用户,剩余部分作为一个新的 结点插入到链表适当位置。 三种方法分配、回收平均检测次数列列表如下 配给方法 分配空闲块 回收空闲块 首次拟合法最佳拟合法|最差拟合法 种方法 无序空闲块链表 <n/2 n 有序空闲块链表 /2 (按容量不增排列) 第16页
第八章 动态存储管理 第16页 分配策略三——最差拟合法 其指导思想是每次都用空闲块链表中最大的空闲块去满足请求 分配，所以若链表中诸结点不是按容量大小排列的话，则每次分配 都扫描整个链表，即检测n次。但是，如果将链表结点按空闲块容 量的不增次序排列，则满足一次请求分配仅需检测一次即可。而回 收一个空闲块将其插入空闲块链表时，同样需平均检测n/2次。 分 配 空 闲 块 回收空闲块 配 给 方 法 首次拟合法 最佳拟合法 最差拟合法 三种方法 无序空闲块链表 <n/2 n n 0 有序空闲块链表 （按容量不增排列） 1 n/2 1 n/2 若按结点容量自大至小有序链接诸空闲块，则分配时仅需删除 第一个结点，并将其中一部分分配给用户，剩余部分作为一个新的 结点插入到链表适当位置。 三种方法分配、回收平均检测次数列列表如下
十边界标识法 第八章动态存储管理 边界标识法( Boundary Tag Method)是操作系统中用 以在运行期间对用户所请求的随意内存块大小进行动态 分区分配的一种存储管理方法。 空例块表是个双向循环链表结构。分配策略或采 用首次拟合法,或釆用最佳拟合法。 系统特点 在每个内存区的头部和底部两个边界上分别设有标志域 以标识该内存区域为占用块或空闲块。在回收时,对物理上 相邻的空闲块进行全并,组合成一个尽可能大的、地址连续 的空闲块 第17页
第八章 动态存储管理 第17页 边 界 标 识 法 边界标识法 (Boundary Tag Method)是操作系统中用 以在运行期间对用户所请求的随意内存块大小进行动态 分区分配的一种存储管理方法。 空闲块链表是个双向循环链表结构。分配策略或采 用首次拟合法，或采用最佳拟合法。 系统特点： 在每个内存区的头部和底部两个边界上分别设有标志域， 以标识该内存区域为占用块或空闲块。在回收时，对物理上 相邻的空闲块进行全并，组合成一个尽可能大的、地址连续 的空闲块
十边界标识法 第八章动态存储管理 可利用空间表的结构 边界标识法中的结点结构head: link tag" size rlink space 一其中 head:结点的头部地址foot: uplink|tag foot:结点的底部地址 space:一组地址连续的待分配存储单元 ag:标志域,1ag0表示空闲块,1g=1表示古用块 size:整个结点的大小,包括头部 header和底部 footer所占空 间(设各占1个字),但在分配时忽略不计 Iink:指向双向循环链表中本结点的前趋结点的指针 rlink:指向双向循环链表中本结点的后继结点的指针 uplink:指向本结点的指针,其值即为该内存块的首地址 第18页
第八章 动态存储管理 第18页 可利用空间表的结构 边界标识法中的结点结构 其中 head：结点的头部地址 foot：结点的底部地址 space：一组地址连续的待分配存储单元 tag：标志域，tag=0表示空闲块，tag=1表示占用块 size：整个结点的大小，包括头部header和底部footer所占空 间（设各占1个字），但在分配时忽略不计 llink：指向双向循环链表中本结点的前趋结点的指针 rlink：指向双向循环链表中本结点的后继结点的指针 uplink：指向本结点的指针，其值即为该内存块的首地址 边 界 标 识 法 space llink tag size rlink uplink tag head： foot：