这些内容主要目的是从老师(郭力维)的PPT中抽离出可能的知识和考点，梳理中学习

操作系统

OS简史与概览

回顾

Recap:什么是操作系统？
- 广义：系统软件->软件基础设施
- 狭义：管理计算机硬件服务于应用的软件
Recap:计算机系统模型
- 静态视角：五大主要部件
  - CPU：中央处理单元
  - Mem：内存
  - Bus：互联总线
  - IO：输入输出设备
  - Storage：存储设备
- 两种架构：
  - 冯诺依曼架构：指令与数据同存储共总线
  - 哈佛架构：指令与数据分存储与总线
  - 在实现上冯诺依曼更简洁，但是实现后速度上哈佛一般更具优势
Recap：CPU执行模型
- 实质上就是在没有停止时循环的取指译码执行
Recap：计算机指令
- 种类上：CISC与RISC
- 形式上都是二进制数据

OS进化史

串行
- 操作系统尚不存在，用户直接与机器交互
批处理
- “操作员”将提交上来的任务按批整理，交由主机执行
- 任务执行完毕再通知操作员
- 一种简单、粗粒度的调度方式
多道批处理系统
- 处理器可以在不同运行的任务中切换
- IO包括：从磁盘、软盘等介质中读取文件
- 类似异步执行，大大提高任务吞吐速度
Memory Wall
- CPU性能提升速度远大于存储设备性能提升速度
- 处理器速度再怎么提高也无法提升程序性能
分时系统
- 对多道批处理的逻辑延申，资源更细力度的划分、调度
- 为用户程序划分的系统资源-时间片
- 为更短的响应时间设计（虽然切换进程开销较大，但为了防止“饿死”情况，必须进行进程轮转执行）
- 分时系统是现代OS的基石

现代OS概览

OS的组成
- 进程管理
- 内存管理
- 存储管理
- 设备管理
- 文件系统
- IO子系统
- 网络工作栈
- Shell
- …
进程
- 程序在CPU上运行的实例
- 进程提供的抽象：
  - 线程：进程内线性指令序列（每一个进程内可以有多个线程）
  - 地址空间：所有进程能访问道的内存
    - 高地址存储内核和栈
    - 低地址存储堆和进程代码
    - 因为用户程序倾向于编写在低地址，故安排内核于高地址
    - 虚拟化内存，运行地址空间大于可用内存
- 进程同时是资源与安全的主体
进程管理
- 进程的创建与删除
- 进程的挂起和恢复
- 进程机制
  - 进程通讯
  - 进程同步
- PCB：OS用于挂历进程的内部数据结构
内存
- 易失性设备
- 保持程序状态的关键
内存管理
- 按需分配、释放内存空间
- 保护
  - 防止进程间非法访问内存
- 支持比物理内存更大的地址空间
存储管理
- 为存储设备提供编程接口
- 管理磁盘空间
- 调度磁盘请求
文件管理
- 文件：一些数据的集合
- 文件与文件夹的创建和删除
- 文件到硬盘的映射
- 文件和文件夹的基本操作
- 文件的共享与保护
I/O子系统管理
- 适配多种多样的IO设备
- 隐藏IO设备的独特性，使用共性接口
- IO子系统
  - 设备文件作统一抽象
  - 设备驱动用来驱动特定硬件
    启动过程
Boot机器是如何启动的
- 主板上电
- CPU上电
- BIOS启动
- BootLoader启动
- 加载操作系统
- 机器启动完成

BIOS

BIOS（基本输入输出系统）
- 固件
- 存在于主板的ROM中
- 上电后运行的第一个程序
基本流程
- 开机自检
- 识别连接的硬件并初始化
- 为ACPI设置硬件描述（定义BIOS和OS的硬件接口）
- 从硬盘中把bootloader加载到内存中（往往是第一个扇区）
- 将CPU控制权转到bootloader
  BootLoader
Bootloader
- 软件，操作系统的一部分
- 加载内核映像
- 上电后第一个用户自定义的软件
基本流程
- 检查内核映像是否正确
- 把内核从磁盘（其实也可用是网络或其余介质）加载到内存
- 将控制转移到操作系统
  UEFI
UEFI
- 可扩展固件接口
- BIOS的继任者

进程

编译流程

编译
链接
- 静态链接
  - 分别编译成目标文件
  - 链接器将目标链接为可执行文件
- 动态链接
ELF（可执行文件结构）
- header（文件头）：“目录”、metadata
- sections（章节）：
  - text：代码段
  - data：只读数据段
  - rodata：数据段
  - bss：未初始化的全局变量
- segments（内存排列）
Symbols（符号）
- 符号是计算机程序的根本基础之一
- 编译器通过符号名称定位变量、函数（重定位）

程序装载

进程
- 静态的可执行文件被操作系统加载运行
- 程序运行的实例
- 特点
  - 进程间隔离（与OS也隔离）
  - 专属地址空间
  - 单独上下文
  - 一个或多个线程
进程与程序的区别
- 程序：静态视角、源代码/二进制
- 进程：现在进行时、执行中的程序实例
PCB（进程控制块）
- PID
- 进程状态
- 进程优先级
- 程序计数器
- 内存相关信息
- 寄存器信息
- IO状态信息
- 杂项信息
双模式
- 基于硬件的隔离与保护机制
- 硬件机制
  - 特权指令
    - 能影响其他进程的指令都可能是特权指令
    - 内核为用户代为执行
    - 为异常主动检测或终止
    - 特权等级多层分级
  - 内存保护
    - 内存虚拟化（对地址的访问进行控制）
    - 分段与分页式虚拟化
  - 时钟中断
    - 防止程序长期不退出使得OS无法打断
    - 在时钟中断发生时OS可做调度决策
  - 状态转换
    - 用户态到内核态
      - 异常：处理器遇到意料之外的情况
      - 中断：外部事务的异步信号
      - 自陷：用户请求系统调用
    - 内核态到用户态
      - 新进程的创建
      - 从中断/异常/自陷中恢复
      - 上下文切换到其他进程（调度器决定）

模式转换

中断

现代操作系统都是由中断驱动的
中断的处理流程
- CPU自动屏蔽中断源
- CPU自动保存被中断的指令地址
- CPU将控制移交给中断处理程序
- 中断处理程序在栈上保存CPU状态
- 中断处理程序处理中断
- 解除中断屏蔽
- 恢复CPU状态
- 恢复被中断的指令
中断处理程序
- 中断向量表（IVT）
- 特殊寄存器指向IVT地址，每个IVT元素指向中断服务程序（ISR）
中断屏蔽
- 防止无休止的嵌套中断
- 实现原子代码区域/临界区
- 中断类型：
  - 可屏蔽中断：所有软件异常和系统调用以及部分硬件异常
  - 不可屏蔽中断：部分硬件异常
