在上一篇笔记中,我们介绍到了通过信号量机制解决进程同步和进程互斥问题的原理,不过,在遇到实际问题的时候,信号量机制到底是如何发挥作用的呢?这篇笔记将会从几个经典的问题出发,在解决问题的过程中,我们会体会到信号量机制的运用。

1 生产者 — 消费者问题

生产者 — 消费者问题描述的是一个对产品生产和消费的过程:首先,对于生产者,如果缓冲区没满,它就会生产产品并将其放入缓冲区,如果缓冲区已满,它就会进行等待;对于消费者,如果缓冲区不空,它就会取走产品并释放缓冲区,如果缓冲区已空,它就会进行等待。

对于这个问题,不难看出有两个进程,一个是生产者进程,一个是消费者进程;同时有一个互斥关系,在同一时间内,只能有一个进程访问同一个缓冲区,要么放入产品,要么取走产品;同时有两个同步关系,一个指的是:必定是先生产产品,后取走产品,另一个指的是:必定是先释放缓冲区,后使用缓冲区。

因此,我们在这里需要准备两个进程,一个是表示生产者进程的 producer,一个是表示消费者进程的 consumer;同时,我们需要准备三个信号量。第一个信号量是互斥信号量,实现对缓冲区这个资源的互斥访问,用 mutex = 1 表示;第二个信号量是同步信号量,表示空闲缓冲区的数量,用 empty = n 表示;第三个信号量也是同步信号量,表示非空闲缓冲区的数量,也即产品数量,用 full = 0 表示。

先考虑对互斥关系的实现。这里所谓的临界资源其实就是某一个缓冲区,生产者进程把产品放进去,消费者进程从里面取走产品,这两者不能同时进行,所以这里是互斥的关系。我们可以想象到,对每一个进程而言,他都有属于自己的一对 PV 操作,用以实现对缓冲区资源的访问。另外,生产者在进行 PV 操作之前,必定要先生产产品;而消费者在进行 PV 操作之后,必定要使用产品。这时候,初步的伪代码是这样的:

producer(){                         consumer(){
    while(1){                           while(1){
        生产产品                              P(mutex)
        P(mutex)                             从缓冲区中取走产品 
		把产品放入缓冲区                       V(mutex)
        V(mutex)                             使用产品 
    }                                   }     
}                                   }

接着考虑第一个同步关系。关注缓冲区,可以知道一定是先释放缓冲区,后使用缓冲区,所以这里“前操作”是释放缓冲区,“后操作”是使用缓冲区,根据上篇笔记所讲的 “前VP后”,我们需要在“前操作”之后针对 empty 这个信号量进行一次 V 操作,需要在“后操作”之前针对 empty 进行一次 P 操作。所以,这时候代码变成:

producer(){                         consumer(){
    while(1){                           while(1){
        生产产品                             P(mutex)
        P(empty)                            从缓冲区中取走产品 
		P(mutex)                            V(mutex)
        把产品放入缓冲区                      V(empty)  
        V(mutex)                            使用产品 
    }                                   }     
}                                   }

再考虑第二个同步关系。关注产品本身,可以知道一定是先生产产品,后使用产品,更进一步地说,一定是先生产产品并将其放入缓冲区,后从缓冲区取出产品并使用。这里划分出前后两个操作,所以再次安排一对 PV 操作。这时候,代码变成:

producer(){                         consumer(){
    while(1){                           while(1){
        生产产品                            P(full)
        P(empty)                           P(mutex)
		P(mutex)                           从缓冲区中取走产品 
        把产品放入缓冲区                     V(mutex) 
        V(mutex)                           V(empty)  
        V(full)                            使用产品 
    }                                   }     
}                                   }

这个实际上就是最后的代码了。现在我们试着跑一下流程:初始的时候 empty = n,表示所有缓冲区都是空闲的,同时 full = 0,表示一个产品都没生产出来。假如处理机首先来到 consumer 进程,那么就会通过 P(full) 检查是否有产品,这里当然是没有,所以它只能进行等待;处理机来到 producer,首先通过 P(empty) 检查是否有空闲缓冲区,这里当然有,于是它开始把生产的产品放入缓冲区,随后记录产品的数量,这个过程可以反复进行,直到所有缓冲区都被占用了,此时 producer 就会进入等待状态,等待 consumer 进程取出产品、释放缓冲区;当然还有可能的情况是,producer 尚未占用完所有缓冲区,进程就切换到 consumer 了,那么这时候 consumer 因为检查到有产品,所以也会取出产品、释放缓冲区。

这里要注意可能会引起“死锁”现象的一种写法。如下所示:

