线程同步

PV 操作的提出是为了解决进程通信时的同步问题。什么是进程(线程)同步?先来看一个例子。

 void *thread1()
 {
     number++;
 }
  
 void *thread2()
 {
     number--;
 }

这是一个用来统计“2010 年上海世博会”园区内游客总数的 C 程序,用线程实现。thread1 放在入口的地方,进来一个人就把计数器加一,相当于记录进入园区的游客总数,而 thread2 就用来统计出园的人数。当然我们知道世博园区的入口和出口不止一个,因此程序中并发着很多个 thread1 和 thread2 这样的线程,我们就说这些线程是同步的。假设某天进园的游客有 70 万人次,而离开园区的有 10 万人,到晚上我们一看发现结果非但不是 60 万,而且还是一个随机的数。

错误的原因

为什么会这样?如果我们把 number++ 写成汇编代码,就会发现它们并不是原子操作,number++ 其实分了三步:

  1. 把 number 的值从内存读到寄存器
  2. 寄存器的值加一
  3. 把寄存器的内容写回 number

之所以要分成这三步,是因为变量都是保存在内存中的,而运算必须在寄存器中进行。

程序在执行时会发生线程的调度,因此很有可能 thread1 刚刚把 number 拿到寄存器,线程就下台了,这个时候 thread2 上台完成了自己操作,将 number 的值减了 1,等到 thread1 重新上台的时候就出错了,因为寄存器中的值已经被 thread2 改变了。

这是线程的情况,进程也是如此,当系统有多个进程想要进行通信的话,通常想到的办法就是用一些共享变量,就像我们在写程序的时候会通过全局变量来传值。但是当多个并发的进程同时访问同一块共享的区域时,就会引起竞争情况(race condition),就像桌上只有一个苹果,大家同时伸手去拿,谁会得到苹果是不确定的。这个时候就需要一种机制,来同步这些临界的资源。

如何解决

人们首先想到方法是用一把“锁”加在访问临界资源这道门前,如果进程想要修改共享变量的值,那么先要看一眼“锁”的情况,如果发现上了锁就要在门外等待。如果发现没锁,就可以进去了,为了防止其他进程再进来,要立刻上锁。那么“锁”是什么呢?有人可能会说,“锁”不就是一个布尔型的变量嘛?1 代表门上了锁,0 代表门没锁。不错,而且锁应该是一个公共的布尔变量,因为每个进程都需要能够看到“锁”,那么我们在做的一件事情就是用一个公共的变量去保护另一个公共的变量。想象下面这种场景,进程 a 跑到门前发现“门没锁”,进去以后还没来得及上锁,就被 CPU 赶下了台,进程 b 上台后看见门开着,也进去了……

每当事情变得不明朗的时候,往往需要个人英雄主义的诞生来解决所有问题,Dijkstra 就在这个时候出现了,那个和高爷爷并成为这个时代最伟大的计算机科学家的荷兰人(为什么又是荷兰人?),据说他在想出那个以他名字命名的最短路径算法时连笔都没动。

信号量和 PV 操作

1965 年,Dijkstra 提出了信号量(semaphore)和 PV 操作,所谓的PV来源于他的母语——荷兰语 Proberen 和 Verhogen,意思是测试和增加。后来美国人为了显示自己在科学上的强势地位,硬是把 PV 操作改名为了 Up/Down 操作。

PV 操作的具体解释是:当某个进程要对信号量进行访问之前需要先测试是否有可用的资源(信号量是否大于 0),如果有则将信号量的值减一(表示占用了资源),进程得以继续执行,如果信号量的值等于零,表示没有空闲的资源,进程则进入阻塞等待状态,直到其他进程唤醒它。当系统中有一个进程完成了操作以后,需要对已使用的资源进行释放(使信号量的值加一),并且唤醒处于等待资源状态的进程,V 操作相当于向系统广播了一条“目前系统中又有空闲资源可供使用”的消息。通常情况下信号量是一个大于等于零的整数。

听起来很复杂,思想其实很简单,原来之所以会发生冲突,是因为所有进程总是一起涌向通往临界资源的大门,解决的方法就是让大家排队,然后凭票入场。

互斥锁

当信号量只有两个值(0 和 1)的时候,就“退化”成为了互斥锁(mutex),互斥锁能够很好地解决世博园区人数统计问题。如果把“进门的权利”看做一种资源的话(票),那么当互斥锁的值为1时就表示“有票”,通过P操作进行检查,如果有系统中此时有一张票,则进程取走通行证进入临界区域,此时票的数量变成 0;否则的话阻塞等待。当进程访问完毕时,通过 V 操作告诉系统,现在又有一张票了!

 void *thread1()
 {
     P();
     number++;
     V();
 }  
  
 void *thread2()
 {
     P();
     number--;
     V();
 }

经典问题

关于信号量的问题,有很多经典的例子,比如吸烟者问题,睡眠理发师问题,生产者-消费者问题,读者-写者问题等等,都可以通过 PV 操作来解决。

信号量机制不能解决的是“死锁”(deadlock)问题,一个典型的例子就是哲学家聚餐问题(该死的哲学家们喜欢边吃饭边想问题,而且喜欢共用餐具,结果产生了死锁)。这个模型提出后没多久,荷兰大叔就抛出了相应的解决方案,即同样著名的“银行家算法”。



Published

29 October 2010

Tags