《深入理解计算机系统》笔记

栈

• 由编译器自动分配释放
• 本函数中栈的用途
  • 把局部变量压入栈保存
• 调用函数时栈的用途
  • 存储被调用函数的参数值
  • 返回地址入栈
  • 被调用函数使用的非静态局部变量以及编译器自动生成的其他临时变量
  • 保存上下文,保存函数调用前后需要保持不变的寄存器
• 函数被调用时,数据入栈顺序
  • 被调用的函数的参数(C编译器中,参数从右到左入栈)
  • 返回地址
  • 旧的%ebp地址,用于还原
  • 保存的寄存器
  • 新函数的局部变量和其他数据
• 注意:静态变量不入栈.本次函数结束后,还原现场

第9章 虚拟存储器

• 物理和虚拟地址
• CPU硬件单元：MMU（地址翻译）
• 地址空间
  • 线性地址空间
  • 虚拟地址空间
• 虚拟存储器
  • N个连续的字节大小的单元组成的数组
  • 磁盘块：磁盘和主存的传输单元
  • 虚拟页（VP），典型的是4KB-2MB
  • 物理页（PP），也称页帧（page frame），大小和虚拟页相同
    • 三个不相交子集
      • 未分配的
      • 缓存的
      • 未缓存的
  • DRAM、SRAM
  • 页表
    • 页表条目（PTE）
      • 一个有效位
      • n位地址字段
    • 页命中
      • 缺页（page fault）
      • 页面交换（swapping），也叫页面调度（paging）
        • 换入（页面调入）
        • 换出（页面调出）
        • 调度策略
          • 按需页面调度（demand paging）
          • 预测不命中？
      • 局部性（locality）
        • 活动页面（active page）集合，也叫工作集（working set）、常驻集（resident set）
        • 颠簸（thrashing）（内存太小）
  • 作为存储器管理工具
    • 每个进程都有独立的页表，即独立的虚拟地址空间
    • 多个虚拟页面可以映射到同一个共享物理页面上
    • 和按需页面调度结合
      • 简化链接
      • 简化加载
      • 简化共享
  • 作为存储器保护工具
    • 额外的许可页（SUP位 是否内核可读，READ位，WRITE位
    • 段错误（segmentation fault）
    • 保护内核代码和数据结构
    • 保护其他进程的私有存储器
    • 保护与其他进行共享的虚拟页
  • 地址翻译
    • 虚拟地址空间和物理地址空间的地址数量（可以不同，通过页面交换来克服）
    • 页大小
    • 虚拟地址
      • 虚拟页面偏移量（字节）
      • 虚拟页号
      • TLB索引
      • TLB标记
    • 物理地址
      • 物理页面偏移量
      • 物理页号
      • 缓存块内的字节偏移量
      • 高速缓存索引
      • 高速缓存标记
    • 高速缓存 L1 L2 等
    • 翻译后备缓冲器（translation lookaside buffer）TLB，包含在MMU中
    • 多级页表
  • Linux 虚拟存储器系统
    • 区域（area），也叫做段
      • 虚拟页必须存在于这些区域中
      • 分级
        • 未知？
        • 程序文件 .text
        • 已初始化数据 .data
        • 未初始化数据 .bss
        • 运行时堆
          • malloc
          • free
        • 共享库
        • 用户栈
        • 内核代码和数据
        • 物理存储器
        • 与进程相关的数据结构
          • 页表
          • task
            • PID
            • 指向用户栈的指针
            • 可执行目标文件的名字
            • 程序计数器
            • …
          • mm结构
          • 内核栈
          • …
    • Linux缺页处理
      • 内核的缺页处理程序
        • 地址合法性：段错误，终止进程
        • 存储器访问合法性：保护异常，终止进程
        • 页面换入
          • 选择牺牲页
          • 换入
          • 重试
      • 地址翻译重试
    • 存储器映射（memory mapping）
      • 容许对象类型
        • Unix 文件系统的普通文件
        • 匿名文件，全是二进制零
      • 权限
        • 共享对象 - 共享区域
        • 私有对象 - 私有区域
          • 写时拷贝（copy on write, COW）
    • fork
    • execve
