第二章进程与线程

第一节进程与线程

「进程」进程的概念

进程	解释
引入原因	描述和控制程序的并发执行
定义	进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位
构成	进程控制块PCB 程序段（能被进程调度程序调度到CPU 执行的程序代码段）数据段（一个进程的数据段，可以是进程对应的程序加工处理的原始数据）
进程实体与进程的区别	进程实体（进程映像）是静态的，进程是动态的

TIP

PCB是进程存在的唯一标志

「进程」进程的特征

进程的特征
动态性	进程是程序的一次执行，具有动态产生、变化、消亡的性质是进程最基本的特征
并发性	指多个进程实体同存于内存中，一段时间内同时运行
独立性	指进程实体是一个能独立运行、获得资源、接受调度的基本单位
异步性	进程相互制约，各自独立，推进速度不可预知，因此操作系统需要进程同步机制

「进程」进程的状态

进程的状态	状态描述
运行态	进程正在运行单处理机中，只能有一个进程在运行
就绪态	得到除处理机的一切资源，有处理机立刻执行
阻塞态（等待态）	缺少资源，有处理机也无法运行系统将阻塞态进程排成队列
创建态	进程正在被创建，尚未转到就绪态
终止态	结束进程时，系统将进程置为终止态，等待资源释放和回收

「进程」进程的状态转换

进程状态转换	触发条件	主动 OR 被动
就绪态 $\to$ 运行态	获得处理机资源
运行态 $\to$ 就绪态	时间片用完，让出处理机给高优先级进程让出处理机
运行态 $\to$ 阻塞态	请求资源，等待事件（IO）发生	主动
阻塞态 $\to$ 就绪态	请求的事件（IO结束）发生	被动，需要其他进程协助

「PCB」PCB 的组成

进程控制块（Process Control Block，PCB）

进程控制块（PCB）
功能	使参与并发执行的每个程序(含数据)都能独立地运行
包含的内容	处理机上下文：进程被切换时，处理机状态信息都必须保存在相应的PCB 中，以便在该进程重新执行时，能从断点继续执行

「PCB」PCB 与进程的关系

PCB的调用
PCB & 系统	系统用PCB描述进程的基本情况和运行状态，进而控制和管理进程系统只能通过PCB感知到进程的存在
PCB & 创建进程	创建进程实体中的PCB，使其常驻内存
PCB & 撤销进程	撤销进程中的PCB
PCB & 进程	PCB是进程存在的唯一标志
PCB & 进程调度	根据其PCB 中所保存的处理机状态信息，设置该进程恢复运行的现场根据其PCB 中的程序和数据的内存始址，找到其程序和数据

「PCB」PCB 的组织方式

PCB组织方式
链接方式	将同一状态的PCB 链接成一个队列，不同状态对应不同的队列
索引方式	将同一状态的进程组织在一个索引表中，索引表的表项指向相应的PCB

「进程」进程的创建过程

进程的创建过程（创建原语）

OS给新进程分配唯一的进程标识号，申请一个空白PCB（PCB有限）
分配进程所需资源
- 资源足够：进程转入就绪态，插入就绪队列
- 资源不足，创建工作未完成，进程状态为创建态
向 PCB 中填写用于控制和管理进程的信息（初始化处理机状态信息等）
插入就绪队列，等待调度

进程中的父与子

允许一个进程创建另一个进程，创建者为父进程，被创建者为子进程
子继承父所有资源，子被撤销，资源全部归还给父
撤销父，子全部撤销

「进程」进程的终止过程

引起进程终止的三种事件

正常结束
异常结束
外界干预

进程终止的过程（终止原语）

根据被终止进程的标识符，检索进程PCB，读出进程状态
1. 运行态，终止，处理机资源给其他进程
2. 有子孙进程，终止
全部资源归还给父进程或操作系统
在队列（链表）删除该进程PCB

「进程」进程的阻塞与唤醒

阻塞原语执行过程

通过标识号找到要阻塞的进程，读取状态
- 运行态，保护现场，状态改为阻塞态，通知运行
PCB 插入等待队列，处理机资源给其他就绪进程

唤醒原语执行过程

在等待队列中找到相应进程 PCB
PCB 从等待队列移出，置就绪态
PCB 插入就绪队列，等待调度

TIP

何时执行阻塞原语？
- 处于运行态的进程（获得了CPU）期待的事件未发生，才能主动调用阻塞原语进入阻塞态。
何时执行唤醒原语？
- 阻塞态进程期待事件已发生，调用唤醒原语进入就绪态。
阻塞原语与唤醒原语的关系？
- Block 原语和 Wakeup 原语是一对作用刚好相反的原语，必须成对使用，不然会导致程序永远阻塞。

「进程通信」高级、低级通信方式

