第3章 进程管理3-进程互斥.ppt

* 互斥问题举例1 首先需要找到共享的临界资源； 如右图所示程序中，每个进程中含有多个变量，但只有共享的公共变量a才是共享的临界资源，而c和y都不是； 找到了共享的临界资源a，则每个程序中涉及该资源a的程序段都是临界区； 为临界资源a设置信号量mutex及其初值； 再针对每个临界区使用mutex的P、V操作将临界区括起来。 * 3.5.4 用P,V原语实现进程互斥 用信号量实现两并发进程PA，PB互斥的描述如下： ⑴设sem为互斥信号量，其取值范围为(1,0,-1) 其中sem=1表示进程PA和PB都未进入类名为S的临界区，sem=0表示进程PA或PB已进入类名为S的临界区，sem=-1进程PA和PB中，一个进程已进入临界区，另一进程等待进入。 ⑵描述: PA: PB: P(sem) P(sem) S S V(sem) V(sem) …… …… * 互斥问题举例2 对于飞机订票系统的例子，可以采用下列方法解决“与时间有关的错误”：针对临界资源机票数设置一个信号量mutex，初值为1。每个终端进程中的程序描述如下： P（mutex）； 在机票数据库中取出当前剩余票数X； 判断X0（有票吗）？ 如果有， X≥N（票够吗）？ 如果够，则出票（打印票据）； X＝X－N（修改剩余票数）； 将X回写到数据库中； V（mutex）； * 互斥问题举例2 如果终端A先来，对mutex进行P操作后，进入临界区，此时mutex为0。当它还没有处理完毕时，其它任何终端到来都因其执行P(mutex)后被阻塞，直到终端A执行了V(mutex)后将它们唤醒后才能进入其临界区对x进行操作，从而保证了只有一个进程进入临界区，避免了“与时间有关的错误” 的发生。 * 互斥问题举例2 如果有n个终端，则mutex信号量的取值范围为： －（n－1）≤mutex≤1 其物理含义为： 当机票数空闲时，mutex=1。 当有一个终端进入，对机票进行处理，其它终端进程还没有到来时，mutex=0。 当所有终端进程都到来，且有一个正在对机票进行处理时，mutex=－（n－1）。它表示有n－1个进程在等待队列上等待。 * [例]假设某飞机定票系统在t0时刻有A、B、C、D四个终端程序同时都要对机票库中的某航班当前剩余票数X进行操作。如果每个终端程序的当前定票需求为N，并对共享变量X进行如下操作： 在机票数据库中取出当前剩余票数X； 判断X0（有票吗）？ 如果有， X≥N（票够吗）？ 如果够，则出票（打印票据）； X＝X－N（修改剩余票数）； 将X回写到数据库中； 互斥问题举例2 问题：x代表某航班的可用座位数，p1和p2两个售票进程，售票工作是对变量x减1。试用信号量的P、V操作实现这两个进程的互斥。 设：mutex为互斥信号量, p1( ) { …… p(mutex)； …… x:=x-1 ； v(mutex)； …… } p2( ) { …… p(mutex)； …… x:=x-1 ； v(mutex)； …… } * 互斥问题举例3 某车站售票厅有20个窗口，任何时刻最多可容纳20名购票者进入，当售票厅中少于20名购票者时，则厅外的购票者可立即进入，否则需在厅外等待。若把一个购票者看作一个进程，请用P、V操作管理这些并发进程，要求如下： ⑴．在主函数中给出信号量的定义和初值。 ⑵．给出一个购票者进程的算法。 ⑶．给出当购票者最多不超过n (设n20)个时，信号量可能的变化范围。 互斥问题举例3 问题分析： 可以将该售票厅的每个窗口看作是一个临界资源为每个购票者进程共享，每个购票者进程只能使用其中一个窗口。 售票厅有20个窗口，所以有20个同类的临界资源，一次可以允许20个进程进入，并且先来者先进入。 由此可知：该问题满足互斥的2个必要条件（共享临界资源，共享方式是先来者先进入），所以该问题是互斥问题。 根据互斥问题的解决方法设置信号量并赋初值： 设置一个信号量mutex，初值为20。 用信号量的P、V操作将临界区括起来。 ⑴．主函数算法： main() { int mutex=20; cobegin P1(); …Pi();…Pn(); coend } ⑵．购票者i的算法： Pi() { P(mutex); 进入售票厅占有一个窗口购票； V(mutex); } 算法描述 ⑶．信号量mutex的取值范围： －(n－20) ≤ mutex ≤ 20 其物理含义是： 当mutex=20时，表示售票厅内没有购票者进入，20个窗口都是空闲的，表示可用资源个数； 当mutex=0时，表示售票