计算机操作系统 - 第二章：进程的描述与控制 - 《计算机专业课笔记》

2.1 💡前趋图和程序执行
2.2 进程的描述
2.3 💡进程控制
2.4 💡进程同步
2.5 💡经典进程的同步问题
2.6 进程通信
- 进程通信的类型
2.7 线程(THREAD)的基本概念（不考）
2.8 线程的实现
- 线程的实现方式
实验

💡整理不易，先赞后看，养成习惯💡

2.1 💡前趋图和程序执行

前驱图

前驱图的定义

💡前趋图是一个有向无循环图,记为 DAG(Directed Acyclic Graph) ，用于描述进程之间执行的前后顺序。

节点和节点之间的表示方式有两种：

p1 -> p2
->={(p1,p2)| p1 必须在p2开始前完成}

一般只采用第一种。

上面的节点表示的可以是一条语句，一个程序段，一个进程，节点上的权重表示该进程的程序量或执行时间。

前驱图不应该出现循环

前驱图

非前驱图

程序的顺序执行及其特征

程序的顺序执行

单道程序环境下，程序段执行有固定的时序，仅当前一操作完成后，才能执行后继操作。

例如：

S1 : a = x + y;
S2 : b = a - 5;
S3 : c = b + 1;

上述的程序中，S2语句中的a需要在S1执行之后才可以获得，同理，S3中的b也只有在S2执行之后才可以获得。综上我们可以得出这个程序的执行顺序：S1 -> S2 -> S3
前驱图的表示即为：

程序顺序执行的特征

顺序性：即每一操作都必须在上一个操作结束之后开始
封闭性：程序运行时独占全机资源；资源的状态（除初始状态外）只有本程序才能改变它。程序一旦开始运行，其执行结果不受外界因素影响。
可再现性：只要执行时的环境和初始条件相同，程序不论是连续执行还是“走走停停”地执行，都将获得相同的结果。

程序的并发执行及其特征
顺序执行的资源利用率很明显是较低的，所以需要并发执行。

程序的并发执行
观察如下前驱图，这个前驱图用于表示计算打印程序：

其中：
I：表示输入程序
C：表示计算程序
P：表示打印程序

对于单个作业，也就是Ii -> Ci -> Pi，很明显只能是顺序执行。但是如果像上图所示一样，对于多个作业进行处理，以输入程序为例，当I1执行完成之后，可以无需等待打印完成即可立即执行I2，从而使得整体上多作业处理程序达成并发执行。

以横轴为时间轴，会发现在同一时刻，多个进程在并发执行。

为什么可以并发？原因在于第i个作业和第i+1个作业之间并不存在前驱关系，也就是不存在C1 -> I2这种关系出现，那么I2就可以在C1执行的时候并发执行。
看如下程序：

S1: a = x + 2
S2: b = y + 4
S3: c = a + b
S4: d = c + b

画出前驱图可得：

发现此时S1与S2其实并未存在前驱关系，所以此时**S****1**与**S****2**可以并发执行。

并发执行的特征

间断性：由于并发执行，所以程序的执行顺序就不固定了，在某一时刻可能是C在执行也可能是I在执行。
非封闭性：程序运行时候不再是独占全机资源，资源变成程序间共享的了，所以有可能其他程序的运行结果影响到本程序的结果。
不可再现性：由于上一点说道的非封闭性，因为其他程序可能改变相关的共享资源，会导致每次该程序的运行结果都可能不一致。

举个例子：

有2个循环程序A和B，它们共享变量N = n；程序A：N=N+1; 程序B: Print(N);N=0;

N=N+1在Print(N)和N=0之前，得到的N值分别为：**n+1, n+1, 0**，最终输出为**n+1**
N=N+1在Print(N)和N=0之后，得到的N值分别为：**n, 0, 1**，最终输出为**n**
N=N+1在Print(N)和N=0之间，得到的N值分别为：**n, n+1, 0**，最终输出为**n**
与顺序执行对比
| 顺序执行 | 并发执行 | | —- | —- | | 顺序性 | 间断性 | | 封闭性 | 非封闭性 | | 可再现性 | 不可再现性 |

并发执行引起的问题

如何协调各程序的执行顺序？
多个执行程序共享系统资源，程序之间可能会相互影响，甚至影响输出结果。
选择哪些、多少个程序进入内存执行？
内存中的执行程序谁先执行？
内存如何有效分配？

2.2 进程的描述

进程的定义和特征

💡进程的定义

从上面的并发执行的例子中我们知道，单纯的程序不可以进行并发执行，会出现失去封闭性从而导致出现不可再现性的特征。为了让每个参与并发执行的程序能够独立运行不受干扰，必须为之配备一个专门的数据结构——进程控制块(PCB)。

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

进程和程序的区别如下：

进程是动态的，程序是静态的：程序是有序代码的集合；进程是程序的执行
进程是暂时的，程序是永久的：进程是一个状态变化的过程，程序可长久保存
进程与程序的组成不同：进程的组成包括程序、数据和系统数据及资源

引入进程的问题
增加了空间开销：为进程建立数据结构
额外的时间开销：管理和协调、跟踪、填写和更新有关数据结构、切换进程、保护现场
更难控制：
- 协调多个进程竞争和共享资源
- 预防解决多个进程因为竞争资源而出现故障
- 处理机的竞争尤为突出。
  💡进程的特征
动态性：进程具有生命周期
独立性：进程的地址空间相互独立，互不干扰
并发性：多个进程实体同存于内存中，且能在一段时间内同时运行
异步性：指进程按各自独立的、不可预知的速度向前推进

💡进程的基本状态以及转换

进程的三种基本状态
就绪状态：指的是进程以及处于准备好运行的状态，此时的进程以及分配到了除了CPU以外的所有必要资源，只需要再获得CPU就可以立即运行。
执行状态：指的是进程已经获得CPU正处于运行状态下。（注意对于单机系统也就是单核CPU的情况下，一个时刻只能有一个进程被执行）
阻塞状态：指的是正在执行的进程因为某个事件被打断，暂时无法继续执行的状态（也叫做等待状态或者封锁状态）。被阻塞的进程会进入到阻塞队列当中。
三种基本状态的转换
进程的并发执行是按照CPU分配的时间片执行的（类似分时处理）。

进程状态状态为：

首先进程进入就绪状态，准备执行
然后进程被CPU进行调度，进入到执行状态
知道CPU给该进程的时间片完，重新回到就绪状态
如果在执行过程中，被其他请求打断，进入阻塞状态，该进程进入阻塞队列
当该请求完成之后，进程重新回到就绪状态
创建状态和终止状态
前面说过进程是有生命周期的，也就是说进程需要被创建和终止（销毁）。
（1）创建状态
在创建一个进程的时候主要做了以下事情：

进程会申请一个空白PCB（进行控制块）
向PCB中填写用于控制和管理进程的信息
为进程分配运行时候所必须使用的资源
把进程转为就绪状态并且插入就绪队列当中

在上述四个步骤里面，如果有一个步骤没有完成，则进程不能进入就绪状态，此时进程就处于创建状态。

引入创建状态有两个主要的原因：

保证就绪的进程控制信息完整
提高管理的灵活性，根据系统的性能或者主存容量限制推迟新进程的提交

因为就绪状态的进程会存放在主存当中，过多的就绪状态的进程会占用太多主存。

（2）终止状态
终止进程的时候主要做了以下事情：

等待操作系统进行善后处理
把进程的PCB清零
将PCB的空间返回给系统

进入终止状态的情况有如下几种：

进程自然结束
出现无法克服的错误
被操作系统终结
被其他有终止权的进程终止

