技术头条 - 一个快速在微博传播文章的方式     搜索本站
您现在的位置：首页 --> 算法 --> lock free的理解

lock free的理解

浏览:2380次  出处信息

its-lock-free

以前一直不明白lock free是什么，后来发现原来是完全理解错了概念，lock free看到大家有的翻译为无锁，有的翻译为锁无关，其实用不用锁和lock free是不相关的，用了锁也可能是lock free，而不用锁有可能不是lock free。

一个lock free的解释是

一个“锁无关”的程序能够确保执行它的所有线程中至少有一个能够继续往下执行。

其实看我们那副图就是说你的各个线程不会互相阻塞，那么你的程序才能成为lock free的。像我们平常用的互斥锁，当有线程获得锁，其他线程就被阻塞掉了，这里的问题就是如果获得锁的线程挂掉了，而且锁也没有释放，那么整个程序其实就被block在那了，而如果程序是lock free的那么即使有线程挂掉，也不影响整个程序继续向下进行，也就是系统在整体上而言是一直前进的。

那么，不用锁就是lock free的吗，一开始就提到了，不用锁也可能不是lock free的，举个例子

  1. while (x == 0) {
  2. x = 1-x;
  3. }

在这里如果两个线程同时执行，可能同时进入while循环，然后x两次改变值之后，依然是0，那么两个线程就会一直互相在这里阻塞掉了，所以这里虽然没有锁，依然不是lock free的。

现在大家写lock free的时候一般都会使用CAS(compare and set)操作来写，因为现在很多的cpu都是支持CAS操作并作为原子操作来处理的，CAS操作一般是这样的

  1. bool compare_and_swap (int *oldval, int *dest, int newval) {
  2.  if (*oldval == *dest) {
  3.  *dest = newval;
  4.  return true;
  5.  }
  6.  return false;
  7. }

其实这样一个操作和乐观锁很像，并且操作简单，相应的比互斥锁的代价要小。所以现在大家都是喜欢用lock free的技术来提高系统的performance。

最后如果大家对于如何编写lock free的数据结构感兴趣的话，可以参考我后面给出的链接。

一种高效无锁内存队列的实现
无锁队列的实现
锁无关的(Lock-Free)数据结构
An Introduction to Lock-Free Programming

建议继续学习：

  1. 无锁消息队列    (阅读：12820)
  2. 并发编程系列之一：锁的意义    (阅读：5905)
  3. 无锁HashMap的原理与实现    (阅读：5352)
  4. MySQL锁管理(并发锁,行锁,表锁,预加锁,全局锁等等)    (阅读：4501)
  5. DYNAMO平台的独门绝技： 利用NWR模型与vector clock解决锁问题    (阅读：3926)
  6. 并行编程中的“锁”难题    (阅读：3762)
  7. MySQL 中 QueryCache 的锁模型    (阅读：3358)
  8. Linux下互斥量加锁与解锁操作的C代码实现    (阅读：3238)
  9. php中读写文件时锁的使用    (阅读：2937)
  10. 锁是怎么实现的？    (阅读：2939)
QQ技术交流群：445447336，欢迎加入！
扫一扫订阅我的微信号：IT技术博客大学习
<< 前一篇：2048-AI程序算法分析
后一篇：15道使用频率极高的基础算法题 >>
文章信息
© 2009 - 2024 by blogread.cn 微博：@IT技术博客大学习

京ICP备15002552号-1