进程管理 | 温存的小窝

[TOC]

一、进程概述

进程：一个具有一定独立功能的程序关于某个数据集合的一次运行活动，是系统进行资源分配和调度的一个独立单位。

进程的组成

程序的代码
程序处理的数据
程序计数器中的值（下一条将运行指令的地址）
一组通用的寄存器的当前值，堆，栈
一组系统资源（如打开的文件）

进程与程序的联系
1.程序是产生进程的基础。
2.程序的每次运行构成不同的进程。
3.进程是程序功能的体现。
4.通过多次执行，一个程序可对应多个进程；通过调用关系，一个进程可包括多个程序。

进程与程序的区别
1.进程是动态的，程序是静态。程序是有序代码的集合；进程是程序的执行，进程会涉及到核心态和用户态的切换。
2.进程是暂时的，程序是永久的。进程是一个状态变化的过程，程序可长久保存。
3.进程与程序的组成不同。
进程=程序+数据+进程控制块。

进程的特征

动态性：进程是程序的一次执行，它有着创建、活动、暂停、终止等过程，具有一定的生命周期，是动态地产生、变化和消亡的。动态性是进程最基本的特征。
并发性：指多个进程实体，同存于内存中，能在一段时间内同时运行，并发性是进程的重要特征，同时也是操作系统的重要特征。引入进程的目的就是为了使程序能与其他进程的程序并发执行，以提高资源利用率。
独立性：指进程实体是一个能独立运行、独立获得资源和独立接受调度的基本单位。凡未建立PCB的程序都不能作为一个独立的单位参与运行。
异步性：由于进程的相互制约，使进程具有执行的间断性，即进程按各自独立的、不可预知的速度向前推进。异步性会导致执行结果的不可再现性，为此，在操作系统中必须配置相应的进程同步机制。
结构性：每个进程都配置一个PCB对其进行描述。从结构上看，进程实体是由程序段、数据段和进程控制段三部分组成的。

二、进程控制块

PCB：操作系统管理控制进程运行所用的信息集合。
PCB是用来描述进程的数据结构。操作系统为每个进程都维护了一个PCB，用来保存与该进程有关的各种状态信息。

PCB中存储的信息

（一）进程标识信息
如本进程的标识，本进程的产生着标识（父进程标识），用户标识等。

（二）处理机状态信息保存区
用户可见寄存器，用户程序可以使用的数据，地址等寄存器；
控制和状态寄存器，如程序计数器，程序状态字；
栈指针，系统带调用/中断处理和返回时需要用到它。

（三）进程控制信息
调度和状态信息，用于操作系统进程并占用处理机使用。
进程间通信信息，为支持进程间的与通信相关的各种标识，信号等这些信息存在接收方的进程控制块中。
存储管理信息，包含有指向本进程映像存储空间的数据结构。
进程所用资源，说明由进程打开，使用的系统资源。
有关数据结构连接信息，进程可以连接到一个进程队列中，或连接到相关其他进程的PCB。

PCB的组织方式

1.链表：同一状态的进程其PCB成一链表，多个状态对应多个不同的链表。如就绪链表，阻塞链表。
2.索引表：同一状态的进程归入一个index表，多个状态对应多个不同的index表。如就绪索引表，阻塞索引表。

注：一般会选择链表，因为可能面临进程创建，销毁等调度导致进程状态发生变化，所以链表能够更加灵活的插入和删除。

三、进程的状态

3.1 进程生命周期管理

操作系统对于进程有一些生命周期的管理，大致有：

进程创建
进程运行
进程等待
进程唤醒
进程结束

进程创建

场景：
1.系统初始化。
2.用户请求创建一个新进程。
3.正在运行的进程执行了创建进程的系统调用。

进程运行

内核选择一个就绪进程，让它占用处理机并执行（和处理机调度算法有关）。

进程等待（阻塞）

场景：
1.请求并等待系统服务，无法马上完成。
2.启动某种操作，无法马上完成。
.需要的数据没有到达。

注：进程只能自己阻塞自己，因为只有进程自身才能知道何时需要等待某种时间的发生。

进程唤醒