中断栈（IRQ stack）
- 保存中断程序状态的特殊内核栈
- 每个核私有，在内核内存中
- 防止全盘信任用户栈内存
IRQ分步处理（软中断）
- 快速保存恢复上下文、应答中断
- 耗时较多的复杂任务
- 防止中断耗费时间过长影响交互性
中断处理对于用户进程不可见
中断遵循安全的设计理念
OS接口&系统调用

POSIX

可移植操作系统接口（POSIX）
- UNIX OSes的一套标准，针对系统调用
libc（标准C语言库）
- POSIX APIs + 标准C函数
- 应用程序调用来进行系统调用
- glibc：GNU C library

多进程接口

fork()
- 创建一份父进程的副本并运行
- 在子进程中返回0
- 在父进程中返回子进程PID
exec()
- 加载并执行对应程序
- 不创建新进程

常见搭配

int pid = fork();
if (pid==0){
  exec("foo");
}else{
  exec("bar");
}

IO接口

文件描述符（fd）
- 操作系统用来唯一标识已打开的文件的整型数字
- 每个进程都有一个文件描述符表
  - 以fd为索引
  - 包含文件存储路径、状态、如何访问等
- 一个文件可被不同进程打开多次
所有IO的统一接口
- open，close，，read，write
- 使用前必须打开文件（open）
- 地址寻址
- 内核对读写进行缓冲
- 显式关闭文件
可扩展的跨进程通讯（IPC）
- 管道：一个有两个文件描述符的内核缓冲区
- pipe（ind fd[2]）创建
  - fd[0] 读
  - fd[1] 写
    系统调用
系统调用需要抵御用户态的攻击/错误
使用stub 检查，再检查
线程

线程抽象
并发（concurrency）
- 某一段时间多个任务同时进行
并行（parallelism）
- 一个时间点多个任务同时进行
串行
- 任务按顺序执行，不会同时进行
线程的抽象
- 每个线程执行一系列指令（赋值、条件语句、循环、过程等），就像是顺序编程模型
- 在任意时刻，操作系统可以运行、暂停或唤醒一个线程
- 线程是操作系统的最小调度单元
- 线程是操作系统的分配资源的最小单元
- 同一进程的线程：
  - 共享内存地址空间（数据、代码、文件）
  - 不共享执行上下文（寄存器、栈）
- 线程的执行速度具有不可预测性
  - 进程中线程间的切换对于程序透明（调度器的职责0
线程与进程的区别
- 并发性
  - 两者均可由操作系统调度
- 上下文
  - 不同进程/线程都有各自的上下文，调度都会带来上下文切换
- 定义
  - 线程可作任务调度的单个指令执行序列，是最小调度单元
  - 执行中的程序，资源的主体
- 资源
  - 线程占用资源少
  - 进程占用资源多
- 内存
  - 同进程中的线程共享地址空间
  - 进程间内存相互隔离
- 通信
  - 线程间通信简单、快速
  - 进程间通信复杂且缓慢
线程API
- pthread_create
  - 创建指定地址属性的进程thread，并调用进程并发执行
- pthread_join
  - 等待由thread指定的线程终止，如果已经终止就立刻返回其数据
  - 指定的线程必须是可连接的，有些不知道什么时候停和无所谓停不停的线程往往被设计为不可连接
- pthread_yield
  - 进程自愿放弃处理器资源并让其他进程运行
- pthread_exit
  - 终止调用进程并返回结果
进程的生命周期
- 五状态
  - 初始（init）
  - 就绪（runnable）
  - 等待（waiting）
  - 执行（running）
  - 终止（dead）
- 七状态
  - 新建（new）
  - 就绪（ready）
  - 阻塞（blocked）
  - 执行（running）
  - 退出（exit）
  - 就绪挂起（ready/suspend）
  - 阻塞挂起（blocked/suspend）
  - 挂起一般和释放资源有关，是比阻塞更强的等待状态，恢复开销较大
调度（前瞻性的讲解）
- 调度主要的两种方式
  - 非抢占式：一直运行到结束或阻塞
  - 抢占式：内核根据时间片来抢占

线程实现

线程数据结构
- 线程控制块（TCB）
  - 栈指针：每个线程都有自己的栈
  - 一组寄存器
    - 通用寄存器：保存运算中间值
    - 特殊寄存器：PC&SP（栈指针）
  - 元数据
    - Thread ID
    - 调度优先级
    - 状态
  - 栈大小：
    - 内核态：往往比较小，Linux x86的内核栈大小为8KB
    - 用户态：跟库函数设置有关
      - 大多数库都有栈溢出检测
      - 一些语言可以在运行时动态调整大小，例如Go
- 共享状态
  - 代码
  - 全局变量、堆
OS不强制实现线程间隔离
- 同一个进程中，如果线程A的一个指针指向线程B的栈上的地址，OS不作访问限制，可以访问与修改
线程实现
- 两种类型：用户线程和内核线程
- 内核线程
  - 内核线程可以被操作系统调度到不同CPU核心上同时运行
  - 内核线程阻塞时，不会把整个流程里的所有执行流动卡死
  - 内核线程由OS调度器管理
- 用户线程
  - 可由用户自行创建，不需要内核协助
  - 一般来讲不在核之间做切换
- 线程销毁
  - 线程通常不应该由自我销毁，因为这无法彻底释放上下文（尤其是栈）
  - 线程通常通过标记自己的线程状态（TCB置为finished）并交由其他线程协助销毁
多线程进程实现
- 实现多线程的方法
  - 通过内核进程（each thread op traps into kernel）
  - 纯用户态（无内核支持）
    - 在用户态维护所有的状态
    - 由自己决定线程的运行
    - 线程操作变为函数调用
  - 混合模式（hybrid mode）
    - 混合模式线程join：开销更小，无需系统调用
    - 调度器激活（scheduler activation）：新版Windows使用，当用户态线程在系统调用中阻塞时，内核通知用户态调度器，从而将阻塞的线程调度出去，最大化利用计算资源
线程创建的开销
- 线程创建需要时间
  - 需要在内核中初始化大量数据结构
  - 内核用户态的切换
- 线程池的使用
  - 预分配
  - 用户态程序自行管理
    - 无模式切换开销
    - 可以直接回收旧线程无需重新创建
  - Cons
    - 复用资源带来的状态残余核上下文污染
    - 不同时长的任务相互挤占使得短任务饿死
    - 线程池的大小初始化难以确认
      地址翻译
      
      地址翻译的概念
虚拟内存的必要性
- 便于多程序和多用户使用内存
- 程序间的内存隔离，即内存的保护
- 虚拟内存可以申请比实际物理内存更多的空间
地址翻译
- 定义：虚拟内存地址到物理内存地址的转换
- 控制进程对于内存/地址的视角
- 实现方法
  - 编译器支持
    - 编译器动态或静态的为程序适配地址的翻译
    - 速率较慢且不具移植性
  - 硬件支持
    - 硬件根据内存中的表执行翻译
    - 快速且常用