进程进入终止状态之后不会再被执行，但是会在操作系统中留一个记录，保存其状态码和一些计时统计数据，供其他进程收集。直到其信息被其他进程提取完毕之后，这个进程才会被系统删除，其PCB会被清零，空白的PCB会返回给系统。

挂起操作和进程状态的转换（了解即可）

挂起操作的引入

挂起操作是为了系统和用户更加方便观察和分析进程所引入的。
所谓的进程挂起是让进程从动态转为静止态。与之对应的就是**激活**，也就是把进程从静态转为动态。
以基础的三个状态为例：

静止的状态主要针对于**就绪状态**以及**阻塞状态**，正在执行中的进程会挂起会直接进入**静止就绪状态**。

挂起：把一个进程从内存转到外存
激活：把一个进程从外存转到内存

引入挂起原语操作后的三个进程状态的转换
引起挂起的原因有：
用户请求
父进程请求
负荷调节的需要
操作系统的需要

关于状态转换：

活动就绪：进程在主存中并可以执行
活动阻塞：进程在主存中并等待一个事件
静止就绪：进程在辅存中，只要被载入主存就可以执行
静止阻塞：进程在辅存中并等待一个事件
进程状态的转换
- 活动就绪-> 静止就绪
- 活动阻塞->静止阻塞
- 静止就绪->活动就绪
- 静止阻塞->活动阻塞
  引入挂起操作后五个进程状态的转换
  在上述三个状态的基础上引入创建和终止：
  
  💡进程管理中的数据结构
  创建数据结构的目的为：
便于管理计算机资源，OS将它们抽象为各种数据结构
协调用户共享资源
操作系统中用于管理控制和数据结构
计算机系统对每个资源和进程都设置了一个数据结构，用于管理计算机中的资源和进程，称之为资源信息表或进程信息表，其中包含了资源或进程的标识，描述，状态等信息以及一批指针。
OS管理的这些数据结构一般可分为四类：内存表，设备表，文件表和**进程表**，其中进程表又称作进程控制块PCB。

最重要的就是这里的进程表。

进程控制块PCB的作用

PCB作用如下：

作为独立运行的基本单位：配置了PCB的程序可以视作一个能在多道环境下独立运行的基本单位（即为进程）
能实现间断性运行方式：程序被中断的时候，通过PCB中的信息可以恢复现场
提供进程管理所需要的信息：管理进程的生命周期
提供进程调度所需要的信息：决定进程应该什么时候被调用
实现与其它进程的同步与通信：进程和进程之间通过PCB进行同步和通信

进程控制块中的信息
进程标识符：进程标识符用于唯一的标识出进程
- 外部标识符：方便用户访问进程
- 内部标识符：方便系统访问进程
处理机状态：也叫处理机的上下文

处理机运行时，许多信息都存放在寄存器中。当处理机被中断时，所有这些信息都必须保存在PCB中，以便该进程重新执行时，能从断点继续执行。

简单来说就是通过处理机的状态来实现中断恢复处理。

进程调度信息：用于控制进程调度相关，包括：
- 进程状态
- 进程优先级
- 进程调度所需的其它信息
- 事件（阻塞原因）
进程控制信息：
- 程序和数据的地址
- 进程同步和通信机制
- 资源清单
- 链接指针
  进程控制块的组织方式
线性方式：将所有的PCB组织在一张线性表中，将该表的首地址放在内存的一个专用区域中。
链接方式：把具有相同状态进程的PCB链接成一个队列，诸如就绪队列，阻塞队列等。
索引方式：根据所有进程状态的不同，建立几张索引表，例如就绪索引表，阻塞索引表等

2.3 💡进程控制

💡进程控制都是通过原语操作实现的。

所谓原语操作就是该操作要么完全执行完成，要不不执行，类似原子操作，具有不可中断性。

操作系统内核

现代的操作系统会把OS分为若干个层次。
通常会把与硬件紧密相关的模块（比如中断处理模块）和运行频率较高的模块都安装在紧靠硬件的软件层次中，这些模块会常驻内存，这样做的目的有两个：

保护这些系统模块，避免收到其他应用程序的破坏
提高OS的运行效率

为了达成以上的目的，这里就把处理机的状态分为了系统态和用户态：

系统态：又叫做内核态，具有最高的指令执行权，能执行一切指令，访问所有的寄存器和存储区
用户态：又叫做目态，具有相对较低的特权，只能执行规定的指令，访问指定的寄存器和存储区

在一般情况下，应用程序只能在用户态运行，这样就可以防止应用程序破坏OS。
操作系统内核包括以下两大功能：

支撑功能
资源管理功能

支撑功能
支撑功能提供给OS其它众多模块所需的一些基本功能，以便支撑这些模块工作。
中断处理
时钟管理
原语操作

资源管理功能
进程管理
存储器管理
设备管理

进程的创建

进程的层次结构
在了解进程的创建之前，首先了解一下进程的层次结构。在OS中，允许一个进程创建子进程，通常把创建进程的进程称为**父进程**，而被创建的进程称为**子进程**。子进程可以继续创建更多的孙进程，由此形成进程的层次结构。

在进程的层次结构当中有如下特点：
子进程可继承父进程所分配到的资源
子进程运行完毕后，将资源归还给父进程
撤销父进程时，其所有的子进程也随之撤销

注意：这种层次结构并不存在于Windows系统当中，在Windows系统中所有进程的地位都是平等的，进程之间通过句柄来控制所谓的子进程。

引起进程创建的事件

用户登录
作业调查
提供服务
用户请求

了解即可。

进程的详细创建

进程创建的原语操作为**creat**（注意没有e）。

创建步骤如下：

申请空白PCB
为新进程分配运行所需要的必备资源
初始化进程控制块PCB，内容包括
- 初始化标识信息
- 初始化处理机状态信息
- 初始化处理机控制信息
如果进程就绪队列能够接纳此进程，则插入该新进程
进程的终止

进程终止的原语操作为**destroy**。

引起进程终止的事件

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

进程终止的过程
根据被终止进程的标识符，从PCB集合中检索出该进程的PCB，从中读出该进程的状态
若被终止进程正处于执行状态，应立即终止该进程的执行，并置**调度标志**为真，用于指示该进程被终止后应重新进行调度
若该进程还有子孙进程，还应将其所有子孙进程予以终止，以防他们成为不可控制的进程
将被终止进程所拥有的全部资源，或者归还给父进程，或者归还给系统
将被终止进程（它的PCB）从所在队列（或链表）中移出，等待其他程序来搜集信息
进程的阻塞与唤醒

进程阻塞的原语操作为**block**。进程唤醒的原语操作为**wakeup**。

引起进程阻塞与唤醒的事件

请求共享资源失败
等待某种操作的完成
新数据尚未到达
等待新任务的到达
进程阻塞的过程

调用block原语
停止当前进程的执行；把PCB中的状态由“执行”改为“阻塞”
将PCB插入到阻塞队列
转调度程序进行重新调度，保留被阻塞进程的处理机状态

进程唤醒的过程
调用唤醒原语wakeup
把被阻塞进程从等待该事件的阻塞队列中移出
将其PCB中的现行状态由阻塞改为就绪
将该PCB插入到就绪队列中
进程的挂起和激活

进程挂起的原语操作为**suspend**。进程激活的原语操作为**active**。

挂起步骤

调用挂起原语suspend
检查被挂起进程的状态，若处于活动就绪状态，则将其改为静止就绪；对于活动阻塞状态的进程，则将其改为静止阻塞。
把该进程的PCB复制到某指定的内存区域
若被挂起的进程正在执行，则转向调度程序重新调度

