一、进程

1、进程的概念

程序：是静态的，就是个存放在磁盘里的可执行文件

进程：是动态的，是程序的一次执行过程

同一个程序多次执行会对应多个进程

2、进程的组成

1）进程控制块PCB

操作系统需要对各个并发运行的进程进行管理，但凡管理时所需要的信息，都会被放在PCB中。

PCB是进程存在的唯一标志，当进程被创建时，操作系统为其创建PCB，当进程结束时，会回收其PCB。

2）程序段、数据段

PCB 是给操作系统用的。

程序段、数据段是给进程自己用的。

一个进程实体（进程映像）由PCB、程序段、数据段组成。

进程是动态的，进程实体（进程映像）是静态的。进程实体反应了进程在某一时刻的状态，类似快照。

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

3、进程的特征

动态性是进程最基本的特征。

异步性会导致并发程序执行结果的不确定性

4、进程的状态

运行态：占有CPU，并在CPU上运行

就绪态：已经具备运行条件，但由于没有空闲CPU，而暂时不能运行

阻塞态（等待态）：因等待某一事件而暂时不能运行

创建态（新建态）：进程正在被创建，操作系统为新进程分配资源、创建PCB

终止态（结束态）：进程正在从系统中撤销，操作系统回收进程的资源、撤销PCB

5、进程状态的转换

6、进程的组织

1）进程的组织概述

进程PCB中，会有一个变量 state 来表示进程的当前状态。（如：1表示创建态、2表示就绪态、3表示运行态…）

为了对同一个状态下的各个进程进行统一的管理，操作系统会将各个进程的PCB组织起来。

2）进程的组织的方式

1. 链接方式

**执行指针：**指向当前处于运行态（执行态）的进程。单CPU计算机中，同一时刻只会有一个进程处于运行态。多核CPU可有多个进程同时处于运行态

**就绪队列指针：**指向当前处于就绪态的进程

**阻塞队列指针：**指向当前处于阻塞态的进程（很多操作系统还会根据阻塞原因不同，再分为多个阻塞队列）

2. 索引方式

7、进程控制

1）进程控制的方式

2）进程控制相关原语

1. 进程的创建

2. 进程的终止

3. 进程的阻塞和唤醒

4. 进程的切换

8、进程通信IPC

进程间通信：是指两个进程之间产生数据交互。

进程是分配系统资源的单位（包括内存地址空间），因此各进程拥有的内存地址空间相互独立。

为了保证安全，一个进程不能直接访问另一个进程的地址空间。

1）共享存储

1. 基于数据结构的共享

**基于数据结构的共享：**这种共享方式速度慢、限制多，是一种低级通信方式。比如共享空间里只能放一个长度为3的数组。

2. 基于存储区的共享

**基于存储区的共享：**操作系统在内存中划出一块共享存储区，数据的形式、存放位置都由通信进程控制，而不是操作系统。这种共享方式速度很快，是一种高级通信方式。

为避免出错，各个进程对共享空间的访问应该是互斥的。

各个进程可使用操作系统内核提供的同步互斥工具

2）消息传递

1. 直接通讯方式

进程间的数据交换以格式化的消（Message）为单位。进程通过操作系统提供的“发送消息/接收消息”两个原语进行数据交换。

消息发送进程要指明接收进程的ID

2. 间接通讯方式

间接通信方式：以“信箱”作为中间实体进行消息传递。

可以多个进程往同一个信箱send消息，也可以多个进程从同一个信箱中receive消息

3）管道通信

“管道”是一个特殊的共享文 件，又名pipe文件。其实就是在内存中开辟一个大小固定的内存缓冲区

管道只能采用半双工通信，某一时间段内只能实现单向的传输。如果要实现双向同时通信，则需要设置两个管道。

各进程要互斥地访问管道（由操作系统实现）

当管道写满时，写进程将阻塞，直到读进程将管道中的数据取走，即可唤醒写进程。

当管道读空时，读进程将阻塞，直到写进程往管道中写入数据，即可唤醒读进程。

管道中的数据一旦被读出，就彻底消失。因此，当多个进程读同一个管道时，可能会错乱。对此，通常有两种解决方案：

