操作系统

2018-09-26

第一讲

中央处理器(CPU)

处理器由运算器，控制器，一系列的寄存器以及高速缓存构成
两类寄存器：
- 用户可见寄存器
- 控制和状态寄存器：
  - 程序计数器
  - 指令寄存器
  - 程序状态字
操作系统的需求——保护
- 从操作系统的特征考虑：
  - 并发，共享->实现保护和控制
  - 硬件提供基本运行机制：
    - 处理器具有特权级别，能在不同的特权级别运行不同指令集合
    - 将 OS 和用户程序隔离
处理器的状态(模式：mod)
- 程序状态字寄存器(PSW) 中专门设置若干位
特权指令和非特权指令
- 操作系统需要两种状态： 内核态 和 用户态
- 特权指令：启动I/O 内存清零修改程序状态字设置时钟允许/禁止中断停机
- 非特权指令：控制转移算术访管指令
- x86 支持 R0-R3 四个级别特权指令 R0 相当于用户态 R3 相当于内核态
CPU状态之间的转换
- 用户态->内核态：只能中断/异常/陷入机制
- 内核态->用户态：设置 PSW
- 特殊指令：访管指令（即陷入指令）提供给用户程序接口调用操作系统的功能
  int, trap, syscall, sysenter/sysexit

第二讲

1. 中断机制

操作系统是由 “中断驱动” 或 “事件驱动” 的
主要作用
- 及时处理设备发来的中断请求
- 可使 OS 可以捕获用户程序提出的服务请求
- 防止用户程序执行过程中的破坏性活动
- 等等
中断与异常引入的原因
- 中断的引入：为了支持 CPU 和设备间的并行操作
- 异常的引入：表示 CPU 执行指令时本身出现的问题（算术溢出，除 0 等）
中断/异常的概念
- CPU 对系统发生的某个事件的一种反应，结果：改变控制流
- CPU 暂停当前程序，保留现场，执行处理程序，返回断点继续执行。（实际上现在是返回调度程序，选择一个程序运行而不是立刻返回）
- 特点：
  - 随时发生
  - 自动处理
  - 可恢复

2.事件

中断（外中断）
- I/O 中断
- 时钟中断
- 硬件故障
异常（内中断）/例外
- 系统调用
- 页错误
- 保护性异常
- 断点指令

3.中断/异常机制工作原理

硬件（中断响应）：补货中断源发出的中断/异常请求，以一定方式响应，将控制权交给处理程序
软件（中断处理）：识别中断/异常类型并完成相应的处理

4.中断响应

处理器控制部件中设有中断寄存器
5.中断向量表
中断向量：一个内存单元，存放中断处理程序入口地址和程序运行所需的处理机状态字
硬件执行流程：按中断号/异常类型的不同，通过中断向量表转移控制权给中断处理程序
中断响应示意图
- 硬件只负责保留 PSW 和 PC 两个重要数据（推入系统栈，不是用户栈），其他保护现场工作由中断处理程序操作

6.中断处理程序

设计操作系统时，为每一类中断/异常事件编好处理程序，设置中断向量表
系统运行时若相应中断，中断硬件部分将 CPU 控制权转给中断处理程序
- 保存相关寄存器
- 分析中断/异常的具体原因
- 执行对应处理
- 恢复现场，返回被打断的程序

IA32 中断实例

基本概念——x86

中断：硬件信号引发，分可屏蔽和不可屏蔽
异常：指令执行引发，对于某些异常 CPU 会执行异常处理程序之前产生硬件出错码并压入内核态堆栈
中断控制器 PIC / APIC：转换硬件中断信号为中断向量，引发中断
实模式：中断向量表
- 入口地址 = 段 << 4 + 偏移
- 不支持 CPU 状态切换
- 与一般的过程调用相似
保护模式：中断描述符表
- 采用门描述符（中断描述符）数据结构描述中断向量
- 任务门
  - 中断发生时，必须把取代当前进程的进程的 TSS 选择符放在任务门（linux 未使用）
- 中断门
  - 给出段选择符，段偏移量
  - 通过中断门后系统会自动禁止中断
- 陷阱门
  - 与中断门类似，但不自动关中断
- 调用门（linux 未使用）
具体结构见图
处理过程
- 确定相关向量
- 通过IDTR寄存器找到IDT表，获得中断描述符(表中的第i项)
- 从GDTR寄存器获得GDT的地址;结合中断描述符中的段选择符，在GDT表获取对应的段描述符;从该段描述符中得到中断或异常处理程序所在的段基址
- 特权级检查
特权级检查（数值越小特权级越高）
- 确保 CPL （当前程序运行的权限级别，存放在CS 寄存器中） ≤ 门描述符 DPL
  - 避免应用程序访问特殊的陷阱们或中断门
- 确保 CPL ≤ 段描述符 DPL
  - 当前特权级不低于中断处理程序的特权级
检查是否发生特权级改变，若有，则进行堆栈切换
硬件压栈
若为中断，则清 IF 位（屏蔽中断）
通过中断描述符内偏移和段描述符的地址找到中断处理程序

操作系统运行机制（系统调用）

系统调用 System call

用户在编程时可以调用的操作系统功能
是操作系统提供给编程人员的唯一借口
使 CPU 状态从用户态陷入内核态
系统调用和 C 函数库/ API 接口之间的关系（具体见图）
系统调用对应的代码称为内核函数

系统调用机制设计与执行过程

中断/异常机制
选择一条特殊指令：陷入指令（访管指令）：引发异常，引发用户态到内核态切换
系统调用号与参数：每个系统调用都事先给定编号
系统调用表：存放系统调用服务例程（内核函数）的入口地址
- 中断向量表 ≠ 系统调用表
- 从中断向量表 0x80 （linux）进入系统调用表，再查系统调用表

操作系统完成上述 2-4 工作，第 3 步需要编译器配合
参数传递过程问题，常用三种方法（系统调用号也是一个参数）
1. 由陷入指令自带参数（不推荐，指令长度有限）
2. 通过通用寄存器传递参数（linux 用的比较多）
3. 在内存中开辟专用堆栈区

系统调用举例

编译
CPU 执行到陷入指令
1. 中断/异常机制：硬件保护现场，查中断向量表，转到系统调用总入口程序
2. 系统调用总入口程序：保存现场；把参数保存到内核堆栈；查系统调用表把控制权交给相应系统调用处理例程或内核函数
3. 执行
linux x86 的系统调用
1. 陷入指令 int 128
2. 门描述符：
  - 对 IDT 表第128号门初始化
  - 门描述符的 2， 3 个字节：内核代码段选择符
  - 0，1，6，7字节：偏移量（system_call（）可执行性代码的第一条指令）
  - 门类型：陷阱门
  - DPL：3，与用户级别相同，允许用户进程使用该门描述符
系统执行 int 0x80
- 由于特选级改变，要切换栈；用户栈 -> 内核栈
  
  CPU 要从任务状态段 TSS 中装入新的栈指针（SS：ESP）
- 用户栈信息（SS：ESP）， EFLAGS，用户态 CS， EIP 压栈
- EFLAG 压栈后复位 TF， IF 保持不变
- 用 128 找到门描述符，找出段选择符装入 CS
- 代码段描述符中的基地址 + 陷阱门描述符中的偏移量 → 定位 system_call()的入口地址

sysenter/sysexit 系统调用机制

X86 提供了上述两条指令用以减少系统调用的开销

系统调用作结

完成系统调用需要的条件
- 静态：封装内核函数->库函数，访管指令与陷入机制；编译器；操作系统（初始化，系统调用编号及参数；系统调用表）
- 动态：陷入内核，总入口程序，保存县城，查表分派，执行返回
中断发生后 OS 底层工作步骤
1. 硬件压栈
2. 硬件从中断向量装入新的 PC
3. 汇编语言过程保存寄存器
4. 汇编语言过程设置新的堆栈
5. C语言中断服务程序运行
6. 进程调度程序决定下一个将运行的进程
7. C语言过程返回至汇编代码
8. 汇编语言过程开始运行新的当前进程

机制与策略分离原则

存储系统

进程必须把程序和数据放到内存才能执行
操作系统本身也要放在内存中运行
多道程序系统中，若干个程序和相关数据都要进内存
存储器的层次结构：外存，内存，高速缓存，寄存器
存储访问的局部原理
存储分块
高速缓存

I/O访问技术

I/O 控制使用一下技术
- 程序控制方式
- 中断驱动方式
- 直接存储器存取（DMA）方式

第三讲

进程线程模型

多道程序设计

