多线程读写无锁链表： 之前有没有相同的实现？ (更新)

zylthinking

windoze 发表于 2013-10-29 17:00
回复 1# zylthinking

这个是“用链表实现的队列”，不是“链表”，你看你连在中加插元素的功能都没有怎 ...

哪里该加？

zylthinking

windoze 发表于 2013-10-29 19:29
回复 26# zylthinking

所有操作链表的lkf_node */lkf_node **类型变量的前面。

我找了找， 似乎没有需要加的地方； 你找一个出来， 一起分析分析

zylthinking

windoze 发表于 2013-10-29 21:28
回复 28# zylthinking

volatile不是必须的，但加上可以防止编译器犯傻。

编译器为什么犯傻？
那几行为什么会出问题？ 内存屏障是在cpu发现不了依赖关系时有意义的， 明显的依赖关系存在为何需要内存屏障； 39 行其实是常量赋值不知注意了没有

zylthinking

回复 31# windoze

好吧， 19行是常量
   

zylthinking

windoze 发表于 2013-10-29 23:16
回复 30# zylthinking

39行是常量么？没发现……

乱序了怎么会出问题？
    struct lkf_node* head = __sync_lock_test_and_set(&(list->root.next), NULL);
    if (head == NULL) {
        return NULL;
    }

    struct lkf_node* next = head->next;
    if (next != NULL) {
        list->root.next = next;
        head->next = head;
        return head;
    }

依赖 1.
        list->root.next = next;
        head->next = head;
依赖 next != NULL

依赖 2.
list->root.next 依赖一开始的 struct lkf_node* next = head->next; 而不是  head->next = head; 赋值后的  head->next

若你说依赖2 不存在， 那么int i = 8; int k = i; i = 9 你猜 k 最终的值是哪个？

zylthinking

mmqmjy 发表于 2013-11-03 12:27
一个小bug，考虑下面的调用序列：

链表list已经插入一个节点nodeA，链表状态

static inline struct lkf_node* lkf_node_next(struct lkf_node* node)
{
    struct lkf_node* ptr = node->next;
    if (ptr == NULL || ptr->next == NULL) {
        return NULL;
    }

    if (ptr == node) {
        return ptr;
    }

    node->next = ptr->next;
    ptr->next = NULL;
    return ptr;
}

提供这个函数的目的就是为了避免调用者掉入你所说的那个坑里面， 标红部分保证了你所说的情况发生的话， 直接返回 null; 但这并不是链表循环的结束

zylthinking

我去， 更新完毕居然不上浮， 人工置顶

zylthinking

我主贴改了你好歹给我升到前面去吧................

zylthinking

回复 45# wlmqgzm

我看了一下说明， 没看实现， 如何理解 [size=13.3333px]single-writer/single-reader？[size=13.3333px]
[size=13.3333px]The [size=13.3333px]spsc_queue[size=13.3333px] class provides a single-writer/single-reader fifo queue, pushing and popping is wait-free.[size=13.3333px]



814     /** Pushes as many objects from the array t as there is space.
815      *
816      * \pre only one thread is allowed to push data to the spsc_queue
817      * \return number of pushed items
818      *
819      * \note Thread-safe and wait-free
820      */
821     size_type push(T const * t, size_type size)
822     {
823         return base_type::push(t, size);
824     }



852     /** Pops a maximum of size objects from ringbuffer.
853      *
854      * \pre only one thread is allowed to pop data to the spsc_queue
855      * \return number of popped items
856      *
857      * \note Thread-safe and wait-free
858      * */
859     size_type pop(T * ret, size_type size)
860     {
861         return base_type::pop(ret, size);
862     }
863



如果照字面意思， 那我觉得还是我的高明些； 我的好歹在 多写/一读 的情况下保证 wait_free

zylthinking

回复 50# wlmqgzm

问题是在不分组映射的情况下， 我的在 多写一读 情况下是 wait_free 的， 甚至在一定意义上来说， 我的是多读多写情况下的 wait free;  这都是不需要分组的.并不是我只说是 lock free 的， 就一定意味着仅仅是 lock free 的

而你说的却是 单读单写 情况下的 wait_free， 然后分成多个组来减少碰撞；用这个能说明什么呢