多进程编程

引言

以哲学思想定制学习框架

唯物辩证法（Materialist Dialectics），是一种研究自然、社会、历史和思维的哲学方法。此处为研究多进程编程
唯物辩证法试图回答的问题是“世界的存在状态问题”。世界存在的基本特征有两个：

• 世界是普遍联系的
  矛盾（即对立统一）是事物普遍联系的根本内容。
  矛盾的双方总是“相比较而存在，相斗争而发展”的
• 世界是永恒发展的
  所谓发展，是指事物由简单到复杂、由低级到高级的变化趋势
  其实质是新事物的产生和旧事物的灭亡。

单线程与多线程

单线程与多线程的联系与发展

• 单线程程序
  一般来说，在没有线程的帮助下，程序在一个时间段只能执行一段代码，其它代码段只有在等待它完成后才能执行。该程序的处理流程从头到尾只有一条线，这样的程序我们称之为单线程程序（Single Thread Program）
• 多线程程序
  当程序由一个以上的线程所构成时，称此程序为多线程程序（Multithread Program）
  典型的多线程程序有：
  • GUI应用程序，Swing桌面程序就属于此类。
  • 较花费时间的I/O处理,一般来说,文件和网络的输入/输出处理比较花费时间,如果在这段无法进行其它处理,则程序性能会大打折扣,遇到这种情况首先要想到用多线程解决问题.
  • 多连接网络处理。

并发与并行

并发与并行的联系与发展

• 并发
  当有多个线程在操作时,如果系统只有一个CPU,则它根本不可能真正同时进行一个以上的线程,它只能把CPU运行时间划分成若干个时间段,再将时间段分配给各个线程执行,在一个时间段的线程代码运行时,其它线程处于挂起状态.这种方式我们称之为并发(Concurrent).
• 并行
  当系统有一个以上CPU时,则线程的操作有可能非并发.当一个CPU执行一个线程时,另一个CPU可以执行另一个线程,两个线程互不抢占CPU资源,可以同时进行,这种方式我们称之为并行(Parallel)
  

多线程在并发和并行环境中的作用

多线程在并发和并行环境中的联系与发展

• 在并发环境时,多线程不可能真正充分利用CPU,节约运行时间,它只是以”挂起->执行->挂起”的方式以很小的时间片分别运行各个线程,给用户以每个线程都在运行的错觉.在这种环境中,多线程程序真正改善的是系统的响应性能和程序的友好性.
• 在并行环境中, 一个时刻允许多个线程运行,这时多线程程序才真正充分利用了多CPU的处理能力, 节省了整体的运行时间.在这种环境中,多线程程序能体现出它的四大优势:充分利用CPU,节省时间,改善响应和增加程序的友好性.

---

多进程编程理论

多进程编程的主要内容是进程控制和进程通信。

唯物辩证法的五对基本范畴是:
现象和本质、内容和形式、原因和结果、可能性和现实性、偶然性和必然性。
除了上述五个基本辩证范畴，比较重要的辩证范畴还有:
整体和部分，个性和共性，相对和绝对，等等。

并发与进程的因果
在多道程序环境下，允许多个程序并发执行，此时它们将失去封闭性，并具有间断性及不可再现性的特征。
为此引入了进程(Process)的概念，以便更好地描述和控制程序的并发执行，实现操作系统的并发性和共享性。

什么是进程?

进程的形式
进程是具有独立功能的程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。

进程的内容
进程一般由程序、数据集合和进程控制块三部分组成。

• 程序用于描述进程要完成的功能，是控制进程执行的指令集；
• 数据集合是程序在执行时所需要的数据和工作区；
• 程序控制块(Program Control Block，简称PCB)，包含进程的描述信息和控制信息，是进程存在的唯一标志。

进程的个性
进程是操作系统的资源分配和独立运行的基本单位。它一般由以下三个部分组成。

• 程序段
  程序段就是能被进程调度程序调度到CPU执行的程序代码段。
  注意，程序可以被多个进程共享，就是说多个进程可以运行同一个程序。
• 数据段
  一个进程的数据段，可以是进程对应的程序加工处理的原始数据，也可以是程序执行时产生的中间或最终结果。
• 进程控制块
  进程创建时，操作系统就新建一个PCB结构，它之后就常驻内存，任一时刻可以存取, 在进程结束时删除。PCB是进程实体的一部分，是进程存在的唯一标志。
  • 当创建一个进程时，系统为该进程建立一个PCB；
  • 当进程执行时，系统通过其PCB了解进程的现行状态信息，以便对其进行控制和管理；
  • 当进程结束时，系统收回其PCB,该进程随之消亡。

进程的共性
进程具有的特征：

• 动态性：进程是程序的一次执行过程，是临时的，有生命期的，是动态产生，动态消亡的；
• 并发性：任何进程都可以同其他进程一起并发执行；
• 独立性：进程是系统进行资源分配和调度的一个独立单位；
• 结构性：进程由程序、数据和进程控制块三部分组成。

进程控制块(PCB)详情

操作系统通过PCB表来管理和控制进程。
PCB通常包含的内容如图：

上图是一个PCB的实例，PCB主要包括进程描述信息、进程控制和管理信息、资源分配清单和处理机相关信息等。各部分的主要说明如下：

• 进程描述信息
  • 进程标识符：标志各个进程，每个进程都有一个并且是唯一的标识号。
  • 用户标识符：进程归属的用户，用户标识符主要为共享和保护服务。
• 进程控制和管理信息
  • 进程当前状态：描述进程的状态信息，作为处理机分配调度的依据。
  • 进程优先级：描述进程抢占处理机的优先级，优先级高的进程可以优先获得处理机。
• 资源分配清单
  用于说明有关内存地址空间或虚拟地址空间的状况；所打开文件的 列表和所使用的输入/输出设备信息。
• 处理机相关信息
  主要指处理机中各寄存器值，当进程被切换时，处理机状态信息 都必须保存在相应的PCB中，以便在该进程重新执行时，能再从断点继续执行。

在一个系统中，通常存在着许多进程，有的处于就绪状态，有的处于阻塞状态，而且阻塞的原因各不相同。为了方便进程的调度和管理，需要将各进程的PCB用适当的方法组织起来。
目前，常用的组织方式有链接方式和索引方式两种。

• 链接方式将同一状态的PCB链接成一个队列，不同状态对应不同的队列，也可以把处于阻塞状态的进程的PCB，根据其阻塞原因的不同，排成多个阻塞队列。
• 索引方式是将同一状态的进程组织在一个索引表中，索引表的表项指向相应的PCB，不同状态对应不同的索引表，如就绪索引表和阻塞索引表等。

进程控制

进程的生命周期

进程在其生命周期内，由于系统中各进程之间的相互制约关系及系统的运行环境的变化，使得进程的状态也在不断地发生变化（一个进程会经历若干种不同状态）。

唯物辩证法认为：可能性和现实性是揭示客观事物由可能向现实转化过程的一对范畴。可能性指事物包含的种种可能的发展趋势，现实性指已经实现了的可能性，即实际存在的事物和过程。
由于事物内部矛盾和外部矛盾的复杂性，事物往往包含相互矛盾的几种可能性。但是只有一种可能性在内外条件齐备的情况下转化为现实，其他的可能性在矛盾的斗争中被克服而没有成为现实。

进程的现实性：创建、运行、结束
进程的可能性：运行、就绪、阻塞状态

创建过程

创建状态
操作系统在创建进程时要进行的工作包括：
分配和建立进程控制块表项、建立资源表格并分配资源、加载程序并建立地址空间；