场景：
1.被阻塞进程需要的资源可被满足。
2.被阻塞进程等待的事件到达。
3.将该进程的PCB插入到就绪队列。

注：进程只能被别的进程或操作系统唤醒。

进程结束

场景：
正常退出（自愿）
错误退出（自愿）
致命错误（强制）
被其他进程所杀（强制）

3.2 进程的三种基本状态

三种基本状态有
运行状态：当一个进程正在处理机上运行时。
就绪状态：一个进程获得了除处理机之外的一切所需资源，一旦得到处理机即可运行。
等待（阻塞）状态：一个进程正在等待某一事件而暂停运行。

其他基本状态
创建状态：一个进程正在被创建，还没被转到就绪状态之前的状态。
结束状态：一个进程正在从系统中消失时的状态。

到目前为止我们的认知应该是这个亚子…

图片来源于网络

注：就绪也叫活动就绪；阻塞也叫活动阻塞。

3.3 挂起

学习操作系统应该都有听过挂起状态，有了阻塞为什么还要挂起呢，进程挂起和阻塞有什么区别，都将在下面整理。

挂起：把一个进程从内存转到外存。
进程在挂起时，不会占用内存空间。处在挂起状态的进程映像在磁盘上。

挂起状态
阻塞挂起状态：进程在外存并等待某事件的出现。
就绪挂起状态：进程在外存，但要进入内存，即可运行。

注：阻塞挂起也叫静止阻塞；就绪挂起也叫静止就绪。

非挂起与挂起间的状态转换
阻塞->阻塞挂起：没有进程处于就绪进程或就绪进程要求更多内存资源时，会进行这种转换，以提交新进程或运行就绪进程。

就绪->就绪挂起：当有高优先级阻塞进程和低优先级就绪进程时，系统会选择挂起低优先级就绪进程。

运行->就绪挂起：对抢先式分时系统，当有高优先级阻塞挂起进程因事件出现而进入就绪挂起时，系统可能会把运行进程转到就绪挂起状态。

挂起与挂起间的状态转换
阻塞挂起->就绪挂起：当有阻塞挂起进程因相关事件出现时，系统会把阻塞挂起进程转换为就绪挂起进程。

挂起与非挂起的状态转换
解挂/激活：把一个进程从外存转到内存。
就绪挂起->就绪：没有就绪进程或就绪进程优先级高于就绪进程时。
阻塞挂起->阻塞：当一个进程释放足够内存时，系统会把一个高优先级阻塞挂起，进程转换为阻塞进程。

增加了挂起状态后，我们的认知应该更新为这个亚子：

3.4 状态队列

进程的状态这个多，操作系统是怎么管理的呢？操作系统维护了一组队列，表示系统中所有进程的当前状态。

简单来说，每个进程的PCB都根据它的状态加入到相应的队列中，当一个进程的状态发生变化时，它的PCB从一个状态队列中脱离出来，加入到另一个队列。

四、线程管理

多进程编程下，进程之间如何通信，共享数据。进程的维护开销较大，创建时需分配资源，建立PCB；撤销时，回收资源，撤销PCB；进程切换时，保存当前进程的状态信息。

此时需要一个实体能够实现并发执行，共享相同的地址空间的功能。因此，线程就出现了。线程是进程的一条执行流程。所以可以理解为进程=资源管理+线程。

进程有进程的PCB，线程有线程的TCB（线程控制块）。

4.1 线程概述

线程的优点

1.一个进程中可以同时存在多个线程
2.各个线程之间可以并发地执行
3.各个线程之间可以共享地址空间和文件等资源

缺点
一个线程崩溃（可能破坏了共享资源），会导致所属进程的所有线程崩溃。

线程和进程的区别

1.进程是资源分配的单位，线程是CPU调度的单位。
2.进程拥有一个完整的资源平台，而线程只独享必不可少的资源，如寄存器和栈。
3.线程同样具有就绪，阻塞和执行三种基本状态，同样具有状态之间的转换。
4.线程能减少并发执行的时间和空间开销：

线程创建，终止时间比较短；
同一进程内的线程切换；
由于同一进程的各线程间共享内存和文件资源，可直接进行不通过内核的通信。

4.2 线程的实现