producer(){                         consumer(){
    while(1){                           while(1){
        生产产品                            P(mutex)
        P(mutex)                           P(full)
		P(empty)                           从缓冲区中取走产品 
        把产品放入缓冲区                     V(mutex) 
        V(mutex)                           V(empty)  
        V(full)                            使用产品 
    }                                   }     
}                                   }

这个写法的问题在于,还没有先检查缓冲区是否没满或者是否非空,就强行进行互斥的“上锁”。假如还是按照前面的流程,一开始处理机在 consumer 这里,那么 consumer 实际上在没有检查缓冲区是否非空的情况下就直接“上锁”了,这导致它在 P(full) 这一步的时候被卡住,只能等待,而在之后切换到 producer 的时候,正常情况下他应该生产可供对方消费的产品,但是由于对方已经上了锁,所以 producer 在 P(mutex) 这一步也被卡住了,只能进行等待。这也就是说,producer 等待 consumer 释放临界区,而 consumer 等待 producer 使用缓冲区,双方陷入循环等待,造成了“死锁”。

另一种情况,我们也可以设想一开始处理机是在 producer 这里,那么是不是不会导致“死锁”呢?并不是。事实上,按照这种情况正常用完全部缓冲区之后,如果处理机还是在 producer 这里,那么 producer 在检查缓冲区是否已满之前也会将自己提前上锁,在 P(empty) 这一步陷入等待,之后即使进程切换到 consumer 这里,它也会因为对方提前上锁,而导致自己在 P(mutex) 这一步陷入等待。也就是说,这不过是前面那种”死锁“现象的翻版。

总之,关键就在于不管是消费者进程,还是生产者进程,都不能先上锁再检查,否则就有可能发生死锁。

2. 橘子 — 苹果问题

橘子 — 苹果问题其实是生产者 — 消费者问题的一种变形,它有多种类型的生产者、多种类型的消费者,所以也叫多生产者 — 多消费者问题。它描述的是:有一个只能放一种水果的空盘子,父亲可以放苹果在上面,母亲可以放橘子在上面,女儿只吃父亲的苹果,而儿子只吃母亲的橘子。只有盘子空的时候父母亲才放水果上去,只有盘子中的水果符合自己的喜好时,女儿或者儿子才会去拿。

从上面这个过程,我们可以分析一下有哪些变量。首先可以肯定的是,有四个进程,父母亲扮演着生产者,女儿儿子扮演着消费者;同时有一个互斥关系,在同一个时间,只能有一个人去“访问”盘子这个资源,所谓“访问”,无非是四种情况:放苹果、放橘子、拿苹果、拿橘子;同时,有三个同步关系,第一个指的是,必定是先有父亲放苹果,后有女儿拿苹果。第二个指的是,必定是先有母亲放橘子,后有儿子拿橘子。第三个指的是,必定是先有女儿或者儿子拿走水果,后有父亲或者母亲放上水果。

因此,这里我们准备四个进程:DadMomSonDaughter;同时,我们需要准备四个信号量。第一个信号量是互斥信号量,实现对盘子这个资源的互斥访问,用 mutex = 1 表示;第二个信号量是同步信号量,表示盘子中苹果的数量,用 apple = 0 表示;第三个信号量也是同步信号量,表示盘子中橘子的数量,用 orange = 0 表示;第四个同样是同步信号量,表示盘子中还可以放多少水果,用 plate=1 表示。

接下来,我们仿照生产者—消费者问题,对伪代码进行推导。由于四个进程都有对互斥资源的访问,也即都有一个 PV 操作,然后,对父亲而言,在 PV 操作之前自己要先拿出苹果,母亲则是拿出橘子;对女儿而言,在 PV 操作之后要吃掉苹果,儿子则是吃掉橘子。这时候,初步的伪代码是这样的:

Dad(){                        Mom(){
    while(1){                     while(1){
        拿出苹果                       拿出橘子
        P(mutex)                      P(mutex) 
		把苹果放入盘子                  把橘子放入盘子
        V(mutex)                      V(mutex)
    }                             }     
}                             }
Daughter(){                   Son(){
    while(1){                     while(1){
        P(mutex)                      P(mutex)
        从盘中取出苹果                 从盘中取出橘子 
		V(mutex)                      V(mutex)
        吃掉苹果                      吃掉橘子
    }                             }     
}                             }

再来考虑第一类同步关系,关注盘子,可以看到必定是先让盘子空出来,后让人使用盘子,所以这里前后操作就分清楚了,接下来再根据“前VP后”插入代码,此时的伪代码是这样的:

Dad(){                        Mom(){
    while(1){                     while(1){
        拿出苹果                       拿出橘子
        P(plate)                      P(plate)  
        P(mutex)                      P(mutex) 
		把苹果放入盘子                  把橘子放入盘子
        V(mutex)                      V(mutex)
    }                             }     
}                             }
Daughter(){                   Son(){
    while(1){                     while(1){
        P(mutex)                     P(mutex)
        从盘中取出苹果                 从盘中取出橘子 
		V(mutex)                     V(mutex)
        V(plate)                     V(plate) 
        吃掉苹果                      吃掉橘子
    }                             }     
}                             }

最后考虑第二类同步关系,这次关注水果,可以看到必定是先拿出水果放到盘子上,后取出盘子上的水果吃掉,根据“前VP后”,最后的伪代码如下:

Dad(){                        Mom(){
    while(1){                     while(1){
        拿出苹果                       拿出橘子
        P(plate)                      P(plate)  
        P(mutex)                      P(mutex) 
		把苹果放入盘子                  把橘子放入盘子
        V(mutex)                      V(mutex)
        V(apple)                      V(orange)
    }                             }     
}                             }
Daughter(){                   Son(){
    while(1){                     while(1){
        P(apple)                     P(orange)
        P(mutex)                     P(mutex)
        从盘中取出苹果                 从盘中取出橘子 
		V(mutex)                     V(mutex)
        V(plate)                     V(plate) 
        吃掉苹果                      吃掉橘子
    }                             }     
}                             }

更进一步地,其实我们这里并不需要互斥变量 mutex,试着把它去掉并跑一下流程:

Dad(){                        Mom(){
    while(1){                     while(1){
        拿出苹果                       拿出橘子
        P(plate)                      P(plate)  
		把苹果放入盘子                  把橘子放入盘子
        V(apple)                      V(orange)
    }                             }     
}                             }
Daughter(){                   Son(){
    while(1){                     while(1){
        P(apple)                     P(orange)
        从盘中取出苹果                 从盘中取出橘子 
        V(plate)                     V(plate) 
        吃掉苹果                      吃掉橘子
    }                             }     
}                             }

在一开始,任何进程都可能先来到处理机,如果是儿子或者女儿,则会因为盘子中暂时没有水果而被堵塞,如果是父母亲,则会按照正常流程放水果上去,我们假设是第一种情况。由于儿子和女儿进程相继被阻塞,所以进程来到父亲这,拿出苹果并放在盘子上。假设这中途因为时间片的缘故被切换到母亲进程,母亲进程由于盘子已经被使用,所以也进入阻塞队列。之后又来到父亲进程,由于它唤醒了女儿进程,女儿进程直接来到就绪队列,并在父亲进程执行完毕之后执行,吃掉苹果。一吃掉苹果,盘子就空了,唤醒了母亲进程,母亲进程放上橘子(这期间即使其它进程进来,也会被阻塞),唤醒了儿子进程,儿子进程就可以吃掉橘子了。

整个过程可能存在各种进程切换的情况,但是无论哪种情况,都可以保证做到进程同步和进程互斥,并且这是在不借助互斥信号量的前提下做到的。基于这个原因,我们在这里可以不使用互斥信号量。

3. 吸烟者问题

吸烟者问题其实是生产者 — 消费者问题的另一种变形,它有可以生产多种类型产品的一个生产者,以及多种类型的消费者,所以也叫单生产者 — 多消费者问题。它描述的是:有一个供应者和三个抽烟者,供应者拥有无限的烟草、纸、胶水三种材料,抽烟者1号只有烟草,抽烟者2号只有纸,抽烟者3号只有胶水。每次供应者提供其中两种材料,其中一个抽烟者拿着这两种材料与自己的材料结合进行抽烟,抽完再发送信号给供应者,供应者重新供应材料。整个过程按照三个抽烟者轮流抽烟的顺序循环往复。

从上面这个过程,我们可以分析一下有哪些变量。首先可以肯定的是,有四个进程,也就是一个供应者和三个抽烟者;同时有一个互斥关系,在同一个时间,只能有一个人去“访问”桌子这个资源(假定材料放在桌子上),所谓访问,无非就是放东西和拿东西两个动作;同时,有四个同步关系,第一个指的是,必定是先放材料组合一,后有抽烟者1号拿材料。第二个指的是,必定是先放材料组合二,后有抽烟者2号拿材料。第三个指的是,必定是先放材料组合三,后有抽烟者3号拿材料;第四个指的是,必定是某一个抽烟者先发出信号,后有供应者重新供应材料。