- 用途
  - 地址空间的隔离
  - 高效进程间通信（共享内存）
  - 共享代码/数据段（例如库函数）
  - 缓存管理
  - 程序断点机制的实现
  - 内存映射文件（无需搬运整块）
  - 按需分页的虚拟内存，使得内存在程序视角里更大
- 转换过程特点
  - 转换只要开始，每个处理器看到的地址都是虚拟地址
  - 需要硬件支持，不是每一个处理器/操作系统都支持地址翻译
  - 地址空间：进程能访问到的所有（虚拟）地址的集合
    分段式
x86对于内存分段的视角
- 保护模式下（内核态），段表被称为全局描述符表（GDT）或局部描述符表（LDT）
- 线性地址 = 基地址 + 偏移
分段内存
- 段寄存器
  - 代码段CS
  - 数据段DS
  - 栈段SS
  - 额外段ES，FS，GS
开发者需遵循以下规则
- 所有CPU 指令都隐式地从代码段（CS 寄存器）中获取。
- 大多数内存引用来自于由DS 寄存器中保存的段选择器所指定的数据段。
- 处理器栈的引用，无论是隐式的（例如push 和pop 指令）还是显式的（使用(E)SP 或(E)BP 寄存器进行内存访问），都使用栈段（SS 寄存器）。
- 字符串指令（例如stos、movs）除了使用数据段外，还使用由ES 寄存器中保存的段选择器所指定的附加段。
Cons:维护可变长度的段开销较大
- 外部碎片（External fragmentation）: 可用的内存变成非连续的地址空间
- 内存整理/压缩非常慢（内存移动、拷贝…）
- 如果段的大小会增长/改变，事情会更加麻烦…（例如堆）
  分页式
分页内存
- 分页：内存划分成固定大小的块（页框），可以理解为特殊的分段
- 每个进程都有一个页表，保存内存页->物理页框的映射
- 内核只有一个页表
- 内存页在物理内存中四处散落，但在虚拟内存中却可以做到连续
- 在一个页中，内存访问是连续的
- 简化内存分配任务
多级分页
- 单级分页解决了大部分页表所需的需求，但是页表可能非常大，甚至比进程本身使用量还大
- 在x86 32时代使用PDE和PTE分别存储下级页表基地址和实际物理页框
- 实际指向的索引只需要20位，因为32位中后12位用于页内偏移
- 32位时，页表每项4B，故在这种情况下单级页索引不可超过10位
内存管理单元（MMU）
- 执行地址翻译的硬件
- OS在内存中根据格式设定号页表
- MMU读取页表，并翻译地址，这个过程对处理器/OS透明
页面大小的选择
- 太小：页表大小变大；缓存命中率降低
- 太大：内部碎片化（合理安排页表不会存在外部碎片化）
页表可以是稀疏的
- 不是每个PDE都有对应页表
- 节省空间
- 页表往往恰好放进一个整页中，页表的大小只能是页大小的整数倍
缺页错误
- 当CPU/MMU访问一个没有被映射的内存地址时发生
  - 软缺页：内存被置换到硬盘、访问暂时没被映射的共享页
    - 处理完毕后，CPU会尝试重新访问该地址
  - 硬缺页：尝试写入只读页面、访问未被分配的页面
    - 造成段错误
- 现代OS，malloc的“懒分配”实现方式
  - 先建立页表项，但是不实际分配页框（先建立 VMA / 虚拟地址区间的记录，不一定立刻建立完整的最终页表项）
  - 当页被真正访问到时，才通过缺页错误处理实际分配物理内存
    TLB和cache
    
    Cache概念
cache：对于一小部分数据/指令的更为快速的访问
- 核心思想：让最频繁的部分变快
  - “缓存命中”才有用
- 计算机系统中最常见的概念
- 现代计算机由于CPU处理速度远大于IO处理速率，故常设计IO缓存和存储缓存
局部性原理（Locality）
- 时间局部性
  - 一条指令被执行过，未来很可能被再次执行
  - 一台哦内存地址被访问过，未来很可能被再次访问
- 空间局部性
  - 如果一个存储器的位置被引用，那么将来他附近的位置也很可能被引用
- 局部性的产生
  - 循环运算
  - 矩阵计算（计算机中非常关键的操作）
缓存使用场景
- 速度、大小和开销的权衡
- 直接使用场景
  - 缓存（主存的缓存、多级）
  - 虚拟内存分页（内存作为硬盘的缓存）
  - 文件系统（硬盘数据块在内存中的缓存）
  - DNS（缓存域名与IP地址的翻译）
  - 浏览器（缓存最近浏览的页面）
高效的地址翻译
- 对于多级页表来说翻译需要多次且重复的进行
- TLB快表
  - 缓存最近虚拟页到物理页框的翻译结果
  - 命中直接使用结果
  - 未命中再去页表查询
  - 每个核心私有
- 地址翻译开销= TLB查表开销+P（TLB miss）*页表查询开销
TLB查询过程
- 硬件可以实现并行化查表
- TLB命中的概率直接决定了地址翻译的性能
TLB Miss主要原因
- 强制miss
- 容器miss
- 冲突miss
- 一致性miss
TLB Miss过程
- 硬件遍历页表
  - TLBmiss时，MMU查询当前页表并填充TLB
    - 若PTE有效，硬件自动填充TLB，处理器不感知
    - 若PTE失效（invalid），造成缺页，交由内核决定
- 软件遍历页表（MIPS）软TLB
- TLB miss时，处理器收到TLB错误
- 内核遍历页表找到PTE
  - PTE有效，填充TLB，从错误状态返回
  - PTE无效，内部调用缺页处理例程
TLB什么时候有效/无效
- 当空间或时间局部性的区域大于TLB存储表大小时会引发频繁替换表项并miss
- 此时需要使用更大的页，在不变TLB（因为TLB作为硬件难以更改数目）的情况下才能完成局部性的利用
- 上下文切换时TLB中的缓存只针对上一个进程，TLB中的cache存在问题
- 使用硬件标识的TLB，为TLB表项添加硬件tag（可以是PID），只有tag和TLB表项一致时才会命中
- 内核更改页权限时必须让硬件清除TLB页表，这在多核处理时，如果不能确认是哪个TLB缓存了，就必须进行TLB击落，所有TLB清除表项（关于这项技术还有更好的现代优化手段）
  按需分页
按需分页
- 现代程序需要很多内存，但一般不需要同时的存储很多内容
  - 90/10定理
- 解决方案
  - 懒加载
    - 需要用的时候才分配，不需要用的时候放在硬盘里
- 无限内存的幻觉
  - 可以使用的虚拟内存可以大于物理内存
  - 所有进程加起来的内存远大于整个系统的物理内存
    - 能够运行更多的进程，增加了并行
    - 前提：只要这些进程不同时使用完字节的内存
