码农翻身讲计算机基础：并发，同步与信号量

微信公众号【黄小斜】大厂程序员，互联网行业新知，终身学习践行者。关注后回复「Java」、「Python」、「C++」、「大数据」、「机器学习」、「算法」、「AI」、「Android」、「前端」、「iOS」、「考研」、「BAT」、「校招」、「笔试」、「面试」、「面经」、「计算机基础」、「LeetCode」 等关键字可以获取对应的免费学习资料。 

                     ​

那些烦人的同步和互斥问题

原创： 刘欣 码农翻身 2016-10-31

真正的知识是深入浅出的，码农翻身” 公共号将苦涩难懂的计算机知识，用形象有趣的生活中实例呈现给我们，让我们更好地理解。

本文源地址：那些烦人的同步和互斥问题

1、批处理和脱机打印

打印机程序，准确的说是打印机进程，在这个批处理系统中生活得非常自在，它所在的机器叫做IBM1401，除了打印之外什么也不干，每天大部分时间都是歇着。

这个系统还有两台机器，一台还是IBM1401，它专门收集程序员写出来的穿孔卡片，然后转成磁带。  然后，操作员把磁带输入到IBM7094这个昂贵又强大的计算机上执行，执行结果也会输出到磁带上。 最后磁带被拿到1401上进行打印， 这叫做脱机打印（不和7094相连接）。如下图：

图一、脱机打印

在没有磁带来的时候，打印机程序无所事事，这就是脱机打印的好处。更大的好处是，磁带上需要打印的东西都是顺序的，一个接一个打印就可以了，完全没有冲突的问题。这是没办法的事情，那时候的计算机，尤其是IBM 7094太过昂贵，要充分的利用它的每一分每一秒，然后就想出了这样一个收集程序，然后成批处理的点子。 

2、假脱机打印

随着计算机系统的发展，打印程序的好日子很快就结束了，电脑越来越便宜，最后每个人的桌子上都有一台电脑了。个人电脑的计算能力更是强大的惊人，打印程序也被集成进了个人电脑里，和其他各种各样的程序生活在一起。打印的需求仍然很强烈，像Word、WPS、Excel 、 IE、Chrome...这些程序时不时都要打印，这时候冲突就会产生。 因为只有一个打印机，到底先打印谁的文档就是个大问题。最后操作系统老大想了个办法，专门开辟了一块空间，谁要想打印的话就按照先来后到的次序排队放在那，原来的打印进程变成了一个打印守护进程，会周期性的检查是否有文件打印，如果有则取出队伍排头的，打印出来，然后删除队列中文件。打印进程觉得这和原来的脱机打印很像，只不过用一个队列替换了原来的磁带，所以就叫做假脱机打印。

图二、假脱机打印

3、冲突

但是这个队列可不是原来的磁带了，它完全是个动态变化的东西，试运行还不到20秒，冲突就出现了。 

WPS气冲冲的来着打印机进程：“打印机，你怎么搞的？我的放假通知.wps 为什么没有打印？” 

打印机：“我没看到什么放假通知.wps啊！”

WPS：“我明明放在了编号为3的槽里，怎么可能没有了？”

在操作系统老大的协助下，大家查了半天，才知道是Word引起的：

当时Word 插了一脚，也进来打印，读到了in = 3，就是说队列中编号为3的槽是空着的，他把3这个值放到了自己的局部变量free_slot中，这时候发生了一次时钟中断，操作系统老大认为Word已经运行了足够长的时间，决定切换到WPS进程。 

WPS也读到了in = 3，把3 也存到自己的局部变量free_slot中，现在Word和WPS都认为下一个空的槽是3！

WPS接着干活，他把文件放到了第3号槽里，并且把in 改为4，然后离开了。接下来又轮到Word运行了，它发现free_slot 为3，就把文件也放到了第3号槽里，把free_slot 加1，得到4，存入in 中。可怜的WPS，他的文件被覆盖掉了。

但是打印机程序啥也察觉不出来，照样打印不误。  

图三、冲突

4、临界区

很明显，Word和WPS 这两个进程甚至多个进程在读写in这个共享变量的时候，最后的结果严重依赖于进程运行的精确次序，这次是WPS的文件被覆盖掉了，下次可能就是Word了。 
这种对共享变量，共享内存，共享资源进行访问的程序片段叫做临界区。代码在进入临界区之前一定要做好同步或者互斥的操作。
WPS说：“老大，当时你切换Word的时候是不是发生了一次时钟中断 ？”
操作系统：“是啊，有了时钟中断我才能计算时间，然后做进程切换啊！”
“那在访问这个in共享变量的时候，我们自己能不能把这个中断给屏蔽？这样就不会有进程切换，肯定没问题了。” Word问道。
“你想的美，时钟中断是最基本的东西，我把这个权限给了你们应用程序，到时候那个家伙屏蔽以后忘记开中断，我们整个系统就要完蛋了！” 操作系统狠狠的瞪了Word 一眼，Word赶紧噤声。 
“不过我听说有些机器提供了一个特别的指令，这个指令能检查并且设置内存的值，而不会被打断，叫做TestAndSet，如果用C语言描述的话，类似这样：”

bool TestAndSet(bool *lock){
  bool rv = *lock;
  *lock = true;
  return tv;      
}

“需要注意的是，这个函数中的三条指令是“原子”执行的，也就是说不会被打断。你们要是想用的话可以这样用：”

bool lock = false;
while(TestAndSet(&lock)){
  ;//什么也不做  
}

临界区;
lock = false;
剩余区;

WPS说：“看起来有点复杂，让我想想啊，我和Word 的临界区代码，就是‘访问in变量，放入待打印文件，然后把in 加1’ 。那在进入临界区之前，我们俩都会调用TestAndSet。如果是我先调用，lock会被置为true，函数就会返回false。我就跳出了循环，可以进行后续临界区操作了，而Word 在调用 TestAndSet的时候，函数一直返回true，他只好不停的在这里循环了。”
“是啊！”，Word 接着说，“我会不停的循环，直到WPS 离开临界区，然后把lock置为false。 ”
“这个方法看起来很简单啊，只要一个变量加上一个函数就能让我和Word 进行互斥操作。”
操作系统说： “是的，实现了你们两个的互斥，但是并不是所有的机器都会提供这样的指令，所以也不通用。”

5、生产者-消费者

打印机进程说：“你们讨论了半天，只是解决了两个进程往队列里放文件的冲突问题，现在也得考虑考虑我了。”
“有你啥事？”，Word和WPS 都不以为然。
“你们想想，那个打印队列对5个‘槽’，要是满了就没法往里边放了，你们都得等；要是空了，我就得等你们往里边放东西，所以咱们之间是不是也得同步？”
“这就是所谓的生产者和消费者问题，也是个老大难问题了”，老大总结道。 
“那用刚才那个锁好像不行啊，它能搞定互斥，但是做多个进程的同步就有点力不从心了。”
操作系统老大说：“听说荷兰有个叫Dijkstra的，发明了一个信号量（semaphore）的东西，能解决这个问题。”

图四、科学家Dijkstra.

“信号量是什么鬼？信号灯吗？ ”
"所谓信号量，说白了其实就是一个整数，基于这个整数有两个操作：wait 和 signa。”

int s;
wait(s){
  while(s <= 0){
        ;//什么也不做
    }  
    s--;
}        

signal(s){
  s++;  
}

“这....这....这是啥玩意儿，这么简单，能解决啥问题？再说了你看看这s++、s--和我们队列中的in、out不是一样吗？在多进程切换下自身正确性都难保，还能解决别人的问题？” ，WPS吃惊的问。
“WPS 问的好啊，说明他思考了，实际上这个东西必须得我出马来实现”，操作系统老大说，“ 我会在内核实现wait 和signal，让你们调用，比如我在做s++、s-- 时，我可以屏蔽中断。”
 Word说：“这个简单的小东西有点意思，比如我们俩可以用它做互斥：”