用户线程：在用户空间实现。
内核线程：在内核中实现。
轻量级进程：在内核中实现，支持用户线程。

用户线程

在用户空间实现的线程机制，它不依赖于操作系统的内核，由一组用户级的线程库函数来完成线程的管理，包括进程的创建，终止，同步和调度等。

用户线程的缺点

1.如果一个线程发起系统调用而阻塞，则整个进程在等待。
2.当一个线程开始运行后，除非它主动交出CPU的使用权，否则它所在的进程中的其他线程将无法运行。
3.由于时间片分配给进程，与其他进程比，在多线程执行时，每个线程得到的时间片较少，执行会较慢。

内核线程

在操作系统的内核当中实现的一种线程机制，由操作系统的内核来完成线程的创建、终止和管理。

由内核来维护PCB和TCB；线程的创建，终止和切换都是通过系统调用/内核函数的方式来进行的，由内核来完成，因此系统开销大。

在一个进程当中，如果某个内核线程发起系统调用而被阻塞，并不会影响其他内核线程的运行；时间片是以线程为单位分配的，多线程的进程获得更多的CPU时间；

轻量级进程

是内核支持的用户线程，一个进程可有一个或多个轻量级进程，每个轻量级进程由一个单独的内核线程来支持。

4.3 上下文切换

进程切换时，需要存储什么上下文？
寄存器（PC，SP等）CPU状态。进程切换的过程是将被切换的进程会将信息保存在PCB中，把另一个进程中的PCB信息恢复到CPU中。

五、进程控制

简单说一下和进程相关的一些系统调用。

5.1 创建进程

在系统中，出现了创建新进程的请求后，OS就调用进程创建原语Creat，经过下面的步骤：
1.申请空白PCB，获得唯一标识，从PCB集合中获取空白PCB。
2.为新进程分配所需资源。
3.初始化进程控制块
4.如果进程就绪队列能够接纳新进程，便将新进程插入就绪队列。

5.2 加载和执行进程

fork()函数的简单实现：
对子进程分配内存；
复制父进程的内存和CPU寄存器到子进程里。

缺点
在fork()之后，几乎都要调用exec()，导致fork()操作中内存复制是没有作用的，而且子进程将可能关闭打开的文件和连接，开销昂贵。

vfork()函数的简单实现：
1.一个创建进程的系统调用，不需要创建一个同样的内存映像，只复制和当前地址空间相关的元数据，页表等。
2.使用copy on write技术，只有当对某个地址写操作的时候才会触发异常，将触发异常的页分成两份，让父进程和子进程分别拥有不同的地址。

5.3 等待和终止进程

wait()函数

**wait()**系统调用是被父进程用来等待子进程的结束。

为什么要让父进程使用wait()来等待子进程结束？
因为子进程的结束只能释放用户空间所占用的内存，他的PCB是存放在内核中的，用户空间释放完，无法进行系统调用删除PCB。所以需要父进程帮助它在内核中删除。

exit()函数

进程结束执行后，它调用exit()，操作系统解锁父进程，并且将通过exit()传递得到的返回值为wait()调用的结果。

调用exit()后，会发生什么？
会将程序结果作为一个参数；关闭打开的文件，连接等；释放内存；释放大部分支持进程的操作系统结构；检查是否父进程是存活。

当子进程执行完exec()后还没返回给wait()回收PCB时，这一阶段，子进程处于僵尸态，也叫僵尸进程。

操作系统如何处理这些僵尸进程的？
如果父进程先于子进程死亡，将没有进程等待子进程释放。Init进程会定期扫描PCB列表，如果有进程处于僵尸态就会代替父进程进行wait()。

六、处理机/CPU调度

首先来看看为什么需要对进程进行调度呢？进程的上下文切换是需要开销的，当然希望越少触发越好，为什么不能让进程一个个运行，节约这个开销，换句话说，调度算法存在的意义是什么呢？

为了让系统的效率更高，满足一些特定的需求，比如实时性，优先级更高的任务。在调度的过程中，前面的进程可能由于某些原因，处于阻塞状态，如进行IO操作读取文件时CPU的利用率较低，此时不进行切换，会导致资源的浪费，效率不高。

