进程管理 | OS

进程与线程

进程的概念和特征

程序顺序执行的特征
1. 顺序性
  
  严格按序
2. 封闭性
  
  程序一旦开始运行，其结果不受外界因素影响
  
  程序运行时独占各种资源，这些资源的状态（除初始状态外）只有本程序才能改变
3. 可再现性
  
  只要初始条件和执行环境相同
程序并发执行的特征
1. 间断
  
  程序间相互制约关系导致走走停停
2. 失去封闭性
  
  资源是共享的
3. 不可再现性
  
  失去封闭性导致的
引入进程的目的

更好地使多道程序并发执行，提高资源利用率和系统吞吐量，实现操作系统最基本的两个特性（并发性和共享性）
进程概念 —— “动态的” “过程性的”

程序的一次执行过程

一个程序及其数据在处理机上顺序执行时所发生的活动

具有独立功能的程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位
进程映像/进程实体（组成）
1. 程序段
2. 相关数据段
  
  原始数据、中间数据、结果数据
3. 进程控制块 PCB (Process Control Block)
  
  进程存在的唯一标志
  
  常驻内存，系统通过控制 PCB 来控制进程
  
  当进程被创建时，系统为它申请和构造一个相应的 PCB
  
  撤销进程，实际上是撤销进程的 PCB
  
  进程映像是静态的，进程是进程实体的运行过程
进程特征
1. 动态性（最基本特征）
  
  具有一定的生命周期，是动态地产生、变化和消亡的
2. 并发性
  
  多个进程实体同时存于内存中，能在一段时间内同时运行
  
  引入进程的目的就是使程序能与其他程序并发执行，以提高资源利用率
3. 独立性
  
  可独立调度和分派的基本单位（未引入线程的传统操作系统）
  
  系统进行资源分配的基本单位（根据 PCB）
4. 异步性
  
  由于进程的相互制约，使得进程具有执行的间断性
  
  进程以各自独立的、不可预知的速度向前推进
  
  为使进程在并发运行时虽具有异步性，但仍能保证执行结果是可再现的，操作系统配置了相应的进程同步机制
5. 结构性
  
  进程实体/进程映像(静态) = 程序段 + 数据段 + 进程控制块 PCB
进程 vs 程序
1. 进程动态，程序静态。进程是程序的执行，程序是有序代码的集合
2. 进程暂时，程序永久
3. 组成不同
4. 通过多次执行，一个程序可以产生多个不同的进程
  
  通过调用关系，一个进程可以执行多个程序
  
  进程可创建其他进程，而程序不能形成新的程序
5. 进程具有并行特性（独立性、异步性），程序没有

进程的状态与转换

基本状态
1. 就绪态
  
  进程获得了除处理机外的一切所需资源
  
  就绪队列：处于就绪态的进程可能有多个
  
  单处理机中所有进程不可能都处于就绪态（有一个在运行）
2. 运行态
  
  进程正在处理机上运行
  
  单处理机每个时刻只有一个进程处于运行态
3. 阻塞态/等待态
  
  进程正在等待某一事件（不包括等待处理机为可用）而暂停运行
  
  同样存在阻塞队列

就绪态可视为特殊的阻塞态，处于就绪态的进程缺少且仅缺少处理机这一资源

“资源”可以理解为：可以使用某设备、让其提供服务的“时间”

创建态和结束态
1. 创建态
  
  进程正在被创建：包括但不限于申请空白 PCB、向 PCB 填写用于控制和管理进程的信息、分配运行时所必需的资源
2. 结束态
  
  进程正从系统消失
  
  系统先将进程置为结束态，然后进一步处理资源释放和回收等工作
五种状态的转换

就绪态 → 运行态：被动，进程被调度，获得处理机资源

运行态 → 阻塞态：主动，进程请求某一资源的使用和分配或等待某一事件的发生时

阻塞态 → 就绪态：被动，需要其他相关进程的协助

运行态 → 就绪态：时间片到（主动）；被剥夺（被动）
挂起态

将暂时不能运行的进程调至外存等待，此时进程的状态称为挂起态

进程控制

创建

创建形式 —— 父进程创建子进程

子进程可以继承父进程所拥有的资源。父进程可与子进程共享一部分资源，但不能共享虚拟地址空间

子进程被撤销，归还资源给父进程/操作系统；父进程被撤销，其所有的子进程被撤销

进程图/树

(Linux) 0 号进程，由系统创建的第一个进程
唯一一个没有通过 fork 或者 kernel_thread 产生的进程
其拥有的所有信息和资源都是“手工设置”，不是复制的

引起进程创建的典型事件
1. 终端用户登录系统
2. 作业调度
3. 系统提供服务
4. 用户程序的应用请求
  
  前三种都是系统内核为用户创建一个新进程
创建过程（创建原语 create）
1. 分配一个唯一的进程标识符，并申请一个空白的 PCB
  
  PCB 有限，申请失败则创建失败
2. 分配运行时所需资源
  
  包括各种物理和逻辑资源，如内存、文件、I/O 设备和 CPU 时间等
  
  资源来源：操作系统、父进程
  
  资源不足则继续处于创建态，等待资源
3. 初始化 PCB
  
  初始化标识信息：标识符和父进程标识符
  
  初始化处理机状态信息：PC
  
  初始化处理机控制信息：设置进程状态为就绪态/静止就绪态
  
  设置优先级（默认最低）
4. 若进程就绪队列能够接纳新进程，则将新进程插入就绪队列

终止

引起进程终止的主要事件
1. 正常结束
2. 异常结束
  
  发生某种异常（如终止异常、不可恢复的故障异常）使程序无法继续运行，如存储区越界、保护错、非法指令、特权指令错、运行超时、算术运算错、I/O 故障等
3. 外界干预
  
  操作员或操作系统干预、父进程请求、父进程终止
终止过程（终止原语）
1. 根据标识符检索 PCB，读出该进程状态
2. 若为运行态，则立即终止，将处理机资源分配给其他进程
3. 终止所有子孙进程（若有），以防它们成为不可控的进程
4. 归还拥有的全部资源给父进程/操作系统
5. 将该 PCB 从所在队列（或链表）删除

阻塞和唤醒

阻塞的引发

正在执行的进程，由于期待的某些事件未发生，如请求系统资源失败、等待某种操作的完成、新数据尚未到达或无新任务可做等，进程便主动调用阻塞原语，使自己由运行态变为阻塞态
阻塞过程（阻塞原语 block）
1. 根据标识符找到 PCB
2. 若为运行态，则保护其现场，状态转为阻塞，停止运行
3. 把该 PCB 插入相应事件的等待队列
4. 转调度程序进行重新调度，将处理机分配给另一就绪进程，并进行切换（保留被阻塞进程的处理机状态，按新进程的 PCB 中的处理机状态设置 CPU 的环境）
唤醒的引发

当被阻塞进程所期待的事件发生时
唤醒过程（唤醒原语 wakeup）—— 由事件有关进程调用
1. 在该事件的等待队列中找到相应进程的 PCB
2. 将其移出等待队列，状态置为就绪
3. 把该 PCB 插入就绪队列

block 原语和 wakeup 原语作用相反，必须成对使用（即若在某进程中调用了阻塞原语，则必须在与之相合作的或其他相关的进程中安排一条相应的唤醒原语），否则阻塞进程将永久阻塞，再无机会运行

进程创建、撤销以及要求由系统设备完成的 I/O 操作都是利用系统调用而进入内核，再由内核中相应处理程序予以完成；进程切换同样是在内核的支持下实现的，因此可以说，任何进程都是在操作系统内核的支持下运行的，是与内核紧密相关的

进程的组成

进程控制块 PCB

由操作系统在进程创建时新建，之后常驻内存，任一时刻可以存取，在进程结束时删除

进程实体的一部分；进程存在的唯一标志

主要内容
常用组织方式
1. 线性方式
  
  可以理解为数组，适合进程数目不多的系统
2. 链接方式
  
  同一状态的 PCB 链接成一个队列，队内通常按优先级高低进行排列
  
  阻塞态 PCB 可根据阻塞原因排成多个阻塞队列
3. 索引方式
  
  将同一状态的进程组织在一个索引表中，索引表的表项指向相应的 PCB，不同状态对应不同的索引表

