操作系统导论

参考资料

• 操作系统导论

操作系统介绍

• 下详叙

虚拟化

CPU 虚拟化

进程

• 进程是程序的一次执行实例, 拥有独立的地址空间, 寄存器状态, 以及其他资源
• 系统会维护一个进程表, 记录所有进程的信息 (PCB)
• 状态
  • 初始
  • 运行
  • 就绪
  • 阻塞
  • 最终 (僵尸进程, 用于让父亲进程获取子进程的退出状态 / 回收资源)
    • 如果父进程一直不回收, 则会积累大量僵尸进程, 占用进程表空间 (PID)
• 创建
  • 在进程表中分配一个新条目
  • 惰性加载程序的代码段和数据段
  • 分配并初始化运行时栈区与堆区
  • 初始化资源, 如标准输入输出的文件描述符
  • 构建初始寄存器状态, 包括程序计数器与栈指针
  • 转移控制权

进程 API

• fork()
  • 复制当前进程为子进程, 父子都从该调用返回继续执行
  • 子进程返回 0, 父进程返回子进程 ID
  • 继承文件描述符, 环境变量等
• wait()
  • 阻塞当前进程, 直到某个子进程退出
  • 返回退出的子进程 ID
• exec()
  • 用一个新程序替换当前进程的代码段和数据段
  • 重新初始化堆区和栈区
• 如此奇怪的设计是为了方便在 fork() 与 exec() 之间插入其他操作, 如重定向标准输入输出

受限直接执行

• 为了提高性能, 允许用户进程直接在 CPU 上运行, 但还是要受限于某些规则
• 区分用户态与内核态
• 提供陷入与从陷阱返回的硬件原语
  • 在每个进程的内核栈中保存现场
  • 内核在启动时设置陷阱表

进程间切换

• 系统可以等待任意系统调用, 或者用户程序进行非法操作
  • yield() 什么也不做, 只是让出 CPU
• 也可以通过时钟中断, 时钟中断也就是为了操作系统维护控制权而设计的
  • 由操作系统启动时钟
  • 触发时会调用内核中的时钟中断处理程序
• 上下文切换
  • 和保存现场类似但不一样
  • 刚被中断的程序的部分内容已经被保存到内核栈中
  • 如果被调度, 更多内容是由操作系统主导的存储在进程结构中的现场保存与恢复

进程调度

• 越了解工作负载, 越能设计出好的调度算法
• \(\text{周转时间} = \text{完成时间} - \text{到达时间}\) 性能指标
  • 性能和公平在调度中往往是矛盾的
• FIFO
  • 先到先工作
  • 出现长作业时, 短作业等待时间过长 (护航效应)
• SFJ 最短作业优先
  • 优先调度估计运行时间最短的作业
  • 需要预知作业运行时间, 实际中难以实现
• 现在考虑任务不同时间到达
• STCF 最短完成时间优先
  • 抢占式的 SJF
  • 新到达的短作业可以抢占正在运行的长作业
• \(\text{响应时间} = \text{第一次运行时间} - \text{到达时间}\) 交互式系统重要指标
• RR 时间片轮转
  • 每个进程分配一个时间片, 时间片用完后切换到下一个进程
  • 时间片过大接近 FIFO, 过小则切换开销过大
  • 但对于周转时间非常差
• 现在考虑 IO 与运行时间不可知
• MLFQ 多级反馈队列
  • 基本思想
    • IO 密集型进程提升优先级, CPU 密集型进程降低优先级
    • 多个就绪队列, 每个队列有不同优先级, 队列内的进程优先级相同
    • 优先级高的队列先调度, 队列中进程采用 RR 调度
  • 方案
    • 新到达的进程进入最高优先级队列
    • 时间片用完后降低优先级, 但若在时间片内主动释放 CPU 则保持优先级
  • 对于 IO 密集型进程太友好, 可能导致 CPU 密集型进程饥饿
    • 每过一段时间, 将所有进程提升到最高优先级队列 (核心问题是具体多长时间)
  • 但是仍然会被恶意进程欺骗
    • 例如一个进程不断地在时间片内释放 CPU, 永远保持最高优先级
    • 解决方法是主动释放 CPU 不重置时间片
• 如果我们不考虑周转时间与响应时间, 而是确保每个工作获得一定比例的 CPU 时间
• 彩票调度
  • 每个进程根据彩票数量获得相应比例调度概率
  • 每次调度时, 系统随机抽取彩票, 持有该彩票的进程获得 CPU 时间
  • 彩票货币
    • 用户分配给进程彩票, 系统自动根据全局彩票池调度
  • 彩票转让
    • 进程可以将彩票转让给其他进程 (我依赖你, 我给你彩票)
  • 彩票通胀
    • 进程相互信任时, 可临时自发行彩票
  • 彩票中奖是随机的, 若为了公平性, 可引入行程, 使用步长调度
    • 用一个大数处以每个进程的彩票数, 结果作为该进程的步长
    • 每次调度一个进程时, 将该进程的行程加上步长
    • 每次调度时选择行程最小的进程

多处理器调度

• SQMS 单队列多处理器调度
  • 所有 CPU 共享一个就绪队列
  • 优点: 简单, 负载均衡
  • 缺点: 缓存亲和性差, TLB 亲和性差, 锁开销大
• MQMS 多队列多处理器调度
  • 每个 CPU 有自己的就绪队列
  • 优点: 缓存亲和性好, 锁开销小
  • 缺点: 负载均衡差 (但解决它的开销显著小于解决锁开销)
  • 解决方法
    • 迁移: 将某些进程从一个 CPU 队列迁移到另一个 CPU 队列
    • 具体实现为工作窃取: 空闲 CPU 从其他 CPU 窃取进程
• Linux 系统的实现, 三足鼎立
  • O(1) 调度器: 基于 MQMS + MLFQ
  • CFS 调度器: 基于虚拟运行时间 + 红黑树 (完全公平调度器, 目前默认)
  • BFS 调度器: 基于 SQMS + EEVEF (最早最合适虚拟截止时间优先算法)

内存虚拟化

地址空间

• 最早使用时分复用, 调度的进程才进入内存, 否则驻留在磁盘上
  • 太慢了, 所以内存够用的时候就不换出, 安全性又成问题
• 使用虚拟内存: 实现透明, 效率与保护
• brk 系统调用用来分配堆空间
  • 调整程序分断 (堆结束) 的位置

地址转换

• 基于硬件的地址转换, 将虚拟地址转换为物理地址
• 需要解决的第一个问题, 如何将基于虚拟地址编写的程序载入到不同物理地址运行
• 动态重定位 (硬件实现, 对应的软件实现就是静态重定位)
  • 使用寄存器保存基址 (基址寄存器) 与界限 (界限寄存器)
  • 每次内存访问时, 将虚拟地址加上基址寄存器的值作为物理地址, 但虚拟地址不允许超过界限寄存器的值
  • 缺点: 只能实现连续分配, 内存碎片严重

分段

• 栈与堆中间的内存未被使用, 导致大量浪费 (内部碎片)
• 考虑引入更多的基址与界限对, 每个分段一对
• 如何了解虚拟地址对应哪个分段
  • 将虚拟地址划分为两部分, 高位作为分段号, 低位作为段内偏移
  • 或者根据地址来源判断 (PC / 栈指针 / 其他)
• 栈在物理内存中也是向下增长的, 所以计算偏移量时要特殊处理
• 段也需要一个段表去维护权限, 基址与界限, 增长方向等信息
• 甚至堆空间的内部碎片也无法避免

空闲空间管理

• 最初空闲列表 (链表) 维护空闲空间起始地址与大小, 不断分割与合并
  • 但是不能记录已分配空间的信息 (用于释放)
  • 链表节点本身就存储在空闲内存块内部, 不需要额外的内存 (size + next)
• 头块
  • 在每个分配块的前面存储一个头块, 记录该块的大小与魔法数 (完整性校验)
  • 返回给用户的指针是头块后面的地址
  • 被隐式创建, 使用, 释放, 用户不可见
  • 其实是标准库堆管理器实现, 应对操作系统最少也要分配一页的情况
• 使用 mmap() 或 sbrk 向操作系统申请内存
• 剩余空间不足时会尝试向操作系统申请更多内存, 还不够则返回 NULL
• 存在外部碎片问题, 尽可能优化分配算法
  • 最优分配: 分配最小的足够空间 (遍历开销大)
  • 最坏匹配: 分配最大的足够空间 (幻想避免产生过小碎片, 现实很骨感, 遍历开销大 + 没啥效果)
  • 首次匹配: 从头开始找到第一个足够空间 (速度快, 碎片更容易合并)
  • 循环首次匹配: 记录上次分配位置, 从该位置开始查找 (避免总是从头开始, 速度更快)
  • 分离空闲列表: 将空闲块按大小分类, 只在对应类别中查找 (减少遍历开销)
  • 伙伴算法: 将内存划分为若干 2 的幂次方大小的块, 分配时向上取整, 回收时合并相邻空闲块
• 现实中往往结合多种算法 + 使用更高级的数据结构 (如平衡树) 来管理空闲空间

分页

• 部分见硬件软件接口
• 分段式将空间划分为若干不同大小的段, 分页式将空间划分为固定大小的页
• 页表设计
  • 物理页号占 \(40\) 位
  • 有效位, 缺不缺页
  • 读写位, 只能限制用户态
  • 特权位
  • 禁止执行位
  • 脏位, 是否被写过, 决定是否需要写回磁盘
    • 先于缓存的脏位, 写回磁盘前会先从缓存写回主存
  • 参考位, 是否被访问过, 用于页面置换算法
• 单级页表流程
  • 掩码 + 移位获得虚拟页号
  • 根据页表基址与虚拟页号计算页表项地址
  • 读取页表项, 物理页号 + 偏移量获得物理地址
  • 也就是翻倍的内存访问开销

TLB 与页表

• TLB 是页表的 Cache
  • 在 CPU 内部的内存管理单元实现, 速度非常快
  • 对其访问是纯硬件的, 操作系统配置一下页大小 (必须是 \(2\) 的幂次方) 和页表位置即可
  • TLB 命中时直接拿到物理地址
  • TLB 失效时查页表, 再加载到 TLB
• TLB 表项
  • 虚拟页号
  • 物理页号
  • 保护位: 读 / 写 / 执行
  • 有效位: 表示缓存是否有效
  • ASID (地址空间标识符)
    • 用于区分不同进程的同一虚拟页号
    • 避免切换进程时清空 TLB 的开销
  • 脏位: 是否被写过
  • 全局位: 是否在所有进程中都有效 (忽略 ASID)
• 线性页表实在太大
  • 大页, 或者至少变长页
  • 分段 + 分页, 页表中只需要保存该段界限大小的地址空间的项
• 多级页表
  • 将线性页表切分为页大小的块, 建立页目录记录这些块的位置
  • 如果一个块内所有页表项都是无效的, 则不分配该块
  • 页目录项 (PDE)
    • 有效位: 指示该页表块是否存在
    • 物理页号: 指向该页表块的物理页号
  • 可以继续多级切分, 会有性能开销, 用 TLB 掩盖
    • 目的是每一级页表都能放在一个页内 (灵活分配内存)
• 反向页表
  • 全局仅有一张页表, 每个页表项为一个物理页框
  • 每个项中保存该页框对应的虚拟页号与进程 ID
  • 通过哈希表建立索引

页面置换

• 将不常用的页换出到磁盘, 释放内存给其他页使用
  • 一般使用 swap 分区
  • 但如果加载的页从不会被修改 (如程序代码页), 则直接覆盖, 下次再从文件加载即可
• 页错误: 访问的页不在内存中
  • 根据页表项的存在位判断
  • 根据页表项中的磁盘地址将页读入内存
  • 内存已满时, 需要选择一个页换出 (页面置换算法)
• 系统一般规定一个最大内存使用量, 保证内存中始终有一定数量的空闲页
  • 通过页面清理程序后台运行, 将脏页写回磁盘, 并将不常用页换出
• 页面置换算法
  • 最优替换
    • 换出未来最长时间内不会被访问的页
    • 理论上最优, 实际中不可实现
  • FIFO 先进先出
    • 换出最早进入内存的页
    • 神奇的 Belady 异常: 增加页框反而增加缺页率, 原因是 FIFO 不具备栈特性 (大小为 \(n + 1\) 的缓存一定包含大小为 \(n\) 的缓存的内容)
  • 随机算法
    • 随机选择一个页换出
  • LRU 最近最少使用
    • 换出最长时间未被访问的页
  • LFU 最不常用
    • 换出访问次数最少的页
