概述

操作系统的功能

• CPU管理：进程/线程管理。进程/线程状态、控制、同步互斥、通信、调度…
• 存储管理。分配/回收、地址管理、存储保护、内存扩充…
• 文件管理。文件目录、文件操作、磁盘空间、文件存取控制…
• 设备管理。设备驱动、分配回收、缓冲技术…
• 用户接口。系统命令、编程接口…

OS是硬件上的第一层软件

• 例如读取文件：“从某个文件读一个数据块” or “移动磁头，等待放下”
• OS 在应用程序578和硬件之间建立一个“虚拟机”
• 对硬件抽象、提高程序可移植性

OS的特征

• 并发（concurrency），能处理同时的活动。
  • 这些活动之间有依赖关系，需要解决同步等问题。
  • 宏观上看，程序在同步执行。微观上看，程序在CPU上轮流执行
• 共享（sharing），
  • 互斥共享（打印机）/同时共享（磁盘文件）
• 虚拟（virtual）
  • 一个物理实体，映射为若干逻辑实体
  • 提高资源利用率
  • 例如：CPU–进程，存储器–每个进程有独立的虚拟地址空间，显示设备–多窗口/虚拟终端
• 随机。处理不可预测的次序发生的事件
  • 多个进程的运行速度不可预知

操作系统的分类（还有别的分类方法，这里只写一种）

1. 批处理操作系统。用户把作业交给系统操作员，操作员把作业输入到计算机系统，计算机批量处理。
   • 用户用卫星机把作业放入“输入井”，主机读取“输入井”，处理后把结果放入“输出井”，用户从“输出井”获取处理结果
2. 分时操作系统：CPU分成片段，轮流供每个用户使用，使用户感觉自己在连续使用。
3. 实时操作系统：要求计算机立即响应外部请求，并在严格时间内完成处理，高可靠性。
   • 工业控制、航空、军事
   • 实时通信（信息）处理
   • 硬实时系统：要求必须在规定时间内完成。
   • 软实时系统：偶尔可以违反时限。例如播放器。
4. 个人计算机操作系统：界面友好、使用方便、应用丰富。
5. 网络操作系统。按网络体系结构协议标准开发的软件。
   • 网络管理、通信、安全、资源共享、各种网络应用
6. 分布式操作系统。是一个统一的操作系统，若干台计算机共同完成任务。
7. 嵌入式操作系统。各种设备，例如汽车、手机、电视机。

系统调用：操作系统给应用程序的接口

• 允许应用程序执行一些操作/服务（例如文件操作、进程管理、内存分配、设备管理）
• 过程中从用户态切换到内核态（叫做陷入 trap）

中断和异常

• 中断由外部设备和事件引起的
• 异常是由正在执行的程序内部产生的错误或特殊情况引起的
• 都对应从 用户态 切换到 内核态

操作系统的性能评价

• 本身的执行速度。操作系统对用户程序的响应时间、操作系统执行用户程序的吞吐量
• 资源利用率。包括操作系统本身的资源占用
• 用户的方便程度。功能的强弱、界面的友好、兼容性
• 操作系统的可扩充性、可移植性、兼容性
• 操作系统管理下的安全性、保密性、正确性、可靠性、可维护性、稳健性
• 性能性价比

进程/线程

多道程序设计：允许多个程序同时进入内存并运行。目的是提高系统效率。

• 每个程序都有自己的逻辑程序计数器
• 哪个运行，就把哪个放入物理计数器
• 每个程序轮流执行，并发执行

并发环境：

• 单个处理器上的程序，同时 处于开始运行但尚未结束的状态
• 并且次序不是事先确定的

进程（Process）：有独立功能的程序关于某个数据集合上的一次运行活动

• 又称任务（Task、Job）
• 是对 CPU 的抽象。
• 是把一个 CPU 抽象为 多个虚拟的CPU
• 一单位为分配，如内存、文件
  • 每个都有独立的地址空间。意味着每个进程的地址空间是逻辑地址，而不是物理地址。
• 操作系统把 CPU 调度给需要的进程

PCB（Process Control Block，进程描述符，进程属性）

• 一个专门数据结构，记录进程的各种属性、描述进程的动态变化过程
• 进程与 PCB 是一一对应的
• 所有 PCB 集合叫做 进程表
  • 进程表的大小限制了操作系统可以同时开多少个进程
• PCB 记录了哪些信息？
  • 进程描述信息
    • 进程标识符 process ID，唯一、整数
    • 进程名，通常基于可执行文件名
    • 用户标识符 user ID
    • 进程组关系
  • 进程控制信息
    • 当前状态
    • 优先级 priority
    • 代码执行入口地址
    • 程序的磁盘地址
    • 运行统计信息（执行时间、页面调度）
    • 进程间同步和通信
    • 进程的队列指针
    • 进程的消息队列指针
  • 进程拥有的资源和使用情况
    • 虚拟地址文件状况
    • 打开文件列表
  • CPU 现场信息。进程不运行状态下保存的信息。
    • 寄存器值（通用机孙琦、PC、状态字PSW、栈指针）
    • 指向进程页表的指针
• 在不同的操作系统下是不一样的。Linux：task_struct, Windows：EPROCESS,KPROCESS,PEB

进程状态（基础状态）

• 运行态（Running），占有 CPU，并在 CPU 运行
• 就绪态（Ready），已经具备运行条件，但没有空闲 CPU
• 等待态（Waiting/Blocked、阻塞态、封锁态、睡眠态），等待某个事件而暂时不能运行。例如等待读磁盘。

进程的其他状态

• 创建态（New），已经完成创建的必要工作（PID，PCB），但是尚未同意执行该进程（例如资源有限）
• 终止态（Terminated）。
  • 终止执行
  • 可完成一些数据统计工作（资源使用量等）
  • 资源回收
• 挂起态（suspend）
  • 用于负载调节
  • 进程的内存会被回收，进程印象道磁盘上。
  • 资源足够后会重新激活

除此之外，还有类似的七状态模型

Linux 的进程态:

进程队列。进程状态的改变，实际上是 PCB 从一个队列出列，进入另一个队列的过程

• 例如，就绪态可能有多个队列

进程控制

进程控制操作完成进程之间的转换，由 原语（primitive） 完成。（原语一种原子操作，不可分割、不可中断）

进程的创建

• 分配一个唯一标识，进程控制块
• 分配地址空间
• 初始化进程控制块
• 设置相应的队列指针。
  • 例如新进程加入到就绪队列链表中。
• unix：fork, exec。Windows：CreateProcess

进程的撤销（结束进程）

• 资源回收：关闭打开的文件、断开网络链接、回收分配的内存
• 撤销进程的 PCB
• unix:exit，windows：TerminateProcess

进程的阻塞

• 进程自己执行阻塞原语
• unix：wait，windows：WaitForSingleObject

unix 几个进程控制函数

• fork() 复制调用进程来建立新的进程。最基本的进程建立过程。
• exec() 用新的程序代码覆盖原来的地址空间，实现进程执行代码的转换
• wait() 初级进程同步操作，使一个进程等待另一个进程的结束
• exit() 终止一个进程的运行

fork() 的实现

• 为子进程分配一个空闲的进程描述符（proc 结构）
• 为子进程分配 pid
• 一次一页的方式复制父进程地址空间
  • 子进程的代码一般与父进程不同，这一步就造成浪费。Linux 采用 Copy-On-Write 技术来解决
    • 不复制父进程地址空间，而是用一个指针指向它，然后设定为只读。
    • 如果需要写入它，就开辟一个新的空间来写入
• 从父进程继承共享资源（如，打开的文件、当前工作目录）
• 把子进程状态设为就绪，插入到就绪队列
• 对子进程返回标识符 0
• 向父进程返回子进程的 pid

fork() 的使用

伪代码：

pid = fork(); // 创建一个子进程
if(pid<0){
    fprintf("出错");
    exit(-1);
}
else if(pid == 0){ 
    // 因为子进程会把父进程的一页复制进来
    fprintf("pid = 0 说明正在运行的是子进程");
    exec("xxx") // 调用 exec，用新代码覆盖子进程的地址空间
}
else {
    fprintf("pid>0 ，指的是子进程的 pid，并且正在运行的是父进程");
    wait(NULL); // 父进程等待子进程结束
    exit(0);
}

进程相关概念

分类1:

• 系统进程（优先级较高）
• 用户进程

分类2:

• 前台进程。与用户直接交互的，例如鼠标键盘
• 后台进程。打印、防火墙、电子邮件接收等

分类3:

• CPU密集型进程
• IO密集型进程

进程的层次结构

• unix：进程树。init 为根。父进程结束，子进程也必须结束。
• Windows：地位相同。虽然也是由进程建立另一个进程，但是未必一个结束另一个也结束。

进程与程序：一个程序可以对应多个进程。

进程有自己的地址空间（逻辑地址，而不是物理地址）

进程映像（IMAGE）

• 由进程地址空间内容、硬件寄存器、进程相关的内核数据结构、内核栈组成
• 相当于一个快照

上下文切换（Context Swith）

• CPU 硬件从一个进程切换到另一个进程的过程
• 进程不运行时，寄存器值保存在 PCB 中；切换到某个进程时，从对应的 PCB 中把值送回寄存器

线程

为什么需要多线程？

• 例如一个编辑器，需要同时处理：键盘输入、自动排版、定时保存。
• 一个Web服务器，需要同时接受网页请求、从磁盘检索网页、读入内存、把结果返回给客户端。

其它方案都有缺点：

• 如果使用单个进程，顺序编程，性能低
• 如果使用多进程，就不能使用共享的内存空间了
• 如果使用有限状态机方法（就是用一些编程手段来模拟多进程），例如非阻塞IO，编程会非常复杂

多线程的好处2:开销小

• 进程涉及到进程创建、进程撤销、进程通信、进程切换，时间和空间开销大
• 线程开销小：
  • 创建和撤销花费时间少
  • 线程切换花费时间少
  • 线程间通信无须调用内核，同一个进程的线程共享内存和文件