6.1 进程调度的方式

对于用户态进程来说：
不可抢占式
调度进程必须等待事件结束。

可以抢占式
允许调度程序根据某种原则，暂停某个正在执行的进程，将已分配给该进程的处理机重新分配给另一进程。

6.2 衡量调度算法的指标

吞吐量
在单位时间内完成的进程数量（操作系统的计算带宽）。

周转时间
一个进程从初始化到结束，包括所有等待时间所花费的时间。

等待时间
进程在就绪队列中的总时间。

响应时间
从一个请求被提交到产生第一次响应所花费的总时间（操作系统的计算延迟）。

6.3 基本调度算法

FCFS（先来先服务）
SJF（短进程优先）
HRRN（最高响应时间比优先）
RR（轮询）
MFQ（多级反馈队列）
FSS（公平共享调度）

FCFS（First-Come First-Served，先来先服务）

思路
处理机按照任务到达的顺序来调度。如果进程在执行中阻塞，队列中的下一个会得到CPU。

优点
实现简单。

缺点
1.平均等待时间波动较大。受制于前面执行之间较长的进程。
2.花费时间少的任务可能排在花费时间长的任务后面。
3.可能导致IO和CPU之间的重叠处理：CPU密集型进程会导致IO设备闲置时，IO密集型进程也在等待。

SJF（Short Job First，短进程优先）

思路
将执行时间短的先执行。
注：这种算法可以是抢占也可以是不抢占的。当CPU执行时，发现新来的进程处理时间更短。如果是非抢占式则排到队列的第一个；如果是抢占式则将当前的进程转换为就绪态，自己接受CPU的执行。

优点
当短作业占有很大比例时，能使他们能比长作业更优先执行；
平均等待时间最小，平均周转时间最小。

缺点
1.可能导致饥饿：连续的段任务会让长任务饥饿；短任务可用时的任何长任务的CPU时间都会增加平均等待时间。
2.需要预知未来，估算作业的运行时间。
3.不能保证紧迫性作业能得到即时处理。

HRRN（Highest Response Ratio Next，最高响应时间比优先）

思路
关注进程等待了多长时间，防止无限期推迟。相当于总和考虑进程的执行时间和等待时间。不可抢占。
R=（w+s）/s
R：响应时间比
w：等待时间
s：执行时间
选择R值最高的进程。

RR（Round Robin，轮询）

思路
让每个进程在就绪队列中的等待时间与享受服务的时间成正比例。
1.系统根据FCFS策略将所有进程排成一个就绪队列，设置一定时间产生一次中断。
2.激活系统中的进程调度程序，完成一次调度。每次中断后都将CPU分配给队首进程。

时间片大小的设定

如果选很小，则有利于短作业，但会频繁地进行上下文切换，增加系统开销；如果很长，为使每个进程都能在一个时间片内完成，就退化为FCFS算法。
一般取略大于一次典型交互所需时间，使大多数交互式进程能在一个时间片内完成。

MFQ（Multileved Feedback Queue，多级反馈队列）

思路
设有n级优先级，一个进程可以在不同的队列中移动。

优先级变化条件
调度的时间片大小随优先级增加而减小；
如果任务在当前的时间片中没有完成，则降到下一个优先级。

过程
（1）设置多个就绪队列，为每个队列分配不同优先级，优先级越高，时间片越小。第一队列优先级最高，第二次之，以此类推。
（2）每个队列都采用FCFS算法。当新进程进入内存后，就放在队尾。当第一个时间片中没有完成，就放入第二队列的队尾，以此类推。最终放到第n队列后会用RR方式调度。
（3）按队列优先级调度程序。当第一队列为空时，才调度第二队列。

优点
CPU密集型任务的优先级下降很快；
达到IO密集型的进程优先级高。

FSS（Fair Share Scheduling，公平共享调度）

思路
保证每个进程都获得相同的处理机时间。一般用来控制用户对系统资源的访问。

优点
1.保证不重要的进程无法垄断资源。
2.未使用的资源按照每个组所分配的资源比例来分配。
3.没有达到资源使用率目标的进程获得更高的优先级。

6.4 实时调度算法

实时调度算法主要面向一些实时控制系统。
强实时系统HRT (Hard Real-time)
需要在保证的时间内完成重要的任务，必须完成。如果错过了最后期限，可能会引发灾难性的后果。

弱实时系统SRT(Soft Real-time)
要求重要的进程的优先级更高，尽量完成，并非必须。如果没被满足，就相应地降低要求。

在实时系统中，对于不同性质的实时任务，HRT和SRT。都会联系着一个截止时间。为保证任务的进程，实时调度必须能满足实时任务对截止时间的要求。

RM（Rate Monotonic，速率单调调度）

是最佳静态优先级调度（在调度之前就确定优先级），通过周期安排优先级，周期越短优先级越高，执行周期最短的任务。

EDF（Earliest Deadline First，最早期限调度）

根据任务的截止时间来确定优先级，deadline越早优先级越高，具有最佳的动态优先级调度（在任务的执行过程中，优先级会发生变化）。每次执行deadline最早的任务。

6.5 优先级反转

首先看一下这个图中反应的问题，优先级T1>T2>T3。T3先执行，当时间为t3时，T1开始执行，当到t4时，T1需要T3占用的共享资源，由于T3没有释放，就先进入阻塞状态。当时间为t5时，T2由于优先级高，开始执行导致T1的等待时间取决于T2的长度。

可以设置优先级天花板来解决这个等待问题。

设置优先级天花板
让资源的优先级和“所有可以锁定该资源的任务中优先级最高的那个任务”的优先级相同。

除非优先级高于系统中所有被锁定的资源的优先级上限，否则任务尝试执行临界区的时候会被阻塞。持有最高优先级的上限信号量锁的任务，会继承被该锁所阻塞的任务的优先级。

因此利用优先级继承，当T3占有共享资源并T1想访问时，可以将T3的优先级进行动态的提升与T1一致，此时T2进程就不会打断T3的执行。

七、同步&互斥

7.1 概念引入

发现问题
对于某些功能的实现上往往由于进程上下文切换而导致共享资源的操作不一致的问题。从而引发系统缺陷，让程序结果依赖于并发执行或事件的顺序/事件。

我们会发现，有时候，操作系统需要对临界区资源保护，采用互斥机制来实现同一时刻，只有一个或n个进程能对进行访问。还有时，操作系统还需要同步机制来保证一定的进程协作执行顺序。而同步和互斥又可以基于原子操作来实现。

在说同步和互斥的手段之前，先要了解几个概念~

原子操作-Atomic Operation
注：原子操作是指一次不存在任何中断或者失败的执行。

临界区
临界区是指进程中的一段需要访问共享资源并且当另一个进程处于响应代码区域时便不会被执行的代码区域。

同步
某些程序为了完成某任务而建立多个进程，这些进程为了完成一项任务而相互合作，在某些位置上协调他们的工作次序，传递信息。同步源于合作。

互斥
当一个进程处于临界区并访问共享资源时，没有其他进程会处于临界区并且访问任何相同的共享资源。

在实现上，应该考虑的一些原则：
空闲让进
当临界区空闲时，允许一个请求进入临界区的进程进入临界区。

忙则等待
当临界区正在被访问时，试图进入临界区的其他资源应该等待。保持对临界区的互斥访问。

有限等待
如果一个线程处于入口，那么在其请求被接受之前，其他线程进入临界区的事件是有限制的。

无忙等待
如果一个进程在等待进入临界区，那么在它可以进入之前会被挂起。

实现互斥的方法有基于硬件和基于软件的解决方案。

7.2 基于硬件的解决方案

7.2.1 禁用硬件中断

让硬件将中断处理延迟到中断启用后。在临界区内，没有中断，没有上下文切换，因此没有并发。

思路
进入临界区；禁用中断。离开临界区；开启中断。

缺点
一旦中断禁止，线程无法被停止；
无法限制响应中断所需的时间。

7.2.2 利用Test-and-Set

这是一条硬件指令-测试并建立。

思路
进入临界区之前，首先用TS指令测试lock，如果为false，则表示空闲，将lock赋为true，关闭临界资源；如果TestAndSet返回true，则一直循环测试，直到返回false，跳出循环，进入临界区。

