《互斥同步与通信》PPT课件

《《互斥同步与通信》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章互斥、同步与通讯并发进程(concurrentprocesses)进程互斥(mutualexclusion)进程同步(synchronization)进程高级通讯(communication)14.1并发进程4.1.1顺序程序及其特性程序的顺序性-内部顺序性：P1:a1,a2,a3;P2:b1,b2,b3-外部顺序性：情形1：a1,a2,a3,b1,b2,b3;情形2：b1,b2,b3,a1,a2,a3顺序程序设计的特性：-顺序性：处理机严格按指令依次执行；-封闭型：执行过程独占资源；-可再现性：程序执行的结果与执行速度无关。多个进程依次执行进程内所有

2、指令按顺序执行24.1并发进程4.1.2并发程序及其特性程序的并发性内部并发性：P2:b1,b2,b3;P2:b1,b3,b2外部并发性：情形1：a1,b1,b2,a2,a3,b3;情形2：b1,b2,a1,b3,a2,a3并发程序的特性（带来好处也引发问题）：-交叉性：不同的交叉可能导致不同的结果；-非封闭性：进程的运行环境可被其他进程所改变；-不可再现性：不可再现上次运行的结果。指令可以按顺序也可以不按顺序执行进程交叉执行并发特性将引发一系列问题如互斥、死锁、饿死等34.1.2与时间有关的错误例：图书借阅系统（x:某种书册数，设当前x=1.）终端1（进程p1

3、）：终端2（进程p2）：do{do{等待借书者；等待借书者；IF(x>=1){IF(x>=1){x=x-1;x=x-1;借书借书}}Else无书Else无书}while(1)}while(1)123444.1.2与时间有关的错误(Cont.)错误原因之1：进程执行交叉(进程推进速度不同);错误原因之2：涉及公共变量(x)。Remarks:某些交叉导致结果不正确;必须去掉导致不正确结果的交叉。54.2进程互斥(mutualexclusion)进程间发生的一种间接性相互作用。4.2.1共享变量与临界区4.2.2临界区域与进程互斥4.2.3进程互斥的实现4.2.4多处

4、理机环境下的互斥64.2.1共享变量与临界区域共享变量（sharedvariable）多个进程都需要访问的变量。临界区（criticalregion）访问共享变量的程序段。一组共享变量CR1CR2CRn…….程序段1程序段2程序段n7共享变量与临界区表示共享变量:shared<一组变量>临界区域:region<一组变量>do<语句＞例子：sharedx1,x2;sharedy1,y2;regionx1,x2do{……regiony1,y2do{……}……}临界区可以嵌套84.2.2临界区域与进程互斥定义：两个或两个以上进程不能同时进入关于同一组共享变量的临

5、界区域，否则可能发生与时间有关的错误，这种现象称为进程互斥。二层涵义：（1）不容许多个进程同时进入关于同一组共享变量的相同的临界区域；（2）不容许多个进程同时进入关于同一组共享变量的不同的临界区域。Remarks:互斥是相对于公共变量而言的。9嵌套临界区域sharedx;sharedy;regionxdo{regionydo{………….regionydo{regionxdo{…….…….}}…………}}临界区可以嵌套：①②已进入临界区域可能引发死锁！104.2.3进程互斥的实现FrameworkRepeatcriticalsectionremainders

6、ectionUntilfalseentrysectionexitsection114.2.3进程互斥的实现实现临界区管理的三个原则：正确性原则：任意时刻至多只能有一个进程处于同一组共享变量的临界区域中；公平性原则：一个请求进入临界区的进程应当在有限等待时间内获得进入临界区的机会；进展性原则：当临界区空闲时，竞争进入临界区的多个进程在有限的时间内确定下一个进入临界区的进程。临界区调度原则：！临界区空闲，想进入的应能进入；！临界区不空闲，进程应等待；！进程离开临界区时，应能唤醒等待进入的进程。124.2.3.1进程互斥的软件实现完全用程序实现，不需特殊硬件指令

7、支持。可用于单CPU和多CPU环境中。有忙式等待问题。Busywaiting“运行”或“就绪”13Lamport面包店算法算法思想：设置一个发号者，按0,1,2,…,发号。想进入临界区的进程抓号，抓到号之后按由小到大的次序依次进入。Problem:两个进程可能抓到相同的号。Why?为保证抓到不同的号，需要互斥机制。Resolution:若抓到相同的号，按进程编号依次进入。Definition:(a,b)<(c,d)if(a

8、所抓到的号码Pi进入：d