①一个管道允许多个写进程，一个读进程（2014年408真题高教社官方答案）

②允许有多个写进程，多个读进程，但系统会让各个读进程轮流从管道中读数据（Linux 的方案）

二、线程

1、线程的概述

资源分配、调度

传统进程机制中，进程是资源分配、调度的基本单位

引入线程后，进程是资源分配的基本单位，线程是调度的基本单位

线程是一个基本的CPU执行单元，也是程序执行流的最小单位

线程则作为处理机的分配单元。

并发性

传统进程机制中，只能进程间并发

引入线程后，各线程间也能并发，提升了并发度

系统开销

传统的进程间并发，需要切换进程的运行环境，系统开销很大

线程间并发，如果是同一进程内的线程切换，则不需要切换进程环境，系统开销小

引入线程后，并发所带来的系统开销减小

2、线程的属性

线程是处理机调度的单位

多CPU计算机中，各个线程可占用不同的CPU

每个线程都有一个线程ID、线程控制块 (TCB)

线程也有就绪、阻塞、运行三种基本状态

线程几乎不拥有系统资源，同一进程的不同线程间共享进程的资源

由于共享内存地址空间，同一进程中的线程间通信甚至无需系统干预

同一进程中的线程切换，不会引起进程切换。不同进程中的线程切换，会引起进程切换

切换同进程内的线程，系统开销很小。切换进程，系统开销较大

3、线程的实现方式

1）用户级线程

早期的操作系统（如：早期Unix）只支持进程，不支持线程。

当时的“线程”是由线程库实现的，很多编程语言提供了强大的线程库，可以实现线程的创建、销毁、调度等功能。

用户级线程由应用程序通过线程库实现，所有的线程管理工作都由应用程序负责（包括线程切换）

用户级线程中，线程切换可以在用户态下即可完成，无需操作系统干预。

在用户看来，是有多个线程。但是在操作系统内核看来，并意识不到线程的存在。“用户级线程”就是“从用户视角看能看到的线程”

**优点：**用户级线程的切换在用户空间即可完成，不需要切换到核心态，线程管理的系统开销小，效率高

**缺点：**当一个用户级线程被阻塞后，整个进程都会被阻塞，并发度不高。多个线程不可在多核处理机上并行运行。

2）内核级线程

内核级线程（又称内核支持的线程）

内核级线程的管理工作由操作系统内核完成。

线程调度、切换等工作都由内核负责，因此内核级线程的切换必然需要在核心态下才能完成。

操作系统会为每个内核级线程建立相应的TCB（Thread Control Block，线程控制块），通过TCB对线程进行管理。“内核级线程”就 是“从操作系统内核视角看能看到的线程”

**优点：**当一个线程被阻塞后，别的线程还可以继续执行，并发能力强。多线程可在多核处理机上并行执行。

**缺点：**一个用户进程会占用多个内核级线程，线程切换由操作系统内核完成，需要切换到核心态，因此线程管理的成本高，开销大。

3、多线程模型

在支持内核级线程的系统中，根据用户级线程和内核级线程的映射关系，可以划分为几种多线程模型

1）一对一模型

**一对一模型：**一个用户级线程映射到一个内核级线程。每个用户进程有与用户级线程同数量的内核级线程。

**优点：**当一个线程被阻塞后，别的线程还可以继续执行，并发能力强。多线程可在多核处理机上并行执行。

**缺点：**一个用户进程会占用多个内核级线程，线程切换由操作系统内核完成，需要切换到核心态，因此线程管理的成本高，开销大。

2）多对一模型

多对一模型：多个用户级线程映射到一个内核级线程。且一个进程只被分配一个内核级线程。

优点：用户级线程的切换在用户空间即可完成，不需要切换到核心态，线程管理的系统开销小，效率高

缺点：当一个用户级线程被阻塞后，整个进程都会被阻塞，并发度不高。多个线程不可在多核处理机上并行运行

操作系统只“看得见”内核级线程，因此只有内核级线程才是处理机分配的单位。

3）多对多模型

多对多模型：n 用户及线程映射到 m 个内核级线程（n >= m）。每个用户进程对应 m 个内核级线程。