当操作系统欲调度某进程运行时，要从该进程的 PCB 中查出其现行状态及优先级；
在调度到某进程后, 要根据其 PCB 中所保存的处理机状态信息，设置该进程恢复运行的现场，并根据其 PCB 中的程序和数据的内存始址，找到其程序和数据；
进程在运行过程中，当需要和与之合作的进程实现同步、通信或访问文件时，也需要访问 PCB；
当进程由于某种原因而暂停运行时，又需将其断点的处理机环境保存在 PCB 中
可见，在进程的整个生命期中，系统总是通过 PCB 对进程进行控制，亦即系统唯有通过进程的 PCB 才能感知到该进程的存在

程序段

程序可被多个进程共享，即多个进程运行同一个程序

数据段

可以是进程对应的程序加工处理的原始数据，也可以是程序执行时产生的中间或最终结果

进程间通信 IPC

进程间通信 IPC (InterProcess Communication) 是指进程之间的信息交换

进程互斥与同步需要在进程间交换一定的信息，这只能称为低级进程通信。以信号量机制为例，之所以低级是在于：

效率低。生产者每次只能向缓冲池投放一个产品（消息），消费者每次只能从缓冲区取得一个消息
通信对用户不透明。OS 只为进程之间的通信提供了共享存储器，而关于进程之间通信所需之共享数据结构的设置、数据的传送、进程的互斥和同步，都必须由程序员去实现

高级通信方式是指以较高的效率传输大量数据且使用方便的通信方式。主要有以下三类：

共享存储

通信进程间存在一块可直接访问的共享空间，通过对这片共享空间进行读写实现信息交换

对共享空间进行读写操作时需使用同步互斥工具（如 PV 操作）

操作系统只负责为通信进程提供可共享使用的存储空间和同步互斥工具，而数据交换则由用户自己安排读/写指令完成

共享存储又分为两种：

低级共享：基于数据结构的共享

通信效率低下，仅适于传递相对少量的数据，属于低级通信
高级共享：基于存储区的共享

OS 在内存中划出一块共享存储区，数据的形式、存放位置甚至访问控制都是由进程负责，而不是 OS

注意，用户进程空间一般都是独立的，进程运行期间一般不能直接访问其他进程的空间，要想让两个用户进程共享空间，必须通过特殊的系统调用实现

消息传递

不必借助任何共享存储区或数据结构，而是以格式化的消息(Message)为单位，将通信的数据封装在消息中，并利用操作系统提供的发送消息和接收消息两个原语，在进程间进行消息传递，完成进程间的数据交换

该方式隐藏了实现细节，通信过程对用户透明，降低了通信程序设计的复杂性和错误率

消息传递也有两种：

直接通信方式（指明接收进程）

发送进程直接把消息发送到接收进程的消息缓冲队列（位于内核空间，由 PCB 保存指向该队列的指针）
间接通信方式/信箱通信方式（信箱）

发送到某个中间实体（貌似也位于内核）

广泛应用于计算机网络

消息传递是当前应用最广泛的进程间通信机制，微内核与服务器之间的通信就采用了消息传递机制。另外该机制还很好地支持多处理机系统、分布式系统和计算机网络

管道通信

管道通信允许两个进程按生产者-消费者方式进行通信

管道 —— pipe 文件

所谓“管道”，是指用于连接一个读进程和一个写进程以实现它们之间通信的一个共享文件，又名 pipe 文件

对于管道两端的进程而言，管道就是一个文件，但它不是普通的文件，它不属于某种文件系统，而是自立门户，单独构成一种文件系统，且只存在于内存

管道实际上是一个固定大小的缓冲区
发送进程以字符流形式将大量数据送入管道

接收进程的读是一次性操作，读取即从管道抛弃
数据在管道中先进先出

只要管道非空，读进程就能从管道中读出数据；只要管道不满，写进程就能往管道中写入数据
为了协调双方通信，管道机制必须提供：
1. 互斥（一方读/写，一方等待）
2. 同步
  
  管道写满，写进程阻塞，直到读进程读出数据，再将写进程唤醒
  
  管道为空，读进程阻塞，直到写进程写入新数据，再将读进程唤醒
3. 确定对方存在（确定对方存在再通信）
管道和一般文件的不同（Linux）
1. 管道大小受限制，防止不加检验地增长
  
  当写进程比读进程工作得快，管道变满时，写满管道将默认地被阻塞，直到某些数据被读取
2. 当读进程比写进程工作得快，管道变空时，读空管道将默认地被阻塞，等待某些数据被写入，而不是一读就直接返回 0（返回文件结束）
管道通信必然是半双工通信（单向）
管道通信是消息传递的一种特殊方式，也可以理解为共享存储的优化和发展
管道只能由创建进程所访问。子进程会继承父进程的打开文件，而管道是一种特殊的文件，子进程自然会继承父进程的管道，并使用它来与父进程通信

因此普通管道只能用于具有共同祖先的进程（具有亲缘关系的进程）之间通信

命名管道 FIFO 允许无亲缘关系的进程访问，不同于 PIPE 管道之处在于它提供一个路径名与之关联，以文件形式存放于文件系统中（即存储在磁盘上）

线程概念和多线程模型

基本概念

引入线程的目的

减小程序在并发执行时所付出的时空开销，提高操作系统的并发性能

进程“太重”，在创建、撤销和切换中，系统要为之付出较大的时空开销
不把可独立调度和分派的基本单位同时也作为系统进行资源分配的基本单位
线程的主要属性

独立运行/调度的基本单位（多线程操作系统）、基本的 CPU 执行单元、程序执行流的最小单元

线程处于“执行”状态 = 该进程的某线程正在执行
1. 线程是一个轻型实体
  
  不拥有系统资源，但应有一个唯一的标识符和一个线程控制块
  
  线程控制块记录线程执行的寄存器和栈等现场状态
2. 不同的线程可以执行相同的程序
3. 同一进程中的各个线程共享该进程所拥有的资源
4. 线程是处理机的独立调度单位，可并发执行
5. 具有生命周期
  
  线程也有就绪、阻塞和运行三种基本状态，三者之间的转换与进程基本状态之间的转换一致
  
  一个线程可以创建和撤销另一个线程
线程 vs 进程
1. 定位
  
  线程 —— 独立调度的基本单位（处理机的分配单元）
  
  进程 —— 拥有资源的基本单位（除 CPU 外的系统资源的分配单元）
2. 资源
  
  线程本身不拥有系统资源（只有一点点必不可少、能保证独立运行的资源）
  
  线程可以访问其隶属进程的系统资源，主要表现在属于同一进程的所有线程都具有相同的地址空间
  
  在每个线程中都应具有用于控制线程运行的线程控制块 TCB、用于指示被执行指令序列的程序计数器、保留局部变量、少数状态参数和返回地址等的一组寄存器和堆栈
3. 独立性
  
  线程没有自己独立的地址空间
  
  属于同一进程的所有线程都具有相同的地址空间
  
  每个线程都可以访问它们所属进程地址空间中的所有地址，一个线程的堆栈可以被同一进程的其他线程读写，甚至完全清除，由一个线程打开的文件可以供同一进程的其他线程读写。因为同一进程中的不同线程往往是为了提高并发性以及进行相互之间的合作而创建的
  
  某进程内的线程对其他进程不可见
4. 并发性
  
  同一进程、不同进程的线程都能并发执行
  
  这使得操作系统具有更好的并发性
  
  多线程进程可将进程中的多个线程分配到多处理机上执行
5. 系统开销
  
  线程创建、撤销和切换的开销远小于进程（只涉及少量寄存器）
  
  同一进程的线程间同步和通信非常容易实现：由于共享进程的地址空间，可以直接读/写进程数据段（如全局变量）来进行通信，无需同步和互斥手段的辅助
  
  在一些操作系统中，线程的切换、同步和通信甚至无需内核干预
线程是怎么提高系统并发性的？

原先多个任务分别由多个进程负责，现在让一个进程的多个线程负责，进程间并发 → 进程内并发，减少进程切换
线程自身也有缺陷，例如健壮性差，若一个线程挂掉，那整一个进程也挂掉了，即同一进程的其它线程都挂掉了；而进程没有这个问题，一个进程挂掉，另外的进程还活着

