假设铁路自动售票系统有n个售票终端，该系统为每个售票终端创建一个进程P<sub>i</sub>..

2018年上半年上午试卷综合知识

第 18 题


知识点	进程间的通信进程间的同步同步与互斥工作流进程信号信号量
关键词	工作流进程信号量信号
章/节	计算机软件基础知识

假设铁路自动售票系统有n个售票终端，该系统为每个售票终端创建一个进程P_i（i＝1，2,…，n）管理车票销售过程。假设T_j（j＝1，2,…,m）単元存放某日某趟车的车票剩余票数，Temp为P_i进程的临时工作单元，x为某用户的购票张数。P_i进程的工作流程如下图所示，用P操作和V操作实现进程间的同步与互斥。初始化时系统应将信号量S赋值为（18）。图中（a）、（b）和（c）处应分别填入（19）。

A. n-1

B. 0

C. 1

D. 2

相关试题进程管理

第26题

2013年上半年

进程资源图如图(a)和(b)所示，其中：图(a)中(25);图(b)中(26)。

第25题

2016年上半年

进程P1、P2、P3、P4和P5的前趋图如下图所示：

第25题

2011年上半年

系统中有R类资m源个，现有n个进程互斥使用。若每个进程对R资源的最大需求为w，那么当m、n、w分别取下表中的值时，对于表中的①〜⑥种情况，(25)可能会发生死锁。若将这些情况的分别加上（..

知识点讲解

· 进程间的通信

· 进程间的同步

· 同步与互斥

· 工作流

· 进程

· 信号

· 信号量

进程间的通信

在多道程序环境的系统中存在多个可以并发执行的进程，使得进程之间会存在资源共享和相互合作的问题。进程通信是指各个进程交换信息的过程。

同步与互斥

同步是合作进程间的直接制约问题，互斥是申请临界资源进程间的间接制约问题。

进程间的同步

在计算机系统中，多个进程可以并发执行，每个进程都以各自独立的、不可预知的速度向前推进，但是需要在某些确定点上协调相互合作进程间的工作。例如，进程A向缓冲区送数据，进程B从缓冲区取数据加工，当进程B要取数据加工时，必须是进程A完成了向缓冲区送数据的操作，否则进程B必须停下来等待进程A的操作结束。

可见，所谓进程间的同步是指在系统中一些需要相互合作，协同工作的进程，这样的相互联系称为进程的同步。

进程间的互斥

进程的互斥是指系统中多个进程因争用临界资源而互斥执行。在多道程序系统环境中，各进程可以共享各类资源，但有些资源一次只能供一个进程使用，称为临界资源（Critical Resource，CR），如打印机、共享变量和表格等。

临界区管理的原则

临界区（Critical Section，CS）是进程中对临界资源实施操作的那段程序。对互斥临界区管理的4条原则如下：

（1）有空即进。当无进程处于临界区时，允许进程进入临界区，并且只能在临界区运行有限的时间。

（2）无空则等。当有一个进程在临界区时，其他欲进入临界区的进程必须等待，以保证进程互斥地访问临界资源。

（3）有限等待。对于要求访问临界资源的进程，应保证进程能在有限的时间进入临界区，以免陷入“饥饿”状态。

（4）让权等待。当进程不能进入自己的临界区时，应立即释放处理机，以免进程陷入忙等状态。

信号量机制

荷兰学者Dijkstra于1965年提出的信号量机制是一种有效的进程同步与互斥工具。目前，信号量机制有了很大的发展，主要有整型信号量、记录型信号量和信号量集机制。

整型信号量与PV操作

信号量是一个整型变量，根据控制对象的不同被赋予不同的值。信号量分为如下两类：

（1）公用信号量。实现进程间的互斥，初值为1或资源的数目。

（2）私用信号量。实现进程间的同步，初值为0或某个正整数。

信号量S的物理意义：S≥0表示某资源的可用数，若S<0，则其绝对值表示阻塞队列中等待该资源的进程数。

对于系统中的每个进程，其工作的正确与否不仅取决于它自身的正确性，而且与它在执行中能否与其他相关进程正确地实施同步互斥有关。PV操作是实现进程同步与互斥的常用方法。P操作和V操作是低级通信原语，在执行期间不可分割。其中，P操作表示申请一个资源，V操作表示释放一个资源。

P操作的定义：S:=S-1。若S≥0，则执行P操作的进程继续执行；若S<0，则将该进程置为阻塞状态（因为无可用资源），并将其插入阻塞队列。

P操作可用如下过程表示，其中，Semaphore表示所定义的变量是信号量。

V操作定义：S:=S+1。若S>0，则执行V操作的进程继续执行；若S≤0，则从阻塞状态唤醒一个进程，并将其插入就绪队列，然后执行V操作的进程继续。

V操作可用如下过程表示：

利用PV操作实现进程的互斥

令信号量mutex的初值为1，当进入临界区时执行P操作，退出临界区时执行V操作。这样，利用PV操作实现进程互斥的代码段如下：

利用PV操作实现进程的同步

进程的同步是由于进程间合作引起的相互制约的问题，要实现进程的同步可用一个信号量与消息联系起来，当信号量的值为0时表示等待的消息未产生，当信号量的值为非0时表示等待的消息已经存在。假定用信号量S表示某条消息，进程可以通过调用P操作测试消息是否到达，调用V操作通知消息已准备好。最典型的同步问题是单缓冲区的生产者和消费者的同步问题。

高级通信原语

进程间通信是指进程之间的信息交换，少则一个信息，多则成千上万个信息。根据交换信息量的多少和效率的高低，进程通信的方式分为低级方式和高级方式。PV操作属于低级通信方式，若用PV操作实现进程间通信，则存在如下问题：

（1）编程难度大，通信对用户不透明，即要用户利用低级通信工具实现进程间的同步与互斥。而且，PV操作使用不当容易引起死锁。

（2）效率低，生产者每次只能向缓冲区放一个消息，消费者只能从缓冲区取一个消息。

为了提高信号通信的效率，传递大量数据，减轻程序编制的复杂度，系统引入了高级通信方式。高级通信方式主要分为共享存储模式、消息传递模式和管道通信。

（1）共享存储模式。相互通信的进程共享某些数据结构（或存储区）实现进程之间的通信。

（2）消息传递模式。进程间的数据交换以消息为单位，程序员直接利用系统提供的一组通信命令（原语）来实现通信，如Send（A）、Receive（A）。

（3）管道通信。管道是用于连接一个读进程和一个写进程，以实现它们之间通信的共享文件（pipe文件）。向管道（共享文件）提供输入的发送进程（即写进程），以字符流的形式将大量的数据送入管道；而接收进程可从管道接收大量的数据。由于它们通信时采用管道，所以称为管道通信。

进程间的同步

可见，所谓进程间的同步是指在系统中一些需要相互合作，协同工作的进程，这样的相互联系称为进程的同步。

同步与互斥

同步是合作进程间的直接制约问题，互斥是申请临界资源进程间的间接制约问题。

进程间的同步

可见，所谓进程间的同步是指在系统中一些需要相互合作，协同工作的进程，这样的相互联系称为进程的同步。

进程间的互斥

临界区管理的原则

临界区（Critical Section，CS）是进程中对临界资源实施操作的那段程序。对互斥临界区管理的4条原则如下：

（1）有空即进。当无进程处于临界区时，允许进程进入临界区，并且只能在临界区运行有限的时间。

（2）无空则等。当有一个进程在临界区时，其他欲进入临界区的进程必须等待，以保证进程互斥地访问临界资源。

（3）有限等待。对于要求访问临界资源的进程，应保证进程能在有限的时间进入临界区，以免陷入“饥饿”状态。

（4）让权等待。当进程不能进入自己的临界区时，应立即释放处理机，以免进程陷入忙等状态。

工作流

工作流的定义

工作流（Workflow）是针对业务流程中具有固定程序的常规活动而提出的一个概念，通过将业务流程分解定义良好的任务、角色、规则和过程来进行执行和监控，达到提高生产组织水平和工作效率的目的，工作流技术为企业更好地实现经营目标提供了先进的手段。工作流要解决的主要问题是：为实现某个业务目标，在多个参与者之间，利用计算机，按某种预定规则自动传递文档、信息或者任务。

一个工作流包括一组活动及它们的相互顺序关系，还包括过程及活动的启动和终止条件，以及对每个活动的描述。

工作流管理系统

工作流管理系统指运行在一个或多个工作流引擎上用于定义、实现和管理工作流运行的一套软件系统，它与工作流执行者（人、应用）交互，推进工作流实例的执行，并监控工作流的运行状态。

工作流管理系统将业务流程中工作如何组织协调在一起的规则抽象出来，从而分离了具体工作的逻辑和流程组织的逻辑。我们在工作流管理系统的协助下：开发人员遵从一定的编程接口及约定，就可以开发出更具灵活性的事务处理系统；最终用户无需重新开发事务处理系统，就可以自己更改工作流程，以适应业务变化的需要。

工作流管理系统可以描述不同覆盖范围和不同时间跨度的经营过程，根据经营过程以及组成活动的复杂程度，工作流管理系统可以采取多种实施方式，在不同实施方式中，所应用的信息技术、通信技术和支撑系统结构会有很大的差别，工作流管理系统的实际运行环境也可以在一个工作组内部，也可以在全企业所有业务部门。

工作流管理系统在实际系统中的应用一般分为三个阶段：即模型建立阶段、模型实例化阶段和模型执行阶段。在模型建立阶段，通过利用工作流建模工具，完成企业经营过程模型的建立，将企业的实际经营过程转化为计算机可处理的工作流模型。模型实例化阶段完成为每个过程设定运行所需的参数，并分配每个活动执行所需要的资源，模型执行阶段完成经营过程的执行，在这一过程中，重要的任务是完成人机交互和应用的执行。

工作流的功能

工作流最大的优点是实现了应用逻辑与过程逻辑的分离，因此可以在不修改具体功能的实现情况下，通过修改过程模型来改变系统功能，完成对生产经营部分过程或全部过程的集成管理，有效地把人、信息和应用工具合理地组织在一起，发挥系统的最大效能。工作流技术可以支持企业实现对经营管理和生产组织的过程控制以及决策支持，实现现代企业对“在适当的时间把适当的信息传给适当的人”的要求。

对于引入工作流的组织，能够在软件开发和业务两个层次受益。

.方便开发，工作流管理系统能够简化企业级软件开发甚至维护。

.降低开发风险——通过使用状态和动作这样的术语，业务分析师和开发人员使用同一种语言交谈。这样开发人员就不必将用户需求转化成软件设计了。

.实现统一集中——业务流程经常变化，使用工作流系统的最大好处是：业务流程的实现代码，不再散落在各种各样的系统中。

.加快应用开发——软件不用再关注流程的参与者，开发起来更快，代码更容易维护。

.业务流程管理（BPM）——提高效率，在自动化过程中会去除一些不必要的过程。

.提高对迭代开发的支持。

如果软件中业务流程部分不容易更改，组织就需要花很大的精力在开发前的业务流程分析中，希望一次成功。但可悲的是，在任何软件项目开发中，这都很少能实现。工作流系统使得新业务流程很容易部署，业务流程相关的软件可以一种迭代的方式开发，因此使用工作流系统使开发更有效、风险更低。

进程

简单而言，一个进程就是一个正在运行的程序。一般来说，一个进程至少应该包括以下几个方面的内容。

.相应的程序：进程既然是一个正在运行的程序，当然需要有相应程序的代码和数据。

.CPU上下文：指程序在运行时，CPU中各种寄存器的当前值，包括：程序计数器，用于记录将要取出的指令的地址；程序状态字，用于记录处理器的运行状态信息；通用寄存器，用于存放数据或地址；段寄存器，用于存放程序中各个段的地址；栈指针寄存器，用于记录栈顶的当前位置。

.一组系统资源：包括操作系统用来管理进程的数据结构、进程的内存地址空间、进程正在使用的文件等。

进程有动态性、独立性和并发行三个特性。

（1）动态性。进程是一个正在运行的程序，而程序的运行状态是在不断地变化的。例如，当一个程序在运行的时候，每执行完一条指令，PC寄存器的值就会增加，指向下一条即将执行的指令。而CPU中用来存放数据和地址的那些通用寄存器，它们的值肯定也不断地变化。另外，堆和栈的内容也在不断地变化，每当发生一次函数调用时，就会在栈中分配一块空间，用来存放此次函数调用的参数和局部变量。而当函数调用结束后，这块栈空间就会被释放掉。

（2）独立性。一个进程是一个独立的实体，是计算机系统资源的使用单位。每个进程都有自己的运行上下文和内部状态，在它运行的时候独立于其他的进程。

（3）并发性。从宏观上来看，在系统中同时有多个进程存在，它们相互独立地运行。

下图表示四个进程A、B、C、D在系统中并发地运行。从中可以看出，虽然从宏观上来说，这四个进程都是在系统中运行，但从微观上来看，在任何一个特定的时刻，只有一个进程在CPU上运行。从时间上来看，开始是进程A在运行，然后是进程B在运行，然后是进程C和进程D。接下来又轮到了进程A去运行。因此，在单CPU的情形下，所谓的并发性，指的是宏观上并发运行，而微观上还是顺序运行，各个进程轮流去使用CPU资源。

四个进程在并发运行

在具体实现上，以CPU中的程序计数器PC为例，真正物理上的PC寄存器只有一个。当四个进程在轮流执行时，PC取值的运动轨迹是先在进程A内部流动，然后再到进程B的内部流动，再到进程C和D。从进程的独立性角度来说，每个进程都有“自己”独立的PC寄存器，即逻辑上的PC寄存器，它们的取值相互独立、互不影响。所谓的逻辑PC，其实就是一个内存变量。例如，在上图中，当进程A要执行的时候，就把A的逻辑PC的值拷贝到物理PC中，然后开始运行。当轮到B运行的时候，先把物理PC的当前值保存到A的逻辑PC中，然后再把B的逻辑PC的值装入到物理PC中，即可运行。这样就实现了各个进程的轮流运行。

信号

任务间同步的另一种方式是异步信号。在两个任务之间，可以通过相互发送信号的方式，来协调它们之间的运行步调。

所谓的信号，指的是系统给任务的一个指示，表明某个异步事件已经发生了。该事件可能来自于外部（如其他的任务、硬件或定时器），也可能来自于内部（如执行指令出错）。异步信号管理允许任务定义一个异步信号服务例程ASR（Asynchronous Signal Routine），与中断服务程序不同的是，ASR是与特定的任务相对应的。当一个任务正在运行的时候，如果它收到了一个信号，将暂停执行当前的指令，转而切换到相应的信号服务例程去运行。不过这种切换不是任务之间的切换，因为信号服务例程通常还是在当前任务的上下文环境中运行的。

信号机制与中断处理机制非常相似，但又各有不同。它们的相同点是：

.都具有中断性：在处理中断和异步信号时，都要暂时地中断当前任务的运行；

.都有相应的服务程序；

.都可以屏蔽响应：外部硬件中断可以通过相应的寄存器操作来屏蔽，任务也能够选择不对异步信号进行响应。

信号机制与中断机制的不同点是：

.中断是由硬件或特定的指令产生，而信号是由系统调用产生；

.中断触发后，硬件会根据中断向量找到相应的处理程序去执行；而信号则通过发送信号的系统调用来触发，但系统不一定马上对它进行处理；

.中断处理程序是在系统内核的上下文中运行，是全局的；而信号处理程序是在相关任务的上下文中运行，是任务的一个组成部分。

实时系统中不同的任务经常需要互斥地访问共享资源。当任务试图访问资源时被正使用该资源的其他任务阻塞，可能出现优先级反转的现象，即当高优先级任务企图访问已被某低优先级任务占有的共享资源时，高优先级任务必须等待直到低优先级任务释放它占有的资源。如果该低优先级任务又被一个或多个中等优先级任务阻塞，问题就更加严重。由于低优先级任务得不到执行就不能访问资源、释放资源。于是低优先级任务就以一个不确定的时间阻塞高优先级的任务，导致系统的实时性没有保障。下图为是一个优先级反转的示例。

一个优先级反转的示例

如上图所示，系统存在任务1、任务2、任务3（优先级从高到低排列）和资源R。某时，任务1和任务2都被阻塞，任务3运行且占用资源R。一段时间后，任务1和任务2相继就绪，任务1抢占任务3运行，由于申请资源R失败任务1被挂起。由于任务2的优先级高于任务3，任务2运行。由于任务3不能运行和释放资源R，因此任务1一直被阻塞。极端情况下，任务1永远无法运行，处于饿死状态。

解决优先级反转问题的常用算法有优先级继承和优先级天花板。

优先级继承协议

L. Sha、R. Rajkumar和J. P. Lehoczky针对资源访问控制提出了优先级继承协议（Priority Inheritance Protocol，PIP）。

PIP协议能与任何优先级驱动的抢占式调度算法配合使用，而且不需要有关任务访问资源情况的先验知识。优先级继承协议的执行方式是：当低优先级任务正在使用资源，高优先级任务抢占执行后也要访问该资源时，低优先级任务将提升自身的优先级到高优先级任务的级别，保证低优先级任务继续使用当前资源，以尽快完成访问，尽快释放占用的资源。这样就使高优先级任务得以执行，从而减少高优先级任务被多个低优先级任务阻塞的时间。低优先级任务在运行中，继承了高优先级任务的优先级，所以该协议被称作优先级继承协议。

由于只有高优先级任务访问正被低优先级任务使用的资源时，优先级继承才会发生，在此之前，高优先级任务能够抢占低优先级任务并执行，所以优先级继承协议不能防止死锁，而且阻塞是可以传递的，会形成链式阻塞。另外，优先级继承协议不能将任务所经历的阻塞时间减少到尽可能小的某个范围内。最坏情况下，一个需要μ个资源，并且与v个低优先级任务冲突的任务可能被阻塞min（μ，v）次。

优先级冲顶协议

J. B. Goodenough和L. Sha针对资源访问控制提出了优先级冲顶协议（Priority Ceiling Protocol，PCP）。

PCP协议扩展了PIP协议，能防止死锁和减少高优先级任务经历的阻塞时间。该协议假设所有任务分配的优先级都是固定的，每个任务需要的资源在执行前就已确定。每个资源都具有优先级冲顶值，等于所有访问该资源的任务中具有的最高优先级。任一时刻，当前系统冲顶值（current priority ceiling）等于所有正被使用资源具有的最高冲顶值。如果当前没有资源被访问，则当前系统冲顶值等于一个不存在的最小优先级。当任务试图访问一个资源时，只有其优先级高于当前系统冲顶值，或其未释放资源的冲顶值等于当前系统冲顶值才能获得资源，否则会被阻塞。而造成阻塞的低优先级任务将继承该高优先级任务的优先级。

已经证明，PCP协议的执行规则能防止死锁，但其代价是高优先级任务可能会经历优先级冲顶阻塞（Priority ceiling blocking）。即高优先级任务可能被一个正使用某资源的低优先级任务阻塞，而该资源并不是高优先级任务请求的。这种阻塞又被称作回避阻塞（avoidance blocking），意思是因为回避死锁而引起的阻塞。即使如此，在PCP协议下，每个高优先级任务至多被低优先级任务阻塞一次。使用PCP协议后，能静态分析和确定任务之间的资源竞争，计算出任务可能经历的最大阻塞时间，从而能分析任务集合的可调度性。在PCP协议下，高优先级任务被阻塞时会放弃处理器，因此，访问共享资源的任务可能会产生4次现场切换。

信号量

信号量是1965年由著名的荷兰计算机科学家Dijkstra提出的，其基本思路是使用一种新的变量类型，即信号量来记录当前可用资源的数量。

在信号量的具体实现上，有两种不同的方式。

（1）方式一：要求信号量的取值必须大于或等于0。如果信号量的值等于0，表示当前已没有可用的空闲资源；如果信号量的值大于0，则该值就代表了当前可用的空闲资源数量；

（2）方式二：信号量的取值可正可负。如果是正数或0，其含义与方式一是相同的；如果是负数，则它的绝对值就代表正在等待进入临界区的任务个数。

信号量是由操作系统来维护的，任务不能直接去修改它的值，只能通过初始化和两个标准原语（即P、V原语）来对它进行访问。在初始化时，可以指定一个非负整数，即空闲资源的总数。所谓的原语，通常由若干条语句组成，用来实现某个特定的操作，并通过一段不可分割或不可中断的程序来实现其功能。原语是操作系统内核的一个组成部分，必须在内核态下执行。原语的不可中断性是通过在其执行过程中关闭中断来实现的。

P、V原语作为操作系统内核代码的一部分，是一种不可分割的原子操作。它们在运行时，不会被时钟中断所打断。另外，在P、V原语中包含有任务的阻塞和唤醒机制，因此，当任务在等待进入临界区的时候，会被阻塞起来，而不会去浪费CPU时间。

P原语中的字母P，是荷兰语单词测试的首字母。它的主要功能是申请一个空闲的资源，把信号量的值减1。如果成功的话，就退出原语；如果失败的话，这个任务就会被阻塞起来。V原语当中的字母V，是荷兰语单词增加的首字母。它的主要功能是释放一个被占用的资源，把信号量的值加1，如果发现有被阻塞的任务，就从中选择一个把它唤醒。

采用信号量来实现任务之间的互斥，优点有两个：一是可以设置信号量的计数值，从而允许多个任务同时进入临界区；二是当一个任务暂时无法进入临界区时，它会被阻塞起来，从而让出CPU给其他的任务。

大多数嵌入式操作系统都提供了信号量的机制，用户可以通过函数调用的方式去使用。

更多复习资料
请登录电脑版软考在线 www.rkpass.cn

京B2-20210865 | 京ICP备2020040059号-5