进程管理B互斥与同步.ppt

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 b4 a1 a2 a3 a4,3,顺序程序设计三个良好的特性：,（1）顺序性：处理机严格按照指令次序依次执行，即仅当一条指令执行完后才开始执行下一条指令； （2）封闭性：程序在执行过程中独占系统中的全部资源，该程序的运行环境只与其自身动作有关，不受其它程序及外界因素影响； （3）可再现性：程序的执行结果与执行速度无关，而只与初始条件有关，给定相同的初始条件，程序的任意多次执行一定得到相同的执行结果.,4,并发程序及其特性,程序的并发性包括如下两层含义: (1) 内部并发性, 对于一个进程来说, 它的所有指令可能按序执行，也可能不按次序执行; (2) 外部并发性: 对于多个进程来说, 所有进程是交叉(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)不可再现性：由于交叉的随机性，并发程序的多次执行可能对应不同的交叉，因而不能期望重新运行的程序能够再现上次运行的结果,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是进程，每个进程中语句执行顺序是不变的，而两个进程的语句是可以交叉执行的，它们以哪种方式交叉执行是不可预知的。,改进：将c处理成临界资源，让P1、P2互斥访问c，一个进程对于c的一次访问完毕，另一个进程才能访问，就不会出现这种情况。,8,与时间有关的错误,上述错误并不是一定发生的, 它与进程的推进速度有关. 即上述错误发生与否与进程P1和P2的推进速度有关, 而速度是时间的函数, 因而这种错误称为与时间有关的错误. 发生上述错误的原因在于两个进程P1和P2同时对于一个变量 C进行操作, 一个进程对C 的操作仅做了一部分, 另一个进程中途插入使得变量C处于一种不确定的状态, 用数据库的术语来说, 就是失去了变量C的数据完整性.,9,临界区critical section,进程访问临界资源的程序段称为临界区。 在一个系统中，可以用某些方法或某种机制保证进程对临界区的互斥访问，一个好的解决方案应该遵循以下条件： (1) 任何两个进程不能同时处于临界区内； (2) 进程在临界区外只作有限时间的等待； (3) 临界区外的进程不得阻塞其它进程进入临界区； (4) 等待临界区时, 释放CPU。,10,2.3 并发原理,在单处理机多道程序的系统中，进程的并发执行方式是插入执行，表面看起来进程如同是同时执行的。在多处理机系统中并发执行方式有插入执行和重叠执行。并发的存在要求操作系统必须能跟踪大量活跃进程,必须为每一活跃进程分配资源，必须保护每一进程的数据和物理资源不被其他进程侵犯，并且进程执行的结果与其他并发进程执行时的相对速度无关。,11,2.3 进程间相互联系与 相互作用,相互联系： （1）相关进程：在逻辑上具有某种联系的进程称作相关进程. （2）无关进程：在逻辑上没有任何联系的进程称作无关进程. 相互作用： （1）直接相互作用：进程之间不需要通过中间媒介而发生的相互作用，这种相互作用通常是有意识的. （2）间接相互作用：进程之间需要通过某种中间媒介而发生的相互作用，这种相互作用通常是无意识的.,12,2.3 进程间的相互竞争,并发进程在竞争使用同一资源时将产生冲突。进程间的竞争面临3个控制问题： 互斥 mutual exclusion(临界资源和临界段) 死锁 deadlock 饥饿 starvation 竞争的控制不可避免地涉及到操作系统，因为是操作系统分配资源，另外，进程自身也必须能以某种方式表达互斥的要求 。,13,2.3 进程间的相互合作,1.通过共享合作 这些进程并不是通过名字察觉到对方，而是通过共享访问间接察觉。进程间通过共享方式进行合作。除互斥、死锁和饥饿外，保证数据的一致性也是一个潜在的控制问题。,14,2.3 进程间的相互合作,2.通过通信合作 进程通信是指进程之间可直接以较高的效率传递较多数据的信息交换方式。这种方式中采用的是通信机构，在进程通信时往往以消息形式传递信息。因为在消息传递中不存在共享，所以这种形式的合作不需要互斥，但是还存在死锁和饥饿问题。,15,进程互斥的实现,实现进程互斥, 也就是实现对于临界区域的管理. 为了保证其管理的正确性和公平性, 应当满足下面三个管理原则: (1) 正确性原则(correctness)：任意时刻至多只能有一个进程处于关于同一组共享变量的临界区域之中； (2) 公平性原则(fairness)：一个请求进入临界区的进程应当在有限等待时间内获得进入该临界区的机会； (3) 进展性原则(progress)：当临界区空闲时，竞争进入临界区的多个进程在有限时间之内确定下一个进入临界区的进程. 对此资源的管理应当满足如下调度原则: (1) 当关于某一组共享变量的所有临界区域均为空闲时, 一个要求进入该组共享变量某一临界区域的进程应当能够立即进入; (2) 当关于某一组共享变量的某一临界区域被占用时, 一个要求进入该组共享变量某一临界区域的进程应当等待; (3) 当一个进程离开关于某一组共享变量的某一临界区域时, 应当容许某一个等待进入关于该组共享变量某一临界区域的进程进入.,16,Dijkstra成就,程序设计：结构化程序设计，goto有害 Os中并发程序设计，CS：what，why，how，P、V原语 网络：最短路径算法,17,Dijkstra成就,1965年提出解决CS问题4个基本准则： 1、不能虚设硬件指令或假设处理机数目，但可以认为基本的机器指令是不会被分割执行的。 2、不能假设n个进程的相对执行速度。 3、当一个进程未处于cs时，它不应阻止其它进程进入cs 4、当若干个进程欲进入cs时，os应在有限的时间内选择出一个进程进入其cs。,18,使用互斥的原则,由Dijkstra的四个基本准则可以导出： 有空让进 无空等待 多中择一 有限等待 让权等待,19,互斥软件解决方法,软件方法对并发进程不提供任何支持，因此，无论是系统程序或应用程序，进程都要同其他进程合作以解决互斥，它们从程序设计语言和操作系统那里得不到任何支持。软件方法易引起较高的进程附和较多的错误，但有利于深刻理解并发的复杂性。,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: =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种途径 这种方法保证了互斥但会导致死锁问题。,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; 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，那么它知道自己应该坚持并不时去查看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; turn: =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 procedure P1; P0; P1 begin parend repeat end.,28,Lamport面包店算法,该算法的基本思想源于顾客在面包店中购买面包时的排队原理. 顾客在进入面包店前, 首先抓一个号, 然后按照号码由小到大的次序依次进入面包店购买面包. 这里, 面包店发放的号码是由小到大的, 但是两个或两个以上的顾客却有可能得到相同的号码(使所抓号码不同需要互斥), 如果多个顾客抓到相同的号码, 则规定按照顾客名字的字典次序进行排序, 这里假定顾客是没有重名的. 在计算机系统中, 顾客就相当于进程, 每个进程有一个唯一的标识, 我们用P的下面加一个下标来表示. 例如: 对于 Pi和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, 对于所有i, 0in-1, kai.,30,Lamport面包店算法,do choosingi = 1; numberi=maxnumber0,number1,numbern-1+1; choosingi = 0; for(j = 0; j0) ,31,互斥硬件解决方法,完全利用软件方法来解决进程互斥进入临界区的问题有一定的难度，且有很大局限性，现在有许多计算机提供了一些可以解决临界区问题的特殊的硬件指令。硬件方法通过特殊的机器指令实现互斥，可以降低开销。,32,开关中断,开关中断是硬件实现进程互斥的一种特殊方法. 如果硬件提供了“关中断”和“开中断”指令, 则进程在进入临界区前只需执行一条“关中断”指令, 在离开临界区时只需执行一条“开中断”指令. 开关中断互斥算法 do 关中断 临界区 开中断 其余部分 while(1),33,禁止中断,优点： 在单处理机中可保证互斥。 实现效率高。 没有忙式等待问题。 简单易行。 缺点： 代价较高，使执行效率显著降低 在多处理机系统中，禁止中断不能保证互斥,34,使用机器指令,1.特殊的机器指令 在多处理机系统中，多个处理机共享一个共同的主存，这里并没有主/从关系，也没有实现互斥的中断机制。许多系统都提供了一些特殊的硬件指令，允许我们在一个存储周期内去测试和修改一个字的内容（Test and Set指令），或者交换两个字的内容（Exchange指令）等等。这些特殊指令可以用来解决临界段问题。,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 临界区代码 lock = 0; /退出临界区 .; /Pi 非临界区代码 如果lock当前的值为0，则将其赋值为1，进程进入临界区；否则lock当前值为1，则反复测试直到lock的值变为0. 显然这里也是忙式等待,37,硬件提供“交换”(swap)指令,“交换指令”将内存中两个单元(位)相互交换，该指令也是原子的，如果硬件提供了“交换”指令, 也可实现进程互斥.“交换”指令定义如下: void swap(int a, int b) int temp; temp = a; a = b; b = temp; 上述指令在执行时也是不可分割的, 即要求在一个指令周期内执行完. 为实现进程互斥, 对于每一组共享变量需要定义一个全局变量: int lock; 其初值为0. 对于每一个要求进入与该组共享变量相关临界区的进程, 需要定义一个局部变量: int key;,38,基于swap指令的互相斥算法,Swap 的应用 /lock为公用变量,初值为0(表临界资源空闲) /keyi为进程Pi的对应变量,初值为1表示要求进入临界区 void Pi( void ) while (1) keyi = 1; while( keyi != 0 ) swap( lock, keyi ); .; /Pi 临界区代码 lock = 0; /退出临界区 .; /Pi 非临界区代码 上面所述的两个进程互斥算法满足正确性要求的互斥性, 但是并不满足有限等待性. 为了使其满足有限等待性, 还需引入新的变量。,39,使用机器指令,优点： 可用于含有任意数量进程的单处理机或共享主存的多处理机； 比较简单，易于验证； 可支持多个临界段，每个临界段用各自的变量加以定义。 缺点： 采用busy-waiting技术，进程等待进入临界段时耗费处理机时间； 可能产生饥饿； 可能产生死锁。,40,公平性硬件互斥算法,do waitingi = 1; key = 1; while (waitingi 算法正确性的证明. 与软件方法相似，上述硬件互斥算法同样存在忙式等待问题,41,多处理机环境下的互斥,在单处理机环境中可以使用硬件提供的swap指令或test_and_set指令实现进程互斥，这些指令涉及对同一存储单元的两次或两次以上操作，这些操作将在几个指令周期内完成，但由于中断只能发生在两条机器指令之间，而同一指令内的多个指令周期不可中断，从而保证swap指令或test_and_set指令的执行不会交叉进行. 但在多处理机环境中情况有所不同，例如test_and_set指令包括“取”、“送”两个指令周期，两个CPU执行test_and_set(lock)可能发生指令周期上的交叉，假如lock初始为0, CPU1和CPU2可能分别执行完前一个指令周期并通过检测(均为0)，然后分别执行后一个指令周期将lock设置为1，结果都取回0作为判断临界区空闲的依据，从而不能实现互斥.,42,多处理机环境下互斥,内存,Word 1000 initial: 0,CPU1,CPU2,Bus,1. Read 0,3. Write 1,2. Read 0,4. Write 1,43,多处理机环境下互斥,为在多CPU环境中利用test_and_set指令实现进程互斥，硬件需要提供进一步的支持，以保证test_and_set指令执行的原子性. 这种支持目前多以“锁总线”(bus locking)的形式提供的，由于test_and_set指令对内存的两次操作都需要经过总线，在执行test_and_set指令之前锁住总线，在执行test_and_set指令后开放总线，即可保证test_and_set指令执行的原子性，用法如下： 多处理机互斥算法 do b=1; while(b) lock(bus); b = test_and_set( 其余部分 while(1) 显然这里存在忙式等待，这种锁被称为自旋锁. 自旋锁一般是低效的，但在多处理机系统中却是经常采用的互斥方法.,44,进程同步,进程同步是进程之间直接的相互作用形式, 是合作进程之间有意识的行为, 这种相互作用只发生在相关的进程之间.,45,进程同步的概念,为了引入进程同步的概念, 我们先看一个生活中同步的例子.设公共汽车上有一个司机和一个售票员,司机活动： 售票员活动： do do 启动车辆 关车门 正常行驶 售 票 到站停车 开车门 while(1) while(1),46,进程同步的概念,为了安全起见, 显然要求: (1)关车门后方能启动车辆; (2)到站停车后方能开车门. 亦即“启动车辆”这一活动应当在“关车门”这一活动之后, “开车门”这一活动应当在“到站停车”这一活动之后; (3)等待&唤醒.,47,进程同步,定义：一组进程, 为了协调其推进速度, 在某些点处需要相互等待与相互唤醒, 进程之间这种相互制约的关系称作进程同步，简称同步(synchronization). 定义：一组进程，如果它们单独不能正常进行, 但并发可以正常进行, 称这种现象为进程合作(cooperation). 参与合作的进程称作合作进程(cooperating process).,48,进程同步机制,定义：用于实现进程间同步的工具称作同步机制，亦称同步设施(synchronization mechanism). 目前, 人们已经研究出许多种用于进程之间同步的机制, 比较早期的如: 信号灯与PV操作、管程、条件临界区、路径表达式等, 这些都属于集中式系统中所使用的同步设施. . 一种同步机制应当满足如下几个基本要求: (1) 描述能力够用: 即用此种同步机制应当能够描述操作系统及并发程序设计中所遇到的各种同步问题 (例如生产者消费者问题、读者写者问题、哲学家就餐问题); (2) 可以实现; (3) 效率高; (4) 使用方便. 其中后面两个要求有时可能是冲突的.,49,2.3.2 信号量,信号灯与PV操作的定义 信号灯类型定义如下: typedef semaphore struct int value; pointer_to_PCB queue; 信号灯变量说明如下: semaphore s; 可见, 一个信号灯变量包括两个部分, 即值部分s.value 和指针部分s.queue. 在任意时刻, s.queue可能指向空, 也可能指向一个由进程PCB所构成队列的头部, 初始时它指向空.,50,信号量,P操作原语定义如下: void P(semaphore *s) s-value-; if(s-value queue); V操作原语定义如下: void V(semaphore *s) s-value+; if(s-value queue); 其中调用了asleep和wakeup两个标准过程, 它们的定义如下: asleep(s-queue): 执行此操作进程的PCB进入队列s-queue的尾部, 其状态由运行转为等待, 系统转到处理机调度程序. wakeup(s-queue): 将队列s-queue头部的进程的PCB由该队列中取出并将其排入就绪队列, 其状态由等待转为就绪.,51,S.value的初值表示系统中某类资源的数目， 因而又称为资源信号量，对它的每次P操作，意味着进程请求一个单位的该类资源，因此描述为S.value =S.value-1； 当S.value0时，表示该类资源已分配完毕，因此进程应调用block原语，进行自我阻塞，放弃处理机，并插入到信号量链表S.L中。可见，该机制遵循了“让权等待”准则。 此时S.value的绝对值表示在该信号量链表中已阻塞进程的数目。 对信号量的每次signal操作，表示执行进程释放一个单位资源，故S.value =S.value+1操作表示资源数目加1。 若加1后仍是S.value0，则表示在该信号量链表中，仍有等待该资源的进程被阻塞，故还应调用V原语，将S.L链表中的第一个等待进程唤醒。如果S.value的初值为1，表示只允许一个进程访问临界资源，此时的信号量转化为互斥信号量。,52,信号量,司机活动： 售票员活动： do do 启动车辆 关车门 正常行驶 售 票 到站停车 开车门 while(1) while(1),53,信号量,用信号量和 P、V操作解决这一问题，需要定义两个信号量，一个信号量start表示是否允许司机启动车辆，另一个信号量open表示是否允许售票员开车门。初始状态是车停在始发站，车门开着，等待乘客上车。因此，两个信号量的初值都是0。,54,信号量,关于信号灯变量的使用有如下两个基本要求: (1) 必需置一次初值, 只能置一次初值, (2)初值必需为非负整数; (3) 只能执行P操作和V操作, 所有其它操作均是非法的.,55,信号量,基于上述规定, 我们可以得到如下几个有用的结论: 当s-value0时, s-value为可用资源个数、不被阻塞的进程数，s-queue阻塞队列为空 ； 当s-valuevalue为s-queue中等待进程的个数; (3) 当s-value的初值为1时, 可以用来实现进程互斥, 这只需在进入临界区时执行一次P操作, 在离开临界区时执行一次V操作. (4) 当s-value的初值为正整数时，可以用来管理同种组合资源(具有多个实例的同种类资源，如5台打印机)，申请时执行一次P操作，归还时执行一次V 操作.,56,用信号量解决互斥问题,信号量的互斥算法可以用小屋模型来描述。除了黑板外，小屋中还有一个大冰箱。某进程进入小屋后执行wait操作将黑板上的数减1，这时，如果黑板上的值非负，它就进入临界段，反之它就进入冰箱内冬眠。这时，就允许另一进程进入小屋。当一个进程完成其临界段后，它进入小屋执行signal，将黑板上的值加1，这时如果黑板上的值为非正数，它就从冰箱中唤醒一个进程。,57,用信号量解决互斥问题,Var s:semaphore(:=1); Procedure P() repeat P(s); ; V(s); forever,58,用信号量解决生产者/消费者问题,问题描述如下：一个生产者生产出某种类型的数据(记录、字符)，并把它送入缓冲区(缓冲区为1)，惟一的一个消费者一次从缓冲区中取走一个数据。系统要保证缓冲区操作不发生重叠，即在任一时刻只能有一方(生产者或消费者)访问缓冲区。,59,例1. 唯一生产者、唯一消费者单缓冲区问题,1,箱子，容量1,生产者,消费者,生产物品 放入B中,B中取物品 消费之,60,例1. 唯一生产者、唯一消费者单缓冲区问题,Producer While(true) 生产一个产品； P(s1); 送入缓冲区； V(s2); s1=缓冲区空位数，初值1,Consumer While(true) P(s2); 缓冲区取一个产品； V(s1); 消费该产品； s2=产品数，初值0,61,用信号量解决生产者/消费者问题,问题描述如下：一个生产者生产出某种类型的数据(记录、字符)，并把它送入缓冲区(缓冲区为n) ，惟一的一个消费者一次从缓冲区中取走一个数据，系统要保证缓冲区操作不发生重叠，即在任一时刻只能有一方(生产者或消费者)访问缓冲区。,62,例2. 唯一生产者、唯一消费者多缓冲区问题,生产者,消费者,生产物品 放入B中,B中取物品 消费之,0 1 k-1,箱子，容量k B:Array0k-1Of item,63,环形缓冲区,1,0,K-1,in,(in+1)mod k,out,(out+1)mod k,64,例2. 唯一生产者、唯一消费者多缓冲区问题,in=0；/全局变量 Producer While(true) 生产一个产品； P(s1); 送入缓冲区bufferin； V(s2); in=(in+1)%n s1=缓冲区空位数，初值n,out=0；/全局变量 Consumer While(true) P(s2); 缓冲区bufferout取产品； V(s1); 消费该产品； out=(out+1)%n s2=产品数，初值0,65,用信号量解决生产者/消费者问题,问题描述如下：m个生产者生产出某种类型的数据(记录、字符)，并把它送入缓冲区(缓冲区为n) ，k个消费者一次从缓冲区中取走一个数据，系统要保证缓冲区操作不发生重叠，即在任一时刻只能有一方(生产者或消费者)访问缓冲区。,66,例3. 生产者/消费者问题,0 1 k-1,箱子，容量k B:Array0k-1Of item,生产者,消费者,生产物品 放入B中,B中取物品 消费之,67,例3. m生产者、k消费者n缓冲区，请问有错吗?,in=0；/全局变量 Producer While(true) 生产一个产品； P(s1); P(mutex); 送入缓冲区bufferin； V(mutex); V(s2); in=(in+1)%n s1=缓冲区空位数，初值n mutex=1,out=0；/全局变量 Consumer While(true) P(s2); P(mutex); 缓冲区bufferout取产品； V(mutex); V(s1); 消费该产品； out=(out+1)%n s2=产品数，初值0,68,例3. m生产者、k消费者n缓冲区正解,Program producers_consumers; Var B:Array0,k-1Of item; S1,S2,mutex:semaphore; in,out:0k-1;,Procedure producer cycle produce a product P(S1); P(mutex); Bin:=product; in:=(in+1)mod k; V(mutex); V(S2) end,Procedure consumer cycle P(s2); P(mutex); x:=Bout; out:=(out+1)mod k; V(mutex); V(S1); consume x; end;,69,程序,Begin S1.value:=k; S2.value:=0; mutex.value:=1; in:=0; out:=0; Cobegin P1: producer; , Pm: producer; C1: consumer; , Cn: consumer; Coend; End.,70,问题,2个P操作互换位置，可否？ 课本P117页第7题？,71,总结,P、V操作必须成对出现，有P必有V对应； 互斥-P、V在同一进程中出现； 同步-P、V不在同一进程中出现； 2个P操作在一起时，P的顺序至关重要，一个同步P与一个互斥P在一起时，同步P在互斥P前； 2个V操作顺序则无关紧要。,72,例4. 读者/写者问题,P. T. Courtois 1971 Communication of the ACM, Vol.14, 667-669. ACM: Association for Computing Machinery 解法1：读者优先 解法2：写者优先,73,例4.读者写者问题(readers and writers problem),Problem Statement: 一组公共数据DB R1 Rm W1 . Wn 设有一组共享数据DB和两组并发进程, 一组进程只对此组数据执行读操作, 另一组进程可对此组数据执行写操作(当然同时也可以执行读操作)，我们将前一组进程称作读者，后一组进程称作写者为了保证共享数据的完整性，要求： (1)多个读者的操作可以同时进行； (2) 多个写者的操作不可同时进行； (3) 任何读者与写者的操作不可同时进行,accessing,74,1、读者优先,如果有读者来时， （1）无读者和写者，新读者可以读； （2）如有写者等待，但有其他读者正在读，则新读者可以读； （3）有写者写，新读者则等待。,75,读者优先,Var wsem:semaphore; (initial value: 1) Writer： while(1) P(wsem); V(wsem); ,76,读者优先,int readCount = 0; semaphore wsem = 1; semaphore mutex = 1; reader()： while(1) P(mutex); readCount = readCount+1; if (readCount = 1) P(wsem); V(mutex);, P(mutex); readCount = readCount-1; if (readCount = 0) V(wsem); V(mutex); 变量wsem用来保证读者与写者之间的互斥，以及写者与写者之间的互斥；变量readCount用来记录读者的数目；变量mutex用来实现读者对于变量readCount访问的互斥.,读者等待在何处？ 读者如何被唤醒？,77,分析：,问题：读者源源不断，readcount不归0，写者会被饿死。这是不合理的，因为写者的操作是更新数据，应当优先进行，否则读者将读到已经过时的数据 策略：一旦有写者等待，新到达读者等待，正在读的读者都结束后，写者进入。,78,2、写者优先,如果有写者来时， （1）无读者，新写者可以写； （2）如有读者正在读，则新读者等待； （3）有其他写者正在写，新写者则等待。,79,2、写者优先,int writeCount = 0; semaphore wsem,rsem = 1; semaphore mutexY = 1; writer()： while(1) P(mutexY); writeCount = writeCount+1; if (writeCount = 1) P(rsem); V(mutexY); P(wsem);, V(wsem); P(mutexY); writeCount = writeCount-1; if (writeCount = 0) V(rsem); V(mutex); 变量wsem用来保证读者与写者之间的互斥，以及写者与写者之间的互斥；变量writeCount用来记录写者的数目；变量mutexY用来实现读者对于变量writeCount访问的互斥.,80,2、写者优先,int readCount = 0; semaphore wsem,rsem = 1; semaphore mutexX,mutex = 1; reader()： while(1) P(mutex); P(rsem); P(mutexX); readCount = readCount+1; if (readCount = 1) P(wsem); V(mutexX); V(rsem); V(mutex);, P(mutexX); readCount = readCount-1; if (readCount = 0) V(wsem); V(mutexX); 变量wsem用来保证读者与写者之间的互斥，以及写者与写者之间的互斥；变量readCount用来记录读者的数目；变量mutexX用来实现读者对于变量readCount访问的互斥;mutex用来实现rsem上不要有长的排队等待。,读者等待在何处？ 读者如何被唤醒？,81,AND型信号量,在两个进程中都要包含两个对Dmutex和Emutex的操作， 即 process A: process B: wait(Dmutex); wait(Emutex); wait(Emutex); wait(Dmutex); 若进程A和B按下述次序交替执行wait操作： process A: wait(Dmutex); 于是Dmutex=0 process B: wait(Emutex); 于是Emutex=0 process A: wait(Emutex); 于是Emutex=-1 A阻塞 process B: wait(Dmutex); 于是Dmutex=-1 B阻塞,82,AND同步机制的基本思想是：将进程在整个运行过程中需要的所有资源，一次性全部地分配给进程，待进程使用完后再一起释放。只要尚有一个资源未能分配给进程，其它所有可能为之分配的资源，也不分配给他。亦即，对若干个临界资源的分配，采取原子操作方式：要么全部分配到进程，要么一个也不分配。 由死锁理论可知，这样就可避免上述死锁情况的发生。为此，在P操作中，增加了一个“AND”条件，故称为AND同步，或称为同时P操作， 即Swait(Simultaneous wait)定义如下：,83,S.value的初值表示系统中某类资源的数目， 因而又称为资源信号量，对它的每次P操作，意味着进程请求一个单位的该类资源，因此描述为S.value =S.value-1； 当S.value0时，表示该类资源已分配完毕，因此进程应调用block原语，进行自我阻塞，放弃处理机，并插入到信号量链表S.L中。可见，该机制遵循了“让权等待”准则。 此时S.value的绝对值表示在该信号量链表中已阻塞进程的数目。 对信号量的每次signal操作，表示执行进程释放一个单位资源，故S.value =S.value+1操作表示资源数目加1。 若加1后仍是S.value0，则表示在该信号量链表中，仍有等待该资源的进程被阻塞，故还应调用V原语，将S.L链表中的第一个等待进程唤醒。如果S.value的初值为1，表示只允许一个进程访问临界资源，此时的信号量转化为互斥信号量。,84,Swait(S1, S2, , Sn) if Si1 and and Sn1 then for (i=1;i=n;i+) Si=Si-1; endfor/满足资源要求时，才进行减操作； else /调用进程进入第一个小于1的信号量的等待队列，阻塞该进程 endif,85,Ssignal,Ssignal(S1, S2, , Sn) for (i=1;i=n;i+)Si=Si+1; for (在Si.queue中等待的每一个进程P) 从等待队列中Si.queue中取出进程P； if(判断该进程是否通过Swait中的测试) 通过，进程P进入就绪队列； else 进程P进入某个等待队列； ,86,信号量集,Swait(S, t, d)；Ssignal(s,d) S：信号量 t：测试值 d：占用值,87,一般“信号量集”的几种特殊情况： (1) Swait(S, d, d)。 此时在信号量集中只有一个信号量S， 但允许它每次申请d个资源，当现有资源数少于d时，不予分配。 (2) Swait(S, 1, 1)。 此时的信号量集已蜕化为一般的记录型信号量(S1时)或互斥信号量(S=1时)。 (3) Swait(S, 1, 0)。这是一种很特殊且很有用的信号量操作。当S1时，允许多个进程进入某特定区；当S变为0后，将阻止任何进程进入特定区。换言之，它相当于一个可控开关。,88,在生产者消费者问题中应注意：首先，在每个程序中用于实现互斥的wait(mutex)和signal(mutex)必须成对地出现； 其次，对资源信号量empty和full的wait和signal操作，同样需要成对地出现，但它们分别处于不同的程序中。,利用AND信号量解决生产者消费者问题,89,2. 利用AND信号量解决生产者消费者问题,ar mutex, empty, full:semaphore =1, n, 0; buffer:array0, , n-1 of item; in out:integer =0, 0; begin parbegin producer:begin repeat produce an item in nextp; Swait(empty, mutex); buffer(in) =nextp; in =(in+1)mod n; Ssignal(mutex, full); until false; end,90,consumer:begin repeat Swait(empty, mutex); nextc =buffer(out); out =(out+1) mod