线程的实现方式

内核级线程 KLT (Kernel-Level Thread)

也称内核支持线程 KST (Kernel-Supported Thread)

线程管理由内核负责（创建、撤销、切换、调度、通信、同步，下同）
内核空间为每一个内核线程设置了一个线程控制块 TCB
内核线程只在内核地址空间范围活动
优点
1. 能发挥多处理机优势，内核能够同时调度同一进程中的多个线程并行执行
2. 当一个线程被阻塞后，允许同进程的其他线程继续执行
3. 相对进程而言，KST 上下文切换比较快、开销小（内核支持线程具有很小的数据结构和堆栈）
  
  注：ULT 切换没有上下文切换
4. 内核本身也可采用多线程技术，提高系统执行速度和效率
缺点

除了上下文切换，KST 切换还造成模式切换：用户进程的线程在用户态下运行，而线程管理在内核实现。这就导致同一进程中的线程切换，需要从用户态转到核心态进行，系统开销较大

用户级线程 ULT (User-Level Thread)

线程管理由用户应用程序负责，内核意识不到线程的存在

用户级线程是在用户空间中实现的，线程管理无需内核支持，即用户级线程与内核无关
应用程序可以通过线程库设计成多线程程序

用户级线程甚至可以在不支持线程机制的操作系统平台上实现
设置了用户级线程的系统，其调度仍是以进程为单位进行

进程包含的线程数量往往不同，采用轮转调度算法时，各进程轮流执行一个时间片，对线程多的进程中的线程不公平
优点：线程管理开销小，效率高
1. 线程切换不需要转换到内核，节省了模式切换的开销
2. 进程可自行选择调度算法管理线程
3. 用户级线程的实现与操作系统平台无关，对线程管理的代码是属于用户程序的一部分
缺点
1. 系统调用的阻塞问题：同一进程的线程一堵全堵
  
  在基于进程机制的 OS 中，大多数系统调用将使进程阻塞，因此当线程执行一个系统调用时，不仅该线程被阻塞，而且进程内的所有线程会被阻塞。而在 KST 中，进程中的其他线程仍可以运行
2. 多线程应用不能利用多处理机进行多重处理（内核每次只给一个进程分配一个 CPU）
实现

运行在一个中间系统上，由这个中间系统与内核打交道。中间系统的实现方式有：
1. 运行时系统(runtime system)
  
  实质上是管理和控制线程的函数/过程集合，包括用于创建和撤销线程的函数、线程同步和通信的函数以及实现线程调度的函数等
  
  所有函数驻留在用户空间，并作为 ULT 与内核之间的接口
  
  正是有了这些函数，才能使用户级线程与内核无关
  
  当线程需要系统资源时，将要求传送给运行时系统，由后者通过相应的系统调用来获得系统资源
2. 内核控制线程/轻型进程 LWP (Light Weight Process)
  
  每一个进程可拥有多个 LWP，把这些 LWP 做成一个缓冲池，称“线程池”
  
  LWP 都有自己的数据结构（如 TCB），共享进程所拥有的资源，可通过系统调用获得内核服务
  
  用户进程中的任一 ULT 都可以连接到 LWP 池中的任何一个 LWP 上
  
  为使每一 ULT 都能利用 LWP 与内核通信，可使多个 ULT 多路复用一个 LWP，但只有当前连接到 LWP 上的线程才能与内核通信
  
  每一个 LWP 都要连接到一个 KLT 上，这样，通过 LWP 可把 ULT 与 KLT 连接起来
  
  若 KLT 发生阻塞，则与之相连接的多个 LWP 也将随之阻塞，进而使连接到 LWP 上的 ULT 也被阻塞，若进程中只包含了一个 LWP，此时进程也应阻塞。若进程中含有多个 LWP，则当一个 LWP 阻塞时，进程中的另一个 LWP 可继续执行。即使进程中所有 LWP 全部阻塞，进程中的线程也仍能继续执行，只是不能再去访问内核

实际上就是下面的组合方式

组合方式 ULT/KST

内核支持多个 KLT 的建立、调度和管理，同时允许用户程序建立、调度和管理 ULT

一些 KLT 对应多个 ULT，这是 ULT 通过时分多路复用 KLT 实现的，即将 ULT 对部分或者全部 KLT 进行多路复用，程序员可按应用需要和机器配置，对 KLT 数目进行调整，以达到较好效果

组合方式线程中，同一进程的多个线程可以同时在多个处理机上并行执行，且在阻塞一个线程时不需要将整个进程阻塞，所以组合方式能结合 KLT 和 ULT 的优点并克服各自的不足

线程库(thread library)

为程序员提供创建和管理线程的 API

实现方法主要有两种：
1. 在用户空间中提供一个没有内核支持的库
  
  这种库的所有代码和数据结构都位于用户空间
  
  这意味着调用库内的一个函数只导致用户空间的一个本地函数的调用
2. 实现由操作系统直接支持的内核级的一个库
  
  这种库的代码和数据结构位于内核空间，调用库中的一个 API 函数通常会导致对内核的系统调用
  
  目前使用的三种主要线程库：POSIX Pthreads、Windows API、Java
3. Pthreads 可提供用户级或内核级的库（类 UNIX 系统）
4. Windows API 属于内核级线程库
5. Java 程序中可使用 Java API 直接创建管理线程。但由于 JVM 实例通常运行在宿主操作系统上，Java 线程 API 通常采用宿主系统的线程库来实现（在 Windows 系统中 Java 线程通常采用 Windows API 来实现，在类 UNIX 系统中采用 Pthread 来实现）

多线程模型

由于 ULT 和 KST 连接方式的不同，组合方式形成了三种不同模型

多对一模型

多个 ULT 映射到一个 KST，这些 ULT 一般属于一个进程

线程的调度和管理在用户空间完成，仅当 ULT 需要访问内核时，才将其映射到一个 KLT 上，但是每次只允许一个线程进行映射

优点：线程管理效率比较高（线程管理在用户空间进行）

缺点：同一进程的线程一堵全堵；并发较差，不能利用多处理机，在任一时刻只能有一个线程能访问内核
一对一模型

优点：不会一堵全堵，并发性较强

缺点：创建线程开销较大，每创建一个 ULT，相应地就需要创建一个 KLT
多对多模型

将许多 ULT 映射到同样数量或更少数量的 KLT 上

既克服了多对一模型并发度不高的缺点，又克服了一对一模型的一个用户进程占用太多 KLT 而开销太大的缺点，另外还拥有上述两种模型的优点，是上述两种模型的折中方案

线程的组织与控制

线程控制块 TCB

用于记录控制和管理线程的信息

通常包括：
1. 线程标识符
2. 一组寄存器：包括 PC、状态寄存器、通用寄存器的内容
3. 线程运行状态
4. 优先级
5. 线程专有存储区：线程切换时用于保存现场等
6. 堆栈指针：用于过程调用时保存局部变量及返回地址等
同一进程的各个线程都可以访问进程地址空间的每个单元，所以一个线程可以读、写或甚至清除另一个线程的堆栈
线程的创建

应用程序启动时通常仅有一个线程在执行，称为“初始化线程”，主要用于创建新线程

创建新线程时需要利用一个线程创建函数或系统调用，并提供相应参数，如线程主程序的入口指针、堆栈的大小、线程优先级等

线程创建函数执行完后，将返回一个线程标识符
线程的终止

当一个线程完成任务或出现异常情况时，由终止线程调用相应的函数或系统调用执行对其终止操作

有些线程（主要是系统线程）创建之后便一直运行下去而不被终止

大多数操作系统中，线程被终止后并不立即释放资源，只有当进程中的其他线程执行了分离函数后，被终止的线程才与资源分离，此时的资源才能被其他线程利用

被终止但尚未释放资源的线程仍可被其他线程调用，以使被终止线程重新恢复运行。为此，调用线程须调用一条被称为“等待线程终止”的连接命令来与该线程进行连接。若在一个调用者线程调用“等待线程终止”的连接命令，试图与指定线程相连接时，若指定线程尚未被终止，则调用连接命令的线程将会阻塞，直至指定线程被终止后，才能实现它与调用者线程的连接并继续执行；若指定线程已被终止，则调用者不会被阻塞而是继续执行

