2022年操作系统教程孙钟秀主编高等教育出社同步通信与死锁ppt完整.ppt

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,操作系统教程孙钟秀主编高等教育出社同步通信与死锁ppt,3.1.1 顺序程序设计,进程的顺序性,一个进程在顺序处理器上的执行是严格按序的，一个进程只有当一个操作结束后，才能开始后继操作。,顺序程序设计是把一个程序设计成一个顺序执行的程序模块，顺序的含义不但指一个程序模块内部，也指两个程序模块之间。,2,顺序程序设计特点,程序执行的顺序性,程序环境的封闭性,程序执行结果的确定性,计算过程的可再现性,顺序程序设计的缺点,计算机系统效率不高。,3,3.1.2 进程的并发性,1、并发程序设计,进程执行的并发性：一组进程的执行在时间上是重叠的。,并发性举例：有两个进程A(a1、a2、a3)和B(b1、b2、b3)并发执行。,a1、a2、a3、b1、b2、b3 顺序执行,a1、b1、a2、b2、a3、b3 并发执行,从宏观上看，并发性反映一个时间段中几个进程都在同一处理器上，处于运行还未运行结束状态。,从微观上看，任一时刻仅有一个进程在处理器上运行。,4,并行工作图示,进程,i1,p1,i,p,o,o1,i2,p2,o2,i3,p3,o3,t1,t2,t3,时间,并行工作,i4,t4,i5,P4,t5,5,并发的实质,并发的实质是一个处理器在几个进程之间的多路复用，并发是对有限的物理资源强制行使多用户共享，消除计算机部件之间的互等现象，以提高系统资源利用率。,6,2、并发进程的特性,无关的并发进程,一组并发进程分别在不同的变量集合上操作，一个进程的执行与其他并发进程的进展无关。,并发进程的无关性是进程的执行与时间无关的一个充分条件，又称为Bernstein条件。,交往的并发进程,一组并发进程共享某些变量，一个进程的执行可能影响其他并发进程的结果。,7,Bernstein条件,R(pi)=a1,a2,an，程序pi在执行期间引用的变量集,W(pi)=b1,b2,bm，程序pi在执行期间改变的变量集,若两个程序的变量集交集之和为空集：R(p1)W(p2)R(p2)W(p1)W(p1)W(p2)=,则并发进程的执行与时间无关。,8,Bernstein条件举例,例如，有如下四条语句：,S1:a:=x+y S2:b:=z+1,S3:c:=a b S4:w:=c+1,于是有：,R(S1)=x,y,R(S2)=z，R(S3)=a,b，R(S4)=c；W(S1)=a,W(S2)=b，W(S3)=c，W(S4)=w。,S1和S2可并发执行，满足Bernstein条件。其他语句并发执行可能会产生与时间有关的错误。,9,并发程序设计的优点,对于单处理器系统,可让处理器和各I/O设备同时工作,发挥硬部件的并行能力。,对于多处理器系统,可让各进程在不同处理器上物理地并行，加快计算速度。,简化了程序设计任务。,10,采用并发程序设计的目的,充分发挥硬件的并行性，提高系统效率。硬件能并行工作仅有了提高效率的可能性，硬部件并行性的实现需要软件技术去利用和发挥，这种软件技术就是并发程序设计。,并发程序设计是多道程序设计的基础，多道程序的实质就是把并发程序设计引入到系统中。,11,3、与时间有关的错误,对于一组交往的并发进程，执行的相对速度无法相互控制，各种与时间有关的错误就可能出现。,与时间有关错误的表现形式：,结果不唯一,永远等待,12,（结果不唯一）机票问题,/飞机票售票问题,void T1()void T2(),按旅客订票要求找到Aj;按旅客订票要求找到Aj;,int X1=Aj;int X2=Aj;,if(X1=1)if(X2=1),X1-;X2-;,Aj=X1;Aj=X2;,输出一张票;输出一张票;,else else,输出信息票已售完;输出信息票已售完;,13,T1、T2并发执行，可能出现如下交叉情况：,T1:X1=Aj;/X1=m,T2:X2=Aj;/X2=m,T2:X2-;Aj=X2;输出一张票;/Aj=m-1,T1:X1-;Aj=X1;输出一张票;/Aj=m-1,同一张票卖给两位旅客,14,（永远等待）主存管理问题,申请和归还主存资源问题,int X=memory;/memory为初始主存容量,void borrow(int B)void return(int B),while(BX)X=X+B;,进程进入等待主存资源队列;修改主存分配表;,X=X-B;释放等主存资源进程;,修改主存分配表，,进程获得主存资源;,15,若对borrow和return的并发执行不加限制将会导致错误，例如：,Borrow:while(BX);,Return:X=X+B;修改主存分配表;释放等待主存资源的进程；,此时，因为borrow还没有进入等待队列，因此，return的释放操作是空操作，当borrow进入等待队列时，可能没有进程再来归还，处于永远等待状态。,16,3.1.3 进程的交互：竞争与协作(1)第一种是竞争关系,系统中的多个进程之间彼此无关,系统中的多个进程之间彼此相关,资源竞争的两个控制问题：,一个是死锁(Deadlock)问题，,一个是饥饿(Starvation)问题,既要解决饥饿问题，又要解决死锁问题。,进程互斥是指若干个进程因相互争夺独占型资源时所产生的竞争制约关系。,17,进程的交往：竞争与协作(2)第二种是协作关系,某些进程为完成同一任务需要分工协作。,进程同步指为完成共同任务的并发进程基于某个条件来协调它们的活动，因为需要在某些位置上排定执行的先后次序而等待、传递信号或消息所产生的协作制约关系。,进程同步指两个以上进程基于某个条件来协调它们的活动。一个进程的执行依赖于协作进程的消息或信号，当一个进程没有得到来自于协作进程的消息或信号时需等待，直到消息或信号到达才被唤醒。,进程互斥关系是一种特殊的进程同步关系，即逐次使用互斥共享资源，是对进程使用资源次序上的一种协调。,18,3.2 临界区管理,3.2.1 互斥与临界区,3.2.2 实现临界区管理的几种尝试,3.2.3 实现临界区管理的软件方法,3.2.4 实现临界区管理的硬件设施,19,3.2.1 互斥与临界区(1),并发进程中与共享变量有关的程序段叫“临界区”，共享变量代表的资源叫“临界资源”。,与同一变量有关的临界区分散在各进程的程序段中，而各进程的执行速度不可预知。,如果保证进程在临界区执行时，不让另一个进程进入临界区，即各进程对共享变量的访问是互斥的，就不会造成与时间有关的错误。,20,互斥与临界区(2),临界区调度原则：,一次至多一个进程能够进入临界区内执行；,如果已有进程在临界区，其他试图进入的进程应等待；,进入临界区内的进程应在有限时间内退出，以便让等待进程中的一个进入。,临界区调度原则总结：,互斥使用、有空让进；,忙则等待、有限等待；,择一而入，算法可行。,21,3.2.2 临界区管理的尝试(1),bool inside1=false;/P1不在其临界区内,bool inside2=false;/P2不在其临界区内,cobegin/*cobegin和coend表示括号中的进程是一组并发进程*/,process P1()process P2(),while(inside2);/,等待,while(inside1);/,等待,inside1=true;inside2=true;,临界区;临界区;,inside1=false;inside2=false;,coend,可能不满足互斥条件,22,临界区管理的尝试(2),bool inside1=false;/P1不在其临界区内,bool inside2=false;/P2不在其临界区内,cobegin,process P1()process P2(),inside1=true;inside2=true;,while(inside2);/,等待,while(inside1);/,等待,临界区;临界区;,inside1=false;inside2=false;,coend,可能出现死循环,23,3.2.3实现临界区的软件算法Peterson算法(1),bool inside2;,inside0=false;,inside1=false;,enum 0,1 turn;,24,Peterson算法(2),cobegin,process P0(),inside0=true;,turn=1;,while(inside1,临界区;,inside0=false;,25,Peterson算法(3),process P1(),inside1=true;,turn=0;,while(inside0,临界区;,inside1=false;,coend,26,3.2.4 实现临界区管理的硬件设施,关中断,测试并建立指令,对换指令,27,关中断,实现互斥的最简单方法,关中断适用场合,简单有效，对操作系统自身有用，可在更新共享变量或列表的几条指令期间禁止中断。,关中断方法的缺点,不适合作为通用的互斥机制，关中断时间过长会影响性能和系统效率；,不适应于多处理器计算机系统，因为一个处理器关中断，并不能防止进程在其它处理器上执行相同的临界段代码；,若将这项权力赋予用户会存在危险，若用户未开中断，则系统可能因此而终止。,28,测试并建立指令(1),TS指令的处理过程,bool TS(bool&x),if(x),x=false;,return true;,else,return false;,TS指令管理临界区时，可把一个临区与一个布尔变量s相连，由于变量s代表了临界资源的状态，可把它看成一把锁。,29,测试并建立指令(2),TS指令实现进程互斥,bool s=true;,cobegin,process Pi()/i=1,2,.,n,while(!TS(s);/上锁,临界区;,s=true;/开锁,coend,30,对换指令(1),void SWAP(bool&a,bool&b),bool temp=a;,a=b;,b=temp;,31,对换指令(2),对换指令实现进程互斥,bool lock=false;,cobegin,Process Pi()/i=1,2,.,n,bool keyi=true;,do,SWAP(keyi,lock);,while(keyi);/上锁,临界区;,SWAP(keyi,lock);/开锁,coend,32,3.3 信号量与,PV操作,3.3.1 同步与同步机制,3.3.2 信号量与PV操作,3.3.3 信号量实现互斥,3.3.4 信号量解决五个哲学家吃通心面问题,3.3.5 信号量解决生产者-消费者问题,3.3.6 记录型信号量解决读者-写者问题,3.3.7 记录型信号量解决理发师问题,33,3.3.1 同步和同步机制,著名的生产者-消费者问题是计算机操作系统中并发进程内在关系的一种抽象，是典型的进程同步问题。,在操作系统中，生产者进程可以是计算进程、发送进程；而消费者进程可以是打印进程、接收进程等等。,解决好生产者-消费者问题就解决好了一类并发进程的同步问题。,34,生产者-消费者问题表述,有界缓冲问题,有n个生产者和m个消费者，连接在一个有k个单位缓冲区的有界缓冲上。其中，pi和cj都是并发进程，只要缓冲区未满，生产者pi生产的产品就可投入缓冲区；只要缓冲区不空，消费者进程cj就可从缓冲区取走并消耗产品。,35,生产者-消费者问题算法描述(1),int k;,typedef anyitem item;/item类型,item bufferk;,int in=0,out=0,counter=0;,36,生产者-消费者问题算法描述(2),process producer(void),while(true)/无限循环,produce an item in nextp;/生产一个产品,if(counter=k)/缓冲满时，生产者睡眠,sleep(producer);,bufferin=nextp;/将一个产品放入缓冲区,in=(in+1)%k;/指针推进,counter+;/缓冲内产品数加1,if(counter=1)/缓冲为空，加进一件产品,wakeup(consumer);/并唤醒消费者,37,生产者-消费者问题算法描述(3),process consumer(void),while(true)/无限循环,if(counter=0)/缓冲区空，消费者睡眠,sleep(consumer);,nextc=bufferout;/取一个产品到nextc,out=(out+1)%k;/指针推进,counter-;/取走一个产品，计数减1,if(counter=k-1)/缓冲满了，取走一件产品并唤,wakeup(producer);/醒生产者,consume the item in nextc;/消耗产品,38,生产者-消费者问题的算法描述(4),生产者和消费者进程对counter的交替执行会使其结果不唯一,生产者和消费者进程的交替执行会导致进程永远等待,39,3.3.2 信号量与,PV操作(1),前节种种方法解决临界区调度问题的缺点:,1)对不能进入临界区的进程，采用忙式等待测试法，浪费CPU时间。,2)将测试能否进入临界区的责任推给各个竞争的进程会削弱系统的可靠性，加重了用户编程负担。,1965年E.W.Dijkstra提出了新的同步工具-信号量和P、V操作。,40,信号量与,PV操作(2),信号量：一种软件资源,原语：内核中执行时不可被中断的过程,P操作原语和V操作原语,一个进程在某一特殊点上被迫停止执行直到接收到一个对应的特殊变量值，这种特殊变量就是信号量(semaphore)，复杂的进程合作需求都可以通过适当的信号结构得到满足。,41,信号量与,PV操作(3),操作系统中，信号量表示物理资源的实体，它是一个与队列有关的整型变量。,实现时，信号量是一种记录型数据结构，有两个分量：一个是信号量的值，另一个是信号量队列的队列指针。,信号量的值(-2),信号量队列指针,42,信号量分类,信号量按其用途分为,公用信号量：用户实现进程互斥，初值为1，相关进程均可在此信号量上执行PV操作；,私有信号量：多用于并发进程同步，初值为0或正整数，仅允许此信号量所拥有的进程执行P操作，而其它相关进程可执行V操作。,信号量按其取值分为,二元信号量：仅允许取值为0或1，主要用于解决互斥问题；,一般信号量：允许取大于1的整型值，主要用于解决同步问题。,43,一般信号量(1),设s为一个记录型数据结构,一个分量为整形量value,另一个为信号量队列queue,P和V操作原语定义：,P(s)；将信号量s减去l，若结果小于0，则调用P(s)的进程被置成等待信号量s的状态。,V(s)：将信号量s加1，若结果不大于0，则释放一个等待信号量s的进程。,44,一般信号量(2),typedef struct semaphore,int value;/信号量值,struct pcb*list;/信号量队列指针,;,void P(semaphore&s),s.value-;,if(s.value0),W(s.list);,void V(semaphore&s),s.value+;,if(s.value=0),R(s.list);,45,一般信号量(3),推论1：若信号量s为正值，则该值等于在封锁进程之前对信号量s可施行的P操作数、亦等于s所代表的实际还可以使用的物理资源数,推论2：若信号量s为负值，则其绝对值等于登记排列在该信号量s队列之中等待的进程个数、亦即恰好等于对信号量s实施P操作而被封锁起来并进入信号量s队列的进程数,推论3：通常，P操作意味着请求一个资源，V操作意味着释放一个资源。在一定条件下，P操作代表挂起进程操作，而V操作代表唤醒被挂起进程的操作,46,二元信号量(1),设s为一个记录型数据结构,一个分量为value,它仅能取值0和1,另一个分量为信号量队列queue,把二元信号量上的P、V操作记为BP和BV,BP和BV操作原语的定义如下：,47,二元信号量(2),typedef struct binary_semaphore,int value;/value取值0 or 1,struct pcb*list;,void BP(binary_semaphore&s),if(s.value=1),s.value=0;,else,W(s.list);,void BV(binary_semaphore&s),if(s.list is empty(),s.value=1;,else,R(s.list);,48,3.3.3 信号量实现互斥,semaphore mutex;,mutex=1;,cobegin,process Pi()/i=1,n,P(mutex);,临界区;,V(mutex);,coend,49,3.3.4 信号量解决五个哲学家吃通心面问题(1),有五个哲学家围坐在一圆桌旁，桌中央有一盘通心面，每人面前有一只空盘于，每两人之间放一把叉子。每个哲学家思考、饥饿、然后吃通心面。为了吃面，每个哲学家必须获得两把叉子，且每人只能直接从自己左边或右边去取叉子。,50,信号量解决五个哲学家吃通心面问题(2),51,哲学家吃通心面问题(3),semaphore fork5;,for(int i=0;i5;i+),forki=1;,cobegin,process philosopher_i(),/i=0,1,2,3,4,while(true),think();,P(forki);,P(fork(i+1)%5);,eat();,V(forki);,V(fork(i+1)%5);,coend,可能死锁！,52,有若干种办法可避免这类死锁,上述解法可能出现永远等待，有若干种办法可避免死锁：,至多允许四个哲学家同时吃；,奇数号先取左手边的叉子，偶数号先取右手边的叉子；,每个哲学家取到手边的两把叉子才吃，否则一把叉子也不取。,53,哲学家吃通心面问题的一种正确解,semaphore fork5;,for(int i=0;i5;i+),forki=1;,cobegin,process,philosopher_i(),/*i=0,1,2,3*/,while(true),think()；,P(forki；,/*i=4,P(fork0)*/,P(fork,(i+1)%5,),；,/*i=4,P(fork4)*/,eat()；,V(forki)；,V(fork(i+1%5)；,coend,54,3.3.5 信号量解决生产者消费者问题,一个生产者、一个消费者共享一个缓冲区,一个生产者、一个消费者共享多个缓冲区,多个生产者、多个消费者共享多个缓冲区,55,一个生产者、一个消费者共享一个缓冲区的解,int B;,semaphore empty;/可以使用的空缓冲区数,semaphore full;/缓冲区内可以使用的产品数,empty=1;/缓冲区内允许放入一件产品,full=0;/缓冲区内没有产品,56,cobegin,process producer()process consumer(),while(true)while(true),produce();P(full);,P(empty);take()from B;,append()to B;V(empty);,V(full);consume();,coend,57,多个生产者/消费者、共享多个缓冲区的解,item Bk;,semaphore empty;empty=k;,/可以使用的空缓冲区数,semaphore full;full=0;,/缓冲区内可以使用的产品数,semaphore mutex;mutex=1;/互斥信号量,int in=0;/放入缓冲区指针,int out=0;/取出缓冲区指针,58,cobegin,process producer_i()process consumer_j(),while(true)while(true),produce();P(full);,P(empty);P(mutex);,P(mutex);take()from Bout;,append to Bin;out=(out+1)%k;,in=(in+1)%k;V(mutex);,V(mutex);V(empty);,V(full);consume();,coend,59,3.3.6 信号量解决读者-写者问题(1),有两组并发进程：读者和写者，共享一个文件F，要求：,允许多个读者同时执行读操作,任一写者在完成写操作之前不允许其它读者或写者工作,写者执行写操作前，应让已有的写者和读者全部退出,60,信号量解决读者写者问题(2),int readcount=0;/读进程计数,semaphore writeblock,mutex;,writeblock=1;mutex=1;,61,信号量解决读者写者问题(3),cobegin,process reader_i()process writer_j(),P(mutex);P(writeblock);,readcount+;写文件;,if(readcount=1)V(writeblock);,P(writeblock);,V(mutex);,读文件;,P(mutex);,readcount-;,if(readcount=0),V(writeblock);,V(mutex);,coend,62,3.3.7 信号量解决理发师问题(1),理发店理有一位理发师、一把理发椅和n把供等候理发的顾客坐的椅子,如果没有顾客，理发师便在理发椅上睡觉,一个顾客到来时，它必须叫醒理发师,如果理发师正在理发时又有顾客来到，则如果有空椅子可坐，就坐下来等待，否则就离开,63,信号量解决理发师问题(2),int waiting=0;/等候理发顾客坐的椅子数,int CHAIRS=N;/为顾客准备的椅子数,semaphore customers,barbers,mutex;,customers=0;barbers=0;mutex=1;,64,信号量解决理发师问题(3),cobegin,process barber(),while(true),P(customers);/有顾客吗？若无顾客，理发师睡眠,P(mutex);/若有顾客时，进入临界区,waiting-;/等候顾客数少一个,V(barbers);/理发师准备为顾客理发,V(mutex);/退出临界区,cut_hair();/理发师正在理发(非临界区),65,process customer_i(),P(mutex);/进入临界区,if(waitingCHAIRS)/有空椅子吗,waiting+;/等候顾客数加1,V(customers);/唤醒理发师,V(mutex);/退出临界区,P(barbers);/理发师忙，顾客坐下等待,get_haircut();/否则顾客坐下理发,else,V(mutex);/人满了，走吧！,coend,66,总结补充,信号量小结,P、V操作小结,前驱关系的信号量解答,针对信号量问题的补充练习,67,1、信号量小结,一个信号量可用于n个进程的同步互斥；且只能由P、V操作修改。,用于互斥时，S初值为1，取值为1-(n-1)（相当于临界区的通行证，实际上也是资源个数）,S=1：临界区可用,S=0：已有一进程进入临界区,S=0,S=0:表示可用资源个数,S0),V(IM.next);,/有就释放一个发出过signal的进程,else,V(IM.mutex);/否则开放管程,94,Hoare管程的wait()操作,void wait(semaphore&x_sem,int,&x_count,InterfaceModule&IM),x_count+;,/等资源进程个数加1，x_count初始化为0,if(IM.next_count0)/判有否发出过signal的进程,V(IM.next);/有就释放一个,else,V(IM.mutex);/否则开放管程,P(x_sem);,/等资源进程阻塞自己，x_sem初始化为0,x_count-;/等资源进程个数减1,95,Hoare管程的signal()操作,void signal(semaphore&x_sem,int,&x_count,InterfaceModule&IM),if(x_count0)/有等资源进程吗?,IM.next_count+;/发出signal进程个数加1,V(x_sem);/释放一个等资源的进程,P(IM.next);/发出signal进程阻塞自己,IM.next_count-;/发出signal进程个数减1,96,3.4.3 使用管程解决进程同步问题,1.霍尔管程解决五个哲学家吃通心面问题(1),type dining_philosophers=monitor,enum thinking,hungry,eating state5;,semaphore self5;,int self_count5;,InterfaceModule IM;,for(int i=0;i5;i+)/初始化，i为进程号,statei=thinking;,define pickup,putdown;,use enter,leave,wait,signal；,97,霍尔管程解决五个哲学家吃通心面问题(2),void pickup(int i)/i=0,1,.,4,enter(IM);,statei=hungry;,test(i);,if(statei!=eating),wait(selfi,self_counti,IM);,leave(IM);,void putdown(int i)/i=0,1,2,.,4,enter(IM);,statei=thinking;,test(i-1)%5);,test(i+1)%5);,leave(IM);,98,霍尔管程实现五个哲学家吃通心面问题(3),void test(int k)/k=0,1,.,4,if(state(k-)%5!=eating)&(statek=hungry),&(state(k+1)%5!=eating),statek=eating;,signal(selfk,self_countk,IM);,99,2.管程解决生产者-消费者问题(1),type producer_consumer=monitor,item Bk;/缓冲区个数,int in,out;/存取指针,int count;/缓冲中产品数,semaphore notfull,notempty;/条件变量,int notfull_count,notempty_count;,InterfaceModule IM;,define append,take;,use enter,leave,wait,signal,；,100,管程解决生产者-消费者问题(2),void append(item x),enter(IM);,if(count=k)/缓冲已满,wait(notfull,notfull_count,IM);,Bin=x;,in=(in+1)%k;,count+;/增加一个产品,signal(notempty,notempty_count,IM);,/唤醒等待消费者,leave(IM);,101,管程解决生产者-消费者问题(3),void take(item&x),enter(IM);,if(count=0),wait(notempty,notempty_count,IM);,/缓冲已空,x=Bout;,out=(out+1)%k;,count-;/减少一个产品,signal(notfull,notfull_count,IM);,/唤醒等待生产者,leave(IM);,102,3.5 进程通信,3.5.1 信号通信机制,3.5.2 管道通信机制,3.5.3 共享主存通信机制,3.5.4 消息传递通信机制,103,进程通信概念,并发进程之间的交互必须满足两个基本要求：同步和通信。,进程竞争资源时要实施互斥，互斥是一种特殊的同步，实质上需要解决好进程同步问题，,进程同步是一种进程通信，通过修改信号量，进程之间建立起联系，相互协调运行和协同工作。,进程协同工作时，需互相交换信息，可能是少量信息，也可能交换大批数据。,进程之间互相交换信息的工作称为进程通信IPC（InterProcess Communication）。,104,进程间通信的方式,信号(signal)通信机制,管道(pipeline)通信机制,消息传递(message passing)通信机制,信号量(semaphore)通信机制,共享主存(shared memory)通信机制,105,进程间通信的方式发展,UNIX发展 中，AT&T的Bell与加大伯克利的BSD是两大主力。,Bell致力于改进传统的进程IPC，形成了SYSTEM IPC机制。,BSD在改进IPC的同时，把网络通信规程(TCP/IP)实现到UNIX内核中，考虑把同一计算机上的进程通信纳入更广的网络范围的进程间通信，这种努力结果出现了socket网络通信机制。,106,3.5.1 信号通信机制,信号机制又称软中断，一种简单的通信机制，通过发送一个指定信号通知进程某个异常事件发生。,用户、内核和进程都能生成信号请求：,1)用户-用户能通过输入ctrl+c，或终端驱动程序分配给信号控制字符的其他任何键来请求内核产生信号。,2)内核-当进程执行出错时，内核检测到事件并给进程发送信号，例如，非法段存取、浮点数溢出、或非法操作码，内核也利用信号通知进程种种特定事件发生。,3)进程-进程可通过系统调用kill给另一个进程发送信号，一个进程可通过信号与另一个进程通信。,107,Linux系统信号分类,与进程终止相关的信号,与进程例外事件相关的信号,与进程执行系统调用相关的信号,与进程终端交互相关的信号,用户进程发信号,跟踪进程执行的信号,108,信号机制的实现,信号有一个产生、传送、捕获和释放的过程,信号屏蔽位blocked,信号发送工作由系统调用kill完成,信号响应使用系统调用sigaction完成,信号的处理过程,109,系统,空间,中断或异常服务,当前进程因中断/异常而进入核心态,在返回用户态之前，调用do_signal()，handle_signal()转向用户空间执行信号处理程序,陷入内核后执行善后工作,从内核返回用户空间,用户空间,应用程序,信号处,理程序,应用程序,继续执行,发送信号,执行信号处理程序,断点,断点返回,信号处理程序执行结束，执行sigreturn(),信号的检测与处理流程,110,3.5.2 管道通信机制,管道(pipeline)是连接读写进程的一个特殊文件，允许进程按先进先出方式传送数据,也能使进程同步执行操作。,发送进程以字符流形式把大量数据送入管道，接收进程从管道中接收数据，所以叫管道通信。,管道的实质是一个共享文件，基本上可借助于文件系统的机制实现，包括（管道）文件的创建、打开、关闭和读写。,111,共享文件通信机制,读写进程相互协调，必须做到：,进程对通信机构的使用应该互斥，一个进程正在使用某个管道写入或读出数据时，另一个进程就必须等待。(write阻塞、read阻塞),发送者和接收者双方必须能够知道对方是否存在，如果对方已经不存在，就没有必要再发送信息。,112,pipe的数据结构,系统打开,文件表,用户打开,文件表,主存活动,索引节点表,外存,fp,读进程,写进程,fp,文件节点指针,文件节点指针,索引,节点,pipe文件,113,父子进程通过管道传送信息,写端,读端,进程A,写端,读端,进程B,管道文件,(缓冲区),进程A打开文件表,进程B打开文件表,114,兄弟进程通过管道传送信息,写端,读端,进程B,管道文件,(缓冲区),写端,读端,进程A,进程A打开文件表,进程B打开文件表,写端,读端,进程C,进程C打开文件表,115,3.5.3 共享主存通信机制,进程1的虚存空间,虚存段,进程2的虚存空间,虚存段,物理主存,共享主存,116,与共享存储有关的系统调用,shmget(key,size,permflags),shmat(shm-id,daddr,shmflags),shmdt(memptr),shmctl(shm-id,command,&shm-stat),117,3.5.4 消息传递(1),什么是消息传递（message passing）?,消息和消息传递机制,基本的消息传递原语send，receive,118,消息传递(2),采用消息传递机制后，一个正在执行的进程可在任何时刻向另一个正在执行的进程发送消息；一个正在执行的进程也可在任何时刻向正在执行的另一个进程请求消息。,一个进程在某一时刻的执行依赖于另一进程的消息或等待其他进程对发出消息的回答，那么，消息传递机制紧密地与进程的阻塞和释放相联系。消息传递就进一步扩充了并发进程间对数据的共享，提供了进程同步的能力。,119,直接通信,发送或接收消息的进程必须指出信件发给谁或从谁那里接收消息。,原语send（P，消息）,把一个消息发送给进程P,原语receive（Q，消息）,从进程Q接收一个消息,120,间接通信,原语send（A，信件）,把一封信件（消息）传送到信箱A,原语receive（A，信件）,从信箱A接收一封信件（消息）,信箱是存放信件的存储区域，每个信箱可分成信箱特征和信箱体两部分。,信箱特征指出信箱容量、信件格式、指针等；,信箱体用来存放信件,121,间接通信的实现,发送信件：,如果指定信箱未满，则将信件送入信箱中由指针所指示的位置，并释放等待该信箱中信件的等待者；否则发送信件者被置成等待信箱状态,接收信件：,如果指定信箱中有信，则取出一封信件，并释放等待信箱的等待者，否则接收信件者被置成等待信箱中信件的状态,122,消息传递机制解决进程互斥问题,create_mailbox(box);,send(box,null);,void Pi()/i=1,2,n,message msg;,while(true),receive(box,msg);,临界区;,send(box,msg);,cobegin,Pi();,coend,123,用消息传递机制解决生产者-消费者问(1),int capacity,i;/缓冲大小,creat-mailbox(producer);/创建信箱,creat-mailbox(consumer);,for(i=0;icapacity;i+),send(producer,null);/发送空消息,124,用消息传递机制解决生产者-消费者问(2),void producer_i()/i=1,n,message pmsg;,while(true),produce();/生产消息,receive(producerer,null);/等待空消息,build();/构造一条消息,send(consumer,pmsg);/发送消息,125,用消息传递机制解决生产者-消费者问题(3),void consumer_j()/j=1,m,message cmsg;,while(true),receive(consumer,cmsg);/接收消息,extract();/取消息,send(producer,null);/回送空消息,consume(csmg);/消耗消息,126,用消息传递机制解决生产者-消费者问题(4),cobegin,producer_i();,consumer_j();,coend,127,信件的格式问题,单机系统中信件的格式可