boolean TestAndSet(boolean *lock){
   boolean old=*lock;
   *lock=TRUE;
   return old;
}

注：整个方法可以看成一条硬件指令，原子操作。
基于这个指令，我们可以实现获取资源和释放资源的操作。

获取资源
在进入临界区之前，先获取资源。
acquire()
{
while(TestAndSet(*lock))；
}
进入临界区后，对临界区进行操作…

解释
当lock为false，说明临界区空闲，则跳出while循环，进入临界区。
当lock为true，说明临界区有正在被使用，则继续在循环内（忙等），直到临界区空闲，才会跳出。

释放资源
退出临界区之前，应先释放资源。
release()
{
*lock=FALSE；
}
*lock=FALSE表示临界区空闲，其他进程可以抢占临界区。

思考
有一个问题，进程在忙等时是会占用CPU的，如何设计一个方案让资源得到合理的应用？可以用一个等待队列，当获取不到时，可以将其PCB放到等待队列中，让出CPU；当有进程release后，唤醒等待队列中的PCB。当上下文开销大于临界区操作时间时，选择忙等实现；反之，采用等待队列的方式实现。

7.2.3 交换

同样，也可以看成一条硬件指令~

void Exchange(boolean *a,boolean *b){
   boolean temp=*a;
   *a=*b;
   *b=temp;
}

思路
1.设置全局变量，int lock=0；
2.每个进程设置局部变量int key=1；
3.每次对于临界区的操作将执行如下代码：

int key;
do{
    key=1;
    while(key==1) Exchange(lock,key);
    //进入临界区
    lock=0;
    //退出临界区
}

解释
初始化后，lock=0，key=1，临界区空闲；循环执行Exchange，当lock==0，key==1时，获得资源，进入临界区；出去后将lock置为0。
当lock=1，key=1时，说明临界区被占用，将永远不可能退出循环，直到获取锁标记。

优点
1.简单。
2.适用于单处理器或共享主存的多处理器中。
3.可以用于支持多临界区。

缺点
忙等消耗CPU开销；
当进程离开临界区并且多个进程在等待的时候可能导致饥饿。

7.3 基于软件的解决方案

算法是挺多的，这里就简单的介绍两个。

7.3.1 Dekker算法

是第一个针对双线程例子的正确解决方案，基于两个进程的情况下。

思路
首先定义了
int turn：指示该谁进入临界区。
boolean flag[]：指示进程是否准备好进入临界区。

进入临界区

flag[i]=TRUE;
//表示其他进程
turn=j;
while(flag[j]&&turn==j);

解释
前提条件是只有i，j两个进程。刚开始，flag[i]=TRUE表示i想占用临界区，而turn=j表示临界区正在被j占用。只有当j不想占用临界区并且已经退出时，i才能占用。

退出临界区

flag[i]=FALSE;
do{
   flag[i]=TRUE;
   turn=j;
    while(flag[j]&&turn==j);
      //在临界区中操作...
      flag[i]=FALSE;
     //退出临界区
}while(TRUE)

解释
退出时只需要flag[i]=FALSE即可。没有占用的意愿后，进程j就能直接进入了。

7.3.2 Bakery算法

是对于N个进程的临界区的解决方案。

思路
1.进入临界区之前，进程接收一个数字。
2.得到的数字最小的进入临界区。
3.如果两个进程收到相同的数字，则比较进程的pid小的先进入临界区。
4.编号方案是按照美剧的增加顺序生成数字。

缺点
1.复杂，需要两个进程间的共享数据项。
2.需要忙等，浪费CPU。
3.没有硬件的保证下，无真正的软件解决方案（需要LOAD和STORE支持）。

八、信号量与管程

对于临界区的控制，我们可以采用一些互斥手段来保证同时只有1个进程在操作共享资源，但有时候，需要限制进入临界区的进程个数。此时就要同步的手段去保证，实现同步的方法有信号量机制和管程。

8.1 信号量机制

首先要清楚，信号量机制可以实现互斥和条件同步（一个线程等待另一个线程的事件发生）。信号量分为整型，记录型和AND型信号量。下面主要用记录型信号量进行实现。

