[科普中国]-PV操作

PV操作是一种实现进程互斥与同步的有效方法。PV操作与信号量的处理相关，P表示通过的意思，V表示释放的意思。

PV操作是典型的同步机制之一。用一个信号量与一个消息联系起来，当信号量的值为0时，表示期望的消息尚未产生；当信号量的值非0时，表示期望的消息已经存在。用PV操作实现进程同步时，调用P操作测试消息是否到达，调用V操作发送消息。

简介1962年，狄克斯特拉离开数学中心进入位于荷兰南部的艾恩德霍芬技术大学(Eindhoven Technical University）任数学教授。在这里，他参加了X86计算机的开发，设计与实现了具有多道程序运行能力的操作系统——THE Multiprogramming System。

THE 是艾恩德霍芬技术大学的荷兰文Tchnische Hoogeschool Eindhov –en的词头缩写。狄克斯特拉在THE这个系统中所提出的一系统方法和技术奠定了计算机现代操作系统的基础，尤其是关于多层体系结构，顺序进程之间的同步和互斥机制这样一些重要的思想和概念都是狄克斯特拉在THE中首先提出并为以后的操作系统如UNIX等所采用的。

为了在单处理机的情况下确定进程(process）能否占有处理机，狄克斯特拉将每个进程分为“就绪”(ready)、“运行”(running)和“阻塞”(blocking)三个工作状态。由于在任一时刻最多只有一个进程可以使用处理机，正占用着处理机的进程称为“运行”进程。当某进程已具备了使用处理机的条件，而当前又没有处理机供其使用，则使该进程处于“就绪”状态。当运行进程由于某种原因无法继续运行下去时，就停止其占用处理机，使之进入“阻塞”状态，待造成其退出运行的条件解除，再进入“就绪”状态。而对系统中所有同时运行的进程之间所存在的相互制约的同步(synchronization，指为了避免错误，在一个进程访问共享数据时，另一个进程不访问该数据)和互斥(mutually-exclusive，指两个进程不能同时在一个临界区中使用同一个可重复使用的资源，诸如读写缓冲区)两个关系，狄克斯特拉巧妙地利用火车运行控制系统中的“信号灯”(semaphore，或叫“信号量”)概念加以解决。

中国读者常常不明白这一同步机制为什么叫PV操作，原来这是狄克斯特拉用荷兰文定义的，因为在荷兰文中，通过叫passeren，释放叫vrijgeven，PV操作因此得名。这是在计算机术语中不是用英语表达的极少数的例子之一。

信号量信号量的概念和PV操作是荷兰科学家E.W.Dijkstra提出来的。信号是铁路交通管理中的一种常用设备，交通管理人员利用信号颜色的变化来实现交通管理。在操作系统中，信号量S是一整数。S大于或等于零，代表可供并发进程使用的资源实体数；在S小于零时，ISl表示正在等待使用资源实体的进程数。建立一个信号量必须说明此信号量所代表的意义并且赋初值。除赋初值外，信号量仅能通过PV操作来访问。1

信号量按其用途可分为两种。1

①公用信号量。联系一组并发进程，相关的进程均可在此信号量上执行P操作和V操作，初值常常为1，用于实现进程互斥。1

②私有信号量。联系一组并发进程，仅允许拥有此信号量的进程执行P操作，而其他相关进程可在其上施行V操作。初值常常为0或正整数，多用于实现进程同步。1

PV操作是由两个操作，即P操作和V操作组成的。P操作和V操作是两个在信号量上进行操作的过程，假定用S表示信号量，则把这两个过程记作P(S)和V(S)。1

原理用PV操作来管理共享资源时，首先要确保PV操作自身执行的正确性。由于P(S)和V(S)都是在同一个信号量S上操作，为了使得它们在执行时不发生因交叉访问信号量S而可能出现的错误，约定P(S)和V(S)必须是两个不可被中断的过程，即让它们在屏蔽中断下执行。把不可被中断的过程称为原语。于是，P操作和V操作实际上应该是P操作原语和V操作原语。1

P操作的主要动作是：1

①S减1；1

②若S减1后仍大于或等于0，则进程继续执行；1

③若S减1后小于0，则该进程被阻塞后放入等待该信号量的等待队列中，然后转进程调度。1

V操作的主要动作是：1

①S加1；1

②若相加后结果大于0，则进程继续执行； 1

③若相加后结果小于或等于0，则从该信号的等待队列中释放一个等待进程，然后再返回原进程继续执行或转进程调度。1

PV操作对于每一个进程来说，都只能进行一次，而且必须成对使用。在PV原语执行期间不允许有中断发生。原语不能被中断执行，因为原语对变量的操作过程如果被打断，可能会去运行另一个对同一变量的操作过程，从而出现临界段问题。如果能够找到一种解决临界段问题的元方法，就可以实现对共享变量操作的原子性。2

应用实现进程的同步要实现进程的同步就必须提供一种机制，该机制能把其他进程需要的消息发送出去，也能测试自己需要的消息是否到达。把能实现进程同步的机制称为同步机制。不同的同步机制实现同步的方法也不同。PV操作和管程是两种典型的同步机制。在这里，只介绍怎样用PV操作实现进程间的同步。1

我们已经知道怎样用PV操作来实现进程的互斥。事实上，PV操作不仅是实现进程互斥的有效工具，而且还是一个简单而方便的同步工具。用一个信号量与一个消息联系起来，信号量的值为0表示期望的消息尚未产生；信号量的值为非0表示期望的消息已经存在。假定用信号量S表示某个消息，现在来看看怎样用PV操作达到进程同步的目的。1

(1)调用P操作测试消息是否到达

任何进程调用P操作可测试到自己所期望的消息是否已经到达。若消息尚未产生，则S=0，调用P(s)后，P(S)一定让调用者成为等待信号量S的状态，即调用者此时必定等待直到消息到达；若消息已经存在，则S≠0，调用P(S)后，进程不会成为等待状态而可继续执行，即进程测试到自己期望的消息已经存在。1

(2)调用V操作发送消息

任何进程要向其他进程发送消息时可调用V操作。若调用V操作之前S=0，表示消息尚未产生且无等待消息的进程，则调用V(S)后，V(s)执行S:=S+1使S≠0，即意味着消息已存在；若调用V操作之前S