因此,这里我们准备四个进程:ProviderSmoker1Smoker2Smoker3;同时,我们准备三个同类信号量,即 offer1offer3,分别表示桌子上某个组合的数量。注意我们这里不准备互斥信号量,因为正如之前的问题提到的,这里即使不引入互斥信号量,也不会影响到我们对于进程互斥和同步的实现。另外,我们再准备一个信号量 finish = 0 表示抽烟是否完成。除了这些,由于题目要求三个抽烟者是轮流抽烟的,所以对于供应者来说,它不能只提供单一材料组合,而要根据索取者的身份选择给定的材料,这里我们还需要再用一个变量 i 记录具体是哪个抽烟者。从 0 到 2,分别表示三个抽烟者。而且在每一次给完材料之后,我们还要改变这个变量的值,好让它指向下一个抽烟者,从而达到“轮流抽烟”的目的。

接下来,我们对伪代码进行推导。由于四个进程都有对互斥资源的访问,也即都有一个 PV 操作,所以初步的伪代码是这样的:

Provider(){           Smoker1(){          Smoker2(){        Smoker3(){
    while(1){           while(1){           while(1){         while(1){ 
     P(mutex)            P(mutex)            P(mutex)          P(mutex)
     放组合一             拿走组合一           拿走组合二         拿走组合三
     放组合二             抽烟,发信号         抽烟,发信号        抽烟,发信号  
     放组合三             V(mutex)            V(mutex)          V(mutex)
   }                    }                    }                 }
}                      }                   }                 }

不过,我们前面说了这里不需要互斥信号量,所以把它去掉。并且这里 Provider 的三个操作肯定是要根据抽烟者身份来决定的,所以我们加个 if 判断,以及对于 i 值的修改:

Provider(){                     Smoker1(){          
    while(1){                      while(1){                     
      if(i==0){                      拿走组合一           
      	放组合一                      抽烟,发信号           
      } else if(i==1){             }                   
        放组合二                 }                 
      } else if(i==2){
        放组合三
      }
      i = (i+1)%3       
  }                  
}
Smoker2(){        Smoker3(){
  while(1){         while(1){  
     拿走组合二         拿走组合三
     抽烟,发信号       抽烟,发信号
   }                 } 
}                 }    

按照“前VP后”的原则,必定是先把某个组合放在桌子上,后有某个抽烟者把组合拿走,所以我们考虑在放置组合的语句后面加上 V(offer),在拿组合的语句前面加上 P(offer);同理,必定是抽烟者先抽完烟发出信号,后有供应者重新放上材料组合,所以我们考虑在抽完烟的语句后面加上 V(finish),在放置组合的语句前面加上 P(finish),所以此时伪代码如下:

Provider(){                    
    while(1){   
      P(finish)  
      if(i==0){                     
      	放组合一 
        V(offer1)
      } else if(i==1){             
        放组合二 
        V(offer2)
      } else if(i==2){
        放组合三
        V(offer3)
      }
      i = (i+1)%3       
  }                  
}
Smoker1(){          Smoker2(){        Smoker3(){
  while(1){           while(1){         while(1){ 
    P(offer1)           P(offer2)         P(offer3)
    拿走组合一           拿走组合二         拿走组合三
    抽烟,发信号         抽烟,发信号       抽烟,发信号    
    V(finish)           V(finish)         V(finish)
  }                    }                 }
}                   }                 }

不过这样我们会发现,Provider 一上处理机就会被阻塞了,因为马上就遇到了 P(finish),而此时根本还没有人拿到烟,更不可能抽完烟。事实上,我们想要的效果只是“抽烟者先抽完烟发出信号,供应者后重新供应”,也就是说,在抽烟者发出信号之前,我们要阻止 Provider 到达“重新放置组合”这一步,我们下意识考虑到的是直接在放置组合语句前加上限制条件,但这样会造成阻塞,所以放弃这个方案。那么何不把限制条件放在放置组合语句后面呢?while 本来就是个首尾连接的循环,放置组合语句的尾部其实就是语句的首部,如果我们在尾部给予了限制,而限制条件满足了,那么照样可以实现“阻止进程 Provider 到达放置组合语句”这个效果。如下所示:

Provider(){                    
    while(1){   
      if(i==0){                     
      	放组合一 
        V(offer1)
      } else if(i==1){             
        放组合二 
        V(offer2)
      } else if(i==2){
        放组合三
        V(offer3)
      }
      i = (i+1)%3       
      P(finish)    
  }                  
}
Smoker1(){          Smoker2(){        Smoker3(){
  while(1){           while(1){         while(1){ 
    P(offer1)           P(offer2)         P(offer3)
    拿走组合一           拿走组合二         拿走组合三
    抽烟,发信号         抽烟,发信号       抽烟,发信号    
    V(finish)           V(finish)         V(finish)
  }                    }                 }
}                   }                 }

