同步

我先说说同步的概念。
同步的前提是并行，或者同时或者并发。没有并行，不会涉及到同步。有时候，我们把同步看作一个名词而不是动词，那么导致同步的那种动作或者方式叫做同步化。在我这儿，同步或者是名词或者是动词，依赖于上下文。
我举例子来说明同步是什么，然后再说我们如何实现同步。
两个人，A和B，A邀请B去帮他到d地去搬一块大石头，石头很大，一个人搬不动。B同意了。B告诉A说他不知道d地在哪儿，让A领着他去。让A第二天早晨到 B家门口等着B出来，然后一起去。A走路的速率比较高，而B恰恰相反。从B家门口到d地有两个拐弯，用b和c表示罢。为了叙述方便，我把B家门口用a表示。现在总结一下涉及的对象。a，b，c，d四个地点。A，B两个人。A首先到达a地，一直等到B也出现在a地。由于A走的快，所以A先到达b地，然后等待。因为如果不等待B也到达b地，B就到达不了d地了。我们就说：a，b，c，d是A，B的同步点。A和B是两个Actor，如果他们没有同步点，那么他们就没有什么关系。
当然，上面只是一个例子。我们现在要推广一下同步点的概念。从上面的描述看出，同步点是Actor共同到达的点。其实同步点的概念比这个广一些。想象一下接力赛，交换接力棒的地方也是同步点。互斥也是一种同步，它的等待条件就是没有任何别的actor到达。从一个Actor的角度来看，所谓同步点就是一个要等待某些条件满足的那个点。之所以采用同步点的方式而不是时时同步——时时同步可以想象两个恋人压马路，他们总是时时同步 ——是因为：一、时时同步的代价太高，二、时时同步不可能真正实现，所谓的时时同步只是同步点设计的比较致密的同步点同步而已。
再重复一次：同步点就是等待某些条件满足的点。这里的某些条件就是某些actor进入某种状态。
那现在的问题是：怎么个等法？怎么判断某些条件已经满足了？简单直觉的想法就是：不断的查询actor的状态，直到它满足为止。这个等待过程叫做阻塞（Block）。这是几乎所有别的办法的基础。有时候，我们讨厌阻塞，回想一下A和B去搬那块石头，A不断的等B使得A的心情非常郁闷。所以A采用了一个非常聪明的办法，在等待B的时候玩玩手机上的俄罗斯方块。B来到的时候，对着A大叫一声，打断A的游戏，于是又开始走了。当然A可能非常聪明，并不立即停止自己的游戏，尤其是正好到了紧要关头，他让B先等一会儿，等游戏结束了再一起走。或者A并不等着B喊一嗓子，而是玩一会儿，就看看B是不是到了，如果没有再玩一回，如果到了就继续。这个似乎没有喊一嗓子那么好，因为毕竟我们可能看过好多回，而且，经常是对方到了跟前一会儿以后了才发现。不过无论如何，我们把这种等待的方法叫做非阻塞，说穿了就是我并不在这儿傻等，我干会别的活，等到条件满足了，对方通知一下我就行了。有时候，我们把这种方式叫做异步方式。实际上，根据最后是不是等待B的通知，我们可以更细的区分成两种，不等待B通知的那种叫做非阻塞，而等待B通知的那种叫做异步（Note：借自集成电路的两个术语描述这两种方式：电平触发方式和边沿触发方式）。异步方式看起来比非阻塞方式更讨人喜欢一些，跟阻塞方式相比就更讨人喜欢了。
但是，上面的描述都是非计算机术语的，这让人觉得不够安全，觉得很难落实到计算机环境中。毕竟不断地查看B是不是走到跟前了，或者B走到跟前打断A玩游戏，对人来说都不是问题，可是计算机也没有眼睛，也不会大喊一声啊。
首先提一个概念，叫信号灯（或者更计算机化的叫做信号量，Semaphore）。它其实就是actor状态的外在表现。计算机没有眼睛，不能看见是否有人靠近，可是，我们可以让那个人来的时候，修改这个Semaphore的值，如果发现这个值改变了，就证明人已经来了。就像如此：

