0%

RDCSS

RDCSS是Harris提出的一种实现double compare single swap方法,它的语义(也就是DCAS)如下,

The CAS1 Approach

下面使用CAS1(single word compare and swap)来实现RDCSS。

这是descriptor和两个data section的示意图,

下面是RDCSS的伪代码,

  1. C1:首先尝试把a2变为descriptor d,如果CAS1成功,那么r == d->o2。

  2. H1:这步主要是针对C1失败的。如果C1成功,r不是descriptor。如果C1失败,有两种原因(其实是一种,只是分开看),(1)a2的数据被其他thread改为其他的数据,(2)a2被其他thread改为descriptor,那就帮助其他thread完成。

  3. B1:如果是H1(2),那么帮助其他thread完成以后,retry。

  4. if(r == d->o2) Complete这步是针对C1成功的。如果C1成功,继续执行。

A practical multi-word compare-and-swap operation - cstheory里,axel22大神问这步能不能在不改变RDCSS语义的情况下省略。回答是,如果省略RDCSS的这个部分if(... && (*a1 == o1)) *a2=n2就不会执行。或者运气好的话,其他thread帮助当前thread完成。

  1. return r返回a2里老的value,包括执行成功的情况和H1(1)。

Problem

C2的if进行比较以后,会不会有其他thread改变o1?

这里是一直没有想明白的。在看了Ctrie的代码以后,发现在做snapshot的时候,里面的root,mainnode和这里的Data section,Control section是对应的。要是这里存在这个问题,那么Ctrie里也存在(会不会有其他thread改变root里mainnode的reference)。

从Ctrie的角度来看,只要有thread在执行RDCSS_Complete,那么root一定是RDCSS_Descriptor。而任何thread想要更改root里mainnode,就必须首先read root。所以mainnode不会在某个thread正执行RDCSS_Complete的时候被改变。
(在上一篇,Notes of Non-Blocking Snapshots Concurrent Tries的A detail in RDCSS_Complete部分,有详细的解释。)

再回过头来看这里的RDCSS,这里的Data section会不会相当于就是一个guard,要更改Control section,就必须首先read Data section。这样,在某个thread执行RDCSS_Complete的时候,其他thread直接去改变o1就是不可能的。(没有在这篇论文里面找到相关的说明,这里只是自己的理解。)

References

  1. A Practical Multi-Word Compare-and-Swap Operation, Timothy L. Harris, Keir Fraser, Ian A. Pratt
  2. A practical multi-word compare-and-swap operationn - cstheory