IO设备

设备控制器

1. 控制设备的部件
   • 解析主机发来的命令，控制设备进行操作
2. 组成
   • 与主机的接口：主机与设备间传递命令、状态、数据
     • 硬件接口：PCIe SATA USB
   • 控制寄存器：1个或多个，控制设备操作
     • 写控制寄存器，命令设备执行指定的操作
     • 读控制寄存器，获得设备的状态
   • 数据缓存区（data buffer）
     • 缓冲数据
     • 使用主机端和设备内的DRAM缓冲数据
     • 如果该缓冲区可用服务读请求，也将其视作数据缓存区

寻址

1. 控制寄存器和设备数据缓冲区
   • I/O端口：I/O地址空间(Port Mapped IO,PMIO)
     • 端口号：8位或16位的数值
     • I/O专用指令in/out（例如x86）：特权指令
     • 控制线：指示CPU发出的地址是内存空间还是I/O空间
     • 内存地址空间和I/O设备地址空间隔离
   • 内存映射I/O（Memory Mapped IO,MMIO）
     • 统一地址空间，内存地址空间预留一部分给I/O设备内存和寄存器
     • 使用常规的访存指令（例如RISC指令集）
     • 内存地址与I/O地址无重叠
     • CPU发出的地址，内存模块和所有设备都要解析
   • 两者可用结合
     • 控制寄存器采用I/O端口寻址
     • 数据缓冲区采用内存映射I/O
   • 好处
     • 编程方便
     • 保护方便 & 灵活：利用虚存的保护机制
     • 高效：访问数据缓冲区不需要专用指令
2. 内核缓冲区
   • 为什么需要内核缓冲区
     • 生产者（应用）和消费者（IO设备）直接速度不匹配
     • 字符设备、块设备速度较慢，适配不同的数据传输速率
   • 用作数据读缓冲
     • 可以服务对同一数据的读请求
     • 减少实际访问设备的I/O请求

数据传输

1. 设备数据传输
   • 启动设备 + 数据传输
   • 启动时间（开销）
     • CPU用于启动设备进行操作的时间
   • 带宽
     • 启动设备后数据传输的速率（Bytes/Sec）
   • 延迟
     • 传输1字节的时间（启动时间 + 将1字节传输到目的地的时间）
2. 通用方法：不同的传输速率
   • 字符设备：对字节流传输的抽象，键盘、串口、打印机等
     • 字节粒度访问：以若干字节为传输粒度，顺序读写
   • 块设备：对块传输的抽象，磁盘、光盘等
     • 块粒度访问：以若干块为传输粒度和存储粒度，按块寻址，整块读写，随机读写

数据传输方式

PIO(Programmed IO)

1. 例子：RS-232串口
   • 简单的串行控制器
     • 状态寄存器：就绪、忙、...
     • 数据寄存器
2. 输出数据时
   • CPU:
     • 等待设备状态变为非"忙"
     • 写数据到数据寄存器
     • 通知设备"就绪"
   • 设备:
     • 等待直到状态变为"就绪"
     • 消除"就绪"标志，设置"忙"标志
     • 从数据寄存器中拿走数据
     • 清除"忙"标志
3. PIO的轮询(Polling)
   • CPU等待直到设备状态变为非"忙"
   • 好处：简单
   • 坏处：慢且浪费CPU资源
   • 改进：使用中断机制可以避免CPU轮询
4. 支持中断的设备
   • 例如：鼠标
   • 简单的鼠标控制器
     • 状态寄存器（完成、中断、...)
     • 数据寄存器（X、Y、按键）
   • 输入数据时
     • 鼠标
       • 等待直到状态变为"完成"
       • 将相应的值保存到数据寄存器
       • 发中断
     • CPU（中断处理）
       • 清除"完成"标志
       • 将数据寄存器的值读到内核缓冲区（内存）中
       • 置"完成"标志
       • 调用调度器

DMA(Direct Memory Access)

1. 基于数据寄存器的不足
   • 数据寄存器满后，发送中断请求，CPU进行中断处理
   • 传输大量数据时，中断频繁，需要CPU频繁处理中断
2. DMA的基本思想
   • 以数据块为单位进行传输，由DMA控制器控制完成外设与主机间的数据传输
   • DMA需要连续的内核缓冲区
   • CPU再数据开始传输前设置DMA控制器
   • 数据传输结束后，DMA控制器发送中断给CPU，CPU再进行处理
   • 减少占用CPU资源
3. 例子：磁盘
   • 简单的磁盘控制器
     • 状态寄存器（完成、中断、...)
     • DMA内存地址和字节数
     • DMA控制寄存器：命令、设备、传输模式及粒度
     • DMA数据缓冲区
   • DMA写
     • CPU：
       • 等待DMA设备状态为"就绪"
       • 清除"就绪"
       • 设置DMA命令为write,地址和大小
       • 设置"开始"
       • 阻塞当前的线程/进程
     • 磁盘控制器：
       • DMA方式将数据传输到缓冲区(Count--;addr++)
       • 当count==0时，发中断
     • CPU（中断处理）
       • 将被该DMA阻塞的线程/进程加入到就绪队列
     • 磁盘
       • 将数据从缓冲区写入磁盘

