进程同步及互斥(1)

1、进程间的相互作用 进程间的联系 进程的同步机制信号量及P.V操作（解决进程同步互斥问题） 进程间的联系相交进程与无关进程相交进程：指多个并发进程在逻辑上有某种联系无关进程（不相交进程）：在逻辑上无任何联系的进程直接作用和间接作用直接作用：进程间的相互联系是有意识的安排的，直接作用只发生在相交进程间间接作用：进程间要通过某种中介发生联系，是无意识安排的，可发生在相交进程之间，也可发生在无关进程之间进程的同步（直接作用）进程的同步：synchronism指系统中多个进程中发生的事件存在某种时序关系，需要相互合作，共同完成一项任务。具体说，一个进程运行到某一点时要求另一伙伴进程为它提供消息，在未获得

2、消息之前，该进程处于等待状态，获得消息后被唤醒进入就绪态。进程的互斥（间接作用）mutual exclusion 由于各进程要求共享资源，而有些资源需要互斥使用，因此各进程间竞争使用这些资源，进程的这种关系为进程的互斥 临界资源（临界资源（Critical resourceCritical resource）：）：系统中某些资源系统中某些资源一次只允许一个进程使用，这样的资源称为临界资源一次只允许一个进程使用，这样的资源称为临界资源或互斥资源或共享变量。或互斥资源或共享变量。 临界区（临界区（Critical regionCritical region）：）：把不允许多个并发进把不允许多个并发

3、进程交叉执行的一段程序称为临界区或临界部分。程交叉执行的一段程序称为临界区或临界部分。 临界区就是访问公用数据的那段程序。临界区就是访问公用数据的那段程序。 例如堆栈操作中的例如堆栈操作中的get(top)get(top)和和rel(blk)rel(blk)程序。程序。程 序 段1程 序 段2程 序 段n共 享 变 量临界区（互斥区）：critical section一个程序片段的集合，这些程序片段分散在不同的进程中，对某个共享的数据结构（共享资源）进行操作。 在进程中涉及到临界资源的程序段叫临界区。 多个进程的临界区称为相关临界区。 在临界区前面增加一段用于进行检查的代码，称为进入区。 在临

4、界区后面加上一段代码，称为退出区。 进程中除了进入区、临界区及退出区之外的其它部分的代码，称为剩余区。使用互斥区的原则：空闲让进：当无进程在互斥区时，任何有权使用互斥区的进程可进入忙则等待：不允许两个以上的进程同时进入互斥区有限等待：任何进入互斥区的要求应在有限的时间内得到满足让权等待：处于等待状态的进程应放弃占用CPU，以使其他进程有机会得到CPU的使用权使用互斥区的原则：前提：任何进程无权停止其它进程的运行 进程之间相对运行速度无硬性规定进程互斥的解决有两种做法:由竞争各方平等协商引入进程管理者，由管理者来协调竞争各方对互斥资源的使用具体方法：硬件（当一个进程进入临界区,就屏蔽所有中断，但

5、成本高）软件（用编程解决，但常常忙等待 ）进程互斥的软件方法 通过平等协商方式实现进程互斥的最初方法是软件方法 。其基本思路是在进入区检查和设置一些标志，如果已有进程在临界区，则在进入区通过循环检查进行等待；在退出区修改标志。 其中的主要问题是设置什么标志和如何检查标志。设有两个计算进程PA、PB共享内存MS。其中MS分为三个领域，即系统区、进程工作区和数据区。这里数据区被划分大小相等的块，每个块中既可能放有数据，也有可能未放有数据。系统区主要是堆栈S，其中存放那些空数据块的地址。 如图所示： getspace（） int g; gstacktop; toptop-1;执行getspace就是

6、获取一个空数据 release(ad) toptop+1 ； stacktopad ； release(ad)就是释放一个地址为ad的数据块 信号量：semaphore 是一个数据结构 定义如下： struct semaphore int value;pointer_PCB queue; 信号量说明： semaphore s;P、V操作P(s) s.value = s.value -; if (s.value 0) 该进程状态置为等待状态； 将该进程的PCB插入相应的等待队列末尾s.queue; V操作V(s) s.value = s.value +; if (s.value = 0) 唤醒相

7、应等待队列s.queue中等待的一个进程； 改变其状态为就绪态 并将其插入就绪队列； P、V操作为原语操作原语：primitive or atomic action 是由若干多机器指令构成的完成某种特定功能的一段程序，具有不可分割性即原语的执行必须是连续的，在执行过程中不允许被中断 实现：开关中断信号量的使用： 必须置一次且只能置一次初值 初值不能为负数 只能执行P、V操作用用P P、V V操作解决进程间互斥问题操作解决进程间互斥问题P(mutex)V(mutex)P1P2P3互斥区互斥区P(mutex)P(mutex)V(mutex)V(mutex)三个进程共用两个I/O缓冲区。解：设用信号