• 近似 LRU 算法
  • LRU 实现开销较大, 需要记录每个页的访问时间, 所以使用近似算法
  • 为每个页维护一个使用位, 硬件在每次访问页时将参考位置 1
  • 时钟算法
    • 将页表项按环形链表连接
    • 使用一个指针指向当前候选页
    • 每次需要换出页时, 检查指针指向的页的参考位
      • 若为 0, 则换出该页
      • 若为 1, 则将参考位清 0, 指针后移, 继续检查下一个页
  • 没有参考位的话只能使用页面缓冲
    • 每个进程使用 FIFO
    • 被换出的页放入全局的干净页列表或脏页列表末尾
    • 如果进程再次访问该页, 则可以直接从列表中取回, 不需要读磁盘
    • 只有当列表满时, 列表头的页才会被真正丢弃或写入磁盘
  • 考虑到写操作的开销, 可以引入脏位, 更优先换出未被修改的页
    • 批处理优化

VAX/VMS 虚拟内存系统

• 地址空间的高半部分是内核, 所有进程共享同一个 S 段映射
  • 上下文切换时, 不需要更改 S 段的映射
  • 内核可以直接访问用户空间的数据
  • 内核不是独立的实体, 而是所有进程的一部分
• 按需置零
  • 申请内存时, 不立即分配物理页, 而是等到第一次访问时才分配并清零
• 写时复制
  • fork() 时不复制内存, 而是共享, 只在写时才复制
• 空指针保护
  • 保留地址空间的低端不映射任何物理页, 防止空指针引用
• 防止恶意进程占用过多内存
  • 给每个进程设定一个驻留集大小上限, 只能踢掉自己进程的页, 防止某个进程占用过多内存

并发

• 目的是保证
  • 并发安全
    • 原子性
    • 可见性
    • 有序性
  • 并发健壮
    • 死锁
    • 活锁
    • 饥饿

线程

• int pthread_create(pthread_t *thread, const pthread_attr_t *attr, void *(*start_routine)(void *), void *arg);
  • thread: 指向存储线程信息的结构体
  • attr: 指定线程属性, 默认可传入 NULL
  • start_routine: 线程函数地址
  • arg: 传递给线程函数的参数, 可传入 NULL (无参数)
• int pthread_join(pthread_t thread, void **retval);
  • 阻塞调用线程, 直到指定线程结束
  • thread: 需要等待的线程 ID
  • retval: 存储线程返回值, 可传入 NULL (不需要返回值)

int thread_function(void *arg) {
    // 线程执行的代码
    return 0;
}

int main() {
    pthread_t thread;
    pthread_create(&thread, NULL, thread_function, NULL); // 创建线程
    // 主线程执行的代码
    pthread_join(thread, NULL); // 等待线程结束
    return 0;
}

• 线程的上下文切换类似进程, 但不需要切换地址空间 (页表)
• 线程的状态保存在线程控制块 (TCB, 本质是特殊 PCB) 中
• 线程共用堆区, 但有独立的栈区, 旁边是线程局部存储 (TLS) 与用户视角线程控制块

锁

• int pthread_mutex_lock(pthread_mutex_t *mutex);
  • 若锁已被其他线程持有则阻塞等待
• int pthread_mutex_unlock(pthread_mutex_t *mutex);
• int pthread_mutex_init(pthread_mutex_t *mutex, const pthread_mutexattr_t *attr);
  • attr: 指定互斥锁属性, 默认可传入 NULL (相当于 pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;)
• int pthread_mutex_destroy(pthread_mutex_t *mutex);
  • 销毁互斥锁
• int pthread_mutex_trylock(pthread_mutex_t *mutex);
  • 若锁已被其他线程持有则立即返回错误码
• int pthread_mutex_timelock(pthread_mutex_t *mutex, const struct timespec *abstime);
  • 若锁已被其他线程持有则阻塞等待直到超时
  • abstime: 指定绝对超时时间

pthread_mutex_t lock;
pthread_mutex_init(&lock, NULL); // 初始化互斥锁
pthread_mutex_lock(&lock); // 加锁
// 临界区代码
// ...
pthread_mutex_unlock(&lock); // 解锁
pthread_mutex_destroy(&lock); // 销毁互斥锁

• 锁实现
  • 早期使用禁用中断
    • 仅适用于单处理器系统, 中断可能丢失, 恶意进程可能一直占用 CPU
  • 高级的软件算法
    • 挺好, 但我们发现如果 CPU 提供了原子操作指令, 问题就迎刃而解了
  • 测试并设置 (Test-and-Set)
    • 原子地将一个变量设置为某个值, 并返回该变量的旧值
    • 使用时需要不停检测旧值 (自旋), 确定状态因自己而改变
  • 比较并交换 (Compare-and-Swap)
    • 原子地比较一个变量与预期值, 若相等则将其设置为新值
  • 链接的加载 + 条件式存储
    • 先链接加载一个变量的值 (跟踪该变量是否被修改)
    • 然后尝试存储新值, 但仅当该变量自加载后未被其他处理器修改过
  • 获取并增加 (Fetch-and-Add)
    • 原子地将一个变量增加某个值, 并返回该变量的旧值
    • 把返回的旧值当作排队序号, 轮到自己的时候再进入临界区
• 自旋锁会导致线程忙等待, 用 yeild 放弃 CPU (将自己放到就绪队列末)
  • 上下文切换开销较大, 有可能饿死

使用队列来休眠

• 使用休眠 + 唤醒原语, 避免忙等待
• 使用等待队列记录等待的线程, 避免饿死
• 对锁与等待队列的操作需要原子性, 使用内部自旋锁保护
• 加锁
  • 获取内部自旋锁
  • 检查锁状态
  • 获得锁后 / 休眠前释放内部自旋锁
• 解锁
  • 先获取内部自旋锁
  • 再检查等待队列, 如果不为空则唤醒队首线程 (锁的所有权直接传递给它, 无需置零, 避免唤醒一大批线程竞争)
  • 否则释放锁
  • 释放内部自旋锁
• 重点: 要保证释放内部自旋锁与休眠的原子性 (通过释放锁前设置意向实现)

Futex

• Linux 的互斥锁实现
• 一个整数 mutex 承载了所有信息 (正负号代表锁状态 + 绝对值为等待者数量)
• 用进程地址空间 ID + 锁变量的虚拟地址唯一标识一个锁, 哈希到内核中的一个等待队列
• futex_wait(address, expected) 保证检查与休眠的原子性
  • 如果 *address == expected 则休眠
  • 否则立即返回
• 加锁
  • 使用 atomic_bit_test_set 指令尝试直接获取锁 (快路径)
  • 拿不到尝试自旋一会
  • 还拿不到调用 futex_wait 休眠 (慢路径)
• 解锁
  • 使用 atomic_add_zero 指令尝试直接释放锁 (快路径)
  • 如果发现有等待者, 则调用 futex_wake 唤醒指定个等待线程 (慢路径), 醒了还要检查锁状态, 避免竞态条件
• 两阶段锁思想
  • 自旋适合锁持有时间极短的场景
  • 休眠适合锁持有时间长的场景
  • 思想就是结合两者, 先自旋一会, 再休眠

基于锁的数据结构

• 直接全局锁简单但并发性能差 + 拓展性差

懒惰计数器

• 每个线程维护一个本地计数器
• 定期将本地计数器的值合并到全局计数器
• 读取全局计数器时, 需要将所有本地计数器的值刷新到全局

手锁链表

• 每个节点有一个锁
• 遍历链表时, 先获取下一个节点的锁, 再释放当前节点的锁
• 高并发但实际上性能并不高, 因为频繁加锁解锁开销大

队列

• 使用两个锁, 分别保护头指针与尾指针
• 入队时只需要获取尾指针锁, 出队时只需要获取头指针锁
• 需要一个哨兵节点, 避免空队列时头尾指针相同导致的竞态条件

散列表

• 每个桶有一个锁

条件变量

• 共享变量作为条件可以, 但是需要自旋等待
• 条件变量是一个队列, 条件不满足时将线程放入队列休眠, 条件满足时唤醒队列中的任意个线程
• int pthread_cond_wait(pthread_cond_t *cond, pthread_mutex_t *mutex);
  • 释放互斥锁并阻塞等待条件变量被其他线程唤醒
  • 被唤醒后重新获取互斥锁
• int pthread_cond_signal(pthread_cond_t *cond);
  • 唤醒等待该条件变量的一个线程
• int pthread_cond_broadcast(pthread_cond_t *cond);
  • 唤醒等待该条件变量的所有线程
• int pthread_cond_init(pthread_cond_t *cond, const pthread_condattr_t *attr);
  • attr: 指定条件变量属性, 默认可传入 NULL (相当于 pthread_cond_t cond = PTHREAD_COND_INITIALIZER;)
• int pthread_cond_destroy(pthread_cond_t *cond);
  • 销毁条件变量

int done = 0; // 完成状态
pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t cond = PTHREAD_COND_INITIALIZER;

void thr_exit() {
    pthread_mutex_lock(&lock); // 保证修改状态与发信号的原子性 (其实不需要)
    done = 1; // 设置完成状态
    pthread_cond_signal(&cond); // 唤醒等待的线程
    pthread_mutex_unlock(&lock); // 必须在这里解锁, 避免引发竞态条件
}

void *child_thread(void *arg) {
    // 子线程执行的代码
    // ...
    thr_exit(); // 通知父线程
    return NULL;
}

void thr_join() {
    pthread_mutex_lock(&lock); // 保证检查与等待的原子性
    while (done == 0) { // 使用 while 而不是 if 防止虚假唤醒
        pthread_cond_wait(&cond, &lock); // 等待条件变量
    }
    // 父线程工作
    // ...
    pthread_mutex_unlock(&lock);
}

int main() {
    pthread_t thread;
    pthread_create(&thread, NULL, child_thread, NULL); // 创建子线程
    thr_join(); // 等待子线程完成
    return 0;
}

• thr_join() 与 thr_exit() 不一定哪个先运行
  • 如果父线程先运行, 它会进入休眠, 等待子线程唤醒
  • 如果子线程先运行, 它会设置状态并发出信号, 父线程随后运行时会发现状态已满足, 直接退出

生产者-消费者问题 (有界缓冲区问题)

• 一个或多个生产者线程生成数据放入缓冲区, 一个或多个消费者线程从缓冲区取出数据进行处理
• 显然放入的条件是缓冲区未满, 取出的条件是缓冲区非空
  • 休眠的条件刚好相反
• 我们认为唤醒你只代表条件可能满足了, 但不保证一定满足, 所以唤醒后还需要重新检查条件 (用 while 而不是 if)
  • 信号的这种释义常称为 Mesa 语义
• 需要两个条件变量, 分别表示缓冲区非空与非满
  • 用一个会导致唤醒线程时无法区分是生产者还是消费者
• 有的时候确实无法精确唤醒, 但至少要保证唤醒的线程范围完全包含满足条件的线程

信号量

• 信号量是一个整数值 sem_t value
• int sem_init(sem_t *sem, int pshared, unsigned int value);
  • pshared: 指示信号量是否在进程间共享, 0 表示仅在线程间共享
  • value: 初始值
• int sem_destroy(sem_t *sem);
• int sem_wait(sem_t *sem);
  • 将信号量值减 1, 若结果为负则阻塞等待
• int sem_post(sem_t *sem);
  • 将信号量值加 1, 若结果不大于 0 则唤醒一个等待线程
• 实现锁
  • 正信号量表示可用资源的数量
  • 负信号量表示等待的线程数量
  • 也叫二值信号量 (实际上非负值两个, 负值若干个)
• 实现条件变量
  • 初始值为 0
  • 等待条件时调用 sem_wait
  • 满足条件时调用 sem_post
• 实现读写锁
  • 读锁使用一个正信号量表示可用读者数量
  • 写锁使用一个二值信号量表示写锁状态
  • 有很多优化, 如写者等待时阻塞新读者等
• 哲学家问题
  • 哲学家坐在圆桌旁, 需要左右两把叉子才能吃饭
  • 实现非常简单, 问题是可能导致死锁
  • 前 \(n-1\) 个哲学家先拿起左边的叉子, 最后一个哲学家先尝试拿起右边的叉子即可

信号量实现有界缓冲区

