《研究生课程_程序语言设计原理教程_第13章.ppt》由会员分享，可在线阅读，更多相关《研究生课程_程序语言设计原理教程_第13章.ppt（27页珍藏版）》请在三一办公上搜索。
1、第13章 程序的并发性和进程交互原语,13.1 基本概念程序与进程一个程序的一次执行叫做一个进程(process)就绪ready 可执行代码装入内存立即可运行运行running 执行进程阻塞blocked 停止本进程执行,随时可恢复执行终止terminated 停止,且不可恢复执行激活：创建一个进程并使之进入就绪或立即运行状态触发：使就绪或阻塞状态转入运行态中断：使运行的进程转入阻塞或终止态原语：程序语言中定义的例程名线程：创建子进程不另分配资源子进程：一个进程执行中再次创建的进程,线程与进程计算模式及分类线程是共享资源的轻量级进程（lightweight process）,它也有线程执行状态
2、，也有其静态存储和局部变量。,MS-DOS,Java,UNIX,Windows NTSolarisMachOS/2,原子动作,原子动作是一次“立即”执行完的“顺序”动作。至于是否真正不再分就不一定了。原子动作一般定义在语句级的事件(event)上事件是本程序表示的状态有了变化例：PL/1的多任务 PL/1的并发进程是任务TASK,它可以定义语句级的事件。P是一个进程,它并行执行Q进程,则P进程的正文可以写:DECLARE X EVENT:CALL Q(APT)TASK(X)/激活Q,进程交互(1)独立进程 两进程并行但不相关 设进程为事件序列,若有C,K两并行进程,可表达为CK.其中:C=C1
3、,C2Cn K=K1,K2,Km 独立进程是两进程内任何事件Ci,Kj的执行都不依赖对方(2)竞争进程 两进程竞争同一资源 临界段(Critical section)：据有并加工资源的代码段 竞争进程一般形式是:C:loop K:loop 入口协议 入口协议 临界段 临界段 出口协议 出口协议 非临界段 非临界段 end loop end loop 入口协议一般是按所设共享变量判断能否进入,出口协议则改置 正确值.为确保进程的确定性,利用共享变量“通信”协调,(3)通信进程 两进程有协议的信息交换设C,K定义如前,Ci必须先于Kj(Kj要用到Ci的结果)的执行,即其它事件先后无所谓,一定要保证
4、Ci,Kj的执行顺序.同步(synchronous)通信 指两进程进度各不相同,但必须同步到达通信点.若一方未到,另一方等待,直至完成信息交换.交换后各自执行各自进程则为单向同步通信.如果交换后,发送方一直等待接受方执行的结果,拿回结果后再各自执行自己的进程为双向同步通信。异步(asynchronous)通信 一般要借助相当大的邮箱.两进程以各自速度执行,发送方有了信息投入邮箱,并继续执行自己进程.接受方在认为合适时从邮箱获取信息.一般不竞争邮箱且为单向通信,当然也可做成双向的。定向/广播式通信 所谓定向是发送方指明接受方.而广播式通信发送方只向公共信道发送信息,任何共享该信道的成员均可接受,
5、所以是异步通信、单向的.,13.2 并发程序带来的问题(1)速度依赖 并发程序执行结果,取决于顺序成分进程执行的相对速度.对于并发且有实时(real time)要求的程序,执行结果还取决于绝对速度.并发程序调整相对速度的办法是延迟快进程.把进程挂起来(进入悬置态)待到指定条件满足才唤醒该进程.其基本原语是:await do(2)输入值依赖 同一并发程序两组数据输入可能会有很大差别(3)不确定性 顺序程序两次同样值的测试,一般情况下都是一致的.即所说的再现.并发程序因上述原因往往没有确定的结果值.对于有副作用的函数或表达式这种先后次序的差异影响则更大,(4)死锁（deadlock）是一种状态,由
6、于进程对资源有互不相兼容的要求而使进程无法进展.表现为:受到排斥 进程永远访问不到所需资源循环等待 进程资源分配链形成一封闭回路无占先(no preemption)进程无法放弃所占的、其它进程需要的资源.所谓占先,只要所据资源的进程未处于使用状态,另一优先级高的进程有了要求,则此资源被后者占去把持(wait and hold)相互以占有对方资源为放弃已占资源的先决条件 解决死锁的方法:利用工具作静态死锁检测,可以避免或减少死锁出现的可能或事前,让进程同时提出所有需要的资源,消除把持条件,或强行给资源排序,按此顺序满足要求,消除循环等待条件或事前,为调度程序声明最大的资源需求一旦出现,最笨的 办
7、法是重新启动,试换数据,找出原因改正之。事后重试解决一旦出现,找出死锁地点,夭折某些事件或进程或设置检测点,(5)死等（starvation）相互竞争的进程如果都满足进入某一资源条件,一般采用排队的先来先服务原则。相对最公平,但有的进程占用一种资源时间过长,致使其它资源长期闲置。适当地让它等待可以解放很多占时少而重要的进程,这样更公平。于是,除了先来先服务而外,在调度例程中约定或在条件中加入优先级表来达到此目的。调度程序则按此优先级和先来后到统一调度。如果优先级不当就会造成某些进程永远处于阻塞态,死等(但不是死锁)。死等是不公平调度引起的。解决的办法是在改变某些进程的优先级,在公平性和合理性上
8、作某种折衷,13.3 并发程序的性质安全性(safety)是程序在执行期间不会出现异常的结果.对于顺序程序指其最终状态是正确的.对于并发程序指保证共享变量的互斥访问和无死锁出现活性(liveness)是程序能按预期完成它的工作.对于顺序程序指程序能正常终止.对于并发程序指每个进程能得到它所要求的服务;或进程总能进入临界段;或送出的消息总能到达目的进程,活性深深受到执行机构调度策略的影响公平性(fairness)指在有限进展的假设下没有一个进程处于死等状态.无条件公平性:调度策略如能保证每个无条件的原子功能均能执行 弱公平性:在具有条件原子动作时,若条件原子动作能执行并依然 保持无条件公平性,则
9、为弱公平性 强公平性:条件原子动作一定能执行,则为强公平性,13.4 低级并发机制和并发原语 无论程序设计语言上层采取何种机制实现程序的并发,最底层不外乎创建进程(装入内存、初始化使之就绪)；起动（或恢复）执行；阻塞(或叫冻结)；停止执行；阻塞父进程创建子进程；撤销进程等六种操作。这六种操作更低层的实现是机器指令 原语（premitive)是包含这些底层指令的例程。由于支持上层不同的并发机制，原语为了表述方便不同语言原语的差别在于所选组合指令的不同,fork/multifork 分股创建多个子进程并执行quit/join 合股新创进程回到原进程wait(e)等待e为真执行本进程signal(e
10、)示信e为真可切换至下一进程sleep(value)若value表达式满足,使所在进程阻塞wakeup(value)若value表达式满足,使所在进程唤醒(恢复执行)cobegin s1s2sn coend 开始多个进程s1sn并发执行coroutine N 指定协例程NresumeM 转入协例程Msend(Exp)to 将表达式值送至进程received(V)from 接受来自进程的消息,值由变量V传入,例如：,基于共享变量的同步机制(1)忙等待(busy wait)设我们把指示变量叫做lock(锁),每次测试临界段是否锁定。竞争进程以测定进入条件(锁)保持协调地进入临界段,我们说它在语义上
11、保证了条件同步。锁就是条件,协调就是同步 请注意,此时未设同步原语。程度员也无法阻塞停止某个进程。如果有多个进程竞争进入临界段,则每个进程都要轮流测试锁。这就是著名的自旋锁(spin lock),其算法如下:,program SPINLOCK:var Lock:=false;process P1:loop when not lock do 条件同步 lock:=true;入口协议 临界段;lock:=false;出口协议 P1的非临界段;end do;end loop;end p1;process pn:end SPINLOCK,process P2:loop when not lock do
12、 lock:=true;临界段;look:=false;P2的非临界段;end do;end loop;end P2;,上述算法如果在多处理器的条件下,进程严格同时到达,对资源的竞争变成对指示变量查询和更改的竞争，要取决于操作系统对公用主存储器的存取访问的排序。如果某进程进入循环且正在更新lock为true期间,第二个进程又访问了lock(为false),那么它也进入临界段。互斥得不到保证。为此,寻找以忙等待实现互斥同步的算法,从65年到81年有许多名家写了上百篇论文,最后peterson的算法(1981)获得满意的解。算法如下:,program MUTUALEXCLUSION Var ent
13、er1:Boolean:=false;enter2:Boolean:=false;turn:String:=“P1”;或赋初值“P2”process P1:loop enter1:=true;以下三行入口协议 turn:=“P2”;while enter2 and turn=“P2”do skip;跳至循环末端 临界段;enter2:=false;出口协议 P1的非临界段;end loop;end;end.,process P2:loop enter2:=true;turn:=“P1”;while enter1 and turn=“P1”do skip;临界段;enter1:=false;p2
14、的非临界段;end loop;end;,(2)信号灯 Dijkstra 首先理解到忙等待的低级和设计麻烦,提出了完整的信号灯(semaphores)理论(1968)。信号灯是一个非负整值变量 s。在其上定义了两个操作P,V(取自荷兰语字头,即wait（等待）和signal（示信）。V操作发信号指示一个事件可以出现,P操作延迟所在进程直至某个事件已经出现:P(s):await s0 do s:=s-1;await 表达延迟的原语 V(s):s:=s+1;,Program MUTEXEXAMPLE;var mutex:Semaphore:=1;process P1:loop P(mutex);入口
15、协议 临界段;V(mutex);出口协议 P1的非临界段;end loop;end p1;process p2:loop P(mutex);临界段;V(mutex);P2的非临界段;end loop;end;end.,例以信号灯实现的两进程互斥,信号灯变量s,当只有一个资源时取值0,1就够了,此时称为二值信号灯。P,V操作很容易扩大到n个进程竞争一个临界段。也可以将二值信号灯劈开分别实施同步警卫功能。以下是生产者/消费者著名问题的同步解。,program PRODUCERCONSUMER var buf:TYPE;任意类型TYPE var empty:sem:=1,full:sem:=0;两信
16、号变量初始化 process PRODUCER i:1.J:loop PRODUCERi 产生一条消息m;deposit:P(empty);存入消息m的三个操作 buf:=m;V(full);end loop;end;end PRODUCERCONSUMER.,process CONSUMER j:1.N:loop fetch:P(full);从buf取出消息m的三条操作 m:=buf;V(empty)；CONSUME Rj取出这条消息m;end loop;end;,将信号变量s一分为二(empty,full)简化了传递方向。称劈分二值信号灯(split binary semaphore).这
17、个算法保证了互斥,无死锁。将P,V操作扩充到多进程,多资源(多个临界段)也是很容易的。例如,我们可实现q个缓冲区的多生产、消费者问题。其算法如下:,program PRODCONS var buf 1.q,mi,mj:TYPE;var front:=0,rear:=0;buf 的下标变量 var empty:sem:=q,full:sem:=0,劈分二值信号 var mutexD:sem:=1,mutexF:semi=1;process PRODi:1.M:loop PRODi产生一条消息mi deposit:P(empty);P(matexD);bufrear:=mi;rear:=rear
18、mod q+1;V(mutexD);V(full);end loop;end;end PRODCONS.,process CONS j:1.N:loop fetch:P(full);P(mutexF);mj:=buf(front);front:=front mod q+1;V(matexF);V(empty);CONSj消费消息mi;end loop;end;,选择互斥是更为复杂的同步机制。用P,V操作也可以实现选择互斥。经典的例子是哲学家就餐问题。一张圆桌坐了五位哲学家,桌上放有一大盆通芯粉,但只有五把叉子.而吃通芯粉必须有两把叉子.一旦据有两把叉子的哲学家就可以吃,否则它只好利用等待的时间
19、思考。如果每人拿一把叉子等待其它人放下叉子,就产生死锁。通芯粉是共享资源,但叉子是只有两个哲学家共享的资源。每个哲学家的行为过程即为一进程。第i个进程只和第i和i+1个叉子有关。故算法如下:,program DININGPHILO:var forks 1.5:sem:=(5*1);process PHILOSOPHER i:1.4:loop P(forks i);P(forksi+1);吃通芯粉;V(forksi);V(forks i+1);思考问题;end loop;end;end DINING-PHILO.,process PHILOSOPHER 5:loop P(forks1);P(fo
20、rks5);吃通芯粉;V(forks1);V(forks5);思考问题;end loop;end;,以上以信号灯实现互斥同步均隐含使用了await等待原语。事实上多数分时处理的机器,单主机多处理器的机器是用系统调用并行核(或叫管理程序)实现的。进程创建就绪后将该进程的描述子(descriptor)入队,即就绪进程表,等待P 操作的完成。这样,进程处于就绪或阻塞状态且未运行。此时P,V操作的语义解释是:P(s):if s=1 then s:=0 else 置进程于queue中等候V(s):if queue!=empty then 从queue中消除一进程,令运行程序执行它 else s:=1,基
21、于消息传递的原语消息是信息传递的单元,按shannon的模型,信息源借助信道(channel)向信息目标发送消息.信道成了并发进程共享的资源.信道是通信网的抽象,泛指进程间通信的路径.信道由两个原语访问:send,receive.当某进程向信道发送一消息,通信就开始了.需要该消息的进程,从信道上接受(获取)这条消息.数据流也随发送者传递到接受者.由于信道本身不能存储,变量只能存放在各个进程中,因而不能共享地访问,所以也用不着互斥机制.由于只有所在进程能考察变量情况,条件同步编程与基于共享变量的大不相同.程序也不一定非要在一个处理器上执行,可以分布在多个处理器上,分布式程序因而得名.反过来,分布
22、式程序却可在单主机或多路处理器的(分时)系统上执行.此时把信道改成共享存储就可以了.,(1)四种传递消息的进程 过滤器(filter)进程 它是一种数据转移器,进程接受数据后按需要加工,然后传出,如同过滤器滤出需要的数据。receivefromsend to 客户/服务器进程 一个客户(client)进程它要求一个或多个服务器(server)进程为其服务,反过来一个服务器也可以为一到多个客户服务。显而易见,一个发出服务要求,一个响应要求后,完成服务,回复应答。通信是双向的。客户/服务器每完成一次通信客户方是发送(请求)接收(应答)两次消息传递,服务器方相反是接受(请求)发送(应答)两次消息传递
23、对等(peer)进程 另一类进程是既是客户又是服务器的peer。一组对等进程共同完成(并行地)一个复杂计算。例如,阵列计算中各结点上的进程都是peer。非阵列式网络上的Peer到Peer的进程交互最能代表网络上通信的一般情况。然而,由于算法复杂到目前还没有通用的解,是网络通信追求的最终目标,(2)两类通信模式 基于消息传递的进程,通信虽然不靠共享存储间接实现，然而通信时也有同步异步之分 同步即两进程都要执行到同步点直接交换数据.判定是否同步只看含send的进程是否有阻塞,等待接受进程的到来.如果是这样，一定是同步的 异步是两进程谁也不等谁按各自速度执行自己进程,就完成了数据通信。其实现,可以看作在接受进程中附带一很大的邮箱(缓冲时间差).发送者按自己进程执行,将一条条消息发到邮箱.而接受者在自己合适的时候处理一条条消息各不相扰,
