程序设计语言原理复习-第13章 程序的并发性和进程交互原语

第章程序的并发性和进程交互原语13前面章节我们已多次提到并行（）命令和并发（）程序，但主要是讨论顺序程序parallel concurrent所谓顺序程序是指一个程序作业从起始到终了的每个作业步骤顺次地执行完毕程序员写程序时就默认有一台顺序执行的机器，为它排出先后执行的动作步（语句）然而，自然界发生的事，大多数是并行的只是我们在讨论之中把它孤立和顺序化这是为了早期计算机昂贵，一台机器只能顺序CPU地执行，自然是首先发展顺序计算在实时控制领域，即使在早期也无法顺序化例如，飞行姿态控制程序，每时每刻都要计算敌我双方飞机的速度、高度、方向才能决定控制措施再如，民航机票发售系统，各站点售票是同时进行的，既让乘客随意订座还不许卖重了这都要求多个计算同时平行地执行，并协调一致我们称这种程序为并发程序（）显然，并发的前题是并行（平行,）concurrent parallel然而，并发和并行的概念在不同文献上也少有出入本书把“并行”定义为程序可相关或不相关平行执行，有时仅指不相关的平行执行“并发”执行必然相关由于近年硬件成本大幅度下降网络计算快速发展，用多台机器，多个完成一个计算是极CPU普通的事因而原先人为顺序化的顺序计算就没有必要了而且今后为了利用信息资源，一上机就上网是应用计算机主流并发程序设计、并发语言将成为主流顺序程序倒成了并发的特例操作系统本身是一个高度并行的软件，它本身一般是某种高级顺序语言（如）扩充了一些支持C并发进程低级原语，加上汇编语言编写而成的在这个意义上，这些扩充了低级原语的语言就是并发高级语言其它更高层的通信机制是建立在这些低级原语上的模块（相当于该语言的库模块）语言的机制与特征并没有扩充，编译也没有大改动完全独立于操作系统，在高级语言内提供全套支持变形程序设计的并发，高级程序设计语言是因为它要编制机载、弹载的嵌入式程序这些程序从单板、单片开始，编制监控程序（小）Ada,

0.S连用应用程序这种语言并不多见因此，研究并发高级程序设计语言，勿宁说首先研究并发程序设计搞清了各种并发模型和通信机制再去看已有语言的扩充就很容易理解和实现了本章介绍并发程序设计的基本概念并发程序带来的问题和要解决的基本问题基于共享变量和基于消息传递的两类并发机制反映了不同物理模型，它们共同要解决的是对共享变量的互斥访问和进程间如何通信协调本章着重介绍概念和术语，是下章讨论各种并发机制的基础基本概念13J并行程序是同时执行两个或多个程序，在程序执行完之前必然有时间上的重叠我们知道,一个程序的一次执行叫做一个进程（）研究并发程序首先要了解进程及其相互作用process程序与进程源程序经编译、连接编辑成为可执行代码它们是可执行的“半成品”，可以作为用户文件寄存于外存可以作为库文件和系统文件一旦需要则调入内存，然后开始执行进程是个动态由于设置了多个变量，使用忙等待设计的同步并发程序，比较难读和理解，作正确性证明也麻烦再者，忙等待比较浪费处理时间，因为在自旋处理周期中完全可以干点别的什么最后，忙等待过于低级，程序员要从同步机制选取一直做到实现测试，设计起来比较麻烦且易出错信号灯2首先理解到忙等待的低级和设计麻烦，提出了完整的信号灯理论Dijkstra semaphores1968信号灯是一个非负整值变量在其上定义了两个操作取自荷兰语字头，即等待和So P,V wait示信操作发信号指示一个事件可以出现,操作延迟所在进程直至某个事件已经出现signal V P表达延迟的表示Ps:await s0do s:=s-1;//awaitVs:s:=s+1;操作的等待用原语表示，判断、设置信号量一般看作原子操作，一气呵成可用硬件复合指P令测试和设置实现信号灯变量当只有一个资源时取值｛｝就够了，此时称为二值信号灯TS s,0,1当有多个资源时初始化等于资源数，这时称通用或记数信号灯s信号灯可保证进程互斥且公平，如下例例以信号灯实现的两进程互斥13-4Program MUTEX_EXAMPLE;var mutex:Semaphore:=1;process Pl::loop〃入口协议Pmutex;临界段；〃出口协议Vmutex;的非临界段；Plend loop;end pl;process p2::loopP mutex;临界段；V mutex;的非临界段；P2end loop;end;end.由于均为原子动作，故可以保证互斥且无死锁和前述自旋锁对比，它清楚、简单、对称P,V由于用原语则不用忙等待在等待期间可干别的事它们至少在进程正文上是公平的CPU操作很容易扩大到个进程竞争一个临界段也可以将二值信号灯劈开分别实施同步警卫功P,V n能以下是生产者/消费者著名问题的同步解例生产者/消费者的同步与互斥13-5program PRODUCER_CONSUMER//任意类型var buf:TYPE;TYPE〃两信号变量初始化var empty:sem:=1,fulksem:=0;process PRODUCERJ]::loop产生一条消息PRODUCER[i]m;deposit:Pempty;〃存入消息m的三个操作buf:=m;Vfull;end loop;end;process CONSUMERloopfetch:Pfull;//从取出消息的〃buf mm:=buf;三条操作V empty,消费取出这条消息CONSUME R[j]m;end loop;end;end PRODUCERCONSUMER.本程序有个生产者，每位每次生产一条消息，只要空则存入，否则等待有个消费者，M bufN每位每次消费一条消息，只要中有消息、以标志则可进入临界段，取出资源上的信息buf fullbuf信号变量的类型为是定义的抽象数据类型fun,empty sem,当程序启动时个生产者和个消费者同时激活激活的微观次序由实现定M N将信号变量一分为二简化了传递方向称劈分二值信号灯S empty,full splitbinary semaphoreo这个算法保证了互斥，无死锁将操作扩充到多进程，多资源多个临界段也是很容易的例如，我们可实现个缓冲区P,V q的多生产、消费者问题其算法如下例多进程的互斥与同步解13-6program PROD_CONSvar buf[l...q],mi,mj:TYPE;的下标变量var front~0,rear:=0;//buf//辟分二值信号var empty:sem:=q,full:sem:=0,var mutexD:sem:=1,mutexF:semi=l;process PROD[i:l..M]::loop产生一条消息PROD[i]mideposti:Pempty;PmatexD;buf[rear]:=mi;rear:=rear modq+1;VmutexD;Vfall;end loop;end;process CONSloopfetch:Pfull;PmutexF;mj:=buffront;front:=front modq+1;V matexFV empty;消费消息CONS[j]mi;end loop;end;end PROD_CONS.的每个元素放一条消息、，它是一个消息队，装入的消息放在缓冲区尾消费的消息从缓buf buf[rear],冲区头中取两组劈分信号，协议中是两次操作一组劈分信号管进入临界段buf[front]P,V另一组劈分信号管开放的是头还是尾empty,full,mLIutexD,mutexFo选择互斥是更为复杂的同步机制不仅多进程，多资源，而且某进程只能选定使用某些资源用操作也可以实现选择互斥经典的例子是哲学家就餐问题P,V例五位哲学家就餐问题13-6一张圆桌坐了五位哲学家，如图所示桌上放有一大盆通芯粉，但只有五把叉子.而吃通芯13-2粉必须有两把叉子.一旦据有两把叉子的哲学家就可以吃,否则它只好利用等待的时间思考如果每人拿一把叉子等待其它人放下叉子，就产生死锁通芯粉当然是共享资源，但叉子是只有两个哲学家共享的资源每个哲学家的行为过程即为一进程第个进程只和第和个叉子有关故算法如下i ii+1program DINING_PHILO:var forks[

1..5J:sem:=5*1;process PHILOSOPHER[i:loopPforks[i];Pforks[i+1];吃通芯粉；Vforks[i|;V forks[i+1];思考问题；end loop;end;process PHILOSOPHER

[5]::loopPforks[l];Pforks

[5];吃通芯粉；Vforks[l];Vforks

[5];思考问题；end loop;end;end DINING-PHILO.图哲学家就餐问题示意图13-2以上以信号灯实现互斥同步均隐含使用了等待原语事实上多数分时处理的机器，单主机await多处理器的机器是用系统调用并行核或叫管理程序实现的进程创建就绪后将该进程的描述子入队，即就绪进程表，等待操作的完成这样，进程处于就绪或阻塞状态且未运行此descriptor P时操作的语义解释是P,VPs:if s=1then s:=0置进程于中等候else queue从中消除一进程，令调度程序执行它Vs:if queue!=empty thenqueueelse s:=1无忙等待的实现更通用，且可用以实现其它上层机制核的工作原理图如图它的主要职责13-1,是为进程分配处理器周期进程在它分配前是阻塞的当然核例程名，调用细节因各同步机制和具体机器不尽一致，但原理是一样的如果为多处理机或分布式系统写一个核，就要复杂一些，就要拿出一个处理器专用于维护就绪表并为其它处理器分配进程这样，就绪表的访问成了共享的，也要保证互斥于是在就绪表上用忙等待保证互斥在分布式处理机上，不仅有一个核管理的就绪表每个点上都得要有自己的核以维持本机的就绪表，进程从一个处理机迁移到另一个上，则置于另一核管理之下，情况就复杂多了基于通信的原语分布式或网络上由于没有共享主存，自旋锁、信号灯实现起来都不太方便上段最后已说明网络提供的通信设施是交换消息这样的系统只能由发送和接受消息实现进程message sendreceive交互基于消息的进程交互一般说来，效率比共享变量的分时或多处理器系统要低虽然年1973Hanson首先把它用于操作系统但直到九十年代这类机制的普及应用才成为可行消息是信息传递的单元，按的模型，信息源借助信道向信息目标发送消息信shannon channel道成了并发进程共享的资源信道是通信网的抽象，泛指进程间通信的路径信道由两个原语访问:当某进程向信道发送一消息，通信就开始了需要该消息的进程，从信道上接受获send,receive取这条消息数据流也随发送者传递到接受者同步也就自然实现了，即不发送没法接受,发送了必须接受那怕暂行存放不处理，否则丢失由于信道本身不能存储，变量只能存放在各个进程中，因而不能共享地访问，所以也用不着互斥机制由于只有所在进程能考察变量情况，条件同步编程与基于共享变量的大不相同程序也不一定非要在一个处理器上执行，可以分布在多个处理器上，分布式程序因而得名反过来，分布式程序却可在单主机或多路处理器的分时系统上执行此时把信道改成共享存储就可以了信道与进1程消息传递利用信道和两个原语可以实现不同的通信模式信道即信息数据传递的路径是网络的抽象在分布式网络中信道不同的组合可组成四类不同逻辑功能的进程•过滤器（）进程它是一种数据转移器，进程接受数据后按需要加工，然后传出，如同过filter滤器滤出需要的数据，故得名如果将一系列过滤器首尾相连则形成管道（）或称流水线信pipeline道每个进程独立激活，物理上可分布在网络各结点或多处理器的单主机上典型过滤器进程均设原语〈变量表〉＜源进程,receive from表达式_表＞＜目的进程,send vto管道信道在操作系统中是最常见的，它把每一个设备抽象为进程，终端一一打印机，即构CPU成运行一个程序的信道，三个进程均为过滤器当验明消息来源无误，接受原语将表达式表中的值“赋给”变量表•客户/服务器进程就分布式网络而言，它的拓扑是一个异质结点的图管道通信只是图上的一条路径即数据流通过管道跨越各进程然而就一般图而言，一个结点可以有多对一，一对一，一对多，多对多的数据流（进程交互）在实际网络应用中有一类进程即这种情况:客户/服务器，一个客户（）进程它要求一个或多个服务器（）进程为其服务，反过来一个服务器也可以为一到client server多个客户服务显而易见，一个发出服务要求，一个响应要求后，完成服务，回复应答通信是双向的客户/服务器每完成一次通信客户方是发送（请求）接收（应答）两次消息传递，服务器方相反是接受（请求）发送（应答）两次消息传递这里也有隐含先来先服务原则网络上的文件服务器就是非常典型的例子•对等（）进程另一类进程是既是客户又是服务器的一组对某进程共同完成（并行地）peer peer一个复杂计算例如，阵列计算中各结点上的进程都是它们作相似的部分计算既发消息，也peer,接受消息、，协作完成一计算非阵列式网络上的到的进程交互最能代表网络上通信的一Peer Peer般情况然而，由于算法复杂到目前还没有通用的解，是网络通信追求的最终目标（）两类通信模式2无论是哪种进程，通信既可按同步也可按异步实现，所谓同步即两进程都要执行到同步点直接交换数据所谓异步是两进程谁也不等谁按各自速度执行自己进程，就完成了数据通信事实上完全不等待是不可能的，一个进程执行到如果没有任何进程它只好等待（跳过语句再次reecive send,receive空循环就是忙等待，否则阻塞在的等待队中）与此相反，一个进程执行到它总可以把receive send,消息发出去不是直接发给接受者就是发向信道（哪怕没人接受）所以，判定是否异步只看含的进程是否阻塞，等待接受进程的到来send异步通信的实现，可以看作在某个进程中附带一无限大的邮箱（抽象说也是信道，缓冲时间差）发送者按自己进程执行，将一条条消息发到邮箱而接受者在自己合适的时候处理一条条消息各不相扰，犹如邮递员给居民投信，可以彼此不见面如果是服务器它就将结果消息投入邮箱回复到客户如果邮箱容量为零，即为同步通信，则非等不可，“见面”交换信息至于怎样激活、怎样等、见面后怎样分手，各种语言有不同的规定到下一章高层通信机制一节再介绍小结

13.5并行程序是两个或多个程序执行时，时间上有覆盖，并行程序间若共享数据或有数据传递,即它们是相关的，称并发程序•程序代码的一次执行叫一个进程研究程序的并行性即研究进程交互一个进程执行中可处于四种状态就绪、运行、阻塞、终止控制进程状态的操作是激活（创建进程并进入就绪态）触发（结束就绪进入运行态）、中断（结束运行进入阻塞态）程序设计语言以这些操作的组合提供原语并行程序的模式有四种单指令单数据流单指令多数据流多指令单数据流多SISD;SIMD;MISD;指令多数据流并发程序主要研究MIMD SIMD,MIMD•原子动作是不可再分成并行子部分的计算机动作它们粒度大小是相对的，一般以事件（程序的状态有了改变）来定义原子动作进程有三种类型独立进程；竞争进程；通信进程竞争资源和进程通信是并发程序研究的两大类问题•并发程序和顺序程序的差别在于依赖执行速度；计算结果不确定；产生死锁；得不到执行•并发程序的基本问题是活性（会不会死锁）公平性（会不会死等）、安全性（会不会出错）它们也是并发程序的基本性质•基于共享变量的进程交互的基本问题是对共享资源的互斥访问和竞争进程间的同步基于共享变量的进程交互的低级机制有自旋锁和信号灯•进程据有运行资源且处于运行中实现的等待称为忙等待简单自旋锁的忙等待只解决同步协调不解决互斥复杂自旋锁不利于编程•信号灯提供操作保留临界段，操作隐含延迟以调整同步是基于共享变量最基本的机制P,VP可在其上构造任何进程交互的通信机制•基于通信的进程可分为四类过滤器，接受消息加工后发送出去客户，发送要求服务的请求，得到已服务的应答服务器，接受服务请求、服务后给出应答等同，既是客户又是服务器，也是双向的过滤器•基于通信的原语是变量-表,源进程〉receivefromv表达式-表〉的进程,send vtoH进程原语匹配实现消息传递•异步消息传递，交互进程间均向信道发/收消息，彼此可不“见面”可借助公共邮箱（附在某进程上）实现•同步消息传递，信道邮箱容量为零，进程必须“见面”一般利用原语将快进程延迟到同步点实现习题

13.1试述顺序、并行、并发程序之同异顺序性是指一个程序作业从开始到终止的每个作业步骤，顺序地执行完毕，并发程序是指多个计算同时平行的执行，并协调一致并发的前提是并行，并行是指程序可相关或不相关串行执行并行程序是两个或多个程序执行时，时间上有覆盖，并行程序间若共享数据或者有数据传递，即它们是相关的，称为并发程序并发程序与顺序程序之间的差别在于依赖执行速度；计算结果确定，产生死锁；得不到执行

13.2试述并发程序的优点、缺点、难点优点有利于多机，多处理器、分布和网络等，提高效率；缺点依赖执行速度；计算结果不确定，产生死锁；得不到执行难点安全性，活性，公平性

13.3客观世界问题是并发的且能用顺序程序模拟实现，什么情况下用并发程序什么情况下用顺序程序，尽你可能讲出理由

13.4何谓同步进程交互是否两进程一定要到同步点？

13.5怎样判定一个程序是异步通信

13.6在有分时的机器上编一程序实现自旋锁程序

13.7在有分时的机器上编一程序实现信号灯程序语言无此功能，可利用操作系统命令

13.8编一程序，模拟实现五位哲学家就餐问题，就餐人次或打出死锁信息语言不限,可利用操1000作系统命令

13.9分布式网络上进程可分哪四类，能举出这以外的进程型式吗？举出三个实际问题说明它们是哪种进程型式解最好

13.10假定有一个原语插入程序后可拉出一新进程，新进程共享原有变量，以下创建的start C,start变量不共享将以下矩阵求和的顺序程序改成并发程序，使计算时间尽可能的少type Matrixis arayl..n,l..n ofFloat;procedure adda,b:in Macrix;sum:out Matrixisbeginfor iin l..n loopforj inl..n loopsumij:=aij+bi,j;end loop;end loop;end;在你的设计中有多少个进程并发执行？什么环境下本并发程序比原顺序程序快？什么情况下难于判定？

13.11写出一死锁程序语言不限说明它真是死锁的

13.12查阅文献，写出信号灯的不变式概念，即程序以一组数据的一次执行我们先看看进程在内存中的执行状态及实现过程就单个进程而言，它有四种状态•就绪可执行代码装入内存立即可运行ready执行进程•运行running停止本进程执行，随时可恢复执行停止，且不可恢复执行•阻塞blocked•终止terminated除了这四种状态而外，控制进程的逻辑操作是激活触发activating和中断所谓激活是创建一个进程并使之进入就绪或立即运行状态所谓触发是使trigging interrant就绪或阻塞状态转入运行态所谓中断即使运行的进程转入阻塞或终止态然而，这些逻辑操作是机器指令层次上的，在语言层次上借助于各种原语或约定实现所谓原语是程序语言中定义primitive的例程名例如,早期的操作系统低级原语和就是用来控制进程状态的一个进程调用fork quitfork例程，则中断本进程创建新的子进程并执行之一个进程调用将终止本进程再如，qait,cobegin-coend或命令，并发程序的开始执行，用某种约定自动激活各个进程，如主控程序开始所有任par-end Ada务均激活一个进程终止则自动触发阻塞的父进程使之执行在更低的实现层次上中断分为外部中断和内部中断由外部触发和本进程触发触发中断后,调用中断处理器例程，再调用原语例程，并将原语例程要求创建或终止的例程提交调interrupt handler度器例程，完成进程控制其控制流示意图如下图进程执行控制流13-1我们把一个进程执行中再次创建的进程，称为子进程一个进程可多次创建子进程，一次可创建多个子进程子进程还可以创建子进程如果被创建的子进程不分配一套资源则称线程，例如，多机上主进程将大型科学计算并行分配到各且共享同一内存如果分配资源，如一般程序进CPU CPU,入打印语句，为此要分配打印机、驱动程序资源，则称子进程并行程序的模式

13.132进程是程序执行的控制流，众所周知，代码执行要加工数据，与进程执行同时存在的还有一个数据流根据的分类法Flynn一组可执行代码装入一个机器内存后，以一个一组数据执行一次它属于执行•CPU,SISD模式即单指令流单数据流的简写物理上对应为单处理器的顺序程序一组可执行代码装入后，可以依次执行多个进程，它属于单指令流多数据流对应•SIMD,为单机多处理器的主机或单的分时系统、阵列机组CPU在多机或多处理器上各有自己的可执行代码协同完成一组数据的计算，是多指令•MISD流单数据流系统对应为分布数据流机则为多指令流多数据流系统，对应为一般分布式系统有多个不同的处理机，•MIMD运行各不相同的进程）局域网和广域网就属于此列如果网上协同运行一个程序作业，则为以系统实现的并发程序MIMD这四种模式包括了单机单处理器，单机多处理器，同型多机多处理器（阵列机）和分布式多机多处理器（异质机联网）的各种物理实现一般并发系统不多用，并发程序主要在MISD SIMD,MIMD上实现在实现多机协作计算时又可以分为两类共享存储和分布式存储共享存储多用于同MIMD类多的单机上，所有处理的进程都共享公共的数据这样，各进程间因数据共享而紧密耦CPU CPU合进程间的关系最初是主/奴（master/slaver）式，即OS的核只执行某个，主，处理器（进程），它统管共享数据并派遣任务到各，奴，处理器的进程优点是设计控制简单，缺点是主进程易成瓶颈当今最流行的是对称多处理器，即的核可以执行任何处理器，每一处理器都是自调度OS（self-scheduling）的，即从待执行进程表中取出一个执行它也派送子进程给其他处理器，也接收其它处理器发出来的子进程，故称对称多处理器SMP并行处理器谱系如图13-2图并行处理器谱系

13.2由于分布式存储是松耦合的计算机群体，它对应为多计算机的簇（cluster）,和一组计算机的集合不同之处在于它们各自的存储是被大家共享的，它们互连，每个计算机只是整个”计算机中的一个节点，是今后高性能、可伸缩、高可靠性计算机的发展方向线程与进程

13.143早期计算机一个进程就是一个执行的线索，它可以和其它进程交替执行，即又开始另一线索执行一个线索是断断续续的（冻结、就绪、运行、终止态等），完全由调遣一个进程可以看作是os派送的单元（）此外，进程执行占有资源（数据、设备、的时间片），所OS Unit of dispatchingCUPo以进程又可以看作资源拥有单元（）后来发现，这两种单元属性是相互独Unitofresource ownership立的在一个资源拥有单元之下可以派生出多个派送单元，即多线执行它们同样可以交互，这就是线程线程是共享资源的轻量级进程（）它也是有线程执行状态，也有其静态存储lightweight process,和局部变量传统的支持单线程的计算模式单用户的和多用户的就是例子，即使OS MS-DOS UNIXUNIX是多线程交互，每一进程之中只有一线程如图左侧图示右侧上图，一个进程多个线程对应13-3为虚机的计算模式而当今所有均发展为右下角的多进程和多线程的计算模式Java OS正是由于线程具有进程的所有派送特性当不涉及资源派送时，线程交互和进程交互是一样的下文讨论只谈进程交互原子动作

13.154并发和抽象一样可以在不同层次研究它一个数据占据位，我们如要拷贝它，可以从第一位32拷贝到第位也可以同时拷贝位（在字位级并发）一个表达式有若干项，每项同时计算最后3232汇总求值（子表达式级并发）同样并发可以在语句级，程序块级，程序单元级，模块级…在级以下则认为是原子的，不再分成子部分并发执行原子动作是一次“立即”执行完的“顺序”动作至于是否真正不再分就不一定了例如，一般顺序程序的输入/出进程和主进程都是并发执行实现的如原子动作定义在程序级上，它们也是“立即、顺序”地执行的并发的讨论则在此级以上原子动作在进程内完成，一个进程可以有多个原子动作（但不得有半个）在高级语言层次上，原子动作一般定义在语句级的事件（）上所谓事件，是本程序表示的event状态有了变化例如，执行了赋值语句，作了初始化、调用、终止…当然，事件也是相对的，一个语句对数据的加工可以是一个事件，右干语句的一个循环，也可以是一个事件例的多任务13-1PL/1的并发进程是任务它可以定义语句级的事件是一个进程，它并行执行进程，PL/1TASK,P Q则进程的正文可以写PDECLARE XEVENT*（）（）激活CALL QAPT TASKX//Q事件变量的一次取值表示一事件，它可取值（相当于）和X IN_EXCEPTION trueTERMINATED（相当于）当进程执行到时激活任务实参表和的形参表匹配合,进程和false PCALL Q,APT QQ进程并行执行事件变量调整两进程的同步变量是共享的P XX P,Q进程交互

13.165并发程序主要是研究进程之间的关系所谓交互即两进程有数据或操作通信如甲进程向乙进程发一条消息送给它数据，或触发乙进程中另一操作，这叫直接通信如果甲进程据有某资源改变了该资源中的数据，以后乙进程也据有该资源，这些改变了的数据对乙进程有了影响，这是共享数据的间接通信一般说来，并行进程有三种类型独立进程两进程并行但不相关1设进程为事件序列，若有两并行进程，可表达为其中:C,K CII KC={Cl,C2・・・Cn}K={K1,K2,-Km}独立进程是两进程内任何事件的执行都不依赖对方因此与进程执行速度无关，执行Ci,Kj CllK时在时间上可任意复盖，也可以按或或秩序任意交错执行，均C;K K;C{C1,C2,K,C3,K2…Km…Cn}能得到正确结果竞争进程两进程竞争同一资源2设是两竞争资源的进程，事件要使用同一资源则必须保证的互斥访问C,K Ci,Kj rCi,Kj matualexclusion,即两访问事件时间上没有复盖，同一时间只有一个事件据有资源r,按Ci；Kj或Kj;Ci次序执行均可我们把据有并加工资源的代码单划出来，叫做临界段一般说来，这段Critical section代码是同一个，所以中有也有显然两次执行，谁先谁后对各自进程计算结果是不Ci CS,Kj CSCS一样的因而结果不确定如果推广到多个进程竞争同一资源，情况更难预料因为各进程输CIIK入的数据只有运行时才知道，因而，进入临界段的时间不确定此外，为了保证互斥则各进程均设进出临界段的协议竞争进程一般形式是Q loopK:loop入口协议入口协议临界段临界段出口协议出口协议非临界段非临界段end loopend loop入口协议一般是按所设共享变量多为布尔型判断能否进入，出口协议则改置正确值为确保进程的确定性，利用共享变量“通信”协调通信进程两进程有协议的信息交换3设定义如前,必须先于要用到的结果的执行，即其它事件先后无所谓，一定要C,K CiKjKj Ci保证的执行顺序对于多个进程则有如和的管道命令Ci,Kj UNIXDOSCl IC2I•••I Cn规定事件先后它是通信进程的一种实现通信的机制有许多种同步的、异步的；单向的,双向的；定向的，广播的这与环境提供的运行机制和并发语言设计需求有关也正是程序并发性要研究的问题我们这里只给出初步概念•同步通信指两进程进度各不相同，但必须同步到达通信点注意不一定同时，synchronous同时是实时程序的概念若一方未到，另一方等待，直至完成信息交换交换后各自执行realtime各自进程则为单向同步通信如果交换后,发送方一直等待接受方执行的结果，拿回结果后再各自执行自己的进程为双向同步通信•异步通信一般要借助相当大的邮箱两进程以各自速度执行，发送方有了asynchronous信息投入邮箱，并继续执行自己进程接受方在认为合适时从邮箱获取信息一般不竞争邮箱且为单向通信，当然也可做成双向的•定向/广播式通信所谓定向是发送方指明接受方而广播式通信发送方只向公共信道发送信息，任何共享该信道的成员均可接受，所以是异步通信、单向的并发程序带来的问题

13.2一般说来，顺序程序和并行程序，与程序执行的速度无关，软件制售商在任何速度的机器开发出的商品，可以到其它速度的机器上运行而不影响其结果并发程序可不这样，因而，并发程序是比较难开发，测试和移植的我们先讨论它带来的新问题速度依赖1并发程序执行结果，取决于顺序成分进程执行的相对速度对于并发且有实时要求的程realtime序，执行结果还取决于绝对速度竞争进程最为明显的，例如，一个进程对资源中的变量求平方；另一进程是对作加一操作r xx结果值可能是后者快、前者慢或前者快后者慢显然，速度依赖导致结果不确定即x+l2x2+l使是速度相同的多处理机上，输入/出设备速度有了小挠动也会影响结果CPU并发程序调整相对速度的办法是延迟快进程把进程挂起来进入悬置态待到指定条件满足才唤醒该进程其基本原语是表达式〉〈语句进程〉awaitv doI进程执行到本句，测试表达式不满足则不作以后的操作即用原语实现条件同步表do await达式即条件输入值依赖2同一并发程序两组数据输入可能会有很大差别因为若有一个判断因值不同跳过一段程序跳过某个进程则会打乱原有速度依赖关系使执行顺序难以预测使并发程序难于设计、测试、修改，就要更多地依赖软件工程技术，加强文档管理不确定性3顺序程序两次同样值的测试，一般情况下都是一致的即所说的再现并发程序因上述原因往往没有确定的结果值对于有副作用的函数或表达式这种先后次序的差异影响则更大所以，软件工程对副作用比较谨慎，并发程序是其原因之一正是由于并发程序的不确定性某一系统上测试通过的并发程序到另一系统上通不过一组输入通过另一组数据通不过这是常有的事即使是同一套系统、同一语言处理器，同样一组输入，有时结果也不一样因为这一系统不单运行这一并发程序，别的作业也会对程序干挠只有在完全一致的条件下测试结果才可以再现在个别临界值的情况下，出现间歇再现，所以，并行程序的测试需要高超的技术死锁4deadlock死锁是一种状态，由于进程对资源有互不相兼容的耍求而使进程无法进展表现为•受到排斥进程永远访问不到所需资源•循环等待进程资源分配链形成一封闭回路它虽无明显把持，但对资源要求通过一组进程最后还是回到自己，不改为先释放已据资源，只能死锁•无占先进程无法放弃所占的、其它进程需要的资源所谓占先，只要所据nopreemption资源的进程未处于使用状态，另一优先级高的进程有了要求，则此资源被后者占去•把持相互以占有对方资源为放弃已占资源的先决条件wait andhold解决死锁的方法到目前为止还无法保证不出现死锁状态即使采用无死锁的通信和同步机制因为意想不到的条件出了错也会产生死锁解决的方法是•利用工具作静态死锁检测，可以避免或减少死锁出现的可能，事前防止或事前，让进程同时提出所有需要的资源，消除把持条件，或强行给资源排序，按此顺序满足要求，消除循环等待条件•或事前，为调度程序声明最大的资源需求少竞争资源死锁可能也小好的调度程序资源稍大即可避免或少出死锁一旦出现，最笨的办法是重新启动，试换数据，找出原因改正之这是事后重试解决•一旦出现，找出死锁地点，夭折某些事件或进程，自动从死锁状态恢复显然夭折的损失要求最小为此，设置检测点，一段一段倒转查找，直至段分得最小，夭折这个最小段rollback这对实时程序仍不可取死等5starvation相互竞争的进程如果都满足进入某一资源条件，一般采用排队的先来先服务原则相对最公平，但有的进程占用一种资源时间过长，致使其它资源长期闲置适当地让它等待可以解放很多占时少而重要的进程，这样更公平于是，除了先来先服务而外，在调度例程中约定或在条件中加入优先级表来达到此目的调度程序则按此优先级和先来后到统一调度如果优先级不当就会造成某些进程永远处于阻塞态，死等但不是死锁死等是不公平调度引起的，解决的办法是在改变某些进程的优先级，在公平性和合理性上作某种折衷并发程序的性质

13.3安全性和活性是一般程序均有的性质程序属性所谓安全性是程序在执行期间safety liveness不会出现异常的结果对于顺序程序指其最终状态是正确的所谓活性是程序能按预期完成它的工作对于顺序程序指程序能正常终止对于并发程序不仅如此还增加了新解释并发程序的安全性还要保证共享变量的互斥访问和无死锁出现活性指每个进程能得到它所要求的服务；或进程总能进入临界段；或送出的消息总能到达目的进程，活性深深受到执行机构调度策略的影响正因为如此，公平性也是并发程序重要性质之一所谓公平是指在有限进展的假设下没fairness有一个进程处于死等状态调度策略如能保证每个无条件的原子功能均能执行则称无条件公平性在具有条件原子动作时，若条件原子动作能执行并依然保持无条件公平性，则为弱公平性条件原子动作一定能执行，则为强公平性低级并发机制和并发原语

13.4无论程序设计语言上层采取何种机制实现程序的并发，最底层不外乎创建进程装入内存、初始化使之就绪；起动执行；阻塞或叫冻结；停止执行；阻塞父进程创建子进程；撤销进程等六种操作这六种操作更低层的实现是机器指令例如，停止和阻塞则利用中断陷井在机器指令中填trap,入陷井地址码利用开关指令从一个进程跳到另一个进程原语是包含这些底层指令的例程由于支持上层不同的并发机制，原语为了表述方便不同语言原语的差别在于所选组合指令的不同例如fork/multifork分股创建多个子进程并执行:quit/join合股新创进程回到原进程f waite等待为真进入临界段操作e PIsignale示信为真临界段可执行,操作e V•sleep value满足使所在进程阻塞value-wakeupvalue满足使所在进程唤醒恢复执行valuecobegin siII s2II•••II sncoend开始多个进程并发执行si…sncoroutine N指定协例程•resumeM No,sendExp to***转入协例程M■receivedV from---将表达式值送至…进程接受来自…消息，值由变量传入V基于共享变量的同步机制1341如前所述，并发程序中进程交互分两大类，一为基于共享变量，一为基于消息传递本小节先介绍基于共享变量的同步机制我们把加工进程共享变量的一组语句叫做临界段竞争进程竞争进入临界段一critical section旦进入就独享共享变量资源从安全性而言，这是必须的为了竞争进程互斥地访问共享变量最简单的办法是另设一公共变量指示是否已有进程进入临界段为此，早期的并发程序设置入口协议和出口协议在协议中设置、判明指示变量的值，以求保护临界段一个时间只有一个进程进入，一般形式见那么不能进入的进程就只好跳到循环末端，再开始一轮循环测试直至用完此资源的进

13.

1.42程在其出口协议中改变了指示变量的值，它才能进入该进程据有所有足以运行的资源占有内存，得到的执行周而复始地测试，实质上是在等待进入临界段我们把这种等待称为忙等待CPU busywait忙等待1设我们把指示变量叫做锁，每次测试临界段是否锁定竞争进程以测定进入条件锁保lock持协调地进入临界段，我们说它在语义上保证了条件同步锁就是条件，协调就是同步请注意，此时未设同步原语程度员也无法阻塞停止某个进程如果有多个进程竞争进入临界段，则每个进程都要轮流测试锁这就是著名的自旋锁其算法如下例spin lock,请注意，以下给出的算法描述语言，类不是可运行的某种语言的简化pascaLAda,例自旋锁13-2program SPIN_LOCK:var Lock:=false;process Pl::loopwhen not lock do〃条件同步lock:=true;〃入口协议临界段；〃出口协议lock:=false;的非临界段；Pl end do;end loop;end p1;process P2::loopwhen notlock dolock:=true;临界段；look:=false;的非临界段;P2enddo;end loop;end P2;process pnendSPIN LOCK其中为共享指示变量本程序运行时每个进程同时启动每一进程执行进入后首先查lock loop只要有一个进程（设）进入临界段工作，它把改成其它进程不断测试，均不满notlockP1lock true足，跳到循环末端，周而复始再测直至在临界段工作完将改成则其它任何第一个测试P1lock false,为的进程即可进入临界段同样，其余进程一直测试，均不满足只好等待false忙等待在实现条件同步上是比较方便的但不能保证互斥对于分时系统竞争进程有个时间差还好一点，如果在多处理器的条件下，进程严格同时到达，对资源（临界段的加工对象）的竞争变成对指示变量查询和更改的竞争要取决于操作系统对公用主存储器的存取访问的排序如果某进程进入循环且正在更新为期间，第二个进程又访问了（为）那么它也进入临界段互斥lock truelock false,得不到保证为此，寻找以忙等待实现互斥同步的算法，从年到年有许多名家（如、6581Dijkstra、等）上百篇论文，最后的算法（）获得Dekker KnuthdeBruijn EisenbergPeterson peterson1981满意的解算法如下例忙等待实现互斥访问13-3program MUTUAL_EXCLUSION〃或赋初值Var enter1:Boolean:=false;enter2:Boolean:=false;turn:String:=Pl”“P2”〃以下三行入口协议process Pl::loop enterl:=true;；跳至循环末端临界段；turn:=“P2”while enter2and turn=P2do skip;//enter2:=false;〃出口协议的非临界段；Pl end loop;end;；临界段；process P2::loop enter2:=true;turn:=Pl”while enterland turn=Pl”do skip;enterl:=false;的非临界段;p2endloop;end;end.这个算法依然是忙等待，但用三个变量代替例中的变量其作用是enterl,enter2turn13-2lock保证互斥，即使进入时，更新了）只要有一点点时间差就可保证互斥除非绝对一P1while P2enter致（此时都在上反复测试，谁也进不了临界段形成死等）因此一般情况下会保证正常互斥while这个算法可保证无死锁且公平任何一个想进入临界段的进程最终都可进入*就是活性所要求保证的有限进展的假设即若同步机制是公平的，则没有一个进程在等待无限长时间才能满足的条件这个算法很容易扩充到多个进程并给出互斥、无死锁、公平性的操作证明Peterson Dijkstra1981年也给出公理证明。