线程的好处3:多个处理器，可以充分发挥优势

线程是什么？

• 进程有两个属性：资源拥有者、CPU调度单位
• 线程只继承一个属性：CPU调度单位。（因此有时候把线程称为 轻量级进程）

线程的属性

• 标识符 ID
• 状态、状态转换
• 不运行时需要保存的上下文（例如PC寄存器）
• 线程有自己的栈和栈指针
• 共享所在进程的地址空间和其它资源
• 线程可以创建、撤销另一个线程

线程的实现

用户级线程

• Run-time system 完成线程的管理工作
• 内核管理的还是进程，不知道线程的存在
• 线程切换不需要内核态特权
• 例子：UNIX，遵守 POSIX 规范
• 优点：
  • 线程切换快
  • 调度算法是应用程序特定的
  • 可以运行在任何操作系统上（只需实现线程库）
• 缺点：
  • 内核把处理器分配给进程。同一个进程的两个线程不能同时运行在两个处理器上
  • 大多数系统调用时阻塞的。因此内核阻塞时，进程中所有线程也被阻塞

核心级线程

• 内核管理所有的线程
• 内核既维护进程，也维护线程
• 线程的切换需要内核支持
• 以线程为基础进行调用
• 例子：Windows

混合模型

• 线程的创建在用户空间完成
• 线程调度在核心态完成
• 例子：Solaris

协程：比线程更加轻量级。用户态。资源消耗更小。

• 计算密集型任务：
  • 多线程：适用于支持真正多线程的编程语言（如C++、Java、Go），能够高效利用多核CPU，实现并行计算。
  • 多进程：适用于存在全局解释器锁（如Python）或需要高隔离性的应用，能够绕过GIL，实现真正的并行。
  • 协程：不推荐单独使用，因其无法充分利用多核并行计算能力。
• I/O密集型任务：
  • 协程：非常适合高并发、I/O密集型任务，通过高效的任务切换和低开销实现高并发。
  • 多线程和多进程： 也可用于I/O密集型任务，但协程在资源利用和性能上更具优势。

通过综合考虑任务类型、编程语言特性和系统架构需求，选择最合适的并发模型能够显著提升系统性能和开发效率。

CPU调度

CPU调度：从就绪队列中选择一个进程，把 CPU 使用权交给它。

• N个进程就绪状态
• M个CPU空闲状态
• 需要决策：给哪个进程分配哪个CPU

需要解决3个问题：

• When：调度时机
• What：调度算法，调度哪个
• How：如何调度（进程的上下文切换）

调度时机：就绪队列改变。具体来说，有4个情况：

• 进程正常终止、由于错误终止
• 新进程创建。某个进程从等待变成就绪
• 进程从运行态变成阻塞态
• 进程从运行态变成就绪态

上下文切换的开销

• 直接开销：内核完成切换所用的CPU时间
  • 保存和恢复寄存器
  • 切换地址空间（昂贵）
• 间接开销
  • 高速缓存、缓冲区缓存、TLB等区域的失效

调度算法考虑的因素

• 不同的系统：批处理系统、多道程序设计系统、批处理与分时的混合系统、个人计算机、网络服务器
• 性能的理解。用户角度：周转时间、响应时间、任务的最后期限。系统角度：吞吐量、CPU利用率。
• 其它方面。用户角度：可预测性。系统角度：公平性、强制优先性、平衡资源。
• 调度算法衡量指标
  • 吞吐量（Throughput）：单位时间完成的进程数
  • 周转时间（TT，Turnaround Time）：进程从提出请求到运行完成的时间
  • 响应时间（RT，Response Time）：从提出请求到第一次回应的时间
  • CPU利用率（CPU Utilization）：CPU做有效工作时间的比例
  • 等待时间（Waiting time）：每个进程就绪队列（ready queue）中的等待时间。
• 调度算法相关的因素：
  • PCB 中存储了优先级。静态优先级（优先级不会变），动态优先级（优先级会变，例如等待较长时间后，把优先级提高）
  • 就绪队列。按照不同的优先级，队列有多个。
  • 抢占 CPU 的方式
    • 不可抢占式（Non-preemitive）。某进程被调度后一直运行下去，除非它由于自身原因不能运行
    • 抢占式（Preemptive）。有更高优先级的进程就绪时，系统强行剥夺正在运行进程的 CPU，提供给更高优先级的进程使用
  • IO密集型/CPU密集型
    • 一般优先运行IO密集型。因为它运行完后会进入等待态。
  • 时间片（Time slice，quantum）。单次允许进程运行的时间
    • 考虑因素：进程切换开销，对响应时间的要求，就绪进程个数，CPU能力，进程的行为。
    • 问题：时间片多大合适？长度固定还是可变？

调度算法

批处理系统常用的调度算法

• 先来先服务（FCFX，First Come First Serve）
  • 按照进程就绪的先后顺序使用 CPU
  • 非抢占
  • 实现简单、公平
  • 如果短进程在后面，整体等待时间长
• 最短作业优先（SJF，Shortest Job First）
  • 有最短完成时间的进程优先执行
  • 非抢占式
  • 提高了平均周转时间
• 最短剩余时间优先（SRTN，Shortest Remaining Time Next）
  • SJF 的抢占式版本，一个新就绪的进程比当前运行的进程有更短的完成时间时，抢占进程。
  • 所有进程同时可运行前提下，有最短的平均周转时间
  • 如果有源源不断的短任务到来，长任务会长时间得不到运行（饥饿问题）
• 最高响应比优先（HRRN，Highest Response Ratio Next）
  • 是 FCFX 和 SJF 的折中。先计算响应比 R = 周转时间/处理时间 = 1 + （等待时间/处理时间），响应比越高越优先。

交互式系统中的调度算法

• 轮转调度（RR，Round Robin）
  • 按照确定的顺序轮番调度，每次运行一个时间片
  • 如何确定时间片：
    • 时间片太长，大于一次典型交互时间，退化成FCFS算法。并且会延长响应时间（例如，100个进程，则需要100T才能轮到）。
    • 时间片太短，小于一次典型交互时间，进程切换频繁，浪费 CPU 时间
    • 经验选择 10ms-100ms 之间
  • 优点：公平。有利于交互式计算，响应快。
  • 缺点：进程切换有成本
  • 缺点：平均完成时间会下降。例如进程 A，B都需要 100ms完成，时间片为 1ms，那么调度顺序为 ABABAB...A(199)B(200)，平均完成时间为 199.5ms。相比之下， FCFS 平均完成时间为 （100ms+200ms）/2= 150ms
• 虚拟轮转算法（Virtual RR）
  • 为什么？使用 RR 算法时，IO 密集型任务每次分片都会提前执行完，并进入调度循环。这对于 IO 密集型任务很不公平。
  • Virtual RR 是 RR 的改进。另开一个“辅助队列”，当一个分片提前执行完，就会放入“辅助队列”。每次轮换优先从“辅助队列”选取，直到“辅助队列”为空。
• 最高优先级调度（HPF，Highest Priority First）
  • 总是选择优先级最高的进程来执行
  • 优先级设计：系统进程高于用户进程，前台进程高于后台进程，IO密集型进程高于CPU密集型进程
  • 优先级可以是静态不变的，也可以是动态变化的
  • 评价：实现简单、不公平、会让某些进程一直无法运行（饥饿现象）
  • 优先级反转 现象。例子，有高、中、低三个优先级的进程，记为 H、M、L，其中 L 持有 H 所需要的资源。那么 H 进入临界区被阻断，L进入临界区被抢占，M一直执行。导致高优先级进程一直无法运行，系统性能降低。（1997年，火星探测器上发生了此现象）
    • 解决方法3种：1）设置优先级上限，进入临界区的进程优先级都是最高的。2）优先级继承，L可以继承H的优先级。3）进入临界区的进程禁止中断
• 多级反馈队列（Multiple feedback queue）非抢占式
  • 是UNIX的BSD采用的调度算法，是一个综合调度算法
  • 就绪队列为多个，每个队列优先级不同，第一个队列优先级最高
  • 每个队列的时间片不同，优先级越低，时间片越大。$2^n$ 的方式递增。
  • 优先调度高优先级，直到高优先级为空，再调度下一个优先级的队列
  • 一个新进程就绪后直接进入第一级队列
  • 由于用完时间片而放弃 CPU 的进程，进入更低等级队列
  • 由于阻塞而放弃 CPU 的进程，就绪后进入原队列。这里有不同的策略：可以插入队尾或队首；分配的时间片可以是原本未用完的，也可以是新值。
  • 评价：对IO密集型更优先调度。对计算密集型，虽然优先度低，但时间分片长。
• 多级反馈队列，允许抢占
  • 被抢占的进程回到原来一级就绪队列的队尾（或队首）
• 最短进程优先（Shortest Process Next），与上面批处理中的 SJF 一样

多处理器调度算法，考虑问题：

• 不但要确定选择哪个进程执行，还要考虑哪个CPU上执行
• 考虑多CPU之间迁移时的开销。进程尽可能在同一个CPU上执行。
• 负载均衡问题

Windows的线程调度算法

典型系统的调度算法

• UNIX 动态优先数
• 5.3BSD 多级反馈队列
• Linux 抢占式调度
• Windows 基于优先级的抢占式多任务调度
• Solaris 综合调度算法

Windows的线程调度

• 由于 Windows 支持内核级线程，因此 调度单位是线程
• 调度算法是：基于动态优先级、抢占式、结合时间配合调整
  • 就绪线程按照优先级进入队列
  • 总是悬着优先级最高的就绪线程运行
  • 同一优先级各线程按时间片轮转进行调度
  • 多 CPU 允许多个线程并行运行