sem_t empty; // 空缓冲区数量
sem_t full; // 满缓冲区数量
pthread_mutex_t lock ; // 保护缓冲区的互斥锁

// add_item_to_buffer 和 remove_item_from_buffer 分别实现向缓冲区添加和移除数据的操作, 需要它们自己维护索引

void producer(void *arg) {
    while (true) {
        int item = produce_item(); // 生产数据
        sem_wait(&empty); // 等待空缓冲区
        sem_wait(&lock); // 获取缓冲区锁
        add_item_to_buffer(item); // 放入缓冲区
        sem_post(&lock); // 释放缓冲区锁
        sem_post(&full); // 增加满缓冲区数量
    }
}

void consumer(void *arg) {
    while (true) {
        sem_wait(&full); // 等待满缓冲区
        sem_wait(&lock); // 获取缓冲区锁
        int item = remove_item_from_buffer(); // 取出数据
        sem_post(&lock); // 释放缓冲区锁
        sem_post(&empty); // 增加空缓冲区数量
        consume_item(item); // 处理数据
    }
}

int main() {
    sem_init(&empty, 0, BUFFER_SIZE); // 初始化空缓冲区数量
    sem_init(&full, 0, 0); // 初始化满缓冲区数量
    sem_init(&lock, 0, 1); // 初始化互斥锁
    // 创建生产者与消费者线程
    // ...
    return 0;
}

实现信号量

#include <pthread.h>

// 自定义信号量结构体定义
typedef struct {
    int count; // 当前可用的资源计数
    pthread_cond_t condition; // 用于阻塞和唤醒线程的条件变量
    pthread_mutex_t lock; // 保护计数器原子操作的互斥锁
} semaphore_t;

void sem_init(semaphore_t *s, int value) {
    s->count = value;
    pthread_cond_init(&s->condition, NULL);
    pthread_mutex_init(&s->lock, NULL);
}

void sem_wait(semaphore_t *s) {
    // 操作前先获取互斥锁, 确保对 count 的访问是线程安全的
    pthread_mutex_lock(&s->lock);

    // 使用 while 循环检查资源是否可用 (防止虚假唤醒)
    // 如果没有可用资源 (count <= 0), 线程释放锁并进入等待状态
    while (s->count <= 0) {
        pthread_cond_wait(&s->condition, &s->lock);
    }

    // 成功获得资源, 计数减 1
    s->count--;

    // 释放互斥锁
    pthread_mutex_unlock(&s->lock);
}

void sem_post(semaphore_t *s) {
    // 操作前先获取互斥锁
    pthread_mutex_lock(&s->lock);

    // 增加资源计数
    s->count++;

    // 发出信号, 唤醒一个正在等待该条件的线程
    // 如果没有线程在等待, 此操作无副作用
    pthread_cond_signal(&s->condition);

    // 释放互斥锁
    pthread_mutex_unlock(&s->lock);
}

死锁

• 死锁预防 (常用)
  • 破坏互斥条件: 乐观锁
  • 破坏持有并等待条件: 进程在获取所有资源前不持有任何资源 (抢锁需要持有全局锁)
  • 破坏非抢占条件: 没一次性获取到所有资源时释放已持有的资源 (常用)
    • 可能导致活锁, 需要引入随机等待时间
  • 破坏循环等待条件: 为每个资源分配一个唯一编号, 进程必须按编号顺序请求资源 (常用)
• 死锁避免
  • 银行家算法
  • 想的挺好, 但实际开销较大并且很难清楚地知道每个进程的资源需求
• 死锁的检查和恢复 (常用)

基于事件的并发

• 不用线程, 而是使用事件循环实现并发
  • 核心问题是了解事件的到达
  • 操作系统提供 API 检查一组 I/O 描述符的状态 -int select(int nfds, fd_set *readfds, fd_set *writefds, fd_set *errorfds, struct timeval *timeout);
  • nfds: 描述符范围 (\(0\) 到 nfds-1)
  • readfds: 关心可读事件的描述符集合
  • writefds: 关心可写事件的描述符集合
  • errorfds: 关心异常事件的描述符集合
  • timeout: 超时时间
    • NULL: 无限阻塞
    • 一个全为 \(0\) 的 timeval 结构体: 无论否有事件立即返回
    • 代表特定时间的 timeval 结构体: 等待指定时间后超时返回
• 工作流程
  • 初始化: 清空描述符集合 (FD_ZERO)
  • 注册: 将所有感兴趣的描述符加入集合 (FD_SET)
  • 查询: 调用 select()
  • 处理: select 返回后, 循环检查哪个描述符被标记为就绪 (FD_ISSET), 然后处理数据
• 优势
  • 避免了线程切换开销, 无并发错误
• 问题
  • 基于事件的循环绝对不能使用阻塞调用, 需要使用非阻塞 I/O
  • 状态生命周期需要手动管理, 编程复杂度极高
  • 多核 CPU 扩展性差, 需要运行多个事件循环, 又回到锁的问题
  • 隐式阻塞 (如 Page Fault) 难以避免
• 现代高性能服务器中通常采用混合模型
  • 使用事件循环处理高并发网络连接
  • 配合线程池来处理阻塞的磁盘 I/O

持久化

I/O 设备

• CPU 通过内存总线与内存通信, 通过 I/O 总线与外设通信 (包括快速的通用 I/O 总线与慢速的外设 I/O 总线)
• 标准 I/O 协议
  • 设备被建模为接口与内部, 其中接口包括三个寄存器 (状态寄存器, 控制寄存器, 数据寄存器)
  • 轮询状态寄存器, 确认设备就绪
  • 通过数据寄存器读写数据, 设置上下文
  • 向控制寄存器写入命令, 启动操作
  • 轮询状态寄存器, 确认操作完成
  • 轮询开销大, CPU 忙等待
• 优化
  • 用中断代替轮询, 设备就绪或操作完成时触发中断, CPU 响应中断处理数据
  • 高速设备可以先轮询一段时间, 再使用中断
  • 网络设备数据到达非常频繁, 考虑将多个数据包合并为一个中断
• DMA 直接存储器访问
  • DMA 引擎是系统中的一个特殊设备, 可以协调完成内存和设备间的数据传递
  • 由操作系统配置 DMA 引擎, 指定源地址, 目标地址, 传输大小等信息
  • 启动 DMA 传输后, CPU 可以继续执行其他任务
  • DMA 传输完成后, 触发中断通知 CPU
