进程的同步与互斥

《进程的同步与互斥》由会员分享，可在线阅读，更多相关《进程的同步与互斥（45页珍藏版）》请在装配图网上搜索。

1、1 2021/4/6 第 3章 进程管理 3.1 进程的引入 3.2 进程的结构 3.3 进程控制 3.4 进程的同步与互斥 3.5 进程间通信 3.6 进程调度 3.7 死锁 3.8 线程 2 2021/4/6 两种制约关系 直接相互制约关系（同步） 间接相互制约关系（互斥） 产生的原因 进程合作 资源共享 3 2021/4/6 进程的同步（ 1） 直接相互制约关系（同步） 指系统中一些进程需要相互合作，共同完成一 项任务 ,这种协作进程之间相互等待对方消息或信 号的协调关系称为 进程同步 .具体说，并发进程在 一些关键点上可能需要互相等待与互通消息，进程 间的相互联系是 有意识 的安排的。

2、 产生的原因 进程合作 4 2021/4/6 进程的同步（ 2） 一般同步问题有两类 保证一组合作进程按逻辑需要的执行次序执行 【 例 】 司机 P1 售票员 P2 REPEAT REPEAT 启动 关门 正常运行 售票 到站停 开门 UNTIL FALSE UNTIL FALSE 保证共享缓冲区（共享数据）的合作进程的同步 【 例 】 输入 进程 PI 缓冲区 缓冲区 计算 进程 PC 打印 进程 PP 5 2021/4/6 进程的互斥 是解决进程间竞争关系 (间接制约关系 )的手段 。 间接相互制约关系（互斥） 是指若干个进程同时竞争一个 需要互斥使用 的资源 时，任何时刻最多允许一个进程

3、去使用，其 他要使用该资源的进程必须等待，直到该资源被释 放。进程间要通过某种中介发生联系，是 无意识 安 排的。 产生的原因 资源共享 互斥是一种特殊的同步 逐次使用互斥资源，也是对进程使用资源次序 上的一种协调。 6 2021/4/6 临界资源 临界资源 系统中某些资源 一次只允许一 个进程使用 ，称这样的资源为临界资 源或互斥资源或共享变量。 硬件临界资源：打印机、磁带机 软件临界资源：只能排它使用的变量、 表格、队列 7 2021/4/6 临界资源实例 二人合作存款 count=100; PA S1:N=count; S2:N=N+100; S3:count=N; PB S4:M=co

4、unt; S5:M=M+200; S6:count=M; 执行情况： （ 1） PA PB ,PB PA count=400 （ 2） S1 PBS2S3 count=200 （ 3） S4 PAS5S6 count=300 因 count是一个互斥性使用的变量，是一个临界资源 8 2021/4/6 临界区 临界区（临界段） 在进程中访问临界资源的那段代码区。 例子 9 2021/4/6 具有临界资源的进程结构 /*进入区 */ critical section; /*临界区 */ /*退出区 */ remainder section; /*剩余区 */ entry section exit

5、section 10 2021/4/6 访问临界区应遵循的原则 空闲让进 当无进程在临界区时，任何有权使用临界区 的进程可进入。 忙则等待 不允许两个以上的进程同时进入临界区。 有限等待 任何进入临界区的要求应在有限的时间内得 到满足。 让权等待 不能进入临界区的进程应放弃占用 CPU。 11 2021/4/6 临界区互斥解决方法 硬件 缺点：成本高 软件 用编程解决 缺点： (1)忙等待 (2)实现过于复杂，需要高的编程技巧 信号量机制 12 2021/4/6 信号量机制 一类资源 抽象成 S（信号量） 信号量 只能由 P、 V操作对其进行操作的变量 。 信号量的使用应注意 必须置一次且只能

6、置一次初值 。 初值只能为非负整数 ， 实现互斥时初值为 1。 只能执行 P、 V操作 。 13 2021/4/6 P、 V操作 P(S)：表示申请一个资源 。 V(S)：表示释放一个资源。 P、 V操作必须成对出现，有一个 P操作就一定 有一个 V操作。 14 2021/4/6 整型信号量 整型信号量 信号量 S：整型量 ， 除初始化外仅能通过 P、 V操作访问 P和 V操作原语定义： var S:integer; S=1; P(S)： while S 0 do no-op S = S -1； V(S )： S = S +1； 一类资源 抽象成 S（信号量） 整型量 15 2021/4/6

7、利用整型信号量实现进程互斥 P(S) V(S) P1 P2 互斥区 P(S) V(S) 16 2021/4/6 记录型信号量 记录型信号量 信号量 S：记录型数据结构 ,一个分量为整型量 value,另 一个分量为信号量队列 L； 信号量的物理含义 当 S.value0：表示可用资源个数 当 S.value 0：表示可用资源正好用完 当 S.value0：表示等待该类资源的进程数 一类资源 抽象成 S（信号量） value0 L=nil 信号量的值 (-2) 信号量队列指针 17 2021/4/6 struct semaphore int value; int *L; void P(struc

8、t semaphore S); S.value = S.value 1; /* 把信号量减去 1 */ if S.value 0 then block(S.L); /* 若信号量小于 0， 则调用 P(S)的进 程被置成等待信号量 S的状态 */ 物理意义：申请一个资源 ， 如果申请成功 ， 则返回；如果申请不成功 ， 则挂在该资源的等待队列上 。 void V(struct semaphore S); S.value = S.value + 1; /* 把信号量加 1 */ if S.value 0: 表示有 S .value个资源可用 S .value =0: 表示无资源可用 S .val

