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

码农翻身 · 公众号 · 程序员架构 · 2016-10-31 19:55

正文

批处理和脱机打印

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

这个系统还有两台机器，一台还是IBM1401，它专门收集程序员写出来的穿孔卡片，然后转成磁带。

然后操作员把磁带输入到IBM7094这个昂贵又强大的计算机上执行，执行结果也会输出到磁带上。

最后磁带被拿到1401上进行打印，这叫做 脱机打印 （不和7094相连接）。

（点击看大图）

在没有磁带来的时候，打印机程序无所事事，这就是脱机打印的好处。

更大的好处是，磁带上需要打印的东西都是顺序的，一个接一个打印就可以了，完全没有冲突的问题。

这是没办法的事情，那时候的计算机，尤其是IBM 7094太过昂贵，要充分的利用它的每一分每一秒，然后就想出了这样一个收集程序，然后成批处理的点子。

假脱机打印

随着计算机系统的发展，打印程序的好日子很快就结束了，电脑越来越便宜，最后每个人的桌子上都有一台电脑了。

个人电脑的计算能力更是强大的惊人，打印程序也被集成进了个人电脑里，和其他各种各样的程序生活在一起。

打印的需求仍然很强烈，像Word, WPS, Excel ， IE, Chrome .... 这些程序时不时都要打印，这时候冲突就会产生，因为只有一个打印机，到底先打印谁的文档就是个大问题。

最后操作系统老大想了个办法，专门开辟了一块空间，谁要想打印的话就按照先来后到的次序排队放在那里，原来的打印进程变成了一个打印守护进程，会周期性的检查是否有文件打印，如果有则取出队伍排头的，打印出来，然后删除队列中文件。

打印进程觉得这和原来的脱机打印很像，只不过用一个队列替换了原来的磁带，所以就叫做 假脱机打印

冲突

但是这个队列可不是原来的磁带了，它完全是个动态变化的东西，试运行还不到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 ，他的文件被覆盖掉了。但是打印机程序啥也察觉不出来，照样打印不误。

临界区

很明显， Word 和 WPS 这两个进程甚至多个进程在读写in 这个共享变量的时候，最后的结果严重依赖于进程运行的精确次序，这次是WPS的文件被覆盖掉了，下次可能就是Word了。

这种对共享变量，共享内存，共享资源进行访问的程序片段叫做临界区 ，代码在进入临界区之前一定要做好同步或者互斥的操作。

WPS说： ”老大，当时你切换Word的时候是不是发生了一次时钟中断？“

操作系统： “是啊，有了时钟中断我才能计算时间，然后做进程切换啊”

“那在访问这个in共享变量的时候，我们自己能不能把这个中断给屏蔽？这样就不会有进程切换，肯定没问题了。” Word 问到。

“你想的美，时钟中断是最基本的东西，我把这个权限给了你们应用程序，到时候那个家伙屏蔽以后忘记开中断，我们整个系统就要完蛋了！ ” 操作系统狠狠的瞪了Word 一眼， Word赶紧噤声。

“不过我听说有些机器提供了一个特别的指令，这个指令能检查并且设置内存的值，而不会被打断，叫做TestAndSet，如果用C语言描述的话，类似这样：”

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

WPS说： “看起来有点复杂，让我想想啊，我和Word 的临界区代码就是‘访问in变量，放入待打印文件，然后把in 加1’ ，那在进入临界区之前，我们俩都会调用TestAndSet, 如果是我先调用， lock会被置为true, 函数就会返回false, 我就跳出了循环，可以进行后续临界区操作了，而Word 在调用 TestAndSet的时候，函数一直返回true, 他只好不停的在这里循环了。”

"是啊" Word 接着说， “我会不停的循环，直到WPS 离开临界区，然后把lock置为false ”

“这个方法看起来很简单啊，只要一个变量加上一个函数就能让我和Word 进行互斥操作。”

操作系统说： “是的，实现了你们两个的互斥，但是并不是所有的机器都会提供这样的指令，所以也不通用。”

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

正文

请到「今天看啥」查看全文