在行动书采用分体式引用计数的并发锁免费栈的实现

-1

在安东尼·威廉姆斯在行动书并发，他实现了采用分体式引用计数锁免费栈。在头节点的初始加载之后。在这里他使用下面代码中列出的方法调用increase_head_count。在行动书采用分体式引用计数的并发锁免费栈的实现

counted_node_ptr old_head = head.load(); 
increase_head_count(old_head); 

void increase_head_count(counted_node_ptr& old_counter) 
{ 
    counted_node_ptr new_counter; 

    do 
    { 
     new_counter = old_counter; 
     ++new_counter.external_count; 
    } 
    while (!head.compare_exchange_strong(old_counter, new_counter)); 

    old_counter.external_count = new_counter.external_count; 
}

完整的实现可以在这个链接中找到https://github.com/subjam/concurrency-in-action/blob/master/ch7/stack_ref.cpp。我的问题是，如果一个senario发生多个线程试图同时执行pop（）并且所有线程读取头节点，然后只有一个线程执行直到结束，其他人开始执行这个功能，然后这个实现是如何工作的。

我在这里呆了一段时间，如果有人能帮助我理解这一点，我会很高兴。

来源

2017-04-26 Kasun

如果在while子句中，old_counter仍然等于new_counter，那么head设置为new_counter。在任何一次成功的单线程中都是这种情况。

对于其他线程同时访问此方法，compare_exchange_strong（）返回false导致循环迭代。但是，它也会复制old_counter的内容。

这意味着在这些其他（不成功）线程的下一个循环中，old_counter已更新为head的当前内容。

来源

2017-04-26 15:37:55

谢谢你的答案..我对这个问题没有多少怀疑。有两个线程来执行increase_head_count函数，一个在开始时暂停。现在有一个线程会一直执行，甚至在暂停线程唤醒时甚至会删除old_node指针（请参阅链接中给出的完整实现），是不是会抛出异常（无效的内存或类似的东西）执行时++ new_counter.external_count;因为它代表被删除的节点（由第一个线程）。 – Kasun

第一个线程（通过'increase_head_count（）'方法一路通过）将在删除它之前控制'head'。它试图在删除之前将其从堆栈中删除。当它从堆栈中成功移除时，第二个线程（在'increase_head_count（）'中唤醒）将不会有任何头的引用。正如我上面所说的，'old_counter'现在将被更新为指向新的'head'，所以它不会尝试访问任何已被删除的节点。 –

我使用此代码的担忧是，如果最后的第一个（成功）的线程获得推节点，'head'现在指向原来'counted_node_ptr'，代码（在方法'pop'）这第二个线程不会试图删除这个'head'，因为'ptr'是'NULL'。不删除头部会允许在'count_node_ptr'内循环的所有辅助线程离开'pop'返回一个空值'T'。然而'head'的原始值'ptr'不能保证是'NULL'，因为没有构造函数它就不会被初始化。 –

在行动书采用分体式引用计数的并发锁免费栈的实现

回答

相关问题