忘记密码   免费注册 查看新帖 | 论坛精华区

ChinaUnix.net

  平台 论坛 博客 认证专区 大话IT HPC论坛 徽章 文库 沙龙 自测 下载 频道自动化运维 虚拟化 储存备份 C/C++ PHP MySQL 嵌入式 Linux系统
最近访问板块 发新帖
楼主: zylthinking

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

论坛徽章:
39
巨蟹座
日期:2013-10-25 10:53:02程序设计版块每日发帖之星
日期:2016-01-27 06:20:00每日论坛发贴之星
日期:2016-01-27 06:20:0015-16赛季CBA联赛之佛山
日期:2016-02-04 21:11:3615-16赛季CBA联赛之佛山
日期:2016-02-05 00:55:2015-16赛季CBA联赛之福建
日期:2016-03-18 12:13:4015-16赛季CBA联赛之辽宁
日期:2016-03-24 21:38:2715-16赛季CBA联赛之福建
日期:2016-04-12 15:21:2915-16赛季CBA联赛之山东
日期:2016-04-17 12:00:282016科比退役纪念章
日期:2016-04-23 00:51:2315-16赛季CBA联赛之新疆
日期:2016-04-25 10:55:45程序设计版块每日发帖之星
日期:2016-07-02 06:20:00
发表于 2013-10-29 23:16 |显示全部楼层
回复 30# zylthinking

39行是常量么?没发现……
另外,39行的list->root.next和40行的head->next没看出有什么依赖关系,但我觉得如果调换次序就会出问题了。

论坛徽章:
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-10-30 00:30 |显示全部楼层
回复 31# windoze

好吧, 19行是常量
   

论坛徽章:
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-10-30 00:48 |显示全部楼层
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 最终的值是哪个?

论坛徽章:
39
巨蟹座
日期:2013-10-25 10:53:02程序设计版块每日发帖之星
日期:2016-01-27 06:20:00每日论坛发贴之星
日期:2016-01-27 06:20:0015-16赛季CBA联赛之佛山
日期:2016-02-04 21:11:3615-16赛季CBA联赛之佛山
日期:2016-02-05 00:55:2015-16赛季CBA联赛之福建
日期:2016-03-18 12:13:4015-16赛季CBA联赛之辽宁
日期:2016-03-24 21:38:2715-16赛季CBA联赛之福建
日期:2016-04-12 15:21:2915-16赛季CBA联赛之山东
日期:2016-04-17 12:00:282016科比退役纪念章
日期:2016-04-23 00:51:2315-16赛季CBA联赛之新疆
日期:2016-04-25 10:55:45程序设计版块每日发帖之星
日期:2016-07-02 06:20:00
发表于 2013-10-30 08:01 |显示全部楼层
回复 33# zylthinking

38行的if检查“head->next”,然后if里面我又看到了list->root.next…………
我没仔细的看你的代码…………最讨厌看这种lock free的东西…………每次都要在纸上画半天各种顺序依赖…………
懒得猜了……谁知道有没有问题……

论坛徽章:
4
天秤座
日期:2013-10-18 13:58:33金牛座
日期:2013-11-28 16:17:01辰龙
日期:2014-01-14 09:54:32戌狗
日期:2014-01-24 09:23:27
发表于 2013-10-30 10:07 |显示全部楼层
,大神给大神review代码,学习了,其实是来顶楼主的。

论坛徽章:
2
处女座
日期:2014-02-11 17:53:48未羊
日期:2014-12-31 15:13:36
发表于 2013-11-03 12:27 |显示全部楼层
一个小bug,考虑下面的调用序列:

链表list已经插入一个节点nodeA,链表状态
list->root.next = nodeA;
nodeA->next = NULL;
list->tail = &nodeA->next;

这时调用put插入节点nodeB,只执行了第一条语句,链表的状态
list->root.next = nodeA;
nodeA->next = NULL;
nodeB->next = NULL;
list->tail = &nodeB->next;
put的最后一句*ptr = node(即nodeA->next = nodeB)还未执行,线程被挂起

这时另一个线程执行get,原链表恢复初始状态,并得到链表nodeB
nodeB->next = nodeA;
nodeA->next = NULL;
得到的新链表不完整,通过next去遍历nodeB只会返回nodeA节点,nodeB丢掉了?
而且,通过next取出nodeA使用完并释放掉内存后,前面挂起的put线程恢复后再执行最后一句就访问到了己释放的内存

PS:put应该要将node->next初始化为NULL吧,反而next最后的ptr->next = NULL有点多余

论坛徽章:
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-11-03 21:46 |显示全部楼层
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; 但这并不是链表循环的结束

论坛徽章:
2
处女座
日期:2014-02-11 17:53:48未羊
日期:2014-12-31 15:13:36
发表于 2013-11-03 23:21 |显示全部楼层
没看到你前面的例子,以为next返回null就结束了
不太符合使用习惯,稍微改一下接口就更完美了

让调用者重试确实是一个很好的替代方案
强求lock-free没必要而且实在太复杂

感谢楼主分享,赞一个

论坛徽章:
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
发表于 2014-08-01 00:19 |显示全部楼层
我去, 更新完毕居然不上浮, 人工置顶

论坛徽章:
33
处女座
日期:2014-06-03 14:14:412015亚冠之莱赫维亚
日期:2015-06-23 13:34:21程序设计版块每日发帖之星
日期:2015-08-30 06:20:00程序设计版块每日发帖之星
日期:2015-12-24 06:20:0015-16赛季CBA联赛之上海
日期:2015-12-27 11:07:07程序设计版块每日发帖之星
日期:2016-01-12 06:20:0015-16赛季CBA联赛之北京
日期:2016-01-15 01:01:2115-16赛季CBA联赛之浙江
日期:2016-01-15 22:38:20程序设计版块每日发帖之星
日期:2016-01-18 06:20:00每日论坛发贴之星
日期:2016-01-18 06:20:0015-16赛季CBA联赛之北控
日期:2016-01-30 21:43:01程序设计版块每日发帖之星
日期:2016-02-08 06:20:00
发表于 2014-08-01 18:13 |显示全部楼层
zylthinking 发表于 2014-08-01 00:19
我去, 更新完毕居然不上浮, 人工置顶

这东西有什么用?
您需要登录后才可以回帖 登录 | 注册

本版积分规则

SACC2017购票8.8折优惠进行时

2017中国系统架构师大会(SACC2017)将于10月19-21日在北京新云南皇冠假日酒店震撼来袭。今年,大会以“云智未来”为主题,云集国内外顶级专家,围绕云计算、人工智能、大数据、移动互联网、产业应用等热点领域展开技术探讨与交流。本届大会共设置2大主会场,18个技术专场;邀请来自互联网、金融、制造业、电商等多个领域,100余位技术专家及行业领袖来分享他们的经验;并将吸引4000+人次的系统运维、架构师及IT决策人士参会,为他们提供最具价值的交流平台。
----------------------------------------
优惠时间:2017年8月2日前

活动链接>>
  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号 北京市公安局海淀分局网监中心备案编号:11010802020122
广播电视节目制作经营许可证(京) 字第1234号 中国互联网协会会员  联系我们:
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP