进程的三种基本状态

（1）就绪状态：进程已获得除CPU外的所有必要资源，只等待CPU时的状态。一个系统会将多个处于就绪状态的进程排成一个就绪队列。

（2） 执行状态：进程已获CPU，正在执行。单处理机系统中，处于执行状态的进程只一个；多处理机系统中，有多个处于执行状态的进程。

（3） 阻塞状态：正在执行的进程由于某种原因而暂时无法继续执行，便放弃处理机而处于暂停状态，即进程执行受阻。（这种状态又称等待状态或封锁状态）

通常导致进程阻塞的典型事件有：请求I/O，申请缓冲空间等。

一般，将处于阻塞状态的进程排成一个队列，有的系统还根据阻塞原因不同把这些阻塞集成排成多个队列。

一个进程在运行期间，不断地从一种状态转换到另一种状态，它可以多次处于就绪状态和执行状态，也可以多次处于阻塞状态。

  1. 就绪→执行

    处于就绪状态的进程，当进程调度程序为之分配了处理机后，该进程便由就绪状态转变成执行状态。

  2. 执行→就绪

    处于执行状态的进程在其执行过程中，因分配给它的一个时间片已用完而不得不让出处理机，于是进程从执行状态转变成就绪状态。

  3. 执行→阻塞

    正在执行的进程因等待某种事件发生而无法继续执行时，便从执行状态变成阻塞状态。

  4. 阻塞→就绪

    处于阻塞状态的进程，若其等待的事件已经发生，于是进程由阻塞状态转变为就绪状态。

信号量和PV操作

信号量

信号量是最早出现的用来解决进程同步与互斥问题的机制。

信号量（Saphore）由一个值和一个指针组成，指针指向等待该信号量的进程。信号量的值表示相应资源的使用情况。

信号量s的物理含义：

(1) 当S>0时，S的值表示同类可用资源的数量。

(2) 当S=0时，表示无可用资源。

(3) 当S<0时，S的绝对值表示正被阻塞的进程数量。

PV操作

P(S)表示申请一个资源，V(S)表示释放一个资源。

P原语（阻塞原语）操作的动作是：

  1. sem减1；
  2. 若sem减1后仍大于或等于零，则进程继续执行；
  3. 若sem减1后小于零，则表示申请的资源已被占用,进程必须等待;信号量的绝对值表示希望申请资源但没有得到而进入阻塞状态的进程数.

V原语（唤醒原语）操作的动作是：

  1. sem加1；
  2. 若相加结果大于零，则表示有进程因等待该资源而处于阻塞队列,执行V操作的进程继续执行.
  3. 若相加结果小于或等于零，则表示有进程希望得到该资源但没有得到而进入了阻塞队列,从而应从等待队列中唤醒一个进程,执行V操作的进程继续执行.

对P、V操作的使用应当注意：

  1. P、V操作都是成对出现的：互斥操作时，它们在同一进程中；同步操作时，它们处于不同进程。

  2. 在进程中，P操作的位置和次序至关重要，如果使用不当，会造成严重后果。一般情况下，对互斥信号量的P操作在后。而对于V操作并没有特别的限制，只是要注意V操作是主动的还是被动的。

P、V操作的优点是：P、V操作原语完备，表达能力强，任何同步和互斥问题都可以用它来解决。

P、V操作的缺点是：作为进程通信的工具，它不够安全，而且在一些复杂问题的实现上相对复杂。

关于PV操作容易产生的一些疑问：

  1. S大于0那就表示有临界资源可供使用，为什么不唤醒进程？

    S大于0的确表示有临界资源可供使用，也就是说这个时候没有进程被阻塞在这个资源上，所以不需要唤醒。

  2. S小于0应该是说没有临界资源可供使用，为什么还要唤醒进程？

    V原语操作的本质在于：一个进程使用完临界资源后，释放临界资源，使S加1，以通知其它的进程，这个时候如果S<0，表明有进程阻塞在该类资源上，因此要从阻塞队列里唤醒一个进程来“转手”该类资源。比如，有两个某类资源，四个进程A、B、C、D要用该类资源，最开始S=2，当A进入，S=1，当B进入S=0，表明该类资源刚好用完， 当C进入时S=-1，表明有一个进程被阻塞了，D进入，S=-2。当A用完该类资源时，进行V操作，S=-1，释放该类资源，因为S<0，表明有进程阻塞在该类资源上，于是唤醒一个。

  3. 如果是互斥信号量的话，应该设置信号量S=1，但是当有5个进程都访问的话，最后在该信号量的链表里会有4个在等待，也是说S=-4，那么第一个进程执行了V操作使S加1，释放了资源，下一个应该能够执行，但唤醒的这个进程在执行P操作时因S<0，也还是执行不了，这是怎么回事呢？

    当一个进程阻塞了的时候，它已经执行过了P操作，并卡在临界区那个地方。当唤醒它时就立即进入它自己的临界区，并不需要执行P操作了，当执行完了临界区的程序后，就执行V操作。

  4. S的绝对值表示等待的进程数，同时又表示临界资源，这到底是怎么回事？

    当信号量S小于0时，其绝对值表示系统中因请求该类资源而被阻塞的进程数目.S大于0时表示可用的临界资源数。注意在不同情况下所表达的含义不一样。当等于0时，表示刚好用完。

生产者-消费者模型

假设存在两个进程，生产者进程T1和消费者进程T2,它们共享一个缓冲区。

设置生产者进程和消费者进程的私用信号量为S1和S2,初值分别为1和0。规定：缓冲区“满”，生产者进程不能放产品；缓冲区“空”，消费者进程不能从中取产品。对两个进程的描述如下：

我们可以通俗地把以上两个进程通信的过程理解为：T1生产了一件产品，要放进缓冲区，它先看缓冲区是否可用，所以要对缓冲区执行P操作，放进一件产品后，用V操作通知T2可以拿产品了； T2要从缓冲区拿出一件产品，要先看缓冲区是否有产品，所以要执行P操作，拿走产品后，用V操作通知T1可以再放产品了。

如果现有k个生产者，m个消费者，共享n个缓冲区，这样，只要n个缓冲区还有空余，T1进程就可以放入产品；只要缓冲区还有产品，T2进程就可以拿出产品。这里判断空和满的信号量还应有计数的功能，所以我们增加同步信号量mutex,初值为1,并设S1、S2的初值分别为n和0。对两个进程的描述如下：

读者-写者模型

并发进程对数据的读写操作是经常发生的，Courtois提出了关于读写同步的问题，称为读者写者问题。

这一问题的要求是：多个读进程可以同时共享资源，但不能和写进程共享;写进程之间互斥，访问时必须独占资源。

这就需要设置一个全局变量对读进程进行计数，当第一个读进程开始进行访问时执行P操作，当最后一个读进程结束访问时执行V操作。

现假设读者优先于写者，即当有读进程在读时，写进程被迫等待，其他读进程允许并发执行。使用readnum对读者计数,初值为0; mutex是对变量readnum进行互斥操作的信号量，初值设为1; write是写信号量。具体程序如下：

很明显，当读进程在读而使一个请求写的进程阻塞时，如果仍有进程不断地请求读，则写者有可能因读者请求过多而无限等待下去，写进程一直得不到响应，这种现象称为“饥饿”现象。

所以我们又设计了另一种算法，让写者在任何时刻都优先于读者，即当有进程在读文件时，如果有进程请求写，那么新的读进程被拒绝，待现有的读进程完成读操作后，立即让写进程开始运行，当无写进程工作时才让读进程工作。

下面，用信号量S实现读者与写者或写者之间的互斥，用信号量Sn限制系统中最多有n个进程，初值为n。具体程序如下：