8、量S表示共享资源，S初始值为2 互斥例子例：用信号量及例：用信号量及P P、V V原语实现两个并发进程原语实现两个并发进程PaPa和和PbPb互斥。互斥。两进程都想进入临界区两进程都想进入临界区S S。解：解：1 1）设）设semsem为互斥信号量，表示临界区是否可进入为互斥信号量，表示临界区是否可进入2 2）设）设semsem的初始值为的初始值为1 1，表示临界区可用，表示临界区可用3 3）描述：）描述：PaPa： Pb:Pb:P(sem) P(sem)P(sem) P(sem) V(sem) V(sem)V(sem) V(sem) 例：大学校门处要求来客登记，只有一张登记表，例：大学校门处

9、要求来客登记，只有一张登记表，登记表同时只能由一个人使用，用登记表同时只能由一个人使用，用P P、V V原语描述一原语描述一个校外人员进入大学的过程。个校外人员进入大学的过程。解：解：1 1）设互斥信号量）设互斥信号量mutexmutex，表示登记表是否正在使用，表示登记表是否正在使用2 2）设）设mutexmutex初始值为初始值为1 1，表示登记表没有人使用，表示登记表没有人使用3 3）描述：）描述：Enter:Enter: P(mutex) / P(mutex) /申请登记表申请登记表 登记登记 V(mutex) /V(mutex) /释放登记表释放登记表 有A、B两进程，A进程从卡片机

10、读信息入缓冲区，B进程负责加工读进缓冲区的卡片 解：设信号量S1：缓冲区中有否可供加工的信息，初始值为0；信号量S2：缓冲区是否为空，初始值为1。同步例子 下列活动属于哪种制约关系 (1) 若干同学去图书馆借书 (2) 两队进行篮球比赛 (3) 流水线生产的各道工序 (4) 商品生产和社会消费习题 某仓库有两名发货员，一名审核员。当顾客提货时，只要发货员空闲，允许顾客进入仓库提货，顾客离开时，审核员检验顾客提货是否正确。其工作流程如下图所示。为了利用PV操作正确地协调他们之间的工作，设置了两个信号量S1和S2，初值分别位2，1。图中的a，b，c，d应分别填（）。顾客进程 （i =1，2，n）a

11、在仓库提货bc检验d应用实例 例1 P1进程和P2进程共享一台打印机，用信号量和P、V操作实现它们的互斥。 例2 矩阵A+B=矩阵和，用信号量和P、V原语操作实现它们的同步。A用甲进程表示，B用乙进程表示。 例3 矩阵A+B= C，用信号量和P、V原语操作实现它们的同步。A用甲进程表示，B用乙进程表示，C用丙进程表示。 例4 设公共汽车上，司机和售票员的活动分别是 司机活动：启动车辆；正常运行；到站停车 售票员活动：关门；售票；开门 用信号量和P、V操作实现它们的关系经典的生产者消费者问题消费者消费者生产者生产者经典的生产者消费者问题同步问题： P进程不能往“满”的缓冲区中放产品，设置信号量为

12、S1 Q进程不能从“空”的缓冲区中取产品，设置信号量S2S1初值为1，S2初值为0P： Q：while (true) while (true) 生产一个产品; P(s2); P(s1) ; 从缓冲区取产品; 送产品到缓冲区; V(s1); V(s2); 消费产品; ;.PQ放 消 息取 消 息nn个 缓 冲 区(Buffer)ij多个缓冲区的生产者和消费者P：i = 0;while (true) 生产产品; P(S1); 往Buffer i放产品; V(S2); i = (i+1) % n; ;Q： j = 0; while (true) P(S2); 从Bufferj取产品; V(S1);

13、消费产品; j = (j+1) % n; ;共享缓冲区共享缓冲区n n生产指针生产指针消费指针消费指针Producer 1Producer 2.Producer MConsumer 1Consumer 2.Consumer K满满空空指针移动方向指针移动方向 P1 有界缓冲区 Q1 P2 Q2 P3 Q3 : : Pm-1 Qk-1 Pm QkQ： j = 0; while (true) P(S2); P(mutex); 从Bufferj取产品; V(mutex); V(S1); 消费产品; j = (j+1) % n; ;n个缓冲区、m个生产者和k个消费者P：i = 0;while (tru

14、e) 生产产品; P(S1); P(mutex); 往Buffer i放产品; V(mutex); V(S2); i = (i+1) % n; ;有错误？若颠倒两个有错误？若颠倒两个P操作的顺操作的顺 序？序？ P：i = 0;while (true) 生产产品; P(mutex); P(S1); 往Buffer i放产品; V(mutex); V(S2); i = (i+1) % n; ;Q： j = 0; while (true) P(mutex); P(S2); 从Bufferj取产品; V(mutex); V(S1); 消费产品; j = (j+1) % n; ;错误错误Q： j =