处理机调度

调度的概念

基本概念

处理机调度是对处理机进行分配（进程数往往多于处理机数）

即从就绪队列按照一定算法选择一个进程并将处理机分配给它运行，以实现进程并发执行

只要对资源的请求大于资源本身的数量，就会涉及调度
目的

提高处理机利用率，合理地处理计算机软/硬件资源
调度层次

一个作业从提交开始直到完成，往往会经历以下三级调度：
1. 作业调度/高级调度
  
  从外存处于后备状态的作业挑选一个或多个，给其分配内存等必要资源，并建立相应进程，使其获得竞争处理机的机会
  
  是内存与辅存之间的调度
  
  每个作业只调入一次，调出一次
  
  主要用于多道批处理系统中，而在分时和实时系统中不设置高级调度
2. 内存调度/中级调度
  
  暂时不能运行的进程会被调至外存等待（变成挂起态），而中级调度的对象是那些外存上的又已具备运行条件的挂起态进程。当内存稍有空闲后，中级调度挑选后将其重新调入内存，状态改为就绪态，挂在就绪队列等待
  
  实际上是存储器管理中的对换功能
3. 进程调度/低级调度
  
  其实就是处理机调度
  
  最基本调度，一般操作系统（多道批处理、分时和实时）必须配置
  
  频率很高，一般几十毫秒一次
三级调度的关系

作业调度为进程活动做准备，进程调度使进程正常活动起来

中级调度将暂时不能运行的进程挂起，处于作业调度和进程调度之间

作业调度次数少，中级调度次数略多，进程调度频率最高

进程调度是最基本的，不可或缺
闲逛进程 idle

在进程切换时，如果系统中没有就绪进程，就会调度闲逛进程运行，如果没有其他进程就绪，该进程就一直运行，并在执行过程中测试中断

闲逛进程的优先级最低，没有就绪进程时才会运行。只要有进程就绪，就会立即让出处理机

闲逛进程不需要 CPU 之外的资源，它不会被阻塞

调度的目标

即对调度算法的评价准则。要从用户角度、系统整体效率、调度算法开销几个角度同时考虑，而且调度本身也有三种，角度不同，评价标准也有差别

CPU 利用率

一般都是越忙越好，别让它闲着
系统吞吐量

单位时间内 CPU 完成作业的数量

只看数量，比较狭隘。抛开算法的话，短作业占比越大系统吞吐量就越大
周转时间（从作业提交到作业完成所经历的时间）

周转时间 = 作业完成时间 - 作业提交时间 = 作业等待 + 在就绪队列中排队 + 在处理机上运行 + 进行输入/输出操作

带权周转时间 = 作业周转时间 / 作业实际运行时间

作业实际运行时间，即系统总共为它提供服务的时间，例题
等待时间

等待处理机的时间之和（即在就绪队列中所花的时间）

处理机调度算法实际上并不影响作业执行或 I/O 操作的时间，只影响作业在就绪队列中等待所花的时间

衡量一个调度算法的优劣，常常只需简单地考察等待时间
响应时间

从用户提交请求到系统首次产生响应所经历的时间

在交互式系统中一般采用响应时间作为衡量调度算法的重要准则之一

调度的实现

调度程序/调度器

用于调度和分派 CPU 的组件，属于操作系统内核程序，由排队器、分派器和上下文切换器三部分组成

排队器

将系统中的所有就绪进程按照一定的策略排成一个或多个队列，以便于调度程序选择。每当有一个进程转变为就绪态时，排队器便将它插入到相应的就绪队列中
分派器

依据调度程序所选的进程，将其从就绪队列中取出，将 CPU 分配给新进程
上下文切换器

对处理机进行切换时会发生两对上下文的切换操作：
1. 将当前进程的上下文保存到其 PCB 中，再装入分派程序的上下文，以便分派程序运行
2. 移出分派程序的上下文，将新选进程的 CPU 现场信息装入处理机的各个相应寄存器中，以便新选进程运行
  
  上下文切换时需要执行大量 load 和 store 指令以保存和更新寄存器的内容，会花费较多时间。现已有硬件实现的方法来减少上下文切换时间：通常采用两组或多组寄存器，一组供内核使用，一组供用户使用。这样上下文切换时，只需改变指针让其指向当前寄存器组即可
  
  进程调度方式
非剥夺调度方式/非抢占方式

再急也要等当前进程执行完或进入阻塞后

一旦把处理机分配给某进程后，就一直让它运行下去，绝不会因为时钟中断或任何其他原因去抢占当前正在运行进程的处理机，直至该进程完成或发生某事件而使其无法再继续运行

优点：实现简单、系统开销小，适用于大多数的批处理系统

缺点：不能用于分时系统和大多数的实时系统
剥夺调度方式/抢占方式

优点：对提高系统吞吐率和响应效率都有明显的好处

抢占不是任意性抢占，必须遵循一定原则（主要有优先级、短进程优先和时间片原则等）

进程调度时机

① 请求调度的事件发生 → ② 运行调度程序，调度新进程 → ③ 进程切换
① 出现后，② 不一定马上进行；② 完成后，③ 往往立刻发生

发生引起调度的条件，但不能进行进程调度与切换的情况
1. 处理中断的过程中
  
  中断处理过程复杂，很难实现切换
  
  中断处理是系统工作的一部分，逻辑上不属于任何进程，不应被剥夺处理机资源
2. 进程在操作系统内核临界区中
3. 其他需要完全屏蔽中断的原子操作过程中
  
  如加锁、解锁、中断现场保护、恢复等（连中断都要屏蔽，更不应该进行进程调度和切换）
  
  若在上述过程中发生了引起调度的条件，则不能马上进行调度与切换，而应置系统的请求调度标志，直到上述过程结束后才进行相应的调度与切换
  
  当进程处于临界区时，说明进程正在占用处理机，只要不破坏临界资源的使用规则，就不会影响处理机的调度（翻译：在进程处于临界区时是可以进行处理机调度的）
应该进行进程调度与切换的情况
1. 发生引起调度条件且当前进程无法继续运行下去时
  
  若操作系统只是在这种情况下进行进程调度，则是非剥夺调度
2. 中断或自陷处理结束后，返回被中断进程的用户态程序执行现场前，若置上请求调度标志，即可马上进行进程调度与切换
  
  若操作系统支持这种情况下运行调度程序，则实现了剥夺式调度
  
  不一定：I/O 中断、故障异常、自陷异常、时钟中断
  
  一定会：终止异常、内存失效、时间片用完

线程的调度

用户级线程调度

由所属进程中的调度程序决定哪个 ULT 运行（内核不知道 ULT 的存在）
内核级线程调度

由内核调度

KST 切换需要完整的上下文切换、修改内存映像、使高速缓存失效，这就导致了若干数量级的延迟

典型的调度算法

先来先服务调度算法 FCFS（作业/进程）

属于不可剥夺算法

特点：
1. 简单但效率低
2. 表面公平：对长作业比较有利，对短作业不利（相对 SJF 和高响应比）
3. 有利于 CPU 繁忙型作业，不利于 I/O 繁忙型作业
  
  不能作为分时系统和实时系统的主要调度策略
  
  常被结合在其他调度策略中使用
短作业优先调度算法 SJF/短进程优先调度算法 SPF

SPF：从就绪队列中选择一个估计运行时间最短的进程，将处理机分配给它

SJF：选择一个或若干估计运行时间最短的作业调入内存运行

优点：平均等待时间、平均周转时间最少

缺点：
1. 对长作业/进程不利，可能会引起长进程/作业的饥饿
2. 完全未考虑紧迫程度
3. 预估运行时间是用户提供的（这就很……，相当于让用户手动设置优先级了）
优先级调度算法（作业/进程）

优先级用于描述作业/进程的紧迫程度

根据新的更高优先级进程进入就绪队列后能否抢占正在执行的进程，可分为非剥夺式优先级调度算法和剥夺式优先级调度算法两种

根据进程创建后其优先级是否可以改变，进程优先级也可分为两种：
1. 静态优先级
  
  创建时确定，运行期间不变
  
  主要依据：进程类型、进程对资源的要求、用户要求