• 动态存储器分配
  • mmap munmap
  • 动态存储器分配器（dynamic memory allocator）
    • heap
      • malloc
        • 返回一个指针，指向大小为至少size（参数）字节的存储器块
      • calloc
        • 基于malloc包装的函数
        • 将分配的存储器初始化为零
      • realloc
        • 改变一个以前已分配块的大小
      • sbrk
        • 将内核的brk指针增加incr（参数）来扩展和收缩堆，所以参数可以为负数
      • free
        • 参数为已分配块的起始位置
        • 无返回值（不会知道出现了错误）
      • 视为一组不同大小的块（block）的集合
        • 已分配的
        • 空闲的
      • 字节对齐
    • 两种风格
      • 显式分配器（explicit allocator）
      • 隐式分配器（implicit allocator）
        • 垃圾收集（garbage collection）
    • 要求
      • 分配请求和释放请求的序列是任意的
      • 立即响应
        • 不允许重排请求序列或者缓冲请求
      • 任何非标量数据结构都必须保存在堆里
      • 对齐块
      • 不能修改已分配的块
    • 目标
      • 最大化吞吐率
      • 最大化存储器利用率
        • 峰值利用率
        • 碎片
          • 内部碎片（块未满）：取决于历史的请求模式和分配器实现方式
          • 外部碎片（单一碎片太小，不足以容纳新请求大小）：还取决于未来的请求的模式
    • 问题细化
      • 空闲块记录组织结构
      • 选择空闲块来放置新块
      • 分隔空闲块
      • 合并空闲块
    • 隐式空闲链表
      • 头部
      • 有效载荷
      • 优点
        • 简单
      • 缺点
        • 任何操作的搜索都与块总数（包含已分配和空闲）呈线性关系
      • 最小块大小
        • 分配器对块格式的选择
        • 系统对齐要求
      • 放置
        • 适配策略
          • 首次适配（first fit）
          • 下一次适配（next fit）
          • 最佳适配（best fit）
        • 未找到合适空闲块
          • 合并空闲块
          • sbrk函数请求额外的堆存储器，作为链表中新的一个空闲块
      • 合并空闲块
        • 何时执行
          • 立即合并（immediate coalescing）：产生大量不必要的分割和合并
          • 推迟合并（deferred coalescing）：更有效率
        • 脚部的 边界标记（boundary tag）：记录前一个块的起始位置和状态
          • 缺点：在操作许多小块时，产生占比更多的标记存储器开销
          • 改进：把前面块的已分配/空闲位存放在当前块中多出来的低位中
            • 已分配的块不需要脚部
            • 空闲块仍需要脚部
            • 缺点：如果当前块没有多余的空闲位呢？
    • 显式空闲列表
      • 将空闲块组织为某种形式的显式数据结构
      • 将前后空闲块的信息存储在空闲块的主体里
        • pred 前驱
        • succ 后继
      • 分配时间从块总数降低到了空闲块数量的线性时间
      • 释放块时间和空闲链表中块的排序策略
        • 后进先出（LIFO）
        • 地址顺序
    • 分离的空闲列表
      • 分离存储（segregated storage）
      • 大小类（size class）
      • 空闲链表数组
      • 两种基本方法
        • 简单分类存储（simple segregated storage）
          • 每个大小类的空闲链表包含大小相等的块
          • 不分割：很可能造成内部碎片（也跟适配策略有关）
          • 不合并：某些引用模式会引起极多的外部碎片
        • 分离适配（segregated fit）
          • 每个空闲链表和一个大小类相关联
          • 并且空闲链表被组织成某种类型的显式或隐式链表
          • 每个链表包含潜在的大小不同的块，这些块大小是大小类的成员
        • 伙伴系统（buddy system）
          • 分类适配的特例，每个大小类都是2的幂
          • （2048游戏）
• 垃圾收集
  • 引用计数
  • 标记清除（mark-sweep）
    • 有向可达图（reachability graph）
    • C 的保守 Mark&Sweep
      • 根本原因：C语言不会用类型信息来标记存储器位置，int、float这样的标量可以伪装成指针