四平市网站建设_网站建设公司_阿里云_seo优化

说明

• 庄老师的课堂，如春风拂面，启迪心智。然学生愚钝，于课上未能尽领其妙，心中常怀惭愧。
• 幸有课件为引，得以于课后静心求索。勤能补拙，笨鸟先飞，一番沉浸钻研，方窥见知识殿堂之幽深与壮美，竟觉趣味盎然。
• 今将此间心得与笔记整理成篇，公之于众，权作抛砖引玉。诚盼诸位学友不吝赐教，一同切磋琢磨，于学海中结伴同行。
• 资料地址：computing-system-security

动态内存分配（重点）

• 程序员使用动态内存分配器（如 malloc）在运行时获取虚拟内存（VM）。
• 动态内存分配器管理进程虚拟内存（VM）中称为堆的一个区域。
  

虚拟内存结构

• 堆位于用户空间中运行时可扩展区域
• 栈向下增长，堆向上增长（由brk指针标识）
• 堆用于运行时动态分配内存（如malloc）
• 分配器管理堆区，作为进程虚拟内存的一部分

分配器功能

• 分配器管理堆为可变大小的块集合。块的状态为已分配或空闲
• 分配器的类型为：
  • 显式分配器：应用程序显式调用分配与释放（如C语言中的malloc/free）。
  • 意外分配器：仅分配不释放，依赖垃圾回收（如Java中的new/GC）。

malloc和free函数

• malloc函数原型：void *malloc(size_t size)
• 成功时返回至少size字节的内存块指针，若size为0，行为未定义（通常返回NULL）；失败时返回NULL，并设置errno为ENOMEM。
• 对齐要求：在x86-64上对齐到16字节边界。

• free函数原型：void free(void *p)
• 将指针p指向的内存块归还给可用池，p必须来自之前的malloc/calloc/realloc调用。
• 多次释放同一指针会导致未定义行为。

#include<stdio.h>#include<stdlib.h>voidfoo(longn){longi,*p;/*Allocate a block of n longs*/// malloc返回的指针对齐到双字（16字节）p=(long*)malloc(n*sizeof(long));if(p==NULL){perror("malloc");exit(0);}/*Initialize allocated block*/for(i=0;i<n;i++)p[i]=i;/*Do something with p*/.../*Return allocated block to the heap*/free(p);}

• 可视化规则：每个字节（1B）用方块表示，分配需满足双字对齐要求。
  
  
  我将从程序员笔记的角度，为您整理并翻译这份关于内存分配约束的内容：

内存分配约束

应用程序约束

• 内存请求灵活性：应用程序可以发出任意顺序的malloc和free请求
• 内存释放规则：free请求必须针对已通过malloc分配的内存块

显式分配器约束

• 无控制权：无法控制分配块的数量或大小。
• 即时响应：必须立即响应malloc请求，不能重新排序或缓冲请求。
• 内存来源：必须从空闲内存中分配块，只能将分配的块放置在空闲内存中。
• 对齐要求：必须对齐块以满足所有对齐要求，64位系统上需要16字节(x86-64)对齐。
• 内存操作限制：只能操作和修改空闲内存。
• 分配后限制：一旦块被malloc分配，就不能移动。

内存碎片

• 内存碎片分为：内部碎片（Internal Fragmentation）和外部碎片（External Fragmentation）。
• 内部碎片：当块的有效负载小于其总大小。主要来源为：对数据结构维护开销、对齐所需的填充字节、显示策略决策。
  
• 外部碎片：虽然总空闲内存足够，但无单一空闲块能满足新请求。
  

空闲块的跟踪和释放

• 核心挑战
  • 如何仅凭指针确定释放多少内存？
  • 如何跟踪空闲块？
  • 分配小结构到大空闲块时如何处理多余空间？
  • 多个合适块中如何选择？
  • 如何复用已释放的块?
• 确定释放内存的大小：在块起始前保留一个“头部”字段，存储快的总大小（包含头部本身[header field]），每个已分配块需额外一个字存储头部，释放时通过指针反推头部获取大小。
  

跟踪空闲块方法

方法1：隐式链表（基于长度）

• 所有块（无论空闲与否）按地址顺序链接，每个块需标记“已分配/空闲”，通过遍历查找可用块。
  

方法2：显式链表

• 仅在空闲块之间建立指针链接，需在空闲块内预留指针空间
  

方法3：分离空闲链表

• 按大小分类维护多个独立空闲链表，提高查找效率

方法4：按大小排序的块

• 使用平衡树（如红黑树），以块大小为键，支持快速查找匹配块

隐式空闲链表

• 问题：计算机内存需要管理很多小块空间，每个小块（称为"块"）需要记录：块的大小，分配状态。如果用两个完整的"字"（word，计算机存储单位）来存这两个信息，会浪费空间！
• 解决方案：当内存块按特定规则对齐时，地址的最低位永远是0，不再浪费一个完整的字来存分配状态，而是把那个"永远为0"的最低位复用作为"分配标志位"。
  • a=1：已分配的块
  • a=0：空闲的块
• 读取时的处理：读取块大小时，需要屏蔽那个被复用的最低位，得到真实的块大小。

+-----------------+|Size|a|←1个字+-----------------+|Payload|← 应用数据（仅分配的块有）+-----------------+|Optional|← 可选填充|padding|+-----------------+

