本篇博客是考研期间学习王道课程传送门的笔记，以及一整年里对 操作系统 知识点的理解的总结。希望对新一届的计算机考研人提供帮助！！！
关于对 “进程与线程” 章节知识点总结的十分全面，涵括了《操作系统》课程里的全部要点（本人来来回回过了三遍视频），其中还陆陆续续补充了许多内容，所以读者可以相信本篇博客对于考研操作系统 “进程与线程” 章节知识点的正确性与全面性；但如果还有自主命题的学校，还需额外读者自行再观看对应学校的自主命题材料。

食用说明书：
第一遍学习王道课程时，我的笔记只有标题和截图，后来复习发现看只看图片，并不能很快的了解截图中要重点表达的知识点。
在第二遍复习中，我给每一张截图中标记了重点，以及每张图片上方总结了该图片 对应的知识点 以及自己的思考。
最后第三遍，查漏补缺。
所以，我把目录放在博客的前面，就是希望读者可以结合目录结构去更好的学习知识点，之后冲刺复习阶段脑海里可以浮现出该知识结构，做到对每一个知识点熟稔于心！
请读者放心！目录展示的知识点结构是十分合理的，可以放心使用该结构去记忆学习！
注意(⊙o⊙)！，每张图片上面的文字，都是该图对应的知识点总结，方便读者更快理解图片内容。

《操作系统》第2章进程与线程

【考纲内容】 王道 P48 ~ 176

(一) 进程与线程

网课耗时：2 h

进程与线程的基本概念；
进程 / 线程的状态与转换；
线程的实现：内核支持的线程，线程库支持的线程；
进程与线程的组织与控制；
进程间通信：共享内存，信息传递，管道；

(二) CPU调度与上下文切换

网课耗时：2 h

调度的基本概念；
调度的目标；
调度的实现：调度器 / 调度程序，调度的时机与调度方式（抢占式 / 非抢占式），闲逛进程，内核级线程与用户及线程调度；
典型调度算法：先来先服务调度算法；短作业（短进程、短线程）优先调度算法，时间片轮转调度算法，优先级调度算法，高响应比优先调度算法，多级队列调度算法，多级反馈队列调度算法；
上下文及其切换机制

(三) 同步与互斥

网课耗时：3.5 h

同步与互斥的基本概念
基本的实现方式：软件方法、硬件方法；
锁；信号量；条件变量；
经典同步问题：生产者-消费者问题，读者-写者问题；哲学家进餐问题；

(四) 死锁

网课耗时：1 h

死锁的基本概念
死锁预防；
死锁避免；
死锁检测和解除；

重点

知识点	选择题	综合题
进程的概念	✔
进程调度	✔	✔
信号量机制实现同步和互斥	✔	✔
进程死锁	✔	✔

2.1 进程与线程

2.1.1 进程的描述

在这里插入图片描述

1. 进程的概念

① 进程是什么？

答：进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位；

其中，==进程实体（进程映像）==包括：PCB + 程序段 + 数据段三部分；

在这里插入图片描述

2. 进程的组成

进程的组成部分：==PCB - 进程控制块、==程序段、数据段；

创建进程的本质是创建进程实体的 PCB ；
撤消进程的实质是撤消进程实体的 PCB ；

在这里插入图片描述

【问题】程序是如何运行的？

在这里插入图片描述

程序编译流程如下：

编译：把源程序（高级语言）翻译成目标程序（机器语言）；
连接：将目标文件连接成可执行文件；
装入 - 执行；

很重要的一句话：进程实体反应了进程在动态执行的某一时刻状态 (进程实体静态，进程动态)；

在这里插入图片描述

进程的三大组成部分：PCB + 程序段 + 数据段；

进程的定义：进程是进程实体的 ==运行过程，==是系统进程资源分配和调度的一个独立单位；

==进程调度，==就是指让哪个进程在CPU上运行；

在这里插入图片描述

3. 进程的特征

在这里插入图片描述

小结

本节的知识点就三部分：进程的概念、组成、特征；

在这里插入图片描述

2.1.2 进程的状态与转换

在这里插入图片描述

1. 进程的状态

① 创建态 + ② 就绪态

创建状态的步骤：

申请空白PCB；
向空白PCB中填写相关信息；
为该进程分配除CPU以外必要的资源；

已就绪的进程会在就绪队列按照优先级策略排队，等待CPU ；

在这里插入图片描述

③ 运行 (Running) 态

进程在CPU上运行；

在这里插入图片描述

④ 阻塞态

阻塞（Block）状态 = 等待状态 = 封锁状态；

进程因某一事件暂停运行，即使CPU空闲也不能执行。阻塞的进程会在阻塞队列里排队等待；

注意！就绪态仅缺CPU，而阻塞态缺其它资源 (除了CPU) 或等待某一事件；

在这里插入图片描述

⑤ 终止态

在这里插入图片描述

2. 进程状态的转换

P42里引入了挂起、激活原语之后的进程状态转换，课程 2.2.1 调度的概念里简单提了提，保险起见去课本里看看；

注意！一个进程，运行 -> 阻塞是主动的行为，阻塞 -> 就绪是被动的行为，需要协助；

三个基础状态	CPU 资源	其它资源
就绪态	×	✔
运行态	✔	✔
阻塞态	×	×

在这里插入图片描述

小结

在这里插入图片描述

2.1.3 进程的组织方式

为了方便进程的调度和管理，需要将 ==各进程的PCB用适当的方法组织起来，==常见的组织方式：

~~线性方式~~
链接方式
索引方式

1. 进程的组织方式 - 链接方式

链接方式：将同一状态的PCB链接成一个队列；

在这里插入图片描述

2. 进程的组织方式 - 索引方式

索引方式：将同一状态的进程组织在一个索引表中，索引表的表项指向相应的PCB；

在这里插入图片描述

小结

在这里插入图片描述

2.1.4 进程控制

在这里插入图片描述

1. 进程控制的基本概念

① 什么是进程控制？

进程控制的主要功能是对系统中的所有进程实施有效的管理，包含功能：

进程的创建
进程的终止
进程的阻塞
进程的唤醒
进程状态的切换

在这里插入图片描述

② 如何实现进程控制？

使用原语实现进程控制，原语操作具有原子性，不可中断；

通俗理解，把原语理解成一段封装好的功能函数，只不过具有原子性；

在这里插入图片描述

思考：为什么进程控制的过程要 “一气呵成” ？

下图中举例说明

在这里插入图片描述

【问题】如何实现原语的 “原子性” ？

答：使用关中断指令和开中断指令这两个特权指令实现原子性

在这里插入图片描述

2. 进程相关的原语

各类原语的操作步骤，不需要死记硬背，只需要理解即可，不会让你默写；

① 进程的创建

这里第一次遇到作业调度这个名词，解释一下。作业就是放在外存，还没有被运行的程序。

在这里插入图片描述

② 进程的终止

在这里插入图片描述

③ 进程的阻塞和唤醒

保护进程运行现场（重点内容，后面在填坑）；

在这里插入图片描述

④ 进程的切换

恢复进程运行环境信息（重点内容，后面在填坑）

在这里插入图片描述

接下来举例介绍运行环境信息

学习完 ==进程控制相关的原语，==再来看看之前的问题：程序是如何运行的？

在这里插入图片描述

CPU里设置了很多 ==寄存器，==存储各类程序运行时需要的数据

在这里插入图片描述

很多的中间计算结果是暂时放在各类寄存器中

例如执行指令3时，x=2，但此时它还没有被写回内存，执行完指令4，内存中的x才变成2；

如果执行完指令3，另一个进程上CPU，他将通用寄存器里的数据改为250，切换回原来的进程，不就数据错误了？

在这里插入图片描述

解决办法：在进程切换时先在PCB中保持这个进程的 ==运行环境，==进程重新运行时，通过PCB恢复当时的运行环境；

在这里插入图片描述

小结

在这里插入图片描述

2.1.5 进程的通信

在这里插入图片描述

【问题】什么是进程间通信？

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

在这里插入图片描述

【问题】为什么进程通信需要操作系统支持？

答：为了进程安全；

在这里插入图片描述

1. 共享存储

在共享存储器系统中，相互通信的进程共享某些数据结构或 ==共享存储区，==进程之间能够通过这些空间进行通信；

在这里插入图片描述

共享存储的两种类型：

低级共享，基于数据结构的共享，速度慢、灵活性差；
高级共享，基于存储区的共享，速度快、灵活性好；

在这里插入图片描述

2. 消息传递

在信息传递机制中，进程不必借助任何共享存储区或数据结构，而是以格式化的信息为单位，将通信的数据封装在信息中，并利用操作系统提供的一组通信命令（原语），在进程间进行信息传递，完成进程间的数据交换；

说白了，就是通过写信进行交流；

在这里插入图片描述

① 直接通信方式

进程P按要求准备好要发送的信息；
通过发送原语，将信息放进进程Q的消息队列里；
进程Q从消息队列里读取信息；

在这里插入图片描述

② 间接通信方式

间接通信方式，进程P只是指明要发信息给信箱A，没有指明发给哪一个进程；

在这里插入图片描述

3. 管道通信

共享存储方式，对共享区的读写很自由；

管道通信方式，读写数据有限制，和循环队列一样；

在这里插入图片描述

小结

在这里插入图片描述

2.1.6 线程和多线程模型

在这里插入图片描述

1. 什么是线程，为什么要引入线程？

在这里插入图片描述

==引入进程的目的：==使得多道程序并行执行，以提高资源利用率；

==引入线程的目的：==减少程序在并发执行时所付出的时间开销，提高OS的并发性能；

在这里插入图片描述

2. 引入线程机制后，有什么变化？

课本P83还补充了从拥有资源、独立性、支持多处理机系统的角度，比较进程与线程的区别；（王道不提，应该不考）

在这里插入图片描述

3. 线程的属性

在这里插入图片描述

4. 线程的实现方式

① 用户级线程

在这里插入图片描述

在上面qq的例子中，操作系统只能看见进程，程序员利用线程库创建逻辑上的线程，就是所谓的用户级线程；

