操作系统
1. 介绍
1.1. 什么是操作系统
1.1.1. 控制程序
1.1.2. 资源分配器
1.1.3. 虚拟机
1.1.4. 一个可使用的计算系统1.2. 操作系统的组成
1.2.1. CPU 管理器
1.2.2. 内存管理器
By CFD 1
1.2.3. 文件系统
1.2.4. 设备管理器
1.3. 大型机和小型机的操作系统
1.3.1. 大型机和小型机有专用的操作系统
1.3.2. 大型机的发展历程：批处理系统 》 多道程序设计系统 》分时系统
1.3.3. 批处理系统
1.3.3.1. 同一时间能且只能运行一个应用
1.3.3.2. 批处理相似的任务
1.3.3.3. 第一个原始的操作系统
1.3.4. 多道程序设计系统
1.3.4.1. 同时把多个程序放入内存并允许它们交替执行和共享
系统中的各类资源。即当一道程序因某种原因（如I/O请求）而暂停执行时，CPU立即转去执行另一道程序。
1.3.4.2.
1.3.5. 分时系统
1.3.5.1. CPU在多个保存在内存中的任务之间切换（CPU仅分配给保存在内存中的任务）
By CFD 2
1.3.5.2. 为了需要快速响应的交互式计算而设计
1.3.5.3. 造成”并发”假象，实质：快速切换
1.4. 桌面计算机的操作系统
1.4.1. Apple: Macintosh
1.4.2. Microsoft: MS-DOS, Windows 9x/NT
1.4.3. IBM: OS/2
1.4.4. Unix
1.4.4.1. BSD:(Berkeley Software Distribution) Unix, 包括FreeBSD，OpenBSD，NetBSD
1.4.4.2. Sun microsystem的Solaris
1.4.4.3. Apple：macOS
1.4.5. Linux
1.5. 嵌入式系统的操作系统
1.5.1. 通常用于控制设备的专用程序中，比如说工厂控制系统（资源受到限制）
1.5.2. 一些控制设备有时间需求
1.5.2.1. 比如说：即时性
1.5.2.1.1. 硬即时
1.5.2.1.2. 软即时
2. 计算机系统结构
2.1. Bootstrap引导
2.1.1. 把操作系统的内核从持久存储中加载出来
2.1.2. 然后把控制在非常基本的环境下转移到操作系统的入口
By CFD 3
2.1.3. 引导操作系统的过程
2.1.4. 进行引导的程序叫做引导器，每个操作系统都需要有引导器boot-loader
2.2. 中断
2.2.1. 现代计算器和操作系统都是中断驱动
2.2.1.1. 外围设备使用中断向CPU发送信号提示某些事要发生
2.2.2. 当CPU发生中断时，必须响应中断，过程如下
2.2.2.1. 1.硬件：存储相关寄存器信息并跳转到中断服务例程interrupt service routine（ISR）
2.2.2.2. 2.ISR中的汇编语言程序：存储剩下的必要的寄存器信息并建立一个方便的环境
2.2.2.3. 3.ISR中的C语言程序：实际响应/服务中断，通常是读取并缓存从外围设备输入的数据
2.2.2.4. 4.ISR中的C语言程序：返回到ISR中的汇编语言程序
2.2.2.5. 5.ISR中的汇编语言程序：软件负责恢复寄存器数据并返回到发生中断的位置
2.2.3. 中断向量
2.2.3.1. CPU用一个独特的号码标记每一个外部设备，称为中断请求号码interrupt request number(IRQ)
2.2.3.2. 所有ISR都被收集到一个表格之中，称为中断向量表interrupt vector table(IVT)
2.2.3.3. 当发生中断的时候，CPU使用IRQ去IVT中索引中断向量获得ISR的地址，并跳转到对应的ISR
2.2.3.4. 中断处理流程
2.2.3.4.1.
By CFD 4
2.2.3.4.1.1.
2.2.4. 中断对比异常
2.2.4.1. 中断
2.2.4.1.1. 外围设备触发
2.2.4.1.2. 异步
2.2.4.2. 异常
2.2.4.2.1. 异常由CPU在执行程序过程中检测出来的，例如：除0错误和无效内存访问异常
2.2.4.2.2. 除此之外，异常与中断一样完全一样，而且异常也有异常号码
2.2.4.2.3. 异常又被称为software-generated interrupt软中断或者synchronous interrupt同步中断
2.3. CPU访问外围设备
By CFD 5
2.3.1. CPU通过设备控制器来访问外围设备，设备控制器包含命令寄存器和数据寄存器
2.3.2. 两种方式访问外围设备
2.3.2.1. I/O端口 I/O port
2.3.2.1.1. 所有的寄存器包括设备控制器都有一个特别的地址进行标识，称为端口port
2.3.2.1.2. I/O指令用来允许数据在寄存器和内存之间传递
2.3.2.1.3. I/O端口是独立的地址空间，不消耗内存空间
2.3.2.2. 内存映射I/O Mempry-mapped I/O
2.3.2.2.1. 用独特的内存地址来标识每一个寄存器，而不是用端口地址
2.3.2.2.2. 内存映射I/O使用相同的总线来访问内存地址和I/ O设备的地址
2.3.2.2.3. 为了容纳I/O设备，CPU必须为I/O设备保留可用地址空间
2.3.2.2.4.
2.3.2.2.5. 优缺点
2.3.2.2.5.1. 优点
By CFD 6
每一条指令都可以查询内存，也可以查询设备控制器
寄存器
不需要用特别的保护机制来防止用户进程执行I/O
2.3.2.2.5.2. 缺点
现在大部分计算机都有一些缓存内存字的形式，但是缓存设备控制器寄存器将会造成灾难性后果，比如缓存即时指令导致延时
解决方法：CPU可以执行特定内存是否缓存
2.3.2.3. 现代计算机系统一般使用两种方法访问外围设备
2.3.2.3.1. 使用内存映射I/O访问数据缓存
2.3.2.3.2. 使用I/O端口访问指令寄存器
2.4. 硬件保护方式
2.4.1. 双模式操作
2.4.1.1. 至少需要两种独立的操作模式
2.4.1.1.1. 用户态
2.4.1.1.2. 内核态（管理者supervisor、系统、特权或者内核模式）
2.4.1.2. 模式位：添加在计算机硬件中用来标识当前模式，内核态0，用户态1
2.4.1.2.1. 初始都是设置为内核态，当操作系统被加载并启动用户程序后进入用户态
2.4.1.2.2.
By CFD 7
2.4.1.2.2.1. INTEL IA-32系统：I/O特权级别（IOPL）
2.4.1.3. 当中断或异常发生时，硬件进入内核态
2.4.1.3.1. 此时，操作系统获得计算机控制权，属于内核态
2.4.1.3.2. 当系统把控制权交给用户程序时再次进入用户态
2.4.1.4. 保护环
2.4.1.4.1.
2.4.1.4.1.1. INTEL IA-32系统：0环为内核态，3环为用户态，仅使用2个环
2.4.2. 特权指令
2.4.2.1. 所有的I/O指令都是特权指令
2.4.2.1.1. 硬件允许特权指令仅仅在内核态中执行
By CFD 8
2.4.2.1.2. 当在用户态下想要执行特权指令时，硬件不会执行，而是把它当做非法指令并产生异常
2.4.2.2. 必须确保所有的用户程序在内核态下不会获得计算机的控制权
2.4.3. 内存保护
2.4.3.1. 添加两个寄存器来决定寻址程序合法访问的范围
2.4.3.1.1. 基址寄存器Base register：存储最小的合法物理内存地址
2.4.3.1.2. 限制寄存器Limit register：存储范围的大小
2.4.3.2.
2.4.4. CPU保护
2.4.4.1. 操作系统仅仅在可以运行时起作用，如果故障程序进入无限循环并且不返还控制权给操作系统，那么操作系统将
失去对CPU的控制权
2.4.4.2. 计时器
2.4.4.2.1. 机制：间隔一定时间中断CPU来确保操作系统维持对CPU的控制权
2.4.4.2.1.1. 理由是当中断发生时，操作系统将通过ISR获得控制权
2.4.4.2.2. 原理：计数器寄存器在石英振荡器定时发送脉冲时自动减一，当计数寄存器达到0的时候，定时器将会中断CPU，然后计数寄存器会用保存寄存器的值重新加载并重
复之前的工作。保存寄存器（Holding register）来加载计
By CFD 9
数器。
2.4.4.2.3. 作用
2.4.4.2.3.1. 维持时钟
2.4.4.2.3.2. 分时系统的关键设备
2.4.4.2.3.3. 保护CPU，维持操作系统对CPU的控制权
2.5. System call系统调用
2.5.1. 操作系统本身没有任何用处，但是给用户程序提供了很多有用的服务，这些服务通过系统调用来提供，即系统调用是操
作系统同用户程序之间的接口
2.5.2. 特点
2.5.2.1. 用户程序只能通过系统调用来请求操作系统提供的服务
2.5.2.2. 接口中的系统调用因操作系统的不同而不同
2.5.2.3. 系统调用又称为监督器调用supervisor call
2.5.3. 调用过程
2.5.3.1. 1-3准备参数
2.5.3.2. 4 调用系统调用的包装wrapper（用汇编语言编写）
2.5.3.2.1. 将汇编语言”转换”成C语言，以便C文件调用：即变成C语言接口
2.5.3.2.2. 将服务名称转为数字
2.5.3.3. 5 把系统调用号码存到寄存器
2.5.3.4. 6 进入（trap into）操作系统
2.5.3.5. 7 通过系统调用号码在系统调用表中索引，获得系统调用服务例程
By CFD 10
2.5.3.6. 8-11 运行系统调用例程，完成以后然后返回用户程序
2.5.3.7.
2.5.3.7.1.
2.5.4. 进入操作系统
2.5.4.1. 用户程序不能直接进入操作系统，进入操作系统的方法有两种
2.5.4.1.1. 异常（软件生成中断）
2.5.4.1.2. 特殊指令（触发异常）
2.5.4.1.3. 实质均为触发异常
2.5.4.2. INTEL IA-32
By CFD 11
2.5.4.2.1. 提供了一条指令触发异常，INT
2.5.4.2.2. 由于INT指令的额外开销，提供了特殊指令，SYSENTER和SYSEXIT
2.5.4.2.2.1. ARM处理器使用swi（Software Interrupt，软件中断）进入操作系统
2.5.5. 系统调用对比库函数
2.5.5.1. 系统调用会进入操作系统内核，但是库函数不会。这也导致系统调用比库函数慢很多
2.5.5.2. 库函数等同于用户自定义的函数，我们可以用我们自己的库函数版本代替已有库函数，但是我们不能代替系统调
用
2.5.5.3. 一个操作系统中的系统调用可能成为另一个操作系统的中的库函数
2.5.5.3.1. 将系统调用封装成库函数，以便程序从一个系统移植到另一个系统
2.5.5.3.2.
3. 操作系统结构
3.1. 操作系统结构
3.1.1. 简单结构或者无结构
By CFD 12
3.1.1.1. 举例
3.1.1.1.1. MS-DOS
3.1.1.1.2. Unix
3.1.1.2.
3.1.2. 分层结构
3.1.2.1. 操作系统被分为多层，每一层建立在较低层的上面
3.1.2.2.
3.1.2.3. 举例：THE操作系统，Dijkstra创建
3.1.2.3.1.
3.1.2.4. 主要困难
By CFD 13
3.1.2.4.1. 分层界限模糊
3.1.2.4.2. 低效率
3.1.3. 微内核结构
3.1.3.1. 微内核方法通过从内核中删除所有非必要的组件并且把它们作为系统级和用户级的程序实现
3.1.3.2. 应该留在微内核中的结构
3.1.3.2.1. CPU管理器
3.1.3.2.2. 内存管理器
3.1.3.2.3. 通信设施
3.1.3.3.
3.1.3.4. 举例
3.1.3.4.1. Mach
3.1.3.4.1.1. 用于Apple macOS/iOS/tvOS/watchOS
3.1.3.4.2. Micorsoft Windows NT/XP
3.1.3.5. PS：纯微内核不可行
3.1.4. 虚拟机
3.1.4.1. 底层真实硬件被”克隆”成几个相同的虚拟机，该虚拟机提供与底层裸机硬件相同的接口
3.1.4.2. 操作系统就建立在虚拟机的上面
3.1.4.2.1.
By CFD 14
3.1.4.3. 虚拟机分类
3.1.4.3.1. 硬件虚拟机（依据实现方法分类）
3.1.4.3.1.1. 仿真/模拟：虚拟机模拟完整的硬件，允许一个完全不同的未修改的操作系统 CPU运行
VMware VirtualBox QEMU Bochs
3.1.4.3.1.2. 克隆-半虚拟化：虚拟机不模拟硬件，而是提供了一个特殊的API，需要操作系统修改运行
剑桥大学的Xen
3.1.4.3.1.3. 克隆-完全虚拟化：虚拟机的一部分模拟足够的硬件以允许未修改的操作系统独立运行，但是客户操
作系统必须为之设计同一类型的CPU
IBM的VM/370
适用于Linux的KVM
3.1.4.3.2. 应用程序虚拟机
3.1.4.3.2.1. 一种将用户正在使用的应用程序与计算机隔离的计算机软件
By CFD 15
3.1.4.3.2.2. 举例：Sun微系统的Java虚拟机(JVM)
3.1.4.4. 虚拟机优缺点
3.1.4.4.1. 虚拟机概念完成了对系统资源的保护，因为每个虚拟机设备都与其他虚拟机隔离开，即不允许直接共享资
源
3.1.4.4.2. 虚拟机是操作系统研究和发展的完美工具
3.1.4.4.3. 虚拟机概念很难实现，理由是需要向底层计算机提供精确副本
3.2. 操作系统设计
3.2.1. 策略Policies和机制Mechanisms
3.2.1.1. 策略-做什么
3.2.1.1.1. 比如用户不应该能够读取其他用户的文件
3.2.1.2. 机制-怎么做
3.2.1.2.1. 比如说文件访问权限应该由开放的系统调用来判断
3.2.2. 操作系统的实现
3.2.2.1. 传统的操作系统由汇编语言编写，现在可以由高级语言编写
3.2.2.2. 高级语言编写的优点
3.2.2.2.1. 编写速度更快
3.2.2.2.2. 更简洁
3.2.2.2.3. 容易理解和Debug
3.2.2.2.4. 方便移植到其他硬件上
4. 进程管理
By CFD 16
4.1. 进程概念
4.1.1. 运行工作/程序/任务的抽象
4.1.2. 组成
4.1.2.1. 文本部分（代码）
4.1.2.2. 数据部分（数据）
4.1.2.3. 寄存器内的内容
4.1.2.4. 栈
4.1.2.5. 堆
4.1.2.6. 其他资源，如打开的文件
4.1.2.7.
4.1.2.7.1. Gap满时显示内存不足
4.2. 进程对比程序
4.2.1. 程序是属于存储的被动实体，进程是包含比程序更多资源的主动实体
4.2.2. 很多进程可能是运行相同的程序，但是进程应该是分开的运行队列，除了分享相同代码段，其他资源都不相同
4.3. 进程状态
By CFD 17
4.3.1. 创建状态
4.3.2. 运行状态
4.3.3. 等待状态：等待某些事件发生
4.3.4. 就绪状态：等待CPU调度
4.3.5. 终止状态
4.3.6. Zombie僵尸状态：执行完毕但资源未回收
4.4. 进程状态转换
4.4.1.
4.5. 进程控制块Process Control Block(PCB)，也叫任务控制块
4.5.1. 进程号码-PID
4.5.2. 程序计数器-PC
4.5.3. 调度信息，包括进程优先级
4.5.4.
By CFD 18
4.6. 进程调度-决定下一个运行的进程
4.6.1. 当前运行进程发生了什么？
4.6.1.1. 上下文切换
4.6.1.1.1.
4.6.1.1.2. 上下文切换是纯消耗
4.6.1.1.2.1. 取决于下层的处理器，消耗许多CPU周期
4.6.1.1.2.2. 上下文切换已经变成了运行瓶颈，需要使用新的结构（缓存）来尽可能的避免
4.6.2. 如何跟踪每一个进程应该做的事？
4.6.2.1. 调度队列
4.6.2.1.1. 工作队列：全部进程
By CFD 19
4.6.2.1.2. 就绪队列：等待被调度执行的进程
4.6.2.2. I/O设备队列
4.6.2.2.1.
4.6.2.3. 队列图：进程调度的一种常用表示
4.6.2.3.1.
4.6.3. 如何决定下一个运行的进程？
4.6.3.1. CPU调度器：从ready队列中选择一个进程，将CPU分配给这个进程
4.7. 进程的操作
4.7.1. 进程终止
4.7.1.1. 正常情况
By CFD 20
4.7.1.1.1. 一个进程被操作系统删除
4.7.1.2. 非正常情况
4.7.1.2.1. 一个进程被另一个进程删除，仅内存资源回收
4.7.2. 进程协作
4.7.2.1. 协作进程之间的同步
4.7.2.2. 进程协作的优点
4.7.2.2.1. 信息共享
4.7.2.2.1.1. 几个进程共享相同的信息
4.7.2.2.2. 计算加速
4.7.2.2.2.1. 将问题分成几个可以并行的子任务
4.7.2.2.3. 模块化
4.7.2.2.3.1. 根据设计将不同功能的过程分开
4.7.2.3. 并行执行的进程需要允许进程通信的机制来同步行为
4.7.2.4. 举例：生产者、消费者问题
4.7.2.4.1. 一般选择有界限的缓冲区
4.7.2.4.2.
4.7.3. 进程间通讯Interprocess communication(IPC)
By CFD 21
4.7.3.1. 距离远：先解决通信在解决同步问题
4.7.3.2. 距离近：同步为主要问题
4.7.3.3. 管道Pipe
4.7.3.3.1. 管道有两个端点:一个用于读取，另一个用于写入。先进先出FIFO原则
4.7.3.3.2. 种类
4.7.3.3.2.1. 匿名管道
单工，数据只在一个方向上传输
在父子进程间传递数据
仅存在于进程运行时
4.7.3.3.2.2. 命名管道
单工或者双工，允许数据同时在两个方向上传输，全
双工通信是两个单工通信方式的结合
允许任意两个进程之间的通信
可以是永久保存或者易丢失的
5. 线程管理
5.1. 线程与进程
5.1.1. 进程
5.1.1.1. 资源分配的单元 调度的单元
5.1.2. 线程
5.1.2.1. 传统的进程只控制一个线程
5.1.2.2. 进程是所调用资源的容器
By CFD 22
5.1.2.3. 线程是CPU实际调度的实体
5.2. 线程概念
5.2.1. CPU调度的基础单元，又称为轻量级进程lightweight process
5.2.2. 多线程
5.2.2.1. 在相同进程中存在允许多个线程
5.2.2.2. 共享进程中的资源，包括代码段、数据段、打开的文件等
5.2.2.3. 每个线程拥有私有线程内容，包括CPU寄存器设置、其他状态信息和私有栈
5.2.2.3.1.
5.2.3. 单线程对比多线程
5.2.3.1.
5.3. 线程的好处
5.3.1. 可响应性
By CFD 23
5.3.2. 资源共享
5.3.3. 经济
5.3.4. 提高多处理器结构的利用率5.4. （多）线程的实现
5.4.1. 用户线程
5.4.2. 内核线程
5.4.2.1. 直接由操作系统支持，内核在内核态下执行线程的创建、调度和管理
5.4.2.2. 缺点
5.4.2.2.1. 线程管理和上下文切换需要进入内核，由内核调度，消耗大量CPU周期
5.4.2.3. 优点
5.4.2.3.1. 如果进程中一个线程被阻塞，内核可以调度同一个进程中的另一个线程
5.4.2.3.2. 当有多个处理机时，一个进程的多个线程可以同时执行
6. CPU调度
6.1. 基本概念
6.1.1. 调度是操作系统的基本功能
6.1.1.1. 空间资源的调度-内存
6.1.1.2. 时间资源的调度-CPU
6.1.2. 当前进程（线程）不能执行时，操作系统必须调度另一个就绪的进程（线程）执行
6.2. CPU-I/O 爆发周期
By CFD 24
6.2.1. 进程执行由CPU执行和I/O等待的周期组成
6.2.2. 进程在这两个状态中轮流切换
6.2.3.
6.3. CPU调度器
6.3.1. 概念
6.3.1.1. 从内存中的挑选已经准备的进程去执行，并把CPU分配到其中一个进程。也称为短期调度器
6.3.2. CPU调度决策发生在当进程发生如下情况时
6.3.2.1. 进程终止
6.3.2.2. 从运行状态变成等待状态
6.3.2.3. 非抢占式的
6.3.2.4. 从运行状态变成就绪状态
6.3.2.5. 从等待状态变成就绪状态
6.3.2.6. 抢占式的
6.4. 调度算法
6.4.1. 先到先服务First-come, first-served(FCFS)
By CFD 25
6.4.1.1.
6.4.2. 耗时最小的工作先执行Shortest-job-First(SJF) --调度最优解，可以获得最小的平均等待时间
6.4.2.1. 非抢占式 -等待时间是从到达之后开始计算
6.4.2.1.1.
6.4.2.2. 抢占式Shortest-Remaining-job-First(SRJF)
6.4.2.2.1.
By CFD 26
6.4.3. 优先级调度Priority scheduling
6.4.3.1. 每个进程被分配了一个静态优先级，CPU每次运行优先级最高的进程
6.4.3.2. 可以是抢占式的，也可以是非抢占式的
6.4.3.3. 问题
6.4.3.3.1. 饿死：低优先级的进程可能永远也不会执行
6.4.3.3.2. 优先级反转：高优先级的进程需要访问低优先级进程所持有的资源
6.4.3.4. 解决办法-老化Aging
6.4.3.4.1. 随着时间推移，进程的优先级会逐渐增加，即采用动态优先级
6.4.4. 轮转调度Round-Robin scheduling(RR)-分时
6.4.4.1. 每个进程得到一个小的CPU时间单位(时间量或时间片)，通常是10-100毫秒。这段时间过后，进程被抢占并添加到就绪队列的末尾
6.4.4.2. 如果就绪队列中有n个进程，时间量为q，然后每个进程一次最多获得CPU总时间的1/n，即q个时间单位，那么任
何进程等待的时间单位都不超过(n-1)q
6.4.4.3. 性能问题
By CFD 27
6.4.4.3.1. q太大时就相当于是FCFS
6.4.4.3.2. q太小时上下文切换开销太高
6.4.5. 多级队列Multilevel queue
6.4.5.1. 就绪队列进一步被分为多个单独的队列，每个队列都有一个优先级数字，且每个队列有它自己的调度算法
6.4.5.1.1.
6.4.5.2. 一个进程可以在不同队列中移动，比如说当一个进程执行了分配给它的时间片以后，它就会下沉到较低优先级队
列
6.4.6. 总结
6.4.6.1. 在实践中做到正确要比在原则上做到正确难得多。结果是调度器很少会做出最佳选择。解决方案：调度策略与调
度机制分离。 也就是说，调度算法以某种方式参数化，但是参数可以由用户根据需要进行填充
7. 进程同步
7.1. 背景
7.1.1. 协作进程通过由内核提供的IPC设备可能共享同一块内存，同一进程内的多线程可能共享全局变量所使用的内存
7.1.2. 并发地访问共享数据，可能会造成前后矛盾，为了维持数据一致性，需要某种机制确保协作进程的有序执行
7.1.3. 当生产者与消费者并发执行时，可能会出现错误，由于汇编语句的交叉
By CFD 28
7.1.3.1.
7.2. 竞争条件Race condition
7.2.1. 竞争条件是指多个进程同时访问和操作相同的数据，执行的结果取决于访问发生的特定顺序
7.2.2. 避免方式
7.2.2.1. 找到某种方法来禁止多个进程同时读写共享数据。也就是说，即使进程尝试并发访问，访问也必须串行化
7.2.3. 临界区Critical section(C.S.)
7.2.3.1. 一段访问共享资源的代码
7.2.4. 竞争条件的解决办法必须满足以下四个条件
7.2.4.1. 互斥：不能存在两个进程同时进入临界区
7.2.4.2. 可运行：某个进程不执行时不能阻止其他线程进入临界区
7.2.4.3. 必须实现的条件
7.2.4.4. 有限等待：进程进入临界区不能永久等待
7.2.4.5. 速度：不受CPU速度和数量影响
7.2.5. 设计一个协议让进程用来进入和离开临界区
7.2.5.1.
By CFD 29
7.3. 解决竞争条件
7.3.1. 第一次尝试
7.3.1.1.
7.3.1.2. 不满足可执行性progress要求，只能严格交替P0 P1 P0 P1...
7.3.2. 第二次尝试
7.3.2.1.
7.3.2.2. 不满足可执行性progress要求，存在flag[0], flag[1]同时被设置为true情况
By CFD 30
7.3.3. 第三次尝试-Peterson算法
7.3.3.1.
7.3.4. 同步化的硬件,几个低级别硬件功能可以解决竞争条件
7.3.4.1. 禁用中断
7.3.4.1.1. 进程切换只发生在时钟中断或者其他中断，如果禁用中断，就不必担心产生竞争条件
7.3.4.1.2. 例子：INTEL x86
7.3.4.1.2.1. CLI - 关中断
7.3.4.1.2.2. STI - 开中断
7.3.4.1.3. 缺点
7.3.4.1.3.1. 用户进程不应该可以禁用中断，CLI/STI都是特权指令
7.3.4.1.3.2. 开关中断在多道程序设计系统中是不可行的
7.3.4.1.3.3. 会丢失一些重要中断，如时钟中断
7.3.4.2. 特殊指令，都是原子执行语句，不可中断
7.3.4.2.1. TSL(Test and Set Lock)返回原值并设置为真
7.3.4.2.1.1.
By CFD 31
7.3.4.2.2. SWAP
7.3.4.2.2.1.
7.3.4.3. 使用特殊指令解决竞争条件
7.3.4.3.1.
7.3.4.3.1.1. 满足互斥与可执行性progress，不满足有限等待
7.3.5. 总结
7.3.5.1. 以上的解决办法都有一个普遍的缺点：忙等
7.3.5.1.1. 当一个进程进入临界区之后，其他进程必须在入口代码处不断循环
By CFD 32
7.3.5.1.2. 忙等浪费CPU周期
7.3.5.2. 解决办法：自旋锁spinlock
7.3.5.2.1. 概念：可以被其他CPU内核调用线程
7.3.5.2.2. 只在多处理器中有效，因为对于短时间内要执行的线程，多处理器下无上下文切换
7.3.5.2.3. 单CPU下不可避免上下文切换，需要用开关中断手段解决竞争条件
7.4. 信号量Semaphore
7.4.1. 信号量介绍
7.4.1.1. 上述解决竞争条件的方法都不容易推广，信号量可以一个同步工具克服这个问题
7.4.1.2. 信号量由Dijkstra发明，第一次使用在THE操作系统中
7.4.1.3. 信号量是一个整型变量，除了初始化，只能通过原子操作P(down)和V(up)改变
7.4.2. 信号量实现
7.4.2.1.
7.4.2.2. 每个信号量均有一个进程队列
7.4.2.3. P操作阻塞一个进程，V操作唤醒一个进程
By CFD 33
7.4.2.4. 注意：P操作下S-\value value
7.4.2.5. value的值代表当前可用资源数量或者某个信号量后等待进程的数量
7.4.2.6. 利用底层方法保证P和V操作的原子性
7.4.2.6.1. 单处理器系统禁止中断
7.4.2.6.2. 多处理器系统采用自旋锁
7.4.2.7. 应用程序编程接口
7.4.2.7.1. Win32
7.4.2.7.1.1. CreateSemaphore/CloseHandle
7.4.2.7.1.2. WaitForSingleObeject/ReleaseSemaphore
7.4.2.7.2. POSIX
7.4.2.7.2.1. sem_init/sem_destroy
7.4.2.7.2.2. sem_wait/sem_post
7.4.3. 著名同步问题
7.4.3.1. 生产者-消费者问题
7.4.3.1.1.
By CFD 34
7.4.3.2. 读-写问题
7.4.3.2.1.
7.4.3.3. PS：mutex互斥信号量的个数（单个变量还是数组）由缓冲区个数决定，保证同一时刻仅有一个进程访问一个缓
冲区
7.4.4. 二元信号量
7.4.4.1. 前面描述的信号量结构通常称为计数信号量，因为它的值可以在不受限制的域内变化。二进制信号量是一个整数
值范围仅在0和1之间的信号量，它比某些硬件架构上的计数信号量更易于实现。计数信号量可以使用二进制信号量实现
7.4.4.2. 二元信号量实现
7.4.4.2.1.
7.4.4.2.2. bP和bV操作必须为原子操作
7.4.4.3. 使用二元信号量实现计数信号量
By CFD 35
7.4.4.3.1.
7.5. 管程Monitor
7.5.1. 高级语言同步结构，将程序、变量和数据结构组合成包
7.5.2. 管程有一个重要的特性，这使得它们对于实现互斥非常有用：在监视器中，任何时刻都只能有一个进程处于活动状态
7.5.3. 条件变量：定义为一种变量类型，它只有两个操作
7.5.3.1. C.wait()
7.5.3.1.1. 表示调用它的进程将挂起，直到另一个进程调用
7.5.3.2. C.signal()
7.5.3.3. 如果没有进程挂起，则signal()操作没有效果
7.5.4.
7.5.5. 可能出现一种情况，P进程调用C.signal()唤醒了进程Q，有三种可能的解决办法
By CFD 36
7.5.5.1. 挂起P，让Q运行
7.5.5.2. 布林奇·汉森式：P必须立即离开管程
7.5.5.3. Mesa风格（Mesa是一种编程语言）：让P运行并挂起Q
7.5.6. 语言支持
7.5.6.1. 管程构造必须由编程语言支持才能使用，也就是说，编译器必须识别监视器构造并生成代码以支持其功能
7.5.6.2. Java（只有一个条件变量的Mesa样式管程），通过向方法声明中添加synchronized关键字，Java保证一旦任何线程已经开始执行该方法，不允许其他线程开始执行该类中
的任何其他同步方法，Java提供了两个操作：wait和notify以阻止和唤醒线程
7.6. 管程与信号量
7.6.1. 信号量和监视器在功能上是等价的，但是它们的使用和实现是完全不同的
7.6.2. 使用管程实现信号量
7.6.2.1.
7.7. 总结
By CFD 37
7.7.1.
8. 死锁
8.1. 死锁问题
8.1.1. 如果进程集合中的每个进程都在等待或只有集合中的另一个进程可以发生的事件，则一组进程将被死锁
8.1.2. 产生原因
8.1.2.1. 计算机行为
8.1.2.1.1. 比如两个磁盘机相互等待
8.1.2.2. 人为造成的程序错误
8.1.2.2.1.
8.2. 系统模型
8.2.1. 一个系统由有限数量的资源组成，这些资源被分配到多个相互竞争的进程中
8.2.2. 使用资源的步骤
8.2.2.1. 请求
By CFD 38
8.2.2.1.1. 如果无法立即授予请求，则请求进程必须等待，直到它能够获取资源
8.2.2.2. 使用
8.2.2.3. 释放
8.2.3. 死锁特征：如果以下四个条件同时保持，则可能会出现死锁
8.2.3.1. 互斥mutual exclusion
8.2.3.1.1. 一次只能使用一个进程
8.2.3.2. 持有和等待hold and wait
8.2.3.2.1. 至少持有一个资源的进程在等待其他进程的资源
8.2.3.3. 无抢占no preemption
8.2.3.3.1. 资源只能由持有它的进程在该进程完成其任务后自动释放
8.2.3.4. 循环等待circular wait
8.2.4. 资源分配图
8.2.4.1.
8.2.4.2.
By CFD 39
8.2.5. 死锁和资源分配图
8.2.5.1. 如果资源分配图里面没有环，就没有进程死锁；如果资源分配图里面有环，则可能存在死锁
8.2.5.2.
8.3. 解决死锁的方法
8.3.1. 死锁预防-攻击四个条件
8.3.1.1. 攻击互斥
8.3.1.1.1. 对于可共享资源（如只读文件）来说，它不是必需的；对于不可共享资源（如打印机），它必须保持
8.3.1.1.2. 如果设备（如打印机）可以排队执行，只有打印机服务器使用打印机资源（其他进程将文档发送到要打印
的打印机服务器），打印机死锁将被清除
8.3.1.1.3. 但是，并不是所有的设备都可以排队执行，一般
By CFD 40
来说，我们不能通过攻击互斥来防止死锁一些本质上是不
可共享的资源
8.3.1.2. 攻击持有和等待
8.3.1.2.1. 我们必须保证，每当进程请求资源时，它不保存任何其他资源
8.3.1.2.2. 因此要求进程在开始执行之前请求并分配其所有资源，或者仅当进程没有资源时才允许进程请求资源
8.3.1.2.3. 可能导致资源利用率低和饿死
8.3.1.3. 攻击非抢占式
8.3.1.3.1. 如果持有某些资源的进程请求另一个不能立即分配给它的资源，那么当前持有的所有资源都将被释放
8.3.1.3.2. 这可以应用于那些状态可以轻松保存和存储的资源，例如CPU，通常不能应用于打印机和磁带机等资源
8.3.1.4. 攻击循环等待
8.3.1.4.1. 我们可以强制所有资源类型的总排序，并要求每个进程以递增的枚举顺序请求资源
8.3.2. 死锁避免
8.3.2.1. 要求系统提供一些额外的先验信息
8.3.2.2. 最简单和最有用的模型要求每个进程声明它可能需要的每种类型的最大资源数
8.3.2.3. 死锁避免算法动态检查资源分配状态，以确保永远不会有循环等待条件
8.3.2.4. 资源分配状态由可用和分配的资源数以及进程的最大需求定义
8.3.3. 安全状态
By CFD 41
8.3.3.1. 如果存在所有进程的安全序列，则系统处于安全状态
8.3.3.2. 基本事实
8.3.3.2.1. 如果系统处于安全状态，没有死锁
8.3.3.2.2. 如果系统处于不安全状态，避免死锁必须确保系统永远不会进入非安全状态
8.3.4. 银行家算法
8.3.4.1. 概念
8.3.4.1.1. 它是1968年由Dijkstra发明的，用于THE操作系统
8.3.4.1.2. 要求一个新进程必须声明它可能需要的每个资源类型的最大项数。此算法需要m x n个操作的顺序才能进行
安全检测
8.3.4.2. 数据结构
8.3.4.2.1.
8.3.4.2.2.
8.3.4.3. 安全检测，Finish[i] = true代表结束进程
8.3.4.3.1.
By CFD 42
8.3.4.3.2. Work代表工作区可用资源数量，Work = Work + Allocation，代表把当前进程结束Finish[i] = true之后，需要把之前分配出去的资源回收
8.3.4.4. 资源请求
8.3.4.4.1.
8.3.4.4.2.
8.3.4.5. 举例
8.3.4.5.1.
By CFD 43
8.4. 死锁检测和恢复
8.4.1. 如果死锁预防和死锁避免算法无法起作用，那么死锁就可能发生。在这种情况下，操作系统必须提供一种算法来判断死
锁是否发生以及从死锁中恢复
8.4.2.
8.4.3. 举例
8.4.3.1.
By CFD 44
8.4.3.2.
8.4.4. 什么时候唤醒死锁检测算法
8.4.4.1. 取决于死锁多久发生一次
8.4.4.2. 取决于有多少进程在死锁发生时会被影响
8.4.5. 死锁恢复
8.4.5.1. 当死锁检测判定死锁发生时，有两种选择
8.4.5.1.1. 结束进程
8.4.5.1.1.1. 直接全部死锁内所有进程
8.4.5.1.1.2. 每次结束一个进程直到死锁解除
8.4.5.1.2. 抢占资源
8.4.6. 鸵鸟算法
8.4.6.1. 我们可以完全忽略这个问题，假装永远不会出现死锁。在大多数操作系统中，包括Windows, Unix/Linux。因为死锁很少发生，死锁预防、避免或死锁检测和恢复算法代价高昂。这是方便与正确之间的权衡
9. 内存管理
9.1. 内存管理介绍
9.1.1. 内存管理的任务
9.1.1.1. 提供一个虚拟的机器接口，让每一个进程都以为是自己在独占RAM
By CFD 45
9.2. 基本方法
9.2.1. 以MS-DOS为例
9.2.1.1. MS-DOS
9.2.1.1.1. 单用户、单任务
9.2.1.1.2. 只能访问1MB内存-INTEL 8086/80286只有20根地址线
9.2.1.1.3. 没有任何保护机制
9.2.1.2. 在MS-DOS中，MS-DOS自己要占用1/3左右，剩余部分留给系统唯一的进程使用。如果在某个MOS-DOS下的应用程序需要超过640K的内存才能运行，怎么办？
9.2.1.2.1. 覆盖Overlay：一种使进程大于分配给它的内存量的技术。 覆盖的思想是在内存中只保存在任何给定时间所需的指令和数据
9.2.1.2.2.
9.2.1.2.3. 覆盖Overlay的思想：无论进程在运行时占有多大的内存，在某一段时间内，它只会访问其中的一部分
9.2.1.3. 假设MS-DOS支持多任务，即系统中有多个进程。而且，进程必须在内存中才能运行，运行中的进程可能会申请额外的内存。假设系统目前有两个进程：P1和P2，而且系统已经没有内存可以用。此时，正在运行的P1又要申请更多的内存才能继续运行，怎么办？
By CFD 46
9.2.1.3.1. 交换Swap：一个进程可以暂时从内存中交换到缓冲存储区，然后进入内存继续执行
9.2.1.3.2.
9.2.1.3.3. Swap的限制
9.2.1.3.3.1. 要求计算机必须配备足够大的backing- store，backing-store一般是快速、大容量的硬盘
9.2.1.3.3.2. 上下文切换要花费大量的时间，主要用于磁盘数据传输，因此调度算法尤其重要，应尽量减少上下
文切换
9.2.1.3.3.3. 被swap-out的进程必须被重新swap-in到相同的内存地址才能继续运行
9.2.1.3.4. Swap思想：当系统内存不足是，可以向backing- store”借”一部分来使用
9.2.2. 多任务多系统的内存管理
9.2.2.1. 重定位问题relocation
9.2.2.1.1. 源程序变成进程的过程
9.2.2.1.1.1. 代码source code先被编译成目标文件object file
9.2.2.1.1.2. 链接器linkage editor连接成可执行文件executable
By CFD 47
链接过程
相同属性的东西（code或data）放置在一起写好调用函数的地址
9.2.2.1.1.3. 最后由操作系统加载可执行文件到内存形成进程
9.2.2.1.2. 重定位概念
9.2.2.1.2.1. 在多任务环境中，可执行文件可能会被加载到内存的任何位置运行
9.2.2.1.2.2. 链接器在生成可执行文件时必须确定程序中各个符号（如函数、全局变量）的地址，把程序中的符
号映射为地址的过程叫做地址绑定address binding
9.2.2.1.2.3. 事实上，由于链接器无法预知程序将被加载到哪个内存位置，因此无法完成绝对的地址绑定。因
此，链接器只能假定程序中第一条指令的地址是0，从而用相对于它的偏移量来进行相对的地址绑定。这样的程序只能被加载到0地址的内存运行，如果该程序被加载到其他非0的地址，必须对程序中所应用的地址进行修改才能运行，这个修改的过程就称为重定位。
9.2.2.1.3. 重定位步骤
9.2.2.1.3.1. 几个概念
逻辑地址logical address：程序中引用的地址，也就是CPU产生的地址
物理地址physical address：系统中内存单元所看到的地址
内存管理单元Memory Management Unit, MMU：专
门完成逻辑地址到物理地址转换的硬件单元，一般是
CPU的一部分
9.2.2.1.3.2.
By CFD 48
9.2.2.2. 内存保护问题protection
9.2.2.2.1. 操作系统如何保护自己和应用程序的内存不被其他进程访问或破坏？
9.2.2.2.1.1. 对应用程序访问的每一个逻辑内存地址进行检查，看是否超出了内存范围。为了获得最好的性能，
一般用MMU通过硬件来实现检查功能。
9.2.2.2.1.2.
9.2.2.2.1.3. 需要硬件的支持才能实施保护
9.2.2.3. 内存分配问题allocation
9.2.2.3.1. 在多任务环境中，操作系统需要为每个新创建的进程分配一定数量的内存才能运行，当进程退出后，操作
系统要回收它所占用的内存。操作系统如何有效地管理内存的分配和回收，以尽量满足进程的需求？也称为动态内存分配问题
9.2.2.3.1.1. 做法
By CFD 49
操作系统保留一个表，指示哪些内存部分可用，哪些
内存块占用
可用的内存块称为洞hole。最初，所有内存都可用于用户进程。当进程到达并需要内存时，操作系统搜索一个足够大的洞hole提供给进程。
当一个进程终止时，它将内存作为一个洞hole返回给操作系统，如果新的洞与其他的洞是相邻的，那么这些相邻的洞将合并成一个更大的洞
9.2.2.3.1.2. 算法
随着系统中进程的创建和退出，系统中可能会形成很
多小的hole，这些hole既不足以满足任何进程的需
求，也不能被合并以形成打的hole。这些hole被称为外部碎片。
用来进行内存分配和释放以减少外部碎片提高内存使
用率的常用算法
首次适应First fit最佳适应Best fit最坏适应Worst fit
9.2.2.3.1.3. 其他方法
把系统内存分成固定大小的内存块，操作系统以块为单位进行内存的分配和释放，最终分配的内存可能会比所需求要多，多出来的部分称为内部碎片
相对于外部碎片，内部碎片的情况不是很严重
9.2.2.3.1.4. 内存的分配和回收不仅出现在OS中，应用程序面临同样的问题
当进程被创建时，操作系统会采用某种算法分配一块足够大的内存给进程，由进程自己挂你（其中的一部分）
By CFD 50
由进程自己管理，库函数new/delete（或
）就是操纵heap中的内存
9.3. 分页内存管理
9.3.1. 介绍
9.3.1.1. 分页解决了以下问题
9.3.1.1.1. 进程所占用的物理内存不必连续
9.3.1.1.2. 没有外部碎片，但有一定量的内部碎片
9.3.1.1.3. 可以对进程所占用的部分内存进行swap-in/ swap-out
9.3.1.2. 早起，分页系统主要由硬件来实现，如今，分页由硬件和操作系统共同完成
9.3.1.3. 基本概念
9.3.1.3.1. 物理内存被分成固定大小的块，称为帧
9.3.1.3.2. 逻辑内存也被分成大小相同的块，称为页
9.3.1.3.3. 页表的条目称为页表条目Page Table Entry(PTE)，每一个映射关系对应一个PTE
9.3.2. 方法
9.3.2.1. 把逻辑地址分为两部分
9.3.2.1.1. 第一部分称为页码page number
9.3.2.1.2. 第二部分称为页偏移量page offset
By CFD 51
9.3.2.2. 地址转换
9.3.2.2.1. 在page table的帮助下，MMU把CPU产生的逻辑地址转换成物理地址
9.3.2.2.2.
9.3.2.2.2.1.
9.3.2.2.3. PS：page大小必须为2^n，提高转换性能
9.3.2.2.3.1.
By CFD 52
9.3.2.2.4. 共享代码的实现：利用page table指向相同的物理地址
9.3.2.3. 地址划分
9.3.2.3.1.
9.3.2.4. 结论
9.3.2.4.1. 分页的一个重要方面是内存的用户视图和实际的物理内存之间的清晰分离，它们之间的差异通过地址转换
硬件来协调，他的映射对用户是隐藏的，由操作系统控制
9.3.2.4.2. 由于是操作系统控制地址映射，它必须记录系统物理内存的使用情况。一般使用一个称为frame table的数
据结构来保存系统中每一个frame的状态，为每一个进程保存一个page table，也就是说，每一个进程都有自己的逻辑地址空间
By CFD 53
9.3.3. 实现
9.3.3.1. page table必须被保存在内存中，CPU中的两个寄存器记录了它的信息
9.3.3.1.1. Page-table base register(PTBR)保存了page table的地址
9.3.3.1.2. Page-table length rejister(PTLR)保存了page table的大小
9.3.3.2. 因此在分页中，每一个内存访问都需要两次内存操作，一次访问page table，一次访问内存数据
9.3.3.3. 为了提高地址转换效率，MMU中包含了一个高速缓存称为translation look-aside buffers(TLBs)
9.3.3.3.1. TLB结构
9.3.3.3.1.1.
9.3.3.3.2. 对于逻辑地址A的转换，如果A在TLB中，直接获取相应映射帧，否则访问内存里的page table
9.3.3.3.3. 增加了TLB的地址转换过程
9.3.3.3.3.1.
By CFD 54
9.3.3.3.4. 性能，注意始终至少一次访问内存
9.3.3.3.4.1.
9.3.4. 内存保护
9.3.4.1. 在分页系统中，内存保护是以页为单位，保护信息通常都保存在PTE中，可以提供只读、读写和执行（Read，Write，eXecute）保护
9.3.4.2. 此外，不是所有的PTE都可以使用，PTE中的一位表示该PTE是否可以使用（valid/inValid），仅当该位有效时，MMU才能用它进行地址转换，否则MMU就通过异常向OS报
告错误
9.3.5. 页表问题
9.3.5.1. 页表大小计算
9.3.5.1.1.
By CFD 55
9.3.5.2. 层级页表Hierarchical Page Tables-以二级页表为例
9.3.5.2.1. 把一个巨大的线性表分割成很多个小的页表，通过称为outer page table的表，把小页表组织起来，通常称outer page table为页目录page directory，其中的每一项称为页目录条目Page Directory Entry(PDE)。size(PDE)=4B
9.3.5.2.2.
9.3.5.2.3. 地址划分
9.3.5.2.3.1.
9.3.5.2.4. 地址转换
9.3.5.2.4.1.
By CFD 56
9.3.5.3. 哈希页表Hashed Page Tables
9.3.5.4. 反向页表Inverted Page Tables
9.3.6. 帧管理
9.3.6.1. 操作系统需要管理系统中所有frame的分配和回收
9.3.6.2. 最简单的方法是维护一个空闲的frame链表（free- frame list）
9.3.6.2.1.
9.4. 分段内存管理
9.4.1. 介绍
9.4.1.1. 分段把进程的逻辑地址空间分成一个个大小不等的段，每一段集中了一种类型的数据，如代码、数据、栈等等
9.4.2. 用户视角的分段式内存
9.4.2.1.
By CFD 57
9.4.2.2.
9.4.3. 实现
9.4.3.1. 逻辑地址由两部分组成
9.4.3.2. 段表用于将逻辑地址映射到物理地址
9.4.3.3. 每个表条目内容
9.4.3.3.1. 基址base：指定段的长度
9.4.3.3.2. 限制limit：指定段的长度
9.4.3.3.3. 保护位protection bits(RWX)
9.4.3.4. Segment-table base register(STBR)：指向内存中的段表位置
By CFD 58
9.4.3.5. Segment-table length register (TLR)：指示进程使用的段数
9.4.3.6. 地址转换
9.4.3.6.1.
9.4.3.6.1.1.
9.4.3.7. 内存保护与共享
9.4.3.7.1. 在分段系统中，内存的保护与共享以段为单位
9.4.4. 结论
9.4.4.1. 分段会产生外部碎片，由于系统无法预测每个进程使用内存的状况，外部碎片很难控制，因此，单纯的分段系统
目前很少使用
By CFD 59
9.5. 段页式内存管理
9.5.1. INTEL IA-32(80386以后CPU的统称，包含80386)是段页式内存管理的典范
9.5.2. 以IA-32为例
9.5.2.1. 分段是必须的，每个段最大可以为4GB，段表项被称为描述符descriptor，相应的段表被称为描述符表descriptor table，逻辑地址中的segment被称为段选择子segment selector，简称selector
9.5.2.2. 分页是可选的，页面和frame大小为4KB，采用二级页表
9.5.2.3. 地址转换
9.5.2.3.1. 段页式内存管理的地址转换包括两个步骤：先分段再分页
9.5.2.3.2.
10. 虚拟内存
10.1. 介绍
10.1.1. 虚拟内存是用户逻辑内存和物理内存的分离
10.1.1.1. 为每个进程提供一个巨大的、连续的和私有的逻辑内存，它可能比物理内存大得多。程序只有一部分需要在内
By CFD 60
存中执行
10.1.1.2. 允许多个进程共享地址空间以更高效地创建进程
10.1.2. 实现方法
10.1.2.1. 按需分页demand paging
10.1.2.2. 按需分段demand segmentation
10.1.3.
10.2. 按需分页相关概念
10.2.1. 一般情况下，我们用swapper表示整个进程的交换，而用pager来表示对页进行交换的lazy swapper
10.3. 什么时候引入页面
10.3.1. 对于每个页表条目（PTE），都会关联一个valid-inValid位，如果该位设置为”有效”，则表示相关联的页是有效的且在
内存中；否则，它表示页面不合法（即不在进程的逻辑地址空
间中），或合法但当前不在内存中
10.3.2.
By CFD 61
10.4. 如果页面不在内存中会发生什么？
10.4.1. 在MMU地址转换期间，如果PTE中的valid-inValid位无效，CPU触发一个缺页异常page-fault，进入操作系统。然后OS查看一个内部表（通常保存在PCB中）来决定它是否是合法
的映射，如果是不合法映射，OS终止进程，合法但不在内存中，操作系统会引入相应页面
10.4.2. 缺页异常服务例程Page-fault service routine
10.4.2.1. 1. 我们检查此进程的内部表，以确定其是否合法或非法内存访问
10.4.2.2. 2. 如果引用是非法的，我们将终止该过程，如果引用是合法的，但是我们还没有引入该页，我们现在将其引入
10.4.2.3. 3. 我们找到一个空闲的frame
10.4.2.4. 4. 我们调度一个磁盘操作，将所需的页读入新的分配帧frame
10.4.2.5. 5. 当磁盘读取完成时，我们修改进程中保留的页表，以指示页现在在内存中
10.4.2.6. 6. 我们重新启动被page-fault中断的指令。此时进程可以访问该页，就好像它一直在内存中一样
10.4.2.7.
By CFD 62
10.4.3. 结构要求
10.4.3.1. 页表
10.4.3.2. 辅助存储器
10.4.3.2.1. 这个存储器保存主存储器中不存在的页。通常称为交换空间swap space
10.4.3.3. 发生page-fault后正确重启指令的能力
10.5. 页面替换page replacement
10.5.1. 如果没有空闲帧frame会发生什么?
10.5.1.1. 在内存中查找一个frame，但不在使用中，将其分页
10.5.2. 通过在页错误服务例程增加页替换来防止内存过度分配
10.5.2.1. 找到一个空闲帧
10.5.2.2. 如果有空闲帧，请使用它：否则使用页面替换算法选择牺牲帧；将牺牲页面写入磁盘；相应地更改PTE
10.5.2.3. 将所需页面读入（新的）空闲框架；更改PTE
10.5.2.4. 重新启动指令
10.5.2.5.
By CFD 63
10.5.3. 页面替换完成了可以在较小的物理内存上提供较大的虚拟内存
10.5.4. 改进
10.5.4.1. 如果没有帧是空闲的，则需要两页传输一写一读
10.5.4.2. 我们可以通过将每个页面关联一个修改位（或脏位）来减少这一开销，每当页面被修改时，硬件都会设置这个位，只有在设置了脏位时才需要写出去
10.5.5. 算法
10.5.5.1. 算法目标：最低page-fault率
10.5.5.2. 评估算法
10.5.5.2.1. 引用字符串-内存引用的字符串，通常以页面为单位
10.5.5.2.2. 通过在引用字符串上运行算法并计算该字符串上的页面错误数来评估算法
10.5.5.2.3. 参考字符串7,0,1,2,0,3,0,4,2,3,0,3,3,3,2,1,2,0,1,7,0
10.5.5.3. page-fault数与frame数关系
10.5.5.3.1.
By CFD 64
10.5.6. 常用page replacement算法
10.5.6.1. 先到先得页面替换FIFO page replacement
10.5.6.1.1. 15次page-fault
10.5.6.1.2. 一般情况下，page-fault会随着frame的数量增加而减少，但是，如 果采用FIFO算法，情况有时并非如
此。
10.5.6.1.2.1.
10.5.6.2. 最佳页面替换Optimal page replacement
10.5.6.2.1. 替换长时间不使用的页
10.5.6.2.2.
By CFD 65
10.5.6.2.3. 需要预测未来，无法实现，仅提供最优解参考
10.5.6.3. 最近最少使用(least-recently-used)LRU page replacement
10.5.6.3.1. 可能需要大量的硬件协助来确定上次使用时定义的帧的顺序
10.5.6.3.2.
10.5.6.4. Second-chance page replacement
10.5.6.4.1. 很少有计算机系统为真正的LRU算法提供足够的硬件支持，为了近似，一些硬件提供了一些引用（R）或访
问（A）位的格式
10.5.6.4.2. 每当访问一个页面时，硬件将设置与该页面相关联的R位，当一个页面被选中时，我们检查它的R位，如
果R=0，替换这个页面；否则，我们再给它一次机会，然后继续选择下一页。当一个页面获得第二次机会时，由软件将它的R位清除。
10.5.6.4.3.
By CFD 66
10.5.6.4.4. 又称为时钟页面替换：当出现页面错误时，检查指针指向的页面所采取的操作取决于R位。R=0：替换页
面，R=1：清除R并前进
10.5.6.4.4.1.
10.5.7. 抖动Thrashing
10.5.7.1. 介绍
10.5.7.1.1. 如果系统没有帧，则页面错误率非常高。这会导致以下问题
10.5.7.1.1.1. CPU利用率低
10.5.7.1.1.2. 接纳调度器认为它需要增加多道程序设计的程度
10.5.7.1.1.3. 系统中添加了更多进程
By CFD 67
10.5.7.2. 概念
10.5.7.2.1. 一种系统忙于将页面导入和导出而没有任何用处的情况
10.5.7.2.2.
10.5.7.3. 局部模型Locality model
10.5.7.3.1. 局部Locality定义为系统中活动使用的一组页
10.5.7.3.2. 进程从一个Locality迁移到另一个Locality
10.5.7.3.2.1.
10.5.7.3.3. Locality model 也是caches可以工作的原因（cache中缓存的就是最近系统使用的页）
10.5.7.3.4. 抖动发生原因
10.5.7.3.4.1.
By CFD 68
10.5.7.4. 工作集Work-set model
10.5.7.4.1. 工作集模型是局部模型的近似，它定义了一个名为working-set窗口，△，作为页引用的数量
10.5.7.4.2. 工作集指的是在最近working-set窗口中的页集合，因此工作集模型就是Locality模型的近似
10.5.7.4.3. 我们用WSS来表示进程P最近working-set窗口里的工作集
10.5.7.4.4.
10.5.7.4.5. 举例
10.5.7.4.5.1.
10.5.7.4.6. 工作集的使用
10.5.7.4.6.1. 操作系统监视每个进程的工作集，并将足够的帧定位到该工作集，以提供其工作集大小
10.5.7.4.6.2. 如果有足够的额外帧，则可以创建新进程；否则，如果工作集大小的总和超过总帧，则操作系统将
选择一个进程来挂起
10.5.7.4.6.3. 工作集策略在保持多道程序设计尽可能高的程度的同时防止抖动
11. 文件管理
11.1. 文件系统接口
By CFD 69
11.1.1. 文件概念
11.1.1.1. 逻辑上的连续辅助存储器，把磁盘虚拟化
11.1.1.2. 类型
11.1.1.2.1. 数据文件
11.1.1.2.2. 程序
11.1.1.3. 文件结构
11.1.1.3.1. 无结构，仅仅是字节序列
11.1.1.3.2. 简单记录结构，线性，固定长度或可变长度
11.1.1.3.3. 复杂结构
11.1.1.3.3.1. 格式化文档Formatted document
11.1.1.3.3.2. Object file
11.1.1.3.3.3. 可执行文件executable file
11.1.1.3.4. 由操作系统和程序决定
11.1.1.4. 文件属性
11.1.1.4.1. 名字
11.1.1.4.2. 类型
11.1.1.4.3. 位置
11.1.1.4.4. 大小
11.1.1.4.5. 保护-访问权限
11.1.1.4.6. 时间，数据以及用户标识
11.1.1.5. 文件操作
By CFD 70
11.1.1.5.1. 创建
11.1.1.5.2. 打开
11.1.1.5.2.1. 当文件被打开时，除了存储在设备上的信息外，还需要一些数据来管理打开的文件
文件指针-指向上次读/写位置的指针，每个打开文件的进程
File-open count-当最后一个进程关闭文件表时，允许从打开的文件表中删除数据的文件打开次数的计数器
数据访问信息的文件缓存的设备位置
访问权限-每个进程访问模式信息
11.1.1.5.3. 关闭
11.1.1.5.4. 读取
11.1.1.5.5. 写入
11.1.1.5.6. 查找
11.1.1.5.7. 删除
11.1.1.6. 文件类型
11.1.1.6.1.
By CFD 71
11.1.2. 访问方式
11.1.2.1. 顺序访问
11.1.2.2. 随机访问
11.1.3. 目录结构
11.1.3.1.
11.1.3.2. 目录操作
11.1.3.2.1. 查找文件
11.1.3.2.2. 创建文件
11.1.3.2.3. 删除文件
11.1.3.2.4. 列出文件目录
11.1.3.2.5. 重命名文件
By CFD 72
11.1.3.2.6. 遍历整个文件系统
11.1.3.3. 单级目录
11.1.3.3.1.
11.1.3.3.2. 问题
11.1.3.3.2.1. 命名问题
11.1.3.3.2.2. 分组问题
11.1.3.4. 二级目录
11.1.3.4.1.
11.1.3.4.2. 功能
11.1.3.4.2.1. 支持文件路径定位
11.1.3.4.2.2. 支持重名文件
11.1.3.5. 三级目录
11.1.3.5.1.
By CFD 73
11.1.3.5.2. 功能
11.1.3.5.2.1. 支持分组
11.1.3.5.2.2. 支持绝对路径或相对路径定位
11.1.3.5.2.3. 每个进程的工作（当前）目录
11.1.3.6. 环状目录
11.1.3.6.1.
11.1.3.6.2. 功能
11.1.3.6.2.1. 支持同一文件的两个不同名称，即别名
11.1.3.6.2.2. 悬垂指针问题
有些操作系统不支持非循环图形目录，例如MS-DOS
By CFD 74
UNIX/LINUX和Windows（7+）通过符号链接支持
11.1.4. 文件系统挂载
11.1.4.1. 文件必须装入位于设备上的文件系统才能进行访问
11.1.4.1.1. 挂载文件系统的位置称为挂载点
11.1.4.1.2. 通常，装入点是一个空目录
11.1.4.2.
11.1.5. 文件共享
11.1.5.1. 在多用户系统上共享文件是可取的，大多数系统通过其唯一的用户标识或UID来标识用户
11.1.5.2. 除了UID，一些系统还实现了组功能，每个组被分配一个唯一的组标识或GID，每个用户可以在一个或多个组中
11.1.5.3. 当文件或目录最初创建时，它与使用的UID和GID相关联，拥有文件的用户是该文件的所有者
11.1.6. 文件保护
11.1.6.1. 文件所有者可以控制文件被哪些人以什么方式访问，读、写、执行、添加、删除、列出
11.1.6.2. UNIX/Linux 文件和目录保护
11.1.6.2.1.
By CFD 75
11.1.6.3. 访问控制列表
11.1.6.3.1.
11.2. 文件系统实现
11.2.1. 文件系统结构
11.2.1.1. 文件
11.2.1.1.1. 逻辑存储单元
11.2.1.1.2. 相关信息的收集
11.2.1.1.3. 文件控制块（File Control Block, FCB）包含文件的所有元信息
11.2.1.1.3.1.
By CFD 76
11.2.1.2. 文件系统驻留在辅助存储上，并被组织成层
11.2.1.2.1. 内存文件系统结构
11.2.1.2.1.1. 内存分区表，其中包含有关每个已装入分区的信息
11.2.1.2.1.2. 一种内存目录结构，保存最近访问的目录的目录信息
11.2.1.2.1.3. 系统范围的打开文件表，包含每个打开文件的FCB副本以及其他信息
11.2.1.2.1.4. 每个进程打开文件表，包含指向系统范围打开文件表中相应项的指针，以及其他信息
11.2.1.2.1.5.
By CFD 77
11.2.2. 文件系统实现
11.2.2.1. 虚拟文件系统Virtual File System(VFS)
11.2.2.1.1. 大多数操作系统使用面向对象技术来简化、组织和模块化
11.2.2.1.1.1. 公共文件系统接口，实现与文件系统实现分离
11.2.2.1.1.2. 文件系统接口，包含诸
如”openclose..write and seek”等系统调用
11.2.2.1.2. 示意图
11.2.2.1.2.1.
11.2.2.1.3. VFS接口提供两个重要功能
11.2.2.1.3.1. 通过定义一个干净的VFS接口将文件系统通用操作与其实现分离
11.2.2.1.3.2. VFS基于一个文件表示结构，称为vnode，它包含一个用于网络范围内唯一文件的数字指示符
11.2.3. 目录实现
11.2.3.1. 许多操作系统把目录当作一个文件对待，一个目录可能包括许多文件或者子目录
By CFD 78
11.2.3.2. 实现方式
11.2.3.2.1. 线性表Linear List-众多操作系统的选择
11.2.3.2.2. 哈希表Hash table
11.2.4. 分配实现
11.2.4.1. 连续分配Contiguous allocation
11.2.4.1.1. 每个文件占用磁盘上的一组相邻块
11.2.4.1.2. 优点
11.2.4.1.2.1. 简单：只保存起始块和长度（块数）
11.2.4.1.2.2. 支持随机访问和缓存友好（局部性好）
11.2.4.1.3. 缺点
11.2.4.1.3.1. 遭受外部碎片的折磨-动态存储分配问题
11.2.4.1.3.2. 难以扩展文件
11.2.4.1.4.
11.2.4.2. 链接分配Linked allocation
11.2.4.2.1. 每个文件都是数据块的链接列表
By CFD 79
11.2.4.2.1.1. FCB包含指向文件的第一个和最后一个块的指针，每个块都包含指向下一个块的指针，这些指针对
用户不可见
11.2.4.2.1.2. 因此，如果数据块是512字节，块地址（指针）需要4字节，那么用户会看到508字节的块
11.2.4.2.2. 优点
11.2.4.2.2.1. 简单：只需要起始地址
11.2.4.2.2.2. 不浪费空间
11.2.4.2.3. 缺点
11.2.4.2.3.1. 指针所需的额外空间
11.2.4.2.3.2. 无随机访问
11.2.4.2.3.3. 指针分散，可靠性差，某一个FCB中指向下一FCB的地址错误，会造成严重后果
11.2.4.2.4. 文件分配表File Allocation Table(FAT)
11.2.4.2.4.1. 为了解决简单的链接分配问题，在每个分区的开头留出一段磁盘来包含一个包含文件系统所有指针
的表这个表被称为文件分配表（FAT）
11.2.4.2.4.2.
By CFD 80
11.2.4.2.4.3.
11.2.4.3. 索引分配Indexed allocation
11.2.4.3.1. 将指向文件数据块的所有指针合并到一个位置索引块中，索引块保存数据块地址数组
11.2.4.3.2. 优缺点
11.2.4.3.2.1. 需要索引表
11.2.4.3.2.2. 随机存取
11.2.4.3.2.3. 没有外部碎片但有索引块开销的动态访问
11.2.4.3.3.
11.2.4.3.4. 索引块结构
11.2.4.3.4.1. 链表结构
11.2.4.3.4.2. 多级结构
11.2.4.3.4.3. 链表和多级结构的混合
11.2.4.3.5. UNIX文件系统的FCB结构，inode
11.2.4.3.5.1.
By CFD 81
11.2.4.3.5.2. 小到40K文件，大到TB级别文件都可以存储
11.2.5. 空闲空间管理
11.2.5.1. 比特向量，又叫位映射
11.2.5.1.1. 空闲置1
11.2.5.1.2. 被分配（占用）置0
11.2.5.2. 链表
11.2.5.2.1. 将所有空闲磁盘块链接在一起，并将指向第一个空闲块的指针放在磁盘上的特定位置，然后将其快速缓存
到内存中
11.2.5.2.2. 优缺点
11.2.5.2.2.1. 指针（链接头除外）保存在空闲块中，占用空间小
11.2.5.2.2.2. 遍历列表以获取空闲块是无效的，因此在开始时缓存空闲块的几个地址
11.2.5.2.3.
