多图警告。

上一章空间管理的问题

  • 大量的空闲(free)空间 -
    • 这些空闲空间实实在在的占用了物理内存
  • 必须为进程的整个虚拟地址空间分配 连续的物理内存 -
    • 会导致什么问题？

一、“分段”地址转换

1. 基本原理

  • 段是虚拟地址空间中的一个连续片段
    • 代码段、栈段、堆段
    • 对于每个段来说，都有它的基址和界限
    • 只需以段为单位，给进程分配连续物理内存
    • 物理地址 = 段基址 + 段内偏移 （段内偏移≠虚拟地址）

enter image description here

enter image description here

enter image description here

  • 粗粒度和细粒度的分段
    • 粗粒度：只支持少量 段，如code、heap、 stack
    • 细粒度：支持很多段， 需要硬件支持段表
  • 如何判定非法内存访问？
    • 硬件在地址转换时检查
    • 如果超出了界限，则会报段错误 (segmentation fault)
    • 陷入内核…

2. 段的表示：显式、隐式

(1) 显式方法：用虚拟地址的高位表示

enter image description here

// get top 2 bits of 14-bit VA
Segment = (VirtualAddress & SEG_MASK) >> SEG_SHIFT
Offset = VirtualAddress & OFFSET_MASK 
if (Offset >= Bounds[Segment])
	RaiseException(PROTECTION_FAULT)
else
	PhysAddr = Base[Segment] + Offset
	//在CPU中将多组基址和界限放到寄存器数组中

(2) 隐式方法：不放在虚拟地址中

根据当前指令类型决定使用 哪个段寄存器

enter image description here

  • 对于栈是否有什么特殊性？
    • 栈是反向增长的，需要额外的硬件支持

enter image description here

3. 段的共享与保护

  • 有些时候需要在地址空间里共享(share)内存段
    • 为了节省内存，例如代码共享
  • 需要硬件提供支持：段的保护位(Protection bits)

enter image description here

4. OS需要处理相关事项

  • 上下文切换时：所有的段寄存器都要保存和恢复
  • 案例：现在有24KB空闲空间， 如何为一个20KB的段分配空间？
    • 需要应对外部碎片(external fragmentation)
      • 空闲的、难以使用的小内存块
      • 产生原因：段内连续，段长可变
    • 紧致化处理(compaction)
      • 对段进行重排
        • 停止进程的运行
        • 拷贝数据
        • 修改段寄存器的值
      • 有效，但是代价高

enter image description here

二、空闲空间管理

1. 底层机制

  • 分割(splitting)：将一个空闲块分割成两块，其中一块给用户

enter image description here

enter image description here

  • 合并(coalescing)：将相邻的两个空闲块合为一块

enter image description here

  • 当一个新空闲块进入队列时，如何高效地进行合并操作？
    • free(void *ptr)接口并没有要释放的块大小的参数

enter image description here

  • 记录已分配块的大小
    • 头块中包含分配空间的大小
    • 也可能包含额外的指针加速释放、magic number用来检查完整性

enter image description here

  • 建立空闲块列表: 列表节点
  • 堆的初始化：假设使用mmap()

enter image description here

  • 案例：通过调用ptr = malloc(100)申请内存

enter image description here

  • 分配3块内存后

enter image description here

  • 释放1块内存后
    • 假设归还的空闲块被插 入到列表的头位置，那 么next指向什么地址？ enter image description here

答：16708

  • 释放3块内存后

enter image description here

目前的内存空间合理吗？

2. 空闲内存分配策略

  • 评价指标：速度快，碎片少，分配成功率高

假设现在需要大小15的内存块

head -> 10 -> 30 -> 20 -> NULL

enter image description here

enter image description here

enter image description here

enter image description here

3. 其他方式

enter image description here

enter image description here

enter image description here

enter image description here