同步I/O 和 异步I/O

同步I/O

1. read()和write()将会阻塞用户进程，直到读写完成
2. 在一个进程做同步I/O时，OS调度另一个进程执行

异步I/O

1. aio_read()和aio_write()不阻塞用户进程
2. 在I/O完成以前，用户进程可以做别的事
3. I/O完成将通知用户进程

同步/异步读过程

1. 用户进程P1调用read()系统调用
2. 系统调用代码检查正确性和缓存
3. 如果需要进行I/O，会调用设备驱动程序
4. 设备驱动程序为读数据分配一个buffer，并调度I/O请求
5. 启动DMA进行读传输
6. 阻塞当前进程P1，调度另一个就绪的进程P2 // 异步I/O: 直接跳到第12步
7. 设备控制器进行DMA读传输
8. 传输完时，设备发送一个中断请求
9. 中断处理程序唤醒被阻塞的用户进程P1（将P1加入就绪队列
10. 设备驱动检查结果（是否有错误），返回
11. 将数据从内核buffer拷贝到用户buffer // 异步I/O: 通知进程P1读操作完成
12. read系统调用返回到用户程序
13. 用户进程继续执行

设备驱动

1. 给操作系统的其它模块提供操作设备的API
2. 与设备控制器交互
   • 与设备控制器交互以进行数据传输：命令、参数、数据
3. 主要功能
   • 初始化设备
   • 解析OS发来的命令
   • 多个请求的调度
   • 管理数据传输
   • 接收和处理中断
   • 维护驱动与内核数据结构的完整性

设备驱动的主要流程

1. 准备工作
   • 参数检查、请求格式转换
   • 设备状态检查：忙 -> 请求入队列
   • 开设备或上电时执行
2. 操纵设备
   • 将控制命令写入设备的控制寄存器
   • 检查设备状态：就绪 -> 写下一命令
   • 直到设备完成所有命令
3. 阻塞等待
   • 等待设备完成工作
   • 被中断唤醒
   • 有的设备不需要等待：如显示器
4. 错误处理
   • 检查设备状态：错误 -> 重试
5. 返回调用者

设备驱动安装

1. 静态安装设备驱动
   • 将设备驱动直接编译进内核，系统启动后可以直接调用
   • 新设备的使用需要重启OS
   • 设备驱动修改效率不高，需要重新编译内核
2. 动态挂载设备驱动
   • 将驱动动态加载进内核空间
   • 不需要重启，而是采用间接指针
     • 设备入口点表：所有设备的入口点
   • 安装入口点，维护相关的数据结构
   • 加载 / 删除设备驱动
     • 分配内核空间 / 删除内核空间
     • 存储驱动代码 / 删除驱动代码
     • 与入口点关联 / 删除入口点

设备驱动的利与弊

1. 灵活性：
   • 用户可以下载和安装设备驱动
   • 灵活接入不同硬件设备
2. 安全隐患
   • 设备驱动运行于内核态
   • 有bug的设备驱动会导致内核崩溃，或者引入安全漏洞
3. 如何让设备驱动更安全
   • 检查设备驱动的代码
   • 为设备驱动构建状态机模型进行检查
4. 用户态驱动：面向高速设备，提升性能

虚存设计

1. 设计目标
   • 保护
     • 隔离进程之间的错误
   • 虚拟化
     • 用磁盘来扩展物理内存的容量
     • 方便用户进行编程（进程地址空间从0-max）
2. 虚存设计时要考虑的问题
   • 虚实映射
     • 映射机制：分段/分页
     • 映射加速：TLB/TLB Miss/TLB表项数目
     • 映射开销：页大小和页表大小
   • 按需加载和页替换
     • 缺页处理
     • 页替换：替换算法/颠簸/pin和unpin
     • 后备存储：Swap
   • 虚存使用
     • 清零
     • Copy on Write
     • 共享内存

虚存设计问题 —— 虚实映射设计问题

页大小

1. 大页
   • 好处：页表小 且 磁盘I/O高效
   • 不足：内部碎片
     • 进程执行不需要的部分也放进了内存
     • 页可能不满，存在浪费
2. 小页
   • 好处：减少内部碎片
   • 不足：页表大
     • 占用更多的内存
     • 加载时间更长
     • 查找虚页的时间更长
   • 不足：磁盘I/O不够高效
     • 进程加载、页替换

虚存设计问题 —— 页替换设计问题

颠簸

1. 颠簸的概念
   • 频繁发生缺页，运行速度很慢
   • 进程被阻塞，等待页从磁盘取进内存
   • 从磁盘中读入一页_{10ms，执行一条指令}几ns
2. 虚存访问时间
   • 请求平均访问时间 = h*内存访问时间 + (1-h)*磁盘访问时间（h：命中率）
   • 例如：假设内存访问时间 = 100ns，磁盘访问时间 = 10ms，h=0.9
     • 请求平均访问时间 = 0.9*100ns + 0.1*10ms = 1.0009ms
3. 颠簸的原因
   • 进程的工作集 > 可用的物理内存
   • 进程过多，即使单个进程都小于内存
   • 内存没有被很好地回收利用