进程通信是指进程之间的信息交换

低级通信方式
- PV 操作
高级通信方式（较高的效率传输大量数据的通信方式）
- 共享存储
- 消息传递
- 管道通信

「进程高级通信」共享存储

INFO

什么是共享存储？
- 通信进程之间的一块可直接访问（进程空间独立，通过特殊系统调用实现）的空间，通过读写操作进行信息交换
- 读写操作用同步互斥工具（P、V操作）
低级共享方式：基于数据结构的共享
高级共享方式：基于存储区的共享
操作系统：只提供共享存储空间和同步互斥工具

「进程高级通信」消息传递

INFO

进程间的数据交换以格式化的消息(Message)为单位
进程通过系统提供的发送消息和接收消息两个原语进行数据交换
直接通信方式
- 发送进程把消息发送给接收进程
- 消息挂在接收进程的消息缓冲队列上
- 接收进程从消息缓冲队列中取得消息
间接通信方式（广泛用于计算机网络中）
- 发送进程把消息发送到某个中间实体（信箱）
- 接收进程从中间实体（信箱）取得消息

「进程高级通信」管道通信

INFO

两个进程按生产者-消费者方式进行通信，生产者向管道的一端写，消费者从管道的另一端读
管道性质
- 管道消息先进先出。
- 管道数据空，读进程阻塞，数据写入时唤醒。
- 管道数据满，写进程阻塞，数据读出时唤醒。
管道机制协调能力：互斥、同步、确定对方存在。
管道本质：一种文件，和一般文件不同
- 管道会限制大小：管道文件是固定大小缓冲区，写满则写进程阻塞。
- 读进程可能比写进成快：管道空，读进程阻塞，解决了read()调用返回文件结束问题。

TIP

从管道读数据是一次性操作，数据一旦被读取，就释放空间以便写更多数据。
普通管道只允许单向通信，若要实现父子进程双向通信，则需要定义两个管道。

「线程」线程的概念

INFO

引入进程的目的是更好地使多道程序并发执行。
引入线程的目的则是减小程序并发执行时的时空开销，提高并发性能。
线程是什么？
- "轻量级进程"，一个基本的 CPU 执行单元
- 程序执行流的最小单元
- 进程中的一个实体，是被系统独立调度和分派的基本单位
线程有什么？
- 不拥有自己的系统资源，但共享进程所拥有的全部资源
- 可以创建和撤销另一个线程的能力
- 同一进程中的多个线程之间并发执行的能力
- 就绪、阻塞和运行三种基本状态

「线程」线程与进程的比较

	线程	进程
调度	同一进程中，线程切换的代价远低于进程	每次调度都要进行上下文切换，开销较大
并发性	进程之间可以并发执行进程中的之间可以并发执行并发性很高	进程之间可以并发执行并发性高
拥有资源	1. 线程不拥有系统资源(仅有一点必不可少、能保证独立运行的资源) 2. 线程共享进程的系统资源，同一进程的所有线程都具有相同的地址空间	是系统中拥有资源的基本单位
独立性	进程中的线程对其他进程不可见	每个进程都拥有独立的地址空间和资源
系统开销	线程切换时只需保存和设置少量寄存器内容系统开销很小	1. 创建或撤销进程时，系统都要为之分配或回收进程控制块 PCB及其他资源 2. 进程切换时，涉及进程上下文的切换系统开销大
支持多处理机系统	进程中的多个线程可分配到多个处理机上执行	不管有多少处理机，进程只能运行在一个处理机上

「线程」线程的属性

TIP

多线程操作系统中的进程已不再是一个基本的执行实体，但它仍具有与执行相关的状态。
所谓进程处于执行状态，实际上是指该进程中的某线程正在执行。

线程的主要属性

线程不拥有系统资源，每个线程都有唯一的标识符和一个线程控制块（记录线程执行状态）
不同线程可执行相同程序（同一程序不同用户调用）
同一进程的各线程共享进程拥有的所有资源。
线程是处理机独立调度单位，可并发执行。
线程创建后，开始了生命周期，直到终止。

「线程」线程的状态与转换

线程之间存在共享资源与合作的制约关系，故运行时也存在间断性，存在三种基本状态。

三种基本状态（和进程基本状态转换相同）

执行状态：线程已获得处理机而正在运行。
就绪状态：线程已具备各种执行条件，只需再获得 CPU 便可立即执行。
阻塞状态：线程在执行中因某事件受阻而处于暂停状态。

「线程」线程的组织和控制

线程控制块(TCB)

系统也为每个线程配置一个线程控制块 TCB，用于记录控制和管理线程的信息
线程控制块构成：
- 线程标识符
- 一组寄存器（包括程序计数器、状态寄存器和通用寄存器）
- 线程运行状态（用于描述线程正处于何种状态）
- 优先级
- 线程专有存储区（线程切换时用于保存现场等）
- 堆栈指针（用于过程调用时保存局部变量及返回地址等）