克服了多对一模型并发度不高的缺点（一个阻塞全体阻塞），又克服了一对一模型中一个用户进程占用太多内核级线程，开销太大的缺点。

用户级线程是“代码逻辑”的载体、内核级线程是“运行机会”的载体（内核级线程才是处理机分配的单位）

一段“代码逻辑”只有获得了“运行机会”才能被CPU执行

内核级线程中可以运行任意一个有映射关系的用户级线程代码，只有两个内核级线程中正在运行的代码逻辑都阻塞时，这个进程才会阻塞

三、调度

1、三层调度

1）高级调度（作业调度）

高级调度（作业调度）：按一定的原则从外存的作业后备队列中挑选一个作业调入内存，并创建进程。**每个作业只调入一次，调出一次。**作业调入时会建立PCB，调出时才撤销PCB。

作业：一个具体的任务

用户向系统提交一个作业：用户让操作系统启动一个程序（来处理一个具体的任务）

2）低级调度（进程调度）

低级调度（进程调度/处理机调度）：按照某种策略从就绪队列中选取一个进程，将处理机分配给它。

进程调度是操作系统中最基本的一种调度，在一般的操作系统中都必须配置进程调度。进程调度的频率很高，一般几十毫秒一次。

3）中级调度（内存调度）

暂时调到外存等待的进程状态为挂起状态。被挂起的进程PCB会被组织成挂起队列

中级调度（内存调度）：按照某种策略决定将哪个处于挂起状态的进程重新调入内存。一个进程可能会被多次调出、调入内存，因此中级调度发生的频率要比高级调度更高。

4）三层调度总结

2、七状态模型

暂时调到外存等待的进程状态为挂起状态（挂起态）

挂起态又可以进一步细分为就绪挂起、阻塞挂起两种状态

3、进程调度的时机

1）需要调度的时机

当前运行的进程主动放弃处理机

进程正常终止

运行过程中发生异常而终止

进程主动请求阻塞（如 等待I/O）

当前运行的进程被动放弃处理机

分给进程的时间片用完

有更紧急的事需要处理（如 I/O中断）

有更高优先级的进程进入就绪队列

2）不能调度的时机

在处理中断的过程中。中断处理过程复杂，与硬件密切相关，很难做到在中断处理过程中进行进程切换。

进程在操作系统内核程序临界区中。（内核程序临界区一般是用来访问某种内核数据结构的，比如进程的就绪队列）（但是进程在普通临界区中是可以进行调度、切换的）

在原子操作过程中（原语）。原子操作不可中断，要一气呵成（如修改PCB中进程状态标志，并把PCB放到相应队列）

4、进程调度切换与过程

狭义的进程调度与进程切换

狭义的进程调度指的是从就绪队列中选中一个要运行的进程。（这个进程可以是刚刚被暂停执行的进程，也可能是另一个进程，后一种情况就需要进程切换）

进程切换是指一个进程让出处理机，由另一个进程占用处理机的过程。（对原来运行进程各种数据的保存、对新的进程各种数据的恢复）

广义的进程调度

广义的进程调度包含了选择一个进程和进程切换两个步骤。

进程切换是有代价的

如果过于频繁的进行进程调度、切换，必然会使整个系统的效率降低，使系统大部分时间都花在了进程切换上，而真正用于执行进程的时间减少

5、进度调度的方式

非剥夺调度方式，又称非抢占方式：只能由当前运行的进程主动放弃CPU

剥夺调度方式，又称抢占方式：可由操作系统剥夺当前进程的CPU使用权

6、调度算法的评价指标

1）CPU利用率

利用率 = 忙碌的时间 / 总时间

2）系统吞吐量

系统吞吐量 = 总共完成了多少道作业 / 总共花了多少时间

3）周转时间

周转时间，是指从作业被提交给系统开始，到作业完成为止的这段时间间隔。

4）等待时间

等待时间：进程/作业处于等待处理机状态时间之和

5）响应时间

响应时间：用户提交请求到首次产生响应所用的时间。

7、调度算法

1）先来先服务（FCFS）

思想：公平

规则：先来后到顺序