激活步骤
调用激活原语active
将进程从外存调入内存
检查该进程的现行状态，若是静止就绪，便将之改为活动就绪；若为静止阻塞，则将其改为活动阻塞。

2.4 💡进程同步

前文说过，如果不引入进程，只是程序间的并发执行，会导致程序结果的不可再现性，在进程中，为了保证结果最后的一致性，避免无序的争夺资源，所以需要做进程同步，保证程序执行的可再现性。

💡进程同步的基本概念

两种制约形式

众所周知，引起不可再现性的核心原因就是对于共享资源访问次序的问题，所以进程和进程之间需要互相制约访问共享资源。一般存在如下两种制约关系：

间接相互制约关系

同处于一个系统的进程，必然共享着某种系统资源，如CPU, I/O等。间接制约关系源于这种资源共享。进程和进程之间只能对于这种系统资源进行互斥的访问。也就是进程A访问CPU的时候，进程B一定不可以访问CPU。

对于系统这类资源，进程在使用之前需要先提出申请，只有申请通过才可以使用这类资源。

直接相互制约

这种制约关系主要源于进程间的合作。也就是进程A和进程B需要合作完成一个任务，两个进程会共享一片数据缓冲区，进程A的执行需要等待进程B的信息。
综上：

间接制约：进行竞争——独占分配到的部分或全部的共享资源，“互斥”
直接制约：进行协作——等待来自其他进程的信息，“同步”
临界资源
所谓**临界资源**，又叫**独占资源**，实际上就是前面提到过的**共享资源**，其详细定义如下：

💡在一段时间内只允许一个进程访问的资源，即仅当一个进程访问完并释放该资源后，才允许另一个进程访问的资源，称为临界资源或独占资源。如，打印机、磁带机、共享变量、队列、……

一般情况下我们后面遇到的问题，临界资源都是程序中人为定义的变量。

后续会介绍相关例子。

临界区

💡把每个进程中访问临界资源的那段代码叫**临界区**(Critical Section)。只要每个进程互斥进入临界区、便可以实现对临界资源的互斥访问。

临界区有进入区和退出区用于标识临界区：

while(true){
    entry section // 进入区 用于检查临界资源是否空闲，有无进程进入
    critical  section; // 临界区
    exit  section  // 退出区 用于释放临界资源，将访问标志复位。
    remainder section; // 剩余区
}

💡同步机制遵循的规则（大概率考）

空闲让进：当临界资源空闲时，允许一个进程进入临界区。
忙则等待：临界资源正被访问时，其它进程必须等待，以保证对临界资源的互斥访问。
有限等待：应保证进程能在有限时间内能进入自己的临界区，以免陷入“死等”
让权等待：如果进程不能进入自己的临界区、应立即释放处理机，以免陷入“忙等”

前两个很好理解，让权等待是指如果有其他“权限”更高的进程抢占了现有进程，导致现有进程不能自己进入临界区，此时需要让权等待。有限等待是本身可以进临界区，但是前一个进程一直在临界区执行导致现有进程等待时间过长，此时需要有限等待。

硬件同步机制（了解）

关中断

关中断方式是实现进程同步最简单无脑的方式，其实现原理很简单：

在单处理机环境下，进程进入临界区之后，关闭中断，直到进程离开临界区再打开中断。

为什么关中断可以实现同步？
因为关中断可以避免临界区发生上下文切换，说人话就是关闭了中断，其他的进程就不可以通过中断处理的方式中断现有进程的执行。

在禁止中断的情况下，操作系统不会响应硬件发出的任何中断请求，包括计时器中断、I/O 中断等，这就保证了当前进程的执行不会被打断，从而使得临界区内的代码能够连续地执行完毕。

优点：

进程在临界区执行期间，计算机不响应中断，不会引发调度，不会发生进程切换或线程切换
保证了对锁的测试和关锁操作的连续性和完整性，有效地保证了互斥

缺点：

滥用关中断权力可能导致严重后果
关中断时间过长，会影响系统效率，限制了处理器交叉执行程序的能力
关中断方法也不适用于多CPU系统，因为，在一个处理器上关中断，并不能防止进程在其它处理器上执行相同临界段代码。
TS指令互斥
TS指令的全程为Test-and-Set，意思是测试并连接，这是一条原语操作。
其核心方法是给所有的临界资源添加一个布尔变量lock，也就是所谓的锁，当这个变量为true的时候，说明这个临界资源被上锁了，也就是说这个临界资源正在被访问中。当这个变量为false的时候，说明这个临界资源处于空闲状态。
TS指令的一般性描述
```
boolean TS(boolean *lock){
  boolean old; // 记录原布尔变量
  old=*lock; // 将锁值赋值给old
  *lock=TRUE; // 上锁
  return old; // 返回上锁之前的状态
}
```
TS指令实现互斥的循环结构描述 ```c do{ … while TS(&lock); // 使用TS上锁 cirtical section; // 临界区 *lock=FALSE; // 释放锁 … }while(TRUE)

当**进程A**在进入临界区前会进入TS指令当中，检查当前`lock`的值，如果`lock`实际值为`false`，代入左边的代码，返回值为上锁前的值，也就是`false`，**TS指令上锁**。这个时候由于while的条件不是`true`，所以跳出循环，此时进程A进入临界区。<br />这个时候如果进程B想要访问临界区，会卡在while循环里面，因为此时的`lock`被进程A调用了TS指令变成了`True`，那么进程B就会一直陷入循环，直到**进程A释放锁**。
> 需要注意的是，由于使用了 while 循环来不断尝试获取锁，因此代码可能会存在**饥饿问题**，即某个进程一直无法获取锁，导致无法进入临界区。
<a name="IPJTS"></a>
#### Swap指令互斥
swap指令指的是**对换指令**，在Intel 80x86又称为XCHG指令，用于交换两个字的内容。<br />其核心方法是：为每个临界资源设置一个**全局的布尔变量**`**lock**`，其初值为`false` ，在每个进程中再利用一个局部布尔变量`key`，默认都是`true`。<br />原理类似TS，这里不细讲了：<br />**swap指令的一般性描述**
```c
void swap(boolean *a,boolean *b){
    boolean temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

swap指令实现互斥的循环结构描述

do{
    key=TRUE;
    do{
        swap(&lock, &key);
       } while (key!=FALSE)
   critical section;
   lock=FALSE;
   …
}while(TRUE)

硬件同步机制的缺点

从TS指令的分析中我们可以知道，利用硬件同步最大的痛点就是如果进程进不去临界区，就会一直陷入循环等待，这不符合同步机制遵循的规则中的让权等待，这样做会浪费处理机资源。
于是出现了下面要讲的信号量机制。

信号量机制

信号量机制的原理

通常来说进程互斥的方法有两种：

由竞争各方平等协商
引入进程管理者，由管理者来协调竞争各方对互斥资源的使用

在前面讲的几种实现进程互斥的方法中：

硬件方法：当一个进程进入临界区,就屏蔽所有中断，但成本高
软件方法：用编程解决，但常忙等待

信号量机制就是引入了进程管理者，简称**管程**。

💡信号量机制的核心原理为：进程通过传递信号进行合作，可迫使某进程在某个位置暂时停止执行（阻塞等待），直到它收到一个可以“向前推进”的信号（被唤醒）。

也就是说管理消息的传递，不再定义一个所谓的全局变量，而是各个进程之间直接协商。

信号量机制是由Dijkstra提出的一种实现进程同步与互斥的通用方法，包括信号量s以及对信号量的两个原子操作wait和signal。早期这两个原语被称为**P(s)**,**V(s)**操作。

在后文中，统一使用PV操作来代替wait和signal两个原子操作的说明。

信号量类型

信号量分为：互斥信号量和资源信号量。

互斥信号量：用于申请或释放资源的使用权，常初始化为1。
资源信号量：用于申请或归还资源，可以初始化为大于1的正整数。表示系统中某类资源的可用个数。

关于两个原子操作：

Wait操作用于申请资源（或使用权），进程执行wait原语时，可能会阻塞自己；
Signal操作用于释放资源（或归还资源使用权），进程执行signal原语时，有责任唤醒一个阻塞进程。
💡整型信号量
首先定义一个整型的信号量s：
```
var s:semaphore=1;
```
💡这个信号量用于表示资源的数量。

接着就是写出关于这个整型信号量的两个原语操作wait和signal

wait(s){
    while(s<= 0);
    s--; 
} 
signal(s){
    s++;
}

注意信号量机制不是软件层面实现的，这里写代码只是为了方便理解。

上面的代码很容易看懂，也就是调用wait操作的时候，信号量s如果大于0会执行自减操作，否则就进入循环等待。当调用signal的时候，信号量**s**就会自增。

也就是说当资源大于0的时候都可以访问，小于0的时候进入等待。

这里有三个注意点：

wait(s)和signal(s)为原子操作
信号量保存在内核中，供系统的所有进程使用，占用系统资源
没有用的信号量应及时删除

由于信号量保存在内核中，所以只有系统可以改变其值，那么就不存在多个进程可以同时改变信号量的大小。

💡记录型信号量

信号量机制相比指令优秀的地方在于，进程如果获取不到资源并不是一昧的循环等待，而是进入阻塞队列中，进程会处于阻塞状态，这样就做到了让权等待，从而不浪费CPU资源。
但是很明显整型信号量机制其实并没有做到这一点，因为在wait的代码中还是出现了while的“死循环”，导致进程仍然有可能一直处于循环等待中。
所以除了记录资源的数量**value**，还需要记录一个进程链表指针list，其代码表示如下：
记录型信号结构体：

typedef  struct{
    int value;
    struct process_control_block  *list;
}semaphore;

PV操作：

wait(semaphore *S){
    S->value--;    
    if( S->value <0)
        block(S->list);//让权等待
} 
signal(semaphore *S){
    S->value++;    
    if( S->value <=0)
        wakeup(S->list);//唤醒第一个等待的进程
}

代码的理解大致同上，改变的地方在于：

调用wait的时候，资源数量小于0的时候，该进程调用block原语进入阻塞状态
调用signal的时候，资源数量小于等于0的时候，该进程调用wakeup原语进入就绪状态

说明：

每次执行完S->value--操作后，若S->value<0时，说明该类资源已分配完毕，因此进程应调用block原语，进行自我阻塞，放弃处理机，并插入到信号量链表S.list中。
每次执行完S->value++操作后，若S->value≤0时，则表示在该信号量链表中，仍有等待该资源的进程被阻塞，故还应调用wakeup原语，将S.list链表中的第一个等待进程唤醒。
若S->value的初值为1，表示只允许一个进程访问临界资源，此时的信号量转化为互斥信号量。

为什么signal中S->value小于0？因为执行signal操作的进程一定是已经访问完临界资源的进程，会释放资源。此时就需要唤醒一个被阻塞的进程（只有S->value <=0说明有进程被阻塞）尝试争取资源（注意是尝试，因为不一定只有当前线程在访问临界资源，有可能有其他的进程在访问），如果尝试失败会继续进入阻塞队列中。 S->value为什么可以等于0？因为S->value最大可以是-1，在调用signal之后进行了自增，也就变成了0。

AND信号量

假设一个情景：现在有两个进程A和B，这两个进程都需要两个临界资源1和2，出现了以下情况：

进程A获得了临界资源1，尝试获取临界资源2
进程B获得了临界资源2，尝试获取临界资源1

由于在一开始，进程AB之间获取的资源不同，所以不会冲突，但是在获取后续资源的时候，就可能会出现上述的情况，这个时候由于两个进程都没有完成自己的任务，所以不会主动释放已有资源，也就导致了互相等待的结果。这种情况被叫做死锁。
从资源分配角度来看待这个情况，就会知道发生死锁的原因就是系统在一开始没有一次性给进程分配所有的临界资源，所以导致了死锁的出现。
无论整型信号量还是记录型信号量都会发现一次只分配一种资源，所以出现了AND信号量，达到一次分配多种资源的目的。

💡AND型信号量集用于同时需要多种资源且每种资源占用一个信号量时的信号量操作

这个时候PV操作就有所变化：

wait(s) -> Swait(s1,s2,…,sn)
signal(s) -> Ssignal(s1,s2,…sn)

伪代码如下：

Swait(S1,S2,…Sn){
    while(TRUE){
        if(S1>=1 && S2>=1…&& Sn>=1){
            for (i=1;i<=n;i++)  Si--;   / /满足资源要求时的处理；
                break;
        }//if
        else {
            //某些资源不够时的处理；
            调用进程进入第一个小于1信号量的等待队列Sj;
            并把该进程的程序计数器指向swait操作的开始。
            }
    }
}
Ssignal(S1,S2,…Sn){
    while(TRUE)
        for (i=1;i<=n;i++) {
            Si++;//释放资源
            把 Si等待队列中的进程调入就绪队列。
        }//for
}

简单来说AND信号量就是记录型信号量的Plus版本，可以一次分配多个资源。

信号量集

引入了一次分配多个资源的AND信号量之后又会诞生新的问题：如果同时需要n个资源，n个资源一定同时都有剩余么？一个进程一次是否可以对同一种资源申请多个？
这就是信号量集需要解决的问题。

💡信号量集用于同时需要多种资源、每种资源的占用数目不同、且可分配的资源还存在一个临界值时的处理。临界值：就是指在某些情况下，当资源数量低于某一下限值时，便不予分配。这个下限值称作临界值。

这个时候的P操作又做了如下的改进：

Swait(S1，t1，d1，…，Sn，tn，dn)
    if (Si>=t1 && … && Sn>=tn ){
        for (i=1 ;i<= n;i++)
          Si:=Si-di；
            else {
          Place the executing process in the waiting queue of the first Si with Si<ti and set its program counter to the beginning of the Swait Operation. 
          }
    }
}

Ssignal操作我没找到，不过不重要，这个代码看一遍就好，主要了解原理。

其中传入的参数不只是Si：

ti：表示该资源i的下限值，当**S****i**小于**t****i**的时候，系统不会为该进程分配资源i
di：表示这个线程一次需要申请资源i的数量

这里有三种特殊的信号量集：

Swait(s,**d**,**d**)：允许每次申请d个资源。当资源数少于d时，不予分配。
Swait(s,**1**,**1**)：S>1，资源信号量。S=1时，互斥信号量。
Swait(s,**1**,**0**)：可控开关，当s>=1时，允许进入，当s变为0后，阻止任何进程不能进入。

💡信号量的应用

信号量实现线程互斥
这一点很简单，只需要为临界资源设置一个互斥信号量即可，一般我们把这个互斥信号量写作mutex，其初始值为1。
```
semaphore mutex=1; // 定义互斥信号
Pa(){ // 进程A
  while(1){
      wait(mutex); // 尝试获取资源并上锁
      临界区；
        signal(mutex); // 释放锁
      剩余区；
  }
}
Pb(){ // 进程B
  while(1){
      wait(mutex); // 尝试获取资源并上锁
      临界区；
        signal(mutex); // 释放锁
      剩余区；
  }
}
```
需要主要的是，wait和signal必须成对出现，否则会出现临界资源永远不被释放的问题。

实现前驱关系
假设有六个进程和六个资源：
```
p1(){ S1; signal(a); signal(b); }
p2(){ wait(a); S2; signal(c); signal(d); }
p3(){ wait(b);S3; signal(e); }
p4(){ wait(c);S4; signal(f); }
p5(){ wait(d);S5; signal(g); }
p6(){ wait(e); wait(f);wait(g);S6; }
main(){
  semaphore a,b,c,d,e,f,g;
  a.value=b.value=c.value=d.value=e.value=f.value=g.value=0;
  cobegin
      p1();p2();p3();p4();p5();p6();
  coend  
}
```
可以画出如下前驱图：

wait表示的就是需要等待的资源，箭头向内；signal就是释放的资源，箭头向外。

管程机制（了解）

管程的定义
前面说过，如果想要通过信号量同步，那么就需要保证每一个进程都配备一对PV操作，这样就会导致大量的同步操作分散在各个进程当中。缺点如下：
同步操作分散：使用不当就可能导致各进程死锁
易读性差：要了解对于一组共享变量及信号量的操作是否正确，必须通读整个系统或者并发程序
不利于修改和维护：各模块的独立性差，任一组变量或一段代码的修改都可能影响全局
正确性难以保证：操作系统或并发程序通常很大，很难保证这样一个复杂的系统没有逻辑错误

所以出现了管程——一种管理进程同步的工具。

💡管程：一个管程定义了一个数据结构和能为并发进程所执行（在该数据结构上）的一组操作，这组操作能同步进程和改变管程中的数据。管程组成： ① 局部于管程的共享变量说明 ② 对该数据结构进行操作的一组过程 ③ 对局部于管程的数据设置初始值的语句 ④ 还须为管程赋予一个名字。

管程如何实现进程同步

这一节书上没有，只是为了更好理解管程写的，可以不看。

管程主要思想是通过一个抽象数据类型来封装共享资源和对共享资源的操作，以保证资源的正确性和并发访问的安全性。
管程实现进程同步通常包括以下几个步骤：

定义管程类（Monitor Class），其中包含共享资源和对资源的操作（例如读写、修改等）。
编写管程类中的方法，需要给相关的共享资源进行上锁等操作，以确保同一时刻只有一个进程可以访问共享资源。
对于每个进程，需要先获得管程对象的锁，然后再执行管程中的方法
执行完方法后，再释放锁，以便其他进程可以获取锁并继续访问共享资源
管程类中通常还会包含条件变量，用于实现进程间的等待和唤醒操作。

当进程需要等待某个条件满足时，可以调用条件变量的wait()方法使自己进入等待状态；当其他进程修改了共享资源并通知条件变量时，可以调用条件变量的signal()唤醒正在等待的进程。

简单的来说，管程就是把共享资源和对于共享资源的相关操作全部抽象成了一个“抽象数据类”，不同进程中就不需要写对于共享资源的访问、上锁释放锁等操作了，只需要进入管程中，然后在管程中执行相关操作，最后退出管程即可。

管程的主要特性

模块化：一个管程是一个基本程序单位，可以单独编译
抽象数据类型：管程是一种特殊的数据类型，其中不仅有数据，而且有对数据进行操作的代码
信息封装：管程是半透明的，管程中的过程（函数）实现了某些功能，至于这些功能是怎样实现的，在其外部则是不可见的

当做面向对象来看就是了。

管程和进程的区别

	进程	管程
结构	私有数据结构PCB	公共数据结构
操作	由对应的代码段决定	同步操作和初始化操作
目的	为了实现并发	解决临界资源的互斥使用
工作方式	主动	被动
是否并发	并发	非并发
调用	动态性	资源管理模块，供进程调用

条件变量

设置条件变量是为了应对进程被挂起或阻塞，由于进程被挂起或者阻塞的原因可能有多个，所以条件变量也是多个。
这里再引入一个知识点

为了进一步保证进程互斥，进程进入管程这一步也是互斥的。

所以有一种可能，就是某一个进程进入了管程，但是获取不到资源所以被阻塞着，此时进程又不释放管程，导致其他进程也进不了管程。此时就需要条件变量了。
管程会记录每个条件变量，形式为condition x,y...;管程对于每个条件变量都保存了一个链表，用户记录因为该条件变量二阻塞的所有进程，当管程中的进程符号某一个条件变量，这个进程进入到这个链表当中，然后释放对于管程的使用。这样其他的进程就可以进入管程执行相关操作了。
对于每一个条件变量，提供了两个操作，以条件x为例，也就是：

x.wait：阻塞或挂起进程
x.signal：唤醒或激活进程

这个时候又有个很明显的问题：
当进程P进入管程后，执行了x.wait进入到阻塞队列之后，此时进程Q进入管程，执行了x.signal导致进程P被唤醒回到管程，那这个时候管程中就出现了两个进程，这个时候应该执行哪个进程呢？
有两种方案：

P等待，直至Q离开管程或等待另一条件
Q等待，直至P离开管程或等待另一条件

2.5 💡经典进程的同步问题

生产者——消费者问题

问题描述

若干进程通过有限的共享缓冲区交换数据。“生产者”进程不断写入，而“消费者”进程不断读出；共享缓冲区共有N个；生产者和消费者必须保持同步。当n个单元装满时，生产者必须等待；当缓冲池空时，消费者必须等待。

简单来说就是**生产者**在格子里生产数据，生产一个指针前移一位（越界就从头循环），**消费者**在后面消费格子里面的数据，消费一个指针也跟进一位（越界就从头循环）。

要点分析

在这个问题当中，很明显生产者是一个进程，消费者也是一个进程，而共享资源就是上面图中的“格子”，这两个进程之间对于格子的访问应该是互斥的，也就说不能同时生成和消费同一个格子的数据。
进程之间互斥访问缓冲池就需要一个互斥信号量，这里设定为mutex。
再思考一下这两个进程什么时候会被阻塞和唤醒：

当缓冲池满数据时，生产者进程应该被阻塞；当缓冲池空数据时，生产者进程应该被唤醒
当缓冲池无数据时，消费者进程应该被阻塞；当缓冲池有数据时，消费者进程应该被唤醒

这里空数据不是说没有数据，而是有“格子”中没有数据。

于是可以定义两个共享变量，用于确定两个进程什么时候阻塞和唤醒，那么假设缓冲区的数量为**n**：

利用empty表示缓冲池中空缓冲区数量，控制**生产者**，初始值为**n**
利用full表示缓冲池满缓冲区数量，控制**消费者**，初始值为**0**

对于这两个变量有：

empty > 0：生产者唤醒
empty <= 0：生产者阻塞
full > 0：消费者唤醒
full <= 0：消费者阻塞

利用记录型信号量解决
直接看代码，首先初始化相关的共享资源、操作指针以及缓冲池：
```
Semaphore mutex,empty,full=1,n,0; //     
item buffer[n];
int in=0, out=0;
```
mutex：互斥信号量
empty：空缓冲区数量，初始为n（也就是无数据）
full：满缓冲区数量，初始为0（也就是无数据）
buffer：缓冲池，大小为n
in、out：生产者和消费者访问缓冲池的指针。

接下来看生产者和消费者的代码：
生产者

void producer(){
    do{ produce an item nextp;
       …
       wait(empty); // 缓冲池有空才访问
       wait(mutex);    // 资源空闲才访问
       buffer[in]=nextp; // 生产数据
       in=(in+1)%n; // 指针后移
       signal(mutex); // 释放资源    
       signal(full); // 释放该满缓冲区
    }while(true);
}

消费者