在这里插入图片描述

② 内核级线程

内核级线程，操作系统支持的线程，~~无论是系统进程还是用户进程，都是在操作系统内核的支持下运行；~~

在这里插入图片描述

5. 多线程模型

学习了用户级线程和 ==内核级线程，==各自都有优缺点，下面的多线程模型就是把他们融合起来

① 一对一模型

在这里插入图片描述

② 多对一模型

在这里插入图片描述

③ 多对多模型

在这里插入图片描述

【大纲新增考点】

在这里插入图片描述

6. 线程的状态与转换

在这里插入图片描述

7. 线程的组织与控制

在这里插入图片描述

小结

王道课本P66页有关于两种线程调度的内容

用户级线程调度
内核级线程调度

在这里插入图片描述

2.2 处理机调度 ⭐

2.2.1 调度的概念

在这里插入图片描述

1. 调度的基本概念

处理机调度：进程数 > 处理机个数，需要对处理机进行分配；

在这里插入图片描述

2. 调度的层次

一个作业从提交开始直到完成，往往需要经历三级调度；

在这里插入图片描述

① 高级调度 (作业调度)

在这里插入图片描述

② 低级调度 (进程调度)

在这里插入图片描述

③ 中级调度 (内存调度)

在这里插入图片描述

3. 三级调度的联系

在这里插入图片描述

补充知识：进程的挂起态与七状态模型

在这里插入图片描述

小结

在这里插入图片描述

2.2.2 调度的目标

在这里插入图片描述

1. CPU利用率

在这里插入图片描述

2. 系统吞吐量

在这里插入图片描述

3. 周转时间

在这里插入图片描述

4. 等待时间

在这里插入图片描述

5. 响应时间

在这里插入图片描述

小结

在这里插入图片描述

2.2.3 调度的实现

在这里插入图片描述

1. 进程调度的时机

在这里插入图片描述

内核程序临界区和 ==临界区，==这两个不是同一个概念

在这里插入图片描述

当某个进程处于普通的临界区（eg：打印机）

在这里插入图片描述

根据当前运行的进程是否可以被强行的剥夺处理机资源对进程调度的方式分成两类，后面会具体介绍；

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

在这里插入图片描述

2. 进程的切换与过程

在这里插入图片描述

3. 进程调度的方式

在这里插入图片描述

4. 调度程序（调度器）

调度程序：用户调度和分派CPU的组件。调度程序是操作系统内核程序；

需要调度程序的调度时机：

创建新进程时，调度程序就会出来看下是否需要让他上处理机；
进程退出时，处理机空闲，调度程序就会出来看让谁接着上处理机；
运行进程阻塞时，调度程序就会出来看让谁接着上处理机；
发生 ==I/O中断时，==有可能使得某些阻塞进程回到就绪态里，一旦就绪队列发生改变时，调度程序就会出来，根据调度算法，判断是否让他上处理机；

在这里插入图片描述

调度程序的三部分：

① 排队器

将系统中的所有就绪进程按照一定的策略排成一个或多个队列，以便进程调度；

② 分派器

将选中的进程从就绪队列取出，分配CPU；

③ 上下文切换器

处理机切换时，会发生两对上下文的切换操作：

当前进程的上下文保存到其PCB中，再装入分派程序的上下文；
移出分派程序的上下文，将新选进程的CPU现场装入处理机的各个相应寄存器；

在上下文切换时，需要执行大量的 ==load 和 store指令，==以保存寄存器的内容；

在这里插入图片描述

5. 两种线程的调度

对于支持线程调度的操作系统来说，分成两种调度 (简单了解、王道课上没提) ：

用户级线程调度：内核不知道线程的存在，内核选择一个进程，由进程的调度程序决定哪个线程运行；
内核级线程调度：内核选择一个特定线程运行，不考虑该线程附属的进程；

如果操作系统支持调度线程，那么调度程序的对象就是内核级线程；

如果操作系统不支持调度线程，那么调度程序的对象就是进程；

~~用户级线程的线程切换在同一个进程中进行，仅需少量的机器指令；~~

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

在这里插入图片描述

6. 闲逛进程

闲逛进程，==无需CPU之外的资源。==说白的就是街溜子，CPU闲的没事干就闲逛；

在这里插入图片描述

小结

在这里插入图片描述

2.2.4 典型的调度算法

在这里插入图片描述

1. 先来先服务（FCFS）

在这里插入图片描述

算法	是否抢占？	是否饥饿	优点	缺点
FCFS	非抢占	不会	公平、简单	对长作业有利，对短作业不利

在这里插入图片描述

2. 短作业优先（SJF）

在这里插入图片描述

算法	是否抢占？	是否饥饿	优点	缺点
FCFS	非抢占	不会	公平、简单	对长作业有利，对短作业不利
SJF/SPF	非抢占	会	短	对短作业有利，对长作业不利
SRTN	抢占式	会	短	对短作业有利，对长作业不利

在这里插入图片描述

3. 高响应优先（HRRN）

在这里插入图片描述