- 实现机制
  - 程序开始时：并非所有代码/数据都被装入内存
    - 未装在的数据和代码没有物理页
  - 直接访问这些数据/代码的虚拟地址
  - 未装载则自陷调用缺页异常处理程序
  - 软硬件协同工作
    - 硬件：在PTE中引入有效位，用于表该页是否真的在内存中
    - 软件：任何不再内存中的页面有效位清0
    - 硬件：若“present”为0，访问该页面会引发异常，即缺页错误
    - 软件：转到内核态并执行缺页错误处理方法
      - 找到一个当前未被使用的页框或用过的页框
      - 若该页已被使用
        
        若已被修改过（dirty位），写入磁盘
        
        无效化其PTE以及TLB表项
      - （可选项）将新页从置换文件中加载出
      - 更新相应PTE，清除原有TLB表项
      - 重新执行产生错误的指令
内存映射文件（Memory-mapped Files）
- 调用：mmap
- 虚拟内存中的段，为已被分配与文件或类文件资源的某一部分建立直接的逐字节对应关系
- 优点：
  - 透明性：程序可以使用指针访问这些数据
  - 零拷贝 I/O：操作系统只需更改页表项，而无需将数据复制到内存中；read()/write() 需要将数据复制两次（磁盘-内核-用户）
  - 流水线处理：程序一旦页表设置完成即可开始执行
  - 进程间通信：共享变得容易
  - 大文件：操作系统自动拆分处理
- 缺点
  - 频繁的缺页错误
- 使用场景
  - 随机访问，而非顺序访问
  - 大文件IO
  - 多进程，数据在进程间共享
- 流程
  - 当程序访问无效地址时
  - [MMU] TLB 未命中；完整页表查找
  - [MMU +OS] 陷入页面错误处理程序
  - [OS] 将虚拟地址转换为文件偏移量
  - [OS] 在内存中分配一个新的页框
  - [OS] 从磁盘将数据读入内存（阻塞）
  - [CPU] 读取完成时产生磁盘中断
  - [OS] 通过将条目标记为有效来更新页表
  - [OS] 恢复进程
  - [MMU] TLB 未命中；完整页表查找
  - [MMU] TLB 更新
    页框淘汰算法
物理页框分配
- 有空的页框就用
- 没有空的页框
  - 选择一个页淘汰
  - 找到指向被淘汰页的PTE
    - core map：页框到PTE的映射
  - 设置PTE为invalid
  - 对应TLB击落
  - 把淘汰页面写回硬盘
脏位
- OS使用PTE中的dirty bit追踪被修改的页
- 初始化为0，当发生store指令置为1
- 同理TLB也有脏位
- UNIX使用后台线程清理并使用脏位
页淘汰/置换算法
- 目标
  - 把“重要的”页面留在内存里
  - 减少错误淘汰，代价很高
- 先进先出（FIFO）
  - 优点：实现简单
  - 缺点：
    - 不区分常用/不常用页面
    - 不能保证增加页框时保留原先保留页框，可能存在Belady异常现象（增加缺页次数）
- 随机策略（RANDOM）
  - TLB的典型策略，硬件实现简单
  - 无法预测，没有性能保障
- 最近最少使用（LRU）
  - 淘汰最长未使用的页面
  - 效果较好，但维护长列表开销大（TLB中可以直接使用，但在页表中需要做修改优化）
- 时钟算法（Clock，近似LRU）
  - 使用页表中的use位
    - 初始化为0
    - 当页被访问时置为1（新添入的页面也认为是刚被访问为1）
  - 针对我们需要淘汰的页面时，从时针（hand）指向的位置开始
    - 如果指向页面use位为1，将其清0，并（顺）时针移动，重复
    - 如果指向页面use位为0，淘汰页面，置换页面，指针在此处停止
  - 指针移速
    - 当移速慢，意味着频繁的置换页面，通常表明总能快速的找到最近没怎么用的页，说明内存压力较大或局部性较差的情况
    - 当移速快，与慢正好相反，说明页面有被反复使用，缺页相对不那么频繁
  - 内存颠簸
    - 一般发生于内存紧张和局部性差的情况
  - Nth机会
    - 每个页表项中use被访问时置为N
    - 作为更宽松的条件，可能增加扫描次数但可能降低缺页率
      调度
      
      调度机制的基础
CPU调度
- CPU调度是多道编程操作系统的基础
- 通过在不同进程间切换CPU，OS可以最大化CPU利用率
  - 在资源有限时才需要调度
  - 动态资源分配
抢占机制的硬件支持
- 进程不愿交出CPU时，OS难以通过软件的方式强制介入
- 硬件支持的中断操作可以安全打断进程
分时系统
- 分时系统支持动态交互
- 时钟中断
  - 分时系统可以使用时钟中断管理CPU
  - 硬件时钟产生，发送到OS，更改/设置需要权限
上下文切换
- 将CPU从一个进程切换到另一个进程
- 保留旧进程状态、重新加载新进程状态
- 保存的状态
  - 寄存器快照
  - 进程状态/模式
  - 调度星系
  - 内存管理信息…
- 保存到记录的控制块（PCB）中
抢占式调度的性能考量
- 时钟颗粒度
  - 细粒度，响应更迅速
  - 粗粒度，切换与调用少，开销少，效率高
- CPU运行信息统计（CPU accounting）
  - 被调度器使用
  - 调度决策的关键
  - 对程序员性能调优等十分有用
调度机制中的挑战
- 灵活性
  - 长任务和短任务
  - 交互式和非交互式
  - IO密集和计算密集
- 目标
  - 公平性，不出现饥饿情况
  - 最大吞吐量
  - 最小响应速率
  - 最小周转时间
  - 计算资源利用率
- 公平性
  - 所有用户都应该得到CPU资源
  - 每个用户得到的CPU资源应该和任务有关，相同条件下应大致相等
    调度的策略
先入先出（FIFO）
- 运行到完成、阻塞或出让
- 优点
  - 简单，最小的上下文切换开销
- 缺点
  - 护航效应，短进程被长进程“遮掩”导致等待时间大幅上升
  - 任务到达序列很大程度影响效果
轮转（RR,Round Robin）
- 每个进程都运行单位时间片
- 时间片选择
  - 开销与响应时间的权衡
- 优点
  - 更利于短任务，公平性好
- 缺点
  - 对于长任务来说上下文切换开销大
  - 相比不公平算法常常会恶化周转时间
最短任务优先（STCF/SJF，Shortest Time-to-Completion/Job First）
- 优先调度运行时间最短的任务
- 优点
  - 假设所有任务同时到达，从平均周转时间来说，SJF被证明为最优算法
  - 尽可能小的平均周转时间
- 缺点
  - 难以预测未来，必须允许到终止（非抢占）
最短剩余完成时间优先（SRTCF，Shortest remaining Time-to-Completion First）
- 抢占式的优先调度剩余完成时间最短的任务
- 每当有新任务到达时做判断
- 优点
  - 尽可能小平均周转时间
- 缺点
  - 存在被打断，基本不公平，因此也可能造成饿死
严格优先级调度（SPS，Strict Priority Scheduling）
- 队列间按照优先级运行
- 同队列中可以使用FIFO、RR或其余策略【并不确定，不是一个具体的策略】
- 通常搭配老化/优先级提升（Aging），一个任务等待一段时间未被执行会逐渐提高优先级
- 优点
  - 使用优先级策略，优先调度紧急程度任务
- 缺点
  - 高优先级任务会导致低优先级的任务饿死
  - 低优先级任务抢占锁时又因为存在高优先级任务使其无法释放锁，形成优先级反转的死锁
最高响应比优先（HRRN，Highest Response Ratio Next）
- $ 响应比= \frac{等待时间 + 预计使用时长}{预计使用时长}$
- 优先偏好短任务，但在短任务不断出现时，长任务也能得到执行
多级反馈队列调度（MLFQ/MFQ，Multi-level Feedback Queue）
- 某个任务在同个优先级队列中执行完设定时间片后未结束或阻塞则降低该任务优先级
- 队列间时间分配：
  - A：高优先级抢占
  - B：优先级权重分配时间片
- 优点
  - 效果近似于SJF，平均周转时间较短
  - 使用优先级，并在尽可能避免饿死，但饿死概率仍较高
- 缺点
  - 大量的高优先级依旧可以饿死低优先级任务
  - 恶意进程可以合理利用规则长期独占资源
- 很多的OS使用MLFQ-like策略调度
实时调度（DDL优先）（RT，Real-Time（EDF，Earliest Deadline First））
- 优先级调度+抢占
- 优先级取决于执行时间与DDL的比值
- 缺点
  - 对于任务太多，EDF可能无法满足要求
完全公平调度器（CFS，Completely Fair Scheduler）
- 优先调度最近拿到的CPU少的任务
- 使用虚拟运行时间来刻画最近占用CPU的量
- 通常维护红黑树排序来进行调度
- Linux中非常重要的调度器
  锁
  
  同步的动机：为什么难
recap：线程抽象
- 线程抽象带哎了“无穷多处理器”的幻觉
- 线程执行速度不一（由调度策略影响）
  - 程序必须在任何调度下都能够正确工作
recap：多进程
- 回顾定义
  - 多处理：Multiple CPUs or cores or hyperthreads
  - 多道编程：Multiple Jobs or Processes
  - 多线程：Multiple threads per Process
- “并发”执行的真实含义
  - 调度器开源以任意顺序执行线程甚至交错执行
线程协作的好处
- 资源利用效率
- 计算效率（并行计算、计算与IO交叠）
- 开发效率（将大程序切成小块）
并发系统的正确性
- 大前提：任意调度下啊程序都需要正确执行
- 情况1：线程间相互独立
  - 线程间无共享状态
  - 确定性->输入状态决定输出结果
  - 可复现性->重复使用相同条件执行，结果一致
  - 调度的顺序不重要
- 情况2：线程协作
  - 多线程间存在共享状态
  - 结果取决于调度
- 实际中：
  - 程序并不是真的相互独立
    - 总存在共享状态：文件系统，OS资源，etc
  - 编译器对指令进行重排序
    - 这能在最大化指令级并行，并在单线程内部正确依赖
    - 单跨线程时拆分与重排序会让竞态更多见，并且更糟糕
  - 原子操作
    - 执行到底或不执行的指令，不可继续分解
    - 底层不可分割的操作是并发程序的关键，也是并发编程的基石
一些关键定义
- 同步（Synchronization）：使用原子操作确保线程间协作正确
- 互斥（Mutual Exclusion）：确保某一时间只有一个线程在做某一件事
- 临界区（Critical Section）：同一时刻只有一个线程能够执行的代码区
  - 临界区是线程间互斥的结果
  - 临界区和互斥其实是在描述同一件事
- 锁（Lock）：阻止线程继续进行的机制
  - 进入临界区、访问共享数据前加锁
  - 离开时、访问后解锁
  - 遇锁等待
    - 重要思想：所有同步都跟等待有关

锁

通常使用硬件锁指令
- 在单核上通过避免上下文切换实现原子操作（不应该在整个流程禁用IRQ，而是在锁的获取释放上禁用IRQ）
- 在多核中通过在CPU cache层面使用MESI-like缓存一致性协议，确保操作的竞争原子一致性
往往锁操作基于硬件支持的原子指令，如CAS，Test&Set等
- 但是此类指令的开销一般比常规指令大
- 所以可以依次在Compare和Test后再接CAS和Test&Set。
3个形式化属性
- 互斥：最多只有一个线程持有该锁
- 进展：如果没有线程持有该锁，并且任何线程尝试获取该锁，那么最终某个线程会成功获取该锁
- 有界等待：如果线程 T 尝试获取一个锁，那么它等待该锁的次数存在一个上界
- 然而，这并不保证等待中的线程会按照 FIFO 顺序获取该锁。
  条件变量
条件变量: 在队列中等待临界区内部一些条件的线程
- 核心思想：通过在进入睡眠时原子地释放锁，允许线程在临界区内睡眠
- 操作：
  - Wait(&lock): 原子释放锁并休眠；返回前再获得锁。
  - Signal(): 唤醒某个等待进程
  - Broadcast(): 唤醒所有等待进程
管程：一种设计模式（mutex+CV）
- 梅萨（Mesa）管程
  - Signaler保有锁和CPU
  - Waiter被放在就绪队列且无特殊优先级
    - 无任何调度保证
  - 对OS的调度策略没有假设、没有约束
  - 在绝大多数真实的操作系统中，都（只能）使用Mesa管程
- 霍尔（Hoare）管程
  - Signaler 释放锁, CPU切到waiter; waiter 马上执行
  - Waiter 释放锁，CPU在以下情况时需马上切到signaler
    - 其退出临界区时
    - 其需要再次等待
  - 可惜不太实用，因为霍尔管程隐式地规定了一个调度约束
    信号量
信号量：一个种泛化锁
- 含有一个非负的值
- 支持两种原子操作
  - P()：原子等待信号量变成正数，然后-1
  - V()：原子的将信号量+1，唤醒任何等待中的P
- 记录型信号量
  - 此类也可以存在负数的情况，代表等待P的任务数
  - 使用进程链表L，用于链接所有等待进程
  - 当信号量做删减后为负数时阻塞并加入等待链表（删减判断为原子操作）
  - 当信号量做增加后小于等于零则唤醒一个链表中的进程（增加和判断为原子操作）
- 常规用法
  - 实现互斥（初始值为1）
    - 也叫二元信号量、互斥锁
  - 实现调度顺序的约束（初始值为0）
    - 运行线程1等待线程2的信号，对线程执行顺序进行约束
  - 使用信号量实现前趋关系
    死锁
    
    死锁概念
