请问这种lock-free list为什么enqueue冲突呢？

lxyscls

dequeue没问题（没有释放内存）
enqueue冲突，但是没看出是什么原因

1. #include <cstddef>
   
2. #include <atomic>
   
3. 
   
4. using namespace std;
   
5. 
   
6. template <typename T>
   
7. class queue;
   
8. 
   
9. template <typename T>
   
10. class record {
    
11.     friend class queue<T>;
    
12.     public:
    
13.         record() : next(NULL) {}
    
14.         record(const T &t) : value(t), next(NULL) {}
    
15. 
    
16.     private:
    
17.         T       value;
    
18.         record  *next;
    
19. };
    
20. 
    
21. template <typename T>
    
22. class queue {
    
23.     public:
    
24.         queue();
    
25. 
    
26.         void enqueue(const T &t);
    
27.         const T &dequeue(void);
    
28. 
    
29.     private:
    
30.         atomic<record<T> *>head;
    
31.         atomic<record<T> *>tail;
    
32. };
    
33. 
    
34. template <typename T>
    
35. queue<T>::queue()
    
36. {
    
37.     record<T> *q = new record<T>;
    
38. 
    
39.     head.store(q);
    
40.     tail.store(q);
    
41. }
    
42. 
    
43. template <typename T>
    
44. void queue<T>::enqueue(const T &t)
    
45. {
    
46.     record<T> *q = new record<T>(t);
    
47.     record<T> *p = tail.load();
    
48.         
    
49.     do {                                                                                                                                                                                       
    
50.         p->next = q;
    
51.     } while (!tail.compare_exchange_weak(p, q));
    
52. }
    
53. 
    
54. template <typename T>
    
55. const T &queue<T>::dequeue(void)
    
56. {
    
57.     record<T> *p = head.load();
    
58. 
    
59.     do {
    
60.         if (p->next == NULL)
    
61.             return static_cast<T>(-1);
    
62.     } while (!head.compare_exchange_weak(p, p->next));
    
63. 
    
64.     return p->next->value;
    
65. }

复制代码

drangon

enqueue 有问题，51行的 p->next = q; 没有保护，并行操作会导致p->next的值有问题

这里面涉及到两步操作（p->next的赋值，以及tail移到下一个节点的赋值），需要很好的进行设计，
核心的一点在于 tail->next 只有在NULL的时候才能更改，compare_exchange_weak要针对这个来使用，

lxyscls

enqueue 有问题，51行的 p->next = q; 没有保护，并行操作会导致p->next的值有问题

<-- 请问这个时候会出现什么问题呢？假设两个线程同时enqueue，并同时拿到了同样的p，挂了不同的q(p->next = q)
      compare_exchange_weak不是只能有一个能成功吗？如果第一个线程成功了，那么第二个线程就不满足tail == p了，compare_exchange_weak应该失败才对

核心的一点在于 tail->next 只有在NULL的时候才能更改，compare_exchange_weak要针对这个来使用

<-- 关于这点，“酷壳”上面的实现，跟您讲得是一样的，但是因为C++ 11的<atomic>没办法对tail->next做compare_exchange_weak，atomic_compare_exchange_weak(tail->next, NULL, q)直接编译失败了
     atomic<record <T> *>tail并没有“next”这个成员，所以我才改成了1楼的方法，没料到错就错在这儿了

     能不能再详细指点指点，lock-free和C++都是新手

wenlq

http://www.codeproject.com/Artic ... entation-in-C-and-C

lxyscls

回复 4# wenlq


    谢谢！

    扫了一眼，是win32 API的，看来只能参考思路了

wenlq

lockfree_linux.cpp (6.94 KB, 下载次数: 9)

2015-09-06 10:12 上传

点击文件名下载附件

[b

]回复 5# lxyscls


   

for linux

lxyscls

回复 6# wenlq


    谢谢！这个思路跟前面那个一样，不过用了ASM来实现CAS，看来需要学习一下这个思路了

    其实我最想知道的是两个问题：为什么“p->next = q; CAS(tail, p, q);”不行，冲突在哪里？用c++ 11 <atomic>怎么改？

TiGEr.zZ

错误2楼已经指出，多个enqueue会同时修改p->next的值，使得结果不定。
你需要对next使用atomic，需要定义其为atomic变量，正如head和tail所做的那样，虽然其实这个不是问题的核心。

lxyscls

回复 8# TiGEr.zZ


    谢谢！

   

错误2楼已经指出，多个enqueue会同时修改p->next的值，使得结果不定。

   
    step 1: a thread p->next = q_1;
    step 2: b thread p->next = q_2;
    step 3: a thread CAS(tail, p, q_1);
   
    这个时候（tail==p && tail->next==q_2），如果CAS(tail, p, q_1)，那么就相当于linked_list断掉了，因为tail->next != q_1

    干