第2章进程管理B互斥与同步.ppt
《第2章进程管理B互斥与同步.ppt》由会员分享,可在线阅读,更多相关《第2章进程管理B互斥与同步.ppt(127页珍藏版)》请在三一文库上搜索。
1、1,第2、3章 进程管理B 互斥与同步,本章知识点: 并发原理 互斥软件解决方法 互斥硬件解决方法 2.3 进程同步 管程 2.5 进程通讯 2.4 经典进程的同步问题,2,顺序程序及其特性,程序的顺序性包括如下两层含义: (1) 内部顺序性, 对于一个进程来说, 它的所有指令是按序执行的; (2) 外部顺序性, 对于多个进程来说, 所有进程是依次执行的; 例如, 假设有P1和P2两个进程, 其活动分别为: P1活动: a1 a2 a3 a4 P2活动: b1 b2 b3 b4 顺序执行时, 有如下两种情形: 情形1: a1 a2 a3 a4 b1 b2 b3 b4 情形2: b1 b2 b3
2、 b4 a1 a2 a3 a4,3,顺序程序设计三个良好的特性:,(1)顺序性:处理机严格按照指令次序依次执行,即仅当一条指令执行完后才开始执行下一条指令; (2)封闭性:程序在执行过程中独占系统中的全部资源,该程序的运行环境只与其自身动作有关,不受其它程序及外界因素影响; (3)可再现性:程序的执行结果与执行速度无关,而只与初始条件有关,给定相同的初始条件,程序的任意多次执行一定得到相同的执行结果.,4,并发程序及其特性,程序的并发性包括如下两层含义: (1) 内部并发性, 对于一个进程来说, 它的所有指令可能按序执行,也可能不按次序执行; (2) 外部并发性: 对于多个进程来说, 所有进程
3、是交叉(interleave)执行的. 例如, 对于上面P1和P2两个进程来说, 只考虑外部并发性,具有许多情形, 如: 情形1: a1 b1 b2 a2 a3 b3 a4 b4 情形2: b1 b2 a1 a2 a3 b3 b4 a4 并发进程在其执行过程中, 出现哪种交叉情形是不可预知的, 这就是并发程序带来的不确定性,5,并发程序三个特性,(1)交叉性:程序并发执行对应某一种交叉,不同的交叉可能导致不同的计算结果,操作系统应当保证只产生导致正确结果的交叉,去除那些可能导致不正确结果的交叉. (2)非封闭性:一个进程的运行环境可能被其它进程所改变,从而相互影响 (3)不可再现性:由于交叉的
4、随机性,并发程序的多次执行可能对应不同的交叉,因而不能期望重新运行的程序能够再现上次运行的结果,6,与时间有关的错误,若有两个进程P1、P2,共享一个公用变量c,初值为8,P1、P2所做工作如下: P1(退票) P2(售票) L1:a = c; L4:b = c; L2:a = a+1; L5:b = b-1; L3:c = a; L6:c = b;,7,与时间有关的错误,试看下述两种执行情况: (1) 若语句执行顺序为L1,L2,L3,L4,L5,L6,则c = 8; (2) 若语句执行顺序为L1,L2,L4,L5,L3,L6,则c = 7。 显然,上述结果是不能令人满意的。P1、P2是进程
5、,每个进程中语句执行顺序是不变的,而两个进程的语句是可以交叉执行的,它们以哪种方式交叉执行是不可预知的。,改进:将c处理成临界资源,让P1、P2互斥访问c,一个进程对于c的一次访问完毕,另一个进程才能访问,就不会出现这种情况。,8,与时间有关的错误,上述错误并不是一定发生的, 它与进程的推进速度有关. 即上述错误发生与否与进程P1和P2的推进速度有关, 而速度是时间的函数, 因而这种错误称为与时间有关的错误. 发生上述错误的原因在于两个进程P1和P2同时对于一个变量 C进行操作, 一个进程对C 的操作仅做了一部分, 另一个进程中途插入使得变量C处于一种不确定的状态, 用数据库的术语来说, 就是
6、失去了变量C的数据完整性.,9,临界区critical section,进程访问临界资源的程序段称为临界区。 在一个系统中,可以用某些方法或某种机制保证进程对临界区的互斥访问,一个好的解决方案应该遵循以下条件: (1) 任何两个进程不能同时处于临界区内; (2) 进程在临界区外只作有限时间的等待; (3) 临界区外的进程不得阻塞其它进程进入临界区; (4) 等待临界区时, 释放CPU。,10,2.3 并发原理,在单处理机多道程序的系统中,进程的并发执行方式是插入执行,表面看起来进程如同是同时执行的。在多处理机系统中并发执行方式有插入执行和重叠执行。并发的存在要求操作系统必须能跟踪大量活跃进程,
7、必须为每一活跃进程分配资源,必须保护每一进程的数据和物理资源不被其他进程侵犯,并且进程执行的结果与其他并发进程执行时的相对速度无关。,11,2.3 进程间相互联系与 相互作用,相互联系: (1)相关进程:在逻辑上具有某种联系的进程称作相关进程. (2)无关进程:在逻辑上没有任何联系的进程称作无关进程. 相互作用: (1)直接相互作用:进程之间不需要通过中间媒介而发生的相互作用,这种相互作用通常是有意识的. (2)间接相互作用:进程之间需要通过某种中间媒介而发生的相互作用,这种相互作用通常是无意识的.,12,2.3 进程间的相互竞争,并发进程在竞争使用同一资源时将产生冲突。进程间的竞争面临3个控
8、制问题: 互斥 mutual exclusion(临界资源和临界段) 死锁 deadlock 饥饿 starvation 竞争的控制不可避免地涉及到操作系统,因为是操作系统分配资源,另外,进程自身也必须能以某种方式表达互斥的要求 。,13,2.3 进程间的相互合作,1.通过共享合作 这些进程并不是通过名字察觉到对方,而是通过共享访问间接察觉。进程间通过共享方式进行合作。除互斥、死锁和饥饿外,保证数据的一致性也是一个潜在的控制问题。,14,2.3 进程间的相互合作,2.通过通信合作 进程通信是指进程之间可直接以较高的效率传递较多数据的信息交换方式。这种方式中采用的是通信机构,在进程通信时往往以消
9、息形式传递信息。因为在消息传递中不存在共享,所以这种形式的合作不需要互斥,但是还存在死锁和饥饿问题。,15,进程互斥的实现,实现进程互斥, 也就是实现对于临界区域的管理. 为了保证其管理的正确性和公平性, 应当满足下面三个管理原则: (1) 正确性原则(correctness):任意时刻至多只能有一个进程处于关于同一组共享变量的临界区域之中; (2) 公平性原则(fairness):一个请求进入临界区的进程应当在有限等待时间内获得进入该临界区的机会; (3) 进展性原则(progress):当临界区空闲时,竞争进入临界区的多个进程在有限时间之内确定下一个进入临界区的进程. 对此资源的管理应当满
10、足如下调度原则: (1) 当关于某一组共享变量的所有临界区域均为空闲时, 一个要求进入该组共享变量某一临界区域的进程应当能够立即进入; (2) 当关于某一组共享变量的某一临界区域被占用时, 一个要求进入该组共享变量某一临界区域的进程应当等待; (3) 当一个进程离开关于某一组共享变量的某一临界区域时, 应当容许某一个等待进入关于该组共享变量某一临界区域的进程进入.,16,Dijkstra成就,程序设计:结构化程序设计,goto有害 Os中并发程序设计,CS:what,why,how,P、V原语 网络:最短路径算法,17,Dijkstra成就,1965年提出解决CS问题4个基本准则: 1、不能虚
11、设硬件指令或假设处理机数目,但可以认为基本的机器指令是不会被分割执行的。 2、不能假设n个进程的相对执行速度。 3、当一个进程未处于cs时,它不应阻止其它进程进入cs 4、当若干个进程欲进入cs时,os应在有限的时间内选择出一个进程进入其cs。,18,使用互斥的原则,由Dijkstra的四个基本准则可以导出: 有空让进 无空等待 多中择一 有限等待 让权等待,19,互斥软件解决方法,软件方法对并发进程不提供任何支持,因此,无论是系统程序或应用程序,进程都要同其他进程合作以解决互斥,它们从程序设计语言和操作系统那里得不到任何支持。软件方法易引起较高的进程附和较多的错误,但有利于深刻理解并发的复杂
12、性。,20,Dekker算法,Dekker算法的优点在于它描述了并发进程发展过程中遇到的大部分共同问题。任何互斥都必须依赖于一些硬件上的基本约束,其中最基本的约束是任一时刻只能有一个进程访问内存中某一位置。,21,Dekker算法,1.第1种途径 这种方法保证了互斥,但它只记住了允许哪个进程进入其临界段,未记住每个进程的状态。,var turn: 01; turn为共享的全局变量 PROCESS 0 PROCESS 1 while turn0 do nothing while turn1 do nothing;critical section; critical section; turn:
13、=1; turn: =0; ,22,Dekker算法,2.第2种途径 这种解决方法依赖于进程执行的相对速度,共享的全局变量是:var flag: array01of boolean; 它被初始化为false PROCESS 0 PROCESS 1 while flag1do nothing; while flag0do nothing; flag0: =true; flag1: =true; critical section; critical section; flag0: =false; flag1: =false; ,23,Dekker算法,3.第3种途径 这种方法保证了互斥但会导致死锁
14、问题。,PROCESS 0 PROCESS 1 flag0: =true; flag1: =true; while flag1 do nothing; while flag0 do nothing; critical section; critical section; flag0: =false; flag1: =false; ,24,Dekker算法,4.第4种途径,PROCESS 0 PROCESS 1 flag0: =true; flag1: =true; while flag1 while flag0 begin begin flag0: =false; flag1: =false;
15、 delay for a short time; delay for a short time; flag0: =true; flag1: =true; end; end; critical section; critical section; flag0: =false; flag1: =false; ,25,Dekker算法,5.一个正确的解决方法 设计一个“指示”小屋,小屋内的黑板标明“turn”,当P0想进入其临界段时,置自己的flag为“true”,这时它去查看P1的flag,如果是“false”,则P0就立即进入自己的临界段,反之P0去查看“指示”小屋,如果turn=0,那么它知道
16、自己应该坚持并不时去查看P1的小屋, P1将觉察到它应该放弃并在自己的黑板上写上“false”,以允许P0继续执行。 P0执行完临界段后,它将flag置为“false”以释放临界段,并且将turn置为1,将进入权交给P1 。,26,Peterson算法,Dekker算法可以解决互斥问题,但是,其复杂的程序难于理解,其正确性难于证明。Peterson给出了一个简单的方法。下面是一个两进程互斥的简单解决方法,进一步可将Peterson算法推广到多个进程的情况。,27,Peterson算法,var flag: array01 of boolean; flag1: =true; turn: 01; t
17、urn: =0; procedure P0; while flag0 and turn=0 do nothing; begin critical section; repeat flag1: =false; flag0: =true; remainder turn: =1; forever while flag1 and turn=1 do nothing; end; critical section; begin flag0: =false; flag0: =false; remainder flag1: =false; forever turn: =1; end; parbegin pro
18、cedure P1; P0; P1 begin parend repeat end.,28,Lamport面包店算法,该算法的基本思想源于顾客在面包店中购买面包时的排队原理. 顾客在进入面包店前, 首先抓一个号, 然后按照号码由小到大的次序依次进入面包店购买面包. 这里, 面包店发放的号码是由小到大的, 但是两个或两个以上的顾客却有可能得到相同的号码(使所抓号码不同需要互斥), 如果多个顾客抓到相同的号码, 则规定按照顾客名字的字典次序进行排序, 这里假定顾客是没有重名的. 在计算机系统中, 顾客就相当于进程, 每个进程有一个唯一的标识, 我们用P的下面加一个下标来表示. 例如: 对于 Pi和
19、Pj, 如果有ij, 则先为Pi服务, 即Pi先进入临界区.,29,Lamport面包店算法,该算法的实现需要如下两个数据结构: int choosingn; int numbern; 前者表示进程是否正在抓号,正在抓号的进程choosingi为1,否则为0, 其初值均为0. 后者用来记录各个进程所抓到的号码, 如numberi为0, 则进程Pi没有抓号, 如numberi不为0, 则其正整数值为进程Pi所抓到的号码, 其初值均为0. 为了方便起见, 我们定义下述表记法: (a,b)(c,d) 如果 ac or (a=c and bd). max(a0,an-1) 其值为一正整数k, 对于所有
20、i, 0in-1, kai.,30,Lamport面包店算法,do choosingi = 1; numberi=maxnumber0,number1,numbern-1+1; choosingi = 0; for(j = 0; j0) ,31,互斥硬件解决方法,完全利用软件方法来解决进程互斥进入临界区的问题有一定的难度,且有很大局限性,现在有许多计算机提供了一些可以解决临界区问题的特殊的硬件指令。硬件方法通过特殊的机器指令实现互斥,可以降低开销。,32,开关中断,开关中断是硬件实现进程互斥的一种特殊方法. 如果硬件提供了“关中断”和“开中断”指令, 则进程在进入临界区前只需执行一条“关中断”
21、指令, 在离开临界区时只需执行一条“开中断”指令. 开关中断互斥算法 do 关中断 临界区 开中断 其余部分 while(1),33,禁止中断,优点: 在单处理机中可保证互斥。 实现效率高。 没有忙式等待问题。 简单易行。 缺点: 代价较高,使执行效率显著降低 在多处理机系统中,禁止中断不能保证互斥,34,使用机器指令,1.特殊的机器指令 在多处理机系统中,多个处理机共享一个共同的主存,这里并没有主/从关系,也没有实现互斥的中断机制。许多系统都提供了一些特殊的硬件指令,允许我们在一个存储周期内去测试和修改一个字的内容(Test and Set指令),或者交换两个字的内容(Exchange指令)
22、等等。这些特殊指令可以用来解决临界段问题。,35,硬件提供“测试并建立” (test and set)指令,“测试并建立”指令实质上是取出内存某一单元(位)的值,然后再给该单元(位)赋一个新值该指令在执行时是不可被分割的, 即原子的(atomic). 硬件“测试并建立”指令定义如下: int test_and_set(int ,36,基于TS指令的互斥算法,Test-and-Set 的应用 /lock为被测试变量,初值为0,互斥进程Pi(i=1,2.n)调用TS void Pi( void ) while (1) while( Test_and_Set( lock); .; /Pi 临界区代码
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 进程 管理 同步
链接地址:https://www.31doc.com/p-2986794.html