线程的创建

操作系统中有用于创建线程和终止线程的函数（或系统调用）。

用户程序启动时，通常仅有一个称为“初始化线程”的线程正在执行，用其创建新线程。
利用一个线程创建函数，并提供相应的参数，如指向线程主程序的入口指针、堆栈的大小、线程优先级等。
线程创建函数执行完后，将返回一个线程标识符。

线程的终止

线程终止时，由终止线程调用函数执行终止操作。
系统线程等线程，一旦创建便不会终止。

线程被终止后，保留所占有资源。
当进程中其他线程执行分离函数后，被终止进程才与资源分离。

被终止进程未释放资源时，仍可被其他线程调用。

「线程」线程的实现方式

TIP

系统进程还是用户进程，都是在操作系统内核的支持下运行的，与内核紧密相关。

用户级线程(ULT)

线程管理由应用程序在用户空间中完成，内核意识不到线程的存在。
调度以进程为单位进行，对线程不公平。
- 假设进程 A 包含 1 个用户级线程，进程 B 包含 100 个用户级线程，进程 A 中线程的运行时间将是进程 B 中各线程运行时间的 100 倍。
优点
- 线程切换不需要换到内核空间，节省切换开销。
- 不同进程可对自己线程选择不同调度算法。
- 用户级线程实现与操作系统无关，对线程管理代码属于用户程序。
缺点
- 线程执行系统调用，进程内所有线程均被阻塞。
- 不能发挥多处理机优势（内核只会给进程分配一个 CPU，只有一个线程能执行）

内核级线程(KLT)

内核级线程在内核的支持下运行，线程管理在内核空间内实现。
内核空间为每个内核级线程设置一个线程控制块，内核根据该控制块感知并控制线程
优点
- 能发挥多处理机优势（内核能同时调度同一进程中的多个线程并行执行）
- 一线程阻塞，其他线程被内核调度占用处理机。
- 线程具有很小的数据结构和堆栈，切换快，开销小。
- 内核本身也可采用多线程技术，提高效率。
缺点
- 同进程的线程切换，需要从用户态切换到核心态，开销大。
  - 用户进程的线程在用户态运行，而线程调度和管理在内核实现

组合方式

内核支持多个内核级线程的建立、调度和管理
同时允许用户程序建立、调度和管理用户级线程
一些内核级线程对应多个用户级线程，用户级线程通过时分多路复用内核级线程实现。
同一进程中的多个线程可以同时在多处理机上并行执行，且在阻塞一个线程时不需要将整个进程。

「线程」多线程模型

多对一模型（多个用户级线程映射到一个内核级线程）

这些用户线程一般属于一个进程，线程的调度和管理在用户空间完成。
用户线程需要访问内核时，将其映射到一个内核级线程上。每次只允许一个线程进行映射。
优点：线程管理在用户空间进行，效率高。
缺点：
- 一线程阻塞，整个进程阻塞。
- 任何时刻，只有一个线程能够访问内核，多个线程不能同时在多个处理机上运行。

一对一模型（每个用户级线程映射到一个内核级线程）

优点：一线程阻塞，可调度另一线程运行，并发强。
缺点：每创建一个用户线程，需要对应创建一个内核线程，开销大。

多对多模型（将 $n$ 个用户线程映射到 $m$ 个内核级线程上，要求 $n \geq m$ ）

特点
- 克服了多对一模型并发度不高的缺点。
- 克服了一对一模型的一个用户进程占用太多内核级线程而开销太大的缺点。

第二节处理机调度

「调度概念」什么是调度？

为什么需要处理机调度？

因为进程的运行需要处理机，而进程数量大于处理机数量，给进程按一定算法分配处理机的过程为处理机调度。
处理机调度是多道程序操作系统的基石。

「调度概念」调度的层次

一个作业从提交开始直到完成，要经历以下三级调度。

「调度概念」高级调度（作业调度）

INFO

什么是作业调度：
- 作业调度就是作业在内存与辅存的调度。
- 每个作业调入一次、调出一次。

「调度概念」中级调度（内存调度）

INFO

什么是内存调度？
- 存储器管理中的对换功能。
目的：
- 提高内存利用率和系统吞吐量。
过程：
- 暂时不能运行的进程调到外存等待，为挂起态。
- 有条件运行时，中级调度决定哪些进程调入内存，为就绪态，挂就绪队列。

「调度概念」低级调度（进程调度）

INFO

过程：
- 按某种算法在就绪队列选一进程，分配处理机。
- 进程调度频率很高，几十毫秒一次。