• 设备交互
  • 通过硬件提供操作设备端口的指令
  • 通过内存映射 I/O, 将设备寄存器映射到内存地址空间
  • 当然, 我们通过驱动程序屏蔽这些细节

磁盘驱动器

• 见硬件软件接口
• \(\text{访问时间} = \text{寻道时间} + \text{旋转延迟} + \text{传输时间}\)
• 磁盘调度算法
  • 先来先服务 (FCFS): 简单, 公平, 但寻道时间长
  • 最短寻道时间优先 (SSTF): 选择距离当前磁头位置最近的请求, 减少寻道时间, 但可能导致饥饿
  • 电梯算法 (SCAN): 磁头在一个方向上移动, 处理沿途的请求, 到达末端后反向, 减少寻道时间, 对中间没那么公平
  • 循环电梯算法 (C-SCAN): 到达末端后跳回起点, 更公平
  • LOOK 与 C-LOOK: 类似 SCAN 与 C-SCAN, 但需要反向 / 归位时直接移动到下一个请求的位置
• 系统接到 I/O 请求后, 会等待一段时间以合并更多请求, 然后排序后发送给磁盘
• 磁盘会利用这些信息优化寻道, 或合并相邻请求

廉价冗余磁盘阵列 (RAID)

• 通过多块磁盘协同工作提高性能与可靠性
• RAID 包含 CPU(校验), 内存 (缓存) 与多块磁盘
• RAID 通过加入少量非易失性存储保存预写日志, 保证多盘数据一致
• RAID 级别
  • RAID 0: 条带化, 提高性能, 无冗余
  • RAID 1: 镜像, 提高可靠性, 无性能提升
  • RAID 4: 带奇偶校验的条带化, 提高性能与可靠性
    • 将其中一块磁盘作为专用的奇偶校验盘
  • RAID 5: 旋转奇偶校验的条带化, 提高性能与可靠性
    • 将奇偶校验信息分布在所有磁盘上, 避免奇偶校验盘瓶颈

文件与目录

• 文件就是线性字节数组, 有一个唯一的文件标识 (inode 号)
• 目录也有 inode 号, 内容是子文件文件名到 inode 号的映射表
• 文件打开后会返回一个文件描述符, 对应内核中的一个文件表项
  • 文件表项保存文件偏移量, 文件状态与引用计数等信息
  • 系统内所有对该文件的引用为零时, 文件表项被销毁, 缓存内容被异步写回磁盘
  • int fsync(int fd) 强制将文件内容写回磁盘, 成功返回 0, 出错返回 -1
  • int fdatasync(int fd) 只写回文件数据, 不写回元数据
  • void sync(void) 将所有文件系统的修改写回磁盘
• 文件表项是内核中的一个数据结构
  • st_dev, 设备号
  • st_ino, inode 号
  • st_rdev, 设备特殊文件的设备号
  • st_mode, 文件类型与权限
  • st_nlink, 硬链接数量
  • st_uid, 所有者用户 ID
  • st_gid, 所有者组 ID
  • st_size, 文件大小 (字节)
  • st_blocks, 文件占用的块数
  • st_atime, 最后访问时间
  • st_mtime, 最后修改时间
  • st_ctime, inode 最后修改时间
• int open(const char *pathname, int flags);
  • 返回文件描述符
  • pathname: 文件路径
  • flags: 打开选项
    • O_RDONLY: 只读
    • O_WRONLY: 只写
    • O_RDWR: 读写
    • O_CREAT: 文件不存在时创建
    • O_TRUNC: 打开时清空文件
    • O_APPEND: 追加写
    • O_EXCL: 与 O_CREAT 一起使用, 文件存在时失败
• ssize_t read(int fd, void *buf, size_t count);
  • 返回实际读取的字节数, 出错返回 -1
  • 从文件描述符 fd 指定的文件中读取最多 count 字节到缓冲区 buf
• ssize_t write(int fd, const void *buf, size_t count);
  • 返回实际写入的字节数, 出错返回 -1
  • 将缓冲区 buf 中的最多 count 字节写入文件描述符 fd 指定的文件
• off_t lseek(int fd, off_t offset, int whence);
  • 返回新的文件偏移量, 出错返回 -1
  • 将文件描述符 fd 指定的文件的偏移量设置为 offset (相对于 whence)
  • whence:
    • SEEK_SET: 文件开头
    • SEEK_CUR: 当前偏移量
    • SEEK_END: 文件结尾
• 目录
  • 对目录的读写类似文件, 但内容是目录项
  • 硬链接, 在当前目录中创建一个指向同一 inode 的目录项
  • 软链接, 一个特殊的文件, 内容是另一个文件的路径
  • 所以删除文件本质就是 unlink() 减少 inode 的引用计数, 直到为零时删除文件数据与元数据
  • 上级目录与当前目录分别用名为 .. 与 . 的目录项表示
  • 目录项
    • inode 号
    • 记录长度
    • 文件名长度
    • 文件名

文件系统

• 磁盘块是文件系统管理磁盘的基本单位, 通常为 4KB
• 磁盘被划分为, 数据, 元数据, 分配记录, 超级块
  • 数据块存储文件数据
  • 元数据块存储 inode 表
  • 分配记录块存储代表是否分配的位图
  • 超级块存储文件系统的整体信息
• inode 本身是跳转表实现, 存储文件元数据
  • mode, \(2\) 字节, 权限
  • uid, \(2\) 字节, 所有者用户 ID
  • size, \(4\) 字节, 文件大小 (字节)
  • time, \(4\) 字节, 最后访问时间
  • ctime, \(4\) 字节, 创建时间
  • mtime, \(4\) 字节, 最后修改时间
  • dtime, \(4\) 字节, inode 被删除时间
  • gid, \(2\) 字节, 所有者组 ID
  • links_count, \(2\) 字节, 硬链接数量
  • blocks, \(4\) 字节, 文件占用的块数
  • block[15], \(4*15\) 字节, 直接与间接块指针
  • 还有操作系统 / 文件系统具体实现可能添加的扩展字段
