[Day 4] lock-free and CAS

前言

昨天聊到原子操作时提到了2个名词, 有些人可能不熟, 会在今天简单说明。明天会有相应的实作。

lock-free 的意义

是一种分类, 在描述某类演算法在处理 multi-Threading 的问题时, 没有为了保证执行顺序令所有 thread 在有限时间内停滞。

换句话说 :

当某个 multi-Threading data structure , 用一用会为了保证执行顺序卡住, 那他就不是 lock-free。

再换句话说 :

当 multi-Thread 对某个 lock-free data structure 操作, 无论任何原因, 最後一定有至少一条 thread 有进度。

为甚麽要 lock-free

原因很多举以下两个

• 避免 thread 被阻塞，无法实时响应。
• dead lock。

这两个原因对非同步框架而言都是需要被克服的。

甚麽是 CAS (compare and swap)

维基百科是这样说的

比较并交换(compare and swap, CAS)，是原子操作的一种，可用於在多执行绪编程中实现不被打断的数据交换操作，从而避免多执行绪同时改写某一数据时由於执行顺序不确定性以及中断的不可预知性产生的数据不一致问题。 该操作通过将内存中的值与指定数据进行比较，当数值一样时将内存中的数据替换为新的值。

说白了他指的是一种由底层提供的 atomic 指令, 其具备 RMW ( read and write ) 的特性, 表示CPU会帮我们确保在read和write的中间不会有其他指令介入。而我们也可以利用这种特性来实作 atomic 的资料结构。

明天会藉由相应的实作来帮助理解该怎麽进行操作。

明天进度

实作一个 lock-free 的 stack 来让大家简单的理解 CAS 的使用。

明天见 !