2. 动态优先级
  
  运行期间根据进程情况的变化动态调整
  
  主要依据：进程占有 CPU 时间的长短、就绪进程等待 CPU 时间的长短
  
  优先级设置一般原则：
3. 系统进程＞用户进程
4. 交互进程＞非交互型进程（前台进程＞后台进程）
5. I/O 型进程＞计算型进程（让处理速度相对较慢的 I/O 设备尽早开始工作，进而提升系统的整体效率）
高响应比优先调度算法（作业）

对 FCFS 和 SJF 的一种综合平衡，克服了 SJF/SPF 可能会产生的饥饿现象

响应比 $R_p = \frac{\text{等待时间 + 要求服务时间}}{\text{要求服务时间}}$

满足短任务优先且不会发生饥饿
时间片轮转调度算法 RR（进程）

属于抢占式算法

系统将所有的就绪进程按 FCFS 策略排成一个就绪队列。系统可设置每隔一定时间（如 30 ms）便产生一次中断，去激活进程调度程序进行调度，把 CPU 分配给队首进程，并令其执行一个时间片。在使用完一个时间片后，即使进程并未运行完成，它也必须释放出（被剥夺）处理机给下一个就绪进程，而被剥夺的进程返回到就绪队列的末尾重新排队，等候再次执行

进程切换时机：① 一个时间片用完；② 一个时间片尚未用完而正在运行的进程便已完成

时间片的大小对系统性能影响很大：太大以致所有进程都能在一个时间片内执行完毕，便会退化成 FCFS；小了会使进程频繁切换，开销增大，导致真正用于运行用户进程的时间将减少

时间片的大小通常由以下因素确定：系统的响应时间、就绪队列中的进程数据和系统的处理能力

主要适用于分时系统（人机交互）
多级队列调度算法

前述的各种算法，在系统中仅设置一个进程的就绪队列，即调度算法是固定且单一的，无法满足系统中不同用户对进程调度策略的不同要求。在多处理机系统中，这种单一调度策略实现机制的缺点更为突出

多级队列调度算法在系统中设置多个就绪队列，每个队列可实施不同的调度算法，队列本身也可以设置不同的优先级。在多处理机系统中，可以很方便为每个处理机设置一个单独的就绪队列
多级反馈队列调度算法

在设计时需考虑就绪队列的数量、就绪队列的优先级、各就绪队列的调度算法和进程在就绪队列间的迁移条件
实现思想：
1. 第 1 ~ $n-1$ 级采用 FCFS，第 $n$ 级采用 RR。不同队列间采用剥夺式优先级调度
2. 每个新进程进入内存后首先被放入第 1 级队列的末尾。到它执行时，若能在一个时间片内完成则完成后撤离系统，否则调度程序将其转入下一级队列的末尾。后序队列以此类推，直到降至第 $n$ 级，采取 RR
3. 仅当 1 ~ $i-1$ 级队列均为空时，才会调度第 $i$ 级队列中的进程运行。若此时有新进程进入 1 ~ $i-1$ 级队列，则该进程会抢占处理机，即由调度程序把正在运行的进程放回第 $i$ 级队列的末尾，把处理机分配给新的更高优先级的进程
  
  优势：
4. 终端型作业用户：交互型作业通常较小，让短作业优先即可
5. 短批处理作业用户：周转时间较短
6. 长批处理作业用户：长作业经过前面几个队列得到部分执行，不会长期得不到处理

常见进程调度算法特点总结

实时：优先级；分时：高响应比优先、时间片轮转、多级反馈队列
时间片与时钟中断

时钟中断是频率性发出的信号，两次时钟中断的间隔时间称为节拍，即时钟周期。时间片是若干时钟周期的片段。时钟中断发生后，系统会修改当前进程在时间片内的剩余时间，即减去一个时钟周期。若剩余时间减到 0，就进行进程调度（因此分时系统实现时间片轮转调度需要使用时钟中断处理程序）

进程在时间片用完之前主动让出 CPU 的时候，进程调度模块会记录下时间片剩余时间，在该进程下次再获得 CPU 时，继续运行之前时间片的剩余时间

进程运行结束不必等待当前进程的时间片全部用完

上下文切换

常见的上下文切换类型：

系统调用的上下文切换（模式切换）
进程上下文切换
线程上下文切换
中断上下文切换

进程上下文切换

进程的物理实体（代码和数据等）和支持进程运行的环境合称为进程的上下文

进程上下文 = 用户级上下文 + 系统级上下文
1. 用户级上下文
  
  用户进程的程序块、数据块、运行时的堆和用户栈（统称为用户堆栈）等组成的用户空间信息
2. 系统级上下文：进程标识信息、进程控制信息、进程现场信息和系统内核栈等组成的内核空间信息
  
  即进程控制块 + 内存管理信息（页表、打开文件表等）+ 内核栈
用户级上下文地址空间和系统级上下文地址空间一起构成了一个进程的整个存储器映像（即进程的虚拟地址空间）
处理机上下文/寄存器上下文/硬件上下文

指处理机中各个寄存器的内容
进程上下文切换时的操作

发生在操作系统调度一个新进程到处理器上运行时，流程如下：
1. 挂起一个进程，保存 CPU 上下文到 PCB 中
2. 将 PCB 移入相应的队列（如就绪、在某事件阻塞等队列）
3. 选择新进程执行，并更新其 PCB
4. 恢复新进程的 CPU 上下文
5. 跳转到新进程 PCB 中的程序计数器所指向的位置执行
开销

通常是计算密集型，意味着需要消耗大量的 CPU 时间

有些处理器提供多个寄存器组，这样上下文切换就只需简单改变当前寄存器组的指针
进程切换 vs 处理机模式切换

处理机模式切换时，处理机逻辑上可能还在同一进程中运行
刚执行过的进程优先级应该降低

降低的时机是时间片用完的时候，而不是刚进入运行态的时候

线程上下文切换

不同进程的两个线程切换 = 进程切换

同进程内的线程切换，要比进程间的切换消耗开销更少

另外，内核级线程的切换还会引起模式切换

中断上下文切换

中断处理作为内核进程，不涉及用户态操作，因此中断上下文只包括处于内核空间的信息：内核堆栈、硬件中断参数等。即使一个中断打断了一个正在用户态处理的进程，陷入内核，也不需要保存和恢复进程的虚拟内存、用户栈等

系统调用上下文切换/模式切换

模式切换时，进程所使用的栈要从用户栈转到内核栈：进程陷入内核态后，先把用户栈地址保存在内核栈之中，然后设置 SP 的内容为内核栈地址，这样就完成了用户栈向内核栈的转换；当进程从内核态切换到到用户态时，将保存在内核栈里面的用户栈的地址恢复到堆栈指针寄存器即可。这样就实现了内核栈和用户栈的互转

问题来了，内核态转到用户态时用户栈地址是在陷入内核的时保存在内核栈里面的，但是在陷入内核时是如何知道内核栈的地址的呢？

进程从用户态转到内核态之时，进程的内核栈一定是空的。这是因为在系统调用过程中，内核栈只是用来保存进程在内核态运行的相关信息以及用户栈地址，一旦进程返回到用户态后，内核栈中保存的信息就会失效。因此每次进程从用户态陷入内核的时候得到的内核栈都是空的。所以在进程陷入内核的时候，直接把内核栈的栈顶地址给 SP 就可以了

严格来说，系统调用过程并不是上下文切换，因为没有涉及到虚拟内存等进程用户态的资源，只是同一进程的用户栈与内核栈的使用转换。但实际上系统调用过程中，CPU 上下文切换还是无法避免的

同步与互斥

在多道程序共同执行的条件下，进程与进程是并发执行的，不同进程之间存在不同的相互制约关系，为了协调进程之间的相互制约关系，引入了进程同步的概念

进程同步的基本概念

临界资源(critical resource)

一次仅允许一个进程使用的资源

临界资源和共享资源的区别在于，在一段时间内能否允许被多个进程访问（并发使用）
临界资源的访问过程（代码部分）
1. 进入区(entry section)
  
  在进入区要检查可否进入临界区
  
  设置了是否有进程正在访问临界区的标志