结束过程

结束状态
进程正从系统中消失，这可能是进程正常结束或其他原因中断退出运行。当进程需要结束运行时，系统首先必须置该进程为结束状态，然后再进一步处理资源释放和回收等工作。

运行过程

• 运行状态
  进程正在处理机上运行。在单处理机环境下，每一时刻最多只有一个进程处于运行状态。
• 就绪状态
  进程获得了除处理机之外的一切所需资源，一旦得到处理机即可运行。以下三种情况进入就绪状态：
  • 创建状态 -> 就绪状态：进程创建之后，等待处理器运行
  • 运行状态 -> 就绪状态：时间片已用完，此进程被强制暂停，等待下一个属于它的时间片到来；
  • 阻塞状态 -> 就绪状态：等待的事件到来时，如I/O操作完成；
• 阻塞状态
  进程需要其他资源（除了处理机）或等待某一事件而暂停运行，如等待某资源为可用（不包括处理机）或等待输入/输出完成。即使处理机空闲，该进程也不能运行。

下图说明了五种进程状态的转换：

进程控制的详情

进程控制的主要功能是对系统中的所有进程实施有效的管理，它具有创建新进程、终止已有进程、实现进程状态转换等功能。
在操作系统中，一般把进程控制用的程序段称为原语，原语的特点是执行期间不允许中断，它是一个不可分割的基本单位。实现方式有两种：

• 通常可由硬件来实现完成不被分割执行特性的功能
• 在单处理机时可由软件通过屏蔽中断方法实现不被中断执行特性。

进程的创建

允许一个进程创建另一个进程。此时创建者称为父进程，被创建的进程称为子进程。子进程可以继承父进程所拥有的资源。当子进程被撤销时，应将其从父进程那里获得的资源归还给父进程。此外，在撤销父进程时，也必须同时撤销其所有的子进程。
在操作系统中，终端用户登录系统、作业调度、系统提供服务、用户程序的应用请求等都会引起进程的创建。
操作系统创建一个新进程的过程如下（创建原语)：

• 为新进程分配一个唯一的进程标识号PID，并申请一个空白的PCB(PCB是有限的)。若PCB申请失败则创建失败。
• 为进程分配资源，为新进程的程序和数据、以及用户栈分配必要的内存空间（在PCB 中体现）。
• 初始化PCB,主要包括初始化标志信息、初始化处理机状态信息和初始化处理机控制信息，以及设置进程的优先级等。
• 如果进程就绪队列能够接纳新进程，就将新进程插入到就绪队列，等待被调度运行。

进程的终止

引起进程终止的事件主要有：

• 正常结束，表示进程的任务已经完成和准备退出运行。
• 异常结束是指进程在运行时，发生了某种异常事件，使程序无法继续运行，如存储区越界、保护错、非法指令、特权指令错、I/O故障等。
• 外界干预是指进程应外界的请求而终止运行，如操作员或操作系统干预、父进程请求和父进程终止。

操作系统终止进程的过程如下（撤销原语）：

• 根据被终止进程的标识符，检索PCB，从中读出该进程的状态。
• 若被终止进程处于执行状态，立即终止该进程的执行，将处理机资源分配给其他进程。
• 若该进程还有子进程，则应将其所有子进程终止。
• 将该进程所拥有的全部资源，或归还给其父进程或归还给操作系统。
• 将该PCB从所在队列（链表）中删除。

进程的阻塞和唤醒

正在执行的进程，由于期待的某些事件未发生，如请求系统资源失败、等待某种操作的完成、新数据尚未到达或无新工作做等，则由系统自动执行阻塞原语(Block)，使自己由运行状态变为阻塞状态。
可见，进程的阻塞是进程自身的一种主动行为，也因此只有处于运行态的进程（获得CPU），才可能将其转为阻塞状态。

阻塞原语

阻塞原语的执行过程是：

• 找到将要被阻塞进程的标识号对应的PCB。
• 若该进程为运行状态，则保护其现场，将其状态转为阻塞状态，停止运行。
• 把该PCB插入到相应事件的等待队列中去。

当被阻塞进程所期待的事件出现时，如它所启动的I/O操作已完成或其所期待的数据已到达，则由有关进程（比如，提供数据的进程）调用唤醒原语(Wakeup)，将等待该事件的进程唤醒。

唤醒原语

唤醒原语的执行过程是：

• 在该事件的等待队列中找到相应进程的PCB。
• 将其从等待队列中移出，并置其状态为就绪状态。
• 把该PCB插入就绪队列中，等待调度程序调度。

需要注意的是，Block原语和Wakeup原语是一对作用刚好相反的原语，必须成对使用。 Block原语是由被阻塞进程自我调用实现的，而Wakeup原语则是由一个与被唤醒进程相合作或被其他相关的进程调用实现的。

进程切换

进程切换是指处理机从一个进程的运行转到另一个进程上运行，这个过程中，进程的运行环境产生了实质性的变化。
进程切换的过程如下：

• 保存处理机上下文，包括程序计数器和其他寄存器。
• 更新PCB信息。
• 把进程的PCB移入相应的队列，如就绪、在某事件阻塞等队列。
• 选择另一个进程执行，并更新其PCB。
• 更新内存管理的数据结构。
• 恢复处理机上下文。

---

进程通信

进程通信是指进程之间的信息交换。PV操作是低级通信方式，髙级通信方式是指以较高的效率传输大量数据的通信方式。

唯物辩证法认为：联系具有客观性、普遍性、和多样性。

• 联系的客观性：联系是事物本身所固有、不以人的主观意志为转移的。
• 联系的普遍性：一切事物、现象和过程，及其内部各要素、部分、环节，都不是孤立存在的，它们相互依赖、相互作用、相互影响、相互制约。但另一方面事物又存在着相对独立性，即任何事物都同其他事物相区别而相对独立地存在。
• 联系的多样性：从大的方面说，联系可分为内部联系和外部联系、本质联系和非本质联系、必然联系和偶然联系、主要联系和次要联系、直接联系和间接联系，等等。

进程之间的联系：通信

低级通信方式

信号量的PV操作，详见信号量机制实现进程同步互斥

高级通信方式

共享内存

在通信的进程之间存在一块可直接访问的共享空间()，通过对这片共享空间进行写/读操作实现进程之间的信息交换。在对共享空间进行写/读操作时，需要使用同步互斥工具（如 P操作、V操作），对共享空间的写/读进行控制。(详见进程间的相互制约关系)

共享内存又分为两种：

• 低级方式的共享是基于数据结构的共享；
• 高级方式则是基于内存区的共享。

操作系统只负责为通信进程提供可共享使用的存储空间和同步互斥工具，而数据交换则由用户自己安排读/写指令完成。

需要注意的是，用户进程空间一般都是独立的，要想让两个用户进程共享空间必须通过特殊的系统调用实现，而进程内的线程是自然共享进程空间的。

消息队列

在消息队列系统中，进程间的数据交换是以格式化的消息(Message)为单位的。
进程通过系统提供的发送消息和接收消息两个原语进行数据交换。

• 直接通信方式
  发送进程直接把消息发送给接收进程，并将它挂在接收进程的消息缓冲队列上，接收进程从消息缓冲队列中取得消息。
• 间接通信方式
  发送进程把消息发送到某个中间实体中，接收进程从中间实体中取得消息。
  这种中间实体一般称为信箱，这种通信方式又称为信箱通信方式。
  该通信方式广泛应用于计算机网络中，相应的通信系统称为电子邮件系统。

