并发进程详稿(12学时)

第 1 页引言：本章第一节首先介绍并发的概念和进程并发执行带来的问题，同时指出并发进程之间的关系(无关的并发进程和相关的并发进程)和判断进程是否相关的 Berstein 条件。特别对于相关的并发进程，可用互斥的方法解决进程间的竞争关系；用同步的方法解决进程间的合作关系。第二节中介绍实现互斥的软件方法和硬件机制。实现互斥的软件方法有Dekker 算法和 Pertenson 算法，也可通过禁止中断或采用特殊的硬件指令等硬件机制来支持互斥。第三节介绍用信号量和 PV 原语来实现进程的互斥和同步。在这一节中我们还将介绍一些进程同步和互斥的经典问题。第四节简单介绍管程的概念以及用管程来实现进程的同步和互斥。最后一节中我们将讨论在并发处理中通常需要解决的两个问题死锁和饥饿，并分析处理死锁的三种常用方法：预防、检测和避免。本章是操作系统课程的精华，也是学习的最大难点。 4.14.1 并发的基本原理并发的基本原理一、再论进程的并发性一、再论进程的并发性1.1. 顺序程序设计顺序程序设计传统的程序设计方法是顺序程序设计，即把一个程序设计成一个顺序执行的程序模块，不同程序也是按序执行的。程序执行不仅具有内部顺序性，也具有外部顺序性。首先程序中包含了用来实现某个算法的若干操作，当程序在处理器上执行时，只有前一个操作结束，才能开始后继操作，称为程序内部的顺序性。如果需要若干不同的程序来完成某个任务，则这些不同程序也将按调用次序严格有序执行，称为程序外部的顺序性。2.2. 顺序程序设计的特性顺序程序设计的特性(1) 执行的顺序性一个程序在处理器上执行是严格有序的，即每个操作必须在下一个操作开始之前结束。(2) 环境的封闭性由于程序是一个个顺序执行的，所以每个程序在执行时独占系统的全部资源，不会受到其他程序和外界因素的干扰。(3) 执行结果的确定性虽然程序执行过程中允许出现中断,但是中断不会引发程序的切换,所以对程序的最终结果没有影响，换言之，程序的执行结果与它的执行速率无关。(4) 计算过程的可再现性一个程序针对同一个数据集一次执行的结果，在下一次执行时会重现，即重复执行程序会获得相同的执行结果。第 2 页程序的顺序执行给程序的编制和调试带来很大方便，缺点是计算机系统的效率不高。3.3. 进程的并发执行进程的并发执行操作系统中引入并发程序设计技术后，程序的执行不再是顺序的，一个程序未执行完而另一个程序便已开始执行，程序外部的顺序性消失，程序与计算不再一一对应，所以在操作系统中引入进程这一概念来描述这种变化。(1) 进程的并发性进程的并发性是指一组进程的执行在时间上是重叠的，即一个进程执行的第一条指令是在另一个进程执行的最后一条指令完成前开始的。例如有两个进程 A 和 B，它们分别执行操作 a1,a2,a3 和 b1,b2,b3。这两个进程在单处理器上可以交叉执行，如执行序列为 a1,b1,a2,b2,a3,b3 或 a1,b1,a2,b2,b3,a3 等，称 A和 B 两个进程的执行是并发的。值得注意的是进程内部的顺序性并未消失，例如不可能出现 a1,b1,a3,b2,a2,b3 这样的执行序列。从宏观上看，并发性反映出一个时间段中有几个进程都处于运行还未运行结束的状态，且进程都在同一处理器上运行；从微观上看，任一时刻最多只有一个进程在处理器上执行。(2) 并发程序设计的优势可将一个程序分成若干个可同时执行的程序模块的方法称并发程序设计，每个程序模块和它在执行时所处理的数据就组成一个进程。采用并发程序设计可以充分发挥硬件的并行性，消除处理器和 I/O 设备的互等现象，提高系统效率。例如有一个程序不断地从输入设备读取一个字符数据(调用 input 过程)，再进行处理(执行 process 过程)，然后将结果写到磁带上(调用 output 过程)，可表示为：while(true)input();process();output();如果程序按照输入处理输出顺序执行，系统的效率是相当低的。如果把这个求解问题的程序分成三部分：while(true)input();send();while(true)receive();process();send();第 3 页while(true)receive();output();每一部分称为一个程序(子)模块，功能是：模块 1：循环执行，读入字符，将字符送缓冲区 1；模块 2：循环执行，处理缓冲区 1 中的字符，将计算结果送缓冲区 2；模块 3：循环执行，取出缓冲区 2 中的计算结果并写到磁带上。其中 send 和 receive 操作是程序模块之间的某种通信机制。从图中不难看出这三个程序模块能同时执行，在 t3 时刻输入 i3、处理 p2 和输出 o1可以并行工作，同样在 t4 时刻输入 i4、处理 p3 和输出 o2 也可以并行工作。由于中断和通道等硬件技术的出现的确可以使处理器和外部设备能并行工作，但是这些部件能并行工作仅仅意味着计算机有提高效率的可能性，只有通过采用并发程序设计技术才能充分发挥和利用机器部件的并行工作能力。4.4. 并发程序设计的特性并发程序设计的特性(1) 并发性进程的执行在时间上可以重叠，单处理器系统中可以并发执行；在多处理器环境中可以并行执行。(2) 共享性进程之间可以共享某些变量，通过引用这些共享变量就能互相交换信号，从而程序的运行环境不再是封闭的。(3) 制约性第 4 页进程并发执行或协作完成同一任务时，会产生相互制约关系，必须对它们并发执行的次序(即相对执行速率)加以协调。(4) 交互性由于进程共享一些变量，所以，一个程序的执行可能会影响其他程序的执行结果。因此，虽然程序自身能正确运行，但由于程序运行环境不再是封闭的，程序结果仍可能是不确定的，计算过程具有不可再现性。二、进程并发执行带来的问题二、进程并发执行带来的问题虽然并发程序设计或者说进程的并发执行可提高系统的工作效率，但是进程的并发执行会引发一系列的问题，从而给操作系统的设计和管理带来困难。第一章在分析操作系统的异步性的时候曾通过飞机订票问题来说明并发执行的进程可能会导致与时间有关的错误。这里再举一些由于进程并发执行而出现错误的例子：1.1. 一个简单的例子一个简单的例子下面过程显示了字符回显程序的基本步骤：void echo()chin=getchar();chout=chin;putchar(chout);每当用户单击一下键，从键盘获得的每个输入字符就保存在变量 chin 中，然后传送给变量 chout，并回送显示器。任何程序可以重复调用该过程，接受用户输入，并在用户的屏幕上显示输入的字符。现有进程 P1 和 P2 共享过程 echo，chin 作为全局变量，而 chout 是每个进程的局部变量。考虑下面的顺序：(1) 进程 P1 调用 echo 过程，并在 getchar 返回输入字符(假设字符 x)并存于 chin 后立即被中断，此时变量 chin 中保存输入字符 x。(2) 进程 P2 被激活并执行 echo 过程，输入的字符 y 覆盖变量 chin 中的值 x，然后在屏幕上显示单个字符 y。(3) 进程 P1 被恢复。此时 chin 中的值 x 被写覆盖，已经丢失，而 chin 中的值 y 被传递给chout 并显示出来。因此，第一个字符丢失，第二个字符被显示了两次，问题的本质在于中断的产生可能会导致进程切换，而全局变量的共享又充满了危险。在多处理器系统中，不仅在单个处理器上会出现上述问题，而且当两个进程同时执行第 5 页并且试图访问同一个全局变量时，也会引发问题。(1) 进程 P1 和 P2 分别在一个单独的处理器上执行，它们都调用了 echo 过程，chin 仍然是共享变量。(2) 下面事件的发生(同行事件表示同时发生的)：结果是输入到 P1 的字符在显示前被丢失，输入到 P2 的字符被显示在 P1 和 P2 中。2.2. 竞争条件竞争条件竞争条件发生在多个进程在读写数据时，其最终的结果依赖于多个进程的指令执行顺序。考虑这样一个简单的例子：两个进程 P3 和 P4 共享全局变量 b 和 c，并且初始值 b=1,c=2。在某一执行时刻，p3执行赋值语句 b=b+c，在另一执行时刻，p4 执行赋值语句 c=b+c。两个变量的最终值依赖于两个进程执行赋值语句的顺序。如果 p3 先执行，最终值 b=3,c=5。如果 p4 先执行，那么最终值 b=4,c=3。三、无关的并发进程三、无关的并发进程1.1. 并发进程之间的关系并发进程之间的关系一组并发执行的进程可能是无关的，也可能是交互的。(1) 无关并发进程无关的并发进程是指它们分别在不同的变量集合上操作。所以，一个进程执行与其他并发进程的进展无关，即一个并发进程不会改变另一个并发进程的变量值。(2) 交互并发进程交互的并发进程，由于共享某些变量，所以一个进程的执行可能会影响其他进程执行的结果，可以认为交互的并发进程之间具有制约关系。2.2. BernsteinBernstein 条件条件并发进程的无关性是指进程的执行与时间无关的一个充分条件。该条件在 1966 年首先由 Bernstein 提出，又称之为 Bernstein 条件。假设 R(Pi)=a1,a2,an表示程序 Pi 在执行期间引用的变量集；第 6 页W(Pi)=b1,b2,bn表示程序 Pi 在执行期间改变的变量集。只要两个进程各自的程序 P1 和 P2 满足 Berstein 条件引用变量集与改变变量集之交集为空，R(P1)W(P2)= R(P2)W(P1)= W(P1)W(P2)=则并发进程的执行与时间无关。【思考思考】下面的进程 P1 和 P2 中的语句是否可以并发执行(对各自结果不会造成影响)？x=y=1;进程 P1 进程 P2y=y+2; x=y+1; z=y+1; x=z+2;四、进程的交互四、进程的交互 基于进程相互之间知道对方是否存在的程度，可将进程的交互方式划分为竞争和合作(共享合作和通信合作)。1.1. 竞争进程竞争进程这是一些独立的进程，它们不会一起工作，彼此间也不知道对方的存在。尽管如此，由于这些进程共享了一套计算机系统资源，因此必然会发生多个进程竞争资源的问题。操作系统要协调好竞争进程对共享资源(尤其是临界资源)的争用。竞争进程间没有任何信息交换，但是一个进程的执行可能会影响到同其竞争资源的其他进程。特别如果两个进程都期望访问同一个资源，操作系统把这个资源分配给了一个进程，另一个就必须等待，被拒绝访问的进程的速度就会变慢。一种极端情况是，被阻塞进程永远不能访问这个资源，因此一直不能成功地终止。2.2. 竞争进程面临的控制问题竞争进程面临的控制问题(1) 互斥的要求系统中的某些资源如打印机、磁带机、卡片机，虽然它们可提供给多个进程使用，但在同一时间段内却只允许一个进程访问这些资源，即要求互相排斥地使用这些资源。当一个程序还在使用该资源时，其他欲访问该资源的进程必须等待，仅当占有者访问完毕并释放资源后，才允许另一个进程对该资源进行访问。一次仅允许一个进程使用的资源称临界资源，进程中访问临界资源的那部分代码称为一次仅允许一个进程使用的资源称临界资源，进程中访问临界资源的那部分代码称为程序的临界区程序的临界区。一次只允许有一个程序在执行临界区，这一点非常重要。例如在打印机的例子中，我们希望任何一个进程在打印整个文件时都拥有打印机的控制权，否则在打印结果总就会穿插着来自竞争进程的打印内容。只能采用互斥的方法来控制竞争进程对临界资源的使用，但互斥的实施又产生了两个额外的控制问题：死锁和饥饿。第 7 页(2) 死锁(deadlock)死锁是指这样一种情况：一组进程中，如果每个进程都获得了部分资源，还想要得到其他进程所占