第2章进程同步与通信-1

1、第二章进 程 管 理 第二章进程的描述与控制 2.4 2.4 进程同步与互斥进程同步与互斥1 1、进程同步与互斥、进程同步与互斥 2 2、信号量和、信号量和P P、V V操作操作ANDAND信号量信号量2.52.5、经典进程同步与互斥问题、经典进程同步与互斥问题2.62.6、 进程通信进程通信 第二章进 程 管 理 2.4.1 进程同步的基本概念进程同步的基本概念 间接制约间接制约: :进程间由于共享某种系统资源，而形成的相进程间由于共享某种系统资源，而形成的相互制约。互制约。 直接制约：直接制约： 进程间由于合作进程间由于合作而形成的相互制约而形成的相互制约。进程进程B B 资源资源进程进程

2、A进程进程A进程进程B B1、进程的两种制约关系、进程的两种制约关系 在多道程序环境下，当程序并发执行时，由于资源共享和进程合作，使同处于一个系统中的诸进程之间可能存在着以下两种形式的制约关系：第二章进 程 管 理 互斥：互斥： 互斥是并发执行的多个进程由于竞争同一资源而产生的相互排斥的关系。同步：同步： 同步是进程间共同完成一项任务时直接发生相互作用的关系。 进程的两大关系进程的两大关系第二章进 程 管 理 同步进程间具有合作关系 在执行时间上必须按一定的顺序协调进行。 临界资源：一次仅允许一个进程使用的共享资源。 如：打印机、磁带机、表格。第二章进 程 管 理 2、临界资源3、临界区在每个

3、进程中访问临界资源的那段程序。 进程必须互斥进入临界区第二章进 程 管 理 访问临界区的循环进程描述访问临界区的循环进程描述repeat进入区进入区临界区临界区退出区退出区剩余区剩余区检查临界资源是否能访问将临界区标志设为未访问 until false;第二章进 程 管 理 进入区：进入区：每个进程在进入临界区之前，应先对欲访问的临界资源进行检查，看它是否正被访问。如果此刻该临界资源未被访问，进程便可进入临界区对该资源进行访问，并设置它正被访问的标志它正被访问的标志； 退出区：退出区：在临界区后面也要加上一段称为退出区(exit section)的代码，用于将临界区正被访问的标志恢复为未被访问

4、的标志。 剩余区：剩余区：进程中除上述进入区、临界区及退出区之外的其它部分的代码，在这里都称为剩余区。第二章进 程 管 理 这样，可把一个访问临界资源的循环进程描述如下：repeatentry sectioncritical section；exit sectionremainder section；until false； 第二章进 程 管 理 4、同步机制遵循的原则、同步机制遵循的原则 (1) 空闲让进空闲让进当无进程处于临界区时，表明临界资源处于空闲状态临界资源处于空闲状态，应允许一个请求进入临界区的进程立即进入自己的临界区，以有效地利用临界资源。(2) 忙则等待忙则等待当已有进程进入临

5、界区时已有进程进入临界区时，表明临界资源正在被访问，因而其它其它试图进入临界区的进程必须等待进程必须等待，以保证对临界资源的互斥访问。 第二章进 程 管 理 (3) 有限等待有限等待对要求访问临界资源的进程，应保证在有限时间内能进入自己有限时间内能进入自己的临界区的临界区，以免陷入“死等”状态。(4) 让权等待让权等待当进程不能进入自己的临界区时，应立即释放处理机不能进入自己的临界区时，应立即释放处理机，以免进程陷入“忙等”状态。 互斥的实现方法互斥的实现方法禁止中断专用机器指令TS（Test and Set）指令 Swap指令（1）硬件方法）硬件方法2.4.2 硬件同步机制硬件同步机制第二章

6、进 程 管 理 禁止中断（中断屏蔽方法）禁止中断（中断屏蔽方法） 当一个进程正在使用处理机执行它的临界区代码时，要防止其他进程再进入其临界区访问的最简单方法是禁止一切中断发生，或称之为屏蔽中断、关中断。其典型模式为：.关中断;临界区;开中断;/TS指令：boolean TS(boolean *lock) boolean temp; temp = *lock; *lock=true; return temp;LockLock有两种状态有两种状态：当当lock=falselock=false时，表示资源空闲时，表示资源空闲; ;当当lock=truelock=true时，表示资源正在被使用。时，表

7、示资源正在被使用。缺点：没有做到：缺点：没有做到：“让权等待让权等待”( (当进程不能进入自不能进入自己的临界区时，应立即释放处理机己的临界区时，应立即释放处理机，以免进程陷入“忙等”状态。 ) )/TS指令的使用while TS (&lock);临界区;lock=false;剩余区；TS（Test and Set）指令互斥实现的软件方法互斥实现的软件方法/进程进程0while (turn!=0) /什么都不做;临界区;turn = 1;剩余区; /进程进程1while (turn!=1) do/什么都不做;临界区;turn = 0;剩余区;设置公共整型变量turn，用于指示进入临界区

