免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
查看: 24624101 | 回复: 24624101

[算法] 多线程读写无锁链表: 之前有没有相同的实现? (更新) [复制链接]

论坛徽章:
11
未羊
日期:2013-12-16 12:45:4615-16赛季CBA联赛之青岛
日期:2016-04-11 19:17:4715-16赛季CBA联赛之广夏
日期:2016-04-06 16:34:012015亚冠之卡尔希纳萨夫
日期:2015-11-10 10:04:522015亚冠之大阪钢巴
日期:2015-07-30 18:29:402015亚冠之城南
日期:2015-06-15 17:56:392015亚冠之卡尔希纳萨夫
日期:2015-05-15 15:19:272015亚冠之山东鲁能
日期:2015-05-14 12:38:13金牛座
日期:2014-12-04 15:34:06子鼠
日期:2014-10-16 13:40:4715-16赛季CBA联赛之八一
日期:2016-07-22 09:41:40
发表于 2013-08-21 10:33 |显示全部楼层
本帖最后由 zylthinking 于 2017-04-18 12:22 编辑

再更新一次? 貌似更新在这里也没什么意义, 包含一个 proc_context 的 bugfix, 另外在 linux 下增加了两个同步函数

  1. #ifdef __linux__
  2. #include <syscall.h>
  3. #include <unistd.h>

  4. static inline void lkf_node_put_wake(struct lkf_list* list, struct lkf_node* node)
  5. {
  6.     node->next = NULL;
  7.     struct lkf_node** ptr = __sync_lock_test_and_set(&(list->tail), &(node->next));
  8.     if (ptr == &list->root.next) {
  9.         while (-1 == syscall(__NR_futex, ptr, FUTEX_WAKE, 1, NULL, NULL, 0));
  10.     }
  11.     *ptr = node;
  12. }

  13. static inline struct lkf_node* lkf_node_get_wait(struct lkf_list* list)
  14. {
  15.     struct lkf_node* ptr = __sync_lock_test_and_set(&(list->root.next), NULL);
  16.     while (ptr == NULL) {
  17.         syscall(__NR_futex, &list->root.next, FUTEX_WAIT, NULL, NULL, NULL, 0);
  18.         ptr = __sync_lock_test_and_set(&(list->root.next), NULL);
  19.     };

  20.     struct lkf_node** last = __sync_lock_test_and_set(&(list->tail), &(list->root.next));
  21.     *last = ptr;
  22.     return *last;
  23. }
  24. #endif

  25. #if 1
  26. typedef struct proc_context {
  27.     struct lkf_list list;
  28.     int stat;
  29. } proc_context;

  30. static int proc_enter(struct proc_context* ctx, struct lkf_node* node)
  31. {
  32.     lkf_node_put(&ctx->list, node);
  33.     __sync_synchronize();
  34.     int n = __sync_bool_compare_and_swap(&ctx->stat, 0, 1);
  35.     if (n == 0) {
  36.         return -1;
  37.     }
  38.     return 0;
  39. }

  40. static int proc_leave(struct proc_context* ctx)
  41. {
  42.     ctx->stat = 0;
  43.     __sync_synchronize();
  44.     if (ctx->list.tail == &ctx->list.root.next) {
  45.         return 0;
  46.     }

  47.     int n = __sync_bool_compare_and_swap(&ctx->stat, 0, 1);
  48.     if (n == 0) {
  49.         return 0;
  50.     }
  51.     return -1;
  52. }
  53. #endif
复制代码





更新: 增加了一个基于 lkf 的 proc_context, 使用场景: 当多个线程拿到同一个实体的数据并进行处理时, 先检查是否有其他线程已经在处理该实体数据, 若是, 将数据移交给该线程, 自身退出, 否则, 亲自处理。
还是希望看得懂的哥们仔细找找是否存在漏洞, 这玩意真是太难想了, 翻来覆去, 总是没有足够自信说没有 bug
  1. struct proc_context {
  2.     struct lkf_list list;
  3.     int stat;
  4. };

  5. static int proc_enter(struct proc_context* ctx, struct lkf_node* node)
  6. {
  7.     lkf_node_put(&ctx->list, node);
  8.     int n = __sync_bool_compare_and_swap(&ctx->stat, 0, 1);
  9.     if (n == 0) {
  10.         return -1;
  11.     }
  12.     return 0;
  13. }

  14. static int proc_leave(struct proc_context* ctx)
  15. {
  16.     ctx->stat = 0;
  17.     if (ctx->list.tail == &ctx->list.root.next) {
  18.         return 0;
  19.     }

  20.     int n = __sync_bool_compare_and_swap(&ctx->stat, 0, 1);
  21.     if (n == 0) {
  22.         return 0;
  23.     }
  24.     return -1;
  25. }