4. 如何避免
   • 多进程时，哪些工作集放进内存
   • 多进程时，如何分配页

多进程时，哪些工作集放进内存

1. 将进程分为两组
   • 活跃组：工作集加载进内存
   • 不活跃组：工作集不加载进内存
2. 如果确定哪些进程是不活跃的
   • 等待事件（键盘、鼠标等IO设备）
   • 等待资源
   • 典型方法是设定一个等待时间阈值，如果超过了这个阈值则被称为不活跃进程
3. 两种调度器
   • 长期调度器（准入调度器）决定
     • 哪些进程可以同时运行（CPU vs I/O，工作集之和，...）
     • 哪些进程是不活跃的进程，将它们换出到磁盘
     • 哪些进程是活跃的进程，将它们换入到内存
   • 短期调度器（CPU调度器）执行CPU调度算法，决定
     • 把CPU分配给哪个活跃进程

多进程时，如何分配页

1. 多个进程同时运行的时候，替换哪个进程的页框？
   • 全局分配
     • 从所有进程的所有页框中选择
   • 局部分配
     • 只从本进程（发生缺页的进程）的页框中选择
2. 全局分配 vs 局部分配
   • 全局分配
     • 从所有进程的所有页框中选择
     • 可替换其他进程的页框
     • 每个进程运行期间，其内存大小是动态变化的
     • 好处：全局资源调配
     • 坏处：没有隔离，干扰其他进程/收到其他进程的页替换干扰
       • 不能控制各个进程的内存使用量
   • 局部分配
     • 只能从本进程（发生缺页的进程）自己的页框中选择
     • 一个进程运行期间，固定其内存大小不变
       • 页框池：分配给进程的页框的集合，不同进程的页框池大小可不同
     • 好处：隔离，不影响其他进程
     • 坏处：不灵活
       • 进程使用内存频繁会产生颠簸
       • 难以充分利用内存：每个进程对内存的需求不一样

平衡分配

1. 局部分配 + 池大小动态调整
   • 每个进程有自己的页框池（pool）
   • 从自己的池中分配页，且从自己的工作集中替换页
   • 用一种机制来运行时动态调整每个池的大小
     • 初始大小 + 动态调整
2. 进程加载方式：进程换入时
   • 纯粹的按需加载页：加载较慢
   • 预加载：先加载部分页 -> 初始池大小
   • 初始池大小约等于工作集的大小
3. 初始池大小
   • 固定大小：所有进程都一样
   • 平均分配
   • 根据进程大小按照比例分配
4. 动态调整池大小：进程大小变化
   • PFF算法（Page Fault Frequency）
     • 缺页率 PFR：进程每秒产生多少次缺页
     • 对应大多数替换策略，PFR随分配给进程的内存增加而减少
   • 根据进程的PFR来调整分配给它的内存量（pool size）
     • 当PFR高于A，就增加其内存（pool 增大）
     • 当PFR低于B，就缩小其内存（pool 减小）
   • PFR的计算
     • 方法1：只看当前1秒钟内的缺页次数Ri
     • 方法2：求滑动均值
       • 例如 \(PFR_i = (R_i + PFR_{i-1}) / 2\)

后备存储

1. 交换区（Swap Area）
   • 在磁盘上
   • 专门用于存储进程换出页
   • 交换分区（Swap Partition）
     • 用专门的磁盘分区保存专门的换出数据
   • 交换文件
     • 用文件保存换出的数据
2. 交换空间分配
   • 静态分配
     • 创建进程时分配，进程结束时回收
     • 大小：进程映像
     • 进程控制块记录交换空间的磁盘地址
     • 绑定：一个虚存页 <-> 一个磁盘页
       • 磁盘页称为shadow page
     • 初始化：两种方法
       • 页换出：进程映像拷贝到交换区
       • 页换入：进程映像加载进内存
     • 缺点：难以增长（栈段/堆）
   • 动态分配
     • 创建进程时不分配
     • 页换出时分配，页换入时回收
     • 虚页和磁盘页不绑定
       • 多次换出，分配不同的磁盘页
     • PTE中记录页的磁盘地址
     • 一个优化：程序text段
       • 直接用磁盘上的可执行文件作为交换区，减少交换区的大小
       • 换出时直接丢弃（只读的），减少不必要的写回
3. 页地址转换
   • PTE： 虚页 -> 页框和磁盘
     • 如果valid bit=1，物理页号pp#
     • 如果valid bit=0，磁盘页号dp#
   • 换出
     • 将PTE和TLB置为无效
     • 把页拷贝到磁盘
     • 将磁盘页号写回PTE
   • 换入
     • 找一个空闲页框（可能触发页替换）
     • 将页从磁盘拷贝到这个页框中
     • 将页框号填入PTE中，并将PTE置为有效

钉住页（pin/unpin）

1. 为什么需要？
   • 有些页需要频繁访问，换出后又会被换入，影响系统性能
   • 数据再内外存间进行传输时，需要传输的页框不能被换出，否则CPU会把新内容写入这些页框
2. 如何设计？
   • 用一个数据结构来记录所有钉住的页
   • 换页算法在替换页时检查该数据结构
     • 如果页被钉住，则不替换它，重新再选择一页

