信号量及其操作

1、1主要内容：主要内容：一、同步与同步机制二、信号量与PV操作三、信号量实现互斥四、信号量解决五个哲学家吃通心面问题五、信号量解决生产者-消费者问题六、记录型信号量解决读者-写者问题七、记录型信号量解决理发师问题八、Linux生产者-消费者实现3.3信号量与PV操作 2一、同步与同步机制 (1) 著名的生产者-消费者问题是计算机操作系统中并发进程内在关系的一种抽象，是典型的进程同步问题。在操作系统中，生产者进程可以是计算进程、发送进程；而消费者进程可以是打印进程、接收进程等等。解决好生产者-消费者问题就解决好了一类并发进程的同步问题。 生产者-消费者问题表述：有一环形缓冲池，包含n个缓冲区（0n

2、-1）。有两类进程：m个生产者进程和n个消费者进程，生产者进程向空的缓冲区中放产品，消费者进程从满的缓冲区中取走产品。 生产者进程和消费者进程共享下面的变量（为了便于分析问题，我们取n=3）： 3一、同步与同步机制 (2) int k;typedef anyitem item; /item类型item bufferk;int in=0,out=0,counter=0;4一、同步与同步机制 (3) process producer(void) while (true) /无限循环produce an item in nextp;/生产一个产品if (counter=k) /缓冲满时，生产者睡眠

3、sleep(producer);bufferin=nextp; /将一个产品放入缓冲区in=(in+1)%k; /指针推进counter+; /缓冲内产品数加1if(counter=1) /缓冲为空，加进一件产品 wakeup(consumer); /并唤醒消费者 5一、同步与同步机制 (4) process consumer(void) while (true) /无限循环if (counter=0) /缓冲区空，消费者睡眠 sleep(consumer);nextc=bufferout;/取一个产品到nextcout=(out+1)%k; /指针推进counter-; /取走一个产品，计数

4、减1if(counter=k-1) /缓冲满了，取走一件产品并唤 wakeup(producer); /醒生产者consume the item in nextc;/消耗产品 6一、同步与同步机制 (5) 需要注意：生产者进程和消费者进程分别有多个，生产者进程与生产者进程之间、消费者进程与消费者进程之间、生产者进程与消费者进程之间均存在资源竞争，如果它们顺序执行，则结果是正确的，但在并发执行时就会出现差错。例如，多个生产者进程可能向同一个缓冲区中投入产品；多个消费者进程可能从同一个缓冲区中取走产品；还会出现生产者进程无法正常唤醒消费者进程的情况，导致缓冲区满，所有进程睡眠。7一、同步与同步机制

5、 (6) 出现错误结果的原因在于各个进程访问缓冲区的速率不同，要得到正确结果，需要调整并发进程的速度，这需要通过在进程间交换信号或消息来调整相互速率，达到进程协调运行的目的。这种协调过程称为进程同步。 操作系统实现进程同步的机制称为同步机制，它通常由同步原语组成。常用的同步机制有：信号量与PV操作管程消息传递 8二、信号量与PV操作 (1) 1.前节种种方法解决临界区调度问题的缺点 1)对不能进入临界区的进程，采用忙式等待测试法，浪费CPU时间。2)将测试能否进入临界区的责任推给各个竞争的进程会削弱系统的可靠性，加重了用户编程负担。 9二、信号量与PV操作 (2) 2.信号量同步机制的提出 1

6、965年荷兰计算机科学家E.W.Dijkstra提出了新的同步工具-信号量和P、V操作。他将交通管制中多种颜色的信号灯管理交通的方法引入操作系统，让两个或多个进程通过特殊变量展开交互。一个进程在某一特殊点上被迫停止执行直到接收到一个对应的特殊变量值，这种特殊变量就是信号量(Semaphore)。进程可以使用P、V两个特殊操作来发送和接收信号。 10二、信号量及其操作 (3)操作系统中，信号量是用来表示物理资源的实体,信号量是一种软资源。它是一个与队列有关的整型变量。实现时，信号量是一种记录型数据结构，有两个分量：一个是信号量的值，另一个是信号量队列的队列指针。除赋初值外，信号量仅能由同步原语对

7、其进行操作，没有任何其他方法可以检查和操作信号量。信号量的值(-2) 信号量队列指针11二、信号量及其操作 (4)原语是操作系统内核中执行时不可中断的过程，即原子操作。Dijkstra发明了两个信号量操作原语：P操作原语和V操作原语（荷兰语中“测试（Proberen）”和“增量（Verhogen）”的头字母）。常用的其他符号有：wait和signal；up和down；sleep和wakeup等。利用信号量和P、V操作既可以解决并发进程的竞争互斥问题，又可以解决并发进程的协作同步问题。 12二、信号量及其操作 (5)3.信号量的分类 信号量按其用途分为2种： (1)公用信号量：初值常常为1，用来

