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

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

4、t section)的代码，用于将临界区正被访问的标志恢复为未 被访问的标志。 剩余区：剩余区：进程中除上述进入区、临界区及退出区之外的其 它部分的代码，在这里都称为剩余区。 第二章进 程 管 理 这样，可把一个访问临界资源的循环进程描述如下： repeat entry section critical section； exit section remainder section； until false； 第二章进 程 管 理 4、同步机制遵循的原则、同步机制遵循的原则 (1) 空闲让进空闲让进 当无进程处于临界区时，表明临界资源处于空闲状态临界资源处于空闲状态， 应允许一个请求进入临界区

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

6、TS（Test and Set）指令 Swap指令 （1）硬件方法）硬件方法 2.4.2 硬件同步机制硬件同步机制 第二章进 程 管 理 禁止中断（中断屏蔽方法）禁止中断（中断屏蔽方法） 当一个进程正在使用处理机执行它的临界区代 码时，要防止其他进程再进入其临界区访问的 最简单方法是禁止一切中断发生，或称之为屏 蔽中断、关中断。其典型模式为： . 关中断; 临界区; 开中断; /TS指令： boolean TS(boolean *lock) boolean temp; temp = *lock; *lock=true; return temp; LockLock有两种状态有两种状态： 当当lo

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

8、; 剩余区; /进程进程1 while (turn!=1) do /什么都不做; 临界区; turn = 0; 剩余区; 设置公共整型变量 turn，用于指示进入 临界区的进程编号 i(i=0,1)。使P0、P1 轮流访问临界资源。 缺点：强制性轮流进 入临界区，不能保证 “空闲让进空闲让进”。 1、单标志算单标志算 法法 /进程进程0 while (flag1) /什么都不做 ; flag0=true; 临界区; flag0 =false; 剩余区; /进程进程1 while ( flag0) /什么都不做 ; flag1=true; 临界区; flag1 =false; 剩余区; 设置数组

9、flag，初始时设 每个元素为false,表示所 有进程都未进入临界区。 若flagi=true,表示进 程进入临界区执行。 在每个进程进入临界区时， 先查看临界资源是否被使 用，若正在使用，该进程 等待，否则才可进入。解 决了“空闲让进”问题。 缺点：可能同时进入临界 区，不能保证“忙则等忙则等 待待”。 用软件方法解决互斥问题用软件方法解决互斥问题 2、双标志、先检查双标志、先检查 算法算法 /进程进程0 flag0=true; while (flag1) /什么也不做; 临界区; flag0 =false; 剩余区; 两进程先后同时作flagi=true; 缺点：保证了不同时进入临界区，

10、但又又 可能都进不去可能都进不去。不能保证“有空让进有空让进”。 /进程进程1 flag1=true; while (flag0) /什么也不做; 临界区; flag1 =false ; 剩余区; 3、双标志、先修改后检查双标志、先修改后检查 算法算法 用软件方法解决互斥问题用软件方法解决互斥问题 /进程进程0 flag0=true; turn=1; while (flag1) 临界区; flag0 =false ; 剩余区; 保证了“有空让进有空让进”和“忙则等忙则等 待待”。 /进程进程1 flag1=true; turn=0; while (flag0) 临界区; flag1 =fals

11、e ; 剩余区; 先修改、后检查、后修改算法先修改、后检查、后修改算法 用软件方法解决互斥问题用软件方法解决互斥问题 第二章进 程 管 理 2.4.3 2.4.3 信号量机制信号量机制 信号量和信号量和P P、V V操作操作 中心街道 楼宇 1 小区A 小区 B 城市公路 进程 第二章进 程 管 理 信号量 l信号量是一种数据结构 l信号量的值与相应资源的使用情况有关 l 信号量的值仅由P、V操作改变 第二章进 程 管 理 1、整型信号量 整型数 S P操作（wait）原语 V操作（signal）原语 第二章进 程 管 理 l Wait（S）: while （S00）；）；/ do no-op

12、/ 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） 是原子操作。是原子操作。 只要信号量只要信号量S0S0就不断测就不断测 试，不满足让权等待。试，不满足让权等待。 第二章进 程 管 理 2、记录型信号量、记录型信号量 记录型结构，包含两个数据项： typedef struct int value; Struct process_control_block *list; semaphore; Value L S wai

13、t操作：申请一个单位资源操作：申请一个单位资源 wait(semaphore *S) S-value-; if(S-valuelist); signal操作：释放一个单位资源操作：释放一个单位资源 signal(semaphore *S) S-value+； if(S-valuelist); 第二章进 程 管 理 lS.value为资源信号量，其初值为某类资源为资源信号量，其初值为某类资源 的数目。的数目。 lS.value0S.value0：表示系统中可用的资源数量：表示系统中可用的资源数量 lS.value0S.value0：其绝对值表示已阻塞的进程数：其绝对值表示已阻塞的进程数 量。（等

14、待使用资源的进程个数）量。（等待使用资源的进程个数） lS.valueS.value初值为初值为1 1时：只允许一个进程访问时：只允许一个进程访问 临界资源，是互斥信号量。临界资源，是互斥信号量。 第二章进 程 管 理 上述的进程互斥问题，是针对各进程之间只共享一个临 界资源而言的。在有些应用场合，是一个进程需要先获得两 个或更多的共享资源后方能执行其任务。假定现有两个进程 A和B，他们都要求访问共享数据D和E。当然，共享数据都 应作为临界资源。为此，可为这两个数据分别设置用于互斥 的信号量Dmutex和Emutex，并令它们的初值都是1。相应地， 在两个进程中都要包含两个对Dmutex和Em

15、utex的操作，即 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阻塞 最后，进程A和B处于僵持状态。在无外力作用下，两者 都

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