• 引发线程调度的条件
  • 一般的：正常终止/错误终止，新线程创建，等待线程变成就绪，运行态进入阻塞态，运行态变成就绪态
  • 还新增两种情况：1）一个线程的优先级改变了。2）一个线程改变它的亲和（Affinity）处理机集合

Windows 共有 32 个优先级

时间配额

进程互斥

进程互斥的例子 某程序是关于从账户付款的，初始余额为 5000元，连续两次付款（1000元和2000元），引发了2个进程：

这两个进程运行后，根据不同的调度顺序，可能有不同的结果

概念

• 进程互斥（Mutual Exclusive）：进程使用的某些共享资源（变量、文件等）需要排他性的使用（否则结果可能不对），各进程之间竞争使用这些资源。
• 临界资源 （critical resource）：资源一次只允许一个进程使用（叫做临界资源、互斥资源、共享变量）
• 临界区(互斥区，critical section，region)：各个进程中对某个临界资源（共享变量）实施操作的程序片段

不允许两个进程同时处于临界区。带来优先级反转问题（前面写了）

为了防止临界区重叠，有一些解决方案

• 软件方案：Dekker、Peterson
• 硬件方案：屏蔽中断、TSL(XCHG)指令

进程互斥的软件解决方案

一个错误的解决方案1：

... ...
while(free); // 如果 free = true，则一直在此等待；如果 free = false，则
free = true; // 标识临界区已被占用

临界区;

free = false; // 表示临界区已释放
... ...

上面的思路正确，但结果仍然可能错误。

• 原因是 程序挂起的时间点可能在 while(free) 和 free = true，这样仍然会临界区重叠
• 解决方案是把 while(free) 和 free = true 变成一个元语 ``，使其不可被中断，如下：

进程互斥的软件解决方案1:

... ...
lock();
临界区;
unlock();
... ...

一个错误的解决方案2：

进程 P:
... ...
while(not turn);
临界区
turn = false;

进程Q:
while(turn);
临界区
turn = true;

错误在于，如果 turn = true，且 Q 不想进入临界区，那么 P 就永远无法进入临界区。

一个错误的解决方案3：

进程 P:
... ...
pturn = true;
while(qturn);
临界区
pturn = false;

进程Q:
qturn = true;
while(pturn);
临界区
qturn = false;

上面的错误在于，如果 P 和 Q 恰好都在 pturn = true; 和 while(qturn); 语句之间中断，那么两个进程都永远无法进入临界区（After you 问题）。

DEKKER算法 （1965年）

• 在解法3 的基础上，引入 turn 变量（枚举类型），当出现 after you 问题时，由 turn 来决定谁进入临界区

进程 P:
... ...
pturn = true;
while(qturn){
    if (turn == 2){
        pturn = false;
        while(turn == 2);
        pturn = true;
    }
}
临界区
turn = 2;
pturn = false;

进程Q:
qturn = true;
while(pturn){
    if (turn ==1){
        qturn = false;
        while (turn == 1);
        qturn = true;
    }
}
临界区
turn = 1;
qturn = false;

此算法的缺点必须轮流运行

peterson算法 （1981年）

• 解决互斥问题
• 克服了DEKKER算法强制轮流的缺点

// 对于进程i：
enter_region(i);
临界区;
leave_region(i);


// 进入临界区的函数：
int turn; // 轮到谁了
int interested[N]; // 兴趣数组，记录哪个进程对进入 CPU 感兴趣，初始化为 false
void enter_region(int process){ // 此案例假设只有 2 个进程，因此 process = 0 或 1
    int other; // 另一个进程的进程号
    other = 1 - process;
    interested[process] = true; // 本进程对进入 CPU 感兴趣
    turn = process; // 设置标志位
    while(turn == process && interested[other] == true);
}


void leave_region(int process){
    interested[process] = false;
}

进程互斥的硬件解决方案

方案1：“开关中断”指令

执行 “关中断”指令
临界区
执行“开中断”指令

评价

• 简单、高效
• 如果临界区大，就限制了 CPU 的并发能力。
• 不适用于多处理器
• 适用于操作系统本身，不适于用户进程（因为用户程序不能使用特权指令）。

方案2:“测试并加锁”指令（TSL，TEST AND SET LOCK）

enter_region:
    TSL REGISTER,LOCK       | 复制锁到寄存器
    CMP REGISTER,#0        | 判断寄存器内容是否为0
    JNE enter_region        | 若不为0，跳转到 enter_region
    RET                     | 返回调用者，使其进入临界区 

leave_region:
    MOVE LOCK,#0            | 在锁中置0
    RET                     | 返回调用者

方案3:“交换指令”

enter_region:
    MOVE REGISTER,#1        | 寄存器置1
    XCHG REGISTER,LOCK      | 交换寄存器和锁的内容
    CMP REGISTER,#0        | 判断寄存器内容是否为0
    JNE enter_region        | 若不为0，跳转到 enter_region
    RET                     | 返回调用者，使其进入临界区 

leave_region:
    MOVE LOCK,#0            | 在锁中置0
    RET                     | 返回调用者

进程同步

进程同步（synchronization）：进程之间存在 时序关系。例如，一个进程运行到某一点，需要另一个进程给它提供消息，此时该进程进入阻塞态，获得消息后才进入就绪态。

生产者/消费者问题

• 生产者负责在缓冲区中放入数据。
• 消费者负责从缓冲区中取出数据。
• 如果缓冲区满了，生产者必须等待消费者消耗掉一些数据后才能继续放入数据。
• 如果缓冲区空了，消费者必须等待生产者放入数据后才能继续取出数据。
• 问题：忙等待，缓存区满/缓冲区空，都会有浪费。
• 解决方法：新增两个原语 睡眠、唤醒

【图片】

问题：if(count==0) sleep(); 之间用完时间并中断，那么重新调用时出现问题

信号量与 P、V 操作

• 1965年 Dijkstra 提出的
• 解决进程同步问题

信号量定义：

struct semaphore{
    int count;
    queueType queue;
}

信号量有3个操作

• 初始化
• P
• V

P(s){
    s.count--;
    if(s.count<0){
        进程设置为阻塞态，并吧进程插入到 s.queue 的末尾;
        重新调度，选另一个进程进入 CPU;
    }
}


V(s){
    s.count++;
    if(s.count<=0){
        唤醒 s.queue 中等待的一个进程;
        将其改为就绪态，并插入到就绪队列;
    }
}

说明：

• P、V 操作是原语
• 最初提出是二元信号量（解决互斥问题）
• 后来推广到一般信号量，可以解决同步问题

使用方法：

• 初始化信号量 mutex = 1
• 进入临界区前实施 P(mutex)
• 退出临界区之后实施 V(mutex)

用信号量解决生产者/消费者问题

【代码】

读者写者问题

问题描述

• 多个进程共享一个数据区，这些进程分为两组：
• 读者进程： 只读数据区中的数据
• 写者进程： 只往数据区写数据
• 要求满足条件：
  • 允许多个读者同时执行读操作
  • 不允许多个写者同时操作
  • 不允许读者、写者同时操作

分析

• 对于读者：
  • 无其他读者、写者，该读者可以读
  • 若已有写者等，但有其他读者正在读，则该读者也可以读
  • 若有写者正在写，该读者必须等
• 对于写者：
  • 无其他读者、写者，该写者可以写
  • 若有读者正在读，该写者等待
  • 若有其他写者正在写，该写者等待
• 读者写者问题是既包括互斥问题，也包括同步问题

Linux提供的读写锁

• 允许多个读同时进行
• 不允许读和写同时进行
• 不允许多个写同时进行

管程

为什么需要 管程（Monitor）

• 问题：信号量机制，程序编写困难、易出错
• 解决：1973年提出了新的同步机制，叫做管程
• 管程是一种高级同步机制
• 是一个特殊的模块，有个名字，有共享资源的数据结构以及一组操作组成
• 进程通过调用管程中的过程来间接访问管程中的数据结构

一个管程

monitor example
    integer i; // 变量
    condition c;

    procedure insert(); // 过程
    procedure remove(); // 过程

管程作为一种同步机制，解决两个问题

• 互斥
  • 管程是互斥进入的，这样可以保证管程中数据结构的完整性。
  • 管程的互斥性由编译器保证
• 同步
  • 管程中设置条件变量及等待/唤醒操作以解决同步问题
  • 可以让一个进程或线程在条件变量上等待（此时，应先释放管程的使用权），也可以通过发送信号将等待在条件变量上的进程或线程唤醒

场景：多个进程同时出现在管程中

• 原因：一个已进入管程的进程执行等待时，后进入管程的进程执行唤醒
• 如何解决
  • Hoare 管程，P 等待 Q 执行
  • MESA 管程，Q 等待 P 继续执行
  • Hansen，规定唤醒操作作为管程中最后一个可执行的操作

Hoare 管程

Hoare 管程说明

• 如果一个进程试图进入一个已被占用的管程，在 入口等待队列 等待
• 如果进程P唤醒进程Q，Q又唤醒R，管程内部出现多个等待进程，因此它们放在 紧急等待队列 中。紧急等待队列的优先级高于入口等待队列
• 条件变量：c:condition;
• 过程 wait(c)： 如果“紧急等待队列”为空，则唤醒第一个等待者；否则释放管程互斥权，并把执行该操作的进程放到 c 链的末尾
• 过程 signal(c)：如果 c 链为空，继续执行下一条语句；否则唤醒第一个等待者，然后执行该操作的进程进入“紧急等待队列”的末尾

如何实现一个管程？

• 直接构造：某个变成语言对应的编译器直接支持
• 间接构造：用已有的机制去构造，例如信号量和PV

用管程解决生产者消费者问题，代码会更简洁

// 生产者
procedure producer;
while 1:
    item = producer.produce();
    ProducerConsumer.insert(item); // 管程

// 消费者
procedure consumer;
while 1:
    item = ProducerConsumer.remove(); // 管程
    consumer.consume(item); 

对应的管程