虚存设计问题 —— 页使用设计问题

清零页

1. 将页清零
   • 把页置成全0
   • 堆和栈的数据都要初始化
2. 如何实现
   • 对于堆和栈段中的页，当它们第一次发生page fault时，将他们清零
   • 可以通过一个专门的线程来实现清零
3. 不做页清零可能会引起安全问题

写时复制（Copy-On-Write）

1. 该技术用于创建子进程（fork系统调用）
2. 原理
   • 子进程的地址空间使用其父进程相同的映射
   • 将所有的页置成 read-only
   • 将子进程置成就绪
   • 对于读，可以随意读
   • 对于写，产生page fault
     • 修改PTE，映射到一个新的物理页
     • 将页内容全部拷贝到新物理页
     • 重新运行发生缺页的指令

进程间共享内存

1. 两个进程的页表共享一些物理页
   • 进程间通信
   • 进程间数据共享
2. 涉及问题
   • 共享页的换入换出
     • 可能会影响到多个进程，需要使用pin/unpin钉住页
   • 有共享页的进程的工作集
     • 共享页优先进入工作集
   • 有共享页的进程结束
     • 根据情况确定是否释放共享页

UNIX 和 Linux 的虚存机制

UNIX的地址空间

1. Text段：只读 & 大小不变
2. 数据段
   • 初始化数据
   • 未初始化数据：BSS段
   • Heap区
3. 栈段
4. 内存映射文件（Memory Mapped File）
   • 将一个文件映射进虚存，并像访问内存一样访问文件
   • mmap 和 unmap

BSD4的虚存

1. 物理内存划分
   • Core map(pin): 所有页框的描述信息
   • 内核(pin)
   • 其它页框：给用户进程
2. 页替换
   • 运行换页守护进程(page daemon)，直到有足够的空闲页
   • 早期BSD使用原始的Clock替换算法（FIFO with Second Chance）
   • 后来的BSD使用双表针的Clock算法
   • 如果page daemon找不到足够多的空闲页的话，则运行swapper
     • 寻找idle时间超过20秒及以上的进程
     • 最大的4个进程

Linux的地址空间

1. 32位机的地址空间
   • 3GB 的用户空间
   • 1GB 的内核空间
2. 栈段从3GB位置向下增长
   • 初始时保存进程的环境变量和命令行参数
3. 数据段
   • 大小可变
   • BSS段：未初始化的全局变量
     • 页加载时初始为0
     • zero page: 避免分配大量全0的物理页
4. 系统调用
   • brk(addr) —— change data segment size
   • mmap(addr,len,prot,flags,fd,offset) —— Map a file in
   • unmap(addr,len) —— Unmap a file
5. Linux的地址转换
   • 2.6.11及之后的Linux都是使用4级页表
     • 虚地址划分为5段: GDT UDT MDT PT 和 Offset
     • 如何支持2级页表的MMU（例如Pentium）
       • 通过将UDT和MDT都设置为只有一个表项
6. Linux的物理页分配
   • 伙伴算法
     • 初始时：只有一个段，含全部可用空间
     • 分配空间，m页：找size>=m 且 size最小的段，假设其为n
     • 如果n>=2m，则将该段对分为两个size=n/2的段
     • 重复对分，直到n>=m>n/2
     • 释放空间：m页，如果其伙伴也是空闲的，则不断合并它们，直到找不到空闲伙伴为止
   • 数据结构
     • 空闲链表数组：每条链上的页大小为2的幂
7. Linux的页替换
   • 方法
     • 保持一定数量的空闲页
     • 文件缓存（page cache）使用Clock算法
     • 未使用的共享页使用Clock算法
     • 用户进程的内存使用改进的Clock算法
       • 两条链
       • Active List：所有进程的工作集
       • Inactive List：回收的候选页
       • Refill是将页从active list移动到inactive list

缺页与换页

进程加载

1. 简单方法
   • 将整个进程加载进内存 -> 运行它 -> 退出
2. 问题
   • 慢（特别是对于大的进程）
   • 浪费空间（一个进程并不是每时每刻都需要所有的内存）
3. 解决办法
   • 按需加载页：只将实际使用的页加载进内存
   • 换页：内存空间有限，只放频繁使用的那些页
4. 机制
   • 一部分虚存映射到内存，另一部分虚存映射到磁盘

缺页处理

1. 内存访问（先查TLB）
2. 若TLB不命中，则进行页表查找，找到PTE
3. 若PTE的valid位=0（页不在内存），则触发缺页（Page Fault）
4. 虚存管理中的缺页处理接管控制，将页从磁盘读到内存
5. 更新PTE：填入PP#，将Valid位置1
6. 重新执行该指令：重新进行内存访问

发生缺页后，如何切换到缺页处理？

• 缺页可能发生在一条指令执行的中途
• 应用程序透明：必须让用户程序不感知缺页
• 需要保存状态并从断点处继续执行

页替换

1. 需要的页不再内存里 -> 需换入 -> 需为它分配一个页框
2. 可能此时没有空闲页框 -> VM需要进行页替换