复制代码
写了一个多线程读多线程写的无锁链表, 完全是自己的思路, 但不知道之前有没有其他人已经提出来过了, 和 MS Queue 比, 应该好点吧, 自以为。
github 地址: https://github.com/zylthinking/lkf/blob/master/lkf.h, 上面有个测试程序, 已经使用 500 读线程 500 写线程 共 1亿次操作测试过了很多次, 没有出现错误。
相关帖子:http://bbs.chinaunix.net/thread-4094984-1-2.html
  1. #ifndef lkf_h
  2. #define lkf_h

  3. struct lkf_node {
  4.     struct lkf_node* next;
  5. };

  6. struct lkf_list {
  7.     struct lkf_node root;
  8.     struct lkf_node** tail;
  9. };


  10. #define LKF_INIT(name) {.root = {NULL}, .tail = &(name.root.next)}
  11. #define LKF_LIST(name) \
  12. struct lkf_list name = LKF_INIT(name)

  13. #define INIT_LKF(name) \
  14. do { \
  15.     name->root.next = NULL; \
  16.     name->tail = &(name->root.next); \
  17. } while (0)

  18. static inline void lkf_node_put(struct lkf_list* list, struct lkf_node* node)
  19. {
  20.     struct lkf_node** ptr = __sync_lock_test_and_set(&(list->tail), &(node->next));
  21.     *ptr = node;
  22. }

  23. static inline struct lkf_node* lkf_node_get_one(struct lkf_list* list)
  24. {
  25.     struct lkf_node* head = __sync_lock_test_and_set(&(list->root.next), NULL);
  26.     if (head == NULL) {
  27.         return NULL;
  28.     }

  29.     struct lkf_node* next = head->next;
  30.     if (next != NULL) {
  31.         list->root.next = next;
  32.         head->next = head;
  33.         return head;
  34.     }

  35.     int b = __sync_bool_compare_and_swap(&(list->tail), &(head->next), &(list->root.next));
  36.     if (b) {
  37.         head->next = head;
  38.         return head;
  39.     }

  40.     list->root.next = head;
  41.     return NULL;
  42. }

  43. static inline struct lkf_node* lkf_node_get(struct lkf_list* list)
  44. {
  45.     struct lkf_node* ptr = __sync_lock_test_and_set(&(list->root.next), NULL);
  46.     if (ptr == NULL) {
  47.         return NULL;
  48.     }

  49.     struct lkf_node** last = __sync_lock_test_and_set(&(list->tail), &(list->root.next));
  50.     *last = ptr;
  51.     return *last;
  52. }

  53. static inline struct lkf_node* lkf_node_next(struct lkf_node* node)
  54. {
  55.     struct lkf_node* ptr = node->next;
  56.     if (ptr == NULL || ptr->next == NULL) {
  57.         return NULL;
  58.     }

  59.     if (ptr == node) {
  60.         return ptr;
  61.     }

  62.     node->next = ptr->next;
  63.     ptr->next = NULL;
  64.     return ptr;
  65. }

  66. #endif
复制代码

论坛徽章:
36
子鼠
日期:2013-08-28 22:23:29黄金圣斗士
日期:2015-12-01 11:37:51程序设计版块每日发帖之星
日期:2015-12-14 06:20:00CU十四周年纪念徽章
日期:2015-12-22 16:50:40IT运维版块每日发帖之星
日期:2016-01-25 06:20:0015-16赛季CBA联赛之深圳
日期:2016-01-27 10:31:172016猴年福章徽章
日期:2016-02-18 15:30:3415-16赛季CBA联赛之福建
日期:2016-04-07 11:25:2215-16赛季CBA联赛之青岛
日期:2016-04-29 18:02:5915-16赛季CBA联赛之北控
日期:2016-06-20 17:38:50技术图书徽章
日期:2016-07-19 13:54:03程序设计版块每日发帖之星
日期:2016-08-21 06:20:00
发表于 2013-08-21 13:45 |显示全部楼层
顶一下               

论坛徽章:
7
天蝎座
日期:2013-09-28 10:45:42双子座
日期:2013-10-16 16:27:09射手座
日期:2013-10-23 10:21:32处女座
日期:2014-09-17 16:44:332015年亚洲杯之巴林
日期:2015-04-09 17:28:01冥斗士
日期:2015-11-26 16:19:0015-16赛季CBA联赛之山东
日期:2018-03-02 23:59:31
发表于 2013-08-21 15:06 |显示全部楼层
本帖最后由 cxytz01 于 2013-08-21 15:26 编辑