monitor Producer Consumer;
    condition full, empty;
    integer count;

    procedure insert(item: integer){
        if count == N{
            wait(full);
        }
        insert_item(item);
        count++;
        if count == 1{
            signal(empty);
        }
    }

    procedure remove(){
        if count == 0{
            wait(empty);
        }
        item = remove_item();
        count--;
        if count==N-1{
            signal(full);
        }
    }

C/C++ 没有支持管程，但是 JAVA 支持

python、rust 本身没有管程，但可以用其它机制实现。

import threading

class Counter:
    def __init__(self):
        self.count = 0
        self.lock = threading.Lock()

    def increment(self):
        with self.lock:
            self.count += 1

    def get_count(self):
        with self.lock:
            return self.count

MESA 管程

Mesa语言（1980）提出的

Hoare 管程的缺点

• 两次额外的进程切换

进程间通信 IPC

为什么需要？

• 信号量和管程只能传递少量信息，不能传递大量信息
• 管程不适合多处理器的情况
• 因此引入进程间通信机制。

进程间通信方法

• 消息传递
• 共享内存
• 管道
• 套接字
• 远程过程调用

消息传递

• 不同的进程，内存地址不一样
• 因此需要“操作系统空间”作为中间缓冲
• 使用 send 和 receive 原语
• send 和 receive 原语可以用PV操作来构建

共享内存

• 两个进程的某一块逻辑地址，实际上都使用同一个物理地址
• 问题1:如何把两个进程各自的逻辑地址空间中的某一块，映射到同一个物理地址
• 问题2:读者-写者问题

管道PIPE

使用一个缓冲传输介质（内存或文件）链接两个进程

• 字符流方式写入读出
• 先进先出顺序
• 管道通信机制必须提供的协调能力
  • 互斥、同步、判断对方进程是否存在

典型操作系统的IPC

• UNIX
  • 管道、消息队列、共享内存、信号量、信号、套接字
• Linux
  • 管道、消息队列、共享内存、信号量、信号、套接字
  • 内核同步机制：原子操作、自旋锁、读写锁、信号量、屏障、BKL
• Windows
  • 同步对象：互斥对象、事件对象、信号量对象临界区对象互锁变量
  • 套接字、文件映射、管道、命名管道、邮件槽、剪贴板、动态数据交换、对象连接与嵌入、动态链接库、远程过程调用

其它概念

• 原子操作。原子操作命令可以确保操作不可中断性。
  • 大多数操作，例如 i++; 也是多步骤执行的，也会被中断，这在多线程中也会引发问题。
  • C/C++ 的 std::atomic, Java 的 AtomicInteger, Rust 的 Atomic
• Barrier （屏障，栅栏，关卡）。
  • 一组线程协同完成一项任务，需要所有线程都到达一个汇合点后再一起向前推进
  • 是一种同步机制，是对一组线程的协调
  • 例如，多线程做矩阵计算，需要等待所有线程执行完毕，才进行下一步操作。

存储模型

为什么需要地址重定位（relocation）

• 进程运行前，代码不知道进程会被加载到内存的哪个区域
• 因此代码使用的地址不是物理地址，而是逻辑地址
• 所以需要 地址重定位，它是逻辑地址和物理地址之间的转化
• 逻辑地址，是汇编后目标代码采用的地址。逻辑地址的首地址为0，其余地址都相对于首地址而编址
• 物理地址：就是内存中存储单元的地址

分类：

• 静态重定位：
  • 当用户程序加载到内存时，一次性实现逻辑地址到物理地址映射
  • 一般可以由软件完成
• 动态重定位（现代操作系统的主流）：
  • 在进程执行过程中进行地址变换。即逐条指令执行时完成地址转换
  • 需要硬件部件支持 内存管理单元（MMU，Memory Management Unit）

空闲内存管理

1. 为了更好的管理，内存可以划分为若干的区域，这分为 等长划分，不等长划分
2. 可以有若干种数据结构管理它：
   • bitmap，只适用于等长划分。用一长串二进制表示，0代表空闲，1代表占用。
   • 空闲表。表中的每一项纪录了空闲区的起始地址、长度、标志（标志用来指向程序）
   • 空闲块链表

内存分配算法，有若干种：

• 首次适配 first fit：在空闲区表中找到第一个满足进程要求的空闲区。
• 下次适配 next fit：从上次找到的空闲区接着查找
• 最佳适配 best fit：遍历整个空闲区表，找到能够满足进程要求的最小空闲区
• 最差适配 worst fit：总是分配满足进程要求的最大空闲区

以“空闲表”为例，分配以后，记得更新“空闲区域表”、“已分配区表”

内存回收算法

• 归还后，前后空闲空间合并
• 四种情况：上相邻、下相邻、上下相邻、上下都不相邻

伙伴系统（Buddy System）

• Linux 采用的一种内存分配算法
• 优点是可以保持大的内存块
• 主要思路：
  1. 把内存按照 $2^n$ 划分
  2. 组成若干空闲块链表
  3. 分配时选择满足要求的最小的块
  4. 如果最小的块超过需要的两倍，就把块二分，继续寻找。
  5. 回收后，如果一对伙伴都空闲，则合并；如果合并后，相邻的伙伴也空闲，继续合并（消消乐）

基本内存管理方案

常见的几种：

• 进程对应的物理内存连续的方案：
  • 单一连续区
  • 固定分区
  • 可变分区
• 进程对应的物理地址不连续的方案：
  • 页式
  • 段式
  • 段页式

单一连续区（Single Contiguous Allocation）。

• 整个可用内存被分配给一个单一的进程。
• 简单，内存利用率低。

固定分区（Fixed Partitioning）。

• 将内存划分为若干分区
• 每个分区大小可以相同，也可以不同
• 分区大小固定不变
• 每个分区可以容纳一个进程。
• 简单、可多进程。内存有浪费，分区大小不灵活。

可变分区（Variable Partitioning）。

• 根据进程需要来分配空间
• 运行一段时间后，随着进程启动和销毁，会出现大量碎片的空闲区（外碎片）。
• 解决方案：紧缩技术（memory compaction，压缩技术、紧致技术、搬家技术）
• 紧缩考虑的问题：系统开销、移动时机。

页式（Paging）

• 进程的地址空间划分为大小相同的 页（page，页面）
• 内存空间也划分同样大小的 页框（page frame）
• 典型的页大小：4K/4M
• 内存分配规则：以页为单位分配，按进程需要的页来分配。逻辑上相邻的页，物理上不一定相邻。
• 使用 页表（Page Table） 这种数据结构来把 逻辑页 映射到 物理页
• 空闲内存管理：bitmap
• 地址转换，用硬件完成。CPU获取逻辑地址，分解为页号+页内地址，用页表把页号映射到页框号，然后页框号+页内偏移=物理地址
• 问题：内碎片。最后一页未用完的空间。例如，最后一页只有1个字节，也要分配一页。

段式（Segmentation）。

• 程序按照自身的逻辑关系，划分为若干程序段。
• 内存动态划分为若干长度不同的物理段
• 内存分配规则：以段为单位进行分配，每段占据物理内存连续，但是段之间物理内存可以不连续

段页式（Segmented Paging）。段页式结合了段式和页式的优点，先将进程划分为多个段，每个段再划分为若干页。

虚拟存储技术

• 问题：如何在较小的内存空间，运行较大的进程？有以下几个方法
• 清除碎片：内存紧缩技术
• 覆盖技术 overlaying：程序大小超过物理内存总和。
  • 早期的操作系统
  • 按照自身的逻辑结构，让不会同时执行的程序段使用同一块内存区域
  • 要求各模块之间有明确的调用结构
  • 程序员声明覆盖结构，操作系统完成自动覆盖
• 交换技术 swapping
  • 也比较原始了
  • 内存空间紧张时，系统将内存中某些进程暂时移到外存，把外存中某些进程换进内存，占据前者所占用的区域（进程在内存与磁盘之间的动态调度）
  • 问题：
    • 进程的哪些内容要交换到磁盘？会遇到什么困难？
    • 在磁盘的什么位置保存被换出的进程？
    • 交换时机？
    • 如何选择被换出的进程？
    • 如何处理进程空间增长？
  • 问题回答
    • 交换的是栈和堆，因为它们会被频繁的分配和释放。代码和静态数据相对稳定，不需要交换。
    • 交换到哪里？交换区 一块特殊的磁盘区域，包含连续的磁道。不经过文件系统，操作系统直接访问低层磁盘读写操作。
    • 何时交换？不用就换出，内存空间不够就换出
    • 不应换出等待IO状态的进程
• 虚拟存储技术 （virtual memory）： 现代操作系统采用的方式

虚拟存储技术（virtual memory） 是指：当进程运行时，先将其一部分装入内存，另一部分暂留在磁盘，当要执行的指令或访问的数据不在内存时，由操作系统自动完成将它们从磁盘调入内存的工作

• 虚拟地址空间 即为 分配给进程的虚拟内存
• 虚拟地址 是 在虚拟内存中指令或数据的位置，该位置可以被访问，仿佛它是内存的一部分

功能

• 虚存地址提供比物理内存空间大得多的地址空间（大小取决于CPU是多少位的）
• 存储保护
  • 确保每个进程都有独立的地址空间
  • 确保进程访问合法的地址范围
  • 确保进程的操作合法
  • 防止越界
  • 防止越权

虚拟页式存储管理系统

• 虚拟存储技术 + 页式存储管理方案
• 基本思想
  • 进程开始运行之前，不是装入全部页面，而是装入一个或零个页面
  • 之后，根据进程运行的需要，动态装入其他页面
  • 当内存空间已满，而又需要装入新的页面时，则根据某种算法置换内存中的某个页面，以便装入新的页面。具体有两种方式
    1. 请求调页（demand paging）（更常用），需要页面时掉入内存。
    2. 预先调页（prepaging），预测并提前掉入内存
• 本质上是以CPU时间和磁盘空间换取昂贵内存空间。

页表和页表项

• 页表由页表项组成
• 通常，页表项是硬件设计的
• 页框号、有效位、访问位、修改位、保护位
  • 页框号（内存块号、物理页面号、页帧号）
  • 有效位（驻留位、中断位）：表示该页是在内存还是在磁盘，0/1 型数据
  • 访问位：1表示正在被访问
  • 修改位：1表示被修改过，之后还会写会到磁盘
  • 保护位：读/可读写

页表也是存放在页中的，也需要多个页来存放，这些页也是不连续存放的，所以还需要一个“页目录”来表示页表存放在哪。

• 这就是“二级页表”
• 多级页表 是现代操作系统采用的技术。CORE I7 有4级页表。

实际实现中，还引入了反转（倒排）页表、Hash 值等

快表（TLB，Translation Look-aside Buffers）

• 为什么？引入页表后，一次访问带来了两次以上的内存访问。CPU指令速度比内存访问快得多，CPU不能被充分利用。
• 由于 程序访问的局部性规律，引入快表
• 快表存放在高速缓存（Cache），它是一种随机存储器，可以在一个存储周期内查找。
• 它还可以在一个存储周期内，按内容并行查找出来
• 快表可以是 64个/128个
• 快表也可以用多级缓存，设计多级快表

页错误

页错误（page fault，页面错误，页故障，页面实效）

• 定义：地址转换过程中产生的异常
• 具体原因：
  • 所访问的虚拟页面没有调入物理内存：缺页异常
  • 页面访问违反权限（读/写、用户/内核）
  • 错误的访问地址（地址指向了还没写入内容的区域）

缺页异常

• 是一种异常
• 操作系统执行 缺页异常处理程序：获得磁盘地址，启动磁盘，把页调入内存
  • 如果内存中有空闲页框，则分配一个页框，将新调入页装入，并修改页表中相应页表项的有效位及相应的页框号
  • 若内存中没有空闲页框，则要置换内存中某一页框；若该页框内容被修改过，则要将其写回磁盘

驻留集 ：实际在物理内存中的页面

• 驻留集大小：指的是给每个进程分配多少页框。
  • 太小会导致频繁的缺页异常
• 固定分配策略：进程创建时确定
  • 可以根据进程类型（交互、批处理、应用类）
  • 或者基于程序员或系统管理员的需要来确定
• 可变分配策略：根据缺页率评估进程局部性表现
  • 缺页率高→增加页框数
  • 缺页率低→减少页框数
  • 系统开销

置换问题

• 置换范围 计划置换页面的集合是局限在产生缺页中断的进程，还是所有进程的页框？
  • 局部置换策略：仅在产生本次缺页的进程的驻留集中选择
  • 全局置换策略：将内存中所有未锁定的页框都作为置换的候选
• 置换策略 在计划置换的页框集合中，选择换出哪一个页框？
  • 所有策略的目标：置换 “最近最不可能访问”的页
  • 由于 局部性原理，大多数策略都基于过去的行为来预测将来的行为
  • 置换策略设计得越精致实现的软硬件开销就越大
  • 不能置换被锁定的页框
• 页框锁定
  • 是什么？给每个页框增加一个锁定位，设置锁定位为 true 后，告诉操作系统，不要把此页面换出物理内存。
  • 为什么？虚存技术带来了开销，使进程运行时间变得不稳定
  • 锁定谁？操作系统核心代码、关键数据结构、IO缓冲区
  • Windows提供了 VirtualLock/VirtualUnLock 函数来控制
• 页框的收回：通过页面置换从驻留集中释放页框，将其归还到空闲页框池
  • 为什么？系统的理想的状态是，缺页异常时系统有大量空闲页框，而不是没有空闲页框不得不使用 页框置换
  • 怎么做？
    • 设计一个进程，叫做 分页守护进程（paging daemon），多数时间睡眠，定期唤醒以检查内存的状态
    • 如果空闲页框过少，分页守护进程通过预定的页面置换算法选择页面换出内存
    • 如果页面装入内存后被修改过，则将它们写回磁盘
• 页缓冲技术 （极大降低置换带来的代价）
  • 已被置换出的页仍然保留在物理内存中，一旦进程又要访问它，并且它还没被新的内容覆盖，将它从空闲页框集合中移出即可恢复该页面(代价很小)
  • 置换出的页放入两个表之一：
    1. 页面未被修改（干净页），放到空闲页链表中；
    2. 页面已被修改（脏页），放到修改页链表中
  • 脏页由后台进程定时、批量写回(而不是一次只写一个，大大减少I/O消耗)

置换算法

置换算法（决定淘汰哪个页面的算法）

• 最佳算法 （OPT），选择以后不再需要，或者最远的将来才会用到的页面
  • 无法实现
  • 作为一种标准（或概念）来衡量其它算法
• 先进先出算法 FIFO
  • 页面做成链表，来实现算法
  • 缺点：总是淘汰最早的页面，常驻进程性能会很低。
• 第二次机会算法 （SCR，Second Chance）
  • 在 FIFO 基础上改进
  • 页面被加载到物理内存时，设置一个访问位初始化为 R=0
  • 页面被访问后，设置 R=1
  • 置换时，如果 R=0，则置换它
  • 置换时，如果 R=1，则 R=0，并移动到队尾（给第二次机会）
  • 避免常驻进程被频繁置换。比LRU简单，无须维护复杂的访问时间记录。
• 时钟算法（Clock）
  • SCR 的一个性能优化，把链表改为环形链表（不用频繁移动到队尾了）
• 最近最少使用（LRU）
  • 评价指标接近 OPT
  • 缺点：开销较大
• 最近未使用（NRU，Not Recently Used）
  • LRU 的近似
  • 选择最近一段时间内未使用的一页，并置换出去
  • 硬件实现，设置访问位R，修改位M，初始化为0
  • 访问后设置 R=1，修改后设置 M=1
  • R位定期清零
  • 缺页异常时，检查R和M，有4类：1）R=0,M=0,2）R=0,M=1,3）R=1,M=0,4）R=1,M=1
  • 置换算法选择：编号最小的非空类中，随机选择一页置换
• 最不经常使用（NFU）
  • LRU 的近似
  • 选择访问次数最少的页面置换，指标接近LRU，开销小一些
  • 实现：每个页都有计数器，缺页异常时选择计数器最小的页置换
• 老化算法（Aging）
  • LRU 的近似，同时降低复杂度
  • 设定一个计数器 counter，它越大，说明最近访问越频繁。
  • counter 初始化为0
  • 系统以固定时间更新每个页面的计数器。每次更新，计数器右移一位（就是除以2，“变老”）
  • 如果被访问了，把最高位设置为1
  • 需要置换时，选择计数器最小的页面。对于计数器相同的情况，用 FIFO 或随机策略决定。

Belady现象：FIFO算法中，偶尔出现这种情况：物理内存大了，缺页异常反而变多。

工作集模型

影响性能的因素

• 页面置换算法
• 页面本身的大小
• 程序的编制方法
• 分配给进程的页框数量

颠簸（Thrashing，抖动）虚存中，页面在内存与磁盘之间频繁调度，使得调度页面所需的时间非常多，这样导致系统效率急剧下降

页面本身的大小 考虑因素：

• 内部碎片
• 页表长度
• 辅存的物理特性

程序编制方法。举例来说，如果每个页框可以放128个整数。我们要为128x128的矩阵赋值，下面两种写法，哪种缺页次数少呢？

// 写法1：缺页 128次
for(int i=0;i<128;i++){
    for(int j=0;j<128;j++){
        A[i][j]=0;
    }
}

// 写法2：缺页 128x128 次
for(int j=0;j<128;j++){
    for(int i=0;i<128;i++){
        A[i][j]=0;
    }
}

分配给进程的页框数量

• 反比例关系
• 找到一个平衡点
• 如何寻找平衡点，就是 工作集算法
• 1968年，Denning提出

工作集（Working Set）：一个进程当前正在使用的页框集合

• 定义为 $W(t,\Delta)$，是一个时间序列，t是时刻，$\Delta$ 是 1个单位时间（或者统计窗口长度），工作集就是 $(t-\Delta,t]$ 时间段内被访问的页面的集合。
• 算法：
  1. 页面置换：不在工作集内的页面被优先置换出去。
  2. 根据工作集的大小，动态改变分配的页框的数量。如果工作集变大，增加分配的页框数量；反之减少

相关技术

内存映射文件 虚拟存储时，并不是使用文件读写，而是通过一个系统调用（mmap）访问磁盘的一部分

• 缺页异常时才会读
• 进程退出，或者解除映射时，修改的页面写回文件

写时复制（Copy-On-Write）

• “前面Linux创建子进程” 的部分写了。
• 复制页面时，不实际复制，而是新建一个指针指向它，并设置为只读。尝试写入时，才会开辟一个物理地址，把新的内容写入进去，并让指针指向它

文件系统

文件：

• 是对磁盘的抽象。正如进程是对CPU的抽象，地址空间是对内存的抽象。
• 是一组带标识（标识即为文件名）的、在逻辑上有完整意义的信息项的序列
  • 信息项：基本单位（单个字节，或多个字节），各信息项之间具有顺序关系

如何设计一个文件系统—-需求分析

• 操作系统角度：怎样组织、管理文件？
  • 文件的描述、分类
  • 文件目录的实现
  • 存储空间的管理
  • 文件的物理地址
  • 磁盘实际运作方式(与设备管理的接口)
  • 文件系统性能
• 用户角度：文件系统如何呈现
  • 一个文件的组织
  • 如何命名？
  • 如何保护文件？
  • 可以实施的操作？

文件系统：操作系统中统一管理信息资源的一种软件，管理文件的存储、检索、更新，提供安全可靠的共享和保护手段，并且方便用户使用

• 统一管理磁盘空间，实施磁盘空间的分配与回收
• 实现文件的按名存取：名字空间->（映射到）-> 磁盘空间
• 实现文件信息的共享，并提供文件的保护、保密手段
• 向用户提供一个方便使用、易于维护的接口，并提供有关统计信息
• 提高性能
• 提供与I/O系统的统一接口

UNIX对文件的分类

• 普通文件。例如文本文件、二进制文件等
• 目录文件。用于管理文件和子目录，包含一些指向它们的指针
• 设备文件。设备抽象为文件
  • 字符设备文件：输入输出有关，用于模仿串行I/O设备，例如终端，打印机，网卡等
  • 块设备文件：磁盘
• 管道文件。用于进程间通信
• socket

文件逻辑结构

• 流式文件：一串字节
• 记录式文件：文件由若干个记录组成，可以按记录进行读、写、查找等操作，每条记录有其内部结构。

访问

• 顺序存取(访问)
• 随机存取(访问)，例如：UNIX的seek操作

磁盘访问

• 一次访问请求：读/写，磁盘地址（设备号、柱面号、磁头号、扇区号），内存地址（src/dst）
  • 柱面号 Cylinder：多个盘面上半径相同的多条磁道。对应的是磁头的移动。
• 完成过程由三个动作组成：
  • 寻道（时间）：磁头移动定位到指定磁道
  • 旋转延迟（时间）：等待指定扇区从磁头下旋转经过
  • 数据传输（时间）：数据在磁盘与内存之间的实际传输

磁盘空间管理

块号与磁盘地址的换算

• 块号->磁盘地址：
  • 柱面号=块号//(磁头数x扇区数)
  • 磁头号=(块号%(磁头数x扇区数))//扇区数
  • 扇区号=(块号%(磁头数x扇区数))%扇区数
• 磁盘地址->块号
  • 块号=柱面号x(磁头数x扇区数)+磁头号x扇区数+扇区号

管理空闲块的数据结构

• bitmap，0代表已分配，1代表空闲。
  • 申请物理块时，寻找1对应的位置
  • 归还时，把对应位置设置为1
• 空闲块表：所有空闲块记录在一个表中，主要内容两个：起始块号，块数
• 空闲块链表：把所有空闲块组成一个链
• 成组链接法：UNIX 使用的方法，图片在下面
  • 每n个（例如n=100）个空闲块划分为一组。每组的第一个记录了指向下一个的信息。
  • 分配空闲块的算法。如果需要的空闲块少，优先从组的底部分配；如果需要的多，第一组分配完后，分配第二组，以此类推。
  • 回收空闲块的算法。空闲块填充到当前组，直到数量达到n；数量到n之后新开一个链表节点

文件

文件控制块（File Control Block）为管理文件而设置的数据结构，保存管理文件所需的所有有关信息（文件属性或元数据）

• 常用属性：文件名，文件号，文件大小，文件地址，创建时间，最后修改时间，最后访问时间，保护，口令，创建者，当前拥有者，文件类型，共享计数，各种标志(只读、隐藏、系统、归档、ASCII/二进制、顺序/随机访问、临时文件、锁)
• 文件基本操作：Create、Delete、Open、Close、Read、Write、Append、Seek、Get Attributes、Set Attributes、Rename

文件目录

• 统一管理每个文件的元数据，以支持文件名到文件物理地址的转换
• 将所有文件的管理信息组织在一起，即构成文件目录
• 目录文件：文件目录也是以文件的形式存放在磁盘上的
• 目录项：构成文件目录的基本单元，FCB
• 相关概念：
  • 路径名（文件名）、绝对路径名、相对路径名
  • 当前目录/工作目录
  • 目录操作：创建目录、删除目录、读目录、写目录、改名、复制

文件的物理结构

• 连续结构
• 链表结构
• 索引结构

文件连续结构：文件连续地存放在物理块中

• FCB 中存放：块首的块号、块数
• 优点
  • 简单
  • 支持顺序存取和随机存取
  • 所需的磁盘寻道次数和寻道时间最少
  • 可以同时读入多个块，检索一个块也很容易
• 缺点
  • 文件不能动态增长。预留空间（浪费） 或 重新分配并移动
  • 不利于文件插入和删除
  • 外部碎片：紧缩技术

文件链表结构

• 对于每个文件，都用一个链表把所有的块管理起来
• FCB中存放：链表首个节点
• 优点
  • 提高了磁盘空间利用率，不存在外部碎片问题
  • 有利于文件插入和删除
  • 有利于文件动态扩充
• 缺点
  • 存取速度慢，不适于随机存取。需要遍历链表
  • 可靠性问题，如指针出错
  • 更多的寻道次数和寻道时间。因为同一个文件的物理块是不连续的分布在整个磁盘上的
  • 链接指针占用一定的空间。一个扇区（例如512字节），还要拿出一些空间来存放指针，这还导致每个块的实际数据量不为整数
• 链表结构的变形：FAT

FAT（文件分配表, File Allocation Table）基于链表结构，不用一个实际的链表来管理，而是是用一个 array 来表示 多个文件 对应的链表

• array 的 index 对应的就是块号，有多少个块 array 就有多长
• 值有三种：
  • 0 表示为空闲块
  • -1 表示最后一个块
  • 其它数字：下一块块号的索引
• 起始块号还是记录在 FCB 中的

索引结构

• 一个文件的信息存放在若干不连续物理块中
• 系统为每个文件建立一个专用数据结构—索引表，并将这些物理块的块号存放在该索引表中
• 索引表就是磁盘块地址数组，其中第i个条目指向文件的第i块
• 索引表存放在何处？存放在一个磁盘块中。它的大小取决于文件的大小。
• FCB 中记录索引表的位置。
• 优点:保持了链接结构的优点，又解决了其缺点
  • 既能顺序存取，又能随机存取
  • 满足了文件动态增长、插入删除的要求
  • 能充分利用磁盘空间
• 缺点
  • 较多的寻道次数和寻道时间
  • 索引表本身带来了系统开销（内存、磁盘空间，存取时间）

问题：使用索引结构时，文件太大（需要的块也就很多），索引表也就很大，索引表无法放入到单个块中，如何解决？

• 多级索引。上一级索引表存放次级索引表对应的块地址。
• 综合模式。上一级索引表既可以存放次级索引表对应的块地址，也可以存放文件内容对应的块地址。

UNIX 采用综合模式，最多3个级别的索引

• 每个文件的索引表有15个索引项，每项2个字节
• 前12项直接存放文件的物理块号（直接寻址）
• 如果文件大于12块，则利用第13项指向一个物理块，在该块中存放文件物理块的块号（一级索引表）
  • 假设扇区大小为512字节，物理块等于扇区块大小，一级索引表可以存放256个物理块号
• 如果文件更大，利用第14项指向一个二级索引表
• 如果文件更大，利用第15项指向三级索引表
• 文件最多多大？$12+256+256^2+256^3$ 个块

文件系统

需要考虑：磁盘上 与 内存中 的 内容布局

• 磁盘上
  • 如何启动操作系统？
  • 磁盘是怎样管理的？怎样获取磁盘的有关信息？
  • 目录文件在磁盘上怎么存放？普通文件在磁盘上怎么存放？
• 内存中
• 当进程使用文件时，操作系统是如何支持的？
• 文件系统的内存数据结构

相关概念

• 磁盘分区(partition)：把一个物理磁盘的存储空间划分为几个相互独立的部分，称为分区
• 文件卷(volume)：磁盘上的逻辑分区，由一个或多个物理块(簇)组成
  • 一个文件卷可以是整个磁盘 或 部分磁盘 或 跨盘（RAID）
  • 同一个文件卷中使用同一份管理数据进行文件分配和磁盘空闲空间管理，不同的文件卷中的管理数据是相互独立的
  • 一个文件卷上：包括文件系统信息、一组文件（用户文件、目录文件）、未分配空间
• 块（Block）或 簇（Cluster） ： 一个或多个（2的幂）连续的扇区，可寻址数据块
• 格式化(format)：在一个文件卷上建立文件系统，即建立并初始化用于文件分配和磁盘空闲空间管理的管理数据

磁盘上的内容

• 引导区
  • 包括了从该卷引导操作系统所需要的信息
  • 每个卷（分区）一个，通常为第一个扇区
• 卷（分区）信息
  • 包括该卷（分区）的块（簇）数、块（簇）大小、空闲块（簇）数量和指针、空闲FCB数量和指针……
• 目录文件(根目录文件及其他目录文件)
• 用户文件

UNIX 文件系统

访问一个文件的两个步骤

• 用户提供的文件名->目录+文件名
• 根据 目录项/FCB，计算磁盘物理地址

目录项分解 为了提高性能，FCB 分为两块存储。访问相关的信息占用的块更少，访问文件时的访盘次数就更少。

1. 文件名、文件号。
2. 文件号、其它信息

FAT

• 簇大小：1、2、4、8、16、32或64扇区
• 文件系统的数据记录在“引导扇区”中
• FAT表项：2字节
• 目录项：32字节
• 根目录大小、位置固定
• 根据表项长度不同，分为，FAT12、FAT16、FAT32

文件系统的性能

文件可靠性：抵御各种物理破坏和人为破坏

• 坏块：用一个特殊文件，把坏块占用起来
• 备份（转储）
  • 全量备份、增量备份
  • 物理转储（从磁盘第0块开始，转储所有磁盘块）、逻辑转储（从若干目录开始，递归转储文件和目录）

文件系统一致性：如果写回磁盘前系统崩溃，则会出现文件系统不一致（指的是meta不一致）。

• 系统再次启动时，运行某个检查程序，检查磁盘块和目录系统
• 检查程序做了什么？（UNIX为例）：
• 建立两张表（array）：1）遍历所有文件，记录每个块在文件中出现次数 2）每个块在“空闲块表”中出现的次数。共有4种结果：
  1. 两个表的记录一致，证明没有问题。
  2. 某个磁盘块，既不在使用表中，也不再空闲表中。认为它丢失了。处理：把它放入到空闲表中
  3. 某个磁盘块，在空闲表中出现了两次。处理：把它变成1。
  4. 某个磁盘块，在使用表中出现两次。处理：在空闲表中找到个区域，把内容复制过去，然后把其中一个文件指向它。