算法	是否抢占？	是否饥饿	优点	缺点
FCFS	非抢占	不会	公平、简单	对长作业有利，对短作业不利
SJF/SPF	非抢占	会	短	对短作业有利，对长作业不利
SRTN	抢占式	会	短	对短作业有利，对长作业不利
HRRN	非抢占	不会

在这里插入图片描述

4. 时间片轮转调度算法（RR）

在这里插入图片描述

算法	是否抢占？	是否饥饿	优点	缺点	对象
FCFS	非抢占	不会	公平、简单	对长作业有利，对短作业不利	作业/进程
SJF/SPF	非抢占	会	短	对短作业有利，对长作业不利	作业/进程
SRTN	抢占式	会	短	对短作业有利，对长作业不利	作业/进程
HRRN	非抢占	不会			作业/进程
RR	抢占式	不会	公平、响应快	额外开销	进程

在这里插入图片描述

5. 优先级调度算法

在这里插入图片描述

算法	是否抢占？	是否饥饿	优点	缺点	对象
FCFS	非抢占	不会	公平、简单	对长作业有利，对短作业不利	作业/进程
SJF/SPF	非抢占	会	短	对短作业有利，对长作业不利	作业/进程
SRTN	抢占式	会	短	对短作业有利，对长作业不利	作业/进程
HRRN	非抢占	不会			作业/进程
RR	抢占式	不会	公平、响应快	额外开销	进程
优先级	都有	会	实时、应急	饥饿	作业/进程

在这里插入图片描述

6. 多级反馈队列调度算法

在这里插入图片描述

算法	是否抢占？	是否饥饿	优点	缺点	对象
FCFS	非抢占	不会	公平、简单	对长作业有利，对短作业不利	作业/进程
SJF/SPF	非抢占	会	短	对短作业有利，对长作业不利	作业/进程
SRTN	抢占式	会	短	对短作业有利，对长作业不利	作业/进程
HRRN	非抢占	不会			作业/进程
RR	抢占式	不会	公平、响应快	额外开销	进程
优先级	都有	会	实时、应急	饥饿	作业/进程
多级反馈队列	抢占式	会			进程

在这里插入图片描述

7. 多级队列调度算法

在这里插入图片描述

小结

算法	是否抢占？	是否饥饿	优点	缺点	对象
FCFS	非抢占	不会	公平、简单	对长作业有利，对短作业不利	作业/进程
SJF/SPF	非抢占	会	短	对短作业有利，对长作业不利	作业/进程
SRTN	抢占式	会	短	对短作业有利，对长作业不利	作业/进程
HRRN	非抢占	不会			作业/进程
RR	抢占式	不会	公平、响应快	额外开销	进程
优先级	都有	会	实时、应急	饥饿	作业/进程
多级反馈队列	抢占式	会			进程

在这里插入图片描述

2.3 同步与互斥 ⭐

2.3.1 同步与互斥的基本概念

前言

在多道程序环境下，进程并发运行，不同的进程之间存在着不同的相互制约关系；

为了协调进程之间的互相制约关系，引入了进程同步的概念；

简单的同步问题举例：1 + 2 × 3，需要先计算乘法，再计算加法，这就是计算中的制约关系；

1. 临界资源

一次仅允许一个进程使用的资源称为临界资源；

对于临界资源的访问，必须是互斥进行的；每个进程中，访问临界资源的那段代码成为临界区；

为了保证临界资源的正确使用，把临界资源的访问过程分为4部分：进入区、临界区、退出区、剩余区；

~~关于临界资源和临界区的内容，将在本节的 3. 进程互斥会再次提及，这里是简单介绍；~~

2. 进程同步

进程同步的大白话理解：相关的进程之间按照 ==某种规则 (前后制约关系)，==并发执行；

【补充】

实际计算机运行中，进程同步需要考虑很多复杂因素，但在《操作系统》中，只需要关注临界资源即可；

进程同步，就是为了争抢临界资源。按照这个思路去学习；

在这里插入图片描述

3. 进程互斥

进程同步是直接制约关系；

进程互斥是间接制约关系；

在这里插入图片描述

临界资源要求一个时间段内只能一个进程访问，也就是互斥访问资源；

下图对临界资源互斥访问的四个部分进行了详细介绍；

在这里插入图片描述

在对临界资源互斥访问的过程中，需要遵守一些原则；

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

【补充概念】

死等：没有进入临界区的正在等待的某进程根本无法获得临界资源而进入进程，这种等待是无结果的；

忙等：没有进入临界区的正在等待的某进程不断的在测试循环代码段中的变量的值，占着处理机而不释放；

在这里插入图片描述

小结

本节内容：临界资源 - 进程同步 - 进程互斥

同步：并发进程为完成同一任务所进行的工作顺序协调；

互斥：并发进程为竞争临界资源所进行的资源分时占用；

在这里插入图片描述

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

1. 进程互斥的软件实现方法

实现临界区互斥，我们只需关注进入区和退出区的操作即可；

软件实现方法的思想：

进入区的操作：
在进入区设置并检查一些标志来标明是否有进程在临界区中；
若已有进程在临界区，则在进入区通过循环检测进行等待；

退出区的操作：进程离开临界区后，在退出区修改标志；