管道通信

管道通信是消息传递的一种特殊方式。所谓“管道”，是指用于连接一个读进程和一个写进程以实现它们之间通信的一个共享文件，又名pipe文件。

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

为了协调双方的通信，管道机制必须提供以下三方面的协调能力：互斥、同步和确定对方的存在。

---

进程同步机制

进程并发与进程同步的因果
在多道程序环境下，进程是并发执行的，不同进程之间存在着不同的相互制约关系。为了协调进程之间的相互制约关系，引入了进程同步的概念。操作系统实现进程同步互斥的机制称为同步机制。

进程间的相互制约关系

临界资源

虽然多个进程可以共享系统中的各种资源，但其中许多资源一次只能为一个进程所使用，我们把一次仅允许一个进程使用的资源称为临界资源。许多物理设备都属于临界资源，如打印机等。此外，还有许多变量、数据等都可以被若干进程共享，也属于临界资源。

对临界资源的访问，必须互斥地进行，在每个进程中，访问临界资源的那段代码称为临界区。
为了保证临界资源的正确使用，可以把临界资源的访问过程分成四个部分：

• 进入区。为了进入临界区使用临界资源，在进入区要检查可否进入临界区，如果可以进入临界区，则应设置正在访问临界区的标志，以阻止其他进程同时进入临界区。
• 临界区。进程中访问临界资源的那段代码，又称临界段。
• 退出区。将正在访问临界区的标志清除。
• 剩余区。代码中的其余部分。

  do {
      entry section;  //进入区
      critical section;  //临界区
      exit section;  //退出区
      remainder section;  //剩余区
  } while (true)

唯物辩证法认为：矛盾（即对立统一）是事物普遍联系的根本内容。
所谓矛盾，在辩证法中是指“事物内部或事物之间的对立统一的辩证关系”；
矛盾的双方总是“相比较而存在，相斗争而发展”的。

• 矛盾的同一性和斗争性
  唯物辩证法认为：同一性和斗争性是矛盾的两种基本属性。
  • 同一性是指矛盾双方相互依存，相互联系、相互吸引、相互贯通、或相互渗透的性质和趋势
  • 斗争性是指矛盾双方相互排斥、相互限制、相互否定、相互分离、或互相批评的性质和趋势；
• 矛盾的普遍性和特殊性
  唯物辩证法认为：
  • 矛盾的普遍性是指矛盾存在于一切事物的发展过程中，每一事物的发展过程中自始至终存在着矛盾运动。
  • 矛盾的特殊性是指具体事物的矛盾及每一矛盾的各个方面都有其特点，这是一事物区别于他事物的本质，是世界上事物之所以有差别的根据。

进程间的矛盾：同步和互斥

同步

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

例如，输入进程A通过单缓冲向进程B提供数据。

• 当该缓冲区空时，进程B不能获得所需数据而阻塞，一旦进程A将数据送入缓冲区，进程B被唤醒。
• 当缓冲区满时，进程A被阻塞，仅当进程B取走缓冲数据时，才唤醒进程A。

互斥

互斥亦称间接制约关系。当一个进程进入临界区使用临界资源时，另一个进程必须等待, 当占用临界资源的进程退出临界区后，另一进程才允许去访问此临界资源。

例如，在仅有一台打印机的系统中，有两个进程A和进程B，如果进程A需要打印时, 系统已将打印机分配给进程B,则进程A必须阻塞。一旦进程B将打印机释放，系统便将进程A唤醒，并将其由阻塞状态变为就绪状态。

实现临界区互斥的方法

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

• 空闲让进。临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区。
• 忙则等待。当已有进程进入临界区时，其他试图进入临界区的进程必须等待。
• 有限等待。对请求访问的进程，应保证能在有限时间内进入临界区。
• 让权等待。当进程不能进入临界区时，应立即释放处理器，防止进程忙等待。

软件实现方法

在进入区设置和检查一些标志来标明是否有进程在临界区中，如果已有进程在临界区，则在进入区通过循环检查进行等待，进程离开临界区后则在退出区修改标志。

单标志法(测试版)

该算法设置一个公用整型变量turn,用于指示被允许进入临界区的进程编号，即若turn=0，则允许P0进程进入临界区。该算法可确保每次只允许一个进程进入临界区。但两个进程必须交替进入临界区，如果某个进程不再进入临界区了，那么另一个进程也将进入临界区（违背“空闲让进”）这样很容易造成资源利用的不充分。

// P0进程
while(turn!=0);
critical section;
turn=1;
remainder section;

// P1进程
while(turn!=1);  // 进入区
critical section;  // 临界区
turn = 0;  // 退出区
remainder section;  // 剩余区

双标志法先检查(测试版)

该算法的基本思想是在每一个进程访问临界区资源之前，先查看一下临界资源是否正被访问，若正被访问，该进程需等待；否则，进程才进入自己的临界区。为此，设置了一个数据flag[i]，如第i个元素值为FALSE，表示Pi进程未进入临界区，值为TRUE，表示Pi进程进入临界区。

// Pi 进程
while(flag[j]);  // ①    
flag[i]=TRUE;  // ③  
critical section;   
flag[i] = FALSE;
remainder section;

// Pj 进程
while(flag[i]);  // ② 进入区
flag[j] =TRUE;  // ④ 进入区
critical section;  // 临界区
flag[j] = FALSE;  // 退出区
remainder section;  // 剩余区

优点：不用交替进入，可连续使用；
缺点：Pi和Pj可能同时进入临界区。按序列①②③④ 执行时，会同时进入临界区（违背“忙则等待”)。即在检查对方flag之后和切换自己flag 之前有一段时间，结果都检查通过。这里的问题出在检查和修改操作不能一次进行。

双标志法后检查(测试版)

“双标志法先检查”是先检测对方进程状态标志后，再置自己标志，由于在检测和放置中可插入另一个进程到达时的检测操作，会造成两个进程在分别检测后，同时进入临界区。
为此，“双标志法后检查”釆用先设置自己标志为TRUE后,再检测对方状态标志，若对方标志为TURE，则进程等待；否则进入临界区。

// Pi进程
flag[i] =TRUE;
while(flag[j]);
critical section;
flag[i] =FLASE;
remainder section;

// Pj进程
flag[j] =TRUE;  // 进入区
while(flag[i]);  // 进入区
critical section;  // 临界区
flag [j] =FLASE;   // 退出区
remainder section;  // 剩余区

当两个进程几乎同时都想进入临界区时，它们分别将自己的标志值flag设置为TRUE，并且同时检测对方的状态（执行while语句），发现对方也要进入临界区，于是双方互相谦让，结果谁也进不了临界区，从而导致“饥饿”现象。(详见进程死锁)

Peterson’s Algorithm(正式版)

flag[n]的值为真，表示ID号为n的进程希望进入该临界区. 变量turn保存有权访问共享资源的进程的ID号.

//flag[] is boolean array; and turn is an integer
flag[i]   = false;
flag[j]   = false;
int turn;

// Pi进程
flag[i]=TURE; turn=j;
while(flag[j]&&turn==j);
critical section;
flag[i]=FLASE;
remainder section;

// Pj进程
flag[j] =TRUE;turn=i;  // 进入区
while(flag[i]&&turn==i);   // 进入区
critical section;  // 临界区
flag[j]=FLASE;  // 退出区
remainder section;  // 剩余区

本算法的基本思想是“单标志法”和“双标志法后检查”的结合。利用flag解决临界资源的互斥访问，而利用turn解决“饥饿”现象。

硬件实现方法

计算机提供了特殊的硬件指令，允许对一个字中的内容进行检测和修正，或者是对两个字的内容进行交换等。通过硬件支持实现临界段问题的低级方法或称为元方法。

中断屏蔽方法

当一个进程正在使用处理机执行它的临界区代码时，要防止其他进程再进入其临界区访问的最简单方法是禁止一切中断发生，或称之为屏蔽中断、关中断。
因为CPU只在发生中断时引起进程切换，这样屏蔽中断就能保证当前运行进程将临界区代码顺利地执行完，从而保证了互斥的正确实现，然后再执行开中断。其典型模式为：

…  
关中断;  
临界区;  
开中断;  
…

这种方法限制了处理机交替执行程序的能力，因此执行的效率将会明显降低。对内核来说，当它执行更新变量或列表的几条指令期间关中断是很方便的，但将关中断的权力交给用户则很不明智，若一个进程关中断之后不再开中断，则系统可能会因此终止。

硬件指令方法

• TestAndSet指令
  TestAndSet指令：这条指令是原子操作，即执行该代码时不允许被中断。其功能是读出指定标志后把该标志设置为真。指令的功能描述如下：

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

  可以为每个临界资源设置一个共享布尔变量lock，表示资源的两种状态：true表示正被占用，初值为false。在进程访问临界资源之前，利用TestAndSet检查和修改标志lock；若有进程在临界区，则重复检查，直到进程退出。利用该指令实现进程互斥的算法描述如下：

  while (TestAndSet (& lock));
  // 进程的临界区代码段;
  lock=false;
  // 进程的其他代码

• Swap指令
  Swap指令：该指令的功能是交换两个字节的内容。其功能描述如下。

  Swap(boolean *a, boolean *b){  
      boolean temp;
      Temp=*a;
      *a = *b;
      *b = temp;
  }

  应为每个临界资源设置了一个共享布尔变量lock，初值为false；在每个进程中再设置一个局部布尔变量key，用于与lock交换信息。在进入临界区之前先利用Swap指令交换lock 与key的内容，然后检查key的状态；有进程在临界区时，重复交换和检查过程，直到进程退出。利用Swap指令实现进程互斥的算法描述如下：

  key=true;
  while(key!=false)
    Swap(&lock, &key);
  // 进程的临界区代码段；
  lock=false;
  // 进程的其他代码；

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

注意：以上对TestAndSet和Swap指令的描述仅仅是功能实现，并非软件实现定义，事实上它们是由硬件逻辑直接实现的，不会被中断。

信号量机制实现进程同步互斥

信号量机制是一种功能较强的机制，可用来解决互斥与同步的问题，它只能被两个标准的原语wait(S)和signal(S)来访问，也可以记为“P操作”和“V操作”。

原语之所以不能被中断执行，是因为原语对变量的操作过程如果被打断，可能会去运行另一个对同一变量的操作过程，从而出现临界段问题。如果能够找到一种解决临界段问题的元方法，就可以实现对共享变量操作的原子性。

信号量

整型信号量

整型信号量被定义为一个用于表示资源数目的整型量S，wait和signal操作可描述为：

wait(S){
    while (S<=0);
    S=S-1;
}

signal(S){
    S=S+1;
}

wait操作中，只要信号量S<=0，就会不断地测试。因此，该机制并未遵循“让权等待” 的准则，而是使进程处于“忙等”的状态。

记录型信号量

记录型信号量是不存在“忙等”现象的进程同步机制。除了需要一个用于代表资源数目的整型变量value外，再增加一个进程链表L，用于链接所有等待该资源的进程，记录型信号量是由于釆用了记录型的数据结构得名。记录型信号量可描述为：

typedef struct{
    int value;
    struct process *L;
} semaphore;

相应的wait(S)和signal(S)的操作如下：

void wait (semaphore S) { //相当于申请资源
    S.value--;
    if(S.value<0) {
        add this process to S.L;
        block(S.L);
    }
}

wait操作，S.value--，表示进程请求一个该类资源，当S.value<0时，表示该类资源已分配完毕，因此进程应调用block原语，进行自我阻塞，放弃处理机，并插入到该类资源的等待队列S.L中，可见该机制遵循了“让权等待”的准则。

void signal (semaphore S) {  //相当于释放资源
    S.value++;
    if(S.value<=0){
        remove a process P from S.L;
        wakeup(P);
    }
}

signal操作，表示进程释放一个资源，使系统中可供分配的该类资源数增1，故S.value++。若加1后仍是S.value<=0，则表示在S.L中仍有等待该资源的进程被阻塞，故还应调用wakeup 原语，将S.L中的第一个等待进程唤醒。

利用信号量实现进程同步

信号量机制能用于解决进程间各种同步问题。设S为实现进程P1、P2同步的公共信号量，初值为0。进程P2中的语句y要使用进程P1中语句x的运行结果，所以只有当语句x执行完成之后语句y才可以执行。其实现进程同步的算法如下：

semaphore S = 0;  //初始化信号量
P1 ( ) {
    // …
    x;  //语句x
    V(S);  //告诉进程P2,语句乂已经完成
}
P2()）{
    // …
    P(S) ;  //检查语句x是否运行完成
    y;  // 检查无误，运行y语句
    // …
}

利用信号量实现进程互斥

信号量机制也能很方便地解决进程互斥问题。设S为实现进程P1、P2互斥的信号量，由于每次只允许一个进程进入临界区，所以S的初值应为1（即可用资源数为1)。只需把临界区置于P(S)和V(S)之间，即可实现两进程对临界资源的互斥访问。其算法如下：

semaphore S = 1;  //初化信号量
P1 ( ) {
    // …
    P(S);  // 准备开始访问临界资源，加锁
    // 进程P1的临界区
    V(S);  // 访问结束，解锁
    // …
}
P2() {
    // …
    P(S); //准备开始访问临界资源，加锁
    // 进程P2的临界区；
    V(S);  // 访问结束，解锁
    // …
}

互斥的实现是不同进程对同一信号量进行P、V操作，一个进程在成功地对信号量执行了P操作后进入临界区，并在退出临界区后，由该进程本身对该信号量执行V操作,表示当前没有进程进入临界区，可以让其他进程进入。

利用信号量实现前驱关系

信号量也可以用来描述程序之间或者语句之间的前驱关系。图2-8给出了一个前驱图，其中S1, S2, S3, …, S6是最简单的程序段（只有一条语句）。为使各程序段能正确执行，应设置若干个初始值为“0”的信号量。例如，为保证S1 -> S2、 S1 -> S3的前驱关系，应分别设置信号量a1、a2。同样，为了保证 S2 -> S4、S2 ->S5、S3 -> S6、S4 -> S6、S5 -> S6,应设置信号量bl、b2、c、d、e。

实现算法如下：

semaphore  al=a2=bl=b2=c=d=e=0;  //初始化信号量
S1() {
    // …
    V(al);  V(a2) ;  //S1已经运行完成
}
S2() {
    P(a1);  //检查S1是否运行完成
    // …
    V(bl); V(b2); // S2已经运行完成
}
S3() {
    P(a2);  //检查S1是否已经运行完成
    // …
    V(c);  //S3已经运行完成
}
S4() {
    P(b1);  //检查S2是否已经运行完成
    // …
    V(d);  //S4已经运行完成
}
S5() {
    P(b2);  //检查S2是否已经运行完成
    // …
    V(e);  // S5已经运行完成
}
S6() {
    P(c);  //检查S3是否已经运行完成
    P(d);  //检查S4是否已经运行完成
    P(e);  //检查S5是否已经运行完成
    // …;
}

经典进程同步问题

分析进程同步和互斥问题的方法：

• 关系分析。找出问题中的进程数，并且分析它们之间的同步和互斥关系。同步、互斥、前驱关系直接按照上面例子中的经典范式改写。
• 整理思路。找出解决问题的关键点，并且根据进程的操作流程确定P操作、V操作的大致顺序。
• 设置信号量。根据上面两步，设置需要的信号量，确定初值，完善整理。

生产者-消费者问题

问题描述

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

问题分析

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

生产者-消费者进程的描述如下：

semaphore mutex=1; //临界区互斥信号量
semaphore empty=n;  //空闲缓冲区
semaphore full=0;  //缓冲区初始化为空
producer () { //生产者进程
    while(1){
        produce an item in nextp;  //生产数据
        P(empty);  //获取空缓冲区单元
        P(mutex);  //进入临界区.
        add nextp to buffer;  //将数据放入缓冲区
        V(mutex);  //离开临界区,释放互斥信号量
        V(full);  //满缓冲区数加1
    }
}
consumer () {  //消费者进程
    while(1){
        P(full);  //获取满缓冲区单元
        P(mutex);  // 进入临界区
        remove an item from buffer;  //从缓冲区中取出数据
        V (mutex);  //离开临界区，释放互斥信号量
        V (empty) ;  //空缓冲区数加1
        consume the item;  //消费数据
    }
}

该类问题要注意对缓冲区大小为n的处理，当缓冲区中有空时便可对empty变量执行P 操作，一旦取走一个产品便要执行V操作以释放空闲区。对empty和full变量的P操作必须放在对mutex的P操作之前。如果生产者进程先执行P(mutex)，然后执行P(empty)，消费者执行P(mutex),然后执行P(fall),这样可不可以？答案是否定的。设想生产者进程已经将缓冲区放满，消费者进程并没有取产品，即empty = 0，当下次仍然是生产者进程运行时，它先执行P(mutex)封锁信号量，再执行P(empty)时将被阻塞，希望消费者取出产品后将其唤醒。轮到消费者进程运行时，它先执行P(mutex)，然而由于生产者进程已经封锁mutex信号量，消费者进程也会被阻塞，这样一来生产者、消费者进程都将阻塞，都指望对方唤醒自己，陷入了无休止的等待。同理，如果消费者进程已经将缓冲区取空，即 full = 0,下次如果还是消费者先运行，也会出现类似的死锁。不过生产者释放信号量时，mutex、full先释放哪一个无所谓，消费者先释放mutex还是empty都可以。

下面再看一个较为复杂的生产者-消费者问题:

问题描述

桌子上有一只盘子，每次只能向其中放入一个水果。爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，儿子专等吃盘子中的橘子，女儿专等吃盘子中的苹果。只有盘子为空时，爸爸或妈妈就可向盘子中放一个水果；仅当盘子中有自己需要的水果时，儿子或女儿
可以从盘子中取出。

问题分析

• 关系分析。这里的关系稍复杂一些，首先由每次只能向其中放入一只水果可知爸爸和妈妈是互斥关系。爸爸和女儿、妈妈和儿子是同步关系，而且这两对进程必须连起来，儿子和女儿之间没有互斥和同步关系，因为他们是选择条件执行，不可能并发，如图2-8所示。
• 整理思路。这里有4个进程，实际上可以抽象为两个生产者和两个消费者被连接到大小为1的缓冲区上。
  
• 信号量设置。首先设置信号量plate为互斥信号量，表示是否允许向盘子放入水果，初值为1，表示允许放入，且只允许放入一个。信号量 apple表示盘子中是否有苹果，初值为0，表示盘子为空，不许取，若apple=l可以取。信号量orange表示盘子中是否有橘子，初值为0，表示盘子为空，不许取，若orange=l可以取。

解决该问题的代码如下：

semaphore plate=l, apple=0, orange=0;
dad() {  //父亲进程
    while (1) {
        prepare an apple;
        P(plate) ;  //互斥向盘中取、放水果
        put the apple on the plate;  //向盘中放苹果
        V(apple);  //允许取苹果
    }
}
mom() {  // 母亲进程
    while(1) {
        prepare an orange;
        P(plate);  //互斥向盘中取、放水果
        put the orange on the plate;  //向盘中放橘子
        V(orange); //允许取橘子
    }
}
son(){  //儿子进程
    while(1){
        P(orange) ;  //互斥向盘中取橘子
        take an orange from the plate;
        V(plate);  //允许向盘中取、放水果
        eat the orange;
    }
}
daughter () {  //女儿进程
    while(1) {
        P(apple);  // 互斥向盘中取苹果
        take an apple from the plate;
        V(plate);  //运行向盘中取、放水果
        eat the apple;
    }
}

进程间的关系如图2-9所示。dad()和daughter()、mam()和son()必须连续执行，正因为如此，也只能在女儿拿走苹果后，或儿子拿走橘子后才能释放盘子，即V(plate)操作。

读者-写者问题

问题描述

有读者和写者两组并发进程，共享一个文件，当两个或以上的读进程同时访问共享数据时不会产生副作用，但若某个写进程和其他进程（读进程或写进程）同时访问共享数据时则可能导致数据不一致的错误。
因此要求：

• 允许多个读者可以同时对文件执行读操作；
• 只允许一个写者往文件中写信息；
• 任一写者在完成写操作之前不允许其他读者或写者工作；
• 写者执行写操作前，应让已有的读者和写者全部退出。

问题分析

• 关系分析。由题目分析读者和写者是互斥的，写者和写者也是互斥的，而读者和读者不存在互斥问题。
• 整理思路。两个进程，即读者和写者。写者是比较简单的，它和任何进程互斥，用互斥信号量的P操作、V操作即可解决。读者的问题比较复杂，它必须实现与写者互斥的同时还要实现与其他读者的同步，因此，仅仅简单的一对P操作、V操作是无法解决的。那么，在这里用到了一个计数器，用它来判断当前是否有读者读文件。当有读者的时候写者是无法写文件的，此时读者会一直占用文件，当没有读者的时候写者才可以写文件。同时这里不同读者对计数器的访问也应该是互斥的。
• 信号量设置。首先设置信号量count为计数器，用来记录当前读者数量，初值为0; 设置mutex为互斥信号量，用于保护更新count变量时的互斥；设置互斥信号量rw用于保证读者和写者的互斥访问。

代码如下：

int count=0;  //用于记录当前的读者数量
semaphore mutex=1;  //用于保护更新count变量时的互斥
semaphore rw=1;  //用于保证读者和写者互斥地访问文件
writer () {  //写者进程
    while (1){
        P(rw); // 互斥访问共享文件
        Writing;  //写入
        V(rw) ;  //释放共享文件
    }
}
reader () {  // 读者进程
    while(1){
        P (mutex) ;  //互斥访问count变量
        if (count==0)  //当第一个读进程读共享文件时
            P(rw);  //阻止写进程写
        count++;  //读者计数器加1
        V (mutex) ;  //释放互斥变量count
        reading;  //读取
        P (mutex) ;  //互斥访问count变量
        count--; //读者计数器减1
        if (count==0)  //当最后一个读进程读完共享文件
            V(rw) ;  //允许写进程写
        V (mutex) ;  //释放互斥变量 count
    }
}

