3进程同步与通信(7学时)

1、第第3章章 进程同步与通信进程同步与通信3.1 进程互斥与同步进程互斥与同步3.2 互斥算法互斥算法3.3 信号量信号量(semaphore)3.4 进程通信进程通信3.1 进程同步与互斥进程同步与互斥3.1.1 进程间的制约关系进程间的制约关系3.1.2 进程的同步进程的同步3.1.3 进程的互斥进程的互斥3.1.1 进程间的制约关系进程间的制约关系 进程间的制约关系进程间的制约关系 间接制约间接制约：进行竞争独占分配到的部分：进行竞争独占分配到的部分或全部共享资源，或全部共享资源，“互斥互斥”. 进程间要通过进程间要通过某种中介发生联系，是无意识安排的，可发某种中介发生联系，是无意识安排的

2、，可发生在相交进程之间，也可发生在无关进程之生在相交进程之间，也可发生在无关进程之间间 直接制约直接制约：进行协作等待来自其他进程：进行协作等待来自其他进程的信息，的信息，“同步同步”。进程间的相互联系是有进程间的相互联系是有意识的安排的，直接作用只发生在相交进程意识的安排的，直接作用只发生在相交进程间间3.1.2 进程的同步（直接作用进程的同步（直接作用synchronism)指系统中一些进程需要相互合作，共同完成一项指系统中一些进程需要相互合作，共同完成一项任务。具体说，一个进程运行到某一点时要求另任务。具体说，一个进程运行到某一点时要求另一伙伴进程为它提供消息，在未获得消息之前，一伙伴进

