进程管理part3.pptx

第二章 进 程 管 理 Heb Nomal University Department of Computer Science12.3 进进 程程 同同 步步 2.3.1 进程同步的基本概念进程同步的基本概念 1.两种形式的制约关系两种形式的制约关系(1)间接相互制约关系。(2)直接相互制约关系。第二章 进 程 管 理 Heb Nomal University Department of Computer Science22.临界资源临界资源(Critical Resouce)生生产产者者-消消费费者者(producer-consumer)问问题题是一个著名的进程同步问题。它描述的是：有有一一群群生生产产者者进进程程在在生生产产产产品品，并将这些产品提供给消费者进程去消费。并将这些产品提供给消费者进程去消费。为为使使生生产产者者进进程程与与消消费费者者进进程程能能并并发发执执行行，在在两两者者之之间间设设置置了了一一个个具具有有n个个缓缓冲冲区区的的缓缓冲冲池池，生生产产者者进进程程将将它它所所生生产产的的产产品品放放入入一一个个缓缓冲冲区区中中；消消费费者者进进程程可可从从一一个个缓缓冲冲区区中中取取走走产产品品去去消消费费。尽尽管管所所有有的的生生产产者者进进程程和和消消费费者者进进程程都都是是以以异异步步方方式式运运行行的的，但但它它们们之之间间必必须须保保持持同同步步，即即不不允允许许消消费费者者进进程程到到一一个个空空缓缓冲冲区区去去取取产产品品；也也不不允允许许生生产产者者进进程程向向一一个个已已装装满满产产品品且且尚尚未未被被取取走走的的缓缓冲冲区中投放产品。区中投放产品。第二章 进 程 管 理 Heb Nomal University Department of Computer Science3Var n,integer;type item=;var buffer:array 0,1,n-1 of item;in,out:0,1,n-1;counter:0,1,n;指针指针in和和out初始化为初始化为1。我们可利用一个数数组组来表示上述的具有n个(0，1，n-1)缓冲区的缓冲池。用输输入入指指针针in来指示下一个可投放产品的缓冲区，每当生产者进程生产并投放一个产品后，输入指针加1；用一个输输出出指指针针out来指示下一个可从中获取产品的缓冲区，每当消费者进程取走一个产品后，输出指针加1。由于这里的缓冲池是组织成循环缓冲的，故应把输输入入指指针针加加1表示成 in=(in+1)mod n；输输出出指指针针加加1表示成out=(out+1)mod n。当当(in+1)mod n=out时时表表示示缓缓冲冲池池满满；而而in=out则则表表示示缓缓冲冲池空。池空。此外，还引入了一个整整型型变变量量counter,其初始值为0。每当生产者进程向缓冲池中投放一个产品后，使counter加1；反之，每当消费者进程从中取走一个产品时，使counter减1。生产者和消费者两进程共享下面的变量：第二章 进 程 管 理 Heb Nomal University Department of Computer Science4producer:repeat produce an item in nextp;while counter=n do no-op;bufferin =nextp;in =in+1 mod n;counter =counter+1;until false;consumer:repeat while counter=0 do no-op;nextc =bufferout;out =(out+1)mod n;counter =counter-1;consumer the item in nextc;until false;指针指针in和和out初始化为初始化为1。在生产者和消费者进程的描述中，在生产者和消费者进程的描述中，no-op是一条空操作指令，是一条空操作指令，while condition do no-op语句表示重复的测语句表示重复的测试条件试条件(condication)，重复测试应进，重复测试应进行到该条件变为行到该条件变为false(假假)，即到该条，即到该条件不成立时为止件不成立时为止在生产者进程中使用一局部变在生产者进程中使用一局部变量量nextp，用于暂时存放每次刚，用于暂时存放每次刚生产出来的产品；而在消费者生产出来的产品；而在消费者进程中，则使用一个局部变量进程中，则使用一个局部变量nextc,用于存放每次要消费的用于存放每次要消费的产品产品第二章 进 程 管 理 Heb Nomal University Department of Computer Science5 虽虽然然上上面面的的生生产产者者程程序序和和消消费费者者程程序序，在在分分别别看看时时都都是是正正确确的的，而而且且两两者者在在顺顺序序执执行行时时其其结结果果也也会会是是正正确确的的，但但若若并并发发执执行行时时，就就会会出出现现差差错错，问问题题就就在在于于这这两两个个进进程程共共享享变变量量counter。生生产产者者对对它它做做加加1操操作作，消消费费者者对对它它做做减减1操操作作，这这两两个个操操作作在在用用机机器器语语言言实实现现时时，常常可可用用下下面面的形式描述：的形式描述：register 1=counter;register1 =register 1+1;counter =register 1;register 2 =counter;register 2 =register 2-1;counter =register 2;Memory5counterregister 1register 25665 65第二章 进 程 管 理 Heb Nomal University Department of Computer Science6 假假设设：counter的的当当前前值值是是5。如如果果生生产产者者进进程程先先执执行行左左列列的的三三条条机机器器语语言言语语句句，然然后后消消费费者者进进程程再再执执行行右右列列的的三三条条语语句句，则则最最后后共共享享变变量量counter的的值值仍仍为为5；反反之之，如如果果让让消消费费者者进进程程先先执执行行右右列列的的三三条条语语句句，然然后后再再让让生生产产者者进进程程执执行左列的三条语句，行左列的三条语句，counter值也还是值也还是5。但是，如果按下述顺序执行：但是，如果按下述顺序执行：register 1 =counter;(register 1=5)register 1 =register 1+1;(register 1=6)register 2 =counter;(register 2=5)register 2 =register 2-1;(register 2=4)counter =register 1;(counter=6)counter =register 2;(counter=4)Memory5counterregister 1register 255646 4第二章 进 程 管 理 Heb Nomal University Department of Computer Science73.临界区临界区(critical section)可把一个访问临界资源的循环进程描述如下：repeat critical section;remainder section;until false;entry sectionexit section第二章 进 程 管 理 Heb Nomal University Department of Computer Science84.同步机制应遵循的规则同步机制应遵循的规则(1)空闲让进。空闲让进。(2)忙则等待。忙则等待。(3)有限等待。有限等待。(4)让权等待。让权等待。第二章 进 程 管 理 Heb Nomal University Department of Computer Science补充：补充：使用信号量之前，进程使用信号量之前，进程互斥互斥方法：方法：l 软件方法软件方法l 硬件方法硬件方法硬件解法硬件解法 (1)“(1)“测试并设置测试并设置”指令指令硬件解法硬件解法 (2)“(2)“交换交换”指令指令硬件解法（硬件解法（3 3）“开关中断开关中断”指令指令 软件方法基本思路软件方法基本思路在进入区检查和设置一些标志，如果已有进程在临在进入区检查和设置一些标志，如果已有进程在临界区，则在进入区通过循环检查进行等待；在退出界区，则在进入区通过循环检查进行等待；在退出区修改标志区修改标志 主要问题是主要问题是设置什么标志设置什么标志和和如何检查标志如何检查标志第二章 进 程 管 理 Heb Nomal University Department of Computer Science 算法算法1：单标志位：单标志位 设有两个进程设有两个进程Pi,PjPi,Pj，其中，其中PiPi进程设立一个进程设立一个公用整型公用整型变量变量 turnturn，用来描述允许进入临界区的进程标识。，用来描述允许进入临界区的进程标识。在进入区循环检查是否允许本进程进入在进入区循环检查是否允许本进程进入turnturn为为i i时，进程时，进程PiPi可进入可进入在退出区修改允许进入进程标识在退出区修改允许进入进程标识进程进程PiPi退出时，改退出时，改turnturn为进程为进程PjPj的标识的标识j j；第二章 进 程 管 理 Heb Nomal University Department of Computer Science(b)(a)while(TRUE)while(turn!=1)/*循环*/;critical_region();turn=0;noncritical_region();while(TRUE)while(turn!=0)/*循环*/;critical_region();turn=1;noncritical_region();缺点：进程强制轮流进入临界区，容易造成资源利用不充分。如：在Pi让出临界区之后，Pj使用临界区之前，Pi不可能再次使用临界区。第二章 进 程 管 理 Heb Nomal University Department of Computer Science算法算法2 2：双标志法（先检查）双标志法（先检查）设立一个标志数组设立一个标志数组flagflag：描述进程是否在临界区，初值：描述进程是否在临界区，初值均为均为FALSEFALSE。先检查，后修改先检查，后修改 在进入区检查另一个进程是否在临界区，不在在进入区检查另一个进程是否在临界区，不在时修改本进程在临界区的标志；时修改本进程在临界区的标志；在退出区修改本进程在临界区的标志；在退出区修改本进程在临界区的标志；第二章 进 程 管 理 Heb Nomal University Department of Computer Science优点优点 不用交替进入，可连续使用不用交替进入，可连续使用缺点缺点 Pi和和Pj可能同时进入临界区可能同时进入临界区 如：按下面序列执行时，会同时进入：如：按下面序列执行时，会同时进入：“Pi Pj Pi Pj”。即在检查对方即在检查对方flag之后和切换自己之后和切换自己flag之前有一段时之前有一段时间间，结果都检查通过。，结果都检查通过。问题出在：检查和修改操作不能连续进行。问题出在：检查和修改操作不能连续进行。第二章 进 程 管 理 Heb Nomal University Department of Computer Science算法算法3 3：双标志法（先修改）双标志法（先修改）类似于算法类似于算法2 2，区别在于，区别在于先修改后检查先修改后检查优点优点 防止两个进程同时进入临界区防止两个进程同时进入临界区缺点：缺点：Pi和和Pj可能都进入不了临界区可能都进入不了临界区 如：按下面序列执行时，都进不了临界区：如：按下面序列执行时，都进不了临界区：“Pi Pj Pi Pj”。即在切换自己。即在切换自己flag之后和检查对方之后和检查对方flag之前之前有一段时间，结果都切换有一段时间，结果都切换flag，都检查不通过。，都检查不通过。第二章 进 程 管 理 Heb Nomal University Department of Computer Science荷兰数学家荷兰数学家T.Dekker通过将通过将轮换法轮换法和和锁变量锁变量以及以及警告变量警告变量的思想相结合，最先提出了一的思想相结合，最先提出了一个不需要严格轮换的互斥算法的软件方案。个不需要严格轮换的互斥算法的软件方案。关于关于Dekker的算法，请参阅的算法，请参阅(DUkstra，1965)。1981年，年，G.L.Petterson发现了一种实现互发现了一种实现互斥的简单方法，这使得斥的简单方法，这使得Dekker的方法遭到废的方法遭到废弃。弃。第二章 进 程 管 理 Heb Nomal University Department of Computer Science算法算法4 4：结合算法结合算法1 1和算法和算法3 3，是正确的算法，是正确的算法 先修改、后检查、后修改者等待先修改、后检查、后修改者等待turn=j;turn=j;描述可进入的进程（同时修改标志时描述可进入的进程（同时修改标志时）在进入区先修改后检查，并检查并发修改的先后在进入区先修改后检查，并检查并发修改的先后检查对方检查对方flagflag，如果不在临界区则自己进入，如果不在临界区则自己进入空闲则入空闲则入否则再检查否则再检查turnturn：保存的是较晚的一次赋值，则较晚的进：保存的是较晚的一次赋值，则较晚的进程等待，较早的进程进入程等待，较早的进程进入先到先入，后到等待先到先入，后到等待PetersonPeterson算法算法 软件算法存在如下缺点：软件算法存在如下缺点：忙等待忙等待实现过于复杂，需要高的编程技巧实现过于复杂，需要高的编程技巧第二章 进 程 管 理 Heb Nomal University Department of Computer Science全国联考全国联考2010 进程进程P0和和P1的共享变量定义及其初值为：的共享变量定义及其初值为：boolean falg2;int turn=0;falg0=FALSE;falg1=FALSE;若进程若进程P0和和P1访问临界资源的类访问临界资源的类C伪代码实现如下：伪代码实现如下：void P0()/进程进程P0while(TRUE)flag0=TRUE;turn=1;while(flag1&turn=1);临界区临界区;flag0=FALSE;void P1()/进程进程P1while(TRUE)flag1=TRUE;turn=0;while(flag0&turn=0);临界区临界区;flag1=FALSE;则并发执行进程则并发执行进程P0和和P1时产生的情形是时产生的情形是A.不能保证进程互斥进入临界区、会出现不能保证进程互斥进入临界区、会出现“饥饿饥饿”现象现象B.不能保证进程互斥进入临界区、不会出现不能保证进程互斥进入临界区、不会出现“饥饿饥饿”现象现象C.能保证进程互斥进入临界区、会出现能保证进程互斥进入临界区、会出现“饥饿饥饿”现象现象D.能保证进程互斥进入临界区、不会出现能保证进程互斥进入临界区、不会出现“饥饿饥饿”现象现象第二章 进 程 管 理 Heb Nomal University Department of Computer Science182.3.2 信号量机制信号量机制 1.整型信号量整型信号量 最初由Dijkstra把整型信号量定义为一个整型量，除初始化外，仅能通过两个标准的原子操作(Atomic Operation)wait(S)和signal(S)来访问。这两个操作一直被分别称为P、V操作。wait和signal操作可描述为：wait(S):while S0 do no-op S=S-1;signal(S):S=S+1;第二章 进 程 管 理 Heb Nomal University Department of Computer Science19 2.记录型信号量记录型信号量 在整型信号量机制中的wait操作，只要是信号量S0，就会不断地测试。因此，该机制并未遵循“让权等待”的准则，而是使进程处于“忙等忙等”的状态。记录型信号量机制，则是一种不存在“忙等”现象的进程同步机制。但在采取了“让权等待”的策略后，又会出现多个进程等待访问同一临界资源的情况。为此，在信号量机制中，除了需要一个用于代代表表资资源源数数目目的的整整型型变变量量value外，还应增增加加一一个个进进程程链链表表L，用于链接上述的所有等待进程。记录型信号量是由于它采用了记记录录型型的的数数据据结结构构而得名的。它所包含的上述两个数据项可描述为：第二章 进 程 管 理 Heb Nomal University Department of Computer Science20type semaphore=record value:integer;L:list of process;end相应地，相应地，wait(S)和和signal(S)操作可描述为：操作可描述为：procedure wait(S)var S:semaphore;begin S.value =S.value-1;if S.value0 then block(S.L)end procedure signal(S)var S:semaphore;begin S.value =S.value+1;if S.value0 then wakeup(S.L);end 第二章 进 程 管 理 Heb Nomal University Department of Computer Science21 在记录型信号量机制中，S.value的的初初值值表表示示系系统统中中某某类类资资源源的的数数目目，因而又称为资源信号量，对它的每次wait操作，意味着进程请求一个单位的该类资源，因此描述为S.value =S.value-1；当当S.value0时时，表表示示该该类类资资源源已已分分配配完完毕毕，因因此此进进程程应应调调用用block原原语语，进进行行自自我我阻阻塞塞，放放弃弃处处理理机机，并并插插入到信号量链表入到信号量链表S.L中中。可可见见，该该机机制制遵遵循循了了“让让权权等等待待”准准则则。此此时时S.value的的绝绝对对值值表表示示在在该该信信号号量量链链表表中中已已阻阻塞塞进进程程的的数数目目。对对信信号号量量的的每每次次signal操操作作，表表示示执执行行进进程程释释放放一一个个单单位位资资源源，故故S.value =S.value+1操操作作表表示示资资源源数数目目加加1。若若加加1后后仍仍是是S.value0，则则表表示示在在该该信信号号量量链链表表中中，仍仍有有等等待待该该资资源源的的进进程程被被阻阻塞塞，故故还还应应调调用用wakeup原原语语，将将S.L链链表表中中的的第第一一个个等等待待进进程程唤唤醒醒。如如果果S.value的的初初值值为为1，表表示示只只允允许许一一个个进进程程访访问问临临界界资资源源，此此时的信号量转化为互斥信号量。时的信号量转化为互斥信号量。第二章 进 程 管 理 Heb Nomal University Department of Computer Science223.AND型信号量型信号量 在两个进程中都要包含两个对Dmutex和Emutex的操作，即process A:process B:wait(Dmutex);wait(Emutex);wait(Emutex);wait(Dmutex);若进程A和B按下述次序交替执行wait操作：process A:wait(Dmutex);于是Dmutex=0process B:wait(Emutex);于是Emutex=0process A:wait(Emutex);于是Emutex=-1 A阻塞process B:wait(Dmutex);于是Dmutex=-1 B阻塞 第二章 进 程 管 理 Heb Nomal University Department of Computer Science23 AND同同步步机机制制的的基基本本思思想想是是：将将进进程程在在整整个个运运行行过过程程中中需需要要的的所所有有资资源源，一一次次性性全全部部地地分分配配给给进进程程，待待进进程程使使用用完完后后再再一一起起释释放放。只只要要尚尚有有一一个个资资源源未未能能分分配配给给进进程程，其其它它所所有有可可能能为为之之分分配配的的资资源源，也也不不分分配配给给他他。亦亦即即，对对若若干干个个临临界界资资源源的的分分配配，采采取取原原子子操操作作方方式式：要要么么全全部部分分配到进程，要么一个也不分配配到进程，要么一个也不分配。由由死死锁锁理理论论可可知知，这这样样就就可可避避免免上上述述死死锁锁情情况况的的发发生生。为为此此，在在wait操操作作中中，增增加加了了一一个个“AND”条条件件，故故称称为为AND同同步步，或或称称为为同同时时wait操操作作，即即Swait(Simultaneous wait)定义如下：定义如下：第二章 进 程 管 理 Heb Nomal University Department of Computer Science24Swait(S1,S2,Sn)if Si1 and and Sn1 then for i=1 to n do Si=Si-1;endfor else place the process in the waiting queue associated with the first Si found with Si1,and set the program count of this process to the beginning of Swait operation endifSsignal(S1,S2,Sn)for i =1 to n do Si=Si+1;Remove all the process waiting in the queue associated with Si into the ready queue.endfor;第二章 进 程 管 理 Heb Nomal University Department of Computer Science254.信号量集信号量集 Swait(S1,t1,d1,Sn,tn,dn)if Sit1 and and Sntn then for i=1 to n do Si=Si-di;endfor else Place the executing process in the waiting queue of the first Si with Siti and set its program counter to the beginning of the Swait Operation.endif signal(S1,d1,Sn,dn)for i=1 to n do Si =Si+di;Remove all the process waiting in the queue associated with Si into the ready queue endfor;第二章 进 程 管 理 Heb Nomal University Department of Computer Science26 一般一般“信号量集信号量集”的几种特殊情况：的几种特殊情况：(1)Swait(S,d,d)。此此时时在在信信号号量量集集中中只只有有一一个个信信号号量量S，但但允允许许它它每每次次申申请请d个个资资源源，当当现现有有资资源源数数少少于于d时时，不予分配。不予分配。(2)Swait(S,1,1)。此此时时的的信信号号量量集集已已蜕蜕化化为为一一般般的的记记录型信号量录型信号量(S1时时)或互斥信号量或互斥信号量(S=1时时)。(3)Swait(S,1,0)。这这是是一一种种很很特特殊殊且且很很有有用用的的信信号号量量操操作作。当当S1时时，允允许许多多个个进进程程进进入入某某特特定定区区；当当S变变为为0后后，将将阻阻止止任任何何进进程程进进入入特特定定区区。换换言言之之，它它相相当当于于一一个个可可控控开关。开关。第二章 进 程 管 理 Heb Nomal University Department of Computer Science272.3.3 信号量的应用信号量的应用 1.利用信号量实现进程互斥利用信号量实现进程互斥 利用信号量实现进程互斥的进程可描述如下：利用信号量实现进程互斥的进程可描述如下：Var mutex:semaphore =1;begin parbegin process 1:begin repeat wait(mutex);critical section signal(mutex);remainder seetion until false;end第二章 进 程 管 理 Heb Nomal University Department of Computer Science28 process 2:begin repeat wait(mutex);critical section signal(mutex);remainder section until false;end parend 第二章 进 程 管 理 Heb Nomal University Department of Computer Science292.利用信号量实现前趋关系利用信号量实现前趋关系 图 2-10 前趋图举例 第二章 进 程 管 理 Heb Nomal University Department of Computer Science30 Var a,b,c,d,e,f,g;semaphore=0,0,0,0,0,0,0;begin parbegin begin S1;signal(a);signal(b);end;begin wait(a);S2;signal(c);signal(d);end;begin wait(b);S3;signal(e);end;begin wait(c);S4;signal(f);end;begin wait(d);S5;signal(g);end;begin wait(e);wait(f);wait(g);S6;end;parend end abcdefg第二章 进 程 管 理 Heb Nomal University Department of Computer Science312.3.4 管管 程程 机机 制制 1.管程的基本概念管程的基本概念 1)管程的定义管程的定义 管程由三部分组成：管程由三部分组成：局部于管程的共享变量说明；局部于管程的共享变量说明；对该数据结构进行操作的一组过程；对该数据结构进行操作的一组过程；对对局局部部于于管管程程的的数数据据设设置置初初始始值值的的语语句句。此此外外，还还须须为为管程赋予一个名字。管程赋予一个名字。第二章 进 程 管 理 Heb Nomal University Department of Computer Science32图 2-11 管程的示意图 第二章 进 程 管 理 Heb Nomal University Department of Computer Science33管程的语法如下：管程的语法如下：type monitor-name=monitor variable declarations procedure entry P1();begin end;procedure entry P2();begin end;procedure entry Pn();begin end;begin initialization code;end 第二章 进 程 管 理 Heb Nomal University Department of Computer Science342)条件变量条件变量 管程中对每个条件变量，都须予以说明，其形式为：Var x,y:condition。该该变变量量应应置置于于wait和和signal之之前前，即即可可表表示示为为X.wait和和X.signal。例例如如，由由于于共共享享数数据据被被占占用用而而使使调调用用进进程程等等待待，该该条条件件变变量量的的形形式式为为：nonbusy:condition。此此时时，wait原原语语应应改改为为nonbusy.wait，相应地，相应地，signal应改为应改为nonbusy.signal。应当指出，X.signal操操作作的的作作用用，是重重新新启启动动一一个个被被阻阻塞塞的的进进程程，但但如如果果没没有有被被阻阻塞塞的的进进程程，则则X.signal操操作作不不产产生生任任何何后后果果。这与信号量机制中的signal操作不同。因为，后者总是要执行s =s+1操作，因而总会改变信号量的状态。第二章 进 程 管 理 Heb Nomal University Department of Computer Science35 如果有进进程程Q处处于于阻阻塞塞状状态态，当当进进程程P执执行行了了X.signal操操作作后，怎样决定由哪个进行执行，哪个等待，可采用下述两种方式之一进行处理：(1)P等待，直至Q离开管程或等待另一条件。(2)Q等待，直至P离开管程或等待另一条件。采用哪种处理方式，当然是各执一词。但是Hansan却采用了第一种处理方式。第二章 进 程 管 理 Heb Nomal University Department of Computer Science362.利用管程解决生产者利用管程解决生产者-消费者问题消费者问题 在利用管程方法来解决生产者-消费者问题时，首先便是为它们建立一个管程，并命名为Proclucer-Consumer,或简称为PC。其中包括两个过程：(1)put(item)过程。(2)get(item)过程。第二章 进 程 管 理 Heb Nomal University Department of Computer Science37 (1)put(item)过过程程。生生产产者者利利用用该该过过程程将将自自己己生生产产的的产产品品投投放放到到缓缓冲冲池池中中，并并用用整整型型变变量量count来来表表示示在在缓缓冲冲池池中中已已有有的的产产品品数数目目，当当countn时时，表表示示缓缓冲冲池池已已满满，生生产产者者须等待。须等待。(2)get(item)过过程程。消消费费者者利利用用该该过过程程从从缓缓冲冲池池中中取取出出一一个个产产品品，当当count0时时，表表示示缓缓冲冲池池中中已已无无可可取取用用的的产产品品，消费者应等待。消费者应等待。第二章 进 程 管 理 Heb Nomal University Department of Computer Science38type producer-consumer=monitor Var in,out,count:integer;buffer:array0,n-1 of item;notfull,notempty:condition;procedure entry put(item)begin if countn then notfull.wait;buffer(in)=nextp;in =(in+1)mod n;count =count+1;if notempty.queue then notempty.signal;end第二章 进 程 管 理 Heb Nomal University Department of Computer Science39 procedure entry get(item)begin if count0 then notempty.wait;nextc =buffer(out);out =(out+1)mod n;count =count-1;if notfull.quene then notfull.signal;end begin in =out =0;count =0 end 第二章 进 程 管 理 Heb Nomal University Department of Computer Science40 在利用管程解决生产者-消费者问题时，其中的生产者和消费者可描述为：producer:begin repeat produce an item in nextp;PC.put(item);until false;end consumer:begin repeat PC.get(item);consume the item in nextc;until false;end