动态分区分配方式 ◆能根据进程实际需要的内存大小,动态分配 能減少内部碎片 ◆关键 数据结构:记录内存的使用情况,特别是空闲内存 分配算法 1958 分配和回收操作 嵌入式系统实验室 EM目 EDDED SYSTEM LA口RAT口RY
动态分区分配方式 ❖能根据进程实际需要的内存大小，动态分配 ➢能减少内部碎片 ❖关键 ➢数据结构：记录内存的使用情况，特别是空闲内存 ➢分配算法 ➢分配和回收操作
数据结构 空闲分区表,占用额外的空间 序号分区大小起始地址状态 空闲分区链,利用空闲分区 前向 后向 指钅 指针 N+2N个字节可用N+2 嵌入式系统实验室 EM目 EDDED SYSTEM LA口RAT口RY
数据结构 ❖ 空闲分区表，占用额外的空间 ❖ 空闲分区链，利用空闲分区 序号 分区大小 起始地址 状态 前向 指针 N个字节可用 后向 指针 N＋2 N＋2 0 0
分区分配算法 ◆在将一个新作业装入内存时,要从空闲分区表或 空闲分区链中,选出一个分区分配给该作业,有 三种常见的分配算法 >首次适应算法FF: First fit 循环首次适应算法 最佳适应算法: Best fit== smallest >最差适应算法: Worst fist= largest 嵌入式系统实验室 EM目 EDDED SYSTEM LA口RAT口RY
分区分配算法 ❖在将一个新作业装入内存时，要从空闲分区表或 空闲分区链中，选出一个分区分配给该作业，有 三种常见的分配算法 ➢首次适应算法FF：First Fit ➢循环首次适应算法 ➢最佳适应算法：Best Fit=smallest ➢最差适应算法：Worst Fist ＝largest
分区分配操作 ◆分配 >设请求的分区大小为 u size 利用某种分配算法,找到待分配的分区,大小为m.size 根据上述分区分配算法,有 m size>u.size 判断 m size- u. size与 min size的大小 min size为事先约定的最小分区大小 ,分割,分割出来的分配出去,余下的加入空闲数据结构 否则,直接分配 将分配到的分区的首地址返回 可以看出,动态分区分配方式中内部碎片最大不超过 min size 嵌入式系统实验室 EM目 EDDED SYSTEM LA口RAT口RY
分区分配操作 ❖ 分配 ➢ 设请求的分区大小为u.size； ➢ 利用某种分配算法，找到待分配的分区，大小为m.size ➢ 根据上述分区分配算法，有m.size>u.size ➢ 判断m.size-u.size与min_size的大小 min_size为事先约定的最小分区大小 ⚫ >，分割，分割出来的分配出去，余下的加入空闲数据结构 ⚫ 否则，直接分配 ➢ 将分配到的分区的首地址返回 可以看出，动态分区分配方式中内部碎片最大不超过 min_size
◆回收,要考虑合并 向前合并 只需修改前一个空闲分区表项中的大小 >向后合并(图) ●只需修改后一个空闲分区表项中的起始地址和大小 >与前后同时合并95 ●修改前一个空闲分区表项中的大小,并取消后个分区表项 无相邻空闲分区,无需合并 ●建立一个新的表项,填写相关信息,插入 ≯上述过程中,根据链表的维护规则,可能需要调整相 应表项在空闲链表中的位置 嵌入式系统实验室 EM目 EDDED SYSTEM LA口RAT口RY
❖回收，要考虑合并 ➢向前合并 ⚫只需修改前一个空闲分区表项中的大小 ➢向后合并（图） ⚫只需修改后一个空闲分区表项中的起始地址和大小 ➢与前后同时合并 ⚫修改前一个空闲分区表项中的大小，并取消后一个分区表项 ➢无相邻空闲分区，无需合并 ⚫建立一个新的表项，填写相关信息，插入 ➢上述过程中，根据链表的维护规则，可能需要调整相 应表项在空闲链表中的位置