(东南大学集成电路课程)内存管理.ppt

1. 内存管理的概念 2. 内存的管理方式 2. 内存的管理方式 2. 内存的管理方式 2. 内存的管理方式 2.2 常用算法 2.2 常用算法 2.2 常用算法 2.2 常用算法 2.2 常用算法 2.2 常用算法 2.2 常用算法 2.2 常用算法 3. uC/OS的内存管理 3. uC/OS的内存管理 3.1 uC/OS-II的内存管理算法 3.1 uC/OS-II的内存管理算法 3.1 uC/OS-II的内存管理算法 东南大学集成电路学院 国家ASIC系统工程技术研究中心 国家ASIC系统工程技术研究中心 嵌入式操作系统 第五章 内存管理 戚隆宁 longn_qi@seu.edu.cn 主要内容 1. 内存管理的概念 2. 内存管理方式 3. uC/OS-II中的内存管理 需求 数据的大范围动态使用 众多的任务共享有限的内存 数据具有不同的生命期（跨越函数边界） 数据规模的不确定性 1. 内存管理的概念 内存布局 堆 动态变量 全局数据区 全局变量/静态变量 栈 局部变量 动态数据 常量区/代码段 常量 静态数据 数据 代码区 代码 存放位置 1. 内存管理的概念 内存管理 任务所需内存资源的分配和回收 一般基于堆进行管理 物理地址与虚拟地址 物理地址（Physical Address）是处理器为内存资源分配的地址空间 虚拟地址（Virtual Address）是经过内存管理单元（MMU）转换后的内存地址空间 虚拟内存 因物理内存不足，将内存数据临时保存在永久存储介质（硬盘）而形成的虚拟内存空间（Virtual Memory） 1. 内存管理的概念 内存保护 数据访问地址越界监控 数据访问权限隔离 操作系统与任务的隔离 任务与任务的隔离 任务1 任务2 任务3 嵌入式操作系统 2.1 标准堆管理 2.2 常见问题 2.3 常用管理算法 2.1 标准堆管理 编程语言和运行时库提供的标准堆管理 C语言 malloc和free C++语言 new和delete，智能指针（smart pointer/auto_ptr） Java语言 动态数组（ArrayList）和垃圾回收（Garbage Collection） 2.2 常见问题 内存碎片（memory fragment） 内存泄露（memory leak） 悬垂指针（dangling pointer） 内存越界访问 2.2 常用算法 固定内存分配大小 链表 可变内存分配大小 首次适应算法 循环首次适应算法 最佳适应算法 最差适应算法 首次适应算法 从空闲分区链首开始查找，直至找到一个能满足其大小要求的空闲分区为止。然后再按照请求的大小，从该分区中划出一块内存分配给请求者，余下的空闲分区仍留在空闲分区链中。 倾向于使用内存中低地址部分的空闲分区，在高地址部分的空闲分区很少被利用，从而保留了高地址部分的大空闲区。有利于以后分配较大的内存。 低址部分不断被划分，内存碎片多，增加查找的开销。 循环首次适应算法 从上次找到的空闲块开始查找，直至 找到一个能满足要求的空闲块，并从中划出一块来分给任务。 使空闲中的内存块分布得更加均匀 缺乏大的空闲块 最佳适应算法 将所有的空闲区按其大小排序后，以递增顺序形成一个空白链。这样每次找到的第一个满足要求的空闲区，必然是最优的。 虽单次最优，但每次分配后剩余的空间一定是最小的，碎片会更加严重。同时每次分配后必须重新排序， 这也带来了一定的开销。 最差适应算法 按大小递减的顺序形成空闲区链，分配时直接从空闲区链的第一个空闲分区中 分配（不能满足需要则不分配）。 内存小碎片较少。 可用大内存块少。 Yorktown算法 数据结构 以 Cartesian 二分法检索树的形式维护空闲堆。节点按照地址从左到右（地址向右增加），按照长度从上到下排列（因此子节点不会比其父节点大）。 分配 删除空闲树中符合请求的地址最低的节点。如果这个节点大于请求量，就分为两块。多余部分插回在空闲树中，符合部分返回给调用者。 释放 标准的根插入算法。 Watson算法 数据结构 在两个单独的 “红黑树” 中以节点的形式维护堆中的空闲空间，分别以地址和大小排序 分配 有哪些信誉好的足球投注网站大小树，寻找符合请求的最小的块。如果找到，那么从大小树和地址树中删除这个块并返回给调用者。如果没有找到，那么扩展堆把扩展后的块添加到大小树和地址树中，然后继续分配。 释放 标准的根插入算法。同时更新两个树。 Malloc 3.1算法 数据结构 以散列 bucket 的形式维护内存堆，每个 bucket 指向一个链表，每个链表只包含特定大小的节点或块。块的大小 = 2 ^ (bucket 编号 + 4)。 分配 根据公式把请求的字节数转换为 bucket 数组索引。如果 bucket 中的