经典P、V 操作问题详解 lionxcat@gmail.cn 一、基本概念 1. 信号量 struct semaphore { int value; // 仅且必须附初值一次，初值非负 PCBtype* wait_queue; // 在此信号量上阻塞的进程队列 } S; // 信号量实例为 S 2. P、V 操作 P(S){ S := S-1; if (S<0) 调用进程自己阻塞自己，等待在 S 的等待队列末尾; } V(S){ S := S+1; if (S≤0) 从 S 等待队列头释放一进程就绪在就绪队列尾; 调用进程继续执行; } 3. 使用方法 (i). P、V 操作成队出现，处理互斥时出现在同一进程中；处理同步时出现在不同进程中。 (ii). 同步 P 先于互斥 P 调用，V 的顺序无关。 4. 另类 P、V 操作导致的问题(或信号量的栈实现方法或漏斗法) [习题 P174-23] 某系统如此定义 P、V 操作： P(S): S = S-1; 若 S＜0，本进程进入 S 信号量等待队列的末尾；否则，继续执行。 V(S): S＝S+1; 若 S≤0，释放等待队列中末尾的进程，否则继续运行。 (1)上面定义的 P、V 操作是否合理？有什么问题？ (2)现有四个进程 P1、P2、P3、P4 竞争使用某一个互斥资源（每个进程可能反复使用多次），试用上面定义的 P、V 操作正确解决 P1、P2、P3、P4 对该互斥资源的使用问题。 答： (1)不合理：先进后出；可能“无限等待”，即等待队列头的进程得不到释放。 (2)思路：令每个信号量上的等待队列中始终只有一个进程。解决方案如下：(n 个进程) n 个进程至多有 n-1 个等待。设置 n-1 个信号量，每个进程阻塞在不同的信号量上，使每个等待队列至多有一个进程等待。用循环模拟队列。 Semaphore S[n-1]; // S[i]的初值为 i+1 Procedure_i() { int j; DO_PRE_JOB(); for(j=n -2; j>=0; j--) P(S[j]); DO_JOB_IN_CRITICAL_SECTION(); for(j=0;j<=n -2;j++) V(S[j]); …… } 二、经典进程同步问题 总述：进程同步问题主要分为以下几类：一（生产者－消费者问题）；二（读者写者问题）；三（哲学家就餐问题）；四（爱睡觉的理发师问题）；五（音乐爱好者问题）；六（船闸问题）；七（红黑客问题）等。其中前两类都是用于处理进程之间通信的问题：生产者－消费者问题主要实现进程的消息机制，而读者－写者问题用于实现管道通信。哲学家就餐问题是经典的互斥转同步防止死锁的多资源争夺。理发师问题适合 I/O 或外部设备的管理，如打印调度。红黑客问题是解决不同条件触发事件的...