wait until semaphore is fire;
process ....

while (semaphore != fire)
    ;
process ....

实际上，有了信号灯这样的东西，各个actor之间就可以进行各种方式的通信了。不过需要注意的是，信号灯对于互相需要同步的actor来说，都要是可以访问的。也就是说，这些actor们都可以读写它。
有了信号灯这个概念，对于同步也就没有什么太多的问题了。但是信号灯是一个非常初级的同步概念，为了实现更复杂的同步，需要付出很多脑力才能设计出比较合用的信号灯通信机制，而且容易出错，所以，人们在信号灯的基础上，开发了很多高级原语，我就不描述了。
信号灯其实是给了actor一个表达自己状态，或者检查别的actor状态的一个机制。有时候我们把信号灯叫做事件或者有更多的名称比如Mutex什么的。
但是刚才有个问题没有深入讨论，那就是打断。还记得B打断A玩俄罗斯方块吧。对于俄罗斯方块，打断也就算了，如果A正在干一些比较重要的事情，这时候被打断了呢？如果没有什么好的处理措施，轻则白做了（早知道白做，还不如不做呢，阻塞着等就行了，毕竟非阻塞还浪费体力一些），重则逻辑错误了，比如：正在做氰化钾试验，结果突然被打断，氰化钾的瓶盖没有盖上，完了，出事了：）。好在计算机不做氰化钾试验，不过它似乎经常打开文件啥的，这个也不好啊。影响后面的动作了。所以，打断的时候，并不是毛手毛脚的去接手新的活，而是把现在的活的现场保留下来，再去干新的活。等到新活处理完了，回过头来继续原来的。
幸好，操作系统已经为我们提供了保存现场，以及以后恢复现场的那种机制了。不过，它并不是慈善家，它的目的也是盈利，所以我们要付出代价才能获得它提供的现场管理的服务。我们不能自己去搞定那些看起来非常自然的打断机制了，我们得缴纳线程税。
现在，按照现实，我提一下现在各种实现同步的现实机制。
低级的就是信号灯，在不同的os中名称各有不同，同时它们的可见范围（是全系统的进程可见？还是进程中的线程可见？）也各不相同。比如Windows系统的 Event，Semaphore，Mutex以及Linux下的高性能的futexes（fast userspace mutexes）。
高级一点的包括：最出名用的最广泛，限制最多，性能最低的是一个叫做select的机制。后来UNIX界发展出来poll机制，改进了select的监听数量，但别的都没有改变。后来有了改进它们的/dev/poll，kqueue，epoll，realtime signal，signal per fd，其中，kqueue以及/dev/poll是level trigger的，kqueue，epoll，realtime signal，signal per fd是edge trigger的。也就是说kqueue可以支持level和edge trigger。当然，还有发展了多少年雷声大雨点小的aio。Windows平台上包括Overlapped IO和IOCP。分别对应于level trigger和edge trigger，不过，IOCP会阻止（拒绝）某些请求，以保证线程数目的常量性。
最后，我们同步的对象也即线程，还有相关的线程调度机制，也在不断地发展也完善中。线程按照实现的方式分为核心级别和用户级别两种，它们的对应得叫做1:1和M:N两种。逻辑上，用户级线程性能高，核心级的线程对于block更容易处理。线程调度的机制现在比较高性能的就是Scheduler Activations模型了，它结合了核心和用户的优点。不过实现的似乎不是很多。顺便说一下，Windows下的线程调度似乎不是很稳定，受到运行时长和线程数目的影响，不知道什么原因。
关于同步，其实大头是各种高级的同步机制，高度的同步模型，但是由于我这是免费的，就不讨论那些了。