void consumer(){
    do{  
        wait(full);//缓冲池有数据才访问
        wait(mutex);//资源空闲才访问   
        nextc=buffer[out];// 消费数据
        out=(out+1)%n;//指针后移
        signal(mutex);//释放资源
        signal(empty);//释放该空缓冲区
        consumer the item in nextc;
        …
    }while(true);
}

这里参照前面讲过的知识可知道两对PV操作的核心：

wait(empty) -> empty—
signal(empty) -> empty++
wait(full) -> full—
signal(full) -> full++

也就是说对于生产者，每执行一次，空缓冲区-1，满缓冲区+1，消费者反之。

接下来以生产者为例，自习看一下核心的四句代码：

wait(empty); // 缓冲池有空才访问
wait(mutex);    // 资源空闲才访问
signal(mutex); // 释放资源    
signal(full); // 释放该满缓冲区

思考一下第1和第2句，以及第3和第4句是否可以交换。点击展开查看答案前两句不可以，后两句可以。
因为如果生产者先获取mutex这个锁，接下来就应该去获得empty这个锁，如果这个时候empty正好小于等于0，生产者进程就会阻塞。而由于生产者提前拿到了mutex这个锁，消费者不能进入临界区，也就无法通过消费者进程去释放empty，于是陷入了死锁当中。

也就是生产者在等empty，消费者在等mutex。

后面两句则没有这个问题，因为本身就不存在等待资源这个说法。

利用AND型信号量解决

从上面生产者例子中我们知道，按照记录型信号的写法，如果wait语句顺序不当，就有可能出现死锁的情况，这就可以用AND信号量一次分配所有资源来解决这个问题：
生产者

void producer(){
    do{
        produce an item nextp;     
        swait(empty,mutex);
        buffer[in]=nextp;
        in=(in+1)%n;
        signal(mutex,full);        
    }while(true);
}

消费者

void consumer(){
    do{
        swait(full,mutex);    
        nextc=buffer[out];
        out=(out+1)%n;
        signal(mutex,empty);
        consumer the item in nextc;
    }while(true);
}

同时分配empty和mutex资源就不会出现死锁问题了。

利用管程解决

设计管程的需要考虑的东西如下：

共享变量：empty、full、总数count以及缓冲池buffer
共享变量过程：获得数据和写入数据
- put(item)过程。生产者利用该过程将自己生产的产品投放到缓冲池中，并用整型变量count来表示在缓冲池中已有的产品数目，当count≥n时，表示缓冲池已满，生产者须等待。
- get(item)过程。消费者利用该过程从缓冲池中取出一个产品，当count≤0时，表示缓冲池中已无可取用的产品，消费者应等待。
条件变量：阻塞队列条件和唤醒队列条件
- cwait(condition)过程。当管程被一个进程占用时，其他进程调用该过程时阻塞，并挂在条件condition的队列上。
- csignal(condition)过程。唤醒在cwait执行后阻塞在条件condition队列上的进程，如果这样的进程不止一个，则选择其中一个实施唤醒操作；如果队列为空，则无操作而返回。

代码设计如下：

Monitor producer-consumer{
    item buffer[n];
    int in,out,count
    condition notfull, notempty;
    public:
    void put(item x){
        if (count>=n)  cwait(notfull);
        buffer[in]=nextp;
        in =(in+1) % n;
        count=count+1;
        csignal(notempty);
    }//end put     
    void get(item x){
        if (count<=0)
            cwait(notempty);
        x=buffer[out];
        out =(out+1) % n;
        count=count+1;
        csignal(notfull);
    }//end get
    {in=0;out=0;count=0;}
}PC;

这一部分代码只需要了解即可。

接下里看在生产者和消费者中如何调用管程：
生产者

void producer(){
    itex x;
    while(1){
        produce an item in nextp;
        PC.put(x);
    }
}

消费者

void consumer(){
    item x;
    while(1){
        PC.get(x);
        consume the item in nextc;
    }
}

哲学家进餐问题

问题描述

:::tips 五个哲学家共用一张圆桌，分别坐在周围的五张椅子上，在圆桌上有五个碗和五只筷子，他们的生活方式是交替地进行思考和进餐。平时，一个哲学家进行思考，饥饿时便试图取用其左右最靠近他的筷子，只有在他拿到两只筷子时才能进餐。进餐后，放下筷子继续思考。 ::: 中间棕色部分表示筷子

要点分析

很明显五个哲学家代表了五个进程，而五个筷子表示了五个互斥信号量。
哲学家问题最主要的就是死锁问题。
最简单的假设就是所有的哲学家一开始都可以拿到左边的筷子，但是这样场上所有的筷子都被拿走了，所有的哲学家都在等待右边的哲学家释放筷子。
解决了死锁问题就解决了哲学家进餐问题。
解决思路有以下几种：

限制同时只允许4个哲学家进餐
当哲学家左右筷子均可用时，才能拿起筷子进餐
限制拿起筷子的方法：一部分（偶数）先拿左边、一部分（奇数）先拿右边
利用记录型信号量解决（死锁）
如果利用记录型信号量，假设每次都先拿左边的筷子，再拿右边的筷子，伪代码如下： ```c semaphore chopstick[5]={1,1,1,1,1}; // 筷子资源 Do{ wait(chopstick[i]); // 拿左边的筷子 wait(chopstick[(i+1) mod 5]); // 拿右边的筷子 …; eat; …; signal(chopstick[i]); // 释放左边的筷子 signal(chopstick[(i+1) mod 5]); // 释放右边的筷子 …; think; }while(TRUE);

这里就会出现死锁问题，解决问题的最简单的思路就是一次性直接分配两个筷子的资源，这个时候就要用到`AND信号量`。
<a name="i4WQm"></a>
#### 利用AND信号量解决
AND信号量解决的伪代码如下：
```c
Semaphore chopstick[5]={1,1,1,1,1};
do{
    swait(chopstick[i], chopstick[(i+1)%5]);
    …;
    eat;
    …;
    ssignal(chopstick[i], chopstick[(i+1)%5]);
    …;
    think;
}while(true)

读者——写者问题

问题描述

:::tips 一个文件被多个进程共享，有些要求读——Reader，有些要求写入或修改——Writer；允许同时读，不允许一个writer与其他writer进程或reader进程同时操作。
简单描述就是：

“读－写”互斥
“写－写”互斥
“读－读”允许 :::

要点分析
根据上述问题的描述，可以设置以下信号量：
Wmutex：保证写互斥的信号量。
Readcount:表示正在读的读者数量。
rmutex:保证互斥修改读者数量的信号量，保证对Readcount的互斥访问。

初始值设置：

Wmutex = 1：描述文件开始可用
Readcount = 0：表示初始还没有读者
rmutex = 1：表示可以修改读者计数器。
利用记录型信号量解决
```c semaphore rmutex,wmutex =1,1; // 定义读写信号量 int readcount =0; // 定义正在读文件的进程个数

// 读者 reader(){ do{ wait(rmutex); if (readcount==0) wait(wmutex); readcount++; signal(rmutex); …; perform read operation; …; wait(rmutex); readcount—; if (readcount==0) signal(wmutex); signal(rmutex); }while(true); }

// 写者 writer(){ do{ wait(wmutex); perform write operation; signal(wmutex); }while(true); }

`写者`部分很好分析，如果写者需要占用CPU资源，就只需要等待`**wmutex**`**信号量**即可，执行完相关写操作之后就可以释放资源。<br />而`读者`部分需要考虑的就比较多，首先是多个`读进程`的控制其实并不是由`rmutex`控制的，因为如果由`rmutex`直接控制互斥`读进程`会导致从始至终最多只有一个`读进程`，就像写进程一样。<br />所以真正控制写进程的是`**wmutex**`**，只有**`**wmutex = 1**`**的时候，也就是没有**`**写进程**`**的时候才可以执行**`**读进程**`。**同样只有没有**`**读进程**`**的时候才可以执行**`**写进程**`。<br />所以这里需要一个`readcount`统计读进程的数量，数量为0的时候需要再保证写进程没有，不为0则不需要。
<a name="p7sUc"></a>
#### 利用信号量集解决
> 不重要，看看就行
```c
void reader(){
    do{
        Swait(L,1,1);
        Swait(mx,1,0) ;
        …;
        perform read operation;
        …;
        Ssignal(L,1);         
    }while(TRUE);
}
void writer(){
    do{
        Swait(mx,1,1; L,RN,0);
        perform write operation ;
        Ssignal(mx,1);
    }while(TRUE);
}