可以看到,这里一定会是抽烟者抽完烟发出信号之后,Provider 才有办法重新放置组合。因为但凡 Provider 想要抢先一步重新放置组合,它都要经过底部 P(finish) 的检查,而这个检查在 Smoker 发出信号之前,不可能轻易通过,因此 Provider 如果想要“强闯”,只会导致自己进入阻塞队列,之后进程切换到 Smoker,Smoker 发出信号,V(finish) 将 Provider 唤醒,Provider 才能重新放置组合,由此就实现了“先发出信号,后重新放置组合”的效果。

4. 读者 — 写者问题

读者 — 写者问题与我们之前遇到的问题类型不同,它描述的是:有读者和写者两组进程,它们共同访问同一个文件。对于读者,它可以与多个读者共同读取文件(因为不会修改到文件);对于写者,它不能与其他任何进程共同访问文件(如果另一进程是写,则可能覆盖同一内容;如果是读,则可能修改到要读的内容)。也就是说,这里的互斥问题是读写互斥的问题,但与之前不同的是,除了实现读写的互斥,我们还要实现读读的“不互斥”。

首先准备一个信号量 rw = 1 表示当前是否有进程在访问文件(注意一开始是没有这样的进程的,1 表示的不是进程数目,仅仅是使用互斥信号量时习惯上给定的初始值,这个看 wait 的代码就能理解了)。

在不考虑“读读不互斥”的情况下,我们的伪代码是这样的:

Writer(){               Reader(){
    while(1){             while(1){
        P(rw)                P(rw)
        写文件               读文件  
        V(rw)                V(rw)
    }                     }
}                      }

这个代码可以实现读写互斥,但显然无法实现“读读不互斥”,因为每个读进程之间也会受到 rw 的影响,使得最后只能有一个读进程访问文件。于是我们考虑从读进程入手,做一些改进。这里读和读不能同时进行的本质原因在于,所有的读进程都会经历“检查并上锁”这个步骤,而一个读进程进入后就会马上检查并上锁,导致另一个也想要进入的读进程被阻塞,所以我们考虑:能不能不要让所有的读进程都经历“检查并上锁”这一步骤?也就是说,某些进程可以跳过 P 操作,直接进入临界区,这样一来,这些进程就不存在在 P 操作这里被阻塞的可能性。

什么样的进程可以跳过 P 操作呢?就是中间的那些读进程。因为一开始肯定要有读进程上锁、最后肯定要有读进程解锁,所以上锁和解锁的任务交付给第一个和最后一个进程,而中间的那些进程来去自如,只需要负责读文件,不需要参与上锁和解锁。为了区分读进程的次序,我们准备一个 count = 0 的变量,它表示的是当前有多少个读进程正在访问文件。然后在读文件的前后,我们分别对 count 进行加一和减一的操作,每次读文件开始之前 count 会加一,所以在此之前如果变量为 0 ,说明当前读进程是第一个读进程;同理,每次读文件之后 count 会减一,所以在此之后如果变量为 0 ,说明当前读进程是最后一个读进程;

此时伪代码如下:

Reader(){
    while(1){
        if(count==0)
            P(rw)
        count++
        读文件
        count--
        if(count==0)
            V(rw)
    }
}

但是这样会产生一些问题。比方 1 号读进程首先进入并上锁,然后在 P 操作之后、count 加一变成 1 之前,进程切换到 2 号读进程,那么 2 号读进程就会卡在 P 操作这个地方,陷入阻塞,显然这时候无法实现我们想要的“读读不互斥”;又比方说,1 号读进程在 count 减一变成 0 之后、释放 rw 之前,进程切换到了 2 号读进程,那么 2 号同样又会被卡在 P 操作这里。所以我们还要进行改进。

问题其实就出在,对 count 的检查和赋值不是一个原子操作,这导致的结果是,如果在检查和赋值之间的空隙,进程发生切换,则必然会使得另一进程陷入阻塞。那么能不能让这两个操作一气呵成呢?事实上,可以把 count 当作是一个互斥访问的资源,对 count 的访问是互斥的,也就说明一个时间段内只能有一个读进程去访问它,即使这个过程中切换到了其它进程,那个进程也会被阻塞,从而保证只有一个进程可以访问 count,而这个访问就是检查和赋值,这种情况下,检查和赋值一定是不会被中断的。