在这里插入图片描述

【问题】

当没有进程互斥时，有可能发生什么事故？

答：两个进程同时操作一个资源，很混乱；

在这里插入图片描述

① 单标志法
int trun = 0;	// trun 表示当前允许进入临界区的进程号
主要问题：违背了空闲让进原则，空闲不让进了；

只能按照 P0 - P1 - P0 - P1 - …… 这样的顺序访问资源，P1必须等待P0访问完才能访问，即使临界区空闲；

在这里插入图片描述

② 双标志先检查法
	bool flag[2];	// 表示进程想进入临界区的意愿flag[0] = false;flag[1] = false;	// 表示P0、P1开始都不需要进入临界区
优点：

解决了单标志法需要交替进入，不可连续使用的问题；

缺点：

进入区需要实现两个功能：==检测和上锁，==但这两个步骤并不是一次性完成的，可能出现两个进程同时进入临界区的情况；

违背了忙着等待原则，忙着还不等；

在这里插入图片描述

③ 双标志后检查法

对双标志先检查法进行修改，先上锁后检测

缺点：

可能出现两个进程都想进入临界区又都无法进入的情况，互相争抢，长期导致饥饿现象；

违背了空闲让进、有限等待原则，空闲不让进、等得老久；

在这里插入图片描述

④ Peterson 算法
	bool flag[2];	// 表示进程想进入临界区的意愿int trun = 0;	// trun 表示优先让哪个进程进入临界区
Peterson = 单标志法 + 双标志后检查法

在这里插入图片描述

谁最后谦让，就失去了行动的优先权

在这里插入图片描述

缺点：

违背让权等待原则，出现忙等；

例如：当P0进程也想进入，就必须等待P1进程结束；

如果它进不来临界区，那么它就会一直被卡在③，不断检测自己是否可以进入临界区，一直占用着CPU资源；

在这里插入图片描述

小结

在这里插入图片描述

2. 进程互斥的硬件实现方法

理解 ==硬件实现，==对信号量的学习很有帮助；

计算机提供了特殊的 ==硬件指令，==通过对一个字中的内容进行 ==检测和修正，==或对两个字的内容进行交换，实现进程互斥；

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

在这里插入图片描述

① 中断屏蔽方法

防止其它进程进入临界区的最简方法就是关中断，简单、高效；

缺点：

关中断指令，==只对发出关中断指令的处理机有效。==如果是在多处理机，关中断指令对于其它处理机是没有效果的；
==关 / 开中断指令是特权指令，==只能在内核态下执行，不适用于用户进程；

在这里插入图片描述

② TestAndSet指令
// 布尔型共享变量 lock，表示当前临界区是否被加锁（是否被占用）
// true 表示已加锁，false 表示未加锁
bool TestAndSet(bool *lock) {bool old;old = *lock;*lock = true;retuen old;
}whiel (TestAndSet (&lock));	// 上锁 + 检测//	临界区代码lock = false;	// 解锁// 剩余区代码
TSL指令就是使用硬件方式，实现上锁和检测的原子操作；

缺点：违背了让权等待原则；

在这里插入图片描述

③ Swap指令

缺点：违背了让权等待原则；

在这里插入图片描述

小结

在这里插入图片描述

2.3.3 互斥锁

1. 互斥锁的概念

这里先简单介绍互斥锁的概念，之后会介绍使用互斥锁解决经典同步问题；

在这里插入图片描述

2. 锁的特性

在这里插入图片描述

2.3.4 信号量 ⭐

在这里插入图片描述

1. 信号量机制的概念

① 把系统中的资源抽象化为变量，信号量记录着资源数；
② 提供一对原语 wait(S) 和 signal(S) 来保证对信号量S 操作的原子性；

在这里插入图片描述

2. 信号量的类别

① 整型信号量

在这里插入图片描述

② 记录型信号量

在这里插入图片描述

当执行P0、P1进程时，有打印机资源；

当执行P2、P3进程时，打印机资源缺乏，P2、P3执行 ==block原语，==被挂在等待队列里；

==S.value = 0：==资源恰好分配完；
==S.value = -1：==有1个进程在等待资源分配；

P0进程使用完打印机，执行 ==signal操作，==sigal是执行value++；

若 value++之后，==value <= 0，==说明有进程在等待该资源，就会执行 ==wakeup原语，==就会唤醒等待队列中的一个进程，例如唤醒此时的P3 ；

在这里插入图片描述

整形信号量违背让权等待原则，会出现忙等现象；

记录型信号量就不会有上述情况；

在这里插入图片描述

小结

在这里插入图片描述

3. 信号量机制的使用

之前学习的几种互斥的软硬件实现方式，还有整形信号量，都无法解决让权等待；

信号量机制设置了进程的 ==阻塞、唤醒，==就刚好解决了这个问题；

在这里插入图片描述

① 信号量机制实现进程互斥

之前提到过，系统中的某一些资源是必须互斥访问的，而访问这些系统资源的代码叫做临界区

所以如果某些资源要互斥访问，说明同一时刻只能有一个进程进入临界区

基于上面的理解，所以就将信号量mutex 表示为进入临界区的名额（名额只有1个）