包含页替换的缺页处理算法

1. 进程A发生缺页，发生缺页的页记为VP
   • 陷入内核，保存进程A的当前状态: PC和寄存器
   • 调用OS的缺页处理模块
     • 检查地址和操作类型的合法性，若不合法则终止进程
     • 为VP分配一个物理页框，记为PP
       • 如果有空闲页框PP1，则用它，记PP=PP1
       • 如果没有空闲页框，选择一个状态为used页框PP2
         • 如果他是脏的(M位=1)，则把它写回磁盘
         • PTE表项的valid置0，刷新TLB
         • 写回完成后，PP=PP2
     • 找到VP对应的磁盘页，把它读到这个页框(PP)中
     • 修改VP的PTE：填入PP#，将valid位置1，并把该PTE加载进TLB
   • 恢复进程A的状态，重新执行发生缺页的指令
2. 通用数据结构
   • 空闲页框链表
   • 一张映射表：页框->PID和虚页

页替换算法

1. 随机选一页
2. 最优算法（MIN）
3. NRU(Not Recently Used)
4. FIFO(First-In-First-Out)
5. FIFO with Second Chance
6. NFU(Not Frequently Used)
7. LRU(Least Recently Used)
8. Aging(Approximate LRU)
9. Clock
10. Working Set
11. WSClock

最优算法（MIN）

1. 算法
   • 替换在未来最长一段时间里不用的页
   • 前提：知道未来所有的访问
2. 例子
   • 内存大小为4个页
   • 访问序列：1,2,3,4,1,2,5,1,2,3,4,5
   • 一共发生6次缺页
3. 好处
   • 是最优的方案，可以作为一种离线的分析手段
4. 坏处
   • 在线系统无法采用，因为不知道未来访问的顺序
   • 没有线性时间复杂度的实现

FIFO

1. 算法
   • 选择最老的页扔掉
2. 例子
   • 内存大小为4个页
   • 访问序列：1,2,3,4,1,2,5,1,2,3,4,5
   • 一共发生10次缺页
3. 好处
   • 实现开销最小
4. 坏处
   • 频繁使用的页被替换

能否通过增加页的数量来减少缺页？

1. 假设内存大小为3个页，访问序列：1,2,3,4,1,2,5,1,2,3,4,5，只发生9次缺页
2. "Belady's Anomaly"现象：采用FIFO算法时，有时会出现分配页数增多，缺页次数反而升高的异常现象

FIFO with Second Chance

1. 核心思想
   • 尽量让频繁使用的页留在内存，不被替换
   • 替换时给访问过的页第二次机会，在内存中呆更长的时间
2. 算法
   • 检查最老页的R位，如果为0，则将其替换
   • 如果为1，则将R位清0，将该页移到队尾，继续查找
3. 例子
   • 内存大小为4个页
   • 访问序列：1,2,3,4,1,2,5,1,2,3,4,5
   • 一共发生8次缺页
4. 好处
   • 实现简单
5. 坏处
   • 最坏情况可以需要很长时间

Clock

1. 改进Second Chance的替换开销
   • 移动开销
2. 算法：把所有页框组织成环形链表
   • 用一个表针指向最老的页
   • 发生缺页的时候，按表针走动方向来检查页
   • 第二次机会
     • 如果R位为1，则将R位清0，且表针向前移一格
     • 如果R位为0，则将该页替换，且表针向前移一格
3. 与Second Chance算法相比
   • 更加高效
4. 如果内存很大
   • 轮转一遍需要很长的时间

LRU

1. 替换最长时间没有使用的页
   • 将所有页框组织成一个链表
   • 前端为最久未访问页（LRU端）：替换的页
   • 后端为最近刚访问的页（MRU端）：新加载的页和命中的页
   • 每次命中将页重新插入 MRU 端
2. 例子
   • 内存大小为4个页
   • 访问序列：1,2,3,4,1,2,5,1,2,3,4,5
   • 一共发生8次缺页
3. 好处
   • 对 MIN 算法的很好近似
4. 坏处
   • 实现困难

NRU（Not Recently Used）

1. 算法
   • 按下面顺序，随机选择一个页
     • 未访问过 且 未修改过
     • 未访问过 且 修改过
     • 访问过 且 未修改过
     • 访问过 且 修改过
2. 例子
   • 内存大小为4个页
   • 访问序列：1,2,3,4,1,2,5,1,2,3,4,5
   • 一共发生7次缺页
3. 好处
   • 实现简单
4. 坏处
   • 需要扫描内存中所有页的R位和M位

LFU（Least Frequently Used）

1. 算法：记录每个页的访问次数，替换访问次数最少的页
   • 每页有一个访问计数器，用软件模拟
   • 每个时钟中断时，所有页的计数器分别和它的R位值相加
2. 例子
   • 内存大小为4个页
   • 访问序列：1,2,3,4,1,2,5,1,2,3,4,5
   • 一共发生8次缺页
3. 坏处
   • 过去访问频繁、现在不访问的页，可能无法被替换出去

Aging

1. 在LFU的基础上消除过去访问的影响
   • 每个时钟中断时，先将所有页计数器右移1位，再将每页计数器最高位与该页的R位相加
   • 替换时，选择计数器最小的页
2. Aging 和 LRU 的主要差别
   • 记录下来的历史更短（计数器长度）
   • 无法区分访问的先后顺序（同一个tick内）
3. Aging需要多少位才够用
   • 实际工作中8位就工作的很好

Working Set

1. 主要思想
   • 80/20原则
     • 80%的访问只涉及20%的内存空间
     • 80%的访问都来自20%的代码
   • 空间局限性
     • 相邻的页很可能会被访问
   • 时间局限性
     • 被访问的页很可能在不远的将来再被访问
2. 工作集的概念
   • 工作集被定义为在最近K次访问的那些页
   • 把工作集放在内存能大大地减少缺页
   • 工作集可以近似为过去T秒钟里使用的页
3. 算法：记录页的"上次访问时间"
   • 在缺页处理时，扫描该进程所有的页
   • 如果R位为1，将该页的上次访问时间设置为当前时间
   • 如果R位为0，计算当前时间和上次访问时间之差
     • 如果差值大于T，则该页在过去T秒里没有被访问过，则替换它
     • 否则，检查下一页
   • 将发生缺页的页加入工作集

WSClock

1. 将 Working Set类似的组织成环形链表（类似 Clock）
2. 按表针走动的顺序来检查页
3. 如果R位为1
   • 将R位置成0，该页的上次访问时间设置为当前时间
   • 检查下一页
4. 如果R位为0
   • 设差值为 当前时间-上次访问时间
   • 如果该值小于等于T，则代表在过去T秒里被访问过，检查下一页
   • 如果该值大于T，则代表在过去T秒里没有被访问过
     • 若M位为1，则将该页写回加入写回链表（异步进行写回），并检查下一页
     • 若M位为0，则将该页替换出去

总结

1. LRU很好但是实现困难，Aging是一个很好的近似LFU
2. Clock被认为是一个很好的实际解决方案
3. 所有的替换算法都不会优化由Cold Miss带来的缺页

计算机存储体系结构

1. 冯·诺依曼结构

2. 层次化存储结构

   • 内存DRAM：快、容量小、易丢失、昂贵
   • 外存磁盘：慢、容量大、不易丢失、便宜

需求一：进程保护

1. 一个进程出错不能影响到其他进程
2. 需要对每个内存访问都进行检查，保证内存访问都合法

需求二：扩展内存和应用透明

1. 一个进程必须能运行再不同的物理内存区域上
2. 一个进程必须能运行在不同的物理内存大小上

问题：如何高效地使用内存空间？

1. 目标1：同时运行多个进程
   • 系统能够运行的进程越多越好
2. 目标2：地址空间足够大
   • 一个大进程，其大小超过物理内存
   • 多个小进程，其大小总和超过物理内存
3. 目标3：保护
   • 一个用户进程不能读取和修改其他用户进程的内存
   • 用户进程不能破坏内核使用的内存空间

解决方案：虚拟内存

1. 基本内存抽象
   • 地址空间：进程的内存视图 -> 虚拟内存
   • 透明使用、高效访问、安全保护
2. 虚拟内存 vs 虚拟CPU
   • 虚拟CPU
     • 进程不与CPU绑定，可以迁移到任一CPU
     • 进程执行时，自以为独占了CPU
     • 进程CPU状态与切换：通过上下文
   • 虚拟内存
     • 进程数据不与物理内存绑定，可以迁移到任意的内存/磁盘空间
     • 进程执行时，自以为独占了内存
     • 进程内存状态：通过swap到磁盘上进行保存

虚拟内存

1. 独立的（进程）地址空间
   • 给每个进程提供一个很大的、静态的"虚拟"内存空间
2. 虚实地址转换
   • 进程运行时，每次访存通过地址转换获得实际的物理内存地址
3. 磁盘作为内存的延展（磁盘交换区）
   • 按需加载：只装载部分地址空间到物理内存

地址空间

1. 独立的进程地址空间 [0,MAX-1]
   • 程序员能够看到的是虚地址
2. 运行时装载部分地址空间
3. 每次访存：虚地址->物理地址
   • CPU 和 进程 看到的是虚地址
   • 内存 和 I/O设备 看到的是物理地址
4. 如果访问到未装载的地址空间
   • 通过OS将它加载进内存

虚存的好处

1. 灵活
   • 进程在执行时才会被放进内存，另一部分在内存/磁盘中
2. 简单
   • 进程的内存访问变得简单
3. 高效
   • 20/80原则：20%的地址空间承担了80%的访问
   • 将20%地址空间放进物理内存
4. 安全
   • 虚实地址转换时进行安全检查，防止非法访问

地址映射

目标

1. 隐式：对每个内存访问，转换是隐式的，用户程序不感知
2. 快速：有转换关系的时候，访存速度非常快
3. 例外：没有转换关系时会触发一个例外
4. 保护：能够隔离用户进程的错误

地址映射和粒度

1. 需要某种"映射"机制
   • 把虚地址空间（大）的内容 放进 物理内存空间（小）
2. 映射必须有合适的粒度
   • 粒度决定灵活性
   • 大粒度映射可能造成内存浪费
   • 细粒度映射则需要更多的映射信息
