内存管理¶

内存管理的概念¶

首次适配（First）：空闲分区链表按地址排序，分配快，回收效率高，小碎片多
临近适配（Next）：从上次分配的地址开始查找，减少搜索时间
最佳适配（Best）：空闲分区链表按块从小到大排序，选择最小的足够大的空闲分区，小碎片多
最差适配（Worst）：空闲分区链表按块从大到小排序，选择最大的空闲分区，多中等碎片
算法对比
- 复杂度：最佳（2+2）> 最差（1+2）>首次（1+1）>循环（1+1）
- 小碎片产生的可能性：最佳 >首次 > 循环 > 最差
- 后继大作业分配成功的可能性：最佳 >首次 > 循环 > 最差

页表（page table）
- 逻辑地址 = 页号 + 页内偏移
- 物理地址 = 帧号 + 页内偏移
快表（TLB：Translation Lookaside Buffer）
- 页表在 Cache 或寄存器中的副本
- 用于加速地址转换
多级页表
- 把整个页表进行分页，分成一张张小页表，每个小页表的大小与页框相同。
- 对小页表顺序编号，允许小页表分散存放在不连续的页框中。
- 为了进行索引查找，应该为这些小页表建一张页目录表（一级页表），其表项指出小页表（二级页表）所在页框号及相关信息。
- 逻辑地址结构有三部分组成：页目录号、页号和位移。
反向页表（Inverted Page Table）
- 虚拟地址的页号使用散列函数映射到哈希表中。
- 把 \(n\) 位页号映射到 \(m\) 位帧号（\(n > m\)）
- 大小与物理内存成正比

位图方式：
- 每个 Bit 表示一块的使用状态。0 表示空闲，1 表示已分配。
- 表示能力：32MB 主存，页大小为 4K，1KB 的空间就足够表示。
- 效率高：只要修改对应 bit 就可以
空闲链表方式：
- 用链结构表示空闲页。

最优淘汰算法（OPT-Optimal）
- 淘汰将来最长时间不使用的页面。
- 需要预知未来的页面访问情况，实际不可行。
- 作为理论上的评价标准，用以鉴别其他淘汰算法的优劣
先进先出淘汰算法（FIFO）
- 淘汰最先进入内存的页面。
- 实现简单。
- 可能导致系统抖动（频繁换入换出页面）。
最近最少未使用算法（LFU-Least Frequently Used）
- 淘汰在一定时间内未被访问的页面。
- 为每页面设置访问计数器，通过比较所有页的计数器值来确定淘汰的页面。
- 需要定期对计数器清零，以淘汰过期页
- 过于复杂
最久不使用淘汰算法（NUR-Not Used Recently），即 Clock 算法
- 结合了 FIFO 和 LFU 的思想。
- 1 个访问位
  - 每个页面有一个访问位，表示最近是否被访问过。
  - 使用一个指针指向当前检查的页面，按顺序检查页面。
  - 如果访问位为 1，则清零并继续检查下一个页面；如果为 0，则淘汰该页面。
- 1 个访问位 + 1 个修改位
  - 每个页面有一个访问位和一个修改位。
  - 访问位表示最近是否被访问过，修改位表示页面是否被修改过。
  - 使用一个指针指向当前检查的页面，按顺序检查页面。
  - 如果访问位为 1，则清零并继续检查下一个页面；如果为 0，则淘汰该页面。
- 适用于大多数实际情况，性能较好。

虚拟分段的优点：
- 简化不断增长的数据结构处理方式
- 允许分块编译
- 有助于进程间的共享
- 有助于实现保护机制
段页式地址翻译
- 段号 \(s\) + 页号 \(p\) + 页内偏移 \(d\)
- 为了进行地址变换，系统为每一个作业建立一张段表，再为每一段建立一张页表。同样，也有一个段表控制寄存器，存放当前作业段表的长度和始址。
读取策略
- 请求式分页
- 预约式分页
放置策略
- 最佳适配
- 首次适配
- 近邻适配
- 最差适配
替换策略
- 算法
  - Opt
  - FIFO
  - LRU
  - Clock（NRU）
- 页缓冲
清除策略（回写）
- 请求式清除
- 预约式清除

伙伴系统（Buddy system）
- 将内存分成大小为 \(2^n\) 的块。
- 分配时，寻找最小的满足要求的块。
- 回收时，将相邻的块合并成更大的块。
- 优点：减少碎片，提高内存利用率。
```
Void get_hole( int i)
{
If ( i == ( u+1) ) failure;
If ( <i_list empty> )
{
get_hole( i+1);
<split hole into buddies>;
<put buddies on i_list>;
}
<take first hole on i_list>;
}
```
Slab 系统
- 将内存分成多个大小相同的块（slab）。
- 每个 slab 包含多个对象，每个对象大小相同。
- 对象分配和回收时，直接在 slab 中进行，不需要频繁的内存分配和释放。
- 优点：减少碎片，提高内存利用率。
SLUB：在 SLAB 的基础上简化设计，提高性能。更适合多处理器系统使用。是目前 Linux 版本的默认配置。
SLOB：为嵌入式系统提供极简的内存分配方案。