需要注意的几个点：

==semaphore mutex = 1，==默认初始化记录型信号量，具有排队阻塞的功能，并不会出现忙等；
对于不同的临界资源需要设置不同的互斥信号量，例如：打印机、摄像头；
P、V操作一定要成对出现；

在这里插入图片描述

② 信号量机制实现进程同步

在这里插入图片描述

③ 信号量机制实现前驱关系

每一对前驱关系，都是一个进程同步问题，就需要一个同步信号量；

在这里插入图片描述

小结

在这里插入图片描述

2.3.5 管程

在这里插入图片描述

1. 为什么要引入管程？

在引入管程之前，计算机使用信号量机制解决互斥问题，但是信号量机制编写代码太麻烦了，所以出现了管程机制；

在这里插入图片描述

2. 管程的定义和基本特征

管程：代表共享资源的数据结构，以及由对该共享数据结构实施操作的一组过程所组成的资源管理程序；

管程很像面向对象中的 ==类，==开头提过 P/V 操作编写太麻烦了，所以引入 ==管程机制，==封装了系统资源以及对应的操作；

在这里插入图片描述

3. 条件变量

当一个进程进入管程后被阻塞，直到阻塞的原因解除时，在此期间，如果该进程还不释放管程，那么其他进程无法进入管程。

(同一时刻，管程中只能有一个进程在执行)

为此，将阻塞原因定义为 条件变量 condition;

通常，一个进程被阻塞的原因可以有多个，因此在管程中设置了多个条件变量；

每个条件变量保存了一个等待队列，用于记录因该条件变量而阻塞的所有进程，对条件变量只能进行两种操作：

① ==x.wait：==当x对应的条件不满足时，正在调用管程的进程调用 x.wait，将自己插入x条件的等待队列，并释放管程。

此时其他进程可以使用该管程。

② x.signal：x对应的条件发生了变化，则调用 x.signal，唤醒一个因x条件而阻塞的进程。（进程离开管程时才能调用）

// 条件变量的定义和使用举例：
monitor Demo {共享数据结构 S;condition x;			// 定义一个条件变量×init_code() { ... }take away() {if(S<=0) 			// 资源不够,在条件变量x上阻塞等待x.wait(O);资源足够,分配资源,做一系列相应处理;}give back() {归还资源,做一系列相应处理;if(有进程在等待) 		// 唤醒一个阻塞进程x.signal; }
}

条件变量和信号量的比较：

相似点：条件变量的wait/signal操作类似于信号量的P/V操作，可以实现进程的阻塞/唤醒；

不同点：

条件变量是没有值的，仅实现了排队等待功能；
信号量是有值的，信号量的值反映了剩余资源数，而在管程中，剩余资源数用共享数据结构记录。

【拓展】：用管程解决生产者消费者问题

管程的互斥由编译器负责实现，程序员无需考虑

在这里插入图片描述

【拓展】Java中类似管程的机制

在这里插入图片描述

小结

在这里插入图片描述

2.3.6 经典同步问题

1. 生产者 - 消费者问题

① 问题描述

在这里插入图片描述

② 问题分析

在这里插入图片描述

③ 如何实现

在这里插入图片描述

思考

在这里插入图片描述

2. 多生产者 - 多消费者问题

① 问题描述

在这里插入图片描述

② 问题分析

在这里插入图片描述

③ 如何实现

在这里插入图片描述

小结

在这里插入图片描述

3. 吸烟者问题

① 问题描述

在这里插入图片描述

② 问题分析

在这里插入图片描述

③ 如何实现

在这里插入图片描述

小结

在这里插入图片描述

4. 读者 - 写者问题

① 问题描述

在这里插入图片描述

② 问题分析

在这里插入图片描述

③ 如何实现

在这里插入图片描述

小结

在这里插入图片描述

5. 哲学家进餐问题

① 问题描述

在这里插入图片描述

② 问题分析

在这里插入图片描述

③ 如何实现

在这里插入图片描述

④ 具体代码

在这里插入图片描述

小结

在这里插入图片描述

2.4 死锁

2.4.1 死锁的概念

在这里插入图片描述

1. 什么是死锁？

循环等待

在这里插入图片描述

2. 死锁、饥饿、死循环的区别

在这里插入图片描述

3. 死锁产生的必要条件

在这里插入图片描述

4.什么时候会发生死锁？

在这里插入图片描述

5. 死锁的处理策略

在这里插入图片描述

小结

在这里插入图片描述

2.4.2 死锁的处理策略 - 预防死锁

在这里插入图片描述

1. 预防死锁 - 破坏互斥条件

在这里插入图片描述

2. 预防死锁 - 破坏不剥夺条件

在这里插入图片描述

3. 预防死锁 - 破坏请求和保持条件

在这里插入图片描述

4. 预防死锁 - 破坏循环等待条件

在这里插入图片描述

小结

在这里插入图片描述

2.4.3 死锁的处理策略 - 避免死锁

在这里插入图片描述

1. 什么是安全序列？

在这里插入图片描述

2. 安全序列、不安全状态、死锁的联系