在上面的算法中，读进程是优先的，也就是说，当存在读进程时，写操作将被延迟，并且只要有一个读进程活跃，随后而来的读进程都将被允许访问文件。这样的方式下，会导致写进程可能长时间等待，且存在写进程“饿死”的情况。

如果希望写进程优先，即当有读进程正在读共享文件时，有写进程请求访问，这时应禁止后续读进程的请求，等待到已在共享文件的读进程执行完毕则立即让写进程执行，只有在无写进程执行的情况下才允许读进程再次运行。为此，增加一个信号量并且在上面的程序中 writer()和reader()函数中各增加一对PV操作，就可以得到写进程优先的解决程序。

int count = 0;  //用于记录当前的读者数量
semaphore mutex = 1;  //用于保护更新count变量时的互斥
semaphore rw=1;  //用于保证读者和写者互斥地访问文件
semaphore w=1;  //用于实现“写优先”
writer(){
    while(1){
        P(w);  //在无写进程请求时进入
        P(rw);  //互斥访问共享文件
        writing;  //写入
        V(rw);  // 释放共享文件
        V(w) ;  //恢复对共享支件的访问
    }
}
reader () {  //读者进程
    while (1){
        P (w) ;  // 在无写进程请求时进入
        P (mutex);  // 互斥访问count变量
        if (count==0)  //当第一个读进程读共享文件时
            P(rw);  //阻止写进程写
        count++;  //读者计数器加1
        V (mutex) ;  //释放互斥变量count
        V(w);  //恢复对共享文件的访问
        reading;  //读取
        P (mutex) ; //互斥访问count变量
        count--;  //读者计数器减1
        if (count==0)  //当最后一个读进程读完共享文件
            V(rw);  //允许写进程写
        V (mutex);  //释放互斥变量count
    }
}

哲学家进餐问题

问题描述

一张圆桌上坐着5名哲学家，每两个哲学家之间的桌上摆一根筷子，桌子的中间是一碗米饭，如图2-10所示。哲学家们倾注毕生精力用于思考和进餐，哲学家在思考时，并不影响他人。只有当哲学家饥饿的时候，才试图拿起左、 右两根筷子（一根一根地拿起）。如果筷子已在他人手上，则需等待。饥饿的哲学家只有同时拿到了两根筷子才可以开始进餐，当进餐完毕后，放下筷子继续思考。

问题分析

• 关系分析。5名哲学家与左右邻居对其中间筷子的访问是互斥关系。
• 整理思路。显然这里有五个进程。本题的关键是如何让一个哲学家拿到左右两个筷子而不造成死锁或者饥饿现象。那么解决方法有两个，一个是让他们同时拿两个筷子；二是对每个哲学家的动作制定规则，避免饥饿或者死锁现象的发生。
  
• 信号量设置。定义互斥信号量数组Ch0PstiCk[5] = {l, 1, 1, 1, 1}用于对5个筷子的互斥访问。

对哲学家按顺序从0～4编号，哲学家i左边的筷子的编号为i，哲学家右边的筷子的编号为(i+l)%5。

semaphore chopstick[5] = {1,1,1,1,1}; //定义信号量数组chopstick[5],并初始化
Pi(){  //i号哲学家的进程
    do{
        P (chopstick[i] ) ; //取左边筷子
        P (chopstick[(i+1) %5] ) ；  //取右边篌子
        eat;  //进餐
        V(chopstick[i]) ; //放回左边筷子
        V(chopstick[(i+l)%5]);  //放回右边筷子
        think;  //思考
    } while (1);
}

该算法存在以下问题：当五个哲学家都想要进餐，分别拿起他们左边筷子的时候（都恰好执行完wait(chopstick[i]);)筷子已经被拿光了，等到他们再想拿右边的筷子的时候（执行 wait(chopstick[(i+l)%5]);)就全被阻塞了，这就出现了死锁。

为了防止死锁的发生，可以对哲学家进程施加一些限制条件，比如至多允许四个哲学家同时进餐;仅当一个哲学家左右两边的筷子都可用时才允许他抓起筷子;对哲学家顺序编号，要求奇数号哲学家先抓左边的筷子，然后再转他右边的筷子，而偶数号哲学家刚好相反。正解制定规则如下：假设釆用第二种方法，当一个哲学家左右两边的筷子都可用时，才允许他抓起筷子。

semaphore chopstick[5] = {1,1,1,1,1}; //初始化信号量
semaphore mutex=l;  //设置取筷子的信号量
Pi(){ //i号哲学家的进程
    do{
        P (mutex) ; //在取筷子前获得互斥量
        P (chopstick [i]) ; //取左边筷子
        P (chopstick[ (i+1) %5]) ;  //取右边筷子
        V (mutex) ; //释放取筷子的信号量
        eat;  //进餐
        V(chopstick[i] ) ;  //放回左边筷子
        V(chopstick[ (i+l)%5]) ;  //放回右边筷子
        think;  // 思考
    }while(1);
}

此外还可以釆用AND型信号量机制来解决哲学家进餐问题，有兴趣的读者可以查阅相关资料，自行思考。

吸烟者问题

问题描述

假设一个系统有三个抽烟者进程和一个供应者进程。每个抽烟者不停地卷烟 并抽掉它，但是要卷起并抽掉一支烟，抽烟者需要有三种材料：烟草、纸和胶水。三个抽烟 者中，第一个拥有烟草、第二个拥有纸，第三个拥有胶水。供应者进程无限地提供三种材料， 供应者每次将两种材料放到桌子上，拥有剩下那种材料的抽烟者卷一根烟并抽掉它，并给供 应者一个信号告诉完成了，供应者就会放另外两种材料在桌上，这种过程一直重复（让三个 抽烟者轮流地抽烟)。

问题分析

• 关系分析。供应者与三个抽烟者分别是同步关系。由于供应者无法同时满足两个或以上的抽烟者，三个抽烟者对抽烟这个动作互斥（或由三个抽烟者轮流抽烟得知
• 整理思路。显然这里有四个进程。供应者作为生产者向三个抽烟者提供材料。
• 信号量设置。信号量offer1、offer2、offer3分别表示烟草和纸组合的资源、烟草和 胶水组合的资源、纸和胶水组合的资源。信号量finish用于互斥进行抽烟动作。

代码如下：

int random; //存储随机数
semaphore offer1=0; //定义信号量对应烟草和纸组合的资源
semaphore offer2=0; //定义信号量对应烟草和胶水组合的资源
semaphore offer3=0; //定义信号量对应纸和胶水组合的资源
semaphore finish=0; //定义信号量表示抽烟是否完成

//供应者
while(1){
    random = 任意一个整数随机数;
    random=random% 3;
    if(random==0)
        V(offerl) ; //提供烟草和纸
    else if(random==l)
        V(offer2);  //提供烟草和胶水
    else
        V(offer3)  //提供纸和胶水
    // 任意两种材料放在桌子上;
    P(finish);
}

//拥有烟草者
while(1){
    P (offer3);
    // 拿纸和胶水，卷成烟，抽掉;
    V(finish);
}

//拥有纸者
while(1){
    P(offer2);
    // 烟草和胶水,卷成烟，抽掉；
    V(finish);
}

//拥有胶水者
while(1){
    P(offer1);
    // 拿烟草和纸，卷成烟，抽掉;
    v(finish);
}

进程死锁

死锁的定义