「调度概念」三级调度的联系

INFO

作业调度：从外存后备队列调作业进内存，建进程，送就绪队列。
进程调度：就绪队列选进程，改运行态，分配CPU。
中级调度：提高内存利用率，把暂时不能运行的进程挂起来。

「调度性能」CPU 利用率

INFO

CPU 资源昂贵，利用率越高越好、
CPU 利用率计算公式：

C P U 的 利 用 率 = \frac{C P U 有 效 工 作 时 间}{C P U 有 效 工 作 时 间 + C P U 空 闲 等 待 时 间}

系统吞吐量

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

「调度性能」周转时间

INFO

作业提交到作业完成经历的时间。
- 作业等待+就绪队列排队+处理机运行+IO操作 时间的总和。
周转时间 计算方法：

周 转 时 间 = 作 业 完 成 时 间 - 作 业 提 交 时 间

平均周转时间 计算方法：

平 均 周 转 时 间 = \frac{(作 业 1 的 周 转 时 间 + \dots + 作 业 n 的 周 转 时 间)}{n}

带权周转时间 计算方法：

带 权 周 转 时 间 = \frac{作 业 周 转 时 间}{作 业 实 际 运 行 时 间}

平均带权周转时间 计算方法：

平 均 带 权 周 转 时 间 = \frac{(作 业 1 的 带 权 周 转 时 间 + \dots + 作 业 n 的 带 权 周 转 时 间)}{n}

「调度性能」等待时间

INFO

进程处于等待处理机的时间之和。
处理机调度算法影响就绪队列等待时间，不影响作业执行和IO操作时间。
算法的优劣看等待时间长短。

「调度性能」响应时间

INFO

用户提交到系统首次响应所用的时间。
交互系统判断算法优劣用响应时间。

「调度实现」调度程序（调度器）

用于调度和分派CPU的组件，由三部分构成。

排队器：
- 将就绪进程按策略排成队列，便于选择。
- 进程变就绪态，将其插入就绪队列。
分派器：
- 将调度程序选的进程从就绪队列取出，分配CPU。
上下文切换器：
- 两对上下文切换操作（对处理机进行切换时）
  1. 当前进程上下文保存到其PCB中，再装入分派程序上下文。
  2. 移出分派程序上下文，将新选进程CPU现场信息装入处理机的各个响应寄存器。
1. 软件上下文切换
  - 需要执行大量 load 和 store 指令，来保存寄存器内容，费时间。
2. 硬件上下文切换
  - 用两组寄存器（一组内核用，一组用户用）
  - 切换时，只需改变指针，指向当前寄存器组。

「调度」时机、切换与过程

操作系统调度顺序（三步）

请求调度事件发生
运行调度程序，调度新的就绪进程
进行进程切换

不能进行进程调度与切换的状态（内核程序运行中，不一定能立刻切换）

处理中断的过程中（过程复杂，难以中断；中断属于系统操作）
进程在操作系统的内核临界区（临界区，独占式访问，加锁）
其他需要完全屏蔽中断的原子操作过程中（加锁，解锁，中断现场保护等）

应该进行进程调度与切换的情况

发生引起调度条件且当前进程无法继续运行下去时
中断处理结束或自陷处理结束后，返回被中断进程的用户态程序执行现场前。置请求调度标志，即可马上进行进程调度与切换。

「调度」进程调度方式

两种调度方式

非抢占式调度方式（非剥夺）：实现简单，系统开销小。
抢占式调度方式（剥夺）：吞吐率、响应效率提高；抢占遵循一定原则。

「调度」闲逛进程

什么是闲逛进程？

进程切换，若无就绪进程，会调度闲逛进程(idle)进行。
优先级最低，若有进程就绪，让出处理机。
不需要除CPU以外的资源，不会被阻塞。

「调度」两种进程的调度

INFO

用户级线程调度
- 内核不知道线程存在，则选一个进程分配处理机资源。
- 进程决定线程处理机资源分配。
内核级线程调度
- 内核选定一个线程分配处理机资源，超出挂起该线程，不考虑属于哪个进程。

用户级、内核级线程切换的比较

用户级线程切换：在同一进程中进行，进需要少量的机器指令
内核级线程切换：需要完整的上下文切换、修改内存影响、使高速缓存失效，导致高延迟。

「调度算法」先来先服务（FCFS）

INFO

算法原理
- 选择后备队列中最先进入队列的一个或多个作业。
先来先服务调度算法属于不可剥夺算法。
FCFS 特点：
- 算法简单，效率低。
- 长作业有利，短作业不利（对比 SJF 和高响应比）。
- 有利于 CPU 繁忙型，不利于 IO 繁忙型。

「调度算法」短作业优先（SJF）

INFO