在这里插入图片描述

3. 银行家算法

如何避免系统进入不安全状态

在这里插入图片描述

举例说明

在这里插入图片描述

实际笔算思路

在这里插入图片描述

举一个找不到安全序列的例子

在这里插入图片描述

伪代码实现银行家算法

在这里插入图片描述

小结

在这里插入图片描述

2.4.4 死锁的处理策略 - 检测和解除

在这里插入图片描述

1. 死锁的检测

在这里插入图片描述

2. 死锁的解除

在这里插入图片描述

小结

在这里插入图片描述

2.5 常见问题和易混淆知识点

1. 进程与程序的区别与联系

① 进程是程序及其数据在计算机上的一次运行活动，是一个动态的概念。

进程的运行实体是程序，离开程序的进程没有存在的意义。

从静态角度看，进程是由程序、数据和进程控制块（PCB）三部分组成的。

而程序是一组有序的指令集合，是一种静态的概念。

② 进程是程序的一次执行过程，它是动态地创建和消亡的，具有一定的生命周期，是暂时存在的；

而程序则是一组代码的集合，是永久存在的，可长期保存。

③ 一个进程可以执行一个或几个程序，一个程序也可构成多个进程。进程可创建进程，而程序不可能形成新的程序。

④ 进程与程序的组成不同。进程的组成包括程序、数据和PCB。

2. 死锁与饥饿

具有等待队列的信号量的实现可能导致这样的情况：

两个或多个进程无限地等待一个事件，而该事件只能由这些等待进程之一来产生。

这里的事件是V操作的执行（即释放资源)。出现这样的状态时，这些进程称为死锁 (Deadlocked)。

为加以说明，考虑一个由两个进程 P₀ 和 P₁ 组成的系统，每个进程都访问两个信号量S和Q，这两个信号量的初值均为1。

P0() {while(1) {P(S);P(Q);...V(S);V(Q);}
}
P1() {while(1) {P(Q);P(S);...V(Q);V(S);}
}

假设进程P₀执行 P(S)，接着进程P₁ 执行P(Q)。当进程P₀执行PQ)时，它必须等待，直到进程P₁执行 V(Q)。类似地，当进程P₁执行 P(S)时，它必须等待，直到进程P₀执行 V(S)。由于这两个V操作都不能执行，因此进程P₀和进程P₁就死锁了。

一组进程处于死锁状态是指组内的每个进程都在等待一个事件，而该事件只可能由组内的另一个进程产生。这里所关心的主要是事件是资源的获取和释放。

与死锁相关的另一个问题是无限期阻塞 (Indefinite Blocking) 或饥饿 (Starvation)，即进程在信号量内无穷等待的情况。

产生饥饿的主要原因是：在一个动态系统中，对于每类系统资源，操作系统需要确定一个分配策略，当多个进程同时申请某类资源时，由分配策略确定资源分配给进程的次序。

有时资源分配策略可能是不公平的，即不能保证等待时间上界的存在。

在这种情况下，即使系统没有发生死锁，某些进程也可能会长时间等待。

当等待时间给进程推进和响应带来明显影响时，称发生了进程“饥饿”，当“饥饿”到一定程度的进程所赋予的任务即使完成也不再具有实际意义时，称该进程被“饿死”。

例如，当有多个进程需要打印文件时，若系统分配打印机的策略是最短文件优先，则长文件的打印任务将由于短文件的源源不断到来而被无限期推迟，导致最终“饥饿”甚至“饿死”。

“饥饿”并不表示系统一定会死锁，但至少有一个进程的执行被无限期推迟。“饥饿”与死锁的主要差别如下:

① 进入“饥饿”状态的进程可以只有一个，而因循环等待条件而进入死锁状态的进程却必须大于等于两个。

② 处于“饥饿”状态的进程可以是一个就绪进程，如静态优先权调度算法时的低优先权进程，而处于死锁状态的进程则必定是阻塞进程。

3. 银行家算法的工作原理

银行家算法的主要思想是避免系统进入不安全状态。

在每次进行资源分配时，它首先检查系统是否有足够的资源满足要求，若有则先进行试分配，并对分配后的新状态进行安全性检查。

若新状态安全，则正式分配上述资源，否则拒绝分配上述资源。这样，它保证系统始终处于安全状态，从而避免了死锁现象的发生。

4. 进程同步、互斥的区别和联系

并发进程的执行会产生相互制约的关系：

一种是进程之间竞争使用临界资源，只能让它们逐个使用，这种现象称为互斥，是一种竞争关系；

另一种是进程之间协同完成任务，在关键点上等待另一-个进程发来的消息，以便协同一致，是一种协作关系。

1) 为什么要引入进程？

在多道程序同时运行的背景下，进程之间需要共享系统资源，因此会导致各程序在执行过程中出现相互制约的关系，程序的执行会表现出间断性的特征。

这些特征都是在程序的执行过程中发生的，是动态的过程，而传统的程序本身是一组指令的集合，是一个静态的概念，无法描述程序在内存中的执行情况，即我们无法从程序的字面上看出它何时执行、何时停顿，也无法看出它与其他执行程序的关系，因此，程序这个静态概念已不能如实反映程序并发执行过程的特征。

