《【2017年整理】第四节 进程同步》由会员分享，可在线阅读，更多相关《【2017年整理】第四节 进程同步（73页珍藏版）》请在金锄头文库上搜索。
1、第四节 进程同步,Concurrency：Mutual Exclusion and Synchronization（并发性：互斥和同步）进程间的联系；进程的同步机制信号量及P.V操作（解决进程同步互斥问题）,同步问题引入：,P1、P2两个进程的执行顺序是随机的，P1、P2可能顺序执行或交错执行。 由图可见，不同的执行顺序，COUNT值会不同，这是不允许的。 在多道程序系统中，由于资源共享或进程合作，使进程间形成间接相互制约和直接相互制约关系,一、进程间的联系,在多道程序的环境中，系统中的多个进程可以并发执行，同时它们又要共享系统中的资源，这些资源有些是可共享使用的，如磁盘，有些是以独占方式使用
2、的，如打印机。由此将会引起一系列的矛盾，产生错综复杂的相互制约的关系。回顾：并发环境的特征：失去封闭性；失去可再现性；,产生这种错综复杂的相互制约关系的原因有二：资源共享（如例售票系统，考虑互斥）；进程合作（如例get-copy-put，考虑同步）。解决方法：进程同步机制（互斥+同步）,无关进程（无交往进程）：在逻辑上无任何联系的进程。无关的并发进程一定没有共享的变量，它们分别在各自的数据集合上操作。 有交往进程：多个并发进程在逻辑上有某种联系。 有交往的并发进程一定共享某些资源。,1并发进程间的联系,进程的同步（直接作用） synchronism，指合作进程在执行时序上的一种相互制约关系。
3、进程的互斥（间接作用）mutual exclusion，协同工作的进程之间存在同步关系，但是进程之间的更一般关系却是互斥。 同一时刻不允许多个进程访问同一资源的现象，称为进程的互斥。,2、有交往进程的两类联系,临界资源：critical resource，系统中某些资源一次只允许一个进程使用，称这样的资源为临界资源或共享变量。临界区：critical section，简称CS，在进程中涉及到临界资源的程序段叫临界区。,3、几个概念,由于并发进程之间存在着同步和互斥等制约关系，为了正确地实现这种复杂的制约关系，我们引入了同步机制 进程同步机制应遵循的原则：空闲让进：当无进程在CS时，任何有权使用
4、CS的进程可进入；忙则等待：不允许两个以上的进程同时进入CS；有限等待：任何进入CS的要求应在有限的时间内得到满足，以免陷入“死等”；让权等待：进程不能进入CS时应放弃占用CPU，以免陷入“忙等”。,4、进程同步机制,二、进程互斥的软硬件解决方法,硬件方法：当一个进程进入临界区,就屏蔽所有中断，但成本高软件方法：用编程解决，但常常造成其它问题,1、对临界区的再说明：临界区(critical section)：进入区(entry section)：在进入临界区之前，检查可否进入临界区的一段代码。如果可以进入临界区，通常设置相应“正在访问临界区”标志退出区(exit section)：用于将“正在
5、访问临界区”标志清除。剩余区(remainder section)：代码中的其余部分,有两个进程Pi, Pj，其中的Pi的描叙如下图。设立公用整型变量turn：进入CS的进程标识在进入区循环检查是否允许本进程进入：turn为i时，进程Pi可进入；在退出区修改允许进入进程标识：进程Pi退出时，改turn为进程Pj的标识j；,2、软件解法1- 单标志法,缺点：强制轮流进入CS，没有考虑进程的实际需要。容易违背“空闲让进”原则,设立一个标志数组flag：描述进程是否在临界区，初值均为FALSE。先检查，后修改：在进入区检查另一个进程是否在临界区，不在时修改本进程在临界区的标志；在退出区修改本进程在临
6、界区的标志；,3、软件解法2-双标志法、先检查,优点：不用交替进入，可连续使用；缺点：Pi和Pj可能同时进入临界区。,4、软件解法3-双标志、先修改标志,类似于算法2，与互斥算法2的区别在于先修改后检查。,优点：可防止两个进程同时进入临界区。缺点：Pi和Pj可能都进入不了临界区。,5、软件解法4- Petersons Algorithm,先修改、后检查、后修改者等待，结合算法1和算法3，是正确的算法。在进入区先修改后检查，并检查并发修改先后；检查对方flag，如果不在临界区则自己进入；否则再检查turn，保存的是较晚的一次赋值，则较晚的进程等待，较早的进程进入先到先入，后到等待,1）有很大局限
7、性（如不适于多进程） 2）实现过于复杂，需要高的编程技巧完全利用软件方法，现在已很少采用。可以考虑利用某些硬件指令其读写操作由一条指令完成，因而保证读操作与写操作不被打断；,6、软件解法的缺点,该指令读出标志后设置为TRUE指令的描叙：boolean TS(boolean *lock) boolean old; old = *lock; *lock = TRUE; return old;lock表示资源的两种状态：TRUE表示正被占用，FALSE表示空闲,硬件解法1-“测试并设置”指令,利用TS实现进程互斥：每个临界资源设置一个公共布尔变量lock，初值为FALSE在进入区利用TS进行检查：有
8、进程在CS时，重复检查；直到其它进程退出时，检查通过； 实现：,指令的描叙：void SWAP(int *a, int *b) int temp; temp = *a; *a = *b; *b = temp;,硬件解法2-“交换”指令swap（或Exchange指令）,利用Swap实现进程互斥：每个临界资源设置一个公共布尔变量lock，初值为FALSE。每个进程设置一个私有布尔变量key 实现： key = TRUE ;DoSWAP(&lock, &key);while(key);Critical sectionLock=FALSE;Remainder section,进入临界区前执行： 执行
9、“关中断”指令离开临界区后执行： 执行“开中断”指令,硬件解法3-“开关中断”指令,硬件方法的优点适用于任意数目的进程简单，容易验证其正确性可以支持进程内存在多个CS，只需为每个CS设立一个布尔变量硬件方法的缺点等待要耗费CPU时间，不能实现“让权等待”可能“饥饿”：从等待进程中随机选择一个进入CS，有的进程可能一直选不上可能死锁,三、信号量机制及P.V操作,前面的互斥算法都是平等进程间的协商机制，它们存在的问题是平等协商无法解决的，需要引入一个地位高于进程的管理者来解决公有资源的使用问题。操作系统可以从进程管理者的角度来处理互斥的问题，信号量(semaphore)就是由操作系统提供的管理公有
10、资源的有效手段。,荷兰学者E.W.Dijkstra在1965年提出了一种解决同步、互斥问题的更一般的方法，这就是信号量(semaphore)机制以及有关的p、v操作P、V分别是荷兰语的test(proberen)和increment(verhogen)一种卓有成效的进程同步机制,1、最初信号量（Semaphore）就是一个整型数，规定在sem大于等于零的时候代表可供并发进程使用的资源实体数，sem小于零的时候，表示正在等待使用临界区的进程的个数。根据这个原则，在给信号量附初值的时候，我们显然就要设初值大于零。根据这个原则，在给信号量附初值的时候，我们显然就要设初值大于零。p操作和v操作是不可中
11、断的程序段，称为原语。,P原语操作的动作是： （1） sem减1； （2） 若sem减1后仍大于或等于零，则进程继续执行； （3） 若sem减1后小于零，则该进程被阻塞后进入与该信号相对应的队列中，然后转进程调度。 V原语操作的动作是： （1） sem加1； （2） 若相加结果大于零，则进程继续执行； （3） 若相加结果小于或等于零，则从该信号的等待队列中唤醒一等待进程，然后再返回原进程继续执行或转进程调度。 注意：P(S) - wait(S); V(S) - signal(S),每个信号量s除一个整数值外s.value，还有一个进程等待队列s.queue，其中是阻塞在该信号量的各个进程的标识
12、；信号量只能通过初始化（一次且仅有一次）和两个标准的原语p(s)、v(s)来访问；初始化指定一个非负整数值，表示空闲资源总数（又称为“资源信号量”）若为非负值表示当前的空闲资源数；若为负值,其绝对值表示当前等待CS的进程数；s.value=1：即互斥信号量。,对信号量的再说明,为临界资源设置一个互斥信号量：mutex(Mutual Exclusion)，其初值为1；在每个进程中将临界区代码置于P(mutex)和V(mutex)原语之间。必须成对使用P和V原语：,利用信号量实现互斥,习题,1、有一单向行驶的公路桥，每次只允许一辆汽车通过。当汽车到达桥头时，若桥上无车，便可上桥；否则，需等待，直到
13、桥上的汽车下桥为止。若每一辆汽车为一进程，请用PV操作实现。 2、有一只铁笼子，每次只能放入一只动物。猎手向笼中放入老虎，农民向笼中放入猪，动物园等待取笼中的老虎，饭店等待取笼中的猪。试用PV操作写出能同步执行的程序。,前趋关系：?例如：并发执行的进程P1和P2中，分别有代码C1和C2，要求C1在C2开始前完成；方法：为每个前趋关系（即前趋图中的每条边）设置一个互斥信号量S12，其初值为0利用信号量描述前趋关系，结构如下：,利用信号量来描述前趋（同步）关系,e.g.1设有前趋关系，如图，请用信号量机制来实现图中所述前趋关系Var a,b,c,d,e,f,g;semaphore:=0,0,0,0
14、,0,0,0;Begin:Begin:s1;v(a);v(b);end;Begin:P(a);s2;v(c);v(d);endBegin:p(b);s3;v(g);end;Begin:P(c);s4;v(e);end;Begin:p(d);s5;v(f);end;Begin:P(e);p(f);p(g);s6;end;End（注意其它教材的写法）,e.g.2用信号灯及P、V操作来描述左图1)说明进程的同步关系 进程P1、P2并行执行，P3的执行必须等待P1、P2都完成后才能开始执行。2)设置信号灯，说明含义、初值。 s13 = 0 表示进程P1尚未执行完成； s23 = 0 表示进程P2尚未执
15、行完成；,用信号量描述前趋关系的其他描述,用于同时需要多个资源时的信号量操作1. AND型信号量集引入：一段处理代码需要同时获取两个或多个临界资源可能死锁（？）：各进程分别获得部分临界资源，然后等待其余的临界资源，“各不相让”。,三）信号量集机制及其应用,基本思想：在一个原语中，将一段代码同时需要的多个临界资源，要么全部分配给它，要么一个都不分配。称为SP(Simultaneous P)。在SP时，由于是对资源全部分配或不分配，所以总有进程获得全部资源并在推进之后释放资源，因此不会死锁。,SP(S1, S2, , Sn) while (TRUE) if (S1 =1 & S2 = 1 & & Sn = 1) for (i = 1; i = n; +i) Si:= Si-1; break; else 进程进入第一个小于1信号量的 等待队列Si.queue; 阻塞调用进程; ,SV(S1, S2, , Sn) for (i = 1; i = n; +i) Si:= Si + 1; for (each process P waiting in Si.queue) 从等待队列Si.queue中取出进程P; if (判断进程是否通过SP中的测试) 进程进入就绪队列; else 进程P进入某等待队列； ,
