ch2_5剖析

《ch2_5剖析》由会员分享，可在线阅读，更多相关《ch2_5剖析（45页珍藏版）》请在金锄头文库上搜索。

1、问题描述 若干读者和写者进程共享一个信息资源（如数据文件或记录等）。 读者：只要求读共享资源的进程； 写者：除读者之外，要求访问共享对象的其他进程 多个读者可以同时访问共享对象 写者与读者之间必须互斥地访问共享对象 写者之间也必须互斥地访问共享对象,2.5 经典进程同步问题,3.读者-写者问题（读者优先）,临界资源和信号量 共享对象（如数据文件）,2.5 经典进程同步问题,3.读者-写者问题, 互斥信号量mutex,(初值为1）,semaphore mutex=1 ,NULL; semaphore rmutex=1 ,NULL;/稍后解释 int readcount= 0; writer()

2、while(1) wait(mutex); writing signal(mutex); ,算法描述,reader() while(1) reading ,wait(mutex);,signal(mutex);,/只第1个读者才需要申请共享的数据文件 if (readcount=0) wait(mutex); readcount+;,/最后1个读者需释放共享资源； readcount-; if (readcount=0) signal(mutex);,临界资源和信号量 共享对象（如数据文件） 整形变量readcount, 互斥信号量mutex,(初值为1）, 互斥信号量rmutex,(初值为1

3、）,reader() while(1) wait(rmutex); if (readcount=0) wait(mutex); /第1个读者 readcount+; signal (rmutex); reading wait(rmutex); readcount-; if (readcount=0) signal(mutex); /最后1个读者 signal(rmutex); ,读者、写者完全按时间顺序 如果前面没有写者，则多个读者可以同时读共享对象；否则，读者必须等前面的写者完成写操作后再读。,2.5 经典进程同步问题,semaphore S=1 ,NULL; semaphore mutex

4、=1 ,NULL; semaphore rmutex=1 ,NULL; int readcount= 0; writer() while(1) wait(S); wait(mutex); signal(S); writing signal(mutex); ,读者、写者完全按时间顺序的算法描述,reader() while(1) wait(S); wait(rmutex); if (readcount=0) wait(mutex); /第1个读者 signal(S); readcount+; signal (rmutex); reading wait(rmutex); readcount-; i

5、f (readcount=0) signal(mutex); /最后1个读者 signal(rmutex); ,写者优先 写者优先于读者（一旦有写者，则后续读者必须等待，唤醒时优先考虑写者）,2.5 经典进程同步问题,semaphore S=1 ,NULL; semaphore mutex=1 ,NULL; semaphore rmutex=1 ,NULL; int readcount= 0; int writecount=0; semaphore wcmutex=1,NULL;,写者优先的算法描述,writer() while(1) wait(wcmutex); if (writecount

6、=0) wait(S); writecount+; signal(wcmutex); wait(mutex); writing signal(mutex); wait(wcmutex); writecount-; if( writecount=0) signal(S); signal(wcmutex); ,reader() while(1) wait(S2); wait(S); wait(rmutex); if (readcount=0) wait(mutex); /第1个读者 signal(S); signal(S2); readcount+; signal (rmutex); readin

7、g ,写者优先权进一步提高,例1 某小型超级市场，可容纳50人同时购物。入口处有篮子，每个购物者可拿一只篮子入内购物。出口处结帐，并归还篮子（出、入口禁止多人同时通过）。试用信号量和P、V操作写出购物者的同步算法。,这是个典型的进程互斥问题,解答:,所用信号量设置如下： ）资源信号量S，初值为50，用以保证最多可以有50个购物者同时进入超市。 ）互斥信号量mutex，初值为1，用以保证同时只能有一个购物者进程进入出入口拿起篮子或者结帐后放下篮子。 用信号量机制给出的每个购物者购物过程的算法描述如下：,购物者i（解法一） 购物者i（解法二）：,P（S）； P（S）； P（mutex）； P（mu

8、tex1）； 从入口处进超市，并取一只篮子； 同左； V（mutex）； V（mutex1）； 进超市内选购商品； 同左 ； P（mutex）； P（mutex2）； 到出口结帐，并归还篮子； 同左 ； V（mutex）； V（mutex2）； 从出口离开超市； 同左 ； V（S）； V（S）； 结 束. 结 束.,出入口在一起： 出入口不在一起：,例2： 桌上有个只能盛得下一个水果的空盘子。爸爸可向盘中放苹果或桔子，儿子专等吃盘中的桔子，女儿专等吃盘中的苹果。规定：当盘子空时，一次只能放入一个水果供吃者取用。试用信号量和P、V操作实现爸爸、儿子和女儿这三个循环进程之间的同步。,本题属于生产者

9、消费者问题的变形，相当于一个能生产两种产品的生产者（爸爸）向两个消费者（儿子和女儿）提供产品的同步问题。因此，可参考生产者与消费者问题的解法。,解答：所用信号量设置如下：,）同步信号量empty，初值为1，表示盘子是空的，即儿子或女儿已把盘中的水果取走。 ）同步信号量orange，初值为0，表示爸爸尚未把桔子放入盘中。 ）同步信号量apple，初值为0，表示爸爸尚未把苹果放入盘中。,使用信号量机制的三个进程的同步描述如下：,爸爸进程（P）： 儿子进程（C1）： 女儿进程（C2）： P（empty）； P（orange ）； P（apple）； 将水果放入盘中； 从盘中取出桔子； 从盘中取出苹果

10、； 若放入的是桔子， V（empty）； V（empty）； 则V（orange）； 吃桔子； 吃苹果； 否则，V（apple）；,作业： 设A、B两点之间是一段东西向的单行车道，现在要设计一个AB路段自动管理系统，管理规则如下：当AB间有车辆在行驶时同方向的车可以同时驶入AB段，但另一方向的车必须在AB段外等待；当AB段之间无车辆行驶时，到达AB段的任一方向的车都可进入AB段，但不能从两个方向同时驶入，即只能有一个方向的车驶入；当某方向在AB段行驶的车辆驶出了AB段且暂无车辆进入AB段时，应让另一方向等待的车辆进入AB段行驶。试用信号量和P、V操作管理AB路段车辆的行驶。,解答：所用信号量和

11、其他变量设置如下：,）整型变量Car_A，初值为0， 用于对从A点（东）驶入AB段的车辆进行记数。 ）整型变量Car_B，初值为0， 用于对从B点（西）驶入AB段的车辆进行记数。 ）互斥信号量mutex，初值为1， 用于实现不同方向的第一辆车互斥驶入AB路段。 ）互斥信号量ma，初值为1， 用于实现东西向的车互斥地访问计数器变量Car_A。 ）互斥信号量mb，初值为1， 用于实现西东向的车互斥地访问计数器变量Car_B。,东向西行驶的车辆i 西向东行驶的车辆j,P（ma）； P（mb）； 若Car_A=0则 P（mutex）； 若Car_B=0则 P（mutex）； Car_A加1； Car_

12、B加1； V（ma）； V（mb）； 车辆从A点通过AB路段 车辆从B点通过AB路段 到达B点 到达A点； P（ma）； P（mb）； Car_A减1； Car_B减1； Car_A=0则 V（mutex）； Car_B=0则 V（mutex）； V（ma）； V（mb）；,1. 管程的引人 2. 管程的基本概念 管程的定义 一个管程定义了一个数据结构和能为并发进程所执行（在该数据结构上）的一组操作，这组操作能同步进程和改变管程中的数据。 管程的组成 管程名称 局部于管程内部的共享数据结构的说明； 对该数据结构进行操作的一组过程； 初始化共享数据结构的语句。,2.6 管程机制,管程的特性 模块

13、化 信息隐蔽性 管程内的局部变量只能被局部于管程内的过程所访问，反之亦然，即局部于管程内的过程只能访问管程内的变量。 任何进程只能通过调用管程提供的过程入口进入管程。 任一时刻，最多只能有一个进程在管程中执行 。,3. 条件变量 一个条件变量是和进程需要等待的某种原因（或说条件）相联系的，当定义一个条件变量时，系统就建立一个相应的等待队列。 条件变量的定义格式为：var x,y:condition ； 对条件变量只能执行wait和signal两种操作。,3. 条件变量 关于条件变量的两个操作： wait操作：如x.wait，表示因条件X无法满足，而将调用进程阻塞。此时，调用进程被挂到与条件变量

14、x相应的等待队列上，而管程则可被其他进程使用。 signal操作：如x.signal，用来唤醒与条件变量x相应的等待队列上的一个进程。值得注意的是，若没有等待进程，则x.signal不起任何作用。,管程结构示意图： 进程等待队列 局部数据定义 条件C1队列 条件变量 初始化语句 C1.wait 过程1 过程2 条件Cn队列 过程 n Cn.wait,入管程,出管程,C1.signal,Cn.signal,管程,管程等待区,4. 利用管程解决生产者-消费者问题（P60) 管程定义 type p_c=monitor Var in, out, count: integer; buffer: array 0,n-1 of itemtype; notfull,notempty:condition; procedure entry put(nextp:itemtype) procedure entry get(nextc:itemtype) if count=n then notfull.wait; if count=0 then notempty.wait; bufferin:=nextp; nextc:=bufferout; in:=(in+1)mod n; out:=(out+1)mod n; count:=count+1;