int lock = 1;
wait(lock);
临界区;
signal(lock);
剩余区;

打印进程说：“既然信号量是个整数，也许可以解决我们消费者-生产者直接的同步问题。”

int lock = 1;
int empty = 5;
int full = 0;

生产者:
while(true){
  //如果empty的值小于等于0，生产者只好等待
  wait(empty);
  //加锁（因为要操作队列，和其它生产者互斥）
  wait(lock);
  把新产生的文件加入队列;
  //释放锁
  signal(lock);
  //通知消费者队列中已经产生了新的文件
  signal(full);     
}

消费者:
while(true){
  wait(full);
  wait(lock);
  把队列头的文件打印，删除;
  signal(lock);
  signal(empty);
}

Word说:“我的天，真是复杂啊，容我想想，我和WPS都是生产者。假设我们俩都开始执行生产者代码，先去wait(empty)，发现没有问题，因为empty的初始值为5。接下来都去执行wait(lock)，这时候就看谁先抢到了。如果我先抢到，我就可以往队列里加文件，然后释放锁，WPS就可以接着放文件了。最后我还要把full这个值加一，目的是打印机进程可能在等待。恩，看起来不错！”
操作系统老大说：“是啊！在多进程下，由于进程的执行随时都有可能被打断，还要保证正确性，不能出一点闪失。这对程序员的挑战很大，出现了疏漏，很难定位。”
打印进程说：“老大，我注意到wait函数中，如果s 的值 为0或小于0 ，那个while 循环会一直执行，CPU岂不是一直在忙等？”
“确实是这样，我们改进下，让忙等的进程进入休眠吧，很明显，这件事还得我做啊”， 操作系统说道。

//把整数型信号量封装成一个结构体
typedef struct{
  int value;
  struct process *list;//process进程就绪队列
}semaphore;

wait(semaphore *s){
  s->value--;
  if(s->value < 0){
    把当前进程加到s->list中;
    block();//把进程休眠，放弃cpu
  }
}

signal(semaphore *s){
  s->value++;
  if(s->value <= 0){
    从s->list中取出一个进程p
    wakup(p);//唤醒进程p
  }
}

WPS说:“唉，真是好复杂！不过我想起一个问题，这些wait、signal 能用到我们内部的线程的同步上吗？”
“当然可以，概念上是一致的，都是访问共享资源的程序，需要做同步和互斥操作，可能表现形式不同。”
“难道那些程序员们真的要使用这些wait、signal 编程吗？多容易出错啊！”
“一般来说，程序员们所使用的工具和平台会做抽象和封装，例如在Java JDK中，已经对线程的同步做了封装了，对于生产者-消费者问题，可以直接使用BlockingQueue。非常简单，完全不用你去考虑这些wait、signal、full、empty。”

//建立一个队列，其中队列中已经对wait和signal操作做了封装
BlockingQueue queues = new LinkedBlockingQueue(10);

生产者:
//如果队列满，线程自动阻塞，直到有空闲位置
queues.put(xxx);

消费者:
//如果队列空，线程自动阻塞，直到有数据到来
queues.take();

WPS说：“果然是抽象大法好，这多简单啊。”

操作系统说：“是啊！无论是什么东西，抽象以后用起来好多了。但是还是要了解底层，这样出现了类似于BlockingQueue这样的新概念， 你能迅速搞明白。”

（完）

如果说要从Java 世界中找一个并发编程的大牛， 我想这个人非Doug Lea莫属， 从JDK 1.5开始， Java 引入了一个非常著名的线程并发库java.util.concurrent ， 由于其良好的抽象， 这个库极大的降低了并发编程的难度， 其作者就是并发编程的权威Doug Lea， 他是纽约州立大学Oswego分校计算机科学系教授， JCP（Java Community Process）执行委员会成员，JSR166（并发编程）的主席 ， 文中的小李就是向Doug Lea致敬。