文件写入策略：考虑文件系统一致性和速度

• 通写（write-through）内存中的修改立即写到磁盘
  • 缺点：速度性能差
  • 例： FAT文件系统
• 延迟写（lazy-write）
  • 利用回写（write back）缓存的方法得到高速
  • 可恢复性差
• 可恢复写（transaction log）采用事务日志来实现文件系统的写入
  • 既考虑安全性，又考虑速度性能
  • 例：NTFS

文件系统的安全性

• 对拥有权限的用户，允许其进行相应操作，否则禁止
• 防止其他用户冒充对文件进行操作
• 两种实现
  • 访问控制表：每个文件一个，上面记录了用户ID和权限
  • 权限表：每个用户一个，记录文件名和权限

文件系统的性能

• 磁盘速度是性能的主要瓶颈
• 文件系统尽可能要减少磁盘访盘次数
• 提高性能的手段
  • FCB分解
  • 当前目录、磁盘碎片整理、块高速缓存、磁盘调度、提前读取、合理分配磁盘空间、信息的优化分布、RAID技术

块高速缓存 （Block Cache、文件缓存、磁盘高速缓存、缓冲区高速缓存）

• 在内存中为磁盘块设置一个缓冲区，保存磁盘中某些块的副本
• 利用了访问的局部性原理。最近访问的块，未来很可能再次访问
• 访问文件时：检查是否在“块高速缓存”，如果在则直接从“块高速缓存”读入；否则先读入到“块高速缓存”，再从“块高速缓存”读入
• 写入文件时：也是写入到“块高速缓存”，之后操作系统控制写回到磁盘
• “块高速缓存”的实现：对块号做 HashTable，这样访问就会快
• 置换策略：块高速缓存满了以后把哪些部分释放掉？LRU等算法。
• 写回（write-back）策略：
  • 有修改立即写回
  • 定时写回，（Windows 采用每1秒写回一次的做法）

提前读取：每次访问磁盘，把之后的磁盘块也读入进去

合理分配磁盘空间

• 优先把数据分配到同一个柱面上，从而减少磁盘臂的移动次数
• 柱面是所有盘片上同一位置的集合
• 因为 磁盘臂的移动速度远远低于数据传输速度

磁盘调度 有多个访盘请求等待时，采用一定的策略，对这些请求的服务顺序调整安排

• 降低平均磁盘服务时间，达到公平、高效
• 一次访盘时间 = 寻道时间+旋转延迟时间+传输时间

磁盘调度算法

• 先来先服务 （FCFS）
  • 简单、公平
  • 效率低，磁头反复移动机械损耗大
• 最短寻道时间优先(Shortest Seek Time First)
  • 谁距离磁头距离最近优先服务谁
  • 缺点：饥饿现象，如果一直有新的请求到来，较远的访问请求长期无法响应
• 扫描算法（SCAN，电梯算法）
  • 磁头有一个当前方向，它只向一个方向移动，直到此方向上没有请求。然后向相反方向继续扫描
• 单项扫描算法
  • 扫描算法的改进。
  • 总是从0号柱面开始扫描
  • 扫描到尾部后，立即回到0号柱面，开始下一次扫描
• N-step-SCAN策略
  • 把磁盘请求分为长度为 N 的几个子队列
  • 每次用 SCAN 处理一个子队列
  • N 较大时接近SCAN，N=1时就是 FCFS
  • 解决了饥饿问题
• FSCAN策略
  • 两个子队列
  • 处理一个队列时，所有新到的请求都放入另一个队列中
  • 两个队列轮换处理
• 旋转调度算法
  • 根据延迟时间来决定执行次序的调度
  • 三种情况：
    • 若干等待访问者请求访问同一磁头上的不同扇区
    • 若干等待访问者请求访问不同磁头上的不同编号的扇区
    • 若干等待访问者请求访问不同磁头上具有相同的扇区
  • 前两种用 FCFS
  • 第三种情况，任选一个读写磁头。不同磁头相同扇区不能同时读，只能等待其旋转一周后再读入。

信息优化分布

• 如果处理信息不需要时间，那么文件写入到连续的扇区性能最高
• 但是考虑到处理信息的延迟，如果写入到连续扇区，那么读入时，可能每次都要多转一圈。

例子：处理程序要求顺序处理8个记录；磁盘旋转一周为20毫秒/周；花5毫秒对记录进行处理

记录的成组与分解

• 成组：假如某些记录总是需要同时读入，那么把它们放到不同的块里（各自还没放满），那么性能就会下降。可以把它们放到同一个块里，减少读块的次数，就能提高性能。
• 分解：假如某个大文件，总是只访问其中某些区域，那么都读入就很浪费，可以分解为若干小文件。
• 目录文件就采用了这个思路

RAID（独立磁盘冗余阵列，Redundant Arrays of Independent Disks）

• 多块磁盘按照一定要求构成一个独立的存储设备
• 目标：提高 可靠性 和 性能
• 考虑：磁盘存储系统 的 速度、容量、容错、数据灾难发生后的数据恢复
• 通过把多个磁盘组织在一起，作为一个逻辑卷提供磁盘跨越功能
• 通过把数据分成多个数据块，并行 写入/读出多个磁盘，以提高数据传输率（数据分条stripe）
• 通过镜像或校验操作，提供容错能力（冗余）
• RAID0
  • 数据分布在阵列的所有磁盘上
  • 有数据请求时，同时多个磁盘并行操作
  • 充分利用总线带宽，数据吞吐率提高，驱动器负载均衡
  • 无冗余。无容错能力。
• RAID1
  • 最大限度保证数据安全及可恢复性
  • 所有数据同时存在于两块磁盘的相同位置
  • 磁盘利用率50%
• RAID4
  • block 级划分 + 校验盘
• 其它
  • RAID2，bit 级划分 + Hamming码
  • RAID3，Byte 级划分 + 专用校验盘
  • RAID5，互为校验盘，防止校验盘磨损更多

IO

IO的特点

• I/O性能经常成为系统性能的瓶颈
• I/O的特点（资源多、杂，并发）是操作系统庞大复杂的原因之一
  • 速度差异很大
  • 应用方法各异
  • 控制接口的复杂性
  • 传送单位不一样
  • 数据表示不一样，例如不同厂商的打印机换行符号不一样
  • 错误条件
• 与其他功能联系密切，特别是文件系统

按数据组织分类

• 块设备
  • 以数据块为单位存储、传输信息
  • 传输速率较高、可寻址（随机读写）
• 字符设备
  • 以字符为单位存储、传输信息
  • 传输速率低、不可寻址

按照资源分配角度分类

• 独占设备。在一段时间内只能有一个进程使用的设备，一般为低速I/O设备（如打印机，磁带等）
• 共享设备。在一段时间内可有多个进程共同使用的设备，多个进程以交叉的方式来使用设备，其资源利用率高（如硬盘）
• 虚设备。在一类设备上模拟另一类设备，常用共享设备模拟独占设备，用高速设备模拟低速设备，被模拟的设备称为虚设备
  • 目的：将慢速的独占设备改造成多个用户可共享的设备，提高设备的利用率

IO管理的目标和任务

1. 按照用户的请求，控制设备的各种操作，完成I/O设备与内存之间的数据交换，最终完成用户的I/O请求
   • 设备分配与回收
   • 记录设备的状态
   • 根据用户的请求和设备的类型，采用一定的分配算法，选择一条数据通路
   • 执行设备驱动程序，实现真正的I/O操作
   • 设备中断处理：处理外部设备的中断
   • 缓冲区管理：管理I/O缓冲区
2. 方便、统一的独立于设备的接口
   • 方便性：向用户提供使用外部设备的方便接口，使用户编程时不考虑设备的复杂物理特性
   • 统一性：对不同的设备采取统一的操作方式，即在用户程序中使用的是逻辑设备
     • 逻辑设备与物理设备
     • 屏蔽硬件细节（设备的物理特性、错误处理、不同I/O过程的差异性）
3. 充分利用各种技术（通道，中断，缓冲，异步I/O等）提高CPU与设备、设备与设备之间的并行工作能力，充分利用资源，提高资源利用率
   • 并行性
   • 均衡性（使设备充分忙碌）
4. 保护
   • 设备传送或管理的数据应该是安全的、不被破坏的、保密的

IO 设备的组成，两个部分：

1. 机械部分 是设备本身（物理装置）
2. 电子部分 (设备控制器，适配器)
   • （端口）地址译码
   • 按照约定的格式和过程接受计算机发来的数据和控制信号 或 向主机发送数据和状态信号
   • 将计算机的数字信号转换成机械部分能识别的模拟信号，或反之
   • 实现设备内部硬件缓冲、数据加工等提高性能或增强功能

I/O端口地址

• 接口电路中每个寄存器具有的、唯一的地址，是个整数
• 所有I/O端口地址形成I/O端口空间(受到保护)
• 编址方式有两种：
  1. I/O独立编址 分配端口空间完全独立，与内存地址空间无关。使用专门的IO指令对端口操作
     • 优点：外设不占用内存空间；编程时，易于区分是内存操作还是端口操作
     • 缺点：I/O端口指令少，不灵活
     • 例子：8086/8088，分配给I/O端口64K，0000H 到 0FFFFH，指令只有 in 和 out
  2. I/O映射编址 分配端口空间与内存的地址空间一起编址，把I/O端口看成一个存储单元，对I/O的读写等同于对内存的读写
     • 优点：
       • 用内存操作指令对I/O端口操作，不再需要专门的I/O指令
       • I/O端口空间可以很大
     • 缺点：占用内存空间

I/O控制的方式

