多线程模型下的无锁编程「建议收藏」

多线程模型下的无锁编程「建议收藏」多线程模式是比较流行的一种并发编程模型,多线程编程的一个特点就是线程间共享内存空间;这可以降低线程间通信的开销,但却引来了另外的一个难缠的问题:竟态条件!,因此,甚至有人对多线程模型提出了质疑,看这里。在多线程编程模型下,解决竟态条件的传统方法就是加锁保护临界区,但这存在影响系统性能、优先级反转等问题.因此又有人提出了,多线程模型下无锁编程的一些方式:1.线程内通信框架:Di

大家好,又见面了,我是你们的朋友全栈君。多线程模式是比较流行的一种并发编程模型,多线程编程的一个特点就是线程间共享内存空间;这可以降低线程间通信的开销,但却引来了另外的一个难缠的问题:竟态条件!,因此,甚至有人对多线程模型提出了质疑,看
这里





在多线程编程模型下,解决竟态条件的传统方法就是加锁保护临界区,但这存在影响系统性能、优先级反转等问题.




因此又有人提出了,多线程模型下无锁编程的一些方式:


1.线程内通信框架: Disruptor, 这是一款开源的并发框架,用于线程间无锁的共享数据,看
这里





2.无锁数据结构


无锁数据结构一般基于一个很重要的操作:CAS–Compare And Swap(看
这里
)。


用C语言表达的一个CAS实现的操作是这样的:

  1. /*定义CAS操作*/
  2. #define CAS __sync_bool_compare_and_swap
  3. /*
  4. * 定义stack的数据结构
  5. */
  6. typedef struct stack_node {

  7.     struct node *next;
  8.     void *data;
  9. }stack_node;
  10. /*栈顶指针*/
  11. stack_node *top = NULL;



CAS的一个重要特性是其必须是原子操作。现在大多数CPU都支持指令级别的CAS操作。


GCC编译也提供了这样的接口:bool __sync_bool_compare_and_swap (type *ptr, type oldval type newval, …)




有了这个原子的CAS后,我们就能实现自己的无锁数据结构了,下面我们就尝试着来实现一个无锁栈:




下面的代码中,我们假设malloc与free是线程安全的(至于malloc与free的可重入性与线程安全问题,可以看
这里

这里
)

首先定义必要的数据结构:

  1. /*定义CAS操作*/
  2. #define CAS __sync_bool_compare_and_swap
  3. /*
  4. * 定义stack的数据结构
  5. */
  6. typedef struct stack_node {

  7.     struct node *next; /*指向下一个节点,即通过链表的形式实现栈*/
  8.     void *data;/*指向该节点的数据*/
  9. }stack_node;
  10. /*栈顶指针*/
  11. stack_node *top = NULL;

接下来是
栈操作:

  1. /*压栈操作*/
  2. void stack_push(void *data)
  3. {

  4.     stack_node *new = malloc(sizeof(struct node));
  5.     new>data = data;
  6.     do {

  7.         new>next = top;/*获取top的快照, 同时初始化了new的next指针*/
  8.     }while(!CAS(&top, new>next, new));
  9. }

在取得top的快照后后, 就通过CAS操作查看top的内容与line 7取得的快照是否一致,如果一致则将top的内容更换为new,CAS函数返回true。

假设有线程A在
stack_push里获取top快照后暂时失去了执行权, 切换至另一个线程B, 而线程B完成了一次
stack_push操作,然后执行权再次回到线程A,

线程A执行CAS操作, 发现top里的内容与快照里的内容已经不一致了,CAS返回false, 估do…while语句重新执行。



接下来是出栈操作:

  1. /*出栈操作*/
  2. void * stack_pop(void)
  3. {

  4.     stack_node *tmp;
  5.     void *data;
  6.     
  7.     do {

  8.         tmp = top;
  9.         if (!tmp) return NULL;
  10.     }while(CAS(&top, tmp, tmp>next) = true);
  11.     data = tmp>data;
  12.     free(tmp);
  13.     return data;
  14. }

其免锁原理与入栈基本一样,估不再赘述。



另外还有一点, 在使用CAS实现免锁数据结构时, 容易出现ABA问题, 这里也暂时不作讨论, 可以从参考资料中得到更多的信息。




参考资料:


1.来自酷客的无锁队列


2.
设计不用互斥锁的并发数据结构

3.透过linux内核看无锁编程

转载自:http://blog.chinaunix.net/uid-25424552-id-3772253.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/141681.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 真封神虚拟服务器,服务器端文件详细介绍即修改(三)

    真封神虚拟服务器,服务器端文件详细介绍即修改(三)我们每星期加三个修改教程,废话不多说开始吧。1.打开服务器端,修改等级在version\chinese_gb\config的game_rule.ini可以设置最高等级和宝宝最高等级包括传送最高多钱。PK设置等等。这个相信大家一看就明白了。2.language这个文件夹属于指令的唯一能用的是W端可以读公告系统也就是点卡系统用公告修改器修改下能发公告这里就不多说了工具都是做好…

  • MYSQL EXPLAIN结果详解

    MYSQL EXPLAIN结果详解EXPLAIN不会告诉你关于触发器、存储过程的信息或用户自定义函数对查询的影响情况。EXPLAIN不考虑各种Cache(缓存)。EXPLAIN不能显示MySQL在执行查询时所作的优化工作。部分统计信息是估算的,并非精确值。 EXPALIN只能解释SELECT操作,其他操作要重写为SELECT后查看执行计划。1idselect的识别符,这是select的查询序列号。如果有两列数据id相同,则为同一组查询,由上到下执行。如果id值不同,id值越大,优先级越高。2select_type

  • 未来将是越界的时代

    未来将是越界的时代

  • 有刷/无刷动力电调与马达知识

    有刷/无刷动力电调与马达知识模型车需要行驶,就跟真车一样,需要一套动力单元,也有分电动和油动,至于混合动力这个估计就不需要奢望了,对于车模这么小的空间来说是不现实的,而且模型车也不需要考虑燃油经济性的问题。本文则重点介绍电动模型的动力单元。电动模型的动力,主要是指2个元件:第一就是带动车架行驶的电机(Motor),也称马达/摩打等。第二就是控制电机转速的调速器(SpeedController),很久之前早期的调速器…

  • MSH FINSH 对比

    MSH FINSH 对比内在的区别我也没看明白,我就把我看到的区别总结下:最明显的,msh命令都带一个__cmd_,而finsh命令不带,__cmd_这个前缀是宏定义时加的,使用FINSH_FUNCTION_EXPORT_ALIA、MSH_CMD_EXPORT这2个宏义就会把命令定义成MSH命令,官方手册也提到了,MSH执行效果FINSH执行效果finSH需要在命令后面加上(),美其名曰“C-Style”模式,MSH->exit->FINSHFINSH-&…

  • margin 等高布局

    margin 等高布局

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号