为了深刻描述程序动态执行过程的性质乃至更好地支持和管理多道程序的并发执行，人们引入了进程的概念。

2）什么是进程？进程由什么组成？

进程是一个具有独立功能的程序关于某个数据集合的一次运行活动。

它可以申请和拥自的统资源，是一个动态的概念，是一个活动的实体。

它不只是程序的代码本身，还包括当前的活动，通过程序计数器的值和处理寄存器的内容来表示。

一个进程实体由程序段、相关数据段和PCB三部分构成，其中 PCB是标志一个进程存在的唯一标识，程序段是进程运行的程序的代码，数据段则存储程序运行过程中相关的一些数据。

3）进程是如何解决问题？

进程把能够识别程序运行态的-一些变量存放在PCB中，通过这些变量系统能够更好了解进程的状况，并在适当时进行进程的切换，以避免一些资源的浪费，甚至划分为更小的调度单位—线程来提高系统的并发度。

本节主要介绍了处理机调度的概念。

操作系统主要管理处理机、内存、文件、设备几种资源.只要对资源的请求大于资源本身的数量，就会涉及调度。例如，在单处理机系统中，处理税只有一个，而请求服务的进程却有多个，所以就有处理机调度的概念出现。而出现调度的概念活、人有了一个问题，即如何调度、应该满足谁、应该让谁等待，这是调度算法所回答的问题:流该满足谁、应该让谁等待，要遵循一定的准则，即调度的准则。调度这一概念贯穿于操作系统的娃终，读者在接下来的学习中，将接触到几种资源的调度问题和相应的调度算法。将它们与处理机调度的内容相对比,将会发现它们有异曲同工之妙。

1）为什么要进行处理机调度？

若没有处理机调度，意味着要等到当前运行的进程执行完毕后，下一个进程才能执行，向实际情况中，进程时常需要等待一些外部设备的输入，而外部设备的速度与处理机相比是非常缓慢的，若让处理机总是等待外部设备，则对处理机的资源是极大的浪费。

而引进处理机调度后，可在运行进程等待外部设备时，把处理机调度给其他进程，从而提高处理机的利用率。

用一句简单的话说，就是为了合理地处理计算机的软/硬件资源。

2）调度算法有哪些？各自特点是什么？适合哪些操作系统？

本节介绍的调度算法有先来先服务调度算法、短作业优先调度算法、优先级调度算法、高响应比优先调度算法、时间片轮转调度算法、多级反馈队列调度算法6种。

先来先服务算法和短作业优先算法无法保证及时地接收和处理问题，因此无法保证在规定的时间间隔内响应每个用户的需求，也同样无法达到实时操作系统的及时性需求。

优先级调度算法按照任务的优先级进行调度，对于更紧急的任务给予更高的优先级，适合实时操作系统。

高响应比优先调度算法、时间片轮转调度算法、多级反馈队列调度算法都能保证每个.务在一定时间内分配到时间片，并轮流占用 CPU，适合分时操作系统。

1）为什么要引入进程同步的概念？

在多道程序共同执行的条件下，进程与进程是并发执行的，不同进程之间存在不同的相互制约关系。

为了协调进程之间的相互制约关系，引入了进程同步的概念。

2）不同的进程之间会存在什么关系？

进程之间存在同步与互斥的制约关系。

同步是指为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调之们的工作次序而等待、传递信息所产生的制约关系。

互斥是指当一个进程进入临界区使用临界资源时，另一个进程必须等待，当占用临界资源的进程退出临界区后，另一进程才允许去访问此临界资源。

3）单纯使用本节介绍的方法解决这些问题时会遇到新的问题吗？

当两个或两个以上的进程在执行过程中，因占有一些资源而又需要对方的资源时，会因为争夺资源而造成一种互相等待的现象，若无外力作用，它们都将无法推进下去。这种现象称为死锁，具体介绍和解决方案请参考下一节。

1）为什么会产生死锁？产生死锁有什么条件？

由于系统中存在一些不可剥夺资源，当两个或两个以上的进程占有自身的资源并请求对方的资源时，会导致每个进程都无法向前推进，这就是死锁。

死锁产生的必要条件有4个，分别是互斥条件、不剥夺条件、请求并保持条件和循环等待条件。

互斥条件是指进程要求分配的资源是排他性的，即最多只能同时供一个进程使用。

不剥夺条件是指进程在使用完资源之前，资源不能被强制夺走。

请求并保持条件是指进程占有自身本来拥有的资源并要求其他资源。

循环等待条件是指存在一种进程资源的循环等待链。

2）有什么办法可以解决死锁问题？

死锁的处理策略可以分为预防死锁、避免死锁及死锁的检测与解除。

死锁预防是指通过设立一些限制条件，破坏死锁的一些必要条件，让死锁无法发生。

死锁避免指在动态分配资源的过程中，用一些算法防止系统进入不安全壮态，从而避免死锁。

死锁的检测和解除是指在死锁产生前不采取任何措施，只检测当前系统有没有发生死锁，若有，则采取一些措施解除死锁。