在多道程序系统中，由于多个进程的并发执行，改善了系统资源的利用率并提高了系统的处理能力。然而，多个进程的并发执行也带来了新的问题——死锁。
所谓死锁是指多个进程因竞争资源而造成的一种僵局（互相等待），若无外力作用，这些进程都将无法向前推进。

下面我们通过一些实例来说明死锁现象。

• 先看生活中的一个实例，在一条河上有一座桥，桥面很窄，只能容纳一辆汽车通行。如果有两辆汽车分别从桥的左右两端驶上该桥，则会出现下述的冲突情况。此时，左边的汽车占有了桥面左边的一段，要想过桥还需等待右边的汽车让出桥面右边的一段；右边的汽车占有了桥面右边的一段，要想过桥还需等待左边的汽车让出桥面左边的一段。此时，若左右两边的汽车都只能向前行驶，则两辆汽车都无法过桥。
• 在计算机系统中也存在类似的情况。例如，某计算机系统中只有一台打印机和一台输入设备，进程P1正占用输入设备，同时又提出使用打印机的请求，但此时打印机正被进程P2 所占用，而P2在未释放打印机之前，又提出请求使用正被P1占用着的输入设备。这样两个进程相互无休止地等待下去，均无法继续执行，此时两个进程陷入死锁状态。

死锁产生的原因

• 系统资源的竞争
  通常系统中拥有的不可剥夺资源，其数量不足以满足多个进程运行的需要，使得进程在运行过程中，会因争夺资源而陷入僵局，如磁带机、打印机等。只有对不可剥夺资源的竞争才可能产生死锁，对可剥夺资源的竞争是不会引起死锁的。
• 进程推进顺序非法
  进程在运行过程中，请求和释放资源的顺序不当，也同样会导致死锁。例如，并发进程P1、P2分别保持了资源R1、R2，而进程P1申请资源R2，进程P2申请资源R1时，两者都会因为所需资源被占用而阻塞。
• 信号量使用不当
  进程间彼此相互等待对方发来的消息，结果也会使得这些进程间无法继续向前推进。例如，进程A等待进程B发的消息，进程B又在等待进程A发的消息，可以看出进程A和B不是因为竞争同一资源，而是在等待对方的资源导致死锁。

死锁产生的必要条件

产生死锁必须同时满足以下四个条件，只要其中任一条件不成立，死锁就不会发生。

• 互斥条件：进程要求对所分配的资源（如打印机）进行排他性控制，即在一段时间内某资源仅为一个进程所占有。此时若有其他进程请求该资源，则请求进程只能等待。
• 不剥夺条件：进程所获得的资源在未使用完毕之前，不能被其他进程强行夺走，即只能由获得该资源的进程自己来释放（只能是主动释放)。
• 请求和保持条件：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源已被其他进程占有，此时请求进程被阻塞，但对自己已获得的资源保持不放。
• 循环等待条件：存在一种进程资源的循环等待链，链中每一个进程已获得的资源同时被链中下一个进程所请求。即存在一个处于等待状态的进程集合{Pl, P2, …, pn}，其中Pi等待的资源被P(i+1)占有（i=0, 1, …, n-1)，Pn等待的资源被P0占有，如图2-15所示。

直观上看，循环等待条件似乎和死锁的定义一样，其实不然。按死锁定义构成等待环所要求的条件更严，它要求Pi等待的资源必须由P(i+1)来满足，而循环等待条件则无此限制。 例如，系统中有两台输出设备，P0占有一台，PK占有另一台，且K不属于集合{0, 1, …, n}。

Pn等待一台输出设备，它可以从P0获得，也可能从PK获得。因此，虽然Pn、P0和其他一些进程形成了循环等待圈，但PK不在圈内，若PK释放了输出设备，则可打破循环等待, 如图2-16所示。因此循环等待只是死锁的必要条件。

资源分配图含圈而系统又不一定有死锁的原因是同类资源数大于1。但若系统中每类资源都只有一个资源，则资源分配图含圈就变成了系统出现死锁的充分必要条件。

死锁的处理策略

预防死锁和避免死锁都属于事先预防策略

• 预防死锁的限制条件比较严格，实现起来较为简单，但往往导致系统的效率低，资源利用率低；
• 避免死锁的限制条件相对宽松，资源分配后需要通过算法来判断是否进入不安全状态，实现起来较为复杂。

检测及解除死锁无需釆取任何限制性措施，允许进程在运行过程中发生死锁。通过系统的检测机构及时地检测出死锁的发生，然后釆取某种措施解除死锁。

死锁的几种处理策略的比较见表2-14。

预防死锁

设置某些限制条件，破坏产生死锁的四个必要条件中的一个或几个，以防止发生死锁。
防止死锁的发生只需破坏死锁产生的四个必要条件之一即可。

• 破坏互斥条件
  如果允许系统资源都能共享使用，则系统不会进入死锁状态。但有些资源根本不能同时访问，如打印机等临界资源只能互斥使用。所以，破坏互斥条件而预防死锁的方法不太可行，而且在有的场合应该保护这种互斥性。

• 破坏不剥夺条件
  当一个已保持了某些不可剥夺资源的进程，请求新的资源而得不到满足时，它必须释放已经保持的所有资源，待以后需要时再重新申请。这意味着，一个进程已占有的资源会被暂时释放，或者说是被剥夺了，或从而破坏了不可剥夺条件。
  该策略实现起来比较复杂，释放已获得的资源可能造成前一阶段工作的失效，反复地申请和释放资源会增加系统开销，降低系统吞吐量。这种方法常用于状态易于保存和恢复的资源，如CPU的寄存器及内存资源，一般不能用于打印机之类的资源。

• 破坏请求和保持条件
  釆用预先静态分配方法，即进程在运行前一次申请完它所需要的全部资源，在它的资源未满足前，不把它投入运行。一旦投入运行后，这些资源就一直归它所有，也不再提出其他资源请求，这样就可以保证系统不会发生死锁。
  这种方式实现简单，但缺点也显而易见，系统资源被严重浪费，其中有些资源可能仅在运行初期或运行快结束时才使用，甚至根本不使用。而且还会导致“饥饿”现象，当由于个别资源长期被其他进程占用时，将致使等待该资源的进程迟迟不能开始运行。

• 破坏循环等待条件
  为了破坏循环等待条件，可釆用顺序资源分配法。首先给系统中的资源编号，规定每个进程，必须按编号递增的顺序请求资源，同类资源一次申请完。也就是说，只要进程提出申请分配资源Ri，则该进程在以后的资源申请中，只能申请编号大于Ri的资源。
  这种方法存在的问题是，编号必须相对稳定，这就限制了新类型设备的增加；尽管在为资源编号时已考虑到大多数作业实际使用这些资源的顺序，但也经常会发生作业使甩资源的顺序与系统规定顺序不同的情况，造成资源的浪费；此外，这种按规定次序申请资源的方法，也必然会给用户的编程带来麻烦。

避免死锁

在资源的动态分配过程中，用某种方法防止系统进入不安全状态，从而避免死锁。这种方法所施加的限制条件较弱，可以获得较好的系统性能。

系统安全状态

避免死锁的方法中，允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次资源分配的安全性。若此次分配不会导致系统进入不安全状态，则将资源分配给进程； 否则，让进程等待。
所谓安全状态，是指系统能按某种进程推进顺序( P1, P2, …, Pn)，为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺序地完成。此时称 P1, P2, …, Pn 为安全序列。如果系统无法找到一个安全序列，则称系统处于不安全状态。