• 起始标记：heap_start；结束标记：heap_end。
• 块表示：大小（字）/分配位
• 示例布局：
  • 16/0：16字空闲块
  • 32/1：32字已分配块
  • 64/0：64字空闲块
  • 8/1：结束块（已分配）

隐式链表数据结构

• 隐式链表：数据结构
  
• 隐式链表：头部访问
  
• 隐式链表：遍历链表
  

隐式链表：查找空闲块

首次适配（First Fit）：从堆起始位置开始搜索，选择第一个满足需求大小的空闲块。

• 时间复杂度为线性时间，可能在列表前端产生碎片（“splinters”）。

下次适配（Next Fit）：类似首次适配，但从上一次搜索结束的位置开始继续搜索。

• 避免重复扫描无用块，通常比首次适配快，但可能导致更严重的碎片化。

最佳适配（Best Fit）：搜索整个列表，选择剩余空间最少但仍能满足需求的空闲块。

• 减少大块浪费，提高内存利用率，但运行速度通常慢于首次适配。
• 属贪心算法，不保证全局最优。

隐式链表：在空闲块中分配

• 分割块（Splitting）：当请求的空间小于空闲块时，将块分割成已分配部分和新的空闲部分。
• 示例：split_block(p, 32)将64字节块分为32字节已分配块和32字节空闲块。
  

隐式链表：释放和合并

• 简单释放仅清除分配标志位会导致“伪碎片”问题。即使有足够连续空闲空间，也可能因未合并相邻空闲块而无法满足分配请求。
  
• 隐式链表合并：若被释放块前后有空闲块，将其合并即可！
  

隐式链表：双向合并

边界标签技术（Boundary Tags）

• 在空闲块末尾添加“边界标签”（即尾部 footer），复制头部信息。
• 支持反向遍历，实现与前一块的合并。
• 增加存储开销，但为通用且重要技术。
• 块格式包含头部和尾部，均含大小和分配位。
  

• 四种合并情况
  情况1：前后均为已分配，当前释放块独立成为空闲块。
  情况2：前块空闲，后块已分配，与前一块合并。
  情况3：前块已分配，后块空闲，与后一块合并。
  情况4：前后均空闲，三块全部合并为一大块。

显式空闲链表

数据结构设计

• 仅维护空闲块列表，非全部块
• 利用空闲块的 payload 区域存储链表指针
• 需要前向（next）和后向（prev）指针，因为下一个空闲块可能在任意位置
• 仍需边界标签以支持合并相邻块

• 空闲块格式：大小字段 | a 标志 | next 指针 | prev 指针 | payload 和填充

• 可选字段：a 表示是否已分配
  

• 逻辑上：A ← → B ← → C （双向链表） A ←→ B ←→ C（双向链表）A←→B←→C（双向链表）

• 物理上：块可在内存中任意顺序排列

• 前向链接连接下一个空闲块，后向链接连接上一个空闲块。示例块大小：32, 48, 32, 32, 48, 32, 32。
  

显式链表中的分配操作

• 分配前状态：若干空闲和已分配块。
• 执行malloc(...)请求内存，若找到合适块则进行分割，更新链表结构并返回指针。
• 分配后状态：新块被标记为已分配，剩余部分保留在空闲链表中
  

显式链表中的插入操作

无序插入

• LIFO（后进先出）策略：将释放的块插入空闲链表头部。
  • 优点：实现简单，时间复杂度为常数
  • 缺点：研究表明碎片化程度高于地址有序
• FIFO（先进先出）策略：将释放的块插入空闲链表尾部。
  • 优点：同样简单快速
  • 缺点：碎片化表现不如地址有序

地址有序策略

• 按地址顺序插入，保持链表中块按地址升序排列，a d d r ( p r e v ) < a d d r ( c u r r ) < a d d r ( n e x t ) addr(prev) < addr(curr) < addr(next)addr(prev)<addr(curr)<addr(next)。
  • 缺点：需要遍历搜索插入位置
  • 优点：研究显示其碎片化程度低于 LIFO/FIFO。

LIFO 释放策略案例

案例一：普通释放

• 释放前：目标块前后均为已分配块
• 操作：将该块插入链表根部（头部）
• 结果：链表头更新为新释放的块
  

案例二：与后继块合并

• 释放前：目标块后接一个空闲块
• 操作：移除后继空闲块，合并两个块，将合并后的块插入链表头部
• 结果：减少碎片，提升可用大块数量
  

案例三：与前驱块合并

• 释放前：目标块前接一个空闲块
• 操作：移除前驱空闲块，合并两个块，将合并后的块插入链表头部。
• 结果：形成更大的连续空闲区域
  

案例四：三重合并

• 释放前：目标块前后均为空闲块
• 操作：移除前后两个相邻空闲块，三块合并成一个大块，插入链表头部。
• 结果：显著降低外部碎片
  

统一数据结构支持多种策略

• 使用循环双链表结构
• 单一数据结构支持多种策略组合：
  • 首次适配（First-fit） vs 下一次适配（Next-fit）：固定游标或随搜索移动。
  • LIFO vs. FIFO：
    • 插入为下一个节点（LIFO）。
    • 插入为前一个节点（FIFO）。

指针测试