3. 极端情况
   • 字节粒度映射：映射表过大
   • 进程粒度映射：内存浪费

基址 + 长度（Cray-1中采用的方法）

1. 连续分配
   • 为每个进程分配地址连续的内存空间
   • 用一个二元组来限定其内存区域: <base,bound>
2. 保护
   • 一个进程只能访问[base,base+bound]区间的内存
3. 上下文切换
   • 保存/恢复 基址寄存器
4. 好处
   • 简单：映射时将虚地址和基地址相加
   • 支持换出(swapping)：多进程并发执行
5. 坏处
   • 外部碎片（进程间的碎片）
   • 难以支持进程增大
   • 难以共享内存

内存碎片：随着进程的换入与换出，内存会产生很多空洞（未使用的小区域）

分段

1. 不连续分配
   • 把程序逻辑上划分为若干段：代码、全局变量、栈
   • 每个段分配连续内存，段间不必连续
   • 每个进程有一张段表
   • 每个段采用基址 + 长度
2. 保护
   • 每个段有不同的权限（Read,Write,Exec)
3. 上下文切换
   • 保存/恢复 段表和指向段表的内核指针
4. 好处
   • 相比于基址 + 长度，资源使用更高效
   • 易共享
5. 不足
   • 管理的复杂度增加
   • 仍然存在外部碎片（段间碎片）

虚实地址转换过程

Virtual Address = Seg# + Offset Seg# 通过 Segment Table 映射到 Physical Address

如果 offset > 段Size， 则触发 Memory Violation异常 如果访问地址所在的 Seg# 的 Valid 为0，则触发 Segment Fault异常

分页

1. 分页机制
   • 使用固定大小的映射单元
   • 把虚存划分成固定大小的单元（称为页 Page）
   • 把物理内存划分成同样大小的单元（称为页框 Page Frame）
   • 按需加载（On-Demand Paging）
2. 用页表来记录映射
   • 虚页 -> 物理页
3. 每个表项都有若干个控制位
   • 按页进行保护（Read,Write,Exec)
4. 上下文切换
   • 与分段类似，保存/恢复页表及其地址
5. 好处
   • 分配简单
   • 易共享
6. 坏处
   • 页表很大
   • 进程地址空间有很多空洞：对应的页表项没用

页表项

1. 表达一个映射关系（Page Table Entry，PTE）
   • 虚页号 -> 物理页号
2. 包含如下信息：
   • 物理页框号
   • 有效位：标志该页是否在内存中
   • 保护位：标志该页的访问权限(Read,Write,Exec)
   • 修改位：标志该页是否被修改过
   • 访问位：标志该页是否被访问过
   • 缓存位
3. PTE的数量
   • 假设一页是 4K（12位页内偏移Offset）
   • 32位虚拟地址空间：2^32 = 4G = 4K * 1024
     • 一个PTE的大小为32位 = 4B，故总共为 4MB
     • 如果有10K个进程，那么可能内存连页表都放不下
   • 64位虚拟地址空间：2^64 = 16EB = 4K * 1024 * 1024 * 1024
     • 一个PTE的大小为64位 = 8B，故总共为 8TB
     • 内存连一个页表的大小都放不下

分段 + 分页

1. 先将进程划分为若干段
2. 每个段采用分页
3. 段表记录它的页表地址
4. 不足：仍然存在分段的不足

多级页表

1. 虚地址除去 offset 之外的部分划分为多个段
   • 每段对应一级页表
   • 多个页表
2. 好处：节省空间

示例：二级页表

1. 虚地址：32位，前10位为一级页表索引，中间10位为二级页表索引，后12位为页内偏移
2. 每个页表4KB，共有1024个页表项，下级页表每一项映射1页(4KB)，上级页表映射1024页(4MB)
3. 对于大地址空间，大部分程序都只需要几个页表

反向页表

1. 基本逻辑
   • 64位地址空间，4K页，共有2^{52个页；256MB物理内存，总共有2}16个页框
   • 按物理页索引，记录每个物理页对应的进程ID及虚页
2. 主要思想
   • 每个物理页对应一个PTE
   • 通过Hash查找进行地址转换（Hash(Vpage,pid) -> Ppage#）
3. 好处
   • 页表大小与地址空间大小无关，只与物理内存大小有关
   • 对于大地址空间，页表较小
4. 坏处
   • 查找困难（Hash冲突）
   • 管理哈希链需要大量开销

MMU 和 TLB

地址转换实现

1. 地址类别
   • CPU发出的是虚地址
   • 内存和IO设备接收的是物理地址
2. MMU（Memory Management Unit，内存管理单元）职责
   • 负责虚地址到物理地址转换的硬件单元，通常在片内实现
   • 虚存地址转换到物理地址（每条Load 和 Store指令都需要地址转换）
   • 内存保护，检查地址是否有效
   • 特殊指令操作对应寄存器，记录Base/Bound，或者页目录
3. 操作系统职责
   • 内存管理：新进程分配空间，结束的进程回收空间
   • 进程切换时上下文管理（RISC-V satp寄存器等）
   • 异常处理：内存越界访问、无效地址等

