经典 P、V 操作问题详解 lionxcat@ 一、基本概念 1. 信号量 struct semaphore { int value; // 仅且必须附初值一次，初值非负 PCBtype* wait_queue; // 在此信号量上阻塞的进程队列 } S; // 信号量实例为 S 2. P、V 操作 P(S){ S := S-1; if (S=0; j--) P(S[j]); DO_JOB_IN_CRITICAL_SECTION(); for(j=0;j<=n-2;j++) V(S[j]); …… } 二、经典进程同步问题 总述：进程同步问题主要分为以下几类：一（生产者－消费者问题） ；二（读者写者问题） ；三 （哲学家就餐问题） ；四（爱睡觉的理发师问题） ；五（音乐爱好者问题） ；六（船闸问题） ；七 （红黑客问题）等其中前两类都是用于处理进程之间通信的问题：生产者－消费者问题主要 实现进程的消息机制，而读者－写者问题用于实现管道通信哲学家就餐问题是经典的互斥转 同步防止死锁的多资源争夺理发师问题适合 I/O 或外部设备的管理，如打印调度红黑客问 题是解决不同条件触发事件的思想方法。
I. 生产者—消费者问题(初始缓冲区为空) 问题：生产者生产产品放到缓冲区，消费者从缓冲区取产品消费 ① 单缓冲区[ 书 P119]( 适合单或多生产消费者) ： 同步：生产者不能往满缓冲区放产品(S1(1))；消费者不能从空缓冲区取产品(S2(0)) void Producer() { while (true){生产一个产品;P(S1); 申请一个空的缓冲区放到缓冲区;V(S2); 返回一个满的缓冲区 }} void Consumer() { while (true){P(S2); 申请一个满的缓冲区从缓冲区取一个产品;V(S1); 返回一个空的缓冲区消费产品; }} ② 环行多缓冲区（或无穷缓冲区）单生产消费者[ 习题 P173-13] ： 同步：生产者不能往满缓冲区放产品(S1(n))；消费者不能从空缓冲区取产品(S2(0))n 为缓冲区 大小 互斥：设置指示下一个空缓冲区的位置变量(i(0))和指示下一个产品在缓冲区的位置变量(j(0))， 由于只有一个生产者和消费者，i 和 j 无须互斥访问此问题无互斥关系 void Producer() { while (true){ 生产了一个产品; P(S1); 把产品放入缓冲区;i = (i+1)%n; // 无穷缓冲区无须’%n’ V(S2); }} void Consumer() { while (true){P(S2);取一个产品;j = (j+1)%n; // 无穷缓冲区无须’%n’V(S1);消费产品; }} ③ 环行多缓冲区多生产消费者[ 书 P120] ：同步：生产者不能往满缓冲区放产品(S1(n))；消费者不能从空缓冲区取产品(S2(0))。
n 为缓冲区 大小 互斥：设置指示下一个空缓冲区的位置变量(i(0))，生产者之间互斥(mutex1(1))；设置指示下一 个产品在缓冲区的位置变量(j(0))，消费者之间互斥(mutex2(1))也可以生产者和消费者 之间都互斥( 把 mutex1 和 mutex2 都换成一个 mutex(1)) void Producer() { while(true){生产一个产品;P(S1); 申请一个空的缓冲区P(mutex1); 一个生产者申请制造产 品放到缓冲区;i = (i+1)%n; 指针移动到下一空的 缓冲区V(mutex1); 释放生产者V(S2); 释放一个满的缓冲区 }} void Consumer() { while(true){P(S2); 申请一个满的缓冲区P(mutex2); 一个消费者申请消费从第 j 个缓冲区取一个产品;j = (j+1)%n; 指向下一个满的缓冲 区V(mutex2); 释放消费者V(S1); 释放一个空的缓冲区消费产品; }} ④ 用进程通信( 信箱通信) 的方法解决上述问题[ 习题 P175-27]: void Producer() { msgbuff mb; //message buffer while (1){ generate sth. to send; receive(consumer, // 取一空缓冲区 create_message( // 放产品到缓 冲区 send(consumer, // 生产好的产品发 给消费者 }} // send 和 receive 原语见信箱通信问题 void Consumer() { msgbuff mb; // empty message for(int i=0 ; i
同步：发送进程发送消息数量不限，无消息时接收进程不能取信息，故设置当前消息数量(m- syn(0)) 互斥：发送和接收进程互斥访问消息队列首指针 m-q，故设置互斥信号量(m-mutex(1))空缓冲区个数为(s-b(n))，设置互斥访问信号量(b-mutex(1)) send(R,M) // 把消息 M 发给 R { 找到接收进程 R ，否则错误返回; 申请缓冲区 P(s-b); P(b-mutex);取一空缓冲区; V(b-mutex); 把信息 M 复制到空缓冲区; receive(A) // 把消息存到地址 A { P(m-syn); P(m-mutex);取一消息复制到 A; V(m-mutex); P(b-mutex);释放消息缓冲区;P(m-mutex);把缓冲区挂到 m-q 上; V(m-mutex); V(m-syn); } V(b-mutex); } ⑥ 进程信箱通信[ 书 P130 ，06 年秋讲义] ： 问题：发送进程把信息发到信箱中，接收进程随时取信 同步：发送进程不能向满信箱中发信(full(0)) ；接收进程不能从空信箱中取信(empty(1)) 。
send(N,M) // 把信件 M 发到信箱 N 中 { 查找信箱 N; P(full);把 M 送入信箱 N; V(empty); } receive(N,X) // 从信箱 N 中取一封信放到 X { 查找信箱 N; P(empty);从信箱 N 中取一封信放到 X; V(full); } ⑦ 进程通信多发送接收者问题[ 习题 P174-16] ： 问题：n1 个进程通过 m 个缓冲区向 n2 个进程发送消息，每个消息所有接收进程都接收一次 同步：发送者不能向满缓冲区发信息(mutex_send[m](1)) ； 接收者不能从空缓冲区接收信息(mutex_receive[m](0)) 互斥：设置指示下一个空缓冲区变量(cur(0))，发送进程互斥访问(mutex_cur(1))；设置 buffer_count[m](0)记录某个缓冲区被读过几次，若某个缓冲区被读过 n2 次，则可 以释放，接收者互斥访问 buffer_count(mutex_count[m](1)) 阻塞分析：若接收者试图接收空缓冲区被阻塞在 mutex_receive[k] 上，则其他要访问同一缓冲区 的接收者被堵塞在 mutex_count[k]上；若此时发送者向缓冲区 k 写入信息，则由第一个 接收者释放其他接收者。
若有一发送者被阻塞在 mutex_send[cur]上，则其他发送者被阻塞在 mutex_cur 上 void send() { while (true){ P(mutex_cur); cur = (cur+1)% m; // 若阻塞则表示 cur 满 P(mutex_send[cur]); 写入 buffer[cur];// cur 内容等待被读取 V(mutex_receive[cur]); V(mutex_cur); } } void receive() { While (true){ for (int i=0; i
而后者如果没有东西消费，就会阻塞等待 第一类( 读者优先)[ 书 P121] ： 问题：写者在写，则其余写者和读者等待； 有读者在读，则其他读者可读，直到没有读者写者才能写 互斥：写者之间互斥以及所有读者和写者之间互斥(write(0/1))；读者之间不互斥； readcount 记录当前读者个数(readcount(0)) ，多个读者对 readcount 互斥访问，访问后加 上 1(mutex(1)); readcount 是一个可被多个读者进程访问的临界资源，所以需要设置一个 互斥信号 mutex 阻塞分析：当有读者在读时，所有写者堵塞在 write 上；有写者在写时，第一个读者阻塞在 write 上，其余的阻塞在 mutex 上，所有写者阻塞在 write 上 void Reader() { P(mutex); 一开始，读者申请一个位置去看书 readcount++;然后逐渐有更多的读者读书，自动加 上 1 if (readcount==1) // 第一个读者，可能有写者在写P(write); 为写者申请一个空间写东西 V(mutex); 读者要释放空间或缓冲区了 P(mutex); 为读者申请能读书的资源 readcount--;读者读不到足够的书 读者逐渐减少 if (readcount==0) // 没有读者了，释放写者V(write); V(mutex); 释放读者，让作者写书 } void Writer() { P(write);写; V(write);// 释放的可能是读者或写者 } /*相对读者优先，即写者可以释放写 者；也可改为绝对读者优先，即只要 有读者在，写者写完优先释放读者。
方法类似于写者优先/ 第二类( 写者优先)[ 习题 P175-24] ： 问题：写者在写，则其余写者和读者等待；写者写完，优先释放下一个写者； 读者在读，若无写者等待，则其他读者可读；读者在读，若有写者等待，则其他读者等 待 互斥：写者之间互斥(write(1))，读者和写者之间互斥(read(1))；读者之间不互斥； 记录当前读者个数(readcount(0)) 和写者个数(writecount(0))，读者对 readcount 互斥访问 (mutex1(1))，写者对 writecount 互斥访问(mutex2(1)) ； 为保证在有读者等待的时候，新写者到来也优先释放写者，让等待的读者继续等待，不 能将读者和写者阻塞在同一队列上(mutex3(1)) 阻塞分析：当。