算法原理
- 从后备队列中选择一个或多个估计运行时间最短的作业，调入内存。
SJF 特点：
- 长作业不利
- 紧迫性作业不利
- SFJ 不一定能真正做到短作业优先（用户会改变作业估计运行时间）
- 平均等待时间，平均周转时间最少

「调度算法」优先级调度算法

INFO

可用于作业调度和进程调度。
优先级描述作业的紧迫程度。
算法原理
- 从后备队列选择一个或多个优先级最高的作业，调入内存。

优先级调度算法分两种

抢占式优先级调度算法
非抢占式优先级调度算法

优先级调度算法分类（根据进程创建后优先级是否可以改变）

静态优先级：根据进程类型、对资源要求、用户要求等。
动态优先级：根据CPU占有时间长短，就绪进程等待CPU时间长短等。

进程优先级设置原则

系统进程 > 用户进程
交互型进程（前台） > 非交互型进程（后台）
IO型进程 > 计算型进程

「调度算法」高响应比优先

INFO

用于作业调度，FCFS和SJF的综合平衡

响应比的变化规律

响 应 比 R_{p} = \frac{等 待 时 间 + 要 求 服 务 时 间}{要 求 服 务 时 间}

由公式知：
- 等待时间相同，服务时间越短，响应比越高，有利于短作业。
- 服务时间相同，等待时间决定作业响应比。
- 响应比随等待时间变长而提高，可克服”饥饿“现象。

「调度算法」时间片轮转

INFO

用于分时系统。
进程排成就绪队列，进程被分配时间片，用完后剥夺处理机，重新排队。

时间片轮转中时间片的长与短

时间片够大，所有进程都能在一个时间片内完成，退化为先来先服务。
时间片很小，处理机在进程间频繁切换，开销大。

「调度算法」多级队列

INFO

不同于前述算法的一条就绪队列，多级队列将不同性质的进程分配到不同就绪队列。
队列中进程与队列均可设置优先级。
在多处理机中，可每个处理机一条就绪队列，使用不同调度策略，便于调度。

「调度算法」多级反馈队列

融合了前几种算法的优点

多级反馈队列 = 时间片轮转 + 优先级
动态调整进程优先级和时间片大小

多级反馈队列的实现思想

多个就绪队列不同优先级。
优先级高的队列时间片越小。
每个队列都采用先来先服务。（n级队列采用时间片轮转）
按队列优先级调度。（1级队列空，调度2级队列运行）

多级反馈队列的优势

终端型作业：短作业优先。
短批处理作业：周转时间短。
长批处理作业：不会长时间无法获得处理机。

「调度算法」常见调度算法的特点

「进程切换」上下文切换

INFO

什么是上下文切换？
- 进程切换（处理机转移）时需要保存当前进程状态并恢复另一进程的状态。
什么是上下文？
- 某一时刻 CPU 寄存器和程序计数器的内容。
进程切换时会发生什么？
- 内核将旧进程状态保存在其PCB中，加载新进程上下文。

上下文切换流程

挂起进程，保存CPU的程序计数器和寄存器内容。
更新PCB信息。
将进程PCB放入响应队列（就绪、阻塞等）。
选择另一进程执行，更新其PCB。
跳转到新进程PCB程序计数器所指向的位置执行。
恢复处理机上下文。

上下文切换的消耗

通常为计算密集型，切换需要很多时间。
若处理器提供多个寄存器组，则上下文切换变成改变当前寄存器组的指针。

上下文切换与模式切换

模式切换与上下文切换不同
模式切换：用户态和内核态之间的切换。
上下文切换：只发生在内核态。

「调度算法」各种调度算法的汇总

INFO

先来先服务、短作业优先
- 无法保证及时接受和处理问题。
优先级
- 紧急任务有更高的优先级，适合实时操作系统。
高响应比优先、时间片轮转、多级反馈队列
- 保证每个任务一定时间内能分到时间片，轮流占用CPU，适合分时操作系统。

第三节同步与互斥

「基本概念」临界资源

什么是临界资源？

一次仅有一个进程能够使用的资源
访问必须互斥的进行

临界资源的访问过程（四个部分）

进入区：进程进入临界区访问临界资源之前，需要进入进入区设置标志，以互斥访问。
临界区：进程中访问临界资源的那份代码。
退出区：将正在访问临界区的标志清除。
剩余区：代码中的剩余部分。

「基本概念」同步

什么是同步？

称为直接制约关系。
两个或多个进程因为合作需要在某个位置等待其他进程的数据等产生的制约关系。

「基本概念」互斥

什么是互斥？

称为间接制约关系。
一个进程进入临界区使用临界资源时，另一进程必须等待。

禁止两个进程同时进入临界区，同步机制遵循准则：

空闲让进。
忙则等待。
有限等待。
让权等待。