2.6 进程通信

进程通信指的是进程之间进行信息交换。比如上面所说的进程互斥信息或者进程同步信息也算是进程通信的一种。
OS提供了高级的通讯工具，可以让进程之间传送大量数据，这个工具的优点有：

使用方便
高效

进程通信的类型
进程之间的通信内容包含两种类型：控制信息和大批量数据。
根据两种信息可以把通信类型分为两类：
高级通信：进程之间交换批量数据的过程
低级通信：进程之间交换控制信息的过程

其中高级通信利用操作系统提供的通信命令（通常是高级通信原语），实现进程之间的相互制约、相互协调地进行信息传送地通信命令。
高级通讯方式有：

共享存储器系统
管道通信系统
消息传递系统
C/S系统
共享存储系统
在共享存储器系统中，相互通信的进程共享某些数据结构或共享存储区，进程之间能够通过这些空间进行通信。又可以分为以下两种类型：
(1)基于共享数据结构的通信方式
该种通信方式中，要求诸进程公用某些数据结构，借以实现诸进程间的信息交换。如生产者-消费者问题中的共享缓冲池。

这种传送数据的效率低下，属于低级通信。

(2)基于共享存储区的通信方式
为了传输大量数据，在存储器中划出了一块共享存储区，诸进程可通过对共享存储区中数据的读和写来实现通信。

通信步骤如下：

申请共享存储区
连接共享存储区到进程的存储空间
互斥访问共享存储区
归还共享存储区

这种传输方式效率较高，属于高级通信。

管道通信系统

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

向管道（共享文件）提供输入的发送进程（即写进程），以字符流形式将大量的数据送入管道；而接受管道输出的接收进程（即读进程），则从管道中接收（读）数据。

管道需要提供以下的协调能力：

互斥
同步
确定对方是否存在，只有确定了对方已存在时，才能进行通信
消息传递系统
在消息传递系统中，进程间的数据交换，是以格式化的消息（Message）为单位的。程序员直接利用系统提供的一组通信命令进行通信。

当今最为流行的微内核操作系统中，微内核与服务器之间的通信，无一例外地都采用了消息传递机制。

其实简单来讲，消息传递系统就是操作系统把需要传递的数据封装为**消息**进行传递。这种方式隐藏了通信实现的细节，让通信过程对于用户透明化，降低了通信设计的复杂度和错误率。
其具体的实现方式有两种：

直接通信方式：发送进程利用OS所提供的发送命令，直接把消息发送给目标进程
间接通信方式：通过中间实体（也称为信箱）来暂存发送进程发送给目标进程的消息，接收进程则从该实体中接收发送给自己的消息

客户机-服务器系统
客户机-服务器系统的通信机制，在网络环境下的各种应用领域以成为当前主流的通信实现机制。
其主要的实现方法有三类：
套接字：一种网络程序接口
远程方法调用和远程过程调用：一个通信协议

2.7 线程(THREAD)的基本概念（不考）

线程的引入

进程的两个属性为：

进程是一个可拥有资源的独立单位
进程是一个可独立调度和分派的基本单位

OS中引入进程的目的是使得多个程序可以并发执行，那么引入线程的目的是为了减少程序再并发执行所付出的时空开销，使得OS有更好的并发性。

进程最主要的时空开销为：

创建进程：系统在创建进程时，必须为之分配其所必需的、除处理机以外的所有资源。如内存空间、I/O设备以及建立相应的PCB
撤消进程：系统在撤消进程时，又必须先对这些资源进行回收操作，然后再撤消PCB
进程切换：在对进程进行切换时，由于要保留当前进程的CPU环境和设置新选中进程的CPU环境，为此需花费不少处理机时间

由于进程是一个资源的拥有者，所以在创建、撤销和切换中，系统必须付出较大的时空开销。正因如此，系统中设置的进程数目不宜过多，进程切换频率也不宜过高，这就限制了并发程度的进一步提高。

线程和进程的比较

比较点	进程	线程
调度的基本单位	切换进程时，需要进行上下文借还，开销较大	切换线程时，仅需保存和设置少量的寄存器内容，代价较低
并发性	相对低	相对高
拥有资源	拥有系统资源	只拥有可以保证独立运行的资源
独立性	高	低
系统开销	大	小
处理机	支持一个处理机	支持多个处理机

线程状态和线程控制块

线程运行的三个状态

线程三个状态为：

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

和进程的状态是一致的，包括状态之间的转换，所以这里不展示状态的转换了。

线程控制块TCB

和进程类似，每个线程都需要配备一个线程控制块TCB。包含以下内容：

线程标识符
一组寄存器，包括程序计数器，状态寄存器和通用寄存器
线程运行状态
线程优先级
线程专有存储区
信号屏蔽
堆栈指针
多线程中OS的进程属性
通常情况下，一个进程可以包含多个线程，当OS支持在进程中创建线程，此时的进程就不再作为一个执行的实体，而是扮演一个给线程提供资源的角色。
进程此时有了以下的属性：

作为系统资源分配的单位
包括多个线程，多个线程之间可以并发执行
进程不是一个可执行的实体

2.8 线程的实现

线程的实现方式

在学习本节之前，可以先回顾一下什么是用户态什么是内核态，参见进程控制这一小节的内容。

内核支持线程KST

内核支持线程KST（Kernel Supported Threads），指的是在内核支持下运行的，即无论是用户进程中的线程，还是系统进程中的线程，他们的创建、撤销和切换等也是依靠内核，在内核空间实现的。线程管理的所有工作都由内核完成。

内核支持线程的方式有以下几个优点：

在多处理器系统中，内核能同时调度同一进程中的多个线程并行执行；
如果进程中的一个线程被阻塞了，内核可以调度该进程中的其他线程或运行其他进程中的线程；
内核支持线程具有很小的数据结构和堆栈，线程的切换比较快，切换开销小；
内核本身也可以采用多线程技术，可以提高系统的执行速度和效率。

个人觉得内核支持线程还有一个优点，就是由于内核可以直接操作系统资源，所以相对下面的用户级线程其执行速度会更快。

缺点如下：
对于用户的线程切换而言，其切换的开销较大

在同一个进程中，从一个线程切换到另一个线程时，需要从用户态转到内核态进行，这种上下文开销是很大的。

用户级线程ULT

用户级线程ULT(User Level Threads)仅存在于用户空间中。对于这种线程的创建、撤销、线程之间的同步与通信等功能，都无须利用系统调用来实现。线程的管理由应用程序完成，在用户空间中实现，内核无需感知线程的存在。

对于用户级线程的切换，通常发生在一个应用进程的诸多线程之间，这时，也同样无须内核的支持。

优点：

线程切换不需要转换到内核空间
调度算法可以是线程专用的
用户级线程的实现与操作系统平台无关

缺点：

系统调用的阻塞问题