3、程为它提供消息，在未获得消息之前，该进程处于等待状态，获得消息后被唤醒进入就该进程处于等待状态，获得消息后被唤醒进入就绪态。绪态。例例: : 司机司机 P1 售票员售票员 P2 REPEAT REPEAT 启动启动 关门关门 正常运行正常运行 售票售票 到站停到站停 开门开门 UNTIL FALSE UNTIL FALSE 3.1.3 进程的互斥进程的互斥( (间接作用间接作用mutual exclusion) 临界资源临界资源：critical resource 系统中某些资源一次只允许一个进程使用，称系统中某些资源一次只允许一个进程使用，称这样的资源为这样的资源为临界资源临界资源或或互斥资

4、源互斥资源或或共享变量。共享变量。返回返回 由于各进程要求共享资源，而有些资源需要由于各进程要求共享资源，而有些资源需要互斥使用，因此各进程间竞争使用这些资源，进互斥使用，因此各进程间竞争使用这些资源，进程的这种关系为程的这种关系为进程的互斥。进程的互斥。3.2 互斥算法互斥算法3.2.1 临界区的访问过程临界区的访问过程3.2.2 使用临界区使用临界区应遵循的准则应遵循的准则3.2.3 进程互斥的软件方法进程互斥的软件方法3.2.4 进程互斥的硬件方法进程互斥的硬件方法实现对共享变量的正确访问。实现对共享变量的正确访问。3.2.1 临界区的访问过程临界区的访问过程entry sectione

5、xit sectioncritical sectionremainder section 临界区临界区(critical section)：进程中访问临界资源的：进程中访问临界资源的一段代码。一段代码。 进入区进入区(entry section)：在进入临界区之前，检查：在进入临界区之前，检查可否进入临界区的一段代码。如果可以进入临界可否进入临界区的一段代码。如果可以进入临界区，通常设置相应区，通常设置相应正在访问临界区正在访问临界区标志标志 退出区退出区(exit section)：用于将：用于将正在访问临界区正在访问临界区标志清除。标志清除。 剩余区剩余区(remainder sectio

6、n)：代码中的其余部分。：代码中的其余部分。3.2.2 使用临界区使用临界区应遵循的准则应遵循的准则 有空让进有空让进：当无进程在互斥区时，任何有权使用互斥区：当无进程在互斥区时，任何有权使用互斥区的进程可进入的进程可进入 无空等待无空等待：不允许两个以上的进程同时进入互斥区：不允许两个以上的进程同时进入互斥区 多中择一多中择一：当没有进程在临界区，而同时有多个进程要：当没有进程在临界区，而同时有多个进程要求进入临界区，只能让其中之一进入临界区，其他进程求进入临界区，只能让其中之一进入临界区，其他进程必须等待必须等待 有限等待有限等待：任何进入互斥区的要求应在有限的时间内得：任何进入互斥区的要

7、求应在有限的时间内得到满足到满足 让权等待让权等待：处于等待状态的进程应放弃占用：处于等待状态的进程应放弃占用CPUCPU 平等竞争平等竞争：任何进程无权停止其它进程的运行：任何进程无权停止其它进程的运行, ,进程之进程之间相对运行速度无硬性规定间相对运行速度无硬性规定3.2.3 进程互斥的软件方法进程互斥的软件方法一、单标志的方法一、单标志的方法turn = j;remainder section1、算法思想、算法思想 设立一个公用整型变量设立一个公用整型变量 turn：描述允许进入临：描述允许进入临界区的进程标识界区的进程标识 在在进入区进入区循环检查是否允许本进程进入：循环检查是否允许本

8、进程进入：turn为为 i 时，时，进程进程Pi可进入；可进入； 在在退出区退出区修改允许进入进程标识：进程修改允许进入进程标识：进程Pi退出时，改退出时，改turn为进程为进程Pj的标识的标识j；2、算法描述、算法描述设有两个进程设有两个进程Pi、Pj，其中，其中Pi访问临界区描述为：访问临界区描述为：while (turn != i);critical sectionturn = j;remainder section3、单标志方法缺点、单标志方法缺点 强制轮流强制轮流进入临界区，没有考虑进程的实际需进入临界区，没有考虑进程的实际需要。容易造成要。容易造成资源利用不充分资源利用不充分：在：

9、在Pi出让临界区之出让临界区之后，后，Pj使用临界区之前，使用临界区之前，Pi不可能再次使用临界区；不可能再次使用临界区；1、算法思想、算法思想设立一个标志数组设立一个标志数组flag ：描述进程是否在临界区，：描述进程是否在临界区，初值均为初值均为FALSE。 先检查，后修改先检查，后修改：在进入区检查另一个进程是否：在进入区检查另一个进程是否在临界区，不在时修改本进程在临界区的标志；在临界区，不在时修改本进程在临界区的标志； 在退出区修改本进程不在临界区的标志在退出区修改本进程不在临界区的标志；Pi:二、双标志、先检查的方法二、双标志、先检查的方法while (flagj);flagi =

10、 TRUE;critical sectionflagi = FALSE;remainder section2、算法描述、算法描述设有两个进程设有两个进程Pi、Pj，其中，其中Pi访问临界区描述为：访问临界区描述为：3、双标志、先检查方法优缺点、双标志、先检查方法优缺点（1）优点）优点：不用交替进入，可连续使用；：不用交替进入，可连续使用；（2）缺点）缺点：Pi 和和 Pj可能同时进入临界区。在可能同时进入临界区。在Pi 和和 Pj都不在临界区时，假设按下面序列执行时，会同都不在临界区时，假设按下面序列执行时，会同时进入：时进入：“Pi; Pj ; Pi; Pj”。即在检。即在检查对方查对方fl

11、ag之后和切换自己之后和切换自己 flag 之前有一段时间，之前有一段时间，结果都检查通过。这里的问题出在检查和修改操结果都检查通过。这里的问题出在检查和修改操作不能连续进行。作不能连续进行。3.2.4 进程互斥的硬件方法进程互斥的硬件方法 完全利用软件方法，有很大局限性（如不适于多进程），现完全利用软件方法，有很大局限性（如不适于多进程），现在已很少采用。在已很少采用。 可以利用某些硬件指令其读写操作由一条指令完成，因可以利用某些硬件指令其读写操作由一条指令完成，因而保证读操作与写操作不被打断；而保证读操作与写操作不被打断；Test-and-Set指令指令该指令读出标志后设置为该指令读出标志

12、后设置为TRUE：boolean TS(boolean *lock) boolean old; old = *lock; *lock = TRUE; return old;lock表示资源的两种状态：表示资源的两种状态：TRUE表示正被表示正被占用，占用，FALSE表示空闲表示空闲Test-and-Set指指令令, 可保证在可保证在一个指令周期一个指令周期内对一个存储内对一个存储单元的读和写，单元的读和写，其功能如右：其功能如右：互斥算法（互斥算法（TS指令）指令） 利用利用TS实现进程互斥：每个临界实现进程互斥：每个临界资源设置一个公共布尔变量资源设置一个公共布尔变量lock，初值为初值为F

13、ALSE 在进入区利用在进入区利用TS进行检查：有进进行检查：有进程在临界区时，重复检查；直到程在临界区时，重复检查；直到其它进程退出时，检查通过；其它进程退出时，检查通过；while TS(&lock);lock = FALSE;critical sectionremainder section相当于测相当于测试并加锁试并加锁相当于相当于解锁解锁测试并加锁：测试并加锁：lock (int *lock) while TS(&lock); 解锁：解锁：unlock (int *lock) * lock = FALSE; 硬件方法的优点硬件方法的优点WS 适用于任意数目的进程，在单处理器或多处理器

14、上适用于任意数目的进程，在单处理器或多处理器上完全相同完全相同 简单，容易验证其正确性简单，容易验证其正确性 支持多个临界区，只需为每个临界区设立一个布尔支持多个临界区，只需为每个临界区设立一个布尔变量变量 硬件方法的缺点硬件方法的缺点WS 等待要耗费等待要耗费CPU时间时间，不能实现，不能实现让权等待让权等待 可能可能“饥饿饥饿”（不公平）：（不公平）：从等待进程中随机选择从等待进程中随机选择一个进入临界区，有的进程可能一直选不上一个进入临界区，有的进程可能一直选不上返回返回3.3 信号量信号量(semaphore)3.3.1 信号量和信号量和P、V原语原语3.3.2 利用信号量实现互斥利用

15、信号量实现互斥3.3.3 利用信号量来描述前趋关系利用信号量来描述前趋关系3.3.4 经典进程同步问题经典进程同步问题 前面的互斥算法都存在问题，它们是前面的互斥算法都存在问题，它们是平等进程平等进程间的间的一种一种协商协商机制，需要一个地位高于进程的机制，需要一个地位高于进程的管理者管理者来来解决公有资源的使用问题。解决公有资源的使用问题。 OS可从进程管理者的角度来处理互斥的问题，可从进程管理者的角度来处理互斥的问题，信号信号量量就是就是OS提供的管理公有资源的有效手段。提供的管理公有资源的有效手段。信号量代表可用资源实体的数量信号量代表可用资源实体的数量。3.3.1 信号量和信号量和P、

16、V原语原语 1965年，由荷兰学者年，由荷兰学者Dijkstra提出（所以提出（所以P、V分别是分别是荷兰语的荷兰语的passeren (pass)和和verhoog (increment)），是），是一种卓有成效的一种卓有成效的进程同步与互斥进程同步与互斥机制。机制。信号量信号量：semaphore是一个数据结构，定义如下：是一个数据结构，定义如下： typedef struct integer count; Pointer_PCB queue; Semaphore;信号量说明：信号量说明： Semaphore s;问题：进程按照什么顺序问题：进程按照什么顺序 从队列中移出？从队列中移出？

17、每个信号量每个信号量 s 除一个除一个整数值整数值 s.count（计数）外，还（计数）外，还有一个有一个进程等待队列进程等待队列 s.queue，其中，其中queue是指向是指向PCB的队列的队列 信号量只能通过信号量只能通过初始化初始化和和两个标准的原语两个标准的原语来访问来访问作为作为OS核心代码执行，核心代码执行，不受进程调度的打断不受进程调度的打断 初始化初始化指定一个非负整数值，表示指定一个非负整数值，表示空闲资源总数空闲资源总数（又称为（又称为“资源信号量资源信号量”）: 若为非负值若为非负值：表示：表示当前的空闲资源数当前的空闲资源数 若为负值若为负值：其绝对值表示：其绝对值表

18、示当前等待临界区的进当前等待临界区的进程数程数1. P原语原语-P(s) 或或wait(s) -s.count;/表示申请一个资源表示申请一个资源; if (s.count 0)/表示没有空闲资源表示没有空闲资源; 调用进程进入等待队列调用进程进入等待队列s.queue; 阻塞调用进程阻塞调用进程; P(Semaphore s)在互斥问题中，申请使用临界资源时调用它在互斥问题中，申请使用临界资源时调用它2. V原语原语V(s) 或或 signal(s) +s.count; /表示释放一个资源；表示释放一个资源； if (s.count = 0) /表示有进程处于阻塞状态；表示有进程处于阻塞状态

19、； 从等待队列从等待队列s.queue中取出一个进程中取出一个进程P; 进程进程P进入就绪队列进入就绪队列; V原语通常唤醒进程等待队列中的头一个进程原语通常唤醒进程等待队列中的头一个进程V(Semaphore s )功能：释放资源，功能：释放资源， 或唤醒进程或唤醒进程使用时机：进程退出临界区之后使用时机：进程退出临界区之后3.3.2 利用信号量实现互斥利用信号量实现互斥 为临界资源设置一个为临界资源设置一个互斥信号量互斥信号量mutex(MUTual Exclusion)，其初值为，其初值为1；在每个进程中将临界区；在每个进程中将临界区代码置于代码置于P(mutex)和和V(mutex)原

20、语之间原语之间 必须必须成对使用成对使用P和和V原语：原语：遗漏遗漏P原语原语则不能保证则不能保证互斥访问，互斥访问，遗漏遗漏V原语原语则不能在使用临界资源之后则不能在使用临界资源之后将其释放（给其他等待的进程）；将其释放（给其他等待的进程）；P、V原语不能原语不能次序错误、重复或遗漏次序错误、重复或遗漏V(mutex);critical sectionremainder sectionP(mutex);3.3.2 利用信号量实现互斥利用信号量实现互斥 用信号量实现两并发进程用信号量实现两并发进程 PA、PB互斥的描述如下：互斥的描述如下： 设设互斥信号量互斥信号量mutex，其取值范围为，其

21、取值范围为(1，0，-1)，其，其中中mutex=1表示进程表示进程PA、PB都未进入临界区都未进入临界区S ， mutex=0表示进程表示进程PA或或PB已进入临界区已进入临界区S， mutex=-1表示进程表示进程PA和和PB中一个进程已进入中一个进程已进入 临界区临界区S，另一个进程等待进入临界区，另一个进程等待进入临界区 描述如下：描述如下： 进程进程PA：P(mutex)V(mutex) 进程进程PB：P(mutex)V(mutex)3.3.2 利用信号量实现互斥利用信号量实现互斥 结论结论:有有m个进程共享同一临界资源个进程共享同一临界资源,若使用若使用信号量机制实现对临界资源的互

22、斥访问信号量机制实现对临界资源的互斥访问,则则信号量的变化范围为：信号量的变化范围为：-(m-1) ,1互斥举例互斥举例1 问题：问题：n个进程共用一个临界区个进程共用一个临界区const int n = 进程数；进程数；Semaphore s = 1;void Process( int i) while ( true) P(s); / wait(s) V(s) / signal(s) remainder section void main() cobegin(Process(1), Process(2), ., Process(n); coend 3.3.3 利用信号量来描述前趋关系利用信号

23、量来描述前趋关系 前趋关系：并发执行的进程前趋关系：并发执行的进程P1和和P2中，分别有中，分别有代码代码C1和和C2，要求，要求C1在在C2开始前完成；开始前完成； 为每个前趋关系设置一个互斥信号量为每个前趋关系设置一个互斥信号量S12，其，其初值为初值为0P2P1C1C2V(S12);P(S12);问题：有如图所示的六个语句（进程），并发执行，其前趋问题：有如图所示的六个语句（进程），并发执行，其前趋关系如图，并发执行描述如下：关系如图，并发执行描述如下：int a=0,b=0,c=0,d=0,e=0,f=0,g=0;main() cobegin S1( ); S2( ); S3( );

24、S4( ); S5( ); S6( ); coendS1S2S3S4S5S6abcdefg问题：有如图所示的六个语句（进程），并发执行，其前趋问题：有如图所示的六个语句（进程），并发执行，其前趋关系如图，并发执行描述如下：关系如图，并发执行描述如下：S1( )v(a); v(b); S2( )p(a);v(c);v(d);S1S2S3S4S5S6abcdefgS3( )p(b);v(e);S4( )p(c); v(f);S5( )p(d);v(g);S6( )p(f); p(g); p(e);3.3.4 经典进程同步问题经典进程同步问题 1. 进程进程Pc 和和 Pp 合作完成计算和打印任务合

25、作完成计算和打印任务缓冲区缓冲区bufPcPp计算计算打印打印放入放入条件条件=缓冲区空缓冲区空取出结果取出结果条件条件=buf 非空非空非空非空空空为各并发进程设置私用信号量为各并发进程设置私用信号量为私用信号量赋初值为私用信号量赋初值利用利用PV原语和私用信号量规定进程的执行顺序。原语和私用信号量规定进程的执行顺序。3步：步： 私用信号量私用信号量：进程同步：进程同步; 公用信号量公用信号量：进程互斥：进程互斥解：解：设信号量：设信号量：bufempty=1表示表示buf 空，空， buffull=0表示表示buf满满 Pc: Pp: A: P(bufempty); B: P(bufful

26、l); 计算；计算； 取出取出buf中的数据中的数据 buf 计算结果计算结果 置空标记，打印置空标记，打印 V( buffull); V(bufempty); Goto A; Goto B; 思考：若上题中的思考：若上题中的Pc和和Pp如下如下Pc： Pp：Repeat Repeat 计算；计算； P(buffull); buf 计算结果计算结果 取出取出buf中的数据中的数据 V(buffull); 置空标记，打印置空标记，打印 P(bufempty) V(bufempty);Until false; Until false;则：则：buffull初值为初值为？，？，bufempty初值为

27、初值为？2. 生产者生产者/消费者问题消费者问题(the producer/consumer problem)问题描述：若干进程通过有限的共享缓冲区交换数据。问题描述：若干进程通过有限的共享缓冲区交换数据。其中，其中，生产者生产者进程不断写入，而进程不断写入，而消费者消费者进程不断进程不断读出；共享缓冲区共有读出；共享缓冲区共有N个；任何时刻只能有一个进个；任何时刻只能有一个进程可对共享缓冲区进行操作。程可对共享缓冲区进行操作。共享缓冲区共享缓冲区生产指针生产指针消费指针消费指针Producer 1Producer 2.Producer MConsumer 1Consumer 2.Consum

28、er N满满空空指针移动方向指针移动方向 分析：分析： 它是一个同步问题它是一个同步问题消费者想要接收一个数据消费者想要接收一个数据,有界缓冲区至少有一有界缓冲区至少有一个是满的个是满的生产者想要发送一个数据时生产者想要发送一个数据时,有界缓冲区至少有有界缓冲区至少有一个是空的一个是空的 它是一个互斥问题它是一个互斥问题有界缓冲区是临界资源有界缓冲区是临界资源,因此因此,各生产者进程必须互各生产者进程必须互斥执行斥执行 设信号量：设信号量： full是是“满满”数目，初值为数目，初值为0， empty是是空空数目，初值为数目，初值为N。实际上，。实际上，full和和empty是同一个含义：是同

29、一个含义：full + empty = N mutex用于访问缓冲区时的互斥，初值是用于访问缓冲区时的互斥，初值是1 ProducerP(empty);P(mutex);/进入区进入区 one unit - buffer;V(mutex);V(full);/退出区退出区ConsumerP(full);P(mutex);/进入区进入区 one unit buf;V(mutex);V(full);P(full);P(mutex);/进入区进入区 one unit-buf;V(mutex);V(empty);/退出区退出区当当full=N(empty=0), mutex = 1时，执行顺序：时，执行

30、顺序： Producer.P(empty) / P 阻塞，等待阻塞，等待Consumer发出的发出的empty信号信号 Consumer.P(mutex) / C阻塞，等待阻塞，等待Producer 发出的发出的full信号信号死锁死锁结结 论论 各进程必须先检查自己对应的资源数目，各进程必须先检查自己对应的资源数目，在确信有可用资源后再申请对整个缓冲区在确信有可用资源后再申请对整个缓冲区的操作。的操作。 如果先申请到对整个缓冲区的互斥操作后，如果先申请到对整个缓冲区的互斥操作后，才发现自己对应的缓冲区不能用，这时已才发现自己对应的缓冲区不能用，这时已不可能放弃对整个缓冲区的占用。不可能放弃对

31、整个缓冲区的占用。返回返回3.4 进程通信进程通信 低级通信：低级通信：只能传递状态和整数值（控制信息），只能传递状态和整数值（控制信息），包括进程互斥和同步所采用的信号量机制。包括进程互斥和同步所采用的信号量机制。 优点：速度快。优点：速度快。 缺点是：缺点是： 传送信息量小：效率低，每次通信传递的信息量固传送信息量小：效率低，每次通信传递的信息量固定，若传递较多信息则需要进行多次通信。定，若传递较多信息则需要进行多次通信。 编程复杂：用户直接实现通信的细节，编程复杂，编程复杂：用户直接实现通信的细节，编程复杂，容易出错容易出错。 高级通信：高级通信：能够传送任意数量的数据，包括：能够传送任

32、意数量的数据，包括：共共享存储器、消息、管道等享存储器、消息、管道等。1. 低级通信和高级通信低级通信和高级通信返回返回2. 高级通信方式高级通信方式汤汤一、共享存储器系统（一、共享存储器系统（Shared-memory system） 相互通信的进程相互通信的进程共享某些数据结构或共享存储区。共享某些数据结构或共享存储区。一一组进程向该公共区中写，另一组进程从公共区中读，组进程向该公共区中写，另一组进程从公共区中读，通过这种方式实现两组进程间的信息交换。因此又分通过这种方式实现两组进程间的信息交换。因此又分为：为：1.1.基于共享数据结构的通信方式：基于共享数据结构的通信方式：进程之间能够通过进程之间能够通过某种类型的数据结构（如有界缓冲区）交换信息，如某种类型的数据结构（如有界缓冲区）交换信息，如生产者和消费者问题。操作系统只负责提供共享存储生产者和消费者问题。操作系统只负责提供共享存储区，而共享数据结构和对进程间的同步处理都是程序区，而共享数据结构和对进程间的同步处理都是程序员的事。因而，通信效率低，只适合于传递少量信息。员的事。因而，通信效率低，只适合于传递少量信息。一、共享存储器系统（续）一、共享存储器系统（续）2.2.基于共享存储区的通信方式：基于共享存储区的通信方式：系统在存储区中划出一块共享存储区，各进程间可系统在存储区中划出一块