「临界区互斥方法」软件实现

在进入区设置并检查标志来标明是否有进程进入临界区。
若临界区有进程，后续进程在进入区循环检查并等待，直到临界区进程退出。

算法一：单标志法

算法二：双标志法先检查

算法三：双标志法后检查

算法四：Peterson's Algorithm

「临界区互斥方法」硬件实现

通过硬件支持实现临界段问题的方法称为低级方法（元方法）。

中断屏蔽方法

硬件指令方法 TestAndSet指令

硬件指令方法 Swap指令

硬件指令方法的优缺点

硬件方法的优点
- 适用于任意数目的进程，而不管是单处理机还是多处理机
- 简单、容易验证其正确性。
- 可以支持进程内有多个临界区，只需为每个临界区设立一个布尔变量。
硬件方法的缺点
- 进程等待进入临界区时要耗费处理机时间，不能实现让权等待。
- 从等待进程中随机选择一个进入临界区，有的进程可能一直选不上，从而导致“饥饿”现象。

「互斥」互斥锁(mutex lock)

什么是互斥锁？

解决临界区最简单的工具。
进程进入临界区获得(acquire())锁，退出临界区释放(release())锁。
函数acquire()，release()是原子操作，互斥锁采用硬件机制实现。

互斥锁的缺点

忙等待
- 其他进程进入已有进程的临界区时 ♻️循环调用 acquire()函数，浪费CPU周期。

「信号量」什么是信号量？

只能被两个标准的原语 wait(S) 和 signal(S) 访问，也可记为 P操作 和 V操作。
P 操作：申请（使用）资源。
V 操作：释放（产生）资源。

「信号量」整形信号量

「信号量」记录型信号量

不存在“忙等”现象的进程同步机制。
用整形变量 value 代表资源数目，用进程链表链接所有等待该资源的进程。

记录型信号量的描述

「信号量」实现同步

利用记录型信号量实现同步

「信号量」实现进程互斥

利用记录型信号量实现进程互斥

信号量互斥原理
- $S$ 为实现进程 $P_{1}, P_{2}$ 互斥的信号量，由于每次只允许一个进程进入临界区，所以 $S$ 的初值应为 $1$ (即可用资源数为 $1$ )。
- 任意一个进程要进入没有进程的临界区，执行 $P$ 操作，把 $S$ 减为 0，进入临界区。
- 当有进程存在于临界区时， $S$ 的值为 $0$ ，再有进程要进入临界区，执行 $P$ 操作会被阻塞，直至在临界区中的进程退出，这样便实现了临界区的互斥。
只需把临界区置于 $P (S)$ 和 $V (S)$ 之间，即可实现两个进程对临界资源的互斥访问。
在互斥问题中， $P, V$ 操作要紧夹使用互斥资源的那个行为，中间不能有其他冗余代码。

「信号量」实现前驱关系

利用记录型信号量实现前驱关系

$S_{1}, S_{2}, \dots$ 为程序段，设置 $a_{1}, a_{2}, \dots$ 等信号量保证运行顺序。

「信号量」进程同步步骤分析

分析进程同步、互斥的方法及步骤

关系分析：找出问题中的进程数，分析进程之间的同步、互斥关系。
整理思路：根据进程操作流程确定 $P, V$ 操作大致顺序。
设置信号量：根据上两步，设置需要的信号量，确定初值。

「管程」定义

管程出现的原因

在信号量机制中，每个访问临界区的进程都自备 $P, V$ 操作，操作不当容易死锁，引入管程来保证进程互斥，不需要程序员自己实现，降低死锁可能。

什么是管程？

管程的定义
- 能够代表共享资源的数据结构，并能统一管理对共享资源的所有访问（申请及释放操作），实现进程互斥的资源管理程序。
管程提供条件变量，程序员可灵活实现进程同步。

管程的组成

管程的名称
局部于管程内部的共享数据结构说明
对共享资源（数据结构）进行操作的一组过程（申请、释放函数）
对局部于管程内部的共享数据设置初始值的语句

管程与类的相似之处

管程把共享资源的操作封装起来，调用管程内过程实现资源访问。
每次仅允许一个进入管程，实现进程互斥。

「管程」条件变量

什么是条件变量？

信号量有 $P, V$ 操作，进程会因为 P 操作而陷入循环等待，因为 V 操作被唤醒。
条件变量就是在信号量的基础上添加条件，比如
- x.wait()：因为 x 条件不满足而陷入循环等待，则调用管程进程调用 x.wait() 把自己插入循环等待队列。
- x.signal()：x 条件发生了变化，调用 x.signal() 唤醒因为 x 条件而被阻塞进程。

条件变量和信号量的比较