用户级线程执行系统调用时，不仅该线程阻塞，而且进程内的所有线程都会阻塞，而内核支持线程方式中，进程中的其它线程仍然可以运行；
在单纯的用户级线程实现方式中，多线程应用不能利用多处理机进行多重处理的优点

内核每次分配给进程的只有一个CPU，因此进程中仅有一个线程能执行

组合方式

简单来说就是对于用户级线程和内核支持线程的结合，它能够结合KST和ULT两者的优点，并克服了各自的不足。其核心思想为：用户层进行选择一部分用户级线程映射到一些内核级线程上。其方式有以下三种：

多对一模型：将多个用户线程映射到一个内核控制线程
一对一模型：将每个用户线程映射到一个内核控制线程
多对多模型：将多个用户线程映射到同样数量或更少数量的内核线程上

实验

Linux常见文件操作命令

命令	说明
ls	列出当前工作目录中的文件和目录。
cd [dir]	更改当前工作目录到指定目录。
mkdir [dir]	创建一个新目录。
touch [file]	创建一个新文件。如果文件已经存在，则更新文件修改时间戳。
rm [file]	删除指定的文件。使用 -r 参数可以递归删除子目录和其中所有的文件。
cp [file] [newfile]	复制文件到新位置。如果目标文件名已经存在，则会覆盖它。使用 -r 参数可以递归复制目录和其中所有的子目录和文件。
mv [file] [newfile]	移动或重命名文件或目录。如果目标文件名已经存在，则会覆盖它。
cat [file]	显示指定文件的内容。
less [file]	快速浏览文件的内容，可以让您上下滚动并查找特定文本。
head [file]	显示文件头部的几行内容。默认为10行。
tail [file]	显示文件尾部几行的内容。默认为10行。
grep [pattern] [file]	在文件中查找匹配的字符串。grep 也可以读取标准输入，并显示与给定模式匹配的所有行。
find [path] -name [name]	在指定路径下查找指定名称的文件。这个命令非常强大，可以使用不同的谓词和选项来搜索符号链接、不同类型的文件、特定时间戳等。
ls	列出当前工作目录中的文件和目录。
cd [dir]	更改当前工作目录到指定目录。
mkdir [dir]	创建一个新目录。
touch [file]	创建一个新文件。如果文件已经存在，则更新文件修改时间戳。
rm [file]	删除指定的文件。使用 -r 参数可以递归删除子目录和其中所有的文件。
cp [file] [newfile]	复制文件到新位置。如果目标文件名已经存在，则会覆盖它。使用 -r 参数可以递归复制目录和其中所有的子目录和文件。
mv [file] [newfile]	移动或重命名文件或目录。如果目标文件名已经存在，则会覆盖它。
cat [file]	显示指定文件的内容。
less [file]	快速浏览文件的内容，可以让您上下滚动并查找特定文本。
head [file]	显示文件头部的几行内容。默认为10行。

Linux运行C程序

首先创建一个c文件

文档名后缀改为C。

在文档中编写一个简单的hello world代码

在当前文件夹下打开终端，输入以下命令
```
gcc -o test demo.c
```
其中test是编译之后的文件名字，可以自取。demo.c就是刚刚创建的c文件。
之后输入一下命令进行运行：
```
./test
```

如果需要运行的程序是一个多线程程序：

gcc thread.c -pthread -o thread
./thread

其中thread是文件名

使用线程模拟消费者生产者问题

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <semaphore.h>
#define BUFF_SIZE 20 // 缓冲区大小
#define PRODUCER_NUM 10 // 生产者数量
#define CONSUMER_NUM 3 // 消费者数量
sem_t empty, full; // 定义信号量变量
pthread_mutex_t mutex;    // 互斥锁
int buffer[BUFF_SIZE]; // 缓冲区
int in = 0, out = 0; // 缓冲区指针
void *producer(void *param);
void *consumer(void *param);
int main() {
    pthread_t producers[10], consumers[10]; // 生产者线程和消费者线程
    // 初始化信号量
    sem_init(&empty, 0, BUFF_SIZE);
    sem_init(&full, 0, 0);
    // 创建生产者线程
    int i;
    for(i = 0 ; i< PRODUCER_NUM ; i++) {
        pthread_create(&producers[i], NULL, producer, (void*)(long)i);
    }
    // 创建消费者线程
    for(i = 0 ; i < CONSUMER_NUM ; i++) {
        pthread_create(&consumers[i], NULL, consumer, (void*)(long)i);
    }
    // 等待所有线程完成
    for(i = 0; i < PRODUCER_NUM ; i++) {
        pthread_join(producers[i], NULL);
    }
    for(i = 0; i < CONSUMER_NUM ; i++) {
        pthread_join(consumers[i], NULL);
    }
    // 销毁信号量
    sem_destroy(&empty);
    sem_destroy(&full);
    return 0;
}
// 生产者
void *producer(void *param) {
    int id = (int)(long)param;
    sem_wait(&empty); // 等待empty信号量
    pthread_mutex_lock(&mutex);
    buffer[in] = rand(); // 生产数据
    printf("Producer %d produces item %d\n", id, buffer[in]);
    in = (in + 1) % BUFF_SIZE; // 修改缓冲区指针
    pthread_mutex_unlock(&mutex);
    sem_post(&full); // 释放full信号量
    pthread_exit(0);
}
// 消费者
void *consumer(void *param) {
    int id = (int)(long)param;
    int item;
    sem_wait(&full); // 等待full信号量
    pthread_mutex_lock(&mutex);
    item = buffer[out]; // 消费数据
    printf("Consumer %d consumes item %d\n", id, item);
    out = (out + 1) % BUFF_SIZE; // 修改缓冲区指针
    pthread_mutex_unlock(&mutex);
    sem_post(&empty); // 释放empty信号量
    pthread_exit(0);
}

第二章：进程的描述与控制

2.1 💡前趋图和程序执行

前驱图

前驱图的定义

前驱图不应该出现循环

程序的顺序执行及其特征

程序的顺序执行

程序顺序执行的特征

程序的并发执行及其特征

程序的并发执行

并发执行的特征

与顺序执行对比

并发执行引起的问题

2.2 进程的描述

进程的定义和特征

💡进程的定义

引入进程的问题

💡进程的特征

💡进程的基本状态以及转换

进程的三种基本状态

三种基本状态的转换

创建状态和终止状态

挂起操作和进程状态的转换（了解即可）

挂起操作的引入

引入挂起原语操作后的三个进程状态的转换

引入挂起操作后五个进程状态的转换

💡进程管理中的数据结构

操作系统中用于管理控制和数据结构

进程控制块PCB的作用

进程控制块中的信息

进程控制块的组织方式

2.3 💡进程控制

操作系统内核

支撑功能

资源管理功能

进程的创建

进程的层次结构

引起进程创建的事件

进程的详细创建

进程的终止

引起进程终止的事件

进程终止的过程

进程的阻塞与唤醒

引起进程阻塞与唤醒的事件

进程阻塞的过程

进程唤醒的过程

进程的挂起和激活

挂起步骤

激活步骤

2.4 💡进程同步

💡进程同步的基本概念

两种制约形式

临界资源

临界区

💡同步机制遵循的规则（大概率考）

硬件同步机制（了解）

关中断

TS指令互斥

硬件同步机制的缺点

信号量机制

信号量机制的原理

信号量类型

💡整型信号量

💡记录型信号量

AND信号量

信号量集

💡信号量的应用

信号量实现线程互斥

实现前驱关系

管程机制（了解）

管程的定义

管程如何实现进程同步

管程的主要特性

管程和进程的区别

条件变量

2.5 💡经典进程的同步问题

生产者——消费者问题

问题描述

要点分析

利用记录型信号量解决