用于作业调度时，考虑的是作业；用于进程调度时，考虑的是进程。

非抢占式的算法

优点：公平、算法实现简单

缺点：排在长作业（进程）后面的短作业需要等待很长时间，带权周转时间很大，对短作业来说用户体验不好。FCFS算法对长作业有利，对短作业不利

不会导致饥饿（饥饿：某进程/作业长期得不到服务）

2）最短作业优先（SJF）

思想：追求最少的平均等待时间，最少的平均周转时间、最少的平均平均带权周转时间

算法规则：服务时间最短的先服务

最短剩余时间优先算法：就绪队列改变时、一个进程完成时就需要重新调度，运行剩余时间最短的进程

可用于作业调度，也可用于进程调度。（用于进程调度时称为“短进程优先算法SPF”）

SJF和SPF是非抢占式的算法。但是也有抢占式的版本（最短剩余时间优先算法SRTN）

优点：“最短的”平均等待时间、平均周转时间

缺点：

不公平。对短作业有利，对长作业不利，产生饥饿现象

运行时间是由用户提供的，并不一定真实，不一定能做到真正的短作业优先

对于最短作业优先算法的补充：

如果题目中未特别说明，所提到的“短作业/进程优先算法”默认是非抢占式的

抢占式的短作业/进程优先调度算法（最短剩余时间优先SRNT算法）的平均等待时间、平均周转时间最少

虽然严格来说，SJF的平均等待时间、平均周转时间并不一定最少，但相比于其他算法（如 FCFS），SJF依然可以获得较少的平均等待时间、平均周转时间

如果选择题中遇到“SJF 算法的平均等待时间、平均周转时间最少”的选项，那最好判断其他选项是不是有很明显的错误，如果没有更合适的选项，那也应该选择该选项

3）最高响应比优先（HRRN）

思想：综合考虑等待时间和要求服务的时间

规则：每次调度前计算响应比，服务响应比最高的作业

响应比 = (等待时间 + 要求服务时间) / 要求服务时间

高响应比优先算法：只有当前运行的进程主动放弃CPU时进行调度，计算所有就绪进程的响应比，处理响应比最高的进程。

既可用于作业调度，也可用于进程调度

非抢占式的调度算法

特点：

综合考虑了等待时间和运行时间（要求服务时间），等待时间相同时，要求服务时间短的优先（SJF 的优点），要求服务时间相同时，等待时间长的优先（FCFS 的优点）

对于长作业来说，随着等待时间越来越久，其响应比也会越来越大，从而避免了长作业饥饿的问题

4）时间片轮转（RR）

思想：公平地、轮流地为各个进程服务

规则：按照各进程到达就绪队列的顺序，轮流让各个进程执行一个时间片。

用于进程调度（只有作业放入内存建立了相应的进程后，才能被分配处理机时间片）

若进程未能在时间片内运行完，将被强行剥夺处理机使用权，因此时间片轮转调度算法属于抢占式的算法。由时钟装置发出时钟中断来通知CPU中指服务

优点：公平、响应快、适用于分时操作系统、不会导致饥饿

缺点：由于高频率的进程切换，因此有一定开销、不能区分任务的紧急程度

5）优先级调度

思想：根据任紧急程度决定顺序

规则：调度时选择优先级最高的作业/进程

非抢占式的优先级调度算法：每次调度时选择当前已到达且优先级最高的进程。当前进程主动放弃处理机时发生调度。

抢占式的优先级调度算法：每次调度时选择当前已到达且优先级最高的进程。当前进程主动放弃处理机时发生调度。另外，当就绪队列发生改变时也需要检查是会发生抢占。

非抢占式只需在进程主动放弃处理机时进行调度即可，而抢占式还需在就绪队列变化时，检查是否会发生抢占

既可用于作业调度，也可用于进程调度。（甚至，还会用于在之后会学习的I/O调度中）

优点：用优先级区分紧急程度、重要程度，适用于实时操作系统。可灵活地调整对各种作业/进程的偏好程度。

缺点：若源源不断地有高优先级进程到来，则可能导致饥饿

6）多级反馈队列

思想：折中权衡

用于进程调度

规则：

设置多级就绪队列，各级队列优先级从高到低，时间片从小到大

新进程到达时先进入第1级队列，按FCFS原则排队等待被分配时间片，若用完时间片进程还未结束，则进程进入下一级队列队尾。如果此时已经是在最下级的队列，则重新放回该队列队尾

只有第 k 级队列为空时，才会为 k+1 级队头的进程分配时间片

抢占式的算法。在 k 级队列的进程运行过程中，若更上级的队列（1~k-1级）中进入了一个新进程，则由于新进程处于优先级更高的队列中，因此新进程会抢占处理机，原来运行的进程放回 k 级队列队尾

特点：

对各类型进程相对公平（FCFS的优点）

每个新到达的进程都可以很快就得到响应（RR的优点）

短进程只用较少的时间就可完成（SPF的优点）

不必实现估计进程的运行时间（避免用户作假）

可灵活地调整对各类进程的偏好程度，比如CPU密集型进程、I/O密集型进程（拓展：可以将因I/O而阻塞的进程重新放回原队列，这样I/O型进程就可以保持较高优先级）

会导致饥饿

四、进程同步和互斥

1、进程同步概述

并发性带来了异步性，有时需要通过进程同步解决这种异步问题。

有的进程之间需要相互配合地完成工作，各进程的工作推进需要遵循一定的先后顺序。

2、进程互斥概述

1）临界资源

把一个时间段内只允许一个进程使用的资源称为临界资源

对临界资源的访问，必须互斥地进行

2）进程互斥四个部分

进入区：检查是否可进入临界区，若可进入，需要“上锁"

临界区：访问临界资源的那段代码

退出区：负贵"解锁"

剩余区：做其他处理

3）互斥操作的原则

空闲让进：临界区空闲时，应允许一个进程访问

忙则等待：临界区正在被访问时，其他试图访问的进程需要等待

有限等待：要在有限时间内进入临界区，保证不会饥饿

让权等待：进不了临界区的进程，要释放处理机，防止忙等

3、进程互斥的软件实现

1）单标志法

turn 变量背后的逻辑：表达“谦让”

单标志法存在的主要问题是：违背“空闲让进”原则（对方不谦让，我就不能用）。

2）双标志先检查法

flag[]数组中各个元素用来标记各进程想进入临界区的意愿

双标志先检查法的主要问题是：违反“忙则等待”原则。

进入区的“检查”和“上锁” 两个处理不是一气呵成的。“检查”后，“上锁”前可能发生进程切换

3）双标志后检查法

双标志后检查法虽然解决了“忙则等待”的问题，但是又违背了“空闲让进”和“有限等待”原则，会因各进程都长期无法访问临界资源而产生“饥饿”现象。

两个进程都争着想进入临界区，但是谁也不让谁，最后谁都无法进入临界区。

4）Peterson算法

结合双标志法、单标志法的思想。如果双方都争着想进入临界区，那可以让进程尝试“孔融让梨”（谦让）。做一个有礼貌的进程。

Peterson 算法用软件方法解决了进程互斥问题，遵循了空闲让进、忙则等待、有限等待三个原则，但是依然未遵循让权等待的原则。

4、进程互斥的硬件实现

1）中断屏蔽方式

利用“开/关中断指令”实现，在某进程开始访问临界区到结束访问为止都不允许被中断，就不能发生进程切换

···

关中断; // 关中断后即不允许当前进程被中断，也必然不会发生进程切换

临界区;

开中断; // 直到当前进程访问完临界区，再执行开中断指令，才有可能有别的进程上处理机并访问临界区

···

优点：简单、高效

缺点：不适用于多处理机；只适用于操作系统内核进程，不适用于用户进程（因为开/关中断指令只能运行在内核态，这组指令如果能让用户随意使用会很危险）

2）TestAndSet（TS/TSL指令）

TSL 指令是用硬件实现的，执行的过程不允许被中断，只能一气呵成。

//布尔型共享变量 lock 表示当前临界区是否被加锁

//true 表示已加锁，false 表示未加锁

bool TestAndset (bool *lock){

bool old;

old = *lock; //old用来存放lock原来的值

*lock = true; //无论之前是否已加锁，都将lock设为true

return old; //返回lock原来的值

}

//以下是使用 TSL 指令实现互斥的算法逻辑

while (TestAndset (&lock)); //"上锁"并"检查"

临界区代码段...

lock = false; //解锁

剩余区代码段...

优点：实现简单、适用于多处理机环境

缺点：不满足“让权等待”原则，暂时无法进入临界区的进程会占用CPU并循环执行TSL指令，从而导致“忙等”。

3）Swap指令（XCHG指令）

Swap 指令是用硬件实现的，执行的过程不允许被中断，只能一气呵成。

//Swap 指令的作用是交换两个变量的值

void Swap (bool *a, bool *b) {

bool temp;

temp = *a;

*a = *b;

*b = temp;

}

//以下是用 Swap 指令实现互斥的算法逻辑

//lock 表示当前临界区是否被加锁

bool old = true;

while (old == true)

Swap (&lock, &old);

临界区代码段...

lock = false;

剩余区代码段...

与TSL 指令类似

5、信号量机制

1）信号量机制概述

信号量：一个变可以用来表示系统中某种资源的数量的变量

原语是一种特殊的程序段，其执行只能一气呵成，不可被中断。原语是由关中断/开中断指令实现的。

一对原语：wait(S) 原语和 signal(S) 原语。简称为 P、V操作

2）信号量分类

1. 整型信号量

用一个整数型的变量作为信号量，用来表示系统中某种资源的数量

存在的问题：不满足“让权等待”原则，会发生“忙等”

int S = 1; //初始化整型信号量s，表示当前系统中可用的资源数

void wait (int S) { //wait 原语，相当于进入区

while (S <= 0); //如果资源数不够，就一直循环等待

S--; //如果资源数够，则占用一个资源

}

void signal (int S) { //signal 原语，相当于退出区

S++; //使用完资源后，在退出区释放资源

}

2. 记录型信号量

记录型信号量：用记录型数据结构表示的信号量

该机制遵循了“让权等待”原则

typedef struct {

int value;

struct process *L; // 等待队列

} semaphore;

void wait (semaphore S) {

S.value--;

if (S.value < 0) {

block(S.L);

}

}

void signal (semaphore S) {

S.value++;

if (S.value <= 0) {

wakeup(S.L);

}

}

如果剩余资源数不够，使用block原语使进程从运行态进入阻塞态，并把挂到信号量 S 的阻塞队列中

释放资源后，若还有别的进程在等待这种资源，则使用wakeup 原语唤醒等待队列中的一个进程，该进程从阻塞态变为就绪态

3）信号量实现互斥

一个信号量对应一种资源

信号量的值 = 这种资源的剩余数量（信号量的值如果小于0，说明此时有进程在等待这种资源）

P(S) ：申请一个资源S，如果资源不够就阻塞等待

V(S) ： 释放一个资源S，如果有进程在等待该资源，则唤醒一个进程

对不同的临界资源需要设置不同的互斥信号量。

P、V操作必须成对出现

semaphore mutex = 1;

f() {

P(mutex);

临界区代码...;

V(mutex);

}

4）信号量实现同步

前V后P

信号量S代表“某种资源”，刚开始是没有这种资源的。P2需要使用这种资源，而又只能由P1产生这种资源

4.5）互斥和同步的对比

5）信号量实现前驱关系

分析问题，画出前驱图，把每一对前驱关系都看成一个同步问题

为每一对前取关系设置同步信号量，初值为0

在每个"前操作"之后执行 V 操作

在每个"后操作"之前执行 P 操作

6、PV操作模型

1）生产者消费者问题

生产者、消费者共享一个初始为空、大小为n的缓冲区。

只有缓冲区没满时，生产者才能把产品放入缓冲区，否则必须等待。

只有缓冲区不空时，消费者才能从中取出产品，否则必须等待。

缓冲区是临界资源，各进程必须互斥地访问。

实现互斥的P操作一定要在实现同步的P操作之后。

V操作不会导致进程阻塞，因此两个V操作顺序可以交换。

semaphore mutex = 1; //互斥信号量，实现对缓冲区的互斥访问

