进程管理2--进程的同步与信号量

1、进程之间两种形式的制约关系

系统中各进程之间在逻辑上存在着两种制约关系：

      即为完成同一个任务的各进程之间，因需要协调它们的工作而相互等待、相互交换信息所产生的直接制约关系。   

     是进程共享独占型资源而必须互斥执行的间接制约关系。

2、临界资源、临界区

例：生产者-消费者问题

      一组生产者向一组消费者提供产品，它们共享一个缓冲池，生产者向其中投放产品，消费者从中取得产品。它是许多相互合作进程的抽象，如输入进程与计算进程；计算进程与打印进程等。

      设缓冲池的长度为n（n>0），一群生产者进程P1,P2,…，Pm，一群消费者进程C1,C2,…，Ck，如图所示。假定生产者和消费者是相 互等效，只要缓冲池未满，生产者就可以把产品送入缓冲区，类似地，只要缓冲池未空，消费者便可以从缓冲区取走产品并消耗它。

      生产者和消费者进程是以异步方式运行的，但必须保持同步关系，即禁止生产者向满的缓冲池输送产品，也禁止消费者从空的缓冲池提取产品。

int n;  //n为缓冲池中缓冲区的个数；
buffer:array[0..n-1] of item;  //buffer为具有n个缓冲区的缓冲池；
in,out:0..n-1;  //in和out为指针，分别指向下一个可投放产品的缓冲区和下一个可获取产品的缓冲区
counter:0..n;

void producer()  //生产者
{
   while(1) {
     ……
     produce an item in nextp;  //生产一个产品
     ……
     if (counter <= n) {   //当生产的数目等于count的时候停止
         buffer[in] = nextp;
         in = (in + 1) mod n;  
         counter = counter + 1;
     } else {
        break;
     }
   }
}

void consumer()  //消费者
{
   while(1) {
       while (counter > 0) {
           nextc = buffer[out];
           out = (out + 1) mod n;
           counter = counter - 1;
           consume the item in nextc;  //消费一个产品
       }
       break;
    }
}

用机器语言实现变量的加1、减1的操作为：

//变量counter加1:  
register1 = counter;
register1 = register1 + 1;
counter = register1;

//变量counter减1:  
register2 = counter;
register2 = register2-1;
counter = register2;

若按另一顺序对变量进行修改，会得到什么结果？

register1 = counter;
register1 = register1 + 1;
register2 = counter;
register2 = register2 - 1;
counter = register1;
counter = register2;

为了保证临界资源的正确使用，可以把一个访问临界资源的循环进程描述如下：

增加在临界区前面的一段代码，用于检查所要访问的临界资源此刻是否被访问。

增加在临界区后面的一段代码，用于将临界资源的访问标志恢复为未被访问标志。

进程中除了进入区、临界区及退出区之外的其余代码。

要进入临界区的若干进程必须满足：

（1）一次只允许一个进程进入临界区

（2）任何时候，处于临界区的进程不得多于一个

（3）进入临界区的进程要在有限的时间内退出

（4）如果不能进入自己的临界区，则应让出处理机资源

解决临界区（互斥）问题的几类方法：

（1）软件方法和硬件方法

（2） P-V操作

（3）管程机制

3、同步机制应遵循的规则

• 空闲让进:当无进程处于临界区时，表明临界资源处于空闲状态，应允许一个请求进入临界区的进程立即进入自己的临界区，以有效地利用临界资源。

• 忙则等待:当已有进程进入临界区时，表明临界资源正在被访问，因而其他试图进入临界区的进程必须等待，以保证对临界资源的互斥访问。

• 有限等待:对要求访问临界资源的进程，应保证在有限时间内能进入自己的临界区，以免陷入“死等”状态。

• 让权等待:当进程不能进入自己的临界区时，应立即释放处理机，以免进程陷入“忙等”。

信号量机制是荷兰科学家E.W.Dijkstra在1965年提出的一种同步机制，也称为P、V操作。由最初的整型信号量发展为记录型信号量，进而发展为信号量集机制。

1、整型信号量

   wait(S)： while S <= 0  do no-op； 测试有无可用资源

             S = S - 1;   可用资源数减一个单位

   signal(S): S = S + 1;

主要问题：只要S <= 0， wait操作就不断地测试（忙等），因而，未做到“让权等待”。

2、记录型信号量

       1、设置一个代表资源数目的整型变量value（资源信号量）

       2、设置一链表L用于链接所有等待访问同一资源的等待进程

     Type semaphore=record

                      value:integer;

                      L: list of process;

                    end

     Var  S: semaphore;

//调用阻塞原语将该进程状态置为
//等待状态，将该进程的PCB插入
//相应的等待队列S.L末尾;
  wait(S)：  
      S.value:=S.value-1;    
      if S.value<0 then
         block(S.L);

//调用唤醒原语唤醒相应等待队列
//S.L中等待的一个进程,改变其状
//态为就绪态,并将其插入就绪队列
  signal(S): 
      S.value:=S.value+1;  
      if S.value£0  then
         wakeup(S.L);

在记录型信号量机制中：

S.value的初值表示系统中某类资源的数目。

S.value的初值为1，S为互斥信号量；

S.value的初值大于1，S为资源信号量；

在记录型信号量机制中

每次wait(S)操作意味着进程请求一个单位的资源，资源数目减1。当S.value<0时表示资源已分配完毕，进 程调用Block()原语进行自我阻塞，放弃处理机，并插入到信号量链表S.L中。此时，|S.value| 表示在该信号量链表中已阻塞进程的数目。

每次signal(S)表示执行进程释放一个单位资源，资源数目加1。若加1后仍有S.value<=0，则表示在该信号量链表中，还有等待该资源的进程，则调用Wakeup()原语，将链表中第一个进程唤醒。

AND型信号量（了解）

一般信号量集（了解）

1、利用信号量实现进程互斥

    利用信号量可以方便地解决临界区问题（进程互斥）（见后面的图）。为临界资源设置一互斥信号量lock，初值为1，则实现进程A、B、C互斥的描述：

2、利用信号量描述前趋关系

方法：

     若图中存在结点S1指向结点S2的有向边，表示进程P1中的程序段S1应该先执行，而进程P2中的程序段S2后执行。设置一个信号量s,初值为0，将V(s)放在S1后面，而在S2前面先执行P(s)。

进程P1的语句序列为：S1;V(s)

进程P2的语句序列为：P(s);S2

例：利用信号量来描述前趋图关系