实现原理（伪代码）
定义一个整型（sem）和两个原子操作。如果要实现同步，则要加入一个等待队列（仅用于互斥就不用啦）。下面讲实现同步的思路：

class Semaphore{
   int sem=n;
   WaitQueue q;
}

sem初始化为资源数。当有线程期望获取资源，则将sem–。
p()：获取资源。sem–；如果sem<0，则将当前线程放到等待队列中，阻塞当前线程。

p(){
  sem--;
  if(sem<0){
    add currentThread to q;
    block currentThread;
  }
}

v()：释放资源。sem++；如果sem<=0，则从等待队列中取出并唤醒线程。

v(){
  sem++;
  if(sem<=0){
    remove a thread from q;
    wakeup a thread;
  }
}

注：PV操作都必须是原子操作。

用信号量解决有界缓冲区的生产者-消费者问题

前提
1.在任何时刻只有一个线程操作缓冲区（互斥）
2.当缓冲区为空，消费者必须等待生产者（同步）
3.缓冲区满，生产者必须等待消费者（同步）

使用三个信号量：

二进制信号量mutex互斥
一般信号量fullBuffers
一般信号量emptyBuffers

伪代码实现：

class Buffer{
  Semaphore mutex=new Semaphore(1);
  //表示刚开始，buffer是空的
  Semaphore fullBuffers=new Semaphore(0);
  //表示buffer的空间为n
  Semaphore emptyBuffers=new Semaphore(n);
}

生产者

//保证缓冲区不要溢出
emptyBuffers.p();
mutex.p();
add to buffer;
mutex.v();
//唤醒阻塞的消费者
fullBuffers.v();

解释
对于缓冲区的操作，必须是用互斥信号量，保证同一时刻只有一个线程进入临界区。生产者刚开始需要判断，如果不满足emptyBuffers的状态就会被阻塞。当往缓冲区中放入数据后，需要唤醒等待在fullBuffer状态的消费者线程。

消费者

//保证缓冲区有数据才能取
fullBuffers.p();
mutex.p();
remove from buffer;
mutex.v();
//唤醒阻塞的生产者
emptyBuffers.v();

解释
消费者需要先判断，缓冲区是否有数据，如果没有则不满足fullBuffers状态而被挂起。当消费数据后就可以唤醒阻塞在emptyBuffers的生产者了。

信号量机制的缺点
1.读/开发代码比较困难。
2.容易出错，使用的信号量被另一个线程占用，忘记释放。
3.不能处理死锁问题。

8.2 管程

在信号量机制下，每个要访问临界资源的进程都必须调用PV操作。使大量的同步操作分散在各个进程中，不便于同一的管理，也容易产生死锁。管程的出现就是为了分离互斥和条件同步的关注。

定义
先简单介绍其定义，代表共享资源的数据结构以及由对该共享数据结构实施操作的一组过程所组成的资源管理程序共同构成了一个操作系统的资源管理模块。简单来说就是管程=共享资源数据结构+对数据结构的操作。
利用少量的共享数据结构抽象的表示系统中共享资源，并且讲对该共享数据结构的特定操作定义为一组过程。对于共享资源的访问必须通过这组过程，每次只有一个进程进入管程。

管程的组成

在管程的设计中包含：
1个锁：指定临界区。来保证同一时刻只有一个线程访问管程。
0或多个条件变量：等待/通知信号量用于管理并发访问共享数据。

注：Java中的ReentrantLock就是基于管程的思想实现的。具体实现可以看我以前些的文章。

实现思路
进入管程需要获得lock，要维护lock的等待队列。如果某个资源得不到满足就会挂到某个条件变量中进行wait并释放锁。当某个条件满足时，会调用某个条件变量的signal，唤醒等待在该条件变量上的线程。

实现原理（伪代码）

class Condition{
   int numWaiting=0;
   WaitingQueue q;
}

numWaiting是等待在该Condition上的线程数量。q是等待队列，可以由链表实现。
wait(lock)：将等待线程数+1并添加到等待队列中，此时释放锁，阻塞当前线程，获取锁。为什么要释放锁再获取锁，后序再解释。