8、实现进程间的互斥。相关进程均可对其执行P、V操作。 (2)私有信号量：初值常常为可用资源数，多用来实现进程同步。拥有该信号量的一类进程可以对其执行P操作，而另一类进程可以对其执行V操作。 13二、信号量及其操作 (6)信号量按其取值分为2种： (1)二元信号量：仅允许取值为0或1，主要用于解决进程互斥问题； (2)一般信号量：初值常常为可用资源数，可以大于1多用来实现进程同步。14二、信号量及其操作 (7)4.一般信号量设s为一个记录型数据结构,一个分量为整型量value,另一个为信号量队列queue, P和V操作原语定义： P(s)；将信号量s减去l，若结果小于0，则调用P(s)的进程被置成

9、等待信号量s的状态。 V(s)：将信号量s加1，若结果不大于0，则释放一个等待信号量s的进程。15二、信号量及其操作 (8)typedef struct semaphore int value; /信号量值struct pcb *list; /信号量队列指针 semaphore; void P(semaphore &s) s.value-; if(s.value0) W(s.list); /将P操作调用者进程置为阻塞状态并移入s信号量队列，转进程调度 void V(semaphore &s) s.value+; if(s.value=0) R(s.list); /从信号量s队列

10、中释放一个等待信号量s的进程并转换成就绪态，自己则继续执行 16二、信号量及其操作 (9)P(s)和V(s)中的s为两个过程的共享变量。s的取值：信号量s的初值在初始化时，根据其用途进行设置。通常，P操作意味着请求一个资源，V操作意味着释放一个资源。 W(s.list)和R(s.list) 是操作系统的基本系统调用。进程A调用W(s.list)将转为等待s的状态，移入s信号量队列，同时释放CPU，转向进程调度。进程A调用R(s.list) ，将释放一个等待信号量s的进程B，将B从s信号量队列中移出，B转为就绪态并移入就绪队列。A继续执行或转向进程调度。17二、信号量及其操作 (10)进程从信号

11、量队列中移出的次序应遵循的公平策略是FCFS算法。18二、信号量及其操作 (11)推论1：若信号量s为正值，则该值等于s所代表的实际还可以使用的物理资源数推论2：若信号量s为负值，则其绝对值等于登记排列在该信号量s队列之中等待的进程个数推论3：通常，P操作意味着请求一个资源，V操作意味着释放一个资源。在一定条件下，P操作代表挂起进程操作，而V操作代表唤醒被挂起进程的操作19二、信号量及其操作 (12)5、二元信号量设s为一个记录型数据结构,一个分量为value,它仅能取值0和1,另一个分量为信号量队列queue, 把二元信号量上的P、V操作记为BP和BV,BP和BV操作原语的定义如下：20二、

