操作系统P V题解
第一章 The P,V Theorem
在操作系统理论中有一个非常重要的概念叫做P,V原语。在我们研究进程间的互斥的时候经常会引入这个概念，将P,V操作方法与加锁的方法相比较，来解决进程间的互斥问题。实际上，他的应用范围很广，他不但可以解决进程管理当中的互斥问题，而且我们还可以利用此方法解决进程同步与进程通信的问题。
一 Introduction of P,V Theorem
阐述P,V原语的理论不得不提到的一个人便是赫赫有名的荷兰科学家你对这位科学家没有什么印象的话，提起解决图论中最短路径问题的们再熟悉不过的。P,V原语的概念以及1965年提出的。
1 Some Conceptions
信号量是最早出现的用来解决进程同步与互斥问题的机制，及对它进行的两个原语操作。信号量为一个整数，我们设这个信号量为：规定在S大于等于零的时候代表可供并发进程使用的资源实体数，在等待使用临界区的进程的个数。根据这个原则，设初值大于零。
p操作和v操作是不可中断的程序段，称为原语。于英文的pass,V是荷兰语的Verhoog,相当于英文中的P原语操作的动作是： （1）S减1；
（2）若S减1后仍大于或等于零，则进程继续执行；（3）若S减1后小于零，则该进程被阻塞后进入与该信号相对应的队列中，然后转进程调度。
V原语操作的动作是： （1）S加1；
（2）若相加结果大于零，则进程继续执行；（3）若相加结果小于或等于零，则从该信号的等待队列中唤醒一等待进程，然后再返回原进程继续执行或转进程调度。
需要提醒大家的是：P,V操作首先是一个原语操作，对于每一个进程来说，都只能进行一次。而且必须成对使用。且在P,V愿语执行期间不允许有中断的发生。对于具体的实现，方法非常多，可以用硬件实现，也可以用软件实现。这里不再赘述。
2 The Most Important Conceptions
临界资源是指每次仅允许一个进程访问的资源。带机等,软件的有消息缓冲队列、变量、数组、缓冲区等。每个进程中访问临界资源的那段程序称为临界区（临界资源是一次仅允许一个进程使用的共享资源）进入临界区，该进程进入后不允许其他进程进入。 P,V操作当中需要使用到的信号量的概念都是由他在在给信号量附初值的时候，P,V原语中incremnet。
属于临界资源可以是硬件的打印机、
E.W.Dijkstra。如果Dijkstra算法应当是我包括一个称为信号量的变量S。很显然，我们S小于零的时候，表示正我们显然就要P是荷兰语的Passeren，相当
磁。每次只准许一个进程进程的同步和互斥互斥：是指某一资源同时只允许一个访问者对其进行访问，具有唯一性和排它性。但互斥无法限制访问者对资源的访问顺序，即访问是无序的。
同步：是指在互斥的基础上（大多数情况），通过其它机制实现访问者对资源的有序访问。在大多数情况下，同步已经实现了互斥，特别是所有写入资源的情况必定是互斥的。少数情况是指可以允许多个访问者同时访问资源。
二Several Typical Examples
本节我们讨论几个利用信号量来实现进程互斥和同步的经典例子。这里的问题关键是如何选择信号量和如何安排P、V原语的使用顺序。
依据信号量与进程的关系，我们可把进程中使用的信号量分成私有信号量和公用信号量。私有信号量是指只与制约进程和被制约进程有关的信号量；公用信号量是指与一组并发进程有关的信号量。这里请不要和C++、JAVA 等编程语言的公有、私有相混淆。这里指的是相对于共享资源来说的。
1 生产者一消费者问题(producer-consumer problem)
生产者--消费者问题(producer-consumer problem)是指若干进程通过有限的共享缓冲区交换数据时的缓冲区资源使用问题。
问题描述：假设“生产者”进程不断向共享缓冲区写人数据(即生产数据)，而“消费者”进程不断从共享缓冲区读出数据(即消费数据)；共享缓冲区共有n个；任何时刻只能有一个进程可对共享缓冲区进行操作。所有生产者和消费者之间要协调，以完成对共享缓冲区的操作。
Figure 1.1: producer-consumer problem
我们可把共享缓冲区中的n个缓冲块视为共享资源，生产者写人数据的缓冲块成为消费者可用资源，而消费者读出数据后的缓冲块成为生产者的可用资源。为此，可设置三个信号量：full、empty和mutex。其中：full表示有数据的缓冲块数目，初值是0；empty表示空的缓冲块数初值是n；mutex用于访问缓冲区时的互斥，初值是1。实际上，full和empty间存在如下关系：full+ empty = N
The P,V code Using Pascal buffer: array [0..k-1]of integer;
in,out: 0..k-1;//in记录第一个空缓冲区，out记录第一个不空的缓冲区 empty,full,mutex: semaphore;
//empty控制缓冲区不满,full控制缓冲区不空,mutex保护临界区； //初始化empty=k,full=0,mutex=1
cobegin
procedure producer: procedure consumer: while true then while true then begin begin produce(&item); p(full);
p(empty); p(mutex);
p(mutex); item:=buffer[out]; buffer[in]:=item; out:=(out+1) mod k; in:=(in+1) mod k; v(mutex); v(mutex); v(empty);
v(full); consume(&item); end end coend
注意：这里每个进程中各个P操作的次序是重要的。各进程必须先检查自己对应的资源数在确信有可用资源后再申请对整个缓冲区的互斥操作；否则，操后申请自己对应的缓冲块资源，就可能死锁。出现死锁的条件是，互斥操作后，才发现自己对应的缓冲块资源，这时已不可能放弃对整个缓冲区的占用。采用AND信号量集，相应的进入区和退出区都很简单。如生产者的进入区为mutex)，退出区为Ssignal(full，mutex)。
2 读者--写者问题(Readers-Writers Problem)
问题描述：有一个许多进程共享的数据区，这个数据区可以是一个文件或者主存的一块空间；有一些只读取这个数据区的进程（Reader）和一些只往数据区写数据的进程此外还需要满足以下条件：
（1）任意多个读进程可以同时读这个文件； （2）一次只有一个写进程可以往文件中写；
（3）如果一个写进程正在进行操作，禁止任何读进程度文件。实验要求用信号量来实现读者写者问题的调度算法。实验提供了过P()、V()两个方法实现了P、V原语的功能。实验的任务是修改Writer类的Write方法。
我们需要分两种情况实现该问题：
读优先： 要求指一个读者试图进行读操作时，如果这时正有其他读者在进行操作，他可直接开始读操作，而不需要等待。
写优先： 一个读者试图进行读操作时，如果有其他写者在等待进行写操作或正在进行写操作，他要等待该写者完成写操作后才开始读操作。
The P,V code Using Pascal 读者优先算法：
rwmutex 用于写者与其他读者/写者互斥的访问共享数据 rmutex 用于读者互斥的访问 readcount 读者计数器
var rwmutex, rmutex ： semaphore := 1, 1 ； int readcount = 0;
cobegin
procedure reader_i
begin // i=1,2,?.
P(rmutex); Readcount + +;
if (readcount = = 1) P(rwmutex); V(rmutex);
申请到对整个缓冲区的如果Swait(empty，(Writer)，
Semaphore类，该类通Reader类的Read方法以及先申请对整个缓冲区的互斥读数据； P(rmutex); Readcount - -;
if (readcount = = 0) V(rwmutex); V(rmutex); end
procedure Writer_j
begin // j = 1,2,?. P(rwmutex); 写更新； V(rwmutex); end
coend
The P,V code Using Pascal 写者优先：
1）多个读者可以同时进行读
2）写者必须互斥（只允许一个写者写，也不能读者写者同时进行）
3）写者优先于读者（一旦有写者，则后续读者必须等待，唤醒时优先考虑写者）
如果读者数是固定的，我们可采用下面的算法：
rwmutex：用于写者与其他读者/写者互斥的访问共享数据
rmutex： 该信号量初始值设为10，表示最多允许10个读者进程同时进行读操作 var rwmutex, rmutex ： semaphore := 1, 10 ； cobegin
procedure reader_i
begin // i=1,2,?.
P(rwmutex); //读者、写者互斥 P(rmutex);
V(rwmutex); // 释放读写互斥信号量，允许其它读、写进程访问资源 读数据； V(rmutex); end
procedure Writer_j
begin // j = 1,2,?.
P(rwmutex);
for (i = 1;i <= 10;i + +) P(rmutex);
//禁止新读者，并等待已进入的读者退出 写更新；
for (i = 1;i <= 10;i + +) V(rmutex); // 恢复允许rmutex 值为10 V(rwmutex); end
相关推荐：
loading