"通信"是一个广义的概念, 不仅限于计算机网络通信, 任何抽象或者具体的对象间的交互行为, 都是一种通信. 对象间一旦进行通信, 便有可靠通信的需求. 可靠通信至少包括三项要求:
- 不丢包
- 不重复
- 完整性(原子性)
为了达到这三项要求, 对应有三条定理(可靠通信三原则):
- 定理一(重传定理): 确认和重传是解决丢包问题的唯一正确方法
- 定理二(去重定理): 排队(串行化)是解决去重问题的唯一正确方法
- 定理三(原子定理): 单点标记或者循环自校验是实现完整性(原子性)的唯一正确方法
有些同学可能对排队理论有怀疑, 表示搞一个全局位图(标记集合)也能解决去重问题. 如果深究, 判断标记和修改标记是独立的两步操作, 这两步操作就遇到去重问题, 也即, 对标记集合的操作本身也需要排队. 当然, CAS 是一种解决方案, 但 CAS 的实现内部本质也是排队.
Continue reading »