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

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， 如果用 46 32676 46 15287 0 0 3538 0 0:00:09 0:00:04 0:00:05 3538C语言描述的话，类似这样：”

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

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 和 signal”

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

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

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

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

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

你看到的只是冰山一角， 更多精彩文章，尽在“码农翻身” 微信公众号， 回复消息"m"或"目录" 查看更多文章
有心得想和大家分享？ 欢迎投稿 ！ 我的联系方式：微信：liuxinlehan  QQ: 3340792577

公众号：码农翻身“码农翻身”公众号由工作15年的前IBM架构师创建，分享编程和职场的经验教训。

掘金是一个高质量的技术社区，从 Swift 到 React Native，性能优化到开源类库，让你不错过互联网开发的每一个技术干货。长按图片二维码识别或者各大应用市场搜索「掘金」，技术干货尽在掌握中。