12、信号量及其操作 (13)typedef struct binary_semaphore int value; /value取值0 or 1 struct pcb *list; ;void BP(binary_semaphore &s) if(s.value=1) s.value=0;else W(s.list);void BV(binary_semaphore &s) if(s.list is empty( ) s.value=1;else R(s.list);21三、信号量的应用 (1) 1.利用信号量实现互斥 (1)方法：为临界资源设一互斥信号量mutex，初值为1，将临界

13、区置于P(mutex)和V(mutex)之间，P(mutex)和V(mutex)一定成对出现在同一个进程中。P、V操作只对信号量测试一次，而TS指令必须反复测试。 (2)应用模式 22三、信号量的应用 (2)semaphore mutex; mutex=1; cobegin process Pi( ) /i=1,n P(mutex); 临界区; V(mutex); coend23三、信号量的应用 (3)(3)一个并发实例 决不会有两个或多个进程同时处于临界区中。全局共享变量：mutex.value=1，0,-1,0,1mutex.list= P2, 空P1P2P(mutex);/ mutex.

14、value=0,成功,mutex.list=空临界区;/切换P(mutex); /mutex.value=-1,mutex.list=P2,阻塞,切换V(mutex);/ mutex.value=0,唤醒P2, mutex.list=空临界区;V(mutex); /mutex.value=1,mutex.list=空24三、信号量的应用 (4)2、利用信号量实现进程同步我们将分析这样几个经典进程的同步问题：（1）哲学家进餐问题（2）生产者-消费者问题（3）读者-写者问题（4）理发师问题25三、信号量的应用 (5)（1）哲学家进餐问题问题描述：有五个哲学家围坐在一圆桌旁，桌中央有一盘通心面，每人

15、面前有一只空盘子，每两人之间放一把叉子。每个哲学家思考、饥饿、然后吃通心面。为了吃面，每个哲学家必须获得两把叉子，且每人只能直接从自己左边或右边去取叉子 26三、信号量的应用 (6)哲学家叉子0011223344哲学家和筷子均要逆时针编号，否则算法会与该图不一致27三、信号量的应用 (7)数据结构：每把叉子都应互斥使用，因此每把叉子都是一个临界资源，都应定义一个信号量forki(i=0,1,2,3,4)，每个信号量的初值为1。哲学家吃东西之前必须同时拿起左右两边的叉子，因此需要执行两次P操作。28三、信号量的应用 (8)semaphore fork5;for (int i=0;i5;i+)fo

16、rki=1;cobeginprocess philosopher_i( ) /i= 0,1,2,3,4while(true) think( ); P(forki); P(fork(i+1)%5);eat( ); V(forki); V(fork(i+1)%5); coend执行代码，在图中标示每步执行结果29三、信号量的应用 (9)算法分析：若每个哲学家都各自拿起他左边的一把叉子，然后再去拿他右边的叉子时，将都拿不到右边的叉子，大家又都不会放下手中的叉子，大家在相互等待别人释放叉子，系统于是进入死锁状态。 死锁问题解决方案： 1）至多允许有四位哲学家同时去拿左边的叉子，最终保证至少有一位哲学家

17、能够进餐，（至多可以有两位哲学家能够进餐）。 30三、信号量的应用 (10)方法一、semaphore fork5;semaphore four=4;/用于获得拿叉子的资格，最多4人有资格for (int i=0;i5;i+)forki=1;cobeginprocess philosopher_i( ) /i= 0,1,2,3,4while(true) think( ); P(four);/*获得拿叉子的资格，若four=0，则阻塞*/ P(forki); P(fork(i+1)%5);eat( ); V(forki); V(fork(i+1)%5); V(four); coend31三、信号

18、量的应用 (11)方法二、semaphore fork5;semaphore mutex=1;/用于互斥访问临界资源整型变量foursemaphore wait_fork=1;/用于阻塞进程int four=4;for (int i=0;i5;i+)forki=1;cobeginprocess philosopher_i( ) /i= 0,1,2,3,4while(true) think( ); P(mutex);four-;if(four0) V(mutex); /*必须先释放信号量mutex，然后等待，否则其它进程无法使用mutex进入自己的临界区*/ P(wait_fork);else

19、V(mutex);32三、信号量的应用 (12)P(forki); P(fork(i+1)%5);eat( ); V(forki); V(fork(i+1)%5); P(mutex);four+;if(four0) V(wait_fork);V(mutex); coend33三、信号量的应用 (13)011223344011223344哲学家0拿起叉子0哲学家1拿起叉子1图2图134三、信号量的应用 (14)0011223344哲学家3拿起叉子3图40011223344哲学家2拿起叉子2图335三、信号量的应用 (15)此时已经有四位哲学家拿起了叉子，所以哲学家4不能再拿叉子了，哲学家3可以拿

20、起叉子4，从而拥有两根叉子可以吃饭。0011223344哲学家3拿起叉子4图536三、信号量的应用 (16)2）规定奇数号哲学家先拿他左边的叉子，然后再去拿右边的叉子；偶数号哲学家先拿他右边的叉子，然后再去拿左边的叉子。3）仅当哲学家的左右两根叉子均可用时，才允许他拿起叉子进餐，否则一把叉子也不取。 37三、信号量的应用 (17)第二种策略semaphore fork5;for (int i=0;i5;i+)forki=1;cobeginprocess philosopher_i( ) /i= 0,2,4，偶数号哲学家操作while(true) think( ); P(forki); P(fo

21、rk(i+1)%5);eat( ); V(forki); V(fork(i+1)%5); 38三、信号量的应用 (18)process philosopher_i( ) /i= 1,3 ，奇数号哲学家操作while(true) think( ); P(fork(i+1)%5);P(forki);eat( );V(fork(i+1)%5); V(forki); coend39三、信号量的应用 (19)第三种策略：先占有空闲叉子，占有后再拿起semaphore fork5;int fork_state5;/取值1表示叉子空闲，为0表示叉子已被拿起semaphore mutex=1;/用于互斥访问整

22、型变量fork_statesemaphore wait_fork5;/用于阻塞进程int waits5;/记录等待叉子i和(i+1)%5的进程数目for (int i=0;i0) waitsi-; V(wait_forki);/*唤醒等待叉子i和(i+1)%5的进程，而不是任何等待进程*/ coend42三、信号量的应用 (22)0011223344哲学家1拿起叉子1图10011223344哲学家3拿起叉子3图243三、信号量的应用 (23)0011223344哲学家0拿不到右边叉子1图30011223344图4哲学家2拿不到右边叉子344三、信号量的应用 (24)0011223344哲学家4

23、拿起右边叉子0图50011223344图6哲学家1拿起右边叉子245三、信号量的应用 (25)00112233441哲学家3拿起右边叉子4，从而哲学家1、3可以吃饭图7001223344图8哲学家0、2、4拿不到两根叉子，不能吃饭46三、信号量的应用 (26)（2）生产者-消费者问题生产者-消费者：指存在数据供给与需求关系的两类进程。 数据结构： 1）含有n个缓冲区的公用缓冲池；2）互斥信号量mutex：实现诸进程对缓冲池的互斥使用，一次仅允许一个进程读或写公用缓冲池，初值为1。3）资源信号量empty：记录空缓冲区个数，初值为n。47三、信号量的应用 (27)4）资源信号量full：记录满缓

24、冲区个数，初值为0。操作要求：多个生产者进程之间、多个消费者进程之间、生产者进程与消费者进程之间均能正确同步。操作描述：48三、信号量的应用 (28)item Bk;semaphore empty;empty=k; /可以使用的空缓冲区数semaphore full; full=0; /缓冲区内可以使用的产品数semaphore mutex;mutex=1; /互斥信号量int in=0; /放入缓冲区指针int out=0; /取出缓冲区指针 cobeginprocess producer_i ( ) process consumer_j ( ) while(true) while(true

25、) produce( ); P(full); P(empty); P(mutex); P(mutex); take( ) from Bout; append to Bin; out=(out+1)%k; in=(in+1)%k; V(mutex); V(mutex); V(empty); V(full); consume( ); coend互斥临界区互斥临界区同步同步49三、信号量的应用 (29)一个运行实例分析：现假定有2个生产者进程P1、P2和2个消费者进程C1、C2，2个缓冲区，这样n=2，empty初值为2。全局变量: in=0,1,0out=0,1,0full.value=0,-1,

26、-2,-1,0full.list= C1,C2empty.value=2,1,0,1,2empty.list=空,mutex.value=1,0,-1,0,1,0,-1,0,1mutex.list=空,P2,C2buffer(0)= Abuffer(1)= B50三、信号量的应用 (30)P1 P2 C1 C21 . P(full);/ full.value= -1, 阻塞,full.list= C1,进程切换2 . P(full);/full.value=-2,阻塞 / full.list= C1,C2,进程切换3 . produce( );/A;4 . P(empty); / empty.

27、value= 1,empty.list=空,进程切换(时间片用完)5 . produce( );/B; 6. P(empty); / empty.value= 0,empty.list=空,进程切换(时间片用完)7 . P(mutex); / mutex.value= 0,mutex.list=空8 . B(in)=A; /in = 0,进程切换9 . P(mutex); / mutex.value=-1,阻塞,mutex.list=P210 . in =(in + 1) % 2;/in = 111 . V(mutex); / mutex.value= 0,唤醒P2, mutex.list=空

28、51三、信号量的应用 (31)12 . B(in)=B;/in = 113 . in =(in + 1) % 2;/in = 014 . V(mutex);/ mutex.value= 1,mutex.list=空15 . V(full);/full.value=-1,唤醒C1,full.list=C216 . P(mutex);/ mutex.value= 0,mutex.list=空1 7 . n e x t c = B(out)=A;/out=018 . out =(out + 1) % 2;/ out=119 . V(full);/full.value= 0,唤醒C2,full.lis

29、t=空20 . P(mutex);/mutex.value=-1,阻塞,mutex.list=C252三、信号量的应用 (32)21 . V(mutex);/mutex.value= 0,唤醒C2,mutex.list=空22 . V(empty);/ empty.value=1,empty.list=空23 . nextc=buffer(out)=B;/out=124 . out =(out+1) % 2;/out=025 . V(mutex);/mutex.value=1 /mutex.list=空26 . V(empty);/empty.value=2 /empty.list=空53三、

30、信号量的应用 (33)注意：1）在每个程序中用于互斥的P(mutex)和V(mutex)必须成对出现；如果mutex初值为1，则位于P(mutex)和V(mutex)之间的程序段是临界区；若mutex初值大于1，则位于P(mutex)和V(mutex)之间的程序段不是互斥段，即；2）对资源信号量empty和full的操作也同样必须成对出现，但它们在不同的程序中；3）在每个程序中的多个P操作顺序不能颠倒，否则容易引起死锁。 54生产者与消费者问题中存在的关系分析 生产者与生产者之间存在互斥关系 两个不同的生产者不能同时访问缓冲池相同或不同的缓冲区 消费者与消费者之间存在互斥关系 两个不同的消费者

31、不能同时访问缓冲池相同或不同的缓冲区 生产者与消费者之间存在互斥关系 生产者与消费者不能同时访问缓冲池相同或不同的缓冲区 生产者与消费者之间存在同步关系 生产者与消费者存在协作关系55三、信号量的应用 (34)（2）读者-写者问题问题描述：若干Reader进程和Writer进程共享一个数据文件，允许多个Reader进程同时读一个共享对象，但不允许一个Writer进程与其它Reader进程或Writer进程同时访问共享对象。 即：1）允许多个读者同时执行读操作2）只允许一个写者执行写操作3）任一写者在完成写操作之前不允许其它读者或写者工作4）写者执行写操作前，应让已有的写者和读者全部退出56三、

32、信号量的应用 (35)数据结构： 1）互斥信号量writeblock：用于Reader与Writer、Writer与Writer之间的互斥，初值为1 ；2）readcount：正在读的进程数目，初值为0；3）互斥信号量mutex：用于Reader与Reader 互斥访问整型量readcount ，初值为1 ； 57三、信号量的应用 (36)情况分析： 1）如果读者数目readcount为0，则可能有也可能没有写者在写；2）如果读者数目readcount不为0，则不会有写者在写，请求读的读者便可读；3）如果读者数目readcount为0，又没有写者在写，则请求写的写者才能写。 58三、信号量的应

33、用 (37)操作描述： int readcount=0;/读进程计数semaphore writeblock,mutex;writeblock=1;mutex=1;59三、信号量的应用 (38)cobeginprocess reader_i( ) process writer_j( ) P(mutex); P(writeblock); readcount+; 写文件; if(readcount=1) V(writeblock); P(writeblock); V(mutex);读文件; P(mutex); readcount-; if(readcount=0) V(writeblock); V

34、(mutex);coend60算法分析（1）r1r2w1r3w2入口出口阅览室（1）假设读者写者r1，r2，w1，r3，w2排队准备进入阅览室。61算法分析（2）r1r2w1r3w2入口出口阅览室（2）读者r1准备进入阅览室。执行如下操作：P(mutex); readcount+;if(readcount=1) P(writeblock); V(mutex);读文件;操作后r1进入阅览室阅读，各变量的值：readcount=1writeblock=0mutex=162算法分析（3）r1,r2w1r3w2入口出口阅览室（3）读者r2准备进入阅览室。执行如下操作：P(mutex); readcou

35、nt+;if(readcount=1) P(writeblock); V(mutex);读文件;操作后r2进入阅览室阅读，各变量的值：readcount=2writeblock=0mutex=163算法分析（4）r1,r2r3w2入口出口阅览室（4）写者w1准备进入阅览室。执行如下操作：P(writeblock);/w1阻塞操作后w1阻塞等待，各变量的值：readcount=2writeblock=-1(w1等待)mutex=1writeblock队列w164算法分析（5）r1,r2,r3w2入口出口阅览室（5）读者r3准备进入阅览室。执行如下操作：P(mutex); readcount+;i

36、f(readcount=1) P(writeblock); V(mutex);读文件;操作后r3进入阅览室阅读，各变量的值：readcount=3writeblock=-1(w1等待)mutex=1writeblock队列w165算法分析（6）r1,r2,r3入口出口阅览室（6）写者w2准备进入阅览室。执行如下操作：P(writeblock);/w2阻塞操作后w2阻塞等待，各变量的值：readcount=3writeblock=-1(w1等待),-2(w2等待)mutex=1writeblock队列w1w266算法分析（7）r2,r3入口出口阅览室（7）过了若干时间后，r1准备退出阅览室。执行

37、如下操作：P(mutex);readcount-;if(readcount=0) V(writeblock);/不执行V(mutex);操作后r1退出阅览室，各变量的值：readcount=2writeblock=-1(w1等待),-2(w2等待)mutex=1writeblock队列w1w2r167算法分析（8）r3入口出口阅览室（8）过了若干时间后，r2准备退出阅览室。执行如下操作：P(mutex);readcount-;if(readcount=0) V(writeblock);/不执行V(mutex);操作后r2退出阅览室，各变量的值：readcount=1writeblock=-1(

38、w1等待),-2(w2等待)mutex=1writeblock队列w1w2r1r268算法分析（9）入口出口阅览室（9）过了若干时间后，r3准备退出阅览室。执行如下操作：P(mutex);readcount-;if(readcount=0) V(writeblock);/执行V(mutex);操作后r3退出阅览室，同时唤醒w1，各变量的值：readcount=0writeblock=-1(w1等待),-2(w2等待),-1(唤醒w1)mutex=1writeblock队列w2r1r2w1r369算法分析（10）w1入口出口阅览室（10）w1恢复执行，进入阅览室。执行如下操作：写文件;操作后各变

39、量的值：readcount=0writeblock=-1(w1等待),-2(w2等待),-1(唤醒w1)mutex=1writeblock队列w2r1r2r370算法分析（11）入口出口阅览室（11）写完后，w1退出阅览室，并唤醒w2。执行如下操作：V(writeblock);操作后w1退出阅览室，同时唤醒w2，各变量的值：readcount=0writeblock=-1(w1等待),-2(w2等待),-1(唤醒w1),0(唤醒w2)mutex=1writeblock队列w2r1r2r3w171算法分析（12）w2入口出口阅览室（12）w2进入阅览室开始写文件。执行如下操作：写文件;操作后各变

40、量的值：readcount=0writeblock=-1(w1等待),-2(w2等待),-1(唤醒w1),0(唤醒w2)mutex=1writeblock队列r1r2r3w172算法分析（13）w2入口出口阅览室（13）在w2退出前，如果接下来r4和w3到来，最先执行P(writeblock);的进程将最先进入阅览室。例如若w3先到，则w3先于r4进入阅览室writeblock队列r1r2r3w173三、信号量的应用 (39)读者优先原则执行情况的实例验证1)假设读者r1、r2在读，随后写者w1到来，接着读者r3到来。预期结果：按照读者优先原则，r3可以读，w1需要等待。2)假设写者w1在写，

41、随后写者w2到来，接着读者r1到来。预期结果：按照读者优先原则，w1退出后应该允许读者r1读。先分析第一种情况的执行结果是否符合预期：74三、信号量的应用 (40)readcount=0,1,2 writeblock=1,0,-1(w1) mutex=1,0,1,0,1r1r2w1r3P(mutex);readcount+;P(writeblock); V(mutex);读文件;P(mutex);readcount+;V(mutex);读文件;P(writeblock);/等待75三、信号量的应用 (41)readcount=0,1,2,3,2,1 writeblock=1,0,-1(w1)

42、mutex=1,0,1,0,1,0,1,0,1,0,1r1r2w1r3P(mutex);readcount+;V(mutex);读文件;P(mutex);readcount-;V(mutex);P(mutex);readcount-;V(mutex);76三、信号量的应用 (42)readcount=0,1,2,3,2,1,0 writeblock=1,0,-1(w1),0(唤醒w1),1 mutex=1,0,1,0,1,0,1,0,1,0,1r1r2w1r3P(mutex);readcount-;V(writeblock);/唤醒w1V(mutex);写文件;V(writeblock);结果

43、与预期完全相符77三、信号量的应用 (43)接下来分析第二种情况的执行结果是否符合预期：即假设写者w1在写，随后写者w2到来，接着读者r1到来。预期结果：按照读者优先原则，w1退出后应该允许读者r1读。78三、信号量的应用 (44)readcount=0,1writeblock=1,0,-1(w2),-2(r1),-1(唤醒w2) mutex=1,0,-1(r2)w1w2r1r2P(writeblock);写文件;P(writeblock);/等待P(mutex);readcount+;P(writeblock);/等待P(mutex);/等待V(writeblock);/唤醒w279三、信号

44、量的应用 (45)readcount=0,1,2writeblock=1,0,-1(w2),-2(r1),-1(唤醒w2),0(唤醒r1)mutex=1,0,-1(r2),0(唤醒r2),1w1w2r1r2写文件;V(writeblock); /唤醒r1V(mutex);/唤醒r2读文件;readcount+;V(mutex);读文件;80三、信号量的应用 (46)readcount=0,1,2,1,0writeblock=1,0,-1(w2),-2(r1),-1(唤醒w2),0(唤醒r1),1mutex=1,0,-1(r2),0(唤醒r2),1,0,1,0,1w1w2r1r2P(mutex)

45、;readcount-;V(mutex);P(mutex);readcount-;V(writeblock);V(mutex);结果与预期不符，在新来读者r1之前等待的所有写者w2被允许写，写完后才允许读者r1读。81三、信号量的应用 (47)将读者优先改为写者优先(参考答案)增加writers变量记录等待写者数量，初值为0，增加信号量readblock用于阻塞读者进程；增加rwaiters变量记录写者出现后后继等待读者数量，初值为0，程序如下：int readcount=0;/在读进程计数int writers =0;/写进程计数int rwaiters =0;/后继等待读进程计数semap

46、hore writeblock, readblock, mutex;writeblock=1;readblock=0;mutex=1;82三、信号量的应用 (48)r1,r2w1w2r3r4r5入口出口阅览室写者优先重要情景分析假设有2个读者r1、r2已经到达阅览室在读，随后写者w1到来，接着读者r3、r4、r5、写者w2陆续到来。在写者优先的原则下，应该安排写者尽快写。做到这一点的措施是没有进入阅览室的后续读者r3、r4、r5需在门外等候。写者w1、w2也在门外等候。写者读者83三、信号量的应用 (48)r1,r2w1w2r3r4r5入口出口阅览室当读者r1、r2阅读完毕退出后，最后退出者(

47、设为r2)唤醒写者w1， w1写完后唤醒w2，w2写完后同时唤醒读者r3、r4、r5。写者w2可能比读者r3、r4或r5到的早，也可能到的晚，但都在读者r3、r4、r5 之前处理，体现写者优先原则。写者读者84三、信号量的应用 (48)r1,r2w1w2r3r4r5入口出口阅览室进程分为3类：在读进程、在等写进程和在等读进程。readcount记录在读进程数目，writers记录在等写进程数目，rwaiters记录在等读进程数目。写者读者在读进程数目readcount=2在等读进程数目rwaiters=3在等写进程数目writers=285三、信号量的应用 (49)cobeginprocess

48、 read_i()P(mutex);if(writers=0) readcount+;/在读进程数目增1 else rwaiters+;/后继等待读进程数目增1 V(mutex);/释放信号量 P(readblock);/等待读 P(mutex);/被唤醒后修改临界变量readcount rwaiters-;/等待者数目减1 readcount+;/在读者数目增1 V(mutex); P(mutex);/再次判定临界变量readcount值 /*如果没有写者,后续读者可进入,否则后续读者暂停进入*/if(readcount=1) P(writeblock);/*若读者已经进入，则写者需等待*/

49、86三、信号量的应用 (49)V(mutex);读文件;P(mutex);readcount-;/读者退出if(readcount=0) V(writeblock);/*若读者已完全退出，则且写者等待则写者可写*/V(mutex);87三、信号量的应用 (50)cobeginprocess writer_j()P(mutex);/*写者写前先登记写请求，即写者数目writers 增1，以便读者暂停进入。如果不断有写者登记，则读者会长时间无法读*/ writers+; V(mutex); P(writeblock);/*如果读者已经退出完毕，则写者可写，写完退出后，写者数目减1*/写文件; wr

50、iters-; while(writers=0)&(rwaiters0) rwaiters-; V(readblock);/*若无写者且有等待读者则唤醒所有等待读者*/ V(writeblock);88三、信号量的应用 (51)考虑当前有2个读者r1、r2在读，接下来来了写者w1、读者r3、写者w2、读者r4。断言：自从写者w1出现后，按照写者优先原则，应该优先安排写者w1尽快写。于是在读进程r1、r2只可退出，后继读者r3、r4不得入内。r1、r2中的最后一个退出时唤醒写者w1，最后一个写者w2一次性唤醒后继等待读者r3、r4。最后一个写者在唤醒读者的过程中，若出现新的写者，则尚未唤

51、醒的读者不再唤醒。已唤醒读者进程读完退出后，新的写者可以写。89三、信号量的应用 (52)写者退出后，等待者读进程开始进入共享文件读，这时若有写者再来，则写者需等待在读进程退出，后来读者置为新的等待读者进程。除了临界区里的程序语句不会被中断外，临界区外的任何两条语句之间都会发生中断。并发程序交叉执行的语句序列往往有很多种，在证明并发程序正确性困难的情况下常常采用分析测试的方法试图发现程序中的错误。我们分析容易发现程序错误的那种交叉执行序列，这种序列或者设计成一前一后争相执行临界区的序列，或者设计为验证某个重要断言的序列，或者违反某种常规操作次序，如唤醒先于等待，这意味着唤醒信号的丢失，等待进程

52、可能永远等待。90三、信号量的应用 (53)readcount=0,1,2 writers =0,1 writeblock=1,0,-1readblock=0 mutex=1 rwaiters=0r1r2w1r3w2r4P(mutex);readcount+;P(writeblock);V(mutex);读文件;P(mutex);readcount+;V(mutex);读文件;P(mutex);writers+;V(mutex);P(writeblock);/等待91三、信号量的应用 (54)readcount=0,1,2 writers =0,1,2 writeblock=1,0,-1(w1

53、),-2(w2)readblock=0,-1(r3) ,-2(r4) mutex=1 rwaiters=0,1,2r1 r2w1r3w2r4P(mutex);rwaiters+;V(mutex);P(readblock);/等待P(mutex);writers+;V(mutex);P(writeblock);/等待P(mutex);rwaiters+;V(mutex);P(readblock);/等待92三、信号量的应用 (55)readcount=0,1,2,1,0 writers =0,1,2,1 writeblock=1,0,-1(w1),-2(w2),-1(唤醒w1),0(唤醒w2)r

54、eadblock=0,-1(r3) ,-2(r4) mutex=1 rwaiters=0,1,2r1r2w1r3w2r4P(mutex);readcount-;V(mutex);P(mutex);readcount-;V(writeblock);/唤醒w1V(mutex);写文件;writers-;V(writeblock);/唤醒W293三、信号量的应用 (56)readcount=0,1,2,1,0,1 writers =0,1,2,1,0 writeblock=1,0,-1(w1),-2(w2),-1(唤醒w1),0(唤醒w2),1,0readblock=0,-1(r3) ,-2(r4)

55、,-1(唤醒r3),0(唤醒r4) mutex=1 rwaiters=0,1,2,1r1 r2w1r3w2r4写文件;writers-;V(readblock);/唤醒r3writers-;V(readblock);/唤醒r4V(writeblock);/空操作P(mutex);rwaiters-;readcount+;V(mutex);P(mutex);P(writeblock);V(mutex);读文件;94三、信号量的应用 (57)readcount=0,1,2,1,0,1,2,1,0 writers =0,1,2,1,0 writeblock=1,0,-1(w1),-2(w2),-1(

56、唤醒w1),0(唤醒w2),1,0,1readblock=0,-1(r3) ,-2(r4),-1(唤醒r3),0(唤醒r4) mutex=1 rwaiters=0,1,2,1,0r1 r2w1r3w2r4P(mutex);readcount-;V(writeblock);V(mutex);P(mutex);readcount-;V(mutex);95三、信号量的应用 (58)readcount=0,1,2,1,0,1,2,1 writers =0,1,2,1,0 writeblock=1,0,-1(w1),-2(w2),-1(唤醒w1),0(唤醒w2),1,0readblock=0,-1(r3

57、) ,-2(r4),-1(唤醒r3),0(唤醒r4) mutex=1 rwaiters=0,1,2,1,0r1 r2w1r3w2r4P(mutex);rwaiters-;readcount+;V(mutex);P(mutex);V(mutex);读文件;P(mutex);readcount-;V(mutex);96三、信号量的应用 (59)1968年，Dijkstra提出睡眠理发师问题：理发店理有一位理发师、一把理发椅和n把椅子供顾客等候理发休息如果没有顾客，理发师便在理发椅上睡觉一个顾客到来时，它必须叫醒理发师如果理发师正在理发时又有顾客来到，则如果有空椅子可坐，就坐下来等待，否则就离开97

58、三、信号量的应用 (61)int waiting=0;/等候理发顾客已坐的椅子数int CHAIRS=N; /为顾客准备的椅子总数semaphore customers,barbers,mutex;customers=0;barbers=0;mutex=1;/*起初，顾客数为0，没有正在理发的顾客*/98三、信号量的应用 (62)int waiting=0;/等候理发顾客坐的椅子数int CHAIRS=N; /为顾客准备的椅子数semaphore customers,barbers,mutex;customers=0;barbers=0;mutex=1;cobeginprocess barber( ) while(true) P(customers);/*有顾客可供消费吗？若无顾客，理发师睡眠*/ P(mutex); /*若有顾客时，以顾客当产品，取一个顾客消费*/ waiting-; /等候顾客数少一个 V(barbers); /理发师喊一个顾客来准备为他理发 V(mutex); /退出临界区 cut_hair(); /理发师正在理发(非临界区)临界区99三、信号量的应用 (63)process customer_i( ) P(mutex); /进入临界区 if(waitingCHAIRS) /*若有空椅子，则等候顾客数加1，否则顾客离开*