9、ue 0: 则 | S .value|表示等待队列中的进程 个数 信号量的初值应该大于等于 0 20 2021/4/6 P、 V操作讨论 (2) P(S)：表示申请一个资源 V(S)：表示释放一个资源。 P、 V操作必须成对出现，有一个 P操作就一定 有一个 V操作 P、 V操作的优点 简单，而且表达能力强，可解决任何互斥问题 P、 V操作的缺点 不够安全， P、 V操作使用不当会出现死锁，遇 到复杂互斥问题时，实现复杂。 21 2021/4/6 用 P、 V操作实现互斥 信号量初值为 1 对于两个并发进程，互斥信号量的值仅取 1、 0 和 -1三个值 ： 若 mutex.value 1表示没

10、有进程进入临界区 若 mutex.value 0表示有一个进程进入临界 区 若 mutex.value -1表示一个进程进入临界区， 另一个进程等待进入。 22 2021/4/6 利用 P、 V操作实现两个进程互斥的模板如下 ： struct semaphore mutex; mutex.value=1; mutex.L=nil; cobegin Process P1:Begin M P(mutex); 临界区 1 V(mutex); M End Process P2:Begin M P(mutex); 临界区 2 V(mutex); M End coend 23 2021/4/6 使用 PV

11、操作实现互斥应注意 识别临界资源 是否被共享 ; 是否有排它性使用要求。 临界区代码应尽量短小，不能有死循环。 P和 V原语应分别紧靠临界区的头尾。 P、 V操作在同一进程中必须成对出现。 24 2021/4/6 思考题 用记录型信号量解决二人存款问题，用 类 C语言编写进程互斥算法 。 25 2021/4/6 用 P、 V操作实现 进程的同步 只要信号量初值是一个大于等于 0的整数就能 达到同步的目的，就可以直接使用 P、 V操作 实现同步 互斥是一种特殊的同步 P、 V操作既可以实现互斥，也可以实现同步 利用信号量实现进程同步的实例 设有三个并发执行的进程 P1、 P2、 P3，其前趋图如

12、下， 试用信号量实现这三个进程同步。 设两个同步信号量 S1、 S2分别表示进程 P2、 P3能否开始执行 struct semaphore S1,S2=0,0; /*初值均为 0*/ cobegin P1: V(S1); V(S2); P2: P(S1); ; P3: P(S2); ; coend P1 P3 P2 27 2021/4/6 使用 PV操作实现同步应注意 信号量的设置 信号量的初值 PV操作要成对出现，并在不同的 进程中 28 2021/4/6 信号量及 P、 V操作讨论 (3) (1) P、 V操作必须成对出现，有一个 P操作就一定有一 个 V操作 (2) 当为互斥操作时，它

13、们同处于同一进程 当为同步操作时，则不在同一进程中出现 (3) 如果 P(S1)和 P(S2)两个操作在一起，那么 P操作的 顺序至关重要。 一个同步 P操作与一个互斥 P操作在一起时，同步 P操作在互斥 P操作前，而两个 V操作无关紧要。 29 2021/4/6 PV操作实现互斥与同步的模板 进程互斥 S初值为 1 P1 P2 P(S) P(S) 临界区 1 临界区 2 V(S) V(S) 在 P1与 P2中设置相同的 P、 V操作 进程同步 S1初值为 n， S2初值为 0 P1 P2 P(S1) P(S2) 段 1 段 2 V(S2) V(S1) 30 2021/4/6 经典的进程同步问

14、题 生产者 /消费者问题 读者 /写者问题 哲学家进餐问题 31 2021/4/6 生产者 /消费者问题 生产者消费者问题是一种同步问题的抽 象描述 。 计算机系统中的每个进程都可以消 费 （ 使用 ） 或生产 （ 释放 ） 某类资源 。 这些 资源可以是硬件资源 ， 也可以是软件资源 。 当某一进程使用某一资源时 ， 可以看作 是消费 ， 称该进程为消费者 。 而当某一进程 释放某一资源时 ， 它就相当于生产者 。 32 2021/4/6 生产者 /消费者问题 (描述 ) 通过一个公用缓冲池可以把一群生产者 p1,p2,pm ，和一群消费者 Q1,Q2,Qn 联 系起来。如图 : 只要缓冲区

15、未满，生产者就可以把产品送入 缓冲区 ; 只要缓冲区未空，消费者就可以从缓冲区中 取走物品。 33 2021/4/6 生产者 /消费者问题 (图示 ) . . P Q 放消息 取消息 n n 个缓冲区 (Buffer) i j 34 2021/4/6 生产者 /消费者问题 (分析 ) 为解决生产者消费者问题，应该设两个同步信号量，一个说 明空缓冲区的数目，用 empty表示，初值为缓冲池的大小 N， 另一个说明已用缓冲区的数目，用 full表示，初值为。 由于在此问题中有 i个生产者和 j个消费者，它们在执行生产活 动和消费活动中要对缓冲池进行操作。由于缓冲池是一个临 界资源，必须互斥使用，所

16、以，另外还需要设置一个互斥信 号量 mutex，其初值为。 struct semaphone empty=n, full=0, mutex=1; void buffern-1; int in=, out=0; 35 2021/4/6 生产者 /消费者问题 (解决 ) Consumerj: while(1) P(full); P(mutex); 从 Bufferout取产品 ; out = (out+1) mod n; V(mutex); V(empty); 消费产品 ; coend; cobegin procedurei: while(1) 生产产品 ; P(empty); P(mutex);

17、 往 Buffer in放产品 ; in = (in+1) mod n; V(mutex); V(full); 36 2021/4/6 生产者 /消费者问题 (思考 ) 在生产者进程和消费者进程中，两个 P操作 的执行顺序是否能交换？两个 V操作的执行 顺序是否能交换？ 37 2021/4/6 思考题 两个进程合作完成数据计算和打印工作， 计算进程未计算完就不可打印，反之也然， 双方共用一个缓冲区，写出此算法 。 38 2021/4/6 读者 /写者问题 有两组并发进程 : 读者和写者 ,共享一个数据文件 要求： 允许多个读者同时执行读操作 不允许读者、写者同时操作 不允许多个写者同时操作 3

18、9 2021/4/6 读者 /写者问题 如果读者来： 1）无读者、写者，新读者可以读 2）有写者等，但有其它读者正在读，则新读者也可以读 3）有写者写，新读者等 如果写者来： 1）无读者、写者，新写者可以写 2）有读者，新写者等待 3）有其它写者，新写者等待 40 2021/4/6 读者写者问题的解法 为实现读者和写者、写者和写者之间的互斥，设置一个互斥 信号量 Wmutex=1 由于“读 读”允许，再设置一个整型变量 Readcount表示 正在读的进程数，初值 Readcount=0 由于 Readcount是一个可被多个读者进程访问的临界资源 ， 所以要为它设置一个互斥信号量 Rmute

19、x=1 读者 写者算法如下： 读者： P(Rmutex); if readcount=0 then P(Wmutex); Readcount= Readcount+1; V(Rmutex); 读 P(Rmutex); Readcount= Readcount-1; if Readcount=0 then V(Wmutex); V(Rmutex); 写者： P(Wmutex); 写 V(Wmutex); 41 2021/4/6 哲学家就餐问题 有五个哲学家围坐在一圆桌旁， 桌中央有一盘通心粉，每人面前 有一只空盘子，每两人之间放一 只筷子。 每个哲学家的行为是思考，感到 饥饿，取筷子，然后吃通心

20、粉， 放筷子，思考。 为了吃通心粉，每个哲学家必须 拿到两只筷子，并且每个人只能 直接从自己的左边或右边去取筷 子。 筷子是临界资源，要用 5个互斥 信号量来表示这 5只筷子。 42 2021/4/6 哲学家就餐问题解 设 fork5为 5 个信号量，初值均为 1 struct semaphore fork 4; forki:= 1; Philosopheri： While(1) 思考； P(forki); P(fork(i+1) mod 5)； 进食； V(forki); V(fork(i+1) mod 5)； 以上解法会出现死锁 ,为防止死锁发生可采 取的措施： 最多允许 4个哲学家同时坐

21、在桌子周围 给所有哲学家编号，奇数号的哲学家必须首 先拿左边的筷子，偶数号的哲学家则反 仅当一个哲学家左右两边的筷子都可用 时，才允许他拿筷子（ ） 43 2021/4/6 思考题 桌子上有一只盘子 ， 每次只能放入一 只水果 。 爸爸专向盘中放苹果 ， 妈妈专向盘 中放桔子 ， 一个儿子专等吃盘中的桔子 ， 一 个女儿专等吃盘中的苹果 。 请利用 P、 V操作 写出父亲 、 母亲 、 儿子 、 女儿进程的同步算 法 。 44 2021/4/6 思考题 分析：在本题中 ， 应设置三个信号量 s、 so、 sa， 信号量 s表示盘子是否为空 ， 其初值为 1； 信号量 so表示盘中是否有桔子 ， 其初值为 0； 信号量 sa表示盘中是否有苹果 ， 其初值为 0。 同步描述如下： 45 2021/4/6 struct semaphone s=1, so=0, sa=0; cobegin father ( ); mother( ); son ( ); daughter ( ); coend father ( ) p(s); 将水果放入盘中； v(sa); mother ( ) p(s); 将水果放入盘中； v(so); son ( ) p(so); 从盘中取出桔子； v(s); 吃桔子； daughter ( ) p(sa); 从盘中取出苹果； v(s); 吃苹果；