CAS是吧?...
打击楼主一下,楼主不是第一个。
不过能耐心写出来也很厉害。

论坛徽章:
11
未羊
日期:2013-12-16 12:45:4615-16赛季CBA联赛之青岛
日期:2016-04-11 19:17:4715-16赛季CBA联赛之广夏
日期:2016-04-06 16:34:012015亚冠之卡尔希纳萨夫
日期:2015-11-10 10:04:522015亚冠之大阪钢巴
日期:2015-07-30 18:29:402015亚冠之城南
日期:2015-06-15 17:56:392015亚冠之卡尔希纳萨夫
日期:2015-05-15 15:19:272015亚冠之山东鲁能
日期:2015-05-14 12:38:13金牛座
日期:2014-12-04 15:34:06子鼠
日期:2014-10-16 13:40:4715-16赛季CBA联赛之八一
日期:2016-07-22 09:41:40
发表于 2013-08-21 16:51 |显示全部楼层
cxytz01 发表于 2013-08-21 15:06
CAS是吧?...
打击楼主一下,楼主不是第一个。
不过能耐心写出来也很厉害。


肯定不是第一个写无锁链表的, 但使用这个思路的是不是第一个呢? 我找了很多资料。 貌似没有相似的思路

论坛徽章:
0
发表于 2013-08-21 19:35 |显示全部楼层
粗略一看,楼主写的不是真正意义无锁队列,从put就可以看出,任何一个操作暂停(线程挂了),链表都会破坏,get也比较可笑,竟然明明队列中有数据也可能读不出来,一致性得不到保证,也就是说只满足特定应用场景。next操作很可能存在冲突。
BTW,链表的接口先搞搞好。

论坛徽章:
11
未羊
日期:2013-12-16 12:45:4615-16赛季CBA联赛之青岛
日期:2016-04-11 19:17:4715-16赛季CBA联赛之广夏
日期:2016-04-06 16:34:012015亚冠之卡尔希纳萨夫
日期:2015-11-10 10:04:522015亚冠之大阪钢巴
日期:2015-07-30 18:29:402015亚冠之城南
日期:2015-06-15 17:56:392015亚冠之卡尔希纳萨夫
日期:2015-05-15 15:19:272015亚冠之山东鲁能
日期:2015-05-14 12:38:13金牛座
日期:2014-12-04 15:34:06子鼠
日期:2014-10-16 13:40:4715-16赛季CBA联赛之八一
日期:2016-07-22 09:41:40
发表于 2013-08-21 19:41 |显示全部楼层
本帖最后由 zylthinking 于 2013-08-21 19:51 编辑
zhouzhenghui 发表于 2013-08-21 19:35
粗略一看,楼主写的不是真正意义无锁队列,从put就可以看出,任何一个操作暂停(线程挂了),链表都会破坏, ...


你先把你写的那个 bug 找出来吧, 好歹我这个跑了好多遍没出错, 你那个一跑就挂, 没一次对的好不好。
而且, 似乎就是 ms queue 的翻版? ms queue 怎么做你就照本宣科?

论坛徽章:
11
未羊
日期:2013-12-16 12:45:4615-16赛季CBA联赛之青岛
日期:2016-04-11 19:17:4715-16赛季CBA联赛之广夏
日期:2016-04-06 16:34:012015亚冠之卡尔希纳萨夫
日期:2015-11-10 10:04:522015亚冠之大阪钢巴
日期:2015-07-30 18:29:402015亚冠之城南
日期:2015-06-15 17:56:392015亚冠之卡尔希纳萨夫
日期:2015-05-15 15:19:272015亚冠之山东鲁能
日期:2015-05-14 12:38:13金牛座
日期:2014-12-04 15:34:06子鼠
日期:2014-10-16 13:40:4715-16赛季CBA联赛之八一
日期:2016-07-22 09:41:40
发表于 2013-08-21 19:50 |显示全部楼层
zhouzhenghui 发表于 2013-08-21 19:35
粗略一看,楼主写的不是真正意义无锁队列,从put就可以看出,任何一个操作暂停(线程挂了),链表都会破坏, ...


,竟然明明队列中有数据也可能读不出来,一致性得不到保证,也就是说只满足特定应用场景。next操作很可能存在冲突