semaphore empty = n; //同步信号量，表示空闲缓冲区的数量

semaphore full = 0; //同步信号量，表示产品的数量，也即非空缓冲区的数量

producer (){

while(1){

生产一个产品;

P(empty);

P(mutex);

把产品放入缓冲区;

V(mutex);

V(full);

}

}

consumer (){

while(1){

P(full);

P(mutex);

从缓冲区取出一个产品;

V(mutex);

V(empty);

使用产品;

}

}

2）多生产者多消费者问题

互斥关系：对缓冲区（盘子）的访问要互斥地进行

同步关系（一前一后）：

父亲将苹果放入盘子后，女儿才能取苹果

母亲将橘子放入盘子后，儿子才能取橘子

只有盘子为空时，父亲或母亲才能放入水果

semaphore mutex = 1; //实现互斥访问盘子（缓冲区）

semaphore apple = 0; //盘子中有几个苹果

semaphore orange = 0; //盘子中有几个橘子

semaphore plate = 1; //盘子中还可以放多少个水果

dad (){

while(1){

准备一个苹果;

P(plate);

P(mutex);

把苹果放入盘子;

V(mutex);

V(apple);

}

}

mom (){

while(1){

准备一个橘子;

P(plate);

P(mutex);

把橘子放入盘子;

V(mutex);

V(orange);

}

}

daughter (){

while(1){

P(apple);

P(mutex);

从盘中取出苹果;

V(mutex);

V(plate);

吃掉苹果;

}

}

son (){

while(1){

P(orange);

P(mutex);

从盘中取出橘子;

V(mutex);

V(plate);

吃掉橘子;

}

}

发现：即使不设置专门的互斥变量mutex，也不会出现多个进程同时访问盘子的现象。

本题中的缓冲区大小为1。在任何时刻，apple、orange、plate 三个同步信号量中最多只有一个是1。

因此在任何时刻，最多只有一个进程的P操作不会被阻塞，并顺利地进入临界区。

3）吸烟者问题

生产多种产品的单生产者多消费者

PV操作顺序：“前V后P”

semaphore offer1 = 0; //桌上组合一的数量

semaphore offer2 = 0; //桌上组合二的数量

semaphore offer3 = 0; //桌上组合三的数量

semaphore finish = 0; //抽烟是否完成

int i = 0; //用于实现“三个抽烟者轮流抽烟”

provider (){

while(1){

if(i==0) {

将组合一放桌上;

V(offer1);

} else if(i==1) {

将组合二放桌上;

V(offer2);

} else if(i==2) {

将组合三放桌上;

V(offer3);

}

i = (i+1)%3;

P(finish);

}

}

smoker1 (){

while(1){

P(offer1);

从桌上拿走组合一；卷烟；抽掉；

V(finish);

}

}

4）读者写者问题

允许多个读者可以同时对文件执行读操作

只允许一个写者往文件中写信息

任一写者在完成写操作之前不允许其他读者或写者工作

写者执行写操作前，应让已有的读者和写者全部退出

互斥关系：写进程—写进程、写进程—读进程。读进程与读进程不存在互斥问题。

读写公平算法

semaphore rw=1; //用于实现对共享文件的互斥访问

int count = 0; //记录当前有几个读进程在访问文件

semaphore mutex = 1; //用于保证对count变量的互斥访问

semaphore w = 1; //用于实现“写优先（公平读写）”

writer (){

while(1){

P(w);

P(rw);

写文件…

V(rw);

V(w);

}

}

reader (){

while(1){

P(w);

P(mutex);

if(count==0)

P(rw);

count++;

V(mutex);

V(w);

读文件…

P(mutex);

count--;

if(count==0)

V(rw);

V(mutex);

}

}

5）哲学家进餐问题

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

如果每位哲学家循环等待右边的人放下筷子（阻塞），发生“死锁”

1、可以对哲学家进程施加一些限制条件，比如最多允许四个哲学家同时进餐。这样可以保证至少有一个哲学家是可以拿到左右两只筷子的

