4进程的同步与通信,进程死锁

1第4章进程的同步与通信、进程死锁主要内容：并发执行，临界段，信号量，经典进程同步问题，消息传递原理，死锁。重点：临界段、同步、互斥的概念；信号量的概念和物理意义；消息传递的原理，死锁的概念。难点：信号量解决进程同步与互斥的方法，死锁防止、避免。计算机操作系统前趋图：用于描述一个程序的各部分（程序段或语句）间的执行顺序关系，或者是一个大的计算各子任务间的因果关系。1）是一个有向无循环图；2）图的结点对应程序中的一条语句、一个程序段或一个进程；3）结点间的有向边：表示两个结点之间存在的偏序或前趋关系“→”；s1s3s2s5s4s7s61.程序的顺序执行计算机操作系统指各程序段按照某种先后次序执行，仅当前一个操作执行完后才能执行后继操作。1.程序的顺序执行I1C1P1I2C2P2其中I、C、P分别表示输入、计算和打印操作图3-2程序顺序执行时的前趋图顺序执行的特点：顺序性，封闭性，可再现性计算机操作系统概念：若干个程序（或程序段）同时在系统中运行，这些程序（或程序段）的执行在时间上是重叠的，一个程序（或程序段）的执行尚未结束，另一个程序（或程序段）的执行已经开始。2.程序的并发执行I1I2I3C1C2C3P1P2P3若顺序执行三个作业共需要9（3*3）分钟并行执行三个作业只需要5（5/3*3）分钟计算机操作系统间断性：并发程序由于共享资源或为完成同一项任务而相互合作，形成相互制约关系。程序并发执行的特点：失去封闭性：多个程序共享系统中的各种资源，资源的状态将由多个程序改变，失去封闭性。一个程序执行时，会受到其他程序的影响。不可再现性（待续）并发与共享的问题：并行程序访问共享数据问题举例:(count为共享变量初值=300)ProgramA:…N=countN=N+100count=N…ProgramB:…M=countM=M-200count=M…如果按以下次序占处理机运行:N=count,N=N+100;M=count,M=M-200,count=M;count=N.结果count=400(应为200)*7并发的需要操作系统应尽量支持用户态程序最大限度地并发执行。程序设计要利用OS对并发运行的支持，安排事务并发执行。操作系统核心程序也要尽可能地并发运行4.1并发执行实现S1S2S3图4.1任务中子任务关系示意图84.1.1并发编程方法传统的串行程序存在着并行成分：Read(a)；Read(b)；c=a+b；Write(c)Read（a）和Read（b）两个语句可并行执行。9识别程序中的并发成分有两种方法：程序员写顺序程序，用识别工具识别并发成分。再组织使用操作系统的并发机制。由程序员识别并发成分:用并发程序设计语言设计并发程序，由编译系统安排并发；直接利用操作系统的系统调用。10并发程序设计语言---并发语句它是一种高级语言；语法形式：ParbeginS1；S2；…Sn；Parend；1）并发语句示例1Parbeginread（a）；read（b）；Parend；c=a+b；write（c）；112）并发语句示例2VarF,G:fileofT;r,s:T;reset(F);read(F,r);whilenoteof(F)do{s=r;Parbeginwrite(G,s);read(F,r);Parend;}write(G,r);}优点:并发语句的结构化特征非常好。缺点：存在着描述能力不强的缺点，即存在着用Parbegin/Parend语句无法描述的并发优先关系。改进手段：辅以其他手段，则并发语句可以大大增加其描述并发的能力。124.1.2并发执行的实现前面是对并发的高级语言描述，要真正实现并发执行，需要通过OS支持的进程机制。实现的两种方法：1)OS提供进程创建，结束和同步的系统调用；2)由并行语言编译器将并发语言的语句转化为对OS的系统调用。13与进程相关的系统调用UNIX操作系统利用进程支持并发执行；它提供了如下系统调用：fork（）：创建一个新进程。(1)该子进程继承了父进程的程序空间，复制了父进程的数据段和栈段。也就是说不管是父进程还是子进程，在占有处理机后，都从fork（）调用的返回点开始运行;(2)父进程fork（）调用的返回值是子进程的进程标识pid；(3)子进程fork（）调用的返回值是0。14exit（status）：进程结束。该系统调用发出后，操作系统将从系统中删除调用exit的进程，并将status值传给等待它结束的父进程。wait（&status）：等待子进程结束。(1)当有多个子进程时，任一个子进程结束即将控制返回调用者，并将子进程调用exit（status）时的status值送到&status指针所指单元中。(2)在控制返回调用者时，同时将所等到的子进程pid作为wait（）系统调用函数的返waitpid（pid，…）：等待pid所指定的进程结束。15多进程实现前述的读写并发程序pid=fork（）ifpid==0then{read（b）；exit（0）；}elseread（a）；wait（&status）；c=a+b；write（c）；16同步关系（直接制约）：为了完成一个共同任务，相互协作的几个进程需要在某些确定点上协调他们的工作，等待来自其它进程的信息，以调整它们的推进速度，方可顺利执行完毕。输入进程缓冲区计算进程4.2进程的同步与互斥互斥关系（间接制约）：把并发进程间存在的因相互竞争使用独占资源（共享资源）而产生的制约关系。例如：打印机，共享内存；17例1同步关系S1S2S4S5S7S3S6进程P1依次运行S1，S2，S4，S5，S7；进程P2依次运行S3，S618临界资源临界资源：一次仅允许一个进程使用的硬件或软件资源。一般包括：慢速设备，共享的变量、数据结构、缓冲区、表格、队列、栈、文件等。注意：对于临界资源，必须互斥访问，否则会导致执行结果的不确定性。4.2.1同步与临界段问题19例：2个进程P1，P2分别对共享变量account执行加1和加2的操作，account初始值为0，account的结果为多少？P1，P2的执行顺序如下：P1M=account;M=M+1;account=M;P2N=account;N=N+2;account=N;P1M=account;M=M+1;account=M;P2N=account;N=N+2;account=N;进程推进顺序按此顺序执行account=2按此顺序执行account=1两点说明：产生与时间有关的错误。对临界资源的互斥使用，应先申请、判断。20临界段定义：指在进程中访问临界资源的那段代码。访问过程：1）在进入临界段之前，写一段代码以检查可否进入临界段，通常把这段代码称为进入区(申请，判断)。2）在退出临界段后，必须有一段代码来清除“正在访问临界段”标志，或发出本进程已经退出临界段的信息，把这段代码称为退出区（释放）。21一个访问临界资源的进程描述如下：While(1){entrycode;//进入区criticalcode;//临界段exitcode;//退出区remaindercode;//剩余区}；22例2：P1,P2两进程使用同一打印机。如果不互斥使用会交叉输出。Entrycodeexitcode使用打印机P1Entrycodeexitcode使用打印机P223例3:对共享变量count的互斥访问。ParbeginP1:{M:=count;M:=M+1;count:=M;}P2:{N:=count;N:=N+2;count:=N;}Parend;EntrycodeexitcodeEntrycodeexitcode24如何实现进入区、退出区代码—同步机构同步机构：指能实现进程同步的机制，该机制能把其它进程需要的信息发送出去，也能测试自己需要的信息是否到达。同步机构应遵循4个准则：1、空闲让进；2、忙则等待；3、有限等待；4、让权等待；实现方法①软件方法②硬件方法254.2.2实现临界段的硬件方法与计算机体系结构有关1、屏蔽中断法中断引起的并发会导致错误的结果进程1的程序disableInterrupt();Balance=balance+amount;enableInterrupt();进程2的程序disableInterrupt();Balance=balance-amount;enableInterrupt();两条命令：enableInterrupt，disableInterrupt缺点：1）可能影响到I/O行为2）只能用于单处理机系统262、“Test_and_Set”指令该指令功能描述为：booleanTest_and_Set（boolean&target）{Booleanrv=target;Target=true；Returnrv}如果机器支持Test_and_Set，可用下列方法解决：(Lock=false)do{while（Test_and_Set(&lock)）;//进入区criticalsection;//临界区lock=false;//退出区noncriticalsection;//其它部分}while（1）;27二、“Swap”指令该指令功能描述为：voidSwap（boolean&a,boolean&b）{booleantemp=aa=bb=temp}28设Lock为全局布尔变量（初值为false），每个进程设一个局部布尔变量Key。利用Swap指令，可实现对临界区的加锁与解锁。do{key=true;while(key==ture)Swap(Lock,key);criticalsectionLock=false;non-criticalsection}while(1)294.2.3信号量(1965年，Dijkstra提出)信号量机构：“信号量”、“P，V操作”。•信号量S为一整型变量：•P(S):WhileS≤0；S=S-1；•V（S）：S=S＋1；P,V操作是两条原语，即保证P，V操作对变量S的访问是互斥操作。301.原语概念与实现原语：指完成某种功能且不被分割或不被中断执行的操作序列(又称原子操作)。实现临界段的元方法:•屏蔽中断(只用于单机)；•加硬锁,如“Test_and_Set”，“Swap”硬指令。P,V操作的实现31P(s)，V(s)的实现P(s){disableIntrrupt();While(s≤0){enableIntrrupt();disableIntrrupt();}s=s-1;enableIntrrupt();}V(s){disableIntrrupt();s=s+1;enableIntrrupt();}32实现信号量时与进程调度相结合，消除忙等待现象。基本思想是：在P操作循环等待的地方加入放弃处理机，进入等待队列动作；在V操作时，从等待队列中摘取进程变为就绪态。2.信号量的具体实现331.信号量定义typedefstruct{int:value;一个数型变量structprocess*L;一个PCB队列}SemaphoreSemaphoreS;2.P操作P(S):S.Value=S.value－1;ifS.value0then保存现场，将本进程挂入S.L队列，等待重新调度。3.V操作V(S):S.value:=value+1ifS.value≤0then从S.L队列取一进程，挂入就绪队列。4.P,V操作的优点：同步能力强5.P,V操作的缺点：程序结构差，易产生死锁。34信号量的物理意义P(s)操作：①请求分配一个S代表的资源，执行S.value-1；②若S.value0，表示系统已无该类资源，申请者阻塞。此时，|S.value|表示该信号量上阻塞的进程数；V(s)操作：①进程释放一个S代表的资源，执行S.value+1；②若S.value=0，表示尚有进程因等待S代表的资源而处于阻塞状态，所以应唤醒其中之一。353.利用信号量实现进程互斥使用方法：1）为每一个共享的临界