并发环境：一段时间间隔内，单处理器上有两个或两个以上的程序同时处于开始但未结束的状态，且次序不是事先确定
proceess
- 程序的一次执行过程
- 是正在运行程序的抽象
- 将一个 CPU 变幻成多个虚拟 CPU
- 系统资源以进程为单位分配，每个进程有独立的地址空间
- 操作系统将 CPU 调度给进程
- 进程是具有独立功能的程序关于某个数据集合上的一次运行活动，是系统资源分配和调度的独立单位又称任务（task / job)
- 进程是对 CPU 的抽象
进程的基本状态
- 三种基本状态：运行态，就绪态，等待态(block 阻塞）
- 进程状态之间的转换
  - 运行可以和就绪互相转换
  - 运行可以转换成等待
  - 等待可以转换成就绪
- 进程的其他状态
  - 创建：已完成创建进程所必要的工作（PID， PCB）但未同意执行该进程（资源有限）
  - 终止：终止执行后，进程进入该状态，可完成一些数据统计工作，资源回收
  - 挂起：把一个进程从内存转到外村，进程不占用内存空间，其他进程映像交换到磁盘上，用于调节负载
- linux 进程状体（图）
进程控制块 PCB
- PCB
  - 操作系统表示进程的专门数据结构
  - 记录进程属性，描述进程动态变化过程
  - 又称进程描述符/进程属性
- 操作系统通过 PCB 来控制和管理进程
  - PCB是系统感知进程存在的唯一标志
  - 进程与 PCB 一一对应
- 进程表：所有进程的 PCB 合集
PCB 内容
- 进程描述信息
  - PID
  - 进程名
  - 用户表示符（user id），进程组关系
- 进程控制信息
  - 当前状态
  - 优先级
  - 代码执行入口地址
  - 程序的磁盘地址
  - 运行统计信息(执行时间，页面调度)
  - 进程间同步和通信；阻塞原因
  - 进程的队列指针
  - 进程的消息队列指针
- 所拥有的资源和使用情况
  - 虚拟地址空间的现状
  - 打开文件列表
- CPU 现场信息
  - 寄存器值
  - 指向赋予该进程的段/页表的指针
进程队列
- 操作系统为每一类进程建立一个或多个队列
- 队列元素为 PCB
- 伴随进程状态的改变，其 PCB 从一个队列进入另一个队列

进程控制

进程控制操作完成进程个状态之间的切换，由具有特定功能的原语完成
- 例子：进程创建/撤销/挂起/唤醒
原语：完成某个操作，不可分割（原子操作）
进程何时创建：
- 系统初始化
- 操作系统提供的服务
- 交互用户登录系统
- 由现有进程派生出一个新进程 fork
- 提交一个程序执行
进程的创建
- 给新进程分配一个唯一标识以及进程控制块
- 为进程分配地址空间
- 初始化进程控制块：设置默认值
- 设置相应的队列指针：把新进程加到就绪队列的脸表中
- 创建或扩充其他数据结构
进程的撤销
- 结束子进程或线程
- 收回资源
- 撤销 PCB
UNIX 的几个进程控制操作
- fork(): 通过复制调用进程来建立新的进程，是最基本的进程建立过程
  - 为子进程分配一个空闲的进程描述符 proc 结构
  - 分配给子进程唯一标识 pid
  - 以一次一页的方式复制父进程地址空间
    - 写时复制（存储管理技术） COW
  - 从父进程处继承共享资源，如打开文件
  - 子进程状态设为就绪，插入就绪队列
  - 对子进程返回标识符 0
  - 父进程返回子进程 pid
- exec(): 包括一系列系统调用，它们都是通过用一段新的代码覆盖原来的内存空间，实现进程执行代码的转换
- wait(): 提供初级的进程同步措施
- exit(): 终止

线程模型

多线程的应用
- 解决前台后台的操作处理问题
- 解决应用中的异步问题
- 解决应用执行速度问题
- 解决程序的模块化设计问题 -> 新型程序设计模型
创建线程的开销小雨创建进程的开销
- 创建线程不需要新建地址空间，创建新线程花费时间小
- 线程之间相互通信不需要调用内核（统一进程内的线程共享内存和文件）
线程的基本概念
- 进程的两个基本属性：
  - 资源的拥有者
  - 调度单位
- 将原来进程的两个属性分别处理
  - 线程：进程中一个运行实体，是 CPU 的调度单位
线程的属性
- 有状态及状态转换 -> 需要提供一些操作
- 不运行时需要保存的上下文：程序计数器等寄存器
- 有自己的栈和栈指针
- 共享所在进程的地址空间和其他资源
- 可以创建，请撤销另一个线程（程序开始是一个单线程）
线程的实现
- 用户级线程：在用户空间实现（unix）
  - kernel 不管理线程，由 runtime system 管理
  - 在用户空间建立线程库：提供一组管理线程的函数
  - 运行时系统：完成线程的管理工作
  - 内核管理的是进程，不知道线程的存在
  - 线程切换不需要内核态特权
  - 优点：
    - 线程切换快
    - 调度算法是应用程序特定的
    - 用户及线程可运行在任何操作系统
  - 缺点：
    - 大多数系统调用是阻塞的，因此，由于内核阻塞进程，故进程中所有线程也呗阻塞
      - 解决方案：
      - 修改系统调用为非阻塞的
      - 重新实现对应系统调用的 I/O 函数库
    - 内核只将处理器分配给进程，统一进程中的两个线程不能同时在两个处理器上
- 核心级线程：在内核中实现（windows）
  - 内核管理所有线程管理，并向应用程序提供API接口
  - 内核维护进程和线程的上下文
  - 线程的切换需要内核支持
  - 以线程为基础进行调度
- 混合——两者结合方法：在内核中实现，支持用户线程（例子 Solaris）
  - 线程创建在用户空间完成
  - 线程调度等在核心态完成
  - 多个用户级线程多路复用多个内核级线程
  - Solaris
    - 进程是资源分配和管理的单元
    - 内核级线程是内核的调度单位

第四讲

处理器调度

三个层次
- 长程调度
  - 创建新进程时->决定是否进入当前活跃进程集合
- 中程调度
  - 进程在内外存之间交换
- 短程调度
  - 选择就绪进程或线程进入运行状态，时间短。
短程调度：按调度算法选择
- 如果没有就绪进程，系统会安排一个系统空闲进程或 idle 进程
- 调度程序：挑选就绪进程的内核函数
- 系统场景： N 个进程就绪， M 个 CPU，决策给哪个进程分配哪个CPU
三个问题：
- WHAT：依据什么原则挑选进程/线程以分配 CPU —— 调度算法
- WHEN：何时分配 CPU —— 调度时机
- HOW：如何分配 CPU —— 调度过程（进程的上下文切换）
CPU 调度的时机
- 事件发生 -> 当前运行的进程暂停运行 -> 硬件响应机制 -> 进入操作系统处理响应时间 -> 结束处理后：某些进程的状态会发生变化，也可能又创建了一些新的进程 -> 就绪队列有调整 -> 需要进程调度根据预设的调度算法从就绪队列选一个进程
- 进程正常终止或由于某种错误而终止
- 新进程创建或一个等待进程变成就绪
- 一个进程从运行态进入阻塞态
- 一个进程从运行态变为就绪态
- 内核处理中断后返回用户态时
调度过程——进程切换
- 进程调度程序从就绪队列选择了要运行的进程：这个进程可以是刚刚被暂停的进程，也可能是另一个新进程
- 主要包含两部分工作：
  - 切换全局页目录以加载一个新的地址空间
  - 切换内核栈和硬件上下文，其中硬件上下文包括内核执行新进程需要的全部信息，如 CPU 相关寄存器。
- 场景 A 下 B 上
  - 保存 A 的上下文
  - 用新状态和其他相关信息更新进 A 的 PCB
  - A 移入合适的队列
  - B 该为运行态
  - 恢复 B 的 PCB 和上下文
- 上下文切换开销
  - 直接开销：内核完成切换所用的 CPU 时间
    - 保存和恢复寄存器
    - 切换地址空间（相关指令比较昂贵）
  - 间接开销：
    - 高速缓存，缓冲区缓存， TLB 失效
处理器调度算法的设计
- 什么情况下需要仔细斟酌调度算法
  - 批处理系统 -> 多道程序设计系统 -> 批处理和分时的混合系统 -> 个人计算机 -> 网络服务器
  - 不同操作系统追求的目标不同
- 调度算法衡量指标
  - 吞吐量：每单位时间完成的进程数目
  - 周转时间：提出请求到运行完成
  - 响应时间：提出请求到第一次回应
  - 其他
    - CPU 利用率
    - 等待时间：每个进程在就绪队列中等待的时间
- 设计时考虑的问题
  - 进程控制块 PCB 中需要记录哪些与 CPU 调度有关的信息
  - 进程优先级及就绪队列的组织
  - 抢占式调度与非抢占式调度
  - I/O 密集型与 CPU 密集型
  - 时间片
- 进程优先级（数）
  - 静态优先级：进程创建指定，不能改变
  - 动态优先级：可以改变
- 抢占和非抢占
  - 可抢占式：当有比正在运行的进程优先级更高的进程就绪时，系统可强行剥夺正在运行进程的 CPU（通过中断/事件等），提供给具有更高优先级的进程使用
  - 不可抢占：某一进程被调度后，除非由于它自身的原因不能允许，否则一直运行下去
- I/O 密集型和 CPU 密集型
  - I/O 密集型：频繁 I/O
  - CPU 密集型：需要大量 CPU 时间进行计算
  - 未来对 I/O 密集型进程的调度处理更重要
- 时间片：一个时间段，分配给调度上 CPU 的进程，确定了允许该进程运行的时间长度
  - 考虑因素：进程切换的开销，对响应时间的要求，就绪进程个数， CPU 能力，进程对行
    为
调度算法
- 批处理系统中的调度算法
  - 先来先服务
    - 没有抢占
    - 优点：公平，简单
    - 缺点：
      - 长进程之后的端进程需要等待很长时间，不利于用户的交互体验
      - I/O 资源和 CPU 资源的利用率较低
  - 短作业优先：
    - 最短作业优先
      - 可以抢占（最短剩余时间），也可以非抢占
      - 思路：先完成短的作业，改善短作业的周转时间
    - 最短剩余时间优先
    - 优点/缺点：
      - 最短的平均周转时间（在所有进程同时可运行时，采用 SJF 调度算法可以得到最短的平均周转时间）
      - 不公平：长任务容易得不到处理时间
      - 需要预测未来
  - 最高响应比优先 HRRN
    - 一个综合算法
    - 响应比 R = 作业周转时间/作业处理时间
      =（作业处理时间+作业等待时间）/ 作业处理时间
      = 1 + （作业等待时间/作业处理时间）
- 交互式系统重的调度算法
  - 轮转调度 RR
    - 周期性切换任务，每个进程分配一个时间片，时钟中断->轮换
    - 目标：为短任务改善平均响应时间
    - 时间片选择：
      - 太长——大于典型的交互时间，降级为先来先服务，延长短进程响应时间
      - 太短——小于典型的交互时间，切换开销大？
    - 优缺点：
      - 公平
      - 有利于交互式计算，响应时间快
      - 较高切换花销，时间片 10 ms 切换花费 0.1ms，占比 1%
      - RR 对不同大小的进程是有利的，但是对于相同大小的进程反而延长平均周转时间
    - 改进：虚拟轮转法 Virtual RR
      - 对计算密集型进程如何分配时间片
      - 对 I/O 的进程放进专门的队列
  - 优先级调度
    - 通常系统进程优先级高于用户进程
      前台进程优先级高于后台进程
      操作系统更偏好 I/O 型进程
    - 就绪队列可以按照优先级组织
    - 实现简单；不公平
    - 优先级发转问题（优先级反置/翻转/倒挂）（抢占）
    - 现象：一个低优先级进程持有一个高优先级进程所需要的资源，使得高优先级进程等待低优先级进程运行
    - 影响：系统错误，高优先级停滞，系统性能降低
    - 解决方案：
      - 设置优先级上限（优先级天花板协议）
      - 优先级继承
      - 使用中断禁止
  - 多级队列与多级反馈队列
    - 设置多个就绪队列，第一级队列优先级最高
    - 给不同就绪队列中的进程分配长度不同的时间片，第一级时间片最小；随着队列优先级别的降低，时间片增大
    - 第一级队列为空时，在第二级队列调度，以此类推
    - 各队列按照时间片轮转方式进行调度
    - 一个新创建进程就绪后，进入第一级队列
    - 进程用完时间片儿放弃 CPU，进入下一级就绪队列
    - 由于阻塞儿放弃 CPU 的进程进入相应的等待队列，一旦等待的事件发生，该进程回到原来等级的就绪队列（不一定从队尾进，可以设计）（再次调度上 CPU 时时间片的处理）（非抢占）
    - 若允许抢占
    - 当有一个优先级更高的进程就绪时，可以抢占 CPU
    - 被抢占的进程回到原来一级就绪队列的末尾/队首
  - 其他：
    - 公平共享调度
    - 保证调度
    - 彩票调度

windows 线程调度

调度单位：线程
动态优先级，抢占调度，结合时间配额调整
- 就绪线程按优先级进入相应队列
- 系统总是选择优先级最高的就绪进程让其运行
- 同一优先级的各线程按时间片轮转进行调度
- 多处理机系统中允许多个线程并行运行
线程调度的条件
- 正常调度条件
- 一个线程的优先级改变了
- 一个线程改变了它的亲和(Affinity)处理机集合
Windows使用32个线程优先级，分成三类
- 16-31 实时优先级：不改变优先级
- 1-15 可变优先级：优先级可在一定范围升降。
  基本优先级和当前优先级
- 0 系统线程：零页线程:用于对系统中空闲物理页面清零
所有线程都运行在中断优先级0和1，用户态线程运行在中断优先级0，内核态的异步过程调用运行在中断优先级1（最低的两个）
线程的时间配额：时间单位可以自定义
- 作用：改变优先级会导致低优先级的进程几乎得不到 CPU，但可以给一个进程增加时间配额
调度策略：
- 主动切换
- 抢占
  - 实时优先级被抢占后：重新获得一个完整时间配额
  - 可变优先级被抢占后：剩余时间配额保持不变
- 时间配额耗尽
  - 优先级没有降低：
  - 队列有其他就绪进程，则排回队尾
  - 没有则获得一个新的时间配额
  - 优先级降低：
  - 选择优先级更高的执行
线程优先级提升
- I/O操作完成
- 信号量或事件等待结束
- 前台进程中的线程完成一个等待操作
- 由于窗口活动而唤醒窗口线程
- 线程处于就绪态超过了一定的时间还没有运行 —— “饥饿”现象，
- 针对可变优先级范围内(1至15)的线程优先级

LINUX 进程调度

实时进程
- 对调度延迟的要求最高，要求立即响应并执行
- 调度策略： FIFO， RR
普通进程
- 交互式进程：间或处于睡眠态，对响应速度要求高
- 批处理进程：后台执行，能忍受响应延迟
- 普通进程调度策略： CFS 完全公平调度算法

linux2.4调度算法

单就绪队列+时间片+优先级
对 runqueue中所有进程的优先级依次进行比较，选择最高优先级的进程作为下一个被调度的进程
创建时进程赋予它一个时间片。时钟中断时递减当前运行进程的时间片，进程的时间片用完时，它必须等待重新赋予时间片才能有机会运行
只有当所有 RUNNING 进程的时间片都用完之后，才对所有进程重新分配时间片。这种设计保证了每个进程都有机会得到执行
counter(时间片)越大，优先级越高
- 时间片指的就是 counter 值，每个进程的可能不一样。而且实时进程的 counter 用完之后会立刻重置 counter 然后放入就绪队列，而非实时进程要等待 runqueue 中为空时，统一重新计算 counter
- 普通进程的优先级主要由进程描述符中的 counter 字段决定 (再实时进程要等待runqueue中为空时，统一重新计算counter要加上 nice 设定的静态优先级)
- nice 从最初的 UNIX 沿用而来，表示进程的静态负向优先级，取值范围为 19~-20，以-20优先级最高
缺点：
- 可扩展性不好
- 高负载系统上的调度性能比较低
- 交互式进程的优化并不完善
- 实时进程支持度不够
O(1) 调度器改进
- 优先级计算方法
- pick next 算法
楼梯调度算法 SD
- 抛弃动态优先级，采取完全公平思路
- 为每一个优先级维护一个进程列表，并将这些列表组织在 active 数组中，当选取下一个要调度进程时， SD算法也同样从 active 数组中直接读取
- 用完时间片后下降一级，降到最低一级后回到初始优先级的下一级队列
- 能避免饥饿，交互式进程睡眠时，同等级进程下楼后，交互式进程苏醒后仍在高处能快速调度
RSDL 对 SD 的改进
- 核心：完全公平
- 引入 expired 数组
- 为每个优先级分配一个 “组时间配额” Tg（耗尽后全部下降）
- 同一优先级的每个进程都拥有同样的“时间配额” Tp （耗尽后自己下降一级优先级）
- Tp 与进程的时间片不同，时间片用完后进程直接进入expired数组，一般有 Tp < time_slice，回到初始优先级队列

CFS（Completely Fair Scheduling）

完全公平思想:每个进程获得1/n的时间片时间
每个进程有一个“虚拟运行时间”（vruntime, 已经跑了多久），调度器会的选择虚拟运行时间最小的进程允许，与运行时间成正比，优先级成反比。
虚拟运行时间组织成一棵红黑树,cached最左进程O(1)，调度O(logn)（/linux/include/linux/sched.h）
调度周期：将所有可调度进程全部调度一遍的时间
分配给某个进程p的运行时间，按权重等比例分配。权重：按nice值算出prio_to_weight (/kernel/sched/core.c)
vruntime = (tp/wp)*NICE_O_LOAD
进程更换CPU时的vruntime策略：/kernel/sched/fair.c migrate_task_rq_fair()

BFS

virtual deadline = jiffies + (user_priority * rr_interval)
优先级顺序：realtime/sched_iso/sched_normal/sched_idleprio
利用bitmap维护一个进程队列头指针的数据结构，依次遍历bitmap的低位到高位，存放优先级从高到低的进程队列
选择virtual deadline最小的进程
进程wakeup：抢占/插入，sleep：VD不变，用完时间片：重新计算VD

实时系统调度算法

静态调度：RMS
- 基于优先级的抢占式调度
- 给所有任务静态分配优先级
动态调度
- EDF：最早截止时间优先算法
  - 维护一个ddl队列，每次取队列头调度
- LLF：最低松弛度优先算法
  - 松弛度=ddl-当前时间-任务完成还需要的时间
  - 维护松弛度序列，每次取队列头进行调度
  - 抢占当且仅当松弛度为0，否则会超过ddl
  - 如果松弛度相同，选择最久未调度的进程调度

多处理器调度

对称多处理器：
- 每个处理器运行自己的调度程序
- 对处理器共享资源进程同步
调度算法设计
- 需要决定在哪个 CPU 上执行
- 需要考虑进程在多个 CPU 之间迁移的开销
  - 缓存， TLB 失效
  - 尽可能使进程在同一个 CPU 上运行
- 考虑负载均衡

第五讲

并发环境

顺序环境：只有一个程序运行，独占所有资源，不受外界影响
- 封闭性：独占资源，执行时不受外界影响
- 结果的确定性
- 调度顺序不重要
并发环境
- 程序执行结果不可再现性：结果与相对速度有关，不确定
- 在并发环境下执行是间断的
- 资源共享：系统中资源被多个进程使用
- 独立性和制约性
- 程序和计算不再一一对应
竞争条件
- 读写共享资源最终结果取决于进程运行的精确时序
进程互斥：由于个进程要求使用共享资源，而这些资源需要排他性使用，各进程之间竞争使用这些资源
- 临界资源：系统中某些资源一次只允许一个进程使用，这样的资源称为 临界资源 或 互斥资源 或 共享变量
- 临界区（互斥区）：各个进程中对某个临界资源实时操作的程序片段
  - 没有进程在临界区，想进入临界区的进程可以进入
  - 不允许两个进程同时处于其临界区
  - 临界区外运行的进程不得阻塞其他进程进入临界区
  - 不得使进程无限期等待进入临界区
进程的同步：多个进程中发生的事件存在某种时序关系，需要相互合作，共同完成一项任务

进程互斥的解决方案

软件方案：
- Dekker 算法
- Peterson 算法
硬件方案：
- “开关中断”指令
  - 简单高效，代价高，限制 CPU 并发能力
  - 不适用于多处理器
  - 适用于操作系统本身，不适用于用户进程
- “测试并加锁”指令
以上解决方案会导致忙等待
- 自旋锁 Spin lock （多处理器使用忙等待：可能其他 CPU 会在忙等待期间开锁，尽可能避免进程切换带来的开销）
临界区导致的优先级反转

生产者/消费者问题

又称为有界缓冲区问题
睡眠与唤醒原语，避免忙等待。

典型的同步机制

信号量和 PV 操作

test&set指令会锁住总线，是一条比较贵的指令
信号量：
- 一个特殊变量
- 用于进程间传递信号的一个整数值（semaphore）
- 结构体：count/queue
P/V操作：
- P操作：
  - s.count–
  - if s.count < 0：
    - 进程进入阻塞状态，并将进程插入等待队列s.queue的末尾
    - reschedule()
- V操作：
  - s.count++
  - if s.count <= 0：
    - 唤醒s.queue中的一个进程，
    - 改变状态为就绪态，并插入就绪队列
- 定义及性质
  - P/V操作为原语操作（执行过程中不允许中断）
  - 在信号量上定义了三个操作：初始化（非负数）/P操作/V操作
  - 最初提出二元信号量（互斥原则），之后推广到了一般信号量（0/1，多值）或计数信号量（semaphore>1，解决同步问题）
- 用P/V操作解决进程间互斥问题
  - 分析并发进程的关键活动，划定临界区
  - 设置信号量mutex，初值为1
  - 在临界区前实施P(mutex)，临界区后实施V(mutex)
- 解决生产者消费者问题（同步问题）
  - 定义三个信号量：(Initialize)
    - mutex = 1: 互斥信号量，控制对临界区的访问
    - empty = N: 空缓冲区个数信号量
    - full = 0: 满缓冲区个数信号量
  - producer进程产生item后P(empty)然后P(mutex),首先P一个空缓冲区，接着P一个互斥互斥锁，在insert操作后，V掉mutex再V出一个full，表示生产出了一个可用的满缓冲区。
  - cosumer进程在获取要消耗的item前需要P掉一个full，再P掉mutex，随后获取remove的item，接着V掉mutex，再V掉一个empty，表示一个item已被消耗。

管程

为什么引入管程？信号量机制的不足：程序编写困难/效率低
一个程序设计的语言成分，高级同步操作
定义：
- 是一个特殊的模块
- 由关于共享资源的数据结构及在其上操作的一组过程组成
- 进程与管程：进程只能通过调用管程中的过程来间接的访问管程中的数据结构
互斥：
- 管程是互斥进入的：为了保证管程中数据结构的完整性
- 管程的互斥性是由编译器负责保证的
同步：
- 管程中设置条件变量及等待/唤醒操作以解决同步问题
- 可以让一个进程或线程等待在条件变量上等待（此时应先释放管程的使用权），也可以通过发送信号将等待在条件变量上的进程或线程唤醒。
允许多个进程同时在管程中
- 问题：一个进程进入管程执行等待操作，释放了管程的互斥权。而后面进入管程的进程执行唤醒操作时（例如P唤醒Q），进程中便存在两个同时处于活动状态的进程
- 解决：
  - P等待Q执行(Hoare)
  - Q等待P继续执行(MESA)
  - 规定唤醒为管程中最后一个可执行的操作(Hansen)
- Hoare管程
  - 条件变量：在管程内部说明和使用的一种特殊类型变量
    - 可以执行wait和signal操作
    - wait(c):如果紧急等待队列非空，则唤醒第一个等待者，否则释放管程的互斥权，执行此操作的进程进入c队列尾部
    - signal(c):如果c队列为空，相当于空操作；如果非空则唤醒第一个c队列中的等待者。
    - 用管程解决生产者消费者问题
      - 条件变量：full/empty，count计数
      - insert过程：
        
        if count == N: wait(full);
        
        insert(item); count++;
        
        if count == 1: signal(empty);
      - remove过程：
        
        if count == 0: wait(empty);
        
        remove = remove_item; count–;
        
        if count == N-1: signal(full);
    - 管程实现的途径：直接构造/间接构造：用某种已经实现的同步机制去构造（例子：信号量P/V操作实现管程，PPT读者写者问题）
- Mesa管程
  - Hoare管程：signal的缺陷
    - 两次额外的进程切换
    - 是否会使条件队列中的进程永久挂起？
  - 解决：signal->notify
    - notify(x)：当一个正在管程中的进程执行notify(x)时，会使x等待队列中的队首进程进入就绪状态，在CPU可用时调度上CPU
    - 注意需要用while判断条件，因为不保证在等待过程中没有其他进程进入管程
    - further改进：broadcast(x)：notify在条件变量x上等待的所有进程

PTHREADS：锁（解决互斥问题）/条件变量（解决同步问题）

锁（互斥量）
- 提供两个过程：上锁和解锁
- 即mutex：互斥量
- 注意两个过程函数：
  - Pthread_mutex_lock: acquire a lock or block
  - Pthread_mutex_trylock: acquire a lock or fail
条件变量
Pthread_cond_wait(&condp, &mutex)/Pthread_cond_signal()
- 先解锁
- 然后等待唤醒信号
- 然后上锁
先lock mutex因为在判断buffer是否非空的时候被打断会出现问题
判断条件用while而不是if，因为在wakeup之后可能会出现条件发生改变的情况

第一类读者写者问题

增加并发性：不需要所有的读者都P&V
只需要第一个读者P最后一个读者V即可
添加计数器rc
- rc++;
- if rc==1: P(w);
- {… rc–; }
- if rc==0: V(w);

锁的实现

lock():
- disable interrupts
- if(value == FREE):
  - value = BUSY
- else:
  - 添加线程等待该锁
  - 切换至下一个可运行线程
- enable interrupts
硬件解法：忙等待，一直占用CPU等待锁
用户态解法：主动让出（yield）

通信机制

解决信号量及管程的不足/多处理器情况下原语失效的问题
基本通信方式：消息传递/共享内存/管道/套接字/远程过程调用（RPC）
消息传递
- send(dest, message)/recieve(src, message)
- 消息缓冲区：消息头/消息体组成一个消息结构体
- 发送者执行send()，陷入内核，将消息复制给消息缓冲区，再将消息结构体指针入队（接收进程的PCB中的消息队列）。接收者执行receive()，将内核中的相应的消息取回。
- 同样可以用消息传递的方式实现生产者消费者问题：
  - 生产者recieve(cousumer, &m); m = build_message(); send(cosumer, &m);
  - 消费者先send一些空message给生产者，然后recieve(producer, &m); m = extract_message(); send(producer, &m);
共享内存
- 进程的某一片地址空间映射到同一片物理内存
- 相互通信的进程间需要建立公共内存区域，从而实现信息传递
管道（pipe）
- 利用一个缓冲传输介质——内存或文件连接两个相互通信的进程
- 字符流方式写入写出
- 管道通信机制必须提供的协调能力：互斥/同步/接收进程是否存在
套接字

第五讲

死锁

一组进程中，每个进程都无限等待被该组进程中另一进程所占有的资源，因而永远无法得到资源，这种现象被称为进程死锁，这组进程被称为死锁进程
为什么会出现死锁？资源数量有限/锁和信号量使用错误
可重用资源：可以被多个进程重复使用
可抢占资源/不可抢占资源
可消耗资源：只可使用一次的可以创建和销毁的资源
活锁与饥饿的区别：活锁加锁，轮询，没有进展也没有阻塞；饥饿：资源分配策略决定
产生死锁的必要条件：
- 互斥使用
- 占有且等待（请求和保持，部分分配）：已有部分资源，还需要新的资源
- 不可抢占（不可剥夺）：资源申请者不能从占有者手中抢夺
- 循环等待： P1 等 P2， P2 等 P3， ….. ,Pn 等 P1

资源分配图（RAG）

用有向图描述资源系统和进程的状态
资源类：用方框表示，进程实例：用方框中的黑圆点表示，进程用圆圈表示
带方向的箭头表示进程对资源的占有和请求
死锁定理：资源分配中没有环路，则系统中没有死锁。如果图中存在环路那么可能会存在死锁。
如果每个资源类中只有一个资源实例，则环路是死锁存在的充分必要条件。
图的化简：
- 1. 找一个非孤立点进程节点且只有分配边，删去该边和相应的边
- 2.？？？
- 重复 1/2

死锁解决

不考虑此问题 —— 鸵鸟算法

阻止死锁发生

死锁预防：静态策略——设计和事的资源分配算法，不让死锁发生
- 破坏产生死锁的条件
  - 破坏互斥使用条件
    - 资源转换技术：独占变为共享资源
    - SPOOLing 技术：设计一个 ”精灵daemon“ 进程/线程负责管理打引进，进程需要打印时，将请求发给该 daemon，由它完成打印任务
  - 破坏占有且等待条件
    - 方案1: 要求每个进程必须一次性申请它所要求的所有资源，均可满足时才分配
      
      问题：资源利用率低， “饥饿”
    - 方案2: 在允许进程动态申请资源前提下规定，在拿不到资源进入等待之前，必须释放已占有的全部资源，若需要则重新申请
  - 破坏不可抢占条件
    - 实现方案：虚拟化资源
    - 当一个进程申请的资源被其他进程占用时，可以通过操作系统抢占这一资源（优先级不同）
    - 局限性：适用于状态易于保存（CPU，内存）和恢复的资源
  - 破坏循环等待条件
    - 实现方案：资源有序分配法
    - 系统中资源标号，申请时必须按递增次序进行
    - 实现时的问题：资源如何编号
死锁避免：动态策略——以不让死锁发生为目标，跟踪并评估资源分配过程，根据评估结果决策是否分配
- 定义：在系统运行过程中，对每一个资源申请进行同台检查，根据检查结果决定是否分配，若可能死锁则不予分配，否则于一分配

-     安全状态： 如果存在一个由系统中所有进程构成的安全序列 P1,...,Pn 则系统是安全的
-    安全序列： 一个进程序列是安全的， 如果对于每一个 Pi， 它**以后尚需要的资源量**不超过系统当前剩余的资源量与前面进程**当前占有**资源量之和（即在前面进程返还资源后能满足要求）， 系统处于安全状态
-     不安全状态： 不存在一个安全序列。
-      不安全状态一定导致死锁（但不代表已经死锁）

-      银行家算法： 仿照银行发放贷款时采取的控制方式而设计的一种死锁避免算法
    -    系统具有的特征：
        -    在固定数量的进程中故乡数量固定的资源
        -     每个进程预先制定完成工作所需要的最大资源量
        -      进程不能申请比系统中可用资源总数还多的资源
        -      进程等待资源的时间是有限的
        -      如果系统满足了进程对资源的最大需求， 那么进程应该在有限时间内使用资源然后返还
    -    n 进程总数， m 资源类总数
    -     available array[1~m] 
        <br> max [n][m]
        <br> allocation [n][m]
        <br> need [n][m]
        <br> request [n][m] (这一次申请)
        <br> 简写时忽略资源维度
        -    （1） if request[i] ≤ need[i]
            <br> 转（2） <br> else 返回错误
        -    （2） if request[i] ≤ avaliable <br> 转(3) <br> else 等待
        -      (3) 进行分配运算 修改各个数据结构
    -    检查安全状态
        -    work[m] 
        -     finish[n] （进程是否结束）
        -     (1)work = avaliable <br> finish = false
        -  (2)寻找满足条件的 i <br> finish[i] == false && need[i] ≤ work <br>不存在转到(4)
        -  (3)work += allocation[i] <br> finish[i] = true <br> 转(2)
        -  (4)若所有的i， finish[i] == true, 则处于安全状态

让死锁发生 —— 死锁检测与解除

允许死锁发生，操作系统不断监视系统进展情况，判断死锁是否发生
一旦死锁发生则采取专门的措施，解除死锁并以最小的代价恢复操作系统运行
检测时机：
- 当进程由于资源请求不满足而等待时检测死锁（缺点：系统开销大）
- 定时监测
- 系统资源利用率下降时检测死锁
一个简单的死锁检测算法
- 每个进程和资源编号
- 设置一张资源分配表记录各进程与其占用的资源之间的关系
- 设置一张进程等待表记录各进程与要申请的资源之间的关系
- 用两张表判断是否形成回路
死锁解除：
1. 撤销所有死锁进程（开销大）
2. 进程回退再启动(开销大)
3. 按照某种原则逐一撤销死锁进程，直到…
4. 按照某种原则逐一抢占资源(资源被抢占的进程必须回退到之前的对应状态),直到…

哲学家就餐问题

为防止死锁发生可采取的措施

最多允许四个哲学家同时坐在桌子旁
仅当一个哲学家左右两边的筷子都可用时，才允许他拿筷子
给所有哲学家编号，奇数号必须先拿左，偶数号必须先拿右

第八讲基本内存管理

物理内存管理方案

空闲内存管理

数据结构
- 位图（等长）：每个分配单元对应于图中的一个位， 0 空闲， 1 占用（或相反）
- 空闲区表：每一项纪录空闲去的起始地址，长度，下一个块
- 空闲表
分配算法
- 首次适配
- 下次适配
- 最佳适配
- 最差适配

伙伴系统（Linux 底层内存管理采用）

一种经典的内存分配方案，一种特殊的“分离适配”算法
主要思想：将内存按2的幂次进行划分，组成若干空闲块链表，查找该链表找到能满足进程需求的最佳匹配块
一开始整个一块

大小大于一半-> 全部分配

否则划成一半，重复过程
不是伙伴的块不进行合并

基本内存管理方案（逻辑空间）

单一连续块：每次只允许一个程序，独占全部内存，总被加载到同一个内存地址
固定分区：划分若干区域
可变分区：根据进程需求，从内存空间分割出一个分区分配给该进程
- 紧缩技术：在内存移动程序，将所有小的空闲区合并为较大的空闲区
- 正在 I/O 的进程不能移动
页式：逻辑空间按页（和物理空间大小相同）分配成大小相同的区域，逻辑相邻的页物理不一定相邻
- 物理页面 page fream 又称页框页帧
- 虚拟页面 page 又称页
段式：按进程逻辑分若干段，内存动态化分若干不等长区域
- 逻辑地址：段号+段内地址
- 段表：段的起始地址 + 段长度
段页式
- 段中分页，物理内存管理比较简单（克服段式缺点）

内存扩充

目标：在较小储存空间运行较大程序时遇到的矛盾
内存紧凑（没有空间是假象）
覆盖技术
- 程序执行过程中，程序的不同部分在内存中相互替代（如 if else 不会同时执行）
- 按照自身逻辑结构将那些不会同时执行的程序段共享同一块内存区域
- 要求程序各模块之间有明确的调用结构
- 程序员声明覆盖结构，操作系统完成覆盖
- 缺点：
  - 编程困难
  - 效率低
交换技术
- 将内存某些进程暂时移到外存，把外存某些进程换进来
- 进程的什么部分交换到磁盘
  - 有的部分是磁盘中本来就有，有的部分是动态产生的
  - 运行时创建或修改的内容：堆和栈（这部分是产生的）
- 有部分动态产生的写回到什么位置
  - 一般系统会指定一块特殊的磁盘区域作为交换空间，包含连续的磁道，操作系统可以使用底层的磁盘读写对其高效访问
- 交换时机
  - 只要不用就换出（很少再用）
  - 内存空间不够或有不够的危险时就换出
  - 与调度器结合使用
- 如何选择被换出的进程
  - 考虑进程的各种属性；不应换出处于 I/O 等待的进程
- 换出后再换入的进程是否回到原处
  - 不一定，采用动态重定位
- 如何处理进程空间增长
  - 栈和堆相向而长
虚存技术

页式管理

页表项：记录了逻辑页号和页框号的对应关系
每个进程一个页表，存放在内存
页表的起始地址保存在 context 中
地址转换（硬件支持）
- CPU 取到逻辑地址，自动划分为页号和页内地址，用页号查页表，得到页框号，再与页内地址拼接为物理地址

第九讲虚拟页式管理

操作系统对存储的抽象：地址空间
操作系统协调各存储器的使用
虚拟内存
- 构建在存储体系之上
- 提供给用户进程一个幻象
- 一个比物理内存空间大的多的地址空间
- 满足：地址独立，地址保护
虚存
- 内存和磁盘结合使用得到一个容量很大的“内存”
- 受寻址机制和可用磁盘容量限制
当进程运行时，先将一部分装入内存，另一部分暂时保存在磁盘，当要执行的指令或访问的数据不在内存时，由操作系统将他们从磁盘装在进来

虚拟页式存储管理

基本思想
- 装载程序时，不是装入全部页面，而是装入几个或零个页面
- 如果进程执行时需要的页面不在内存，则动态装入所需
- 需要时，将内存中暂时不用的一些页面交换到磁盘以便获得更多的内存空间
通常有两种方式
- 请求调用
- 预先调页
MMU：内存管理单元
如何处理页表巨大的问题
地址重定位与快表（TLB）
一种最常见的 Page Fault -> 缺页中断
驻留集管理
置换策略
清楚策略
加载控制

页表表项的设计

页框号PFN
有效位P：表示该页是在内存还是在磁盘
访问位A：引用位
修改位D：页面是否被修改过
保护位（读/写/执行）

一个进程的页表的各页在内存中若不连续存放，则需要引入地址索引 -> 页目录
注意：页表本身也放在虚存中（进程运行时，部分页表映射到内存）
两级页表：顶级页表起始地址放在 context 中，加载到内存
虚拟地址-> 页目录偏移（10） + 页表偏移（10）+ 页内偏移（12）
- 64位（实际只有48位地址使用）：每个表项64位，四级页表 9 + 9 + 9 + 9（地址翻倍长度，能存的数量减半） + 12
引入反转页表：从物理地址指向虚拟地址
- 从物理地址空间出发，系统建立一张页表
- 页表项纪录进程 i 的某虚拟地址与页框号的映射关系
- 直放：由 vpn 得到一个物理表项，如果冲突，另行计算
  - 对应物理位置放入 pid 和 vpn 信息（虚拟地址： vpn + offset）
  - 取的时候找 vpn 相同的再检验pid
- 用 pid 和 vpn 做 hash确定表项
  - 查询的时候效率比较高
- PowerPC， UltraSPSRC 和 IA-64使用
- 页表大小和物理内存相关和地址无关。
地址转换（硬件机制）
- 页面不在内存/页面非法/页面受到保护…
  
  硬件产生一程 page fault
- 否则页框号 = 页表[虚页号]；物理地址 = 页框号 + 页内偏移
快表（TLB）的引入
- 页表->两次获两次以上的内存访问
- CPU 的指令处理速度与内存指令的访问速度差异大， CPU 速度得不到充分利用
- 相联存储器，按内容并行查找（一个周期内同时查找所有项）
- 保存正在进行进程的页表的子集（部分表项）

缺页异常处理

有空闲页框->分配，内存中没有空闲页，置换（修改过的部分要写会）

驻留集管理

驻留集大小：给每个进程分配多少页框
固定分配策略
可变分配策略
- 根据缺页率评估进程局部性表现
- 高-> 增加/ 低-> 减少
- 系统开销
置换问题
- 置换范围
  - 局部/全局
  - 固定分配职能使用局部置换
- 置换策略
  - 放置（分配）
  - 置换（替换/淘汰）
  - 所有策略的目标 -> 置换最近最不可能访问的页
  - 根据局部性原理：最近的访问历史和最近将要访问的模式间存在相关性，因此，大多数策略都基于过去的行为来预测将来的行为
  - 注意：置换策略设计得越精致复杂，实现的软硬件开销就越大
  - 约束：不能置换被锁定的页框
    - 例如：操作系统核心代码，关键数据结构， I/O 缓冲区
    - 用户进程锁定的上限有限
页面置换算法
- 最优置换算法 OPT
  - 设计思想：置换以后不再需要的或最远的将来才会使用的页面
  - 实现：无法实现
  - 作用：作为标杆，接近这个算法的算法就比较好
- 先进先出
  - 选择再内存中驻留时间最长的页置换（参照：超市撤换商品）
  - 实现：页面链表法
- 第二次机会只换算法 SCR
  - 按照先进先出算法选择某一页面，检查其访问位 R，如果为 0，则置换该页；如果为 1，则给第二次机会，并将访问位置 0
- 时钟算法 Clock（一种实现方式而不是算法设计）
  - 移动指针来选择页框
  - 实现：优先选择不需要写回的
- 最近未使用算法（NRU）
  - 选择在最近一段时间内未使用过的一页纸换
  - 实现：设置页表表项的两位：访问（R），修改（M）
  - 启动一个进程时， R， M 置为 0， R位定期清零（复位），修改后 M 置 1
    - 0: 无访问无修改
    - 1: 无访问有修改
    - 2：有访问无修改
    - 3：有访问有修改
    - 从上到下一次选，从同一类中随机选择
- 最近最少使用 LRU
  - 选择最后一次访问时间距离当前时间最长的一页置换
  - 性能接近 OPT
  - 实现：时间戳或维护一个访问页的栈
    - 开销大
  - 硬件实现 n x n 矩阵
    - 访问时把对应行置 1，对应列置 0，（k，k）值位0
    - 把值最小的行换出对应的页面换出
- 最不经常使用算法 NFU
  - 但选择访问次数最少的页面置换
  - LRU 的一种软件解决方案（提出者声称）
  - 实现：
    - 软件计数器，一页一个，初始为0
    - 每次时钟中断：计数器加 R（被访问的）
    - 发生缺页时，选择计数器值最小的置换
- 老化算法 Aging （改进 NFU）
  - 模拟 LRU：计数器在加 R 前先右移一位， R 加在技术起的最左端（高位）
Belady 现象：
- 系统给某进程分配 m 个页框，并不是 m 越大缺页越少（某些算法产生的异常现象）
- 如：用 FIFO，考虑 1 2 3 4 1 2 5 1 2 3 4 5， m = 3 / 4 时， m=4 缺页10次， m=3 缺页9词
- 算法满足栈式算法则不会产生这样的异常现象（如 LRU）
影响缺页次数的因素
- 页面置换算法
- 页面本身的大小
  - 页面尺寸问题
    - 是硬件指标，对于操作系统是个可选参数
    - 多种页面尺寸，为有效使用 TLB 带来灵活性，但给操作系统带来复杂性
    - 要考虑的因素
    - 内部碎片
    - 页表长度
    - 辅助储存的物理特性
    - 页面尺寸和缺页率关系
    - 缺页率：先上升再下降
- 程序的编制方法
  - 页面大小 4K，只有一个页框，矩阵A[1024][1024] 按行存放
  - 按列访问和按行访问缺页次数：按列每次修改一位就加载下一个页，而按行则每次赋值完
- 分配给进程的物理页面数：页框越多，缺页次数越少：减少速度不断下降（成本越来越高）
  - 存在平衡点 W
  - 工作集模型
颠簸（抖动）：虚存中，页面在内存与磁盘之间的频繁调度，使得调度时间比实际运行时间长，导致系统效率下降

工作集模型

基本思想：局部性原理，一般情况下，进程在一段时间内总是集中访问一些页面，这些页面称为活跃页面，如果能提供与活跃页面数相等的页框数，则可减少缺页次数
工作集 W = (t,∆) = 该进程在过去的∆个虚拟时间单位中使用的虚拟页面集合
- 工作集内容取决于三个因素
  - 访问序列特性
  - 当前时刻 t
  - 工作集窗口长度 ∆
驻留集：当前时刻进程实际驻留在内存当中的页框集合
两者关系：
- 工作集是进程运行过程中固有的性质，驻留集取决于操作系统分配的页框数和页面置换算法
改进：
- 监视每个进程的工作集
- 周期性地从一个进程的驻留集中移去那些不在它工作集的页面（可以用 LRU 策略）
- 只有当一个进程的工作集在内存中时，才可以更好地工作，即进程的驻留集包括了它的工作集
工作集算法：
- 找出一个不在工作集的页面置换
- 思路
  - 每个页表项中增加一个字段：记录该页面最后一次被访问的时间
  - 设置一个时间值 T
  - 判断：根据一个页面的访问时间是否略在“当前时间 - T”之前或之中决定该页面是否在工作集中
- 实现：扫描所有页表项执行操作
  - 一个页面的 R 为 1，设置最后访问时间为当前， R 设为 0
  - 如果 R 为 0，则检查是否不在工作集
    - 是，被替换
    - 不是，记录当前所有扫描的最小值，继续扫描
讨论
- 很多操作系统试图采用工作集算法
- 其中的一种方法是考虑进程的缺页率并监视来达到类似效果 —— 缺页旅算法
页面置换算法小结：见图

清除策略

分页系统工作的最佳状态：发生缺页异常时，系统中有大量的空闲页框
结论：保存一定数目的页框供给比使用所有内存并在需要时搜索一个页框有更好的性能

分页守护进程

实现：
- 设计一个分页守护进程，多数时间书面，定期唤醒检查内存状态
- 如果空闲页框过少，分页守护进程通过预设的页面置换算法选择页面换出内存
- 如果页面装入内存后被修改过，则将它们写回磁盘
分页守护进程可保证所有的空闲页框都是“干净”的
当一个进程需要使用一个已置换出的页框时，如果该页框还没有被新的内容覆盖，则它从空闲页框缓冲池中恢复即可
清楚策略实现
- 使用一个双指针时钟，前指针由分页守护进程控制：当它指向一个“脏”页面时，就把该页写回磁盘，前指针向前，仅仅向移动指针
- 后指针用于页面置换，与标准时钟算法一样
- 由于分页守护进程的工作，后指针命中干净页面的概率会增加

页缓冲技术

目的：提高性能
思路：
- 不丢弃置换出的页，将它们放入两个表之一：如果未被修改，则放到空闲页链表种，如果修改了则放到修改页链表
- 被修改的页以簇的方式写回磁盘（不是一次只写一个，减少 I/O 操作数量，减少磁盘访问时间），写回后放入空闲页链表
- 被置换的页仍然保留在内存中，一旦进程又要访问该页，可以迅速将它加入该进程的驻留集集合（代价很小）

加载控制

系统并发读：驻留在内存中的进程数目
- 通过调节并发进程数进行系统负载控制
解决方案：进程挂起

其他问题

内存映射文件

基本思想：进程通过一个系统调用将一个文件映射到虚拟地址空间的一部分，访问这个文件就象访问内存中的一个大数组而不是对文件读写
在多数实现中，在映射共享的页面时不会实际读入页面内容，而是访问时每次一页载入，磁盘文件则被当作后备存储
当进程退出或显式解除映射时，修改会写回磁盘

策略和机制分离

控制系统复杂度的重要方法：机制和策略分离
不一定管理全部要在内核
讨论（基于 Mach 微内核操作系统）
- 存储管理系统分为三部分
  - 底层 MMU 处理程序（与机器相关）
  - 做为内核一部分的缺页中断处理程序（与机器无关）
  - 运行在用户空间中的外部页面调度程序（策略）

第十讲 Windows 虚存管理

x86

Windows 虚存管理

内存管理器的组成部分
- 一组执行体系服务程序部分
- 一个页面错误陷阱处理程序
- 工作集管理器（16）
- 进程栈交换器（23）
- 修改页面写出器（17）
- 映射页面写出器（17）
- 零页线程（0）
动态产生的内容在需要写回磁盘时，写回到专门的交换空间（windows 中称为页面文件page file）
windows 无效的 PTE
- 所引用的页面没有被提交（不在内存）
- 尝试违反权限的页面访问
- 修改一个共享的写时复制页面
- 需要扩大栈
- 所引用的页已被提交但尚未被映射（清除策略收回了页面，但页面实际存在）
- 请求一个零页面
页目录
- 物理地址包存在 KPROCESS
- 硬件访问页目录，页表，页通过 PFN 完成
- 内核：通过虚地址来对它们进行访问，实际上在 x86 还同时映射到0xc0300000
- 专用寄存器 CR3 用于保存页目录物理地址
页目录自映射机制
- 1024 页的页表能表示整个地址空间
- 那么必定存在一页代表了页目录（两者内容相同）
- 0xc0300000 前十位和中间十位相同
  - PD[0x300] 即自映射目录项
windows 的工作集（windows 中工作集等驾驭驻留集）
- 驻留在物理内存中的虚拟页面的子集
- 进程工作集：为每个进程分配的一定数量的页框
- 系统工作集：为可分页的系统代码和数据分配页框
- 工作集大小动态变化：开始执行后，随着访问新页面逐步建立较稳定的工作集
- 内存访问的局部性区域的位置大致稳定时，工作集大小页大致稳定
- 局部性区域的位置改变时，工作集快速扩张和收缩过度到下一区域
页面置换算法
- 基于工作集模型
  - 由以装入内存的页框组成
  - 最小值（一开始的时候都 load 进来）/最大值（超过最大时，如果有空闲还是会分配）
  - 当可用页框数量数量降低到一定程度时，启动工作集修正策略
- 平衡集管理器线程（调度算法中提到过，每秒醒来一次）调用工作集管理器
  - 周期性检查：大量可用内存，内存开始紧张，内存紧缺
用户空间内存分配方式
- 以页为单位的虚拟内存分配方式（Virtualxxx）
  - 进程地址空间 0～0x7fffffff ，用户必须经过保留和提交两个阶段
  - windows 中用 VAD 来解决判断保留页面的问题
  - 每一个进程，内存管理器维护一组虚拟地址描述符（VAD）来描述一段被分配的进程虚拟空间的状态（结构：平衡二叉树）
- 内存映射文件（CreateFileMapping， MapViewOfFile）
  - windows 中使用区域对象（底层），开放的接口：文件映射对象
  - 为大数据流和文件共享服务
  - 两个进程对同一个区域对象建立视图时，发生了区域共享
  - 对区域读写与读写数组一样
- 内存堆方法（Heapxxx 和早起的借口 Loaclxxx 和 Globalxxxx）
  - 适合大量小内存申请
物理内存管理
- 页框号数据库（PFN数据库）
- 结构 MMPFN（24字节）：保存每一个物理页的相关信息
  - 页框的状态
    - 活动（Active） / 有效（Valid）：在工作集中
    - 过度（Transition）：系统正在从一个文件将内容读入该页框，或者写出该页内容
    - 空闲（Free）
    - 零初始化（zeroed）空闲且为 0
    - 坏（Bad）该页框存在硬件错误，不能被使用
    - 后备（standby）：
    - 曾经在某个进程工作集里，且该页框的内容还没有改变
    - 但该页框已经被移出工作集，只是 PTE 被标记为 invalid 和 transition（两位表示 standby）
    - 当此进程需要再次访问这一页，直接把该页框从 stanby 变为 active（valid）
    - 修改（modify）：
    - 有修改的 standby
    - 在被其他进程使用之前写回
- 全局变量 MmPfnDatabase 保存页框号数据库的首地址
支持写时复制技术

第十一讲文件系统

文件系统的基本概念

文件是对磁盘的抽象
所谓文件是指一组带标识（即文件名）的，在逻辑上有完整意义的信息项序列
信息项：构成文件内容的基本单位（单个/多个字节），各信息项之间具有顺序关系
谁建立/谁使用谁解释
文件系统：操作系统中统一管理信息资源的子系统，管理文件的存储，检索，更新，提供安全可靠的共享和保护手段，并且方便用户使用
- 统一管理磁盘空间，实施磁盘空间的分配和回收
- 实现文件的按名存取（名字空间映射磁盘空间）
- 实现文件信息的共享，提供数据可靠性和安全保障
- 向用户提供一个方便使用，维护的接口，并向用户提供相关信息
- 提高文件系统性能
- I/O 接口相关
文件的分类
- 普通文件
- 目录文件：管理文件系统的系统文件
- 特殊文件
文件的逻辑结构
- 文件内部结构：从用户角度看文件，由用户的访问方式确定
- 流式文件 / 记录式文件（操作系统角度）
- 堆结构 / 顺序结构 / 索引结构（数据库管理系统角度）
文件的存取方式
- 顺序存去
- 随机存取
存储介质与物理块
- 磁盘 / SSD / 磁带 / …..
- 物理块
  - 存储设备划分为大小相等的块，统一编号
  - 以块为单位进行信息的存储、传输、分配
磁盘结构
- 扇区：标题、数据、 ECC 纠错信息
- 三个动作：
  - 寻道
  - 旋转延迟
  - 数据传输
文件属性
- 文件控制块（或元数据）FCB：操作系统为管理文件而设置的数据结构，存放了为管理文件所需的所有有关信息
- 常用属性：文件名、文件号、保护、口令….
文件操作
- create / delete / open / close
文件目录
- 统一管理每个文件信息
- 将左右文件的管理信息阻止在一起，即构成文件目录
- 目录项
  - 构成文件目录的基本单元
  - 目录项可以是FCB，目录是文件控制块的有序集合
- 目录文件（记录式）
  - 将文件目录以文件的形式存放在磁盘上
  - 一种特殊类型的文件，其内容由目录项组成
- 只允许内核修改目录，应用程序通过系统调用访问目录
- 树形结构目录

文件系统布局

概述

实现文件系统需要考虑：磁盘与内存中的内存布局
- 磁盘上
  - 如何启动所存储的操作系统
  - 磁盘是怎样管理的？即怎样获取磁盘的有关信息？
  - 目录文件在磁盘上存放？普通文件在磁盘上怎么存放
- 内存中
磁盘分区：把一个物理磁盘的存储空间划分为几个相互独立的部分，称为分区
文件卷：逻辑分区，由一个或多个物理块组成
- 一个文件卷可以是整个磁盘或部分磁盘或跨盘（RAID）
- 同一个文件卷中使用同一份管理数据进行文件分配和磁盘空闲空间管理，不同的文件卷中的管理数据是独立的
- 一个文件卷上: 包括文件系统信息、一组文件（用户、目录）、未分配空间
- 物理块/块/蔟：一个或多个（2的幂）连续的扇区， 可寻址数据块
- 格式化：在一个文件卷上建立文件系统的过程
磁盘上的内容
- 引导区：通常为第一个，从改卷引导操作系统所需信息，每个卷一个
- 卷（分区）信息
- 目录结构（目录文件）
- 用户文件

磁盘上文件系统的布局

UNIX
- 主引导记录 — 分区表 — 分区1 - 分区2….
- 每个分区结构
  引导记录 - 超级数据块（管理数据） - 空闲区管理 - I-节点区 - 根目录区 - 文件和目录区
WINDOWS
- FAT 文件系统
  - 引导区 - 文件分配表1 - 文件分配表2（与1一摸一样） - 根目录 - 其他目录和文件
- NTFS 卷
  - 引导区 - 主控文件表 - 系统文件 - 文件存储区

文件的物理结构

文件在物理介质上的存放方式，也是系统分配给文件的物理块的位置和顺序
要考虑的问题：
- 存储效率：外部碎片等
- 读写性能：访问速度
连续结构（顺序）：文件的信息是存放在若干连续块
- 优点
  - 简单、高效
  - 支持顺序存取和随机存取
  - 所需的磁盘寻到次数和寻到时间最少
  - 可以同时读多个块，检索一个块容易
- 缺点
  - 文件不能动态增长：
    - 预留空间：浪费或重新分配和移动
  - 不利于文件内容的插入和删除
  - 外部碎片问题：存储紧缩技术
链接结构：一个文件的信息存放在若干不连续的物理块中，各块之间通过指针连接
- FCB 只需要记录首块指针
- 优点
  - 提高磁盘空间利用率，不存在外部碎片
  - 忧虑与文件的内容插入和删除
  - 有利于文件动态扩充
- 缺点
  - 指针占一些空间，数据不是整数次幂
  - 可靠性问题：链接指针出错
  - 更多的寻到次数和时间
  - 存取慢，不支持随机存取
- 变形： FAT 结构，把所有指针放在一起而不是放在各块
  - windows 中 FCB = 目录项，包含起始蔟号
  - 表项由三种值： 0（没分出去），下一块号， -1（结束）
  - FAT 表所有文件共享一张
    - FCB -> FAT表中某项 -> …. -> -1
索引结构：系统为每个文件简历一个专用数据结构——索引表，并将这些块的块号存在一个索引表中，一个索引表就是磁盘块地址数组，其中第 i 个条目指向文件的第 i 块
- 问题：索引表很大，需要多个物理块存放时怎么办
- 索引表组织：
  - 链接方式：一个盘块存一个索引表，多个索引表
  - 多级索引
  - 综合（UNIX）（UNIX FCB = 目录项 + I-节点）
    - 每个文件的索引表 15 个索引项，每项 2 字节
    - 最前面 12 项直接存放文件信息的物理块号（直接寻址）
    - 第 13 项指向一个物理块，该块中最多可以存放 256 个文件物理块的块号（一级索引表）
    - 对于更大的文件，还可以利用第14和第15项作为二级和三级索引表
目录文件：文件目录在磁盘上的存储方式（操作系统使用）
- windows 目录项 = FCB
- 组织方式：
  - 顺序
  - 散列表（hash）
  - B 树/B+ 树（NTFS系统使用）
文件目录检索
- 文件名 -> 文件目录 -> 磁盘
- 访问一个文件两个步骤
- 步骤1:
  - 目录检索 —— 文件名 -> FCB
  - 文件名解析：把逻辑名字转化为物理资源
- 步骤2: 文件寻址
目录文件的改进：加快目录检索
- 一种解决方案
  - FCB 分成两部分
    - 符号目录项：文件名、文件号
    - 基本目录项：文件名以外的字段
  - 例子： UNIX 的 I节点
UNIX 文件系统
- FCB = 目录项 + I 节点
- 目录项：文件名 + I 节点好
- 目录文件由目录项构成
- I 节点：描述文件的相关信息
- 每个文件由一个目录项、一个I节点和若干磁盘快构成
Windows —— FAT16 文件系统（16 表示 FAT 表项大小）
- FAT16
  - 蔟： 1、2、4、8、16、32 或 64 扇区
  - 文件系统的数据记录在“引导扇区”中
  - 文件分配表 FAT 的作用：描述蔟的分配状态、标注下一簇的蔟号
  - FAT 表项： 2字节（16位）
  - 目录项： 32 字节
  - 根目录大小固定
- 引导区
  - MBR 主引导扇区 —— 0号扇区
  - DBR 一般引导扇区
  - MBR / DBR 结束标志 0x55AA，开头为跳转到引导代码
- 文件分配表 FAT
  - 可以看成一个整数数组，每个证书代表数据去的一个蔟号
  - 状态：未使用、坏蔟、系统保留、被文件占用（下一簇号）….
FAT32
- 根目录不固定大小
- 目录项仍然 32 字节，但有不同类型： “.“目录项， ”..“目录项、短文件名目录项、长文件名目录项
- 支持长文件名格式，支持 Unicode，无法支持高级容错特性
- 一个文件至少对应两个目录项（名字越长占用越多）
空闲块管理
- 位图
- 空闲块表
- 空闲块链表
  - 成组链接法
  - 每组第一块不空，用来放下一组的空闲块块号
  - 专用块记录空闲磁盘块的第一组空闲块的块号
  - 专用块放在空闲管理区
  - 第一组的第一块分出去之前要复制到专用块里
  - 倒数第二组的索引最多 99 个，因为最后一组没有管理块
运行时文件结构 UNIX
- 系统打开文件表
  - 整个系统一张
  - 放在内存：用于保存已打开文件的 FCB
  - FCB + 引用计数 + 修改标志
- 用户打开文件表
  - 每个进程一个
  - 维护打开文件的状态和信息
  - 进程的PCB中记录了用户打开文件表的位置
  - 文件描述符+打开方式+读写指针+系统打开文件表入口
文件操作的实现
- 创建文件：使之时创建文件的 FCB
  - 分配足够的存储空间
  - 在目录中为新文件建立一个目录项，根据提供的参数及需要填写有关内容
  - 目的：建立系统与文件的联系
- 打开文件：
  - 根据文件名在文件目录中检索，并将该文件的目录项读如内存，建立相应的数据结构，为后续的文件操作做好准备
  - 返回文件描述符 / 文件句柄
文件共享：一个文件被多个用户或进程使用
- 目的：节省时间和存储空间 / 交换信息
- 一种实现 —— 文件别名
  - 硬链接：利用多个路径名描述统一共享文件，多个目录项只想一个文件
    - Link 命令：在用户自己的目录中对要共享的文件建立起相应的表目，即建立两个文件的等价关系
    - Linux 例子：
    - 多个文件名的目录项指向同一个 i 节点
    - i 节点中增加引用计数字段
  - 软链接（符号链接/快捷方式）：建立一种特殊类型的文件，通过文件内容与另一个文件建立链接
    - 建立一种特殊类型的文件
    - 只有真正的文件所有者才有指向 i 节点的指针
    - 系统开销大
挂在和卸载
- 将一个文件系统加入到另一个文件系统
- 用户提供：被挂在的文件系统的根目录/挂载点

第十二讲文件系统的管理

文件系统的管理

文件系统的可靠性
- 可靠性：抵御和预防各种物理性破坏和人为破坏的能力
- 坏块问题：禁止使用
- 备份：通过转储操作，形成文件或文件系统的多个副本
  - 全量转储：定期将所有文件拷贝到后援处理器
  - 增量转储：只转储修改的文件，即两次本分之间的修改，减少系统开销
  - 物理转储：从磁盘第 0 块开始，将所有磁盘块按序列输出到磁带
  - 逻辑转储：从一个或几个指定目录开始，递归地转储自给定日期后所有更改的文件或目录
文件系统的一致性（源数据的一致性）
- 问题的产生：磁盘块 -> 内存 -> 写回磁盘块，写回之前系统崩溃，则文件系统出现不一致 - 解决方案：设计一个实用程序，当系统再次启动时，运行该程序，检查磁盘块和目录
  - UNIX 检查过程：两张表，每块对应表中一个计数器，初值为 0
    - 表1记录每块在文件中出现的次数
    - 表2记录每块在空闲块表中的出现次数
文件系统写入方式
- 考虑文件系统一致性和性能
- 通写
  - 内存中的修改立即写到磁盘
  - 缺点：性能差
  - 例： FAT 文件系统
- 延迟写（lazy-write）
  - 利用回写缓存的方法得到高速
  - 可恢复性差
- 可恢复写
  - 采用事务日志来实现文件系统的写入
  - 既考虑安全性，又考虑速度性能
  - 例： NTFS
文件系统的安全性
- 安全性：确保未经授权的用户不能存取某些文件
- 数据丢失 -> 备份解决
- 入侵者
- 文件保护机制
  - 文件保护：用于提供安全性、特定的操作系统机制
    - 对拥有权限的用户，应该让其进行相应操作，否则应该禁止
    - 放置其他用户冒充对文件进行操作
  - 用户身份验证
    - 用户登录时，检验其身份（用户是谁，用户拥有什么，用户知道什么）
    - 口令
    - 物理坚定：磁卡、指纹、签名分析、手指长度分析
  - 访问控制
    - 主动控制：访问控制表
    - 每个文件一个，放在内核空间
    - 记录用户 ID 和访问权限
    - 用户可以是组，文件也可以是组
    - 能力表
    - 每个用户一个，放在内核空间
    - 记录用户可以访问的权限
- UNIX 的文件保护
- 数据恢复技术
  - 数据恢复的原理：数据未被真正破坏，只是组织形式被破坏，操作系统或用户不能访问

文件系统的性能

提高文件系统性能的方法：目录项（FCB）分解、当前目、磁盘碎片整理、磁盘（块）高速缓存、磁盘调度、提前读取、合理分配磁盘空间、信息的优化分布、RAID技术

磁盘高速缓存

内存中为磁盘块设置的一个缓冲区，保存了磁盘中某些块的副本
当出现一个对某一特定块的 I/O 请求时，首先检测以确定改块是否在磁盘高速缓存中
如果在直接读写；否则加载到高速缓存，再拷贝到需要的地方
利用局部性原理
有些系统成为文件缓存、块高速缓存、缓冲区高速缓存
块高速缓存的组织、置换、一致性
- hash 表（检索块） + 链表（计算 LRU）

提前读取

思路：每次访问磁盘，多读入一些磁盘块
依据：空间局部性
开销：较小（只有数据传输时间）
具有针对性

windows 的文件访问方式

不使用文件缓冲
- 普通方式
使用文件缓冲
- 预读取，每次读取的块大小、缓冲区大小、置换方式
- 写回。写回时时机选择，已知性问题。
异步模式
- 不再等待磁盘操作完成
- 使处理器和 I/O 并发工作
cache manager 实现对缓存的控制（使用文件缓冲）
- 读取数据的时候预取
- 定时保护一致性

合理分配磁盘空间

分配块时，把有可能顺序存取的块放在一起
- 尽量分配在同一柱面上，减少磁盘臂的移动

磁盘调度

当多个访盘请求在等待时，采用一定的策略，对这些请求的服务顺序调整安排
降低平均磁盘服务时间，达到公平、高效
公平：一个 I/O 请求在有限时间内满足
高效：减少设备机械运动带来的时间浪费
- 减少寻道时间
- 减少延迟时间
先来先服务：
- 优点：简单、公平
- 缺点：效率不高，相邻两次请求可能会造成最内到最外的柱面寻道，使磁头反复移动，增加了服务时间，对机械也不利
最短寻道时间有限：优先选择距当前次头最近的访问请求进行服务，主要考虑寻道优先
- 优点：改善平均服务时间
- 缺点：不公平，饥饿
扫描算法/电梯算法
- 当设备无访问请求，不动
- 有访问请求，按一个方向移动，在移动过程中对遇到的请求进行服务，然后判断该方向上是否还有访问请求，如果有则继续扫描；否则改变移动方向，并为经过的请求服务，如此反复
单向扫描调度算法
- 总是从 0 号柱面开始向里扫描
- 按照各自要访问的柱面位置的次序去选择访问者
- 移动臂到达最后一个柱面后，快速返回 0 柱面
- 返回时不进行服务
N-step-scan
- 把磁盘请求队列分成长度为 N 的子队列，每一次用 SCAN 处理一个子队列
- 在处理某一队列时，新请求必须添加在….
FSCAN
- 两个队列，开始时都在一个队列，新请求在另一个队列，然后交换
旋转调度算法：根据延迟时间来决定执行次序的调度
- 分析：
  - 若干等待访问者请求访问同一磁头的不同扇区
  - 若干等待访问者请求访问不同磁头的不同编号的扇区
  - 若干等待访问者请求访问不同磁头上具有相同的扇区
- 解决方案
  - 对于前两种情况：总是让首先到达读写磁头位置下的扇区先进行传送操作
  - 对于第三种情况：这些扇区同时到达读写磁头位置下，可任意选择一个磁头读写或传送

信息的优化分布

记录在磁道上的排列方式也会影响输入输出操作的时间

记录的成组与分解

记录的成组：把若干个逻辑记录合成一组存放一块的工作
进行成组操作时必须使用内存缓冲区，缓冲区的长度等于逻辑记录长度乘以成组的块因子
目的：提高了存储空间的利用率；减少了启动外设的次数，提高系统的工作效率
记录的分解：从一组逻辑记录中吧一个逻辑记录分离出来的操作

RAID 技术

设计时要考虑的是：磁盘存储系统的速度、容量、容错、数据灾难后的数据恢复
解决方案： RAID （独立磁盘冗余阵列）
- 多块磁盘按照一定要求构成，操作系统则将它们看成一个独立的存储设备
目标：提高可靠性和性能
把多个磁盘（物理）组织在一起，作为一个逻辑卷提供磁盘跨越功能
数据组织：
- 通过把数据分成多个数据块，并行读出/写入多个磁盘，提高传输率（条带化 strip）
- 通过镜像或校验操作，提供容错能力（冗余）
最简单的 RAID：镜像 / 最复杂的 RAID：块交错校验

RAID 0 - 条带化

数据分布在阵列的所有磁盘上
有数据请求时，同时多个磁盘并行操作
充分利用总线带宽，数据吞吐率提高，驱动器负载平衡

RAID 1 - 镜像

最大限度保证数据安全及可恢复行
所有数据同时存在两快盘的相同位置
利用率 50%

RAID 2 并行访问 - 海明码校验

专门盘放校验码（条为单位）

RAID 3 - 叫错位奇偶校验

以字节单位将数据拆分，交叉写入
专门放置一个存储校验盘，保存奇偶校验

RAID 4 - 交错块奇偶校验

和 RAID 3 类似，块为单位

RAID 5 - 交错块分布式奇偶校验

奇偶校验分散在各个磁盘（分布式）
数据读出效率高，写入效率一般
磁盘利用率好

RAID 6 交错块双重分布式校验

参考 4 ，5

RAID 7 最优化异步高 I/O 速率及高数据传输率

有一个操作系统独立主机运行

文件系统的结构设计

文件系统分类
- 磁盘文件系统
- 数据库文件系统
- 日志文件系统
- 网络/分布式文件系统
- 虚拟文件系统
如何定义对用户接口
- 文件及属性、文件操作、目录结构
如何将逻辑文件系统映射到物理磁盘设备
- 数据结构及算法
文件系统实现时如何分层
虚拟文件系统：对多个不同文件系统的抽象
- 功能：
  - 提供相同的文件和文件系统接口
  - 管理所有文件和文件系统关联的数据结构
  - 高效查询历程，遍历文件系统
  - 与特定文件系统模块的交互
日志结构文件系统
- LFS Log-structured File System
- 思路：提高磁盘写操作的效率 -> 避免寻找写的位置
- 典型写操作：改变文件目录i节点、目录项、文件i节点、文件本身
- 把整个磁盘看作是一个日志，每次写到其末尾。集中（按一段）写入日志末尾，将 i 节点和文件内容一起写入，建立子 i 节点表
- 清理线程：扫描日志，清理，生成新的段
日志文件系统
- 借鉴日志文件结构文件系统设计思路：鲁棒性
- 保存一个日志：记录系统下一步要做什么
- 系统出错后，恢复时查看日志，完成所作操作
- windows 的 NTFS， Linux 的 ext3、 ReiserFS
- 步骤：例如删除一个文件
  - 操作：
    - 目录中删除
    - 释放 i 节点
    - 磁盘块归还到空闲
  - 实际操作：
    - 写日志项（3个操作）
    - 日志项写入磁盘
    - 执行操作
    - 擦除日志项（做一个操作擦一个）

Windows 文件系统模型

NTFS 文件系统

基于原子事务概念
NTFS 对关键文件系统信息采用冗余存储
NTFS 提供了综合的安全模型，支持加密文件系统
NTFS 多级目录结构，支持别名
NTFS 文件由多个文件属性构成，每个属性由属性名和属性流（属性值）组成 - 如：文件内容（data， ….） data 为属性名
NTFS 的磁盘结构
- 卷
  - 可以一盘多卷，可以一卷多盘
- 蔟
  - 逻辑蔟号 LCN：整个卷中的蔟号
  - 虚拟蔟号 VCN：文件内部的蔟从头到尾编号
文件名/目录名：最多255字节，可以包含 unicode
- 每个文件有一个 64位的，称为引用号的唯一标示
- 文件引用号的组成
  - 文件号（48位，该文件在 MFT（主控文件表）中的位置）
  - 文件顺序号
主控文件表 MFT （类似 i 节点）
- 每个记录对应一个文件或目录
- 自身也是一个文件
- 每个文件/目录至少有一个 MFT
- 一般：每个 MFT 的前几十个字节有固定头结构，用以描述本 MFT 项的属性（如是否占用等）；之后的字节用于存放属性；其余信息可以放到卷中其他可用蔟中
- 访问文件：先找 MFT 项，再根据其中信息找到文件内容
NTFS 对属性提供各种操作
- 读写都是针对属性
- 常驻属性与非常驻属性
  - 标准信息、文件名、索引根是常驻属性（常驻在 MFT）
  - 延展或延伸： MFT 之外的区域，可存放变长的非常驻属性

分布式文件系统

分布式计算机系统
- 强调资源、任务、功能和控制的全面分布
工作方式
- 任务分布
- 功能分布
分布式文件系统
- 完成的功能类似于传统操作系统中的文件系统，永久性存储和共享文件，允许用户直接存取远程文件而不需要将它们复制到本地
HDFS
- 分布式，部署在低廉设备上
- 高容错、高吞吐、适合大数据集
- 块存储
  - 默认一块 64M
  - 如果文件大小小于数据块，也不独占
  - 为什么用块存储：减少寻址规模
- 流式读写
  - 校验和检验
  - 只支持在文件末尾添加数据
  - 不支持在任意位置修改
  - 并发读
  - 不并发写
- 数据冗余

第十三讲 I/O 系统

I/O 的特点
- I/O 性能经常是系统性能的瓶颈
- 操作系统庞大复杂的原因之一
  - 资源多、杂，并发均来自 I/O（不同 I/O 各种属性例如速度，数据表示，传送单位不同）
  - 与其他功能联系密切，特别是文件系统
CPU 与设备的连接
- 设备控制器
  - CPU 和 I/O 设备的接口
  - 特殊寄存器
设备分配——按数据特征分
- 字符设备
  - 字节为单位，传输速率低，不可寻址（键盘、鼠标）
  - I/O 命令： get(); put(); 通常使用文件接口和语义
- 块设备
  - 以数据块为单位，传输速率较高，可寻址（随机读写）（磁盘）
  - I/O 命令：原始 I/O 或文件系统接口；内存映射文件访问
- 网络设备
  - 格式化报文交换（以太网、蓝牙）
  - I/O 命令： send/receive 网络报文；通过网络接口支持多种网络协议
设备的分类 —— 从资源分配角度
- 独占设备：一段时间一个进程使用，一般为低速设备（打印机）
- 共享设备：多个进程交叉使用，效率高（磁盘）
- 虚设备：在一类设备上模拟另一类：如用共享设备模拟独占设备，被模拟的称为虚设备
I/O 管理
- 应用程序/文件管理 -> I/O 设备管理 -> 设备控制器中的特殊寄存器
- 设备管理器：逻辑I/O（设备无关） + 设备驱动程序 + 中断服务程序
I/O 管理的目标和任务
- 完成用户的请求，控制设备的各种操作，完成 I/O 设备与内存之间的数据交换，最终完成用户的I/O请求
  - 设备分配与回收
    - 记录设备的状态
    - 根据用户的请求和设备的类型（可能独占，需要分配给对应进程），采用一定的分配算法，选择一条数据通路
  - 执行设备驱动程序，实现真正的I/O操作
  - 设备终端处理：处理外部设备的中断
  - 缓冲区管理：管理 I/O 缓冲区
- 建立方便、同意的独立于设备的接口
  - 方便性：向用户提供使用外部设备的方便接口，使用户使用时不考虑设备的复杂物理特性
  - 统一性：对不同的设备采取统一的操作方式，在用户程序中使用的是逻辑设备
  - 逻辑设备与物理设备、屏蔽硬件细节
- 充分利用各种技术（通道、中断、缓冲、异步I/O等）提高CPU与设备、设备与设备之间的并行工作能力，充分利用资源，提高资源利用率
  - 并行性
  - 均衡性（使设备充分忙碌）
- 保护
  - 设备传送或管理的数据应该是安全的、不被破坏的、保密的

I/O 硬件组成

一般由机械和电子两部分组成
- 机械部分是设备本身（物理装置）
- 电子部分又称为设备控制器（或适配器）
  - （端口）地址译码
  - 按照主机与设备之间约定的格式和过程接受计算机发来的数据和控制信号或向主机发送数据和状态信号
  - 将计算机的数字信号转换成机械部分能识别的模拟信号或反之
  - 实现设备内部硬件缓冲、数据加工等提高性能或增强功能
控制器的作用
- 操作系统将命令写入控制器的接口寄存器/缓冲区，以实现输入/输出，并从借口寄存器读取状态信息或结果信息
- 当控制器接受一条命令后，可独立于 CPU 完成制定操作；命令完成时，控制器产生中断通知系统；通过读控制器中的信息，获得结果和状态；
- 控制器与设备之间低级借口
- 任务：串行位流转为字节块，进行必要的错误修正

I/O 端口地址

I/O 端口地址：接口电路中每个寄存器具有的、唯一的地址，是个整数，也叫 I/O 地址
所有I/O端口地址形成I/O端口空间（受到保护）
主要两种形式：
- 内存映射编址（内存映射I/O）
- I/O 独立编址（I/O 专用指令）

I/O 独立编址

端口地址空间与内存地址无关
优点：
- 外设不占用内存地址空间
- 编程时易于区分内存操作和I/O操作
缺点： I/O 端口操作的指令类型少，操作不灵活

内存映射编址

分配各系统中所有端口的地址空间与内存的地址空间统一编址
把I/O端口看作一个存储单元，对I/O的读写操作等同于对内存的操作
优点：
- 凡是可对内存操作的指令都可对I/O端口操作
- 不需要专门的I/O指令
- I/O 端口可有较大地址空间
缺点：占用内存地址空间
内存映射 I/O 可以直接用内存保护机制进行保护，不需要其他特殊机制，但要避免把包含控制寄存器的那部分地址空间放入任何用户的虚拟地址空间之中
内存映射 I/O 的每一条指令也可以引用控制寄存器
- 要注意对设备控制寄存器不能进行高速缓存，否则无法探测到变化，为避免这一情形，硬件必须针对每个页面具备选择性禁用高速缓存的能力，操作系统必须管理选择性高速缓存，增加了复杂性
内存映射 I/O ：如果只存在一个地址空间，那么所有的内存模块和所有的I/O设备都必须检查所有的内存引用，以便了解谁做出响应
- 如果单一总线，那么让每个内存模块和I/O设备查看每个地址是简单易行的

I/O 控制方式

可编程I/O （轮询/查询）
- 由 CPU 代表进程给 I/O 模块发 I/O 命令，进程进入忙等待，直到操作完成才继续执行
中断驱动I/O
- 目的：减少设备驱动程序不断得询问控制器状态寄存器的开销
- 实现： I/O 操作结束后，由设备控制器主动通知设备驱动程序
DMA
I/O 部件的演化
1. CPU 直接控制外围设备
2. 增加了控制器或I/O不见， CPU 使用非中断的可编程 I/O
3. 与2相同，但采用了中断方式。 CPU 无需花费等待执行一次 I/O 操作所需的时间，因而提高了效率
4. I/O 部件通过 DMA 直接控制存储器，可以在没有 CPU 参与的情况下，从内存中移出或者往内存中移入一块数据，仅仅在传送开始和结束时需要 CPU 干预
5. I/O 部件增强为一个单独的处理器，有专门为 I/O 设计的指令集； CPU 指导 I/O 处理器执行内存中的一个 I/O 程序。 I/O 处理器在没有 CPU 干涉的情况下取指令并执行这些指令
6. I/O 部件有自己的局部存储器（其本身就是一台计算机）：使用这种体系结构可以控制许多 I/O 设备，并且使需要 CPU 参与程度降到最低（通常用于控制与交互终端的通信， I/O 处理器负责大多数控制终端的任务）

I/O 软件设计

分层的设计思想
- 底层处理硬件相关特性
- 上层屏蔽细节
软件层次
- 用户级 I/O
- 设备无关的 OS 软件
  - 驱动程序的统一接口
  - 缓冲
  - 错误报告
  - 分配与释放设备
  - 提供与设备无关的块大小
- 设备驱动
- 中断处理
- 硬件
设备独立性
- 用户编写的程序可以访问任意 I/O 设备，无需实现制定设备
- 用户：使用逻辑设备名
- 系统：除了底层软件，其他部分不依赖硬件

缓冲技术

提高 CPU 与设备的并行性
减少中断请求次数
缓冲区分类
- 硬缓冲：由硬件寄存器实现（如：设备中设置的缓冲区）
- 软缓冲：在内存中开辟一个空间，用作缓冲区
缓冲区管理
- 单缓冲
- 双缓冲
- 缓冲池（多缓冲，循环缓冲）：统一管理多个缓冲区，采用有界缓冲区的生产者/消费者模型对缓冲池中的缓冲区进行循环使用
例子：终端输入软件中的键盘驱动程序其任务之一：收集字符
- 常见两种字符缓冲方法：
  - 公共缓冲池（驱动程序中）
  - 终端数据结构缓冲（终端绑定缓冲区）
- UNIX System V
  - 采用缓冲池技术，可平滑和加快信息在内存和磁盘之间的传输
  - 缓冲区结合提前读和延迟写技术对具有重复性及阵发性 I/O 进程、提高 I/O 速度很有帮助
  - 可以充分利用之前从磁盘读入、虽已传入用户区但仍在缓冲区的数据（尽可能减少磁盘 I/O 的次数，提高系统运行的速度）
  - 缓冲池： 200个缓冲区（512字节或1024字节）
  - 每个缓冲区由两部分组成：缓冲控制块或缓冲首部 + 缓冲数据区
  - 空闲缓冲区队列（av链）：队列头部为 bfreelist
  - 设备缓冲队列（b链）：链接所有分配给各类设备使用的缓冲区，按照散列方式组织。
    - 双向链，假设有64个队列，每个队列首部有头标
    - 根据块号计算队列号
  - 缓冲首部
    - 设备号和块号：标志文件系统和数据所在的盘块号，是缓冲区的唯一标志
    - 状态项：指明该缓冲区当前的状态：忙/闲、上锁/开锁、是否延迟写、数据有效性等
    - 两组指针 av + b
  - 每个缓冲区同时在 av链和 b 链
    - 开始：在空闲 av 链（缓冲区未被使用）
    - 开始 I/O 请求：在设备I/O请求队列和设备b链
    - I/O 完成：在空闲 av 链和设备 b 链
  - 进程想从盘块读数据时，系统在 b 链中查找，如果找到对应缓冲区，则把该缓冲区标记为“忙”，并从空闲 av 队列中取下，然后完成从缓冲区到内存用户区的数据传送
  - 如果设备 b 链中未找到时，则从空闲 av 链队首摘取一个缓冲区，插入设备 I/O 请求队列；并从源设备 b 链中取下，插入由读入信息盘块号确定的新的设备 b 链中
  - 当数据从磁盘块读入到缓冲区后，缓冲区从设备 I/O 请求队列取下；当系统完成从缓冲区到内存用户去的数据传送后，要把缓冲区释放，插入 av 链队尾
  - 当数据从磁盘块读入到缓冲区并传送到用户区后，缓冲区保留在 b 链中，使用完后插入 av 尾部，但数据仍然有效。如果需要再次使用，则从 av 链中摘下，如果没有，则缓冲区慢慢升到头部
设备管理有关的数据结构
- 描述设备、控制器等部件的表格
- 建立同类资源的队列：把物理属性相同的设备连成队列（也称设备队列）
- 面向进程 I/O 请求的动态数据结构：进程发出 I/O 请求时，系统建立一张表格（I/O请求包），填入参数，可以组成队列
- 建立 I/O 队列
独占设备的分配
- 显式分配
- 静态分配：运行前分配，结束后回收缺点：效率低
- 动态分配：可能产生死锁
分时式共享设别的分配
- 不同进程 I/O 请求排队

设备驱动程序

驱动程序的任务是接收来自与设备无关的上层软件的抽象请求，并执行这个请求
驱动程序的接口
- 与操作系统的接口
- 与系统引导的接口：初始化，包括分配数据结构，建立设备的请求队列
- 与设备的接口

典型的实现方案： I/O 进程

I/O 进程：专门处理系统中的 I/O 请求和 I/O 中断工作
I/O 请求的进入
- 用户程序：调用 send 将 I/O 请求发送给 I/O 进程；调用 block 将自己阻塞，直到 I/O 任务完成后被唤醒
- 系统：利用 wakeup 唤醒 I/O 进程，完成用户要求的操作
I/O 中断的进入
- 当 I/O 中断发生时，内核中的中断处理程序发一条消息给 I/O 进程，由 I/O 进程负责判断并处理中断
是一个系统进程，一般最高优先级，一旦唤醒很快运行
I/O 进程开始运行后，先关中断，用 reveive 接收
有消息（没有就关中断阻塞自己）
- I/O 请求：准备通道程序（驱动），发出启动 I/O 指令，继续判断有无消息
- I/O 中断：
  - 正常结束：唤醒对应进程
  - 异常结束：异常处理

未来机械研究所

操作系统

第一讲

中央处理器(CPU)

第二讲

1. 中断机制

2.事件

3.中断/异常机制工作原理

4.中断响应

5.中断向量表

6.中断处理程序

IA32 中断实例

基本概念——x86

操作系统运行机制（系统调用）

系统调用 System call

系统调用机制设计与执行过程

系统调用举例

sysenter/sysexit 系统调用机制

系统调用作结

机制与策略分离原则

存储系统

I/O访问技术

第三讲

进程线程模型

多道程序设计

进程控制

线程模型

第四讲

处理器调度

windows 线程调度

LINUX 进程调度

linux2.4调度算法

CFS（Completely Fair Scheduling）

BFS

实时系统调度算法

多处理器调度

第五讲

并发环境

进程互斥的解决方案

生产者/消费者问题

典型的同步机制

信号量和 PV 操作

管程

PTHREADS：锁（解决互斥问题）/条件变量 （解决同步问题）

第一类读者写者问题

锁的实现

通信机制

第五讲

死锁

资源分配图（RAG）

死锁解决

不考虑此问题 —— 鸵鸟算法

阻止死锁发生

让死锁发生 —— 死锁检测与解除

哲学家就餐问题

为防止死锁发生可采取的措施

第八讲 基本内存管理

物理内存管理方案

空闲内存管理

伙伴系统 （Linux 底层内存管理采用）

基本内存管理方案（逻辑空间）

内存扩充

页式管理

第九讲 虚拟页式管理

虚拟页式存储管理

页表表项的设计

缺页异常处理

驻留集管理

工作集模型

清除策略

分页守护进程

页缓冲技术

加载控制

其他问题

内存映射文件

策略和机制分离

第十讲 Windows 虚存管理

x86

Windows 虚存管理

第十一讲 文件系统

PTHREADS：锁（解决互斥问题）/条件变量（解决同步问题）

第八讲基本内存管理

伙伴系统（Linux 底层内存管理采用）

第九讲虚拟页式管理

第十一讲文件系统

第十二讲文件系统的管理