相似点
- 条件变量的 wait/signal 操作类似于信号量的 P/V 操作，可以实现进程的阻塞/唤醒。
不同点
- 条件变量是“没有值”的，仅实现了“排队等待”功能；
- 而信号量是“有值”的，信号量的值反映了剩余资源数，而在管程中，剩余资源数用共享数据结构记录。

「经典同步问题」生产者消费者问题

问题描述

一组生产者进程和一组消费者进程共享一个初始为空、大小为 n 的缓冲区，只有缓冲区没满时，生产者才能把消息放入缓冲区，否则必须等待；
只有缓冲区不空时，消费者才能从中取出消息，否则必须等待。
由于缓冲区是临界资源，它只允许一个生产者放入消息，或一个消费者从中取出消息。

问题分析

关系分析
1. 生产者和消费者对缓冲区互斥访问是互斥关系，同时生产者和消费者又是相互协作的关系，只有生产者生产之后，消费者才能消费，它们也是同步关系。
整理思路
1. 这里比较简单，只有生产者和消费者两个进程，正好是这两个进程存在着互斥关系和同步关系。那么需要解决的是互斥和同步 $P, V$ 操作的位置。
信号量设置
1. 信号量 mutex 作为互斥信号量，用于控制互斥访问缓冲池，互斥信号量初值为 1；
2. 信号量 full 用于记录当前缓冲池中的“满”缓冲区数，初值为 0。
3. 信号量 empty 用于记录当前缓冲池中的“空”缓冲区数，初值为 n。

生产者-消费者进程的描述

「经典同步问题」读者写者问题

「经典同步问题」哲学家进餐问题

「经典同步问题」吸烟者问题

第四节死锁

「死锁」死锁产生的原因

两条原因

系统资源的竞争
进程推进顺序非法

「死锁」死锁产生的必要条件

四个条件

互斥条件
不剥夺条件
保持并请求条件
循环等待条件

「死锁」死锁的处理策略

三种处理策略

死锁预防
避免死锁
死锁的检测及解除

死锁处理策略的比较

预防死锁和避免死锁为事先预防策略，条件严格，实现简单，效率低。

「死锁预防」死锁预防条件

三个条件

破坏互斥条件
破坏不剥夺条件
破坏保持并请求条件
破坏循环等待条件

「死锁避免」系统安全条件

什么是系统安全？

系统安全条件：
- 允许进程动态申请资源，系统分配之前，先计算本次分配安全性。

注意事项

并非所有不安全状态都是死锁状态
- 当系统进入不安全状态后，可能进入死锁状态。
系统处于安全状态，可避免死锁。

「死锁避免」银行家算法

「死锁检测与解除」资源分配图

系统死锁可用资源分配图解决。

资源分配图中符号含义

圆代表一个进程，框代表一类资源。
框中的一个圆代表一类资源中的一个资源。
进程到资源的有效边代表请求边，表示进程申请的资源。
资源到进程的边代表分配边，表示资源分配给了进程。

「死锁检测与解除」死锁定理

简化资源分配图可检测系统状态 $S$ 是否为死锁状态

资源分配图的简化方法

先运行进程 $P_{1}$ ， $P_{1}$ 申请右侧框中的一个资源（成功），获得左侧框中两个资源分配，完成运行后释放 $P_{1}$ 所有资源，如图 $(b)$ 。
依次运行。

什么是死锁定理？

S 为死锁的条件是当且仅当 S 状态的资源分配图是不可完全简化的，该条件为死锁定理。

「死锁检测与解除」死锁解除

死锁解除的三种方法

资源剥夺法：挂起死锁进程，资源给其他进程。
撤销进程法：强制撤销死锁进程并剥夺资源。
进程回退法：将进程回退到回避死锁的状况。

第二章 进程与线程 ​

第一节 进程与线程 ​

「进程」进程的概念 ​

「进程」进程的特征 ​

「进程」进程的状态 ​

「进程」进程的状态转换 ​

「PCB」PCB 的组成 ​

「PCB」PCB 与进程的关系 ​

「PCB」PCB 的组织方式 ​

「进程」进程的创建过程 ​

「进程」进程的终止过程 ​

「进程」进程的阻塞与唤醒 ​

「进程通信」高级、低级通信方式 ​

「进程高级通信」共享存储 ​

「进程高级通信」消息传递 ​

「进程高级通信」管道通信 ​

「线程」线程的概念 ​

「线程」线程与进程的比较 ​

「线程」线程的属性 ​

「线程」线程的状态与转换 ​

「线程」线程的组织和控制 ​

「线程」线程的实现方式 ​

「线程」多线程模型 ​

第二节 处理机调度 ​

「调度概念」什么是调度？ ​

「调度概念」调度的层次 ​

「调度概念」高级调度（作业调度） ​

「调度概念」中级调度（内存调度） ​

「调度概念」低级调度（进程调度） ​

「调度概念」三级调度的联系 ​

「调度性能」CPU 利用率 ​

「调度性能」周转时间 ​

「调度性能」等待时间 ​

「调度性能」响应时间 ​

「调度实现」调度程序（调度器） ​

「调度」 时机、切换与过程 ​

「调度」进程调度方式 ​

「调度」闲逛进程 ​

「调度」两种进程的调度 ​

「调度算法」先来先服务（FCFS） ​

「调度算法」短作业优先（SJF） ​

「调度算法」优先级调度算法 ​

「调度算法」高响应比优先 ​

「调度算法」时间片轮转 ​

「调度算法」多级队列 ​

「调度算法」多级反馈队列 ​

「调度算法」常见调度算法的特点 ​

「进程切换」上下文切换 ​

「调度算法」各种调度算法的汇总 ​

第三节 同步与互斥 ​

「基本概念」临界资源 ​

「基本概念」同步 ​

「基本概念」互斥 ​

「临界区互斥方法」软件实现 ​

「临界区互斥方法」硬件实现 ​

「互斥」互斥锁(mutex lock) ​

「信号量」什么是信号量？ ​

「信号量」整形信号量 ​

「信号量」记录型信号量 ​

「信号量」实现同步 ​

「信号量」实现进程互斥 ​

「信号量」实现前驱关系 ​

「信号量」进程同步步骤分析 ​

「管程」定义 ​

「管程」条件变量 ​

「经典同步问题」生产者消费者问题 ​

「经典同步问题」读者写者问题 ​

「经典同步问题」哲学家进餐问题 ​

「经典同步问题」吸烟者问题 ​

第四节 死锁 ​

「死锁」死锁产生的原因 ​

「死锁」死锁产生的必要条件 ​

「死锁」死锁的处理策略 ​

「死锁预防」死锁预防条件 ​

「死锁避免」系统安全条件 ​

「死锁避免」银行家算法 ​

「死锁检测与解除」资源分配图 ​

「死锁检测与解除」死锁定理 ​

「死锁检测与解除」死锁解除 ​

第二章进程与线程

第一节进程与线程

「进程」进程的概念

「进程」进程的特征

「进程」进程的状态

「进程」进程的状态转换

「PCB」PCB 的组成

「PCB」PCB 与进程的关系

「PCB」PCB 的组织方式

「进程」进程的创建过程

「进程」进程的终止过程

「进程」进程的阻塞与唤醒

「进程通信」高级、低级通信方式

「进程高级通信」共享存储

「进程高级通信」消息传递

「进程高级通信」管道通信

「线程」线程的概念

「线程」线程与进程的比较

「线程」线程的属性

「线程」线程的状态与转换

「线程」线程的组织和控制

「线程」线程的实现方式

「线程」多线程模型

第二节处理机调度

「调度概念」什么是调度？

「调度概念」调度的层次

「调度概念」高级调度（作业调度）

「调度概念」中级调度（内存调度）

「调度概念」低级调度（进程调度）

「调度概念」三级调度的联系

「调度性能」CPU 利用率

「调度性能」周转时间

「调度性能」等待时间

「调度性能」响应时间

「调度实现」调度程序（调度器）

「调度」时机、切换与过程

「调度」进程调度方式

「调度」闲逛进程

「调度」两种进程的调度

「调度算法」先来先服务（FCFS）

「调度算法」短作业优先（SJF）

「调度算法」优先级调度算法

「调度算法」高响应比优先

「调度算法」时间片轮转

「调度算法」多级队列

「调度算法」多级反馈队列

「调度算法」常见调度算法的特点

「进程切换」上下文切换

「调度算法」各种调度算法的汇总

第三节同步与互斥

「基本概念」临界资源

「基本概念」同步

「基本概念」互斥

「临界区互斥方法」软件实现

「临界区互斥方法」硬件实现

「互斥」互斥锁(mutex lock)

「信号量」什么是信号量？

「信号量」整形信号量

「信号量」记录型信号量

「信号量」实现同步

「信号量」实现进程互斥

「信号量」实现前驱关系

「信号量」进程同步步骤分析

「管程」定义

「管程」条件变量

「经典同步问题」生产者消费者问题

「经典同步问题」读者写者问题

「经典同步问题」哲学家进餐问题

「经典同步问题」吸烟者问题

第四节死锁

「死锁」死锁产生的原因

「死锁」死锁产生的必要条件

「死锁」死锁的处理策略

「死锁预防」死锁预防条件

「死锁避免」系统安全条件

「死锁避免」银行家算法

「死锁检测与解除」资源分配图

「死锁检测与解除」死锁定理

「死锁检测与解除」死锁解除