假设系统中有三个进程P1、P2和P3,共有12 台磁带机。进程P1总共需要10台磁带机，P2和P3 分别需要4台和9台。假设在T0时刻，进程P1、P2 和P3已分别获得5合、2台和2台，尚有3台未分配，见表2-15。

则在T0时刻是安全的，因为存在一个安全序列P2、P1、P3，即只要系统按此进程序列分配资源，则每个进程都能顺利完成。若在T0时刻后，系统分配1台磁带机给P3，则此时系统便进入不安全状态，因为此时已无法再找到一个安全序列。
并非所有的不安全状态都是死锁状态，但当系统进入不安全状态后，便可能进入死锁状态；反之，只要系统处于安全状态，系统便可以避免进入死锁状态。

银行家算法

银行家算法是最著名的死锁避免算法。
它提出的思想是：把操作系统看做是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。
操作系统按照银行家制定的规则为进程分配资源

• 当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。
• 当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。

数据结构描述

• 可利用资源矢量Available：含有m个元素的歎组，其中的每一个元素代表一类可用的资源数目。Available[j]=K，则表示系统中现有Rj类资源K个。
• 最大需求矩阵Max：为n*m矩阵，定义了系统中n个进程中的每一个进程对m类资源的最大需求。Max[i, j]=K，则表示进程i需要Rj类资源的最大数目为K。
• 分配矩阵Allocation：为n*m矩阵，定义了系统中每一类资源当前已分配给每一进程的资源数。All0Cati0n[i, j]= K，则表示进程i当前已分得Rj类资源的数目为K。
• 需求矩阵Need：为n*m矩阵，表示每个进程尚需的各类资源数。Need[i, j]=K，则表示进程i还需要Rj类资源的数目为K。

上述三个矩阵间存在下述关系：
Need[i, j] = Max[i, j] - Allocation[i, j]

银行家算法描述
设Requesti是进程Pi的请求矢量，如果Requesti[j]=K，表示进程Pi需要Rj类资源K个。当Pi发出资源请求后，系统按下述步骤进行检查：

①如果Requesti[j] <= Need[i, j]，便转向步骤②；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。
②如果Requesti[j] <= Available[j]，便转向步骤③;否则，表示尚无足够资源，Pi须等待。
③系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值：

Available[j] = Available[j] - Requesti[j];  
Allocation[i, j] = Allocation[i, j] + Requesti[ j];  
Need[i, j] = Need[i, j] - Requesti[j];

④系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。

安全性算法
①设置两个矢量。
工作矢量Work；它表示系统可提供给进程继续运行所需的各类资源数目，它含有所个元素，在执行安全算法开始时，Work=Available;
Finish：它表示系统是否有足够的资源分配给进程，使之运行完成。开始时 Finish[i]=false；当有足够资源分配给进程 Pi 时，再令 Finish[i]=true。
②从进程集合中找到一个能满足下述条件的进程：Finish[i]=false; Need[i, j]<=Work[j]; 若找到，执行下一步骤，否则，执行步骤4。
③当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：

Work[j]=Work[j]+Allocation[i, j];
Finish[i]=true;
go to step <2>;

④如果所有进程的Finish[i]=tme都满足，则表示系统处于安全状态；否则，系统处于不安全状态。

银行家算法举例

假定系统中有5个进程{P0, P1, P2, P3, P4}和三类资源{A, B, C}，各种资源的数量分别为10、5、7，在T0时刻的资源分配情况见表2-16。

• T0时刻的安全性。
  利用安全性算法对T0时刻的资源分配进行分析，由表2-17可知，在T0时刻存在着一个安全序列{P1, P3, P4, P2, P0}，故系统是安全的。
  
• P1请求资源
  P1发出请求矢量Request1(l，, 0, 2)，系统按银行家算法进行检查：
• Request1(1, 0, 2) <= Need1(l, 2, 2)。
• Request1(1, 0, 2) <= Available1(3, 3, 2)。
• 系统先假定可为P1分配资源，并修改Available、Allocation1和Need1矢量，由此形成的资源变化情况见表2-18。
• 再利用安全性算法检查此时系统是否安全。
  
• P4请求资源
  P4发出请求矢量Request4(3, 3, 0)，系统按银行家算法进行检查：
  Request4(3, 3, 0) <= Need4(4, 3, 1)。
  Request4(3, 3, 0) > Available(2, 3, 0)，让 P4 等待。
• P0请求资源
  P0发出请求矢量Request0(0, 2, 0)，系统按银行家算法进行检查：
  Request0(0, 2, 0) <= Need0(7, 4, 3)。
  Request0(0, 2, 0) <= Available(2, 3, 0)。
  系统暂时先假定可为P0分配资源，并修改有关数据，见表2-19。
  
• 进行安全性检测。
  可用资源Available(2, 1, 0)已不能满足任何进程的需要，故系统进入不安全状态，此时系统不分配资源。

死锁的检测及解除

前面绍的死锁预防和避免算法，都是在为进程分配资源时施加限制条件或进行检测，若系统为进程分配资源时不釆取任何措施，则应该提供死锁检测和解除的手段。

资源分配图

系统死锁，可利用资源分配图来描述。
如图2-17所示，用圆圈代表一个进程，用框代表一类资源。由于一种类型的资源可能有多个，用框中的一个点代表一类资源中的一个资源。从进程到资源的有向边叫请求边，表示该进程申请一个单位的该类资源；从资源到进程的边叫分配边，表示该类资源已经有一个资源被分配给了该进程。

在图2-17所示的资源分配图中，进程P1已经分得了两个R1资源，并又请求一个R2 资源；进程P2分得了一个R1和一个R2资源，并又请求一个R1资源。

死锁定理

可以通过将资源分配图简化的方法来检测系统状态S是否为死锁状态。简化方法如下：

• 在资源分配图中，找出既不阻塞又不是孤点的进程Pi（即找出一条有向边与它相连，且该有向边对应资源的申请数量小于等于系统中已有空闲资源数量。若所有的连接该进程的边均满足上述条件，则这个进程能继续运行直至完成，然后释放它所占有的所有资源）。消去它所有的请求边和分配边，使之成为孤立的结点。在图2-18(a)中，P1是满足这一条件的进程结点，将P1的所有边消去，便得到图248(b)所示的情况。

• 进程Pi所释放的资源，可以唤醒某些因等待这些资源而阻塞的进程，原来的阻塞进程可能变为非阻塞进程。在图2-17中，进程P2就满足这样的条件。根据第1) 条中的方法进行一系列简化后,若能消去图中所有的边，则称该图是可完全简化的，如图2-18(c)所示。
  
  S为死锁的条件是当且仅当S状态的资源分配图是不可完全简化的,该条件为死锁定理。

死锁的解除

一旦检测出死锁，就应立即釆取相应的措施，以解除死锁。死锁解除的主要方法有：

• 资源剥夺法。挂起某些死锁进程，并抢占它的资源，将这些资源分配给其他的死锁进程。但应防止被挂起的进程长时间得不到资源，而处于资源匮乏的状态。
• 撤销进程法。强制撤销部分、甚至全部死锁进程并剥夺这些进程的资源。撤销的原则可以按进程优先级和撤销进程代价的高低进行。
• 进程回退法。让一（多）个进程回退到足以回避死锁的地步，进程回退时自愿释放资源而不是被剥夺。要求系统保持进程的历史信息，设置还原点。

---

参考

[1] 和风细雨
[2] 计算机操作系统
[3] mickole

引申

[1] [操作系统概念 第7版]
[2] [UNIX环境高级编程]
[3] [UNIX网络编程_卷2_进程间通信]