2、要求奇数号哲学家先拿左边的筷子，然后再拿右边的筷子，而偶数号哲学家刚好相反。用这种方法可以保证如果相邻的两个奇偶号哲学家都想吃饭，那么只会有其中一个可以拿起第一只筷子，另一个会直接阻塞。这就避免了占有一支后再等待另一只的情况

3、仅当一个哲学家左右两支筷子都可用时才允许他抓起筷子。

7、管程

组成：

共享数据结构

对数据结构初始化的语句

一组用来访问数据结构的过程（函数）

基本特征：

各外部进程/线程只能通过管程提供的特定”入口"才能访问共享数据

每次仅允汻一个进程在管程内执行某个内部过程

各进程必须互斥访问管程的特性是由编译器实现的

可在管程中设置条件变量及等待/唤醒操作以解决同步问题

每次只能有一个线程进入add函数，如果多个线程同时调用add函数，则后来者需要排队等待

static class Main {

private int cnt = 0;

public synchronized int add (int n) {

return cnt + n;

}

}

五、死锁

1、死锁概述

死锁：在并发环境下，各进程因竞争资源而造成的一种互相等待对方手里的资源，导致各进程都阻塞，都无法向前推进的现象。

饥饿：发生饥饿的进程既可能是阻塞态（如长期得不到需要的I/O设备），也可能是就绪态（长期得不到处理机）

2、死锁产生的必要条件

互斥条件：对必须互斥使用的资源的争抢才会导致死锁

不剥夺条件：进程保持的资源只能主动释放，不可强行剥夺

请求和保持条件：保持着某些资源不放的同时，请求别的资源

循环等待条件：存在一种进程资源的循环等待链。循环等待未必死锁，死锁一定有循环等待

3、预防死锁（静态策略）

1）破坏互斥条件

将临界盗源改造为可共享使用的资源

缺点：可行性不高，很多时候无法破坏互斥条件

2）破坏不剥夺条件

1、申请的资源得不到满足时，立即释放拥有的所有资源

2、申请的资源被其他进程占用时，由操作系统协助剥夺 （考虑优先级）

缺点：实现复杂、剩夺资源可能导致部分工作失效、反复申请和释放导致系统开销大、可能导致饥饿

3）破坏请求和保持条件

远行前分配好所有需要的资源，之后一直保持

缺点：资源利用率低、可能导致饥饿

4）破坏循环等待条件

给资源编号，必须按编号从小到大的顺序申请资源

缺点：不方便添加新设备、会导致资源浪费、用户编程困难

4、避免死锁（动态策略）

1）安全序列

安全序列：指如果系统按照这种序列分配资源，则每个进程都能顺利完成。

安全状态：只要能找出一个安全序列的系统

因此可以在资源分配之前预先判断这次分配是否会导致系统进入不安全状态

系统处于不安全状态未必死锁，但死锁时一定处于不安全状态。系统处于安全状态一定不会死锁。

2）银行家算法

核心思想：在进程提出资源申请时，先预判此次分配是否会导致系统进入不安全状态。如果会进入不安全状态，就暂时不答应这次请求，让该进程先阻塞等待。

5、死锁的检测

资源分配图

两种节点

进程结点：对应一个进程

资源结点：对应一类资源，一类资源可能有多个

两种边

进程结点 => 资源结点：表示进程想申请几个资源（每条边代表一个)

资源节点 => 进程结点：表示已经为进程分配了几个资源（每条边代表一个）

依次消除与不阻塞进程相连的边，最终能消除所有边，就称这个图是可完全简化的。此时一定没有发生死锁（安全序列）。如果最终不能消除所有边，那么此时就是发生了死锁，最终还连着边的那些进程就是处于死锁状态的进程。

死锁定理：如果某时刻系统的资源分配图是不可完全简化的，那么此时系统死锁

6、死锁的解除

资源剥夺法：挂起某些死锁进程，并抢占它的资源，将这些资源分配给其他的死锁进程。但是应防止被挂起的进程长时间得不到资源而饥饿。撤销进程法（或称终止进程法）：强制撤销部分、甚至全部死锁进程，并剥夺这些进程的资源。进程回退法：让一个或多个死锁进程回退到足以避免死锁的地步。这就要求系统要记录进程。