2. 临界区(critical section)
  
  进程中访问临界资源的那段代码，又称临界段
3. 退出区(exit section)
  
  将标志设置为未被访问
4. 剩余区(remainder section)
  
  代码中的剩余部分
两种形式的进程间制约关系
1. 同步（直接制约关系）
  
  为完成某种任务而建立的两个或多个进程，这些进程因需要协调它们的工作次序而等待、传递信息所产生的制约关系
2. 互斥（间接制约关系）
  
  并发进程访问同一临界资源形成的制约关系
同步机制应遵循的规则
1. 空闲让进
  
  临界区空闲的话，允许一个请求进入临界区的进程立即进入
2. 忙则等待
  
  有进程进入临界区了，其他进程得等他出来才能进
3. 有限等待
  
  对请求访问的进程，应保证能在有限时间内进入临界区
4. 让权等待
  
  不能进入临界区时应立即释放处理机，别在那忙等
  
  忙等：等待进程一直轮询某个变量直到符合条件，浪费时间片
  
  实现临界区互斥，“让权等待”不一定非得实现

实现临界区互斥的基本方法

软件实现方法（标志）

单标志法

一个公用整型变量 return，值表示被允许进入临界区的进程编号。某进程在退出临界区时把接下来进入的“机会”指名让给另一个进程

显然本算法要求进程必须交替进入临界区。若被指名的进程不打算进入临界区，其他进程就都没法再进入临界区，即使临界区是空闲的，因此该方法违背了“空闲让进”
双标志法先检查

每个进程都有一个布尔类型的标志，标志为 true 时意味着宣布自己正在访问临界资源。每个进程在进入区会通过检查其它进程的标志来确认临界资源是否正被访问，若为空闲才进入临界区。进入临界区后先设置自己的标志为 true，在进入退出区时再设置为 false

本算法不要求进程交替进入，可连续使用

但检查和设置是分开的，不能一次进行，两个进程按 ①②③④ 的顺序执行时就会同时进入临界区，违背了“忙则等待”
双标志法后检查

先设置再检查，虽然避免了之前的问题，但又会导致两个进程饥饿（互等，但其实谁都没进去），违背“空闲让进”和”有限等待“
Peterson’s Algorithm

flag[i] 设置为 true 表示进程 i 想要进入临界区，表达自己想要之后，再将 turn 设置为 j（可以理解为“我想进，但还是让 j 先来吧）

之后 i 进行 while 检查，如果 j 也表达了自己想进，并且 j 已在临界区中，那就等 j 弄完；如果 j 不想进，或者 j 也想要，但是在自己“谦让”之后，j 也“谦让”了，那就不在那瞎客气了，心安理得地进临界区了

> 先谦让的只是假客气：
>
> “你先吧” “你先你先” “那我不客气了”
> “你先吧” “我现在不想” “那我不客气了”

本算法是单标志法和双标志法后检查的结合，利用 flag 解决临界资源的互斥访问，利用 turn 解决饥饿现象

违背“让权等待”

硬件实现方法（低级方法/元方法）

关中断指令

当有进程在执行它的临界区代码时，直接暴力关中断，执行完再开

因为 CPU 只在发生中断时引起进程切换（进程切换要在核心态下进行，只有利用中断才能进入核心态），因此屏蔽中断能够保证当前运行的进程让临界区代码顺利地执行完

如此简单粗暴，自然存在很多缺点：
1. 将关中断的权力交给用户很不明智
  
  若一个进程关中断后不再开中断，则系统可能会因此终止
2. 限制了处理机交替执行程序的能力，执行的效率会明显降低
3. 对多处理机系统没用
  
  在一个 CPU 上关中断并不能防止进程在其他 CPU 上执行相同的临界区代码

原语功能的不被中断执行特性在单处理机上可由软件通过屏蔽中断方法实现

硬件指令方法（原子操作）
1. TestAndSet 指令
  1
  2
  3
  4
  5
  boolean testAndSet(boolean *lock) {
  boolean old = *lock;
  *lock = true;
  return old;
  }
  为每个临界资源设置一个共享布尔变量 lock，true 表示正被占用
  
  利用该指令实现互斥的过程描述如下：
  1
  2
  3
  4
  while (testAndSet(&look));
  critical section;
  lock = false;
  remainder section;
  优点：相比于软件实现方法，TS 指令将“加锁”和“检查”操作用硬件的方式变成了一气呵成的原子操作；相比于关中断方法，由于“锁”是共享的，这种方法适用于多处理器系统
  
  缺点：违背“让权等待”，暂时无法进入临界区的进程会占用 CPU 循环执行 TS 指令
2. Swap 指令（交换两个字的内容）
  1
  2
  3
  4
  5
  void Swap(boolean *a, boolean *b) {
  boolean temp = *a;
  *a = *b;
  *b = temp;
  }
  为每个临界资源设置一个共享布尔变量 lock，每个进程中再设置一个局部布尔变量 key
  1
  2
  3
  4
  5
  6
  7
  key = true;
  while (key) {
  Swap(&lock, &key);
  }
  critical section;
  lock = false;
  remainder section;
  两个指令的功能由硬件逻辑直接实现，不会被中断
  
  其实两个算法思路很像，都是上来就将临界资源的 lock 设置为 true，再看设置前的 lock。如果原来就是 true，那就等，之前的设置 true 没什么影响；如果原来是 false，那正好，没白设置，接下来直接进
  
  优点：
3. 适用于任意数目的进程，支持多处理器系统
4. 简单、容易验证其正确性
5. 支持进程内有多个临界区（只需为每个临界区设立一个布尔变量）
  
  缺点：
6. 违反“让权等待”，等待进入临界区的进程会占用 CPU 执行 while 循环
7. 违反“有限等待”，可能发生饥饿，因为是随机从等待进程中选择一个进入临界区，有的进程可能一直选不上

互斥锁 mutex lock

解决临界区最简单的工具

进程在进入临界区应获得锁，在退出临界区时释放锁

acquire() {
    while (!available);  // 忙等
    available = false;  // 拿到锁
}

release() {
    available = true;  // 释放锁
}

acquire() 和 release() 的执行必须是原子操作，因此互斥锁通常采用硬件机制实现

上面描述的互斥锁也称自旋锁，主要缺点是 acquire() 会忙等，违反“让权等待”，因此通常用于多处理器系统

自旋锁的优点是，进程在等待锁期间，没有上下文切换，若上锁的时间较短，则等待代价不高

信号量

可用来解决互斥与同步问题

信号量只能被两个标准的原语 wait(S) 和 signal(S) 访问

P 操作 —— Passeren/Pass —— wait(S) 原语
V 操作 —— Verhoog/Increment —— signal(S) 原语

P、V 操作都是低级的进程通信原语

整型信号量

一个表示资源数目的整型量 S

void wait(S) {
    while (S <= 0);  // 忙等
    S--;
}

void signal(S) {
    S++;
}

和互斥锁很像，没有遵循“让权等待”

记录型信号量

一种不存在忙等现象的进程同步机制

引入一个进程链表，用于链接所有等待该资源的进程

typedef struct {
    int value;  // 资源数目
    struct process *L;  // 等待该资源的进程链表
} semaphore;

void wait(semaphore S) {  // 相当于申请资源
    S.value--;
    if (S.value < 0) {
        add this process to S.L;
        block(this process);  // 自我阻塞
    }
}

void signal(semaphore* S) {  // 相当于释放资源
    S.value++;
    if (S.value <= 0) {
        remove a process P from S.L;
        wakeup(P);
    }
}

记录型信号量由于引入阻塞机制，消除了不让权等待的情况

利用信号量实现同步

例：P2 中的语句 y 要在 P1 中的语句 x 执行完后才可以执行

semaphore S = 0;
P1() {
    ...
    x;
    V(S);
    ...
}
P2() {
    ...
    P(S);
    y;
    ...
}

利用信号量实现互斥

semaphore S = 1;
P1() {
    ...
    P(S);
    critical section;
    V(S);
    ...
}
P2() {
    ...
    P(S);
    critical section;
    V(S);
    ...
}

利用信号量实现前驱关系

