C++11如何实现无锁队列
无锁操作的本质依赖的原子操作，C++11提供了atomic的原子操作支持
atomic
compare_exchange_weak / compare_exchange_strong
当前值与期望值相等时，修改当前值为设定值，返回true
当前值与期望值不等时，将期望值修改为当前值，返回falsememory_order枚举值
template<typename T>
class lock_free_stack
{
private:
struct node
{
T data;
node* next;
node(T const& data_):
data(data_)
{
}
};
std::atomic<node*> head;
public:
void push(T const& data)
{
node* const new_node=new node(data);
new_node->next=head.load();
/*
** 当前值.compare_exchange_weak(期望值, 设置值)
** 单线程的情况：
** 第一次执行while循环：
** 此时当前值与期望值相等，修改当前值为设定值 head = new_node，返回true
** 多线程的情况：
** 第一次执行循环体的时候：
** compare_exchange_weak如果失败, 返回false, 证明有其他线程更新了栈顶head，
** 当前值与期望值不等时，将期望值修改为当前值, 即new_node->next等于新的栈顶head,
** 被其他线程更新的新栈顶值会被更新到new_node->next中，
** 因此循环可以直接再次尝试压栈而无需由程序员更新new_node->next。
** 然后第二次执行循环体：
** 此时 head == new_node->next, 所以 head = new_node.
** 如果这是仍有其他线程干扰，则仍为循环更新new_node->next
*/
while(!head.compare_exchange_weak(new_node->next,new_node));
}
};
CAS原子操作
- CAS即Compare and Swap，是所有CPU指令都支持CAS的原子操作（X86中CMPXCHG汇编指令），用于实现实现各种无锁（lock free）数据结构。
- CAS用于检查一个内存位置是否包含预期值，如果包含，则把新值复赋值到内存位置。成功返回true，失败返回false。
示例代码如下：
bool compare_and_swap ( int *memory_location, int expected_value, int new_value)
{
if (*memory_location == expected_value)
{
*memory_location = new_value;
return true;
}
return false;
}
ABA问题
所谓ABA（见维基百科的ABA词条），问题基本是这个样子：
- 进程P1在共享变量中读到值为A
- P1被抢占了，进程P2执行
- P2把共享变量里的值从A改成了B，再改回到A，此时被P1抢占。
- P1回来看到共享变量里的值没有被改变，于是继续执行。
虽然P1以为变量值没有改变，继续执行了，但是这个会引发一些潜在的问题。ABA问题最容易发生在lock free 的算法中的，CAS首当其冲，因为CAS判断的是指针的地址。如果这个地址被重用了呢，问题就很大了。（地址被重用是很经常发生的，一个内存分配后释放了，再分配，很有可能还是原来的地址）
eg:
好比你拿着一个装满钱的手提箱在飞机场，此时过来了一个火辣性感的美女，然后她很暖昧地挑逗着你，并趁你不注意的时候，把用一个一模一样的手提箱和你那装满钱的箱子调了个包，然后就离开了，你看到你的手提箱还在那，于是就提着手提箱去赶飞机去了。
这就是ABA的问题。
Fetch-And-Add （FAA）
一般用来对变量做+1的原子操作
Test-And-Set (TAS)
写值到某个内存位置并传回其旧值
参考文章
C++11：原子交换函数compare_exchange_weak和compare_exchange_strong
到此这篇关于C++11如何实现无锁队列的文章就介绍到这了,更多相关C++11无锁队列内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！
相关推荐
-
c++11 atomic的使用详解
std::atomic_flag std::atomic_flag是一个原子的布尔类型,可支持两种原子操作: test_and_set, 如果atomic_flag对象被设置,则返回true; 如果atomic_flag对象未被设置,则设置之,返回false clear. 清楚atomic_flag对象 std::atomic_flag可用于多线程之间的同步操作,类似于linux中的信号量.使用atomic_flag可实现mutex. #include <iostream> #include
-
浅谈C++11的std::mem_fn源码解析
目录 1.源码准备 2.通过一个简单的例子来了解std::mem_fn的作用 3.std::mem_fn源码解析 3.1.std::mem_fn解析 3.2.std::_Mem_fn解析 3.3.在代码中正确使用std::_Mem_fn 4.总结 1.源码准备 本文是基于gcc-4.9.0的源代码进行分析,std::mem_fn是C++11才加入标准的,所以低版本的gcc源码是没有std::mem_fn的,建议选择4.9.0或更新的版本去学习,不同版本的gcc源码差异应该不小,但是原理和设计思想
-
浅谈C++11的std::function源码解析
目录 1.源码准备 2.std::function简介 3.源码解析 3.1.std::function解析 3.2.std::_Function_handler解析 3.3._Any_data解析 3.4.std::_Function_base解析 4.总结 1.源码准备 本文是基于gcc-4.9.0的源代码进行分析,std::function是C++11才加入标准的,所以低版本的gcc源码是没有std::function的,建议选择4.9.0或更新的版本去学习,不同版本的gcc源码差异应该不
-
详解C++11中的线程锁和条件变量
线程 std::thread类, 位于<thread>头文件,实现了线程操作.std::thread可以和普通函数和 lambda 表达式搭配使用.它还允许向线程的执行函数传递任意多参数. #include <thread> void func() { // do some work } int main() { std::thread t(func); t.join(); return 0; } 上面的例子中,t是一个线程实例,函数func()在该线程运行.调用join()函数是
-
c++11 多线程编程——如何实现线程安全队列
线程安全队列的接口文件如下: #include <memory> template<typename T> class threadsafe_queue { public: threadsafe_queue(); threadsafe_queue(const threadsafe_queue&); threadsafe_queue& operator=(const threadsafe_queue&) = delete; void push(T new_va
-
详解C++11的std::addressof源码解析
目录 1.源码准备 2.std::addressof简介 3.std::addressof源码解析 4.总结 1.源码准备 本文是基于gcc-4.9.0的源代码进行分析,std::addressof是C++11才加入标准的,所以低版本的gcc源码是没有这个的,建议选择4.9.0或更新的版本去学习,不同版本的gcc源码差异应该不小,但是原理和设计思想的一样的,下面给出源码下载地址 http://ftp.gnu.org/gnu/gcc 2.std::addressof简介 std::addresso
-
C++11如何实现无锁队列
无锁操作的本质依赖的原子操作,C++11提供了atomic的原子操作支持 atomic compare_exchange_weak / compare_exchange_strong 当前值与期望值相等时,修改当前值为设定值,返回true 当前值与期望值不等时,将期望值修改为当前值,返回false memory_order枚举值 template<typename T> class lock_free_stack { private: struct node { T data; node* n
-
解析C++无锁队列的实现代码
本文给出一种C++无锁队列的实现代码,主要用于一个线程读取数据另外一个线程写数据 复制代码 代码如下: #ifndef LOCK_FREE_QUEUE_H_#define LOCK_FREE_QUEUE_H_ //不加锁队列,适合一个线程读取,一个线程写#include <list>template <typename T>class LockFreeQueue{ public: LockFreeQueue() { list
-
Java语言中cas指令的无锁编程实现实例
最开始接触到相关的内容应该是从volatile关键字开始的吧,知道它可以保证变量的可见性,而且利用它可以实现读与写的原子操作...但是要实现一些复合的操作volatile就无能为力了...最典型的代表是递增和递减的操作.... 我们知道,在并发的环境下,要实现数据的一致性,最简单的方式就是加锁,保证同一时刻只有一个线程可以对数据进行操作....例如一个计数器,我们可以用如下的方式来实现: public class Counter { private volatile int a = 0; pub
-
java无锁hashmap原理与实现详解
java多线程环境中应用HashMap,主要有以下几种选择:使用线程安全的java.util.Hashtable作为替代使用java.util.Collections.synchronizedMap方法,将已有的HashMap对象包装为线程安全的.使用java.util.concurrent.ConcurrentHashMap类作为替代,它具有非常好的性能.而以上几种方法在实现的具体细节上,都或多或少地用到了互斥锁.互斥锁会造成线程阻塞,降低运行效率,并有可能产生死锁.优先级翻转等一系列问题.
-
Java 高并发四：无锁详细介绍
在[高并发Java 一] 前言中已经提到了无锁的概念,由于在jdk源码中有大量的无锁应用,所以在这里介绍下无锁. 1 无锁类的原理详解 1.1 CAS CAS算法的过程是这样:它包含3个参数CAS(V,E,N).V表示要更新的变量,E表示预期值,N表示新值.仅当V 值等于E值时,才会将V的值设为N,如果V值和E值不同,则说明已经有其他线程做了更新,则当前线程什么 都不做.最后,CAS返回当前V的真实值.CAS操作是抱着乐观的态度进行的,它总是认为自己可以成功完成 操作.当多个线程同时使用CAS操
-
Java中的线程同步与ThreadLocal无锁化线程封闭实现
Synchronized关键字 Java语言的关键字,当它用来修饰一个方法或者一个代码块的时候,能够保证在同一时刻最多只有一个线程执行该段代码. 当两个并发线程访问同一个对象object中的这个synchronized(this)同步代码块时,一个时间内只能有一个线程得到执行.另一个线程必须等待当前线程执行完这个代码块以后才能执行该代码块. 然而,当一个线程访问object的一个synchronized(this)同步代码块时,另一个线程仍然可以访问该object中的非synchronized(
-
使用JAVA实现高并发无锁数据库操作步骤分享
1. 并发中如何无锁.一个很简单的思路,把并发转化成为单线程.Java的Disruptor就是一个很好的例子.如果用java的concurrentCollection类去做,原理就是启动一个线程,跑一个Queue,并发的时候,任务压入Queue,线程轮训读取这个Queue,然后一个个顺序执行. 在这个设计模式下,任何并发都会变成了单线程操作,而且速度非常快.现在的node.js, 或者比较普通的ARPG服务端都是这个设计,"大循环"架构.这样,我们原来的系统就有了2个环境:并发环境 +
-
Java日常练习题,每天进步一点点(58)
目录 1.对于A.B两种排队方式,说法正确的是 2.Inter-process communication (IPC) is the transfer of data among processes. Which of the following is NOT a typical programming technique for IPC? 3.设在内存中有P1,P2,P3三道程序,并按照P1,P2,P3的优先级次序运行,其中内部计算和IO操作时间由下表给出(CPU计算和IO资源都只能同时由一个
-
Java 浅谈 高并发 处理方案详解
目录 高性能开发十大必须掌握的核心技术 I/O优化:零拷贝技术 I/O优化:多路复用技术 线程池技术 无锁编程技术 进程间通信技术 Scale-out(横向拓展) 缓存 异步 高性能.高可用.高拓展 解决方案 高性能的实践方案 高可用的实践方案 高扩展的实践方案 总结 高性能开发十大必须掌握的核心技术 我们循序渐进,从内存.磁盘I/O.网络I/O.CPU.缓存.架构.算法等多层次递进,串联起高性能开发十大必须掌握的核心技术. - I/O优化:零拷贝技术 - I/O优化:多路复用技术 - 线程池技