1. 可编程I/O（轮询/查询）。CPU给I/O模块发命令后，进程进入忙等待，不断查询设备是否操作完成。
2. 中断
3. DMA（直接存储器访问）

IO软件的层次

1. 用户级IO软件
   • 用户进程层执行输入输出系统调用，对I/O数据进行格式化，为假脱机输入/输出作准备
2. 与设备无关的OS软件
   • 独立于设备的软件实现设备的命名、设备的保护、成块处理、缓冲技术和设备分配
     • 驱动程序的统一接口
     • 缓冲
     • 错误报告
     • 分配与释放设备
     • 提供与设备无关的块大小
3. 设备驱动程序
   • 设置设备寄存器、检查设备的执行状态
4. 中断处理程序
   • 负责I/O完成时，唤醒设备驱动程序进程，
5. 硬件
   • 实现物理I/O的操作

缓冲技术

• 操作系统中最早引入的技术
• 解决CPU与I/O设备之间速度的不匹配问题
• 凡是数据到达和离去速度不匹配的地方均可采用缓冲技术
• 实现：
  • 硬件实现：设备中有缓冲区
  • 软件实现：内存中开辟空间作为缓冲区

UNIX 的缓冲技术

• 缓冲池技术
• 提前读、延迟写技术
• 充分利用之前的读入，虽已传入用户区，单仍在缓冲区的数据
• 空闲缓冲区队列（av链）、设备缓冲队列（b链）

UNIX 的缓冲算法

• 进程想读入时，先从b链查找。
  • 如果找到，将其标记为“忙”，然后从av队列取下，然后完成缓冲区向内存的传输
  • 如果在b链中未找到，则从av队首pop一个缓冲区，然后请求IO，从b链取下插入新的
• 数据读入缓冲区后，缓冲区从IO请求队列取下；完成缓冲区到内存的传送后，放入av链的队尾。随着系统运行它会慢慢到队首，之后的IO中重复使用
• 实际上是近似 LRU 算法

设备驱动程序的一种典型实现：IO进程

• 专门处理系统中的I/O请求和I/O中断工作
• IO请求
  • 用户程序：调用send把IO请求发送给IO进程；调用block阻塞自己；
  • 系统：用wakeup唤醒IO进程，完成IO任务
• IO中断
  • 内核：发送消息给IO进程，由IO进程判断和处理 中断
• IO进程
  • 是系统进程，由最高优先级
  • 进入运行态时候，先关闭中断，然后用 receive 接收消息
    • 如果没有消息，则打开中断，然后阻塞自己
    • 如果有消息，判断类型（IO请求还是IO中断），并做相应的处理

IO性能问题

入手点：

• 使CPU利用率仅可能不被IO降低
• 使CPU仅可能摆脱IO

技术：

• 减少速度差距：缓冲技术
• 使CPU不等待IO：异步IO
  • 异步IO：启动一个IO操作后，IO的执行的同时CPU继续处理其它代码
  • 同步IO：应用程序阻塞直到IO操作完成
  • Windows提供了 异步IO 和 同步IO
• 让CPU摆脱IO：DMA、通道

死锁

定义：一组进程中，每个进程都无限等待被另一进程所占有的资源，因而永远无法得到的资源，这种现象称为进程死锁，这一组进程就称为死锁进程

如果死锁发生，会浪费大量系统资源，甚至导致系统崩溃

例子1。D是磁盘上的某个文件，T是磁带机，有两个进程：

如果进程P锁定了D，恰好进程Q锁定了T，那么两个进程锁死

如果进程P1申请了80kb，恰好进程P2申请了70kb，那么两个进程锁死

与死锁不同的别的概念

• 活锁：与死锁的区别是，活锁一直在轮询状态，会轮番上CPU
• 饥饿：资源分配算法有问题，使某些进程永远轮不到CPU

死锁产生的必要条件（4个，任意一个不成立就不会发生死锁）

1. 资源独占：一个资源每次只能给一个进程使用
2. 占有且等待：进程在申请新的资源的同时保持对原有资源的占有
3. 不可抢占：资源申请者不能强行的从资源占有者手中夺取资源，只能等待占有者主动释放
4. 等待环路：一组进程的等待关系，形成了一个环路

资源分配图（RAG，Resource Allocation Graph）

• 节点。两种：资源或进程
• 边。两种：资源->进程，这是分配边。进程->资源，这是申请边

定理：如果每个资源类只包含一个资源示例，那么环路是死锁的充分必要条件

解决死锁

• 不考虑死锁问题：鸵鸟
• 死锁预防：静态策略，设计合适的资源分配算法，不让死锁发生
• 死锁避免：动态策略：以死锁不发生为目标，跟踪并评估资源分配过程，根据评估结果决策是否分配
• 允许死锁发生，然后死锁检测与解除

死锁预防：思路是破坏死锁的4个条件之一

1. 资源独占
   • 资源转换技术：把独占资源变为共享资源
   • SPOOLing技术。例如，解决不允许任何进程直接占有打印机的问题。设计一个“守护进程/线程”负责管理打印机，进程需要打印时，将请求发给该daemon，由它完成打印任务
2. 占有且等待
   • 要求每个进程运行前必须一次性申请所有需要的资源。系统在所有资源都满足的时候才一次性分配。性能低、饥饿现象。
   • 一个进程在申请新的资源不能立即得到满足而变为等待状态之前，必须主动释放已占有的全部资源，若需要再重新申请。饥饿现象。
3. 不可抢占
   • 允许某个进程通过操作系统抢占资源
   • 局限性：仅适用于状态易于保存和恢复的资源。如CPU、内存。
4. 等待环路。定义资源类型的线性顺序。
   • 系统的所有资源编号。进程申请资源时，必须严格按照资源编号顺序进行，否则操作系统不予分配。
   • 经常用的资源编号小，不经常用的编号大
   • 可以证明 这种做法不会产生死锁

死锁避免 进程每次资源申请，都做动态检查，根据检查结果决定是否分配资源

• 定义 安全状态：系统内有一系列进程，对于任何一个进程，它之后所需的资源量都不超过当前空闲资源总和。
• 安全状态下一定没有死锁
• 死锁避免的思路就是使其一直处于安全状态
• 银行家算法（Banker's Algorithm），Dijkstra 在1965年提出，是仿照银行发放贷款时的控制方式而设计的算法。
  • 银行客户不会一次性把所有额度借走，而是按需借走。因此所有客户的额度之和可能超过银行资金。
  • 银行家算法的使用条件
    1. 进程数量固定，资源数量固定
    2. 每个进程预先指定所需的最大资源数量
    3. 进程不能申请比系统中可用资源总数还多的资源
    4. 进程等待资源的时间是有限的
    5. 如果系统满足了进程对资源的最大需求，那么，进程应该在有限的时间内使用资源，然后归还给 系

银行家算法

变量定义

n: 进程数量
m: 资源数量

Available: ARRAY[1..m] of integer; 每类资源的数量
Max: ARRAY[1..n,1..m] of integer; 每个进程队每个资源的最大需求量
Allocation: ARRAY[1..n,1..m] of integer; 当前每个进程已分配的资源数量
Need: ARRAY[1..n,1..m] of integer; 当前每个进程还需要多少资源
Request: ARRAY[1..n,1..m] of integer; 当前的申请量

算法：

当进程 Pi 申请资源时，执行：

1. 如果 Request[i]<=Need[i] 转到2，否则报错返回
2. 如果 Request[i]<=Available 转到3，否则进程等待
3. 假设系统分配了资源，那么状态变为：

   Available=Available-Request[i];
   Allocation[i]=Allocation[i]+Request[i];
   Need[i]=Need[i]-Request[i];
   

   判断这个状态是否安全。如果安全则分配资源；如果不安全，则不分配资源，恢复为原来的状态，进程进入等待态

如何判断是否处于安全状态：

//1. 定义数据结构
Work=Available; // 当前可用资源数量
Finish=false

// 2. 寻找满足条件的 i
Finish[i]==false // 这个进程还没检查过
and Need[i]≤Work // 剩余资源可以满足 i 
// 如果不存在，则转到4；如果存在，转到3

// 3. 分配资源
Work = Work + Allocation[i];
Finish[i] = true;
// 然后转到2 

// 4. 若对所有i，Finish[i]==true，
则系统处于安全状态，否则系
统处于不安全状态

死锁的检测和解除

1. 允许死锁发生，但是操作系统会不断监视并判断死锁是否真的发生
   • 检测时机
     • 进程由于资源不足等待时检测（开销大）
     • 定时检测
     • 系统资源利用率下降时检测
   • 检测算法：判断是否有环路
2. 一旦死锁发生则采取专门的措施，解除死锁并以最小的代价恢复操作系统运行
   • 撤销所有死锁进程。代价大
   • 进程回退（Roll back）再启动。代价大
   • 按照某个原则逐一撤销进程
   • 按照某个原则逐一抢占资源

哲学家就餐问题

• 有五个哲学家围坐在一圆桌旁，桌中央有一盘通心粉，每人面前有一只空盘子，每两人之间放一只筷子
• 每个哲学家的行为是思考，感到饥饿，然后吃通心粉
• 为了吃通心粉，每个哲学家必须拿到两只筷子，并且每个人 只能直接从自己的左边或右边去取筷子（筷子的互斥使用、不能出现死锁现象）

几种方法

1. （会死锁）把筷子当作信号量处理。如果都拿左边的筷子，就会死锁
2. 最多允许4个哲学家同时坐在桌子周围
3. 近当一个哲学家两边的筷子都可用时，才允许其拿筷子。管程。
4. 给所有哲学家编号，奇数号的哲学家必须首先拿左边的筷子，偶数号的哲学家则反之
5. …

参考资料

写本文时，画了一些图片素材：操作系统.pptx

Coursera课程：《操作系统原理》，北京大学，陈向群

• 课件pdf

说明：本文中的代码均为伪代码。