semaphore a1 = a2 = b1 = b2 = c = d = e = 0;
S1() {
    ...;
    V(a1); V(a2);
}
S2() {
    P(a1);
    ...;
    V(b1); V(b2);
}
S3() {
    P(a2);
    ...;
    V(c);
}
S4() {
    P(b1);
    ...;
    V(d);
}
S5() {
    P(b2);
    ...;
    V(e);
}
S6() {
    P(c);
    P(d);
    P(e);
    ...;
}

管程 monitor

信号量机制虽然方便有效，但每个要访问临界资源的进程都必须自备 PV 操作，使得大量同步操作分散在各个进程中，不仅给系统管理带来了麻烦，还可能因使用不当而导致系统死锁

管程 —— 包含面向对象思想的进程同步工具

将表征共享资源的数据结构及其对数据结构操作的一组过程，包括同步机制，全都集中封装在一个对象内部，隐藏实现细节
管程组成
1. 管程名称
2. 局部于管程内部的共享数据结构说明
3. 对局部于管程内部的共享数据结构设置初始值的语句（init 初始化）
4. 对该数据结构进行操作的一组过程/函数（对共享资源的申请、释放等操作）
在管程的设计中还要包含
1. 一把基于 mutex 的锁
  
  确保进程互斥进入管程
2. 多个条件变量 condition
  
  管程也是一种“资源”。当一个进程进入管程后被阻塞，它应该释放管程，让其他进程有机会进入管程，而自己挂到临界资源的等待队列上
  
  将阻塞原因定义为条件变量 condition
  
  阻塞原因有多个，相应地会有多个等待队列。每个条件变量保存了一个等待队列，同时提供了 wait 和 signal 两个原子操作，对于条件变量 x：
  
  x.wait：当 x 对应的条件不满足时，该进程调用 x.wait 将自己挂在 x 条件的等待队列，并释放锁（管程）
  
  x.signal：当 x 对应的条件发生了变化，当前进程调用 x.signal 唤醒一个因 x 条件而阻塞的进程（没有就算了）
条件变量 vs 信号量

条件变量“没有值”，仅实现了“排队等待”，剩余资源数由管程中的共享数据结构记录
管程是语法范围，无法创建和撤销

经典同步问题

生产者-消费者问题

最简单的生产者-消费者问题：

问题描述：懒得描述
问题分析

互斥：缓冲池是临界资源

同步：缓冲池满了就不能生产，缓冲池空了就不能消费
解决思路

mutex 作为互斥信号量，用户控制互斥访问缓冲池，初值为 1

信号量 full 用于记录缓冲池中的满缓冲区数，初值为 0

信号量 empty 用于记录当前缓冲池中的空缓冲区数，初值为 n

算法描述

semaphore mutex = 1, empty = n, full = 0;
producer() {
    while (1) {
        produce an item in nextp;  // 生产数据
        P(empty);
        P(mutex);
        add nextp to buffer;
        V(mutex);
        V(full);
    }
}
consumer() {
    while (1) {
        P(full);
        P(mutex);
        remove an item in nextp;
        V(mutex);
        V(empty);
        consume the item;  // 消费数据
    }
}

注意，对 empty 和 full 的 P 操作要放在对 mutex 的 P 操作之前，不然会出现消费者/生产者把自己锁在空/满缓冲池里阻塞，生产者/消费者怎么也进不去的画面（即要先同步后互斥）

复杂点的生产者-消费者问题：

问题描述

桌上有一盘，每次只能放一个水果，爸爸负责放苹果，妈妈负责放橘子，女儿只吃苹果，儿子只吃橘子
问题分析

互斥：盘子是临界资源，爸妈互斥放，子女互斥拿

同步：爸爸放橘子 → 女儿吃橘子，妈妈放苹果 → 儿子吃苹果
解决思路

抽象为两个生产者和两个消费者被连接到大小为 1 的缓冲区上

算法描述

semaphore plate = 1, apple = 0, orange = 0;
dad() {
    while (1) {
        prepare an apple;
        P(plate);
        put the apple on the plate;
        V(apple);
    }
}
mom() {
    while (1) {
        prepare an orange;
        P(plate);
        put the orange on the plate;
        V(orange);
    }
}
son() {
    while (1) {
        P(orange);
        take an orange from the plate;
        V(plate);
        eat the orange;
    }
}
daughter() {
    while (1) {
        P(apple);
        take an apple from the plate;
        V(plate);
        eat the apple;
    }
}

读者-写者问题

问题描述

可以同时读，不可以同时写，也不可以在写的时候读
问题分析

互斥：读写互斥，写写互斥
解决思路

写者与读写都互斥，只使用一把互斥锁 lock 即可

读者只需与写者竞争锁 lock，因此设置一个信号量 count 为读者计数器（初值为 0），用它来判断当前是否有读者在读，再设置一把互斥锁 mutex 保护 count 的访问

算法描述

读者优先

int count = 0;
semaphore lock = 1, mutex = 1;
writer() {
    while (1) {
        P(lock);
        writing;
        V(lock);
    }
}
reader () {
    while (1) {
        P(mutex);
        if (count == 0) {
            P(lock);  // 只有第一个读者需要获取lock锁
        }
        count++;
        V(mutex);
        reading;
        P(mutex);
        count--;
        if (count == 0) {
            V(lock);  // 直到最后一个读者再释放lock锁
        }
        V(mutex);
    }
}

一旦有读者在读，那后面来的读者可以无视写者直接插队。只有当没有读者排队时才能轮到写者，所以容易导致写者饥饿

读写公平

不能再让读者无脑插队了，当有读进程正在读共享文件时，有写进程请求访问，这时应禁止后续读进程的请求

只需再加一把互斥锁 queue 即可

int count = 0;
semaphore mutex = 1, lock = 1, queue = 1;
writer() {
    while (1) {
        P(queue);
        P(lock);
        writing;
        V(lock);
        V(queue);
    }
}
reader() {
    while (1) {
        P(queue);
        P(mutex);
        if (count == 0) {
            P(lock);
        }
        count++;
        V(mutex);
        V(queue);
        reading;
        P(mutex);
        count--;
        if (count == 0) {
            V(lock);
        }
        V(mutex);
    }
}

写者优先

semaphore readLock = 1;  // 互斥信号量,用于给读者上锁
semaphore writeLock = 1;  // 互斥信号量,用于给写者上锁
semaphore rmutex = 1;  // 互斥信号量,实现对readCount互斥访问
semaphore wmutex = 1;  // 互斥信号量,实现对writeCount互斥访问
int readCount = 0, writeCount = 0;
writer(){
    while(1){
    	P(wmutex);
    	writeCount++;
    	if (writeCount == 1) P(readCount);  // 第一个到达的写者对读者上锁
    	V(wmutex);
    	P(writeLock);
    	writing;
    	V(writeLock);
    	P(wmutex);
    	writeCount--;
    	if (writeCount == 0) V(readCount);  // 最后一个写者写完后对读者解锁
    	V(wmutex);
    }
}
reader(){
    while(1){
    	P(readLock);  // 每个读者达到时先对read上锁
    	P(rmutex);
    	readCount++;
    	if (readCount == 1) P(writeCount);  // 第一个到达的读者对写者上锁
    	V(rmutex);
    	V(readLock);  // 每个读者读之前对read解锁
    	reading;
    	P(rmutex);
    	readCount--;
    	if (readCount == 0) V(writeLock);  // 最后一个读者读完后对写者解锁
    	V(rmutex);
    }
}

哲学家进餐问题

问题描述

看图意会
问题分析

相邻两个哲学家对其中间的叉子是互斥访问

要避免死锁和饥饿
解决思路
1. 思路一：对哲学家编号，奇数号先拿左边的叉子，偶数号先拿右边的叉子
2. 思路二：当一名哲学家左右两边都有叉子时才允许他去拿
3. 。。。

算法描述（思路二）

