第四章互斥同步与通讯课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《第四章互斥同步与通讯课件.ppt》由用户(晟晟文业)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第四 章互斥 同步 通讯 课件
- 资源描述:
-
1、进程进程(线程线程)之间的相互作用:之间的相互作用:互斥、同步、通讯互斥、同步、通讯4.1 并发进程并发进程(concurrent processes)4.2 进程进程互斥互斥(mutual exclusion)4.3 进程进程同步同步(synchronization)4.4 进程高级进程高级通讯通讯(communication)4.1.1 顺序程序及其特性顺序程序及其特性程序的顺序性程序的顺序性有两层含义:(1)内部顺序性:指一个进程的所有指令 按序执行按序执行;(2)外部顺序性:指多个进程依次执行依次执行;例如,假设有两个进程P1和P2:P1活动:a1 a2 a3 a4 P2活动:b1 b
2、2 b3 顺序执行时,有如下两种情形:情形1:a1 a2 a3 a4 b1 b2 b3 情形2:b1 b2 b3 a1 a2 a3 a4 顺序程序的特性顺序程序的特性:(1)顺序性顺序性:处理机严格按指令次序依次执行,仅当一条指令执行完才开始执行下一指令;(2)封闭性封闭性:程序在执行过程中独占系统的全部 资源。该程序的运行环境只与其自身动作有 关,不受其它程序及外界因素影响;(3)可再现性可再现性:程序的执行结果只与初始条件有 关,与执行速度无关。给定相同的初始条件 ,程序的任意多次执行一定得到相同结果。4.1.2 并发程序及其特性并发程序及其特性程序的并发性程序的并发性有两层含义:(1)内
3、部并发性内部并发性:指一个进程的所有指令不一定不一定 按序执行;(2)外部并发性外部并发性:指多个进程交叉执行交叉执行。例如,假设有两个进程:P1活动:a1 a2 a3 a4 P2活动:b1 b2 b3 内部并发性如内部并发性如:P2:b1,b3,b2;外部并发性如外部并发性如:情形1:a1 b1 b2 a2 a3 b3 a4 情形2:b1 b2 a1 a2 a3 b3 a4 并发进程在执行过程中出现哪种交叉情形是不可预知的,这就是并发程序的不确定性并发程序的不确定性。并发程序的特性并发程序的特性:(1)交叉性交叉性:一个进程的某些指令可交叉执行,不同的进程亦可交叉执行;程序并发执行时,不同的
4、交叉可能导致不同的 计算结果。OS应保证只产生导致正确结果的交 叉,去除那些可能导致不正确结果的交叉。(2)非封闭性非封闭性:一个进程的运行环境可能被其它进 程改变,从而相互影响。(3)不可再现性不可再现性:并发程序的多次执行可能对应不 同的交叉,因而不能期望重新运行的程序能够 再现上次运行的结果。如运行时间4.1.2 与时间有关的错误与时间有关的错误例如 图书借阅系统(设x:某种书册数,当前x=1)终端1:终端2:CYCLE CYCLE 等待借书者;等待借书者;IF x=1 Then IF x=1 Then Begin Begin x:=x-1;x:=x-1;借书 借书 End End El
5、se 无书 Else 无书 End End 1234 上述错误的发生与进程的推进速度有关(速度是时间的函数)。当进程P1执行到处被中断,之后P2插入,则不会发生上述错误。若一种错误的发生与进程的推进速度有关,则称这种错误为与时间有关的错误与时间有关的错误。发生与时间有关错误与时间有关错误的原因:(1)进程执行交叉(interleave)。(2)涉及公共变量(x)。若两个进程同时对变量x进行操作,其中一个进程对x的操作仅做了一部分时,另一个进程中途插入,则可能使变量x处于一种不确定状态,从而失去其数据完整性。OS必须防止这种情况的发生。进程互斥进程互斥是进程间发生的一种间接相互作用,这种相互作用
6、是进程本身不希望的,也是运行进程感觉不到的。进程互斥可能发生在相关进程之间进程互斥可能发生在相关进程之间,也可也可能发生在无关进程之间能发生在无关进程之间。4.2.1 共享变量与临界区共享变量与临界区 (shared variable&critical region)1.1.共享变量与临界区的概念共享变量与临界区的概念共享变量共享变量:可以被多个进程访问的变量。也称公共变量。临界区临界区:访问共享变量的程序段。也称为临界段(critical section)。共享变量与临界区的关系:一组公共变量一组公共变量CR1CR2CRn.2.2.共享变量与临界区的表示共享变量与临界区的表示共享变量的表示共
7、享变量的表示(说明):shared 如,shared x1,x2;临界区的表示临界区的表示:region do 这是一个语句,称作临界区语句。其中可为任意语句,包括临界区语句。例如,region x1,x2 do (访问x1,x2)再如,shared b:array0,.,n-1 of integer;region b do begin (访问b)end;若一个临界区语句中的部分包括另一个临界区语句,便发生了临界区嵌套临界区嵌套。例如,shared x1,x2;shared y1,y2;region x1,x2 do region y1,y2 do 再如,shared x1,x2;shared
8、 y1,y2;region x1,x2 do region y1,y2 do begin begin .region y1,y2 do region x1,x2 do begin begin .end end end;end;4.2.2 临界区与进程互斥临界区与进程互斥进程互斥进程互斥:两个或两个以上的进程不能同时进入 关于同一组共享变量的临界区,否则可能发 发生与时间有关的错误与时间有关的错误,这种现象被称作进进 程互斥程互斥。进程互斥有两层含义进程互斥有两层含义:(1)不容许多个进程同时进入关于同一组共享 变量的相同的临界区;(2)不容许多个进程同时进入关于同一组共享 变量的不同的临界区。
9、注意:进程互斥是相对于共享变量而言的。当然,若容许多个进程同时进入关于同一组共享变量的临界区,也不是一定会发生错误。是否会发生错误与进程并发执行时的推进速度有关。不容许多个进程同时进入关于同一组共享变量的临界区,是保证正确性的要求。这件事的实现应由OS及并发程序设计者在编写程序时保证,这需要必要的互斥机制。使用嵌套的临界区时需特别注意,否则可能会发生不期望的后果。例如,shared x;shared y;region x do region y do (1)(2)region y do region x do 当进程P1执行到(1)、进程P2执行到(2)时,P1已进入关于x的临界区,要求进入关
10、于y的临界区,P2则反之。由于临界区是互斥的,因此二者均无法继续向前推进,这种现象称为死锁死锁(第五章)。4.2.3 进程互斥的实现进程互斥的实现 进程互斥的实现进程互斥的实现就是实现对临界区的管理。对临界区的管理对临界区的管理应满足如下管理原则管理原则:(进程互斥的Requirements)(1)正确性原则正确性原则(correctness):mutual exclusion 一次只允许一个进程活动在关于同一组公共 变量的临界区中。即任意时刻最多只能有一个进程处于关于同 一组共享变量的临界区中;(2)公平性原则公平性原则(fairness):bounded waiting 一个请求进入临界区
11、的进程应在有限时间内 获得进入该临界区的机会;(3)进展性原则进展性原则(progress):临界区空闲时,竞争进入临界区的多个进程 在有限时间内确定下一个进入临界区的进程。以上原则是对互斥的实现互斥的实现而言的。临界区的管 理实现后,使用时使用时,如果不慎可能会违背上述 原则。例如,临界区中的程序出现了死循环。临界区相当于一个独占型资源。对临界区资源的管理应满足如下调度原则调度原则:(1)当关于某一组共享变量的所有临界区均为空闲时,一个要求进入该组共享变量某一临界区的进程应能立即进入;(2)当关于某一组共享变量的某一临界区域被占用时,一个要求进入该组共享变量某一临界区域的进程应等待;(3)当
12、一个进程离开关于某一组共享变量的某一临界区时,应容许某一个等待进入关于该组共享变量某一临界区域的进程进入。完全用程序实现进程的互斥,不需特殊硬件指令的支持。可用于单CPU和多CPU环境中。有忙式等待忙式等待问题。Repeat critical section remainder sectionUntil falseentry sectionexit sectionFramework进程互斥的软件实现算法:Lamport面包店算法两种算法均假定系统中进程的个数有限,如n个实现进程互斥的软件的结构框架结构框架:面包店算法的基本思想来源于顾客在面包店购买面包时的排队原理。顾客进入面包店前,首先首先抓
13、一个号码抓一个号码,然后然后按号码由小到大的次序依次进按号码由小到大的次序依次进入面包店购买面包入面包店购买面包。这里假定:(1)面包店按由小到大由小到大的次序发放号码,且两个或两个以上的顾客有可能得到相同号码(要使顾客的号码不同,需互斥机制)。(2)若多个顾客抓到相同号码,则按顾客名字的字典次序排序(假定顾客没有重名)。计算机系统中,顾客相当于进程,每个进程有一个唯一的标识,用Pi,i=1,2,表示。对于Pi和Pj,若有ij,即Pi先进入临界区,则先为Pi服务。1.1.Lamport面包店算法面包店算法面包店算法的基本思想面包店算法的基本思想:首先设置一个发号器,按由小到大由小到大的次序发放
14、号码。进程进入临界区前先抓一个号码进程进入临界区前先抓一个号码,然后按号码由小到大的次序依次进入临界,然后按号码由小到大的次序依次进入临界区区。若多个进程抓到相同的号码,则按进程编号依次进入。实现面包店算法所需的数据结构实现面包店算法所需的数据结构:int choosingn;int numbern;或choosing:ARRAY 0.n-1 OF integer;number:ARRAY 0.n-1 OF integer;choosingn用来表示进程是否正在抓号,其初值均为0。若进程i正在抓号,则choosingi赋为1,否则choosingi为0。numbern用来记录进程抓到的号码,其
15、初值均为0。若numberi为0,则进程Pi没有抓号;若numberi不为0,则其正整数值为进程Pi抓到的号码。为便于面包店算法的描述为便于面包店算法的描述,引入下述表记法:引入下述表记法:设设(a,b):Pi,(c,d):Pj,则,则 (a,b)(c,d)iff(ac)or(a=c and bd)max(a0,an-1)=k:对所有的对所有的i,0 i n-1,kai,k为正整数。为正整数。算法4.1 Lamport面包店算法面包店算法do choosingi=1;numberi=max(number0,number1,numbern-1)+1;choosingi=0;for(j=0;jn;
16、j+)while(choosingj)skip;while(numberj0)&(numberj,j)(numberi,i)skip;临界区临界区 numberi=0;其余部分其余部分 while(1);(1)P1抓到1尚未赋值(2)P2抓到1(3)P3抓到2变量变量choosing的作用的作用 当进程Pi计算完max()+1但尚未将值尚未将值赋给numberi时,进程Pj中途插入,计算max()+1,得到相同的值。在这种情况下,choosingj保证编号较小的进程先进入临界区。忙式等待忙式等待:上述Lamport面包店算法中,若while循环的循环条件成立,则进程将重复测试,直到条件为假。实
17、际上,当while循环条件成立时,进程Pi不能向前推进,而在原地踏步原地踏步,这种原地踏步被称为忙式等待(busy waiting)。忙式等待空耗CPU资源,因而是低效的。验证面包店算法是否满足临界区管理原则验证面包店算法是否满足临界区管理原则:(1)正确性正确性:若进程Pj已在CS,而进程Pi(ij)拥有 与Pj不同的号,则(numberj,j)(numberi,i)。此时进程Pi若试图进入该临界区,则忙式等待忙式等待,直至进程Pj离开临界区。(2)公平性公平性:因进程按FIFO次序进入临界区,且进 程个数有限,故进程不会无限等待进入临界区。(3)进展性进展性:当多个进程竞争进入临界区时,下
18、述 条件之一成立:一个进程抓到最小号码;若干进程抓到最小号码。情形抓到最小 号码的进程获准进入临界区;情形抓到最小 号码且编号最小的进程获准进入临界区。因而 能在有限时间内确定进入临界区的进程。Eisenberg算法采用的数据结构算法采用的数据结构:enum flagn(idle,want_in,in_cs);int turn;/in the range of(0,n-1)int j;/in the range of(0,n-1)或 flag:ARRAY 0.n-1 OF(idle,want_in,in_cs);其中,flagi=idle:进程Pi不想进入临界区,flagi=want_in:进
19、程Pi想进入临界区,flagi=in_cs:进程Pi想进或已进临界区,flag的所有元素初值均为idle,turn的初值为0到n-1之间的任一正整数,j为每个进程拥有的一个局部变量,其初值为 0到n-1之间的任一正整数。2.2.Eisenberg/Mcguire 算法算法算法4.2 Eisenberg/Mcguire 算法算法do do flagi=want_in;j=turn;/turn表示允许进入CS的进程编号 while(j!=i)if(flagj!=!=idle)j=turn;else j=(j+1)%n;/mod flagi=in_cs;j=0;while(jvalue-;if(s-
20、value queue);asleep(s-queue):(1)将执行此操作的那个进程的PCB插入 s-queue所指PCB队列的尾部,其状态 由运行转为等待;(2)转到处理机调度程序。原语原语:一段不可间断执行的程序称为原语。说明:P操作对应申请资源。V操作操作原语原语的定义:void V(semaphore*s)s-value+;if(s-value queue);wakeup(s-queue):将s-queue所指队列首部的PCB取出 并将其插入就绪队列,其状态由等待 转为就绪。说明:V操作对应释放资源 使用信号灯变量的规定使用信号灯变量的规定:(1)必须置一次初值,只能置一次初值,且初
21、值 必需为非负整数:(2)只能执行P操作和V操作,其它操作均非法。关于信号灯变量关于信号灯变量 的几个有用结论的几个有用结论:(1)当s-valuevalue|为s-queue中 等待进程的个数;(2)当s-value0时,s-queue为空;(3)当s-value初值为初值为1,可用来实现进程互斥进程互斥。这只需在进入CS时执行一次P操作,离开CS 时执行一次V操作。(4)当s-value初值为初值为0,可用来实现进程同步进程同步。这只需在后进行的动作前后进行的动作前执行一次P操作,在先进行的动作后先进行的动作后执行一次V操作。(5)当s-value初值为正整数初值为正整数,可用来管理同种组
22、管理同种组 合资源合资源。使用资源前执行一次P操作(申请),用完后执行一次V操作(归还)。组合资源:若干相对独立的资源独立的资源构成的资源集 合,其中每个相对独立的资源称为子资源。同种组合资源:相同类型相同类型子资源构成的组合资源.对同种组合资源同种组合资源进行管理时 semaphore S=子资源个数;/初值例如,2台打印机 semaphore S=2;P(S);/申请 使用 V(S);/释放shared x,y,z:integer;CR1CR2CRn shared x,y,z:integer;P(mutex)P(mutex)P(mutex)CR1 CR2 CRnV(mutex)V(mute
23、x)V(mutex)semaphore mutex=1;semaphore mutex=1;终端1:终端2:CYCLE CYCLE 等待借书者;等待借书者;P(mutex)P(mutex)IF x=1 Then IF x=1 Then Begin Begin x:=x-1;x:=x-1;V(mutex)V(mutex)借书 借书 End End Else V(mutex);Else V(mutex);/无书 End End例例 图书借阅系统图书借阅系统 P(S)后动作后动作 先动作先动作 V(S)P1P2 例例 司机司机-售票员问题售票员问题 semaphore s1=0,s2=0;司机活动:
24、售票员活动:Repeat Repeat P(S1)关车门 启动车辆 V(S1)正常行驶 售 票 到站停车 P(S2)V(S2)开车门 Until false Until false2.信号灯与信号灯与PV操作的应用操作的应用 用信号灯与PV操作解决进程同步及互斥问题.(1)Producers and consumers problem (2)Readers and writers problem (3)Dining philosophers problem (4)Cigarette smokers problem (5)Sleepy barbers problem 例例1 生产者生产者-消费者
展开阅读全文