这个你得解释解释, 什么叫有数据读不出来, 看你怎么定义数据准备好了, 我的定义就是 1. 如果 A->B->NULL 则认为 A 准备好了, B  2) 如果在取得同时发现没有人马上使用 B->next, 则认为 B准备好了, 否则, B认为没准备好, 返回NULL 下次再取; 一致性是什么意思, 难道不是读出 A 后要么读不出来, 要读就读出 B来么, 难道 A, B 之间可能返回空就叫做一致性得不到保证??? 你得哪个难道一定返回数据???

next 操作冲突看你怎么用, 本来 next 操作的含义就是为一个单线程准备的, 典型用法:

ptr = get();
while (ptr != ptr->next()) {
    if (ptr == NULL) 下条数据尚未准备好, 爱干嘛干嘛
    else ptr 已经指向下条数据
}

所有线程冲突的地方都是 get 在负责好不好。



论坛徽章:
0
发表于 2013-08-21 19:54 |显示全部楼层
之前的代码只是针对特定问题给出的,有没有错或者错在哪里我的确不知道,但那并不重要。更别说我也给出真正能保证正确的做法和建议。
至于所谓相似,基本的技巧和理念都是相通的,你没有理解什么叫无锁队列,给出来只是在线程都必须运行,并且循环反复重试场景下的才工作的实现,跟真正意义上的无锁相差甚远。我是惜才才提醒几句,建议去掉浮躁才能真正的做好技术。

论坛徽章:
11
未羊
日期:2013-12-16 12:45:4615-16赛季CBA联赛之青岛
日期:2016-04-11 19:17:4715-16赛季CBA联赛之广夏
日期:2016-04-06 16:34:012015亚冠之卡尔希纳萨夫
日期:2015-11-10 10:04:522015亚冠之大阪钢巴
日期:2015-07-30 18:29:402015亚冠之城南
日期:2015-06-15 17:56:392015亚冠之卡尔希纳萨夫
日期:2015-05-15 15:19:272015亚冠之山东鲁能
日期:2015-05-14 12:38:13金牛座
日期:2014-12-04 15:34:06子鼠
日期:2014-10-16 13:40:4715-16赛季CBA联赛之八一
日期:2016-07-22 09:41:40
发表于 2013-08-21 20:27 |显示全部楼层
zhouzhenghui 发表于 2013-08-21 19:54
之前的代码只是针对特定问题给出的,有没有错或者错在哪里我的确不知道,但那并不重要。更别说我也给出真正 ...


所有线程都必须运行, 意思不过是说不能莫名其妙被取消掉, 而且 必须不能在
    struct lkf_node** ptr = __sync_lock_test_and_set(&(list->tail), &(node->next));
    *ptr = node;
这两行中间被莫名其妙取消掉才行, 否则没有任何问题。 我的实现是有这问题, 但我不认为这是个很大问题, 我不认为这两句之间会有什么可以说得通的原因导致这个线程会被取消, 信号之类的不再考虑之内, 用户 pthread_kill 不在考虑之内

那么什么叫无锁队列,  谁在规定什么叫无锁队列?

另外, 惜才啊, 留作业啊什么的拜托别说的那么顺口, 我没有随便拜师的毛病, 之前你说的时候就觉得怎么这么装, 代码一测, 还跑不通, 到现在你都没解决, 看样子也不想找到原因了, 就这样 还建议去掉浮躁才能真正的做好技术???

论坛徽章:
11
未羊
日期:2013-12-16 12:45:4615-16赛季CBA联赛之青岛
日期:2016-04-11 19:17:4715-16赛季CBA联赛之广夏
日期:2016-04-06 16:34:012015亚冠之卡尔希纳萨夫
日期:2015-11-10 10:04:522015亚冠之大阪钢巴
日期:2015-07-30 18:29:402015亚冠之城南
日期:2015-06-15 17:56:392015亚冠之卡尔希纳萨夫
日期:2015-05-15 15:19:272015亚冠之山东鲁能
日期:2015-05-14 12:38:13金牛座
日期:2014-12-04 15:34:06子鼠
日期:2014-10-16 13:40:4715-16赛季CBA联赛之八一
日期:2016-07-22 09:41:40
发表于 2013-08-21 20:29 |显示全部楼层
zhouzhenghui 发表于 2013-08-21 19:54
至于所谓相似,基本的技巧和理念都是相通的,你没有理解什么叫无锁队列.


我真不想故意曲解, 但真的想恶意引申一下, 你是在说, 真正的无锁队列就是基本技巧和理念和你的相通的才能叫是不是?
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP