信号量与PV操作

1、主要内容： 同步与同步机制 信号量及其操作 信号量的应用 哲学家进餐问题 生产者-消费者问题 读者-写者问题 理发师问题,3.3 信号量与PV操作,3.1.1 同步与同步机制,著名的生产者-消费者问题是计算机操作系统中并发进程内在关系的一种抽象，是典型的进程同步问题。 在操作系统中，生产者进程可以是计算进程、发送进程；而消费者进程可以是打印进程、接收进程等等。解决好生产者-消费者问题就解决好了一类并发进程的同步问题。 生产者-消费者问题表述：有n个生产者和m个消费者，连接在k个单位缓冲区的有界环形缓冲池上，故又叫有界缓冲问题。其中pi和cj都是并发进程，只要缓冲区未满，生产者进程pi所生产的产

2、品就可以放入缓冲区；只要缓冲区非空，消费者进程cj就可以从缓冲区取走并消耗产品。,.,.,int k; typedef anyitem item; /item类型 nextp, nextc: item; item bufferk; int in=0, out=0, counter=0;,process producer(void) while(TRUE) produce an item in nextp; if(counter=k) sleep(producer); bufferin=nextp; in=(in+1) % k; counter+; if(counter=1) wakeup(co

3、nsumer); ,process consumer(void) while(TRUE) if(counter=0) sleep(consumer); nextc=bufferout; out=(out+1) % k; counter-; if(counter=k-1) wakeup(producer); consume the item in nextc; ,生产者和消费者单独运行都是正确的，但是，如果并发执行（交替执行）就会产生错误： 结果不唯一 永远等待 出现错误结果的原因在于各个进程访问缓冲区的速率不同，要得到正确结果，需要调整并发进程的速度，这需要通过在进程间交换信号或消息来调整相互

4、速率，达到进程协调运行的目的。这种协调过程称为进程同步。 操作系统实现进程同步的机制称为同步机制，它通常由同步原语组成。常用的同步机制有：信号量与PV操作、管程和消息传递。,3.3.2 信号量与PV操作,1.前节种种方法解决临界区调度问题的缺点 1)对不能进入临界区的进程，采用忙式等待测试法，浪费CPU时间。 2)将测试能否进入临界区的责任推给各个竞争的进程会削弱系统的可靠性，加重了用户编程负担。 3）这些方案只能解决进程竞争，不能解决进程协作问题。 2.信号量同步机制的提出 1965年荷兰计算机科学家E.W.Dijkstra提出了新的同步工具-信号量和P、V操作。他将交通管制中多种颜色的信号

5、灯管理交通的方法引入操作系统，让两个或多个进程通过特殊变量展开交互。一个进程在某一特殊点上被迫停止执行直到接收到一个对应的特殊变量值，这种特殊变量就是信号量(Semaphore)。,进程可以使用P、V两个特殊操作来发送和接收信号，如果协作进程的相应信号仍未送到，则进程被挂起直到信号送达为止。（注意：这里的“挂起”并不是第二章里的被对换到硬盘上，而是转入等待状态！） 操作系统中，信号量是用来表示物理资源的实体，用一个结构性变量表示，有两个分量：一个是信号量的值，另一个是指向信号量的队列的指针。 除赋初值外，信号量仅能由同步原语P和V对其进行操作，没有任何其他方法可以检查和操作信号量。 原语是操作

6、系统内核中执行时不可中断的过程，即原子操作。Dijkstra发明了两个信号量操作原语：P操作原语和V操作原语（荷兰语中“测试（Proberen）”和“增量（Verhogen）”的头字母）。常用的其他符号有：wait和signal；up和down；sleep和wakeup等。 利用信号量和P、V操作既可以解决并发进程的竞争问题，又可以解决并发进程的协作问题。,信号量的分类 信号量按其用途分为2种： 公用信号量：初值常常为1，用来实现进程间的互斥。相关进程均可对其执行P、V操作。 私有信号量：初值常常为可用资源数，多用来实现进程同步。拥有该信号量的一类进程可以对其执行P操作，而另一类进程可以对其执

7、行V操作，多用于并发进程的同步。 信号量按照取值可以分为两种： 二元信号量： 仅允许取0和1，主要用于解决进程互斥； 一般信号量（计数信号量）：允许取任意整数值，主要用于解决进程同步问题。,一般信号量 数据类型：s是结构性变量，其中成员value为整型变量，系统初始化时为其赋初值；成员list为等待使用此类资源的进程队列的头指针。 P(s): 将s的成员value的值减一； 若结果小于0，则执行P操作的进程被阻塞，并且进入s的成员list指向的队列；否则，执行P操作的进程继续执行。 (2) V(s): 将s的成员value的值加一； 如果结果小于等于0，则执行V操作的进程从s的成员list指向

8、的队列中唤醒一个进程（使其转变为就绪态），随后自己继续执行；如果结果大于0，则执行V操作的进程继续执行。,结构型信号量和PV操作的实现： typdef struct semaphore int value; struct pcb *list; ; void P(semaphore ,其中 W(s.list)和R(s.list)是操作系统的基本系统调用， W(s.list)表示把调用它的进程置成等待信号量s状态，并移入s信号量队列，同时释放CPU，转向进程调度； R(s.list)表示释放一个等待s信号量的进程，转换成就绪态并且移入就绪队列，执行该操作的进程继续执行（时间片未到期）或者转向进程调

9、度（时间片已到期）。 进程从队列中移出时的次序按照FCFS算法，被阻塞的时间越长的进程越优先出队，一避免饥饿现象。,结构型信号量与PV操作的关系,推论1：若信号量s.value为正值，则该值等于在封锁进程之前对信号量s可施行的P操作数、亦等于s所代表的实际还可以使用的物理资源数 推论2：若信号量s.value为负值，则其绝对值等于登记排列在该信号量s队列之中等待的进程个数、亦即恰好等于对信号量s实施P操作而被封锁起来并进入信号量s队列的进程数 推论3：通常，P操作意味着请求一个资源，V操作意味着释放一个资源。在一定条件下，P操作代表挂起进程操作，而V操作代表唤醒被挂起进程的操作,记录型信号量与

10、PV操作的注意事项,P 操作 信号量的值减一 如果满足if条件，执行了P操作的进程会挂起，P操作语句之后的语句都不会再执行。 被挂起的进程，除非另一个进程调用V()来唤醒它，否则永远不会执行。 V 操作 信号量的值加一 如果满足if条件，执行V操作的进程会去唤醒另一个正在等待的进程（被挂起的进程）。 执行V操作的进程不会自愿停止， V操作后面的语句会接着执行 被唤醒的进程只是进入了就绪队列，并不一定有机会马上被执行 被唤醒的进程，从挂起点接着执行，也就是P操作之后的语句,2 二元信号量,设s为一个结构型数据结构,其中一个为value,它仅能取值0和1,另一个分量为信号量队列头指针list ty

11、pedef struct binary_semaphore int value; struct pcb *list; ; void BP(binary_semaphore 可以证明，二元信号量与其他结构信号量具有一样的表达能力。,3.3.3 信号量实现进程互斥,semaphore mutex; mutex= 1; cobegin process Pi() /i=1,2,n . P(mutex); 临界区； V(mutex); . coend;,信号量解决机票问题,哲学家吃通心面问题,有五个哲学家围坐在一圆桌旁，桌中央有一盘通心面，每人面前有一只空盘于，每两人之间放一把叉子。每个哲学家思考、饥饿

12、、然后吃通心面。为了吃面，每个哲学家必须获得两把叉子，且每人只能直接从自己左边或右边去取叉子,哲学家吃通心面问题示意图,4,0,0,1,4,3,1,2,3,2,哲学家,叉子,哲学家吃通心面问题,semaphore fork5; for(int i;i5;i+) forki := 1; cobegin process Philosopher_i() / i=0,1,2,3,4, while(true) think()； P(forki)； P(forki+1%5)； eat()； V(forki)； V(fork(i+1)%5)； coend,上述算法能够实现进程的互斥（同步），但是，它可能发生

13、死锁：如果每一个哲学家依次拿起右边（或者左边）的叉子，结果就会出现每一个人都拿到一把叉子，而都等待第二把叉子的现象。 解决死锁问题的方案： 至多允许4位哲学家吃面； 奇数号哲学家先拿左边的叉子，偶数号哲学家先拿右边的叉子； 规定每一个哲学家都必须拿到两把叉子才能吃面，否则一把也不拿即当拿不到第二把叉子时，即放弃已拿到的第一把。注意：实现该方案需要修改信号量和PV操作的定义！,生产者消费者问题,生产者和消费者共享缓冲区 缓冲区中有空时，生产者可放入产品（不许放重），否则等待 缓冲区中有产品时，消费者可取出产品（不许取重），否则等待 一个生产者、一个消费者共享一个缓冲区 一个生产者、一个消费者共享

14、多个缓冲区 多个生产者、多个消费者共享多个缓冲区 多个生产者、多个消费者共享一个缓冲区 多个生产者、一个消费者共享多个缓冲区 一个生产者、多个消费者共享多个缓冲区,一个生产者一个消费者共享一个缓冲区,int B; semaphfore empty; /可以使用的空缓冲区数目 semaphore full; /缓冲区内可以使用的产品的数目 empty=1; /初始缓冲区内允许放入一件产品 full=0; /初始缓冲区内没有产品,cobegin process producer() while(true) produce(); P(empty); append() to B; V(full); c

15、oend,process consumer() while(true) P(full); take() from B; V(empty); ,过程分析,情况一： Producer: P(empty); empty=0; (进入临界区) Consumer: P(full); full=-1; (挂起) Producer: V(full); full=0; (唤醒consumer) Consumer: 临界区语句； (进入临界区),过程分析,情况二： Consumer: P(full); full=-1; (挂起) Producer: P(empty); empty=0; 临界区; V(full)

16、; full=0;(唤醒消费者) Consumer: 临界区语句； V(empty) ; empty= 1; Producer: .,一个生产者一个消费者共享多个缓冲区,前面的例子里生产者和消费者共享的是一个缓冲区，实际上，他们也可以共享多个缓冲区。 为了实现协调，必须增加一个信号量。 mutex信号量（初值1），使进程互斥地访问缓冲区 empty信号量（初值k），保证生产者不向满的缓冲区存 full信号量（初值0），保证消费者不从空的缓冲区取,m个消费者和n个生产者共享多个缓冲区,int Bk; semaphore empty; empty=k; semaphore full; full=0

17、; semaphore mutex; mutex=1; int in=0; int out=0;,cobegin process producer_i() while(true) produce(); P(empty); P(mutex); append() to Bin; in :=(in+1) % k; V(mutex); V(full); coend;,process consumer_j () while(true) P(full); P(mutex); take() from Bout; out=(in+1) % k; V(mutex); V(empty); consume(); ,

18、实例分析,情况一 (producer在临界区中， consumer加入) producer_i: P(empty);(empty=k-1) P(mutex);(mutex=0) 临界区 consumer_i: P(full); (full=-1;) 挂起 producer_i: V(mutex);(mutex=1) V(full); (full=0;)(唤醒consomer_i) comsumer_i: P(mutex); (mutex=0;) 临界区； V(mutex);(mutex=1;) V(empty); (empty=k),实例分析,情况二： (consumer先启动) consum

19、er_i: P(full); (full=-1;) 挂起 producer_i: P(empty);(empty=k-1;) P(mutex);(mutex=0) 临界区； V(mutex);(mutex=1) V(full);(full=0;) comsumer_i: P(mutex); (mutex=0;) 临界区； V(mutex);(mutex=1;) V(empty); (empty=k),P操作的次序,如果有多个P操作，必须注意它们之间的顺序 一般来说，用于互斥的信号量上的P操作应该在后面。 V操作的次序无关紧要。 讨论：如果在生产者进程中将P(mutex)和P(empty)交换则

20、 若缓冲区已满 （empty=0;full=k;mutex=1;）,则 producer: P(mutex);(mutex=0) P(empty);(empty=-1;) 挂起 consumer: P(full);(full=k-1); P(mutex);(mutex=-1); 挂起,读者写者问题,有两组并发进程：读者和写者，共享一个文件F，要求： 允许多个读者同时执行读操作 任一写者在完成写操作之前不允许其它读者或写者工作 写者执行写操作前，应让已有的写者和读者全部退出,单纯使用信号量不能解决问题，需要引入计数器readcount对读进程计数，mutex代表对计数器操作的互斥信号量，writ

21、elock表示是否允许写的信号量。 int readcount=0; semaphore writeblock, mutex; writeblock=1; mutex=1;,cobegin process reader_i() P(mutex); readcount+; if(readcount=1) P(writeblock); V(mutex); 读文件； P(mutex); readcount-; if(readcount=0) V(writeblock) ; V(mutex); ,process writer_j() P(writeblock); 写文件； V(writeblock);

22、 coend,本算法中，读者是优先的，当存在读者时，写者将被延迟，而且只要有一个读者活跃，随后的读者都被允许访问文件，从而导致写者长时间等待，并可能出现写者饥饿的现象。 解决的方案：增加信号量修改程序，可以得到写者具有优先权的方案，确保当一个写者进程想要访问文件时，不允许新的读者进程访问。 读者写者锁： 允许多名读者同时以只读方式存取有锁保护的对象；或者一位写者以写方式存取有锁保护的对象 。 当一名或多名读者已经上锁后，此时形成读锁，写者将不能访问有读锁保护的对象；当锁被请求者用于写操作时，形成写锁，其他进程的读写操作必须等待。,写者优先的算法（增加一个信号量s，用于在写进程到来之后封锁后来的

23、读进程）,cobegin process reader_i() P(s); P(mutex); readcount+; if(readcount=1) P(writeblock); V(mutex); V(s); 读文件； P(mutex);,readcount-; if(readcount=0) V(writeblock) ; V(mutex); process writer_j() P(s); P(writeblock); 写文件； V(writeblock); V(s); coend,读者写者锁： 允许多名读者同时以只读方式存取有锁保护的对象；或者一位写者以写方式存取有锁保护的对象 。

24、当一名或多名读者已经上锁后，此时形成读锁，写者将不能访问有读锁保护的对象；当锁被请求者用于写操作时，形成写锁，其他进程的读写操作必须等待。,理发师问题,理发店有一位理发师、一把理发椅和n把供等候理发的顾客坐的椅子 如果没有顾客，理发师便在理发椅上睡觉 当一个顾客到来时，它必须叫醒理发师 如果理发师正在理发时又有顾客来到，则如果有空椅子可坐，他们就坐下来等待，否则就离开,int waiting0； /等候理发的顾客数 int CHAIRS=n; /为顾客准备的椅子数 semaphore customers, barbers，mutex; customers = 0; barbers= 0; mutex := 1; cobegin process barber() while(true) P(cutomers);