wait(lock){
  numWaiting++;
  add this thread to q;
  release(lock);
  block current thread;
  require(lock);
}

signal()：当等待线程数>0时，才会唤醒对应的线程。这里可以先解释wait()中为什么要require(lock)。当某个wait的线程被唤醒后，需要先获得锁，才能进入管程。

signal(){
  if(numWaiting>0){
    remove a thread t from q;
    wakeup(t);
    numWaiting--;
  }
}

注：wait和signal必须是原子操作。

用管程解决有界缓冲区的生产者-消费者问题

class Buffer{
  Lock lock;
  int count=0;
  Condition notFull,notEmpty;
}

lock是进入管程前需要获取的对象，count表示多少线程在缓冲区中。

生产者

lock.acquire();
while(count==n) notFull.wait(&lock);
add c to the buffer;
count++;
notEmpty.signal();
lock.release();

解释
操作管程前，要先获取锁。然后保证缓冲区不为满，满了则阻塞。将数据放入缓冲区后，需要唤醒消费者来取，最终释放资源。

消费者

lock.acquire();
while(count==0) notEmpty.wait(&lock);
remove c from buffer;
coutn--;
notFull.signal();
lock.release();

解释
获得锁进入管程，当缓冲区没有数据时，等待生产者添加。成功取出后，唤醒阻塞生产者来放数据，然后释放资源。

思考
生产者的实现与信号量的解决方案相比，为什么获取释放锁要放在头和尾？
因为要保证在管程内只有一个线程，才能正常调用管程的一些操作。

为什么wait里要有release(lock)的操作？
在生产者中调用wait，如果不释放，会导致所有想要进入管程的线程都在等待。

九、进程间通信的方式

可以分为直接通信和间接通信。

直接通信

进程必须正确的命名对方，必须有明确的发送方，message，接收方。

通信链路的属性
1.自动建立链路
2.一条链路恰好对应一对通信进程
3.每对进程之间只有一个链接存在
4.链接可以是单项的，但通常为双向

间接通信

进程定向地从消息队列接收消息，每个消息都有一个唯一的ID，只有他们共享了一个消息队列，进程才能通信。

通信链路的属性
1.只有进程共享一个共同的消息队列，才建立链路
2.链路可以与许多进程相关联
3.每对进程可以共享多个通信链路
4.连接可以是单向或双向的

具体的通信方式有信号，管道，消息队列，共享内存。下面简单介绍一下四种通信方式。

9.1 信号

是软件通过系统调用，以软件中断通知事件处理。

应用程序对信号的处理方式

catch：指定信号处理函数被调用
ignore：依靠操作系统的默认处理
mask：闭塞信号因此不会传送

缺点
只能传递信号，不能传输要交换的任何数据。

优点
效率高。

实现原理

图片来源于网络

1）应用程序注册处理信号的handles，进行系统调用，由用户态切换到内核态。
2）内核处理信号，返回时通过改变栈指针，将返回点从系统调用的后一条语句改成信号处理函数的入口并分发给handler。
3）处理完毕再将栈指针指向调用系统调用的后一条语句。

9.2 管道

管道用于数据交换，是用于连接一个读进程和写进程以实现他们呢之间通信的一个共享文件。
进程不知道是从键盘，文件还是程序读写到终端，文件程序。

指令ls|more的shell实现方式：
shell创建两个子进程，ls和more。子进程共享父进程的文件描述符，ls输出到管道上，more从管道中取数据；当ls发现管道中已经满了或more发现管道中没有数据的就会阻塞。

9.3 消息队列

也是一种数据传输机制，以格式化的message（作为一个字节序列存储）为单位，将通信数据封装在消息中，并利用操作系统提供的一组通信命令（原语），完成消息传递与交互，按照FIFO来管理消息。

注：消息队列有直接通信方式和间接通信方式，上述为直接通信方式。而间接的是通过共享中间实体进行发送和接收。

9.4 共享内存

在每个进程的私有地址空间，中明确地设置了共享内存段。

优点
快速，方便地共享数据。

不足
必须依赖同步机制，同步数据访问。

来自知乎操作系统（三）—进程管理 - 知乎 (zhihu.com)