8、的进程编号i(i=0,1)。使P0、P1轮流访问临界资源。缺点：强制性轮流进入临界区，不能保证“空闲让进空闲让进”。1、单标志算单标志算法法/进程进程0 while (flag1)/什么都不做 ;flag0=true;临界区;flag0 =false;剩余区;/进程进程1while ( flag0) /什么都不做 ;flag1=true;临界区;flag1 =false;剩余区;设置数组flag，初始时设每个元素为false,表示所有进程都未进入临界区。若flagi=true,表示进程进入临界区执行。在每个进程进入临界区时，先查看临界资源是否被使用，若正在使用，该进程等待，否则才可进入。解决了

9、“空闲让进”问题。缺点：可能同时进入临界区，不能保证“忙则等忙则等待待”。用软件方法解决互斥问题用软件方法解决互斥问题2、双标志、先检查双标志、先检查算法算法/进程进程0flag0=true;while (flag1)/什么也不做;临界区;flag0 =false;剩余区;两进程先后同时作flagi=true;缺点：保证了不同时进入临界区，但又又可能都进不去可能都进不去。不能保证“有空让进有空让进”。/进程进程1flag1=true;while (flag0)/什么也不做;临界区;flag1 =false ; 剩余区;3、双标志、先修改后检查双标志、先修改后检查算法算法用软件方法解决互斥问题用

10、软件方法解决互斥问题/进程进程0flag0=true;turn=1;while (flag1) & (turn=1)/什么也不做;临界区;flag0 =false ;剩余区;保证了“有空让进有空让进”和“忙则等忙则等待待”。/进程进程1flag1=true;turn=0;while (flag0) & (turn=0)/什么也不做;临界区;flag1 =false ;剩余区;先修改、后检查、后修改算法先修改、后检查、后修改算法用软件方法解决互斥问题用软件方法解决互斥问题第二章进 程 管 理 2.4.3 2.4.3 信号量机制信号量机制信号量和信号量和P P、V V操作操作中心街

11、道 楼宇 1小区A小区 B城市公路进程第二章进 程 管 理 信号量l信号量是一种数据结构l信号量的值与相应资源的使用情况有关l 信号量的值仅由P、V操作改变第二章进 程 管 理 1、整型信号量 整型数SP操作（wait）原语V操作（signal）原语第二章进 程 管 理 l Wait（S）: while （S00）；）；/ do no-op/ do no-op S:=S-1; S:=S-1;l Signal（S）: S:=S+1;S:=S+1;S表示资源数目，是个整型量。第二章进 程 管 理 waitwait（s s）和）和signalsignal（S S）是原子操作。是原子操作。 只要信号量

12、只要信号量S0S0就不断测就不断测试，不满足让权等待。试，不满足让权等待。第二章进 程 管 理 2、记录型信号量、记录型信号量 记录型结构，包含两个数据项： typedef structint value;Struct process_control_block *list;semaphore;ValueLSwait操作：申请一个单位资源操作：申请一个单位资源 wait(semaphore *S)S-value-;if(S-valuelist);signal操作：释放一个单位资源操作：释放一个单位资源signal(semaphore *S)S-value+；if(S-valuelist); 第

13、二章进 程 管 理 lS.value为资源信号量，其初值为某类资源为资源信号量，其初值为某类资源的数目。的数目。lS.value0S.value0：表示系统中可用的资源数量：表示系统中可用的资源数量lS.value0S.value0：其绝对值表示已阻塞的进程数：其绝对值表示已阻塞的进程数量。（等待使用资源的进程个数）量。（等待使用资源的进程个数）lS.valueS.value初值为初值为1 1时：只允许一个进程访问时：只允许一个进程访问临界资源，是互斥信号量。临界资源，是互斥信号量。第二章进 程 管 理 上述的进程互斥问题，是针对各进程之间只共享一个临界资源而言的。在有些应用场合，是一个进程需

14、要先获得两个或更多的共享资源后方能执行其任务。假定现有两个进程A和B，他们都要求访问共享数据D和E。当然，共享数据都应作为临界资源。为此，可为这两个数据分别设置用于互斥的信号量Dmutex和Emutex，并令它们的初值都是1。相应地，在两个进程中都要包含两个对Dmutex和Emutex的操作，即 process A:process B:wait(Dmutex)；wait(Emutex)；wait(Emutex)；wait(Dmutex)； 第二章进 程 管 理 若进程A和B按下述次序交替执行wait操作：process A: wait(Dmutex)； 于是Dmutex=0process B:

15、 wait(Emutex)； 于是Emutex=0process A: wait(Emutex)； 于是Emutex=-1 A阻塞process B: wait(Dmutex)； 于是Dmutex=-1 B阻塞 最后，进程A和B处于僵持状态。在无外力作用下，两者都将无法从僵持状态中解脱出来。我们称此时的进程A和B已进入死锁状态。显然，当进程同时要求的共享资源愈多时，发生进程死锁的可能性也就愈大。 第二章进 程 管 理 3、AND型信号量基本思想：将进程在整个运行中需要的所基本思想：将进程在整个运行中需要的所有资源，一次性全部分配给进程，待进程有资源，一次性全部分配给进程，待进程使用完后一起释放。使用完后一起释放。由死锁理论可知，这样就可避免上述死锁情况的发生。第二章进 程 管 理 在在wait中加入中加入AND条件，又称条件，又称AND同步或同同步或同时时wait操作。操作。 Swait(Simultaneous wait) Swait(S1，S2，Sn)While(TRUE) if (S11 &Sn1)for(i=1;i