15、0; while (true) P(S2); P(mutex); 从Bufferj取产品; j = (j+1) % n; V(mutex); V(S1); 消费产品;n个缓冲区、m个生产者和k个消费者P：i = 0;while (true) 生产产品; P(S1); P(mutex); 往Buffer i放产品; i = (i+1) % n; V(mutex); V(S2); ;正正 确确P.V操作讨论1) 信号量的物理含义：S0表示有S个资源可用S=0表示无资源可用S=1 & S2 = 1 & & Sn = 1)/满足资源要求时的处理；满足资源要求时的处理； for

16、(i = 1; i = n; +i) -Si; /注：与注：与P的处理不同，这里是在确信可满足的处理不同，这里是在确信可满足 / / 资源要求时，才进行减资源要求时，才进行减1操作；操作；break;else /某些资源不够时的处理；某些资源不够时的处理； 调用进程进入第一个小于1信号量的等待队列Si.queue; 阻塞调用进程; Ssignal(S1, S2, , Sn)/V操作for (i = 1; i = ti；即当资源数量低于ti时，便不予分配）占用值为di（表示资源的申请量，即Si = Si - di）对应的P、V原语格式为：Swait(S1, t1, d1; .; Sn, tn,

17、dn);Ssignal(S1, d1; .; Sn, dn);一般“信号量集”可以用于各种情况的资源分配和释放，几种特殊情况： Swait(S, d, d)表示每次申请d个资源，当少于d个时，便不分配 Swait(S, 1, 1)表示互斥信号量 Swait(S, 1, 0)可作为一个可控开关 （当S1时，允许多个进程进入临界区； 当S=0时，禁止任何进程进入临界区）3 IPC经典问题1.读者写者问题 有两组并发进程: 读者和写者,共享一组数据区 要求： 允许多个读者同时执行读操作 不允许读者、写者同时操作 不允许多个写者同时操作第一类：读者优先如果读者来：1）无读者、写者，新读者可以读2）有写

18、者等，但有其它读者正在读，则新读者也可以读3）有写者写，新读者等如果写者来：1）无读者，新写者可以写2）有读者，新写者等待3）有其它写者，新写者等待第一类读者写者问题的解法读者： while (true) P(mutex); readcount +; if (readcount=1) P (w); V(mutex); 读; P(mutex); readcount -; if (readcount=0) V(w); V(mutex); ;写者： while (true) P(w); 写; V(w); ;第一类读者写者问题的解法（一般信号量集）写者：Swait(wmutex,1,1; rcount

19、,R,0);写；Ssignal(wmutex,1);读者：Swait(rcount,1,1; wmutex,1,0);读；Ssignal(rcount,1);2.哲学家就餐问题有五个哲学家围坐在一圆桌旁，桌中央有一盘通心粉，每人面前有一只空盘子，每两人之间放一只筷子 每个哲学家的行为是思考，感到饥饿，然后吃通心粉为了吃通心粉，每个哲学家必须拿到两只筷子，并且每个人只能直接从自己的左边或右边去取筷子用用P P、V V原语实现原语实现 哲学家问题哲学家问题 例：例：5 5个哲学家在圆桌前进餐，两个人之间各放一个哲学家在圆桌前进餐，两个人之间各放一根筷子。哲学家或者思考或者分别取左右手边的筷根筷子。

20、哲学家或者思考或者分别取左右手边的筷子进餐。请用子进餐。请用P P、V V原语描述每个哲学家的进餐过程。原语描述每个哲学家的进餐过程。0123414032用用P P、V V原语实现原语实现 哲学家问题哲学家问题( (完整完整) )解：解：1 1）设公用信号量）设公用信号量mutexmutex表表示哲学家是否能同时取到示哲学家是否能同时取到2 2个个筷子，筷子，sisi表示是否能取到表示是否能取到第第I I个筷子（个筷子（i=0,1,2,3,4 i=0,1,2,3,4 ） 2 2）设初始值）设初始值mutex=1mutex=1，si=1 si=1 （i=0,1,2,3,4 i=0,1,2,3,4

21、 ） 3 3）描述第）描述第i i个哲学家个哲学家PiPi：Pi:while(true) think; P(mutex); P(si); P(s(i+1) mod 5); V(mutex); eat; V(si); V (s(i+1) mod 5); 解决思路如下：让奇数号的哲学家先取右手边的筷子，让偶数号解决思路如下：让奇数号的哲学家先取右手边的筷子，让偶数号的哲学家先取左手边的筷子。的哲学家先取左手边的筷子。 这样任何一个哲学家拿到一只筷子以后，就已经阻止了邻座这样任何一个哲学家拿到一只筷子以后，就已经阻止了邻座的一个哲学家吃饭的企图，除非某个哲学家一直吃下去，否则不的一个哲学家吃饭的企图，除非某个哲学家一直吃下去，否则不会有人饿死。会有人饿死。描述第描述第i i个哲学家个哲学家PiPi：Pi:While(true) if (i mod 2=0) P(si); P(s(i+1)mod 5); Eat; V(si); V(s(i+1)mod 5);el