加速地址转换

1. 程序只知道虚地址
   • 每个程序或进程的地址空间是[0,max-1]
2. 每个虚地址必须要进行转换
   • 可能需要逐级查找多级页表
   • 页表保存在内存中，一个内存访问可能变成多个内存访问
3. 解决办法
   • 用速度更快的部件来缓存使用最频繁的那部分页表项

TLB（Translation Look-aside Buffer，地址转换旁路缓冲）

TLB是一种页表的缓冲机制

1. 共有的（必须的）位
   • VP#（虚页号）：与虚地址进行匹配
   • PP#（物理页号）：转换后的实际地址
   • Valid位：标志此表项是否有效
   • 访问控制位：运行内核/用户访问，以及允许何种访问（Read,Write）
2. 可选的（有用的）位
   • 进程标签（pid）
   • 访问标签位（R位）
   • 修改标志位（M位）
   • 缓存标志位

TLB具体流程（硬件和软件不同）

1. CPU先把一个虚地址VA给MMU进行转换
2. MMU先查TLB: VA = VP# || offset
   • 将该虚页号同时与TLB中所有的表项进行比较（硬件支持）
3. TLB hit：TLB里找到含 VP# 的表项
   • 如果有效（TLB的Valid位=1），取表项中的物理页号
   • 如果无效（TLB的Valid位=0），则等同于TLB miss
4. 如果TLB miss（不命中）：TLB中没有含有 VP# 的表项
   • MMU硬件在页表中进行查找，得到PTE / 进入内核异常处理程序，软件在页表中进行查找，得到PTE
   • 将找到的PTE加载进TLB
     • 如果没有空闲表项，则替换一个TLB表项
   • 获取TLB表项中的物理页号 / 重新执行TLB不命中的指令

硬件控制 vs 软件控制

1. 硬件控制
   • 高效
   • 不灵活
2. 软件控制
   • 简化 MMU 的逻辑，是的 CPU芯片上有更多面积可以用于缓存
   • 软件控制更加灵活
   • 可以使用反向页表进行映射，处理大的虚地址空间

TLB 设计问题

1. 替换哪个TLB表项
   • 伪随机 或 LRU算法
2. 上下文切换时需要做什么
   • 有进程标签：修改TLB寄存器和进程寄存器的内容
   • 无进程标签：将整个TLB的内容置于无效
3. 修改一个页表项时需要做什么
   • 修改内存中的PTE
   • 将对应的TLB表项置于无效（刷新TLB）
4. TLB的大小
   • 很小的TLB（64项），能够有很好的TLB命中率
   • 不能太大（不超过256项），CPU的面积有限

进程间通信（IPC Inter-Process Communication）

• 共享资源互斥访问

• 条件同步

• 数据传输

信号量

为什么需要信号量

生产者-消费者问题

• 一个或多个生产者再生成数据后放进了一个缓冲区里
• 单个消费者从缓冲区取出数据处理
• 任何时刻只能有一个生产者或消费者可访问缓冲区

锁方案

• 临界区：读写缓冲区
  • 保证始终只有一个线程访问缓冲区
• 问题：生产者线程释放锁后，可能仍然是生产者线程获得锁
  • 锁能够保护共享资源互斥访问
  • 但锁不能够提供线程条件同步

所需的机制特征

• 表示资源状态：缓冲区空 VS 缓冲区满
• 条件同步：使得多进程/线程根据资源的状态执行

死锁的条件

共享资源访问

锁机制

• 锁获取：是一个原子操作；一个进程获得锁后，其他进程等待
• 锁释放：锁释放后，请求锁的某一个进程可以获得锁
• 锁的原子性：通过进入临界区的原子性保证锁的原子性

资源持有与请求

当资源持有与请求图中形成环路，则代表形成死锁

例如：进程A持有资源R，进程B持有资源S。A在持有R的时候请求S，而B在持有S的时候请求R，这样就导致了死锁。

并发访问控制

通过互斥访问保障 多进程/多线程正确地使用共享资源

临界区（Critical Section）

进程中访问临界资源（共享资源）的一段需要互斥执行的代码

进入临界区

• 检查是否可以进入临界区
• 如果可以进入，则设置相应“正在访问临界区”的标志

退出临界区

• 清除“正在访问临界区”的标志

CPU调度基础

进程调度

• 进程切换和调度
  • CPU是共享资源，进程按照一定的策略使用CPU资源
  • 当发生进程切换时，原先的进程不再使用CPU，切换到新的进程使用CPU
  • 进程切换场景
    • 进程主动放弃CPU使用权
    • 进程等待IO、等待资源（例如锁）
    • 内核不让进程使用CPU（例如有更高优先级进程要运行）
  • 进程调度需求
    • 决定使用CPU的进程
    • 非抢占式调度和抢占式调度

线程的概念

引入线程

• 线程是进程的一部分，具有一段执行流
• 线程在同一个进程的地址空间内，可以共享变量
• 线程是CPU调度的基本单位

进程 VS 线程

进程：

• 运行时：代码、寄存器、堆栈、数据段
• 资源：地址空间、文件描述符、权限等

最简单的进程只有一个线程