semaphore fork[5] = {1, 1, 1, 1, 1};
semaphore mutex = 1;
Pi() {
    do {
        P(mutex);
        P(fork[i]);
        P(fork[(i+1)%5]);
        V(mutex);
        eat;
        V(fork[i);
        V(fork[(i+1)%5]);
        think;
    } while (1);
}

吸烟者问题

问题描述

三个抽烟者进程和一个供应者进程。烟草、纸和胶水各一个可合成一支烟。供应者拥有三种材料，三个抽烟者各拥有一种资源。供应者每次提供两种材料各一个放到桌子上，拥有剩下一种材料的抽烟者就卷成一支烟并抽掉它
问题分析

互斥：三个抽烟者对抽烟这个动作互斥

同步：供应者与三个抽烟者分别同步

算法描述

int num = 0;
semaphore offer1 = 0, offer2 = 0, offer3 = 0;
semaphore finish = 0;
P0() {
    while (1) {
        num = (num + 1) % 3;
        if (num == 0)
            V(offer1);  // 提供烟草和纸
        else if (num == 1)
            V(offer2);  // 提供烟草和胶水
        else
            V(offer3);  // 提供纸和胶水
        P(finish);  // 阻塞自己,防止过量提供材料造成多个吸烟者吸烟(实现吸烟互斥)
    }
}
P1() {  // 只有烟草
    P(offer3);
    V(finish);
}
P2() {  // 只有纸
    P(offer2);
    V(finish);
}
P3() {  // 只有胶水
    P(offer1);
    V(finish);
}

死锁

概念

定义

多个进程因竞争资源而造成的一种僵局（互相等待），若无外力作用，这些进程都将无法向前推进

由于系统中存在一些不可剥夺资源，当两个或两个以上的进程占有自身的资源并请求对方的资源时，会导致每个进程都无法向前推进
产生原因
1. 对系统不可剥夺资源的竞争
2. 进程推进顺序非法
  
  进程请求和释放资源的顺序不当、信号量使用不当
死锁产生的必要条件（即需全部满足才可能死锁）
1. 互斥条件
  
  进程要求对所分配的资源进行排他性使用
  
  即在一段时间内某资源仅为一个进程所占有
2. 不剥夺条件
  
  进程所获得的资源在未使用完之前，不能被其他进程强行夺走，即只能由获得该资源的进程自己主动释放
3. 请求并保持条件
  
  进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源已被其他进程占有，此时请求进程被阻塞，但对自己已获得的资源保持不放
4. 循环等待条件
  
  存在一种进程资源的循环等待链，链中每个进程已获得的资源同时被链中下一个进程所请求
资源分配图含圈（循环等待）而系统又不一定有死锁的原因：同类资源大于 1

若系统中每类资源都只有一个资源，则资源分配图含圈就变成了系统出现死锁的充分必要条件
饥饿 vs 死锁
1. 进入饥饿状态的进程可以只有一个，而因循环等待条件而进入死锁状态的进程却必须大于或等于两个
2. 发生饥饿的进程的状态可能是就绪态（长期得不到处理机），也可能是阻塞态，而发生死锁的进程的状态必定是阻塞态

死锁处理策略

死锁预防

通过设立一些限制条件，破坏产生死锁必要条件中的一个或几个，让死锁无法发生

破坏互斥条件

不太可行
破坏不剥夺条件

当一个已保持某些不可剥夺资源的进程请求新的资源而得不到满足时，它必须释放已保持的所有资源，待以后需要时再申请

实现起来比较复杂：
1. 释放已获得资源可能造成前一阶段工作失效
2. 反复申请、释放资源会增加系统开销，降低系统吞吐量
  
  适用：状态易于保存和恢复的资源（如处理机的寄存器及内存资源），一般不能用于打印机之类的资源
破坏请求并保持条件

预先静态分配方法 —— 进程在运行前一次申请完它所需要的全部资源

所需资源未满足前，不投入运行；运行期间，这些资源归其所有，但不许再提出其他资源请求

实现简单，但缺点也显而易见：
1. 系统资源被严重浪费（有些资源仅在运行初期或快结束时才使用，甚至不使用）
2. 可能会导致饥饿现象，进程迟迟不能开始运行
破坏循环等待条件

顺序资源分配法 —— 系统中的所有资源按种类统一编号，申请时必须以上升的次序（即某进程前面申请过的资源种类以后不能再申请）

系统要求申请进程：
1. 同类资源（同一个编号）一次申请完
2. 申请不同类资源时，按各类设备的编号依次申请
  
  存在问题：
3. 编号必须稳定 → 限制了新类型设备的增加
4. 尽管在为资源编号时已考虑到大多数作业实际使用这些资源的顺序，但也经常会发生作业使用资源的顺序与系统规定顺序不同的情况，造成资源的浪费
5. 按规定次序申请资源的方法必然会限制用户简单、自主地编程

死锁避免

在资源动态分配过程中，防止系统进入不安全状态，以避免发生死锁

安全状态：至少有一个资源分配序列不会导致死锁

不安全状态：系统中不存在任何一个安全序列，使得所有进程都能够运行完

不安全状态 ≠ 死锁状态，不安全状态 ≠ 死锁不可避免，安全状态 = 可避免死锁
关于“不安全状态 ≠ 死锁不可避免”的一个解释：有的进程获取了一部分资源之后，并不是一定会在获得所需要的所有资源之后才会释放之前所占用的资源

死锁状态一定是不安全状态，安全状态不可能成为死锁状态
银行家算法（一种死锁避免算法）

主要思想是避免系统进入不安全状态
1. 数据结构描述
- 可利用资源向量 Available
- 最大需求矩阵 Max
- 分配矩阵 Allocation
- 需求矩阵 Need
  
  Need = Max - Allocation
1. 算法描述
- 进程请求不超过其 Need，继续；否则出错
- 进程请求不超过 Available，继续；否则让该进程等待
- 系统进行试探性分配（设定分配后为 T 时刻）
- 系统执行安全性算法，检测 T 时刻系统是否处于安全状态。若是，则正式分配；若不是，则分配作废，让该进程等待
1. 安全性算法（银行家算法的核心）
- 找 T 时刻 Available 能满足 Need 的不在安全序列的进程，将该进程 Allocation 加到 Available，然后将其放进安全序列
- 循环执行上一步，若到最后所有进程都能在安全序列中，则 T 时刻处于安全状态

死锁检测和解除

不采取任何限制性措施，允许进程在运行过程中发生死锁，只检测当前系统有没有发生死锁，若有则采取措施解除死锁

资源分配图
死锁定理

系统状态 S 为死锁状态的条件是：当且仅当 S 状态的资源分配图是不可完全简化的

资源分配图的简化：找出既不阻塞又不孤立的进程（即该进程申请的资源够给它的），消去它所有的请求边和分配边，使之成为孤立的结点。若能消去图中所有的边，则称该图是可完全简化的
死锁解除
1. 资源剥夺法
  
  挂起某些死锁进程，并抢占它的资源，将这些资源分配给其他的死锁进程
  但应防止被挂起的进程长时间得不到资源而处于资源匮乏的状态
2. 撤销进程法
  
  强制撤销部分甚至全部死锁进程并剥夺这些进程的资源
  
  撤销的原则可以按进程优先级和撤销进程代价的高低进行
3. 进程回退法
  
  让一或多个进程回退到足以回避死锁的地步，进程回退时自愿释放资源而非被剥夺
  
  要求系统保持进程的历史信息，设置还原点

进程与线程

进程的概念和特征

进程的状态与转换

进程控制

创建

终止

阻塞和唤醒

进程的组成

进程控制块 PCB

程序段

数据段

进程间通信 IPC

共享存储

消息传递

管道通信

线程概念和多线程模型

基本概念

线程的实现方式

内核级线程 KLT (Kernel-Level Thread)

用户级线程 ULT (User-Level Thread)

组合方式 ULT/KST

多线程模型

线程的组织与控制

处理机调度

调度的概念

调度的目标

调度的实现

调度程序/调度器

进程调度方式

进程调度时机

线程的调度

典型的调度算法

上下文切换

进程上下文切换

线程上下文切换

中断上下文切换

系统调用上下文切换/模式切换

同步与互斥

进程同步的基本概念

实现临界区互斥的基本方法

软件实现方法（标志）

硬件实现方法（低级方法/元方法）

互斥锁 mutex lock

信号量

管程 monitor

经典同步问题

生产者-消费者问题

读者-写者问题

哲学家进餐问题

吸烟者问题

死锁

概念

死锁处理策略

死锁预防

死锁避免

死锁检测和解除