死锁（DeadLock）
- 一系列线程的环状等待，其中每一个线程都在等待环中的某一个线程完成一些操作
- 四个条件
  - 互斥（Mutual exclusion）
    - 一个时间仅有一个线程能够拥有资源
  - 持有等待（Hold and wait）
    - 至少持有一个的某线程在等待着获取更多由其他线程持有的资源
  - 无抢占（No preemption）
    - 资源仅能被线程自愿释放，无法被抢占
  - 环形等待（Circular wait）
死锁与锁
- 交叉上锁的模式可能造成非确定性死锁，时而发生时而不发生
处理死锁的方式
- 允许系统进入死锁状态，之后恢复
  - 需要死锁检测算法
  - 某种强制抢占资源或终止进程的技术
- 确保系统永远不会进入死锁
  - 需要监控所有锁的获取状态
  - 有选择性地拒绝可能导致死锁的状态
- 忽略这个问题，假装死锁从来没有发生过
  - 现代OS主要采用这种策略，因为其他的方式开销一般很大
    相关问题
哲学家问题
银行家算法
- 动态的分配资源
  - 评估每个请求，并且如果之后某种线程排序仍然不会发生死锁，则予以授予
  - 实现方法：假装每个请求都已被授予，然后运行死锁检测算法，如果结果无死锁，则授予请求
    存储和文件系统
    
    存储设备
Magnetic disks (磁盘)
- 极少发生损坏的存储
- 低成本大容量
- 块级随机访问
- 随机访问性能差
- 顺序访问性能好
Flash memory (闪存)
- 极少发生损坏的存储
- 中等成本容量（磁盘的5-20 倍）
- 块级随机访问
- 读取性能好；随机写入性能较差
- 需要以大块为单位进行擦除
- 磨损模式问题
磁盘构造
- 扇区:数据传输的最小单元
- 磁道:一圈圈扇区
- 柱面:堆叠起来的磁道，柱面数=单盘磁道数
- 磁头:与可移动悬臂相连，读取数据- 每个磁片每个面都有一个
- 存储容量= $（磁头数）（柱面数）（扇区数）*（扇区大小）$
数据读写的三个步骤 :
- 寻道时延: 移动磁头/臂到正确的磁道（径向）
- 延迟时延: 等待扇区旋转到磁头下
- 传输时延: 传输磁头下扇区的数据（读写）
磁盘调度
- 调度可以分别由OS,固件完成，也可由二者同时完成。
- FIFO
  - 公平
  - 但是请求访问的地址有随机性->长寻道时间
- 最短寻道实际优先（SSTF，Shortest seek time first）
  - 类似SJF，并不公平，可能饿死
  - 寻道时间短、效率和吞吐率高
- 电梯算法（SCAN：Elevator Algorithm）
  - 取最近的请求，并沿该方向运行，直到触底反弹
  - 无饿死，但是保留了一些SSTF的特质
- C-SCAN：Circular-Scan
  - 折返过程中忽略其中任何请求
  - 比SCAN更公平，不偏袒路程中的扇区
Solid State Disks (SSDs) 固态硬盘
- 使用 NAND Multi-Level Cell (2 or 3-bit/cell) 的闪存
  - 扇区寻址，4-64个“页”一个内存块，使用对齐机制
  - 通过捕获的电子来分辨0还是1
- 没有物理移动开销
  - 消除了寻道和旋转时延，在顺序或者随机读取上效果都很好
  - 极低功耗、轻便
  - 写入次数有限
IO与设备驱动
- OS通过设备驱动（Device Driver）控制IO设备
- 设备驱动通过与IO设备的控制器打交道，“间接”驱动设备
  - 控制器往往通过内存映射IO将内部的寄存器暴露给OS
  - 控制器通过中断向处理器发送信号
- 数据传输方式
  - 程序IO（Programmed I/O）: 处理器从设备寄存器读取/写入数据
    - 优点：简单的硬件（控制和数据接口相同）
    - 缺点：I/O 会消耗大量CPU 时间
  - 中断驱动IO：当某进程要启动某个I/O 设备工作时，便由CPU 向相应的设备控制器发出一条I/O 命令，然后立即返回继续执行原来的任务
  - 直接内存访问（Direct Memory Access，DMA）: I/O 控制器在无需CPU 介入的情况下从RAM 中读取/写入
    - OS 指定要通过设备控制器寄存器使用的物理地址范围
    - 优点：CPU 现在可以在大型I/O操作期间执行其他任务
    - 缺点：DMA的权限过大，有很大的安全隐患
简单的read（）生命周期
- 进程发出syscall read（）
- OS 将调用线程移动到等待队列（state=WAITING）
- OS使用内存映射I/O 告诉磁盘读取请求的数据并设置DMA，以便磁盘可以将数据放入内核的内存中
- Disk 读取数据并将其DMA 写入主内存
- 磁盘触发中断
- OS 的中断处理程序将数据从内核的缓冲区复制到进程的地址空间
- OS 将线程移动到就绪列表
- 线程在CPU 上调度，并从read（）返回
  文件系统抽象
文件描述符：OS用于标识文件状态的实体
文件系统
- 把磁盘设备基于“块”的抽象转化为文件、目录抽象的软件
  - 更准确来说：文件系统是管理硬盘地址空间的软件（广义上的硬盘，不单指某一介质）
- 组件
  - Naming 按名存取：用于按名称而非按块查找文件的接口
  - Disk Management 磁盘控制：将磁盘块收集为文件
  - Protection 保护：保障数据安全的层次
  - Reliability/Durability 可靠性/持久性：即使在崩溃、介质故障、攻击等情况下，仍保持文件持久可用。
不同视角下的文件
- 用户视角：
  - 持久数据结构
- 系统视角（系统调用接口）：
  - 字节集合（UNIX）
- 系统视角（操作系统内部）：
  - 区块(block) 集合（区块是逻辑传输单元，扇区(sector) 是物理传输单元）
  - 区块 (block) 大小 >= 扇区 (sector) 大小; 在 UNIX 中，块大小为 4K
磁盘管理策略
- 磁盘上的基础实体:
  - 文件File: 在逻辑空间中按顺序排列的用户可见的数据块组
  - 目录Directory: 用户可见的将名称映射到文件的索引
- 将磁盘作为扇区的线性数组访问。
  - 两个方法：
    - 将扇区标识为向量[cylinder， surface， sector]，按柱面优先顺序排序
      - 在BIOS 中使用，但不再在现代OS中使用
    - 逻辑块寻址（Logic Block Addressing，LBA）：每个扇区都有从零到最大扇区数的整数地址
      - 控制器负责地址转换，LBA ->物理扇区
        
        第一种情况：OS/BIOS 必须处理坏扇区
        
        第二种情况：硬件保护OS免受磁盘结构的影响
- 跟踪空闲磁盘区块
  - 使用位图 (bitmap) 表示磁盘上的可用空间
- 结构化文件
  - 跟踪哪些块属于逻辑文件结构中的哪些偏移量
  - 优化文件磁盘块的放置方式 (placement) 以匹配访问和使用模式
文件
- 命名的永久存储
- 组成部分
  - 数据：磁盘中的扇区/区块
  - 元数据（属性）：
    - 作者、大小、最后一次修改时间…
    - 访问权限
目录
- 是文件和目录指针的集合
- Volume (卷): 构成逻辑存储设备的物理存储资源的集合。可以是物理设备的一部分或许多物理设备。
- Mount (挂载): 将已挂载卷文件系统的根目录映射到现有文件系统中的某个路径的操作
  FileSystem design
  
  文件系统组成
多级翻译
- 文件路径 -> 目录项查找 -> inode number（i-number） -> inode
  - 路径解析时，文件系统逐级遍历目录
  - 目录项的核心作用是把“文件名”映射到 inode number
  - inode 中保存文件元数据，以及文件数据块/索引块的位置
  - 因此真正用于定位文件内容的是 inode，而“文件号”更准确地说是 inode number
- open 系统调用建立“进程视角”与“内核视角”的映射
  - 内核根据路径找到目标文件后，创建/引用一个打开文件对象，记录访问模式、当前偏移、状态等信息
  - 再在进程的文件描述符表中分配一个表项（fd）指向该打开文件对象
  - 最终返回给用户进程的是文件描述符 fd 这个整数“句柄”，而不是 inode 本身
  - 文件描述符表通常属于进程，可在 PCB 关联的进程资源中维护
- 后续 read、write、lseek、close 等操作都先作用于 fd
  - 系统调用先根据 fd 查进程文件描述符表
  - 再找到对应的打开文件对象、inode 以及底层数据块映射
  - 读写时通常还会结合页缓存/缓冲区缓存，而不是每次都直接访问磁盘
- 可概括为三层映射
  - 文件名/路径 -> inode
  - fd -> 打开文件对象
  - 打开文件对象 -> inode -> 数据块
- 系统调用接口
  - open：按路径查找文件并返回 fd
  - read/write：基于 fd 读写文件内容
  - close：释放该进程对 fd 的引用
    典型文件系统
文件系统的关键设计
- 目录：给数据命名，“路径”作为名称的一部分
  - 如何将文件名转换成文件对应的编号
- 文件：查找数据
  - 如何根据文件号找到对应的存储块
- 虚拟文件系统：virtual file system（VFS）
  - 如何让不同文件系统（轻易地）共同工作
主流文件系统
- FAT (Microsoft File Allocation Table)
  - 极其简单的索引结构：链表。
  - 仍然广泛用于闪存和数码相机等设备
- FFS (Unix Fast File System)
  - 基于树的多级索引，提高随机访问效率。
  - 使用一组局部启发式方法来获得良好的空间局部性。
  - EXT2 和 EXT3 基于 FFS。
- NTFS (Microsoft New Technology File System)
  - 更灵活的树结构。
  - MS 上的主流文件系统。
  - 与EXT4和Apple 的分层文件系统（HFS 和HFS+）并列。
目录结构
- 目录被视为一个文件，包含<file name： file number> 映射列表
- 目录的数据保存在文件中，可被read读取（通常不这么做）
  - 一般使用系统调用访问目录
- 实现方式
  - 目录文件内容需要支持任意位置的删除与插入
  - 索引file name时通常可以使用链表
  - 当数据量过大时访问速度过慢，可以使用树状结构，NTFS就使用到了B/B+树
- 访问开销
  - 当前工作目录（CWD）：指向用于解析文件名称的目录，由每个进程私有
    - 使得允许用户指定相对文件名而不是绝对路径
  - 解析多层路径时，每一层都进行数据块的查找与读取
- 链接方式
  - 硬链接：多个目录项（文件名）可映射到同一个 inode number，因此共享同一份文件数据与元数据
  - 软链接：一个特殊文件，其内容是目标文件的路径名；访问软链接时，需要再按该路径继续解析
  - inode 通常维护链接计数（link count）
    - 删除一个文件名时，通常是删除对应目录项，并将该 inode 的链接计数减 1
    - 只有当链接计数为 0，且该文件不再被任何进程打开时，文件数据块才会被真正回收
文件结构
- FAT
  - 存储文件块的简单方法：链表
  - 文件编号就是一个块/簇编号
  - 每一个数据块在表中占据一个条目
  - FAT（文件分配表）包含指向每个条目的下一块（或者特殊END值）的指针
  - 查找空闲区域
    - 表中free块的条目值为0
    - 没有另外的索引，只能通过扫描整个FAT才能找到可用空间
  - 优点
    - 极度简单：能够在固件中实现
  - 缺点
    - 局部性差：碎片化严重
    - 随机访问性能差：需要遍历文件的FAT条目，直到目的块
    - 存储在目录条目中的文件元数据受限制
      - 对卷和文件大小的限制
        
        块地址保留前4bit，28bit可用
        
        2^28个数据块*4KB数据块大小=1TB
        
        文件大小以32位编码，单文件大小不能大于4GB
- FFS
  - 大文件使用多级索引、小文件使用有限索引
    - 小文件由12个块索引直接查找数据块号
    - 大于12块的文件被认为是大文件，继续使用分层的三级间接指针块存储
  - 元数据与文件本身相关联（在inode 中），而不是其目录映射中
    - 使能hard/soft links
  - 针对HDD的局部性启发式设计
    - 将来自同一文件的块保存在磁盘的同一物理区域中，以最大程度地减少寻道、旋转延迟
    - 同一目录中的文件同理
    - 实话实说，在SSD 的时代中已经变得不太重要
  - 优点
    - 兼顾大小文件
    - 文件内容和元数据的一致性
  - 缺点
    - 对于小文件效率低下
    - 对属于同一文件的连续范围的块的编码效率低下
- NTFS
  - 现代Windows系统上的默认文件系统
  - 主文件表（Master File Table）
    - 代替FAT或inode数组
    - 每个表项的最大大小为1KB
    - 组成部分
      - 元数据
      - 文件数据（适用于小文件）
      - 文件数据的区段列表（起始块、大小）
      - 对于大文件：指向具有更多区域extent列表的其他MFT条目指针
  - 使用日志提升可靠性
文件系统中有趣的设计
- 分区（Partitions）
  - 分区分的是硬盘地址空间
  - 每个分区都从逻辑块0开始
    - 作为一层抽象和虚拟化
  - 每个分区都可用有自己的文件系统
  - 分区表存放了分区和其起始物理扇区对应关系
- 环回设备
  - 硬盘映像文件
    - 可用冒充硬盘
- 磁盘碎片整理
  - 磁盘碎片
    - 由不连续的块分配引起
    - 文件系统老化
    - 极大拖慢电脑速度
  - 为局部性而对磁盘块重定位、分配
- 数据恢复
  - 处于性能/寿命的原因，OS/存储可能会：
    - 延迟分配
    - 延迟删除
  - 更糟糕的是，删除可能永远不会发生
    虚拟文件系统（VFS）
现代虚拟文件系统
- 支持数十种文件系统
  - 允许对应用程序透明的新功能和设计
  - 与可移动媒体设备和其他OS的互作性
- 独立于存储的层
  - 用于配置OS的伪文件系统
- 网络文件系统支持
虚拟文件系统的作用
- 一段重要的代码
  - 不仅仅是一个API 包装器
- 缓存文件系统元数据（例如，名称、属性）
  - 使用page cache缓存数据
- 实现通用访问控制模型
- 实现复杂的通用例程
  - Path lookup （name resolution 命名解析）
  - Opening files
  - File handle management
    可靠的文件系统
对文件系统可靠性的威胁
- 操作中断
  - 崩溃或电源故障
  - 文件操作通常包含许多对存储的I/O 更新
- 存储文件可能丢失
  - 物理丢失或掉电
Reliability （可靠性）：存储系统在某个指定时间段内继续可靠的概率
Availability （可用性）：存储系统在任何给定时间可用的概率
“事务”：确保原子更新的操作
实现可靠性的方法
- 设计执行顺序
  - 按特定顺序对操作进行排序
    - 精心设计，允许安全地中断序列
  - 崩溃后恢复
    - 读取数据结构查看是否有任何正在进行的操作
    - 按需进行清理/完成相应操作
  - FFS的写入顺序规则
    - 在初始化指针所指向的结构之前，绝不要写入该指针
    - 在将所有指向某资源的指针置空之前，绝不要重用该资源
    - 在设置新的指针之前，绝不要清除指向仍存活资源的最后一个指针
  - 缺点
    - 执行/失败顺序可能性过多：难以保证可靠性
    - 文件系统在每个依赖间插入同步操作：更新缓慢
    - 需要扫描元数据的不一致：恢复速度极慢
- 事务
  - 使用事务进行原子更新
    - 确保以原子方式执行多个相关更新
    - 如果中间发生崩溃，则系统的状态将反映所有更新或不反映任何更新
    - 大多数现代文件系统在内部使用事务来更新文件系统结构和元数据
    - 应用程序能自主实现自己的事务
  - 将原子更新的概念从内存扩展到持久性存储
    - 以原子方式更新多个持久化数据结
  - 流程
    - 开始一个事务：获取事务ID
    - 执行一系列操作
      - 如果过程中有任何失败，回滚
      - 如果和其他事务冲突，回滚
    - 提交事务
ACID
- 原子性：发生或不发生
- 一致性：事务会确保数据的正确性（余额非负、预约的时期需合法…）
- 隔离性：事务间的执行独立
- 持久性
日志
- 不直接修改磁盘上的数据结构，而是将更改写入日志/日志
- 一旦更改记录在日志中，就可以安全地将更改应用于磁盘上的数据结构
- 提交事务后，可以考虑清理日志
- Redo Log
  - Prepare
    - 将所有更改/更新写入日志
    - 可以一次性写完，也可以随着时间推移一条条写
    - 等待所有更新都写入日志
  - Commit
    - 将提交记录追加到日志
    - 或者可以回滚（将之前的修改舍去），写入回滚记录
    - 在commit前可以安全的回滚，在此之后，事务必须生效
  - Write-back
    - 将事务的所有更新写入磁盘
  - Recovery
    - 读取日志
    - 重做已提交事务的任何操作
    - 垃圾回收
  - Garbage collection
    - 回收日志中的空间
  - 实现上的细节
    - 处理并发事务
      - 必须标识日志记录属于哪个事务
    - 重复写回是可以的
      - 适用于幂等更新
        
        幂等：多次操作后结果保持一致
      - 重做日志系统不允许非幂等记录
    - 可以重新恢复
      - 如果在恢复过程中再次发生崩溃
    - 性能上的考量
      - 日志更新是连续的
      - 回写是异步的
    - 正确的顺序是关键
      - 在提交之前，事务的更新位于磁盘上的日志中
      - 在任何回写之前，提交都在磁盘上
      - 在对事务的日志记录进行垃圾回收之前，所有回写都在磁盘上
在文件系统中使用事务的两种方法
- journaling （日志）：对系统的元数据使用事务进行更新
- logging：同时在元数据和数据中使用事务更新

处理介质故障的冗余硬件架构

存储设备失败
- 扇区和页面故障：磁盘的一个或多个单个扇区丢失，但磁盘的其余部分继续正常运行
- 全盘故障：设备无法为所有扇区提供读写服务
廉价磁盘冗余阵列（RAID，Redundant Arrays of Inexpensive Disks）
- 数据存储在多个磁盘上（冗余）
- 由软件或硬件实现
  - 在硬件情况下，由磁盘控制器完成;文件系统甚至可能不知道有多个磁盘正在使用
- RAID1：每个磁盘都完全复制到镜像磁盘上
- RAID5：数据分散在多个硬盘上，校验块数据由其余四盘的异或得到
分布式实现的高可用和高耐用
- 优点：
  - 高耐用（durability）：难以销毁所有副本
  - 高可用（availability）：可以读取任何副本
- 缺点：
  - 写入可用性低
    - 如果任何一个副本未启动，则无法写入
    - 或者–可以使用宽松的一致性模型
- 为什么我们需要分布式系统？
  - 成本低、容易构建
  - 更容易逐步增加算力
  - 用户可以完全控制某些组件（如其中的某台电脑）
  - 协作：用户更容易通过网络资源（如网络文件系统）进行协作
- 分布式系统的“饼”:
  - 更高的可用性：一台机器宕机，使用另一台机器
  - 更好的持久性：将数据存储在多个位置
- 现实很骨感
  - 可用性更差了: 取决于每台机器的正常运行
  - 可靠性更差了: 如果任何计算机崩溃，都可能会造成数据丢失
  - 安全性更差了: 世界上任何地点的任何人都可以入侵系统
  - 协调也变得更困难
    - 必须协调共享状态信息的多个副本（仅使用网络）
    - 在集中式系统中很容易的事情变得困难得多

操作系统

OS简史与概览

回顾

OS进化史

现代OS概览

启动过程

BIOS

BootLoader

UEFI

进程

编译流程

程序装载

模式转换

中断

OS接口&系统调用

POSIX

多进程接口

IO接口

系统调用

线程

线程抽象

线程实现

地址翻译

地址翻译的概念

分段式

分页式

TLB和cache

Cache概念

按需分页

页框淘汰算法

调度

调度机制的基础

调度的策略

锁

同步的动机：为什么难

锁

条件变量

信号量

死锁

死锁概念

相关问题

存储和文件系统

存储设备

文件系统抽象

FileSystem design

文件系统组成

典型文件系统

虚拟文件系统（VFS）

可靠的文件系统

“事务”：确保原子更新的操作

处理介质故障的冗余硬件架构

CATALOG

FEATURED TAGS

FRIENDS