准备一个互斥信号量 mutex = 1 表示对 count 的互斥访问,将检查和赋值封装在一个 PV 操作里。伪代码如下:

Reader(){
    while(1){
        P(mutex)
        if(count==0)
            P(rw)
        count++
        V(mutex)
        读文件
        
        P(mutex)
        count--
        if(count==0)
            V(rw)
        V(mutex)
    }
}

现在我们再来跑一下过程。假设还是 1 号读进程运行到 P 操作的时候,进程切换到了 2 号读进程,那么由于互斥信号量 mutex 的存在,导致 2 号进程进入了 mutex 对应的阻塞队列 —— 是的,这时候看起来 2 号进程还是被阻塞了,不过我们要关注到的是,阻塞它的信号量是 mutex,不是 rw。这意味着,在进程重新切换回 1 号进程的时候,1 号进程一旦执行了 V(mutex),就可以将 2 号进程唤醒并送到就绪队列了。也就是说,尽管 2 号进程还是经历了“阻塞”这个过程,但是这个过程只是为了确保 1 号进程检查和上锁两个操作的原子性,一旦操作完成,2 号进程马上就被唤醒了。而之前那种情况不同,之前的情况是,导致 2 号进程被阻塞的是信号量 rw,除非 1 号进程读完后释放,否则 2 号进程会一直处于阻塞状态。这就是说,2 号进程永远不可能与 1 号进程同时读文件,但是改进后是可以的。

但随之而来的又是另一个问题, “读写不公平”。也就是说,这样的代码本质上是对读进程更有利的。

因为对读进程来说,一旦第一个读进程进来了,中间即使穿插再多的读进程,也都是允许的,他们根本不受到 rw 这个“锁”的限制;而对于写进程,它的运气就没这么好了,写进程只要想进来,就必须通过 rw 这个“锁”,而这个“锁” 实际上又掌握在最后一个读进程手里 —— 这就是说,万一读进程源源不断进来,始终轮不到最后一个读进程解锁,那么写进程就只能陷入无尽的等待了。

既然 rw 这把锁无法做到公正对待每一个进程,那我们就考虑在外层加一把“更大、更公正的锁”。也就是说,所有的进程,无论读还是写,无一例外必须通过这把“锁”的检查。为此,我们准备一个新的互斥信号量 w = 1,并将 Writer 和 Reader 的一些关键操作封装在 w 的一对 PV 操作里。此时,伪代码如下:

我们来跑一下流程。假设首先来到 1 号读进程,那么它就会执行 P 操作上锁,这个过程中即使有写进程想进来,也会被送到 w 对应的阻塞队列。在 1 号读进程执行到 V 操作之后,写进程才会被唤醒并送到就绪队列,之后就轮到写进程执行了,而写进程虽然通过第一个 P 操作,但是被卡在了第二个 P 操作(读进程尚未释放 rw),所以他来到了 rw 对应的阻塞队列。

注意!重点来了,如果这时候 2 号读进程也想要访问文件,那么在以前,它是不需要通过任何检查就可以直接来读文件的,并且直到 2 号读进程释放 rw 之后,写进程才能真正来执行写文件的操作。但是现在由于我们加了一把“更大的锁”,导致 2 号进程也必须先通过 w 的检查,而由于写进程抢先在他之前上了锁,所以 2 号读进程被送到了 w 对应的阻塞队列。也就是说,现在的情况是:写进程等着 1 号读进程释放 rw,而 2 号读进程等着写进程释放 w,1 号读进程是让一切正常进行下去的关键。在处理机又来到 1 号读进程并执行 V(rw) 之后,写进程从 rw 的阻塞队列被唤醒,继续往下执行写文件的操作。而在写进程真正执行完之后,w 才能得到释放,由此又唤醒了 w 阻塞队列中的 2 号读进程,2 号读进程来到处理机运行。

如果换一种情况,是按照 写者 — 读者 — 写者的顺序,那么由于读者在第二个写者之前,所以是读者作为阻塞队列队头,第二个写者则次之,在后续执行过程中,根据队列“先进先出”的原则,也会是读者先于第二个写者访问文件。

也就是说,实际上谁先到、谁就在后续过程中先被执行(而不是像之前那种情况,无论写进程先还是后,读进程都可以“无视规则”抢先一步执行)。由此,我们就实现了“读写公平”。

5. 哲学家就餐问题

最后我们再来看哲学家就餐问题。这个问题描述的是:一张圆桌,五个哲学家,五支筷子(每两个哲学家中间会有一支筷子),哲学家要么思考,要么吃饭,吃饭前会拿起左右两边的筷子,吃饭后会放下筷子。如果筷子被其它哲学家拿走,则自己需要等待。我们的目的很简单:保证所有哲学家都有机会吃上饭,不能让一个或者多个哲学家始终无法吃饭

首先,五个哲学家对应了五个进程,然后在同一个时间段内,对于同一支筷子,只能有一个哲学家去使用它,所以筷子是一种临界资源,我们用互斥信号量 chopstick = 1 表示。鉴于这里有五支筷子,所以我们准备一个互斥信号量数组 chopstick[5] = {1,1,1,1,1}。另外,由于任何一个哲学家都只可能拿离自己最近的左右筷子,所以为了加以区分,我们需要给哲学家和筷子进行编号。对于哲学家,从 0 到 4 进行编号,由于哲学家按照圆桌首尾连接,所以某个哲学家左右两边的筷子编号与自己本身的编号相关。以哲学家 i 为例,它左边的筷子编号是 i。右边则是 (i+1)%5,如下图所示:

对每一个哲学家进程来说,它都只能拿起左右两边的筷子,并且一定是吃饭前拿筷子,吃饭后放下筷子,所以初步的伪代码是这样的(这里忽略思考的过程):

Pi(){
    while(1){
        P(chopstick[i])
        P(chopstick[(i+1)%5])
        eat()
        V(chopstick[i])
        V(chopstick[(i+1)%5])
    }
}

如果哲学家 0 号拿起左右筷子后,进程切换到哲学家 1 号,那么哲学家 1 号是会被阻塞的,所以这样写可以保证相邻的哲学家中有一个可以吃饭。但是,如果是拿起左筷子,之后进程切换到 1 号,那么 1 号也会拿起自己的左筷子,以此类推,直到 4 号也拿起自己的左筷子。接着,进程来到 0 号,这时候,0 号会发现自己已经没有右筷子可以拿了(作为 1 号的左筷子),于是 0 号被阻塞;同理,1 号也没有右筷子,所以他也被阻塞…以此类推,由于所有的哲学家都只有左筷子,他们的右筷子都在其他人手里,这导致了所有的哲学家都被阻塞,等待着另一个哲学家释放筷子。但实际上,没有任何哲学家能够吃饭,因此没有人可以释放筷子,这使得这些哲学家都陷入无限的等待中,造成“死锁”的发生。

解决这个问题有三个方法。

(1)实现原子操作

很容易想到的是,这里的一个问题在于,拿起左筷子和拿起右筷子并不是一个原子操作,如果在这之间发生了进程切换,那么就可能会像上面那样导致“死锁”的发生。所以我们设想能否将这两个操作一气呵成完成。按照前面问题的思路,第一种做法就是准备一个互斥信号量 mutex = 1 ,并把拿筷子的操作封装在一个 PV 操作里。代码如下:

Pi(){
    while(1){
        P(mutex)
        P(chopstick[i])
        P(chopstick[(i+1)%5])
        V(mutex)
        eat()
        V(chopstick[i])
        V(chopstick[(i+1)%5])
    }
}

这样一来,在 0 号哲学家拿起左筷子之后,即使发生进程切换,来到 1 号进程,1 号进程也会被卡在 mutex 的 P 操作这里。被送往阻塞队列,其它进程也同理。所以最后又来到了 0 号进程,0 号进程顺利拿起了右筷子,之后释放阻塞队列队头的 1 号进程,自己开始吃饭。这种做法保证了有一个哲学家是可以吃饭的,不存在“所有哲学家都无法吃饭”的情况。

另外,这里涉及到了一个进程需要一次性两个资源才能完成任务的问题,这时候也可以考虑使用我们之前提到的 AND 信号量集机制。我们回顾一下,AND 信号量集机制的 P 操作是一个相对苛刻的操作,要求一个进程要么拿到全部资源,要么一个资源也拿不到,所以这里可以做到的是:对于初始的那个 0 号进程,他在拿筷子的时候要么左右筷子都拿到,要么一支筷子都拿不到。由于一开始筷子数量足够,所以它在一开始就可以一次性拿到左右筷子。同理,在释放筷子的时候,也是一次性释放两支筷子。

代码如下:

Pi(){
    while(1){
        Swait(chopstick[(i+1)%5],chopstick[i]);
        eat()
        Ssignal(chopstick[(i+1)%5],chopstick[i]);
    }
}

因此,我们同样可以保证有一个哲学家是可以吃饭的,不存在“所有哲学家都无法吃饭”的情况。

(2)只有四个人可以参与这个过程

我们也可以从另一个角度考虑,之前的情况是五个哲学家,五支筷子,所以很容易出现谁也无法吃饭的情况,但是如果我们规定整个过程最多只有四个哲学家参与,那么即使这四个哲学家每个人都拿走了一支筷子,也还剩下一支筷子可以分配给某个哲学家。换句话说,这样做,我们同样可以让至少一个哲学家吃到饭。

问题在于如何限定“只有最多四个人可以参与这个过程”呢?我们可以准备一个互斥信号量 count,但是这个信号量初值不再是 1 ,而是 4,表示最多允许四个哲学家参与过程。当 count 减少到 -1 的时候,就不能再让哲学家进来了,因此可以保证最多只有四个哲学家。代码如下:

Pi(){
    while(1){
        P(count)
        P(chopstick[i])
        P(chopstick[(i+1)%5])
        eat()
        V(chopstick[i])
        V(chopstick[(i+1)%5])
        V(count)
    }
}

我们再来演示前面发生“死锁”的过程。假如一开始还是从 0 号进程开始,在他拿到左筷子之后,进程切换到 1 号进程,由于 count 数量充足,所以它不会阻塞,而是同样拿到了左筷子…以此类推,到了 4 号哲学家的时候,由于 count = -1<0,所以它此时是无法进来的。所以有一支筷子在一开始谁也没拿到,就是 4 号哲学家左边的筷子。而在稍后进程轮到 3 号哲学家的时候,它是可以拿到这支筷子然后去吃饭的。

这只是其中一种情况,但即便是其它情况,也能保证剩下一支暂时没被用到的筷子,而这支筷子也一定会在最后被某个进程拿走。因此得以保证总会存在至少一个进程可以吃到饭。

(3)奇数拿左边,偶数拿右边

还可以考虑对拿筷子的优先顺序进行调整。规定对于奇数哲学家,总是先拿左筷子再拿右筷子;对于偶数哲学家,总是先拿右筷子再拿左筷子。那么 0 号哲学家和 1 号哲学家就会争夺 1 号筷子,而 2 号哲学家和 3 号哲学家就会争夺 3 号筷子。如图所示:

伪代码如下:

Pi(){
    while(1)
	{
		if(i%2 == 0) // 偶数哲学家,先右后左。
		{
			P(chopstick[(i + 1)%5]) ;
			P(chopstick[i]) ;
			eat();
			V(chopstick[(i + 1)%5]) ;
			V(chopstick[i]) ;
		}
		else   //奇数哲学家,先左后右。
		{
			P(chopstick[i]) ;
			P(chopstick[(i + 1)%5]) ;
			eat();
			V(chopstick[i]) ;
			V(chopstick[(i + 1)%5]) ;
		}
	}
}

假如一开始还是从 0 号进程开始,很显然 0 号先拿到 1 号筷子,所以在之后切换进程的时候,1 号进程就会直接被阻塞。接着来到 2 号进程,显然他先拿到 3 号筷子,所以之后轮到 3 号进程的时候,3 号进程直接被阻塞。现在考虑轮到 4 号进程,它优先拿到右边的 0 号筷子,之后进程又切换到其它地方。但是,由于先前 3 号进程已经被阻塞,所以在再次轮到 4 号进程的时候,并没有人和他一起争夺 4 号筷子,换言之,4 号进程可以拿到 4 号筷子,再加上之前优先拿到的 0 号筷子,4 号进程现在就可以吃饭了。

值得提醒的是,这仍然只是其中一种情况,类似的排列组合有很多,但是无论是哪一种,在一对进程的争抢中必然有一个进程首先被送到阻塞队列,“被淘汰出局”,因此这个“被淘汰的”进程很难再去影响其它进程,相当于间接提高了其它进程拿到筷子的可能性。就像我们上面的例子一样,一下子“淘汰了” 1 号和 3 号两个进程,并且这两个进程当时并没有带着筷子进入阻塞队列,所以对于其它进程 2 号、4 号、 0 号来说,再次拿到一支筷子的可能性就大大提高了。所以,我们还是能够达到最初的目的,也就是至少让一个哲学家吃上饭。


操作系统系列学习笔记:

操作系统学习笔记-1:基础概念

操作系统学习笔记-2:体系结构和运行机制

操作系统学习笔记-3:初识进程和进程控制

操作系统学习笔记-4:进程同步与进程互斥(一)

操作系统学习笔记-5:进程同步与进程互斥(二):信号量机制

操作系统学习笔记-6:进程同步与进程互斥(三):经典问题

操作系统学习笔记-7:进程通信

操作系统学习笔记-8:线程

操作系统学习笔记-9:调度