• 多级索引
  • 块指针指向间接块, 间接块中存储更多块指针
  • 直接块指针 (12 个): 直接指向数据块
  • 一级间接块指针 (1 个): 指向一个间接块, 该块中存储多个数据块指针
  • 二级间接块指针 (1 个): 指向一个间接块, 该块中存储多个一级间接块指针
  • 三级间接块指针 (1 个): 指向一个间接块, 该块中存储多个二级间接块指针
  • 因为小文件更常见
• 缓存
  • 文件系统缓存文件数据与元数据, 减少磁盘访问
  • 写入延迟, 写入缓存后等待一段时间再写回磁盘
    • 写入调度
    • 批处理, 例如一次更新多个元数据

局部性和快速文件系统

• 为了解决传统 UNIX 文件系统性能差的问题, 快速文件系统开始考虑磁盘的物理特性, 优化文件与目录的布局 (磁盘意识)
• 磁盘划分为若干个块组 (微缩的文件系统)
  • 相关的数据放在同一个组内
  • 每个组包含超级块副本, 位图, inode 区域, 数据块区域, 组描述符表 (GDT, 描述该组的元数据位置)
  • inode 需要除以块组数量取余分配到不同组
• 分配策略
  • 目录放置在块组中空闲 inode 较多并且分配目录数较少的组
  • 文件数据块放置在与其 inode 同一组内
  • 同一目录下的文件尽量放在同一组内
  • 因为 \(40%\) 的文件访问是针对同一个文件或同一个目录下的文件
• 大文件处理
  • 大文件的直接块放在 inode 所在组内
  • 间接块指针放在不同组内, 避免挤占空间 (找得慢, 但是多, 摊销成本)

崩溃一致性: FSCK 和日志

• 文件系统崩溃后可能导致元数据不一致
• 一次写入包括数据块, inode 块, 位图块
  • 只有数据块写入成功, 无所谓
  • 只有 inode 块写入成功, 导致文件系统不一致 + 垃圾数据
  • 只有位图块写入成功, 导致块泄露
  • 只有 inode 块与位图块写入成功, 导致文件系统一致, 但是垃圾数据
  • 只有数据块与位图块写入成功, 导致块泄露
  • 只有数据块与 inode 块写入成功, 导致文件系统不一致 (数据可能被覆盖)
• FSCK 文件系统检查程序
  • 扫描整个文件系统, 检查并修复不一致 + 块泄露
  • 垃圾数据无法发现, 而且太慢
• 日志文件系统
  • 将所有修改先写入日志 (顺序写入, 快)
  • 崩溃后只需回放日志即可恢复一致性
  • 超级块后面有一个专门的日志区域
  • 数据日志
    • 记录所有元数据与用户数据的修改
    • 日志写入
    • 写入事务结束块
    • 加检查点 (将日志内容写回文件系统)
    • 释放日志空间
    • 最安全但最慢
  • 元数据日志
    • 只记录元数据的修改
    • 用户数据直接写入最终位置
    • 再写入元数据日志
    • 提交事务结束块
    • 加检查点 (将元数据写回文件系统)
    • 释放日志空间
  • 为什么日志写入需要事务结束块
    • 只有对单一块的写入是原子操作
    • 磁盘写入可能乱序
    • 事务结束块通过写屏障标记日志完整性
    • 因为有些磁盘不支持写屏障, ext4 引入校验和机制
  • 块复用
    • 日志写入时, 可能会复用之前日志中使用过的块
    • 在日志中写入撤销记录 (对该块之前的日志无效)
  • 软更新: 算法上保证元数据写入顺序正确, 避免日志开销
  • 写时复制: 修改数据时创建数据副本, 避免覆盖旧数据, 随后更新元数据指向新数据

日志结构文件系统 (LFS)

• 旧文件系统跟不上时代
  • 内存越来越大, 可以缓存更多数据
  • 顺序 / 随机读写差距越来越大
  • 旧的策略表现不佳, 尤其小写入太多, 并且写入需要随机寻道
  • RAID 4/5 小写入问题尤其明显
• LFS 思想, 追加写入 + 写时复制 + 快照机制的雏形
  • 将所有数据与元数据的更改写入一个内存段中
  • 段满后顺序写入磁盘, 并只写空闲位置
  • 为什么需要攒着: 磁盘会旋转, 必须同时写入多个块才能保证真正顺序写入 (而不是下一圈才能写入)
• inode 一直在变化
  • 引入 iMap, 保存 inode 号到 inode 位置的映射
  • 奇葩的是, iMap, inode, 数据块都写在一起, 所以还得想办法找到 iMap 的位置
    • 应该是因为整个 iMap 太大, 放在一起不现实, 所以分散存储 (摊销更新成本)
    • 磁盘上固定一个检查点区域, 保存最新的 inode 映射表位置 (\(30s\) 更新一次)
• 读取文件流程
  • 读取检查点区域, 找到最新的 inode 映射表位置
  • 读取整个 iMap, 根据 inode 号找到 inode 位置
  • 根据 inode 位置读取 inode
  • 根据 inode 读取数据块
• 递归更新问题
  • 目录存的是文件名到 inode 的映射, 因为 inode 一直在变化, 所以目录也得更新, 这会递归更新到根目录
  • 目录里只存 inode 号, inode 号不变, 目录不需要更新
• 垃圾回收机制
  • 因为 LFS 只追加写入, 所以旧数据块会变成垃圾
  • 必须一次性清理掉一个段的垃圾, 否则会变成随机写入
  • 读入若干旧段, 挑出活块, 紧凑打包写入新段, 回收旧段
  • 通过版本号检测块是死是活
  • 清理垃圾多的段还是垃圾少的段
    • 冷段 (数据稳定): 优先清理, 整理好后长期受益
    • 热段 (数据频繁修改): 推迟清理, 等块自然死绝
• 崩溃恢复
  • 段本身就是日志
  • 磁盘首尾各存一个检查点区域 (CR)
  • 写入 CR 时, 先写头时间戳, 再写内容, 最后写尾时间戳
  • 启动时检查两个 CR, 选择旧的那个
  • 这过程中的新段怎么办
    • LFS 通过前滚恢复这些新段
    • 从 CR 指向的末尾开始, 向后读取磁盘
    • 用校验和确定哪些段是完整写入的
    • 段的段摘要块告诉我们这是哪些文件的更新, 重放这些更新, 修正 CR 指向的 Imap
• 缺点
  • 文件系统碎片化严重, 读取性能差
  • 需要频繁垃圾回收
    • WAFL 等现代系统: 将旧数据的管理转化为快照机制, 废物利用

数据完整性和保护

• 部分磁盘故障
  • 潜在扇区错误, 扇区损坏导致数据无法读取
  • 块讹误, 磁盘无法发现的各种错误, 如位翻转
• 处理潜在扇区错误, 尝试用冗余数据恢复
• 检测块讹误
  • 每个块添加校验和
    • 异或
    • 加法
    • 循环冗余校验 (CRC)
  • 读取时验证校验和
  • 校验失败使用冗余数据恢复 / 报告错误
• 处理一些常见错误
  • 错误位置的写入: 在校验和计算中加入块地址
  • 丢失的写入: 写入后立即读 / 在 inode 中保存一份校验和

分布式

• 如何基于不可靠的网络与存储构建可靠的分布式系统
• 分布式系统必须端到端考虑可靠性 (一切皆有可能失败)
• 分布式共享内存 (DSM)
  • 让不同机器共享同一个虚拟地址空间, 利用 OS 的虚拟内存缺页中断来获取远程页面
  • 失败原因: 故障处理难 (地址空间在变化), 性能隐患 (误以为是本地内存访问)
• 远程过程调用 (RPC)
  • 让在远程机器上执行代码就像调用本地函数一样简单, 成功
  • 存根生成器
    • 客户端存根假装是本地函数, 实际只负责封送 / 序列化, 解封送 / 反序列化
    • 服务器存根才是真正调用远程函数的代码 (更像 API)
  • 运行时库
    • 处理命名 (找到服务器)
    • 选择传输协议
    • 确定序列列化协议
    • 处理特殊场景 (keep alive, 分片, 异步)

NFSV2 网络文件系统

• NFS 希望程序能安然的崩溃重启, 不需要恢复复杂的状态
  • 换言之, NFS 使用无状态的协议, 所有信息都必须包含在同一个请求中
• 文件句柄作为文件的唯一标识符
  • 卷标识符 + Inode 号 + 世代号
  • 世代号用于解决 Inode 复用问题
• 操作
  • LOOKUP: 获取文件名 -> 文件句柄
    • 分步解析路径, /a/b/c 需要先获取 / 的 a 句柄, 再获取 a 的 b 句柄, 最后获取 b 的 c 句柄
  • READ/WRITE: 读写文件数据, 需要文件句柄, 偏移量, 长度
    • 分片, 信息存在请求的 Cookie 中
  • GETATTR: 获取文件属性, 服务于缓存
  • 客户端必须维护文件描述符到文件句柄的映射表 + 每个文件的当前偏移量
  • 服务端采用线程池处理请求
• 幂等性
  • READ 是幂等的
  • WRITE 也是幂等的, 因为使用绝对偏移量 (无状态的好处)
  • mkdir 不是幂等的
• 客户端缓存, 需要解决可见性
  • 关闭时刷新, 文件关闭时把缓存写回服务器
  • 使用前检查, 读缓存前先检查服务器文件修改时间
• NFS 服务器必须在数据真正写入磁盘后, 才能向客户端发送成功的回复

AFS Andrew 文件系统

• 核心目标是解决 NFS 客户端的使用前检查机制导致服务器负载过重 (可扩展性问题)
• NFS 的问题
  • 解析路径 / 检查缓存可用性 / 小块读写频繁访问服务器
  • 缓存不一致
  • 为了防止崩溃恢复, 必须在数据真正写入磁盘后回复客户端
  • 并发冲突, 不知道另一个客户端对文件的使用
• 全文件缓存
  • 当客户端打开文件时把整个文件拉取到本地磁盘
  • 避免频繁小块读写对服务器的访问
  • 变相解决必须在数据真正写入磁盘后回复客户端 (写入的次数大大减少)
  • AFS 赌的
• 回调
  • 服务端文件修改后主动通知客户端缓存失效
  • 避免频繁检查缓存可用性
• 解析路径时, 客户端缓存目录内容, 直接使用 FID 访问文件
• 解决缓存一致性
  • 同一机器的多个客户端实例共享缓存
  • 最后关闭者胜出
  • 收到新版本回调通知所有缓存失效
  • 崩溃后客户端重新验证所有缓存
• 解决并发冲突
  • 就是乐观并发控制, 冲突时让最后一个写入者胜出
• AFS 赌的场景
  • 文件不经常共享, AFS 的缓存开销不小, 并且并发冲突代价较高
  • 大文件顺序读写, 全量缓存开销平摊下来不算太高
  • 文件大多很小, 全量缓存开销不大

虚拟机

虚拟机 CPU 虚拟化

• 让多个 Guest OS 共享同一个物理 CPU, 同时保证 VMM 对机器的绝对控制
• 类似于操作系统对进程的管理, VMM 对虚拟机进行管理
• 机器切换类似于上下文切换, 但是需要保存整个机器状态
• 拦截特权操作, VMM 代为执行
• 虚拟机上的进程进行系统调用时, 陷阱会先进入 VMM, VMM 再转发给 Guest OS
  • 此时 Guest OS 运行在降低的特权级别, 不能直接执行特权指令
  • 这时 Guest OS 执行特权指令会再次陷入 VMM, VMM 代为执行
• 中间特权级
  • Guest OS 不能真持有内核模式, 也不能完全运行在用户模式
  • 一些 CPU 支持中间特权级 (如 MIPS 的 Supervisor Mode, x86 的 Ring 1)
  • 否则 VMM 需要通过修改页表保护位, 在切换到 Guest OS 时临时开放内核数据的读写权限

虚拟机内存虚拟化

• 通过虚拟地址与机器地址中间维护一层 Guest OS 认为的物理地址让多个 Guest OS 共享物理内存
• 就是两层页表
• 所有对页表 / TLB 的操作都需要 VMM 代理
  • 有时候索性软件模拟 TLB
• 有些硬件直接遍历页表, VMM 需要维护影子页表, 让硬件直接看见最终的虚拟地址到机器地址映射

信息沟

• VMM 不知道 Guest OS 的意图
  • Guest OS 空闲循环时, VMM 以为它很忙
  • VMM 对硬件资源的管理与 Guest OS 的管理重复
• 两个方案
  • 推断, VMM 猜测 OS 的行为
  • 半虚拟化, 修改 Guest OS 代码让它知道自己运行在虚拟机上