Handle table中CAS操作与A-B-A Problem解析
在研究handle table的时候顺便研究的东西。Baidu了下,发现国内这方面的资料几乎没得,然后就准备瞎bb下,为下面的一篇介绍handle table的结构做准备。
关于lock-free data structure。以及解决这个问题中使用的CAS(compare and swap)操作。以及使用CAS操作的时候出现的A-B-A Problem。
对于lock-free data structure问题的解决,一般是使用流行的CAS操作。来防止需要读写的区域的数值和预期的数值不一样的情况。
Shared,non-blocking的数据结构,和shared blocking的数据结构相比,采用了比较原始的同步方法。咱讨论最多的一个同步方法,就是CAS(compare and swap)。
<?xml:namespace prefix = o ns = "urn:schemas-microsoft-com:office:office" />
关于CAS操作的伪代码如下:
CAS(A,B,C)
BEGIN ATOMIC
if (A==C) {A=B; return TRUE; }
else { return FALSE; }
END ATOMIC
在使用CAS操作的时候,在计算之前,首先记录下一个变量的值。经常是记录一个shared data structure 实现的pointer。然后把这个变量的值存起来。这个时候,当得到了这个变量的新的值,需要update这个共享变量的数值的时候,就需要采用CAS操作来自动update这个共享变量的值。
CAS操作首先检查shared var的值和已经保存起来的值是不是一样的,如果是一样的,就执行update操作。如果不是一样的,就报错。
如果操作失败了的话,就使用这个shared var的新的值来重新做一次计算操作。这个原理,和数据库管理系统里面的并发控制是非常类似的。然后,就把这个shared var所在的link list里面相关的节点,指向一个新的node。这个过程就叫做swap。
就如上面的伪代码里面给出的实现,下面给一个代码实现:
bool cas(volatile word* memory, word newValue, word expectedValue)
{
atomically
{
if(*memory == expectedValue)
{
*memory = newValue;
return true;
}
return false;
}
}
这里介绍了对共享变量的最常用的CAS操作,那么使用这个操作的时候,会出现一个比较经典的问题,叫做A-B-A Problem。
ABA Problem就是譬如一个共享变量A,需要update到一个新的值C,而记录这个变量的值是B,此时A=B;在记录和update的这段时间中,这个共享变量被其余的job或者是thread操作修改了很多次,但是在update之前,还是回到了最开始的值。这就叫做ABA Problem。在构造一个特定的程序的时候,就会出现问题。
下面是在一个调用stack里面的ABA Problem:
| class members | foo (thread stack) | ||
foo: pop till 1. | head_ = a | current = a | ||
| head_->next_ = b | current->next_ = b | ||
bar: pop node a | head_ = b | | ||
| head_.next_ = c | |||
bar: pop node b | head_ = c | head_.next_ = d | ||
bar: push node a | head_ = a | |||
foo: pop 2. cas | head_ = a | current = a | head_.next_ = c | current->next_ = b |