MyException - 我的异常网
当前位置:我的异常网» 人工智能 » Java并发包Atomic 跟Unsafe续:Lockfree And Waitfr

Java并发包Atomic 跟Unsafe续:Lockfree And Waitfree算法

www.myexceptions.net  网友分享于:2013-11-27  浏览:145次
Java并发包Atomic 和Unsafe续:Lockfree And Waitfree算法

在上篇文章中,Unsafe的操作都是native操作,这个我们在上一节中已经分析过了,那么这些native操作有几个比较特殊:

 

 

public final native boolean compareAndSwapObject(Object o, long offset, Object expected, Object x);

public final native boolean compareAndSwapInt(Object o, long offset, int expected,  int x);

public final native boolean compareAndSwapLong(Object o, long offset, long expected, long x);

 

这几个函数都有个compareAndSwap操作,这个是什么操作?

这个是典型的CAS的操作,这个操作能够保证操作的原子性;这个操作在并行化编程中是个很重要的技术,链接请戳这里。现在几乎所有的CPU都至此这个操作,在X86系统结构中,compare-and-exchange(CMPXCHG)指令能够实现这个原子操作,有了这个院子操作,就可以使用这个操作实现各种无锁(Lock free)的数据结构。

想象一下这个CMPXCHG操作是什么样子的?使用wikipedia上的一个例子来表示这个过程:

 

 

int compare_and_swap (int* reg, int oldval, int newval) 
{
  int old_reg_val = *reg;
  if (old_reg_val == oldval) 
     *reg = newval;
  return old_reg_val;
}

 

这个操作还是比较易懂的,先看*reg的内存值是不是等于oldval,如果是的话,将其赋值newval

这个操作其实并不能看出来赋值是否成功,只是赋值而已;因为这个操作始终会返回oldval。我们将这个返回值设定为bool型,可以确定使用者的调用是不是成功。

 

 

bool compare_and_swap (int *accum, int *dest, int newval)
{
  if ( *accum == *dest ) {
      *dest = newval;
      return true;
  } else {
      *accum = *dest;
      return false;
  }
}
 

好了,现在大家理解了这个操作,与CAS类似的原子操作还有:

Fetch-And-Add

Test and Test-And-Set

Test-Add-Set

CASABA问题:

 

问题描述:

1:进程T读取共存变量值A

2T进程被抢占,进程K执行

3:进程K把共享变量值从A改为B,使用完毕后,再改回A,此时进程T抢占。

4:进程T读取变量值A,发现没有变化,继续执行后续流程。

问题:虽然T认为变量值没有变化,继续执行;但是这回引发潜在的问题。CAS是最容易受到影响的实现,因为CAS判断的是指针的地址。如果地址被重用,那就麻烦了。

解决方案:

wikipedia上的Compare-and-set后面,提供了一个Double Compare-And-Set的解法,戳这里。例如在32位系统上,需要检查64位的内容。

1:一次CAS操作检查双倍长度的值,前半部分是指针,后半部分是计数器值。

2:必须这两个值全部通过,才能进行Double-CAS赋值操作。

这样的话,ABA问题发生时,值同计数器值不同,就能顺利解决ABA问题。依然的问题是,DCAS并不被所有的CPU支持(up to 2006);所以基于DCAS的解决方案都是当成理想方案来考虑的。大家考虑的解决方案依然是用CAS解决。


上面提到了Lock-FreeWait-FreeLock-Based,那么这几种算法究竟是什么意思呢?

Lock-Free:锁无关,一个锁无关的程序能够确保它所有线程中至少有一个能够继续往下执行。这意味着有些线程可能会被任意的延迟,然而在每一个步骤中至少有一个线程能够执行下去。因此这个系统作为一个整体总是在前进的,尽管有些线程的进度可能没有其它线程走的快。

Wait-Free:等待无关,一个等待无关的程序可以在有限步之内结束,而不管其它线程的相对执行速度如何。

Lock-Based:基于锁,基于锁的程序无法提供上面的任何保证,任一线程持有了某互斥体并处于等待状态,那么其它想要获取同意互斥体的线程只有等待,所有基于锁的算法无法摆脱死锁的阴影。

那么根据上述的描述,Wait-FreeLock-Free算法意味着它们有更多的有点:

1:线程中止免疫-杀掉系统中的任何线程都不会倒置其它线程被延迟。

2:信号免疫-线程可以自由穿插执行,不会导致死锁。

3:优先级倒置免疫-这两种算法对优先级倒置免疫。

可见在高并发系统中,基于lock-freewait-free的算法对性能的关键性。

最后返回来,我们再看下AtomicLonggetAndIncrement实现:

 

 

public final long getAndIncrement() {
        while (true) {
            long current = get();
            long next = current + 1;
            if (compareAndSet(current, next))
                return current;
        }
}

 

有感觉到这个实现熟悉嘛?再回一下compareAndSetC++实现,你还有什么想问的呢。


大家在学习时,要多看源码,考虑下开源代码的实现思路,认真学习,总结,再学习,形成自己的学习方法。下面提供几个算法的系统实现链接:

 

Java:

            LockfreeStack:  https://github.com/mthssdrbrg/LockFreeStack

Disruptor: http://www.searchtb.com/2012/10/introduction_to_disruptor.html

 

C:

Nobel:  http://www.cse.chalmers.se/research/group/noble/

Lock-free-lib: http://www.cl.cam.ac.uk/research/srg/netos/lock-free/

 

更多项目实现:

http://www.rossbencina.com/code/lockfree

 

文章评论

旅行,写作,编程
旅行,写作,编程
Java 与 .NET 的平台发展之争
Java 与 .NET 的平台发展之争
如何区分一个程序员是“老手“还是“新手“?
如何区分一个程序员是“老手“还是“新手“?
老美怎么看待阿里赴美上市
老美怎么看待阿里赴美上市
程序员眼里IE浏览器是什么样的
程序员眼里IE浏览器是什么样的
团队中“技术大拿”并非越多越好
团队中“技术大拿”并非越多越好
我的丈夫是个程序员
我的丈夫是个程序员
我跳槽是因为他们的显示器更大
我跳槽是因为他们的显示器更大
程序员和编码员之间的区别
程序员和编码员之间的区别
我是如何打败拖延症的
我是如何打败拖延症的
要嫁就嫁程序猿—钱多话少死的早
要嫁就嫁程序猿—钱多话少死的早
漫画:程序员的工作
漫画:程序员的工作
程序员应该关注的一些事儿
程序员应该关注的一些事儿
十大编程算法助程序员走上高手之路
十大编程算法助程序员走上高手之路
如何成为一名黑客
如何成为一名黑客
 程序员的样子
程序员的样子
总结2014中国互联网十大段子
总结2014中国互联网十大段子
做程序猿的老婆应该注意的一些事情
做程序猿的老婆应该注意的一些事情
程序员周末都喜欢做什么?
程序员周末都喜欢做什么?
不懂技术不要对懂技术的人说这很容易实现
不懂技术不要对懂技术的人说这很容易实现
程序猿的崛起——Growth Hacker
程序猿的崛起——Growth Hacker
老程序员的下场
老程序员的下场
聊聊HTTPS和SSL/TLS协议
聊聊HTTPS和SSL/TLS协议
5款最佳正则表达式编辑调试器
5款最佳正则表达式编辑调试器
程序员都该阅读的书
程序员都该阅读的书
“懒”出效率是程序员的美德
“懒”出效率是程序员的美德
什么才是优秀的用户界面设计
什么才是优秀的用户界面设计
鲜为人知的编程真相
鲜为人知的编程真相
为什么程序员都是夜猫子
为什么程序员都是夜猫子
Web开发人员为什么越来越懒了?
Web开发人员为什么越来越懒了?
程序员必看的十大电影
程序员必看的十大电影
编程语言是女人
编程语言是女人
每天工作4小时的程序员
每天工作4小时的程序员
当下全球最炙手可热的八位少年创业者
当下全球最炙手可热的八位少年创业者
“肮脏的”IT工作排行榜
“肮脏的”IT工作排行榜
60个开发者不容错过的免费资源库
60个开发者不容错过的免费资源库
初级 vs 高级开发者 哪个性价比更高?
初级 vs 高级开发者 哪个性价比更高?
程序员最害怕的5件事 你中招了吗?
程序员最害怕的5件事 你中招了吗?
Web开发者需具备的8个好习惯
Web开发者需具备的8个好习惯
看13位CEO、创始人和高管如何提高工作效率
看13位CEO、创始人和高管如何提高工作效率
代码女神横空出世
代码女神横空出世
为啥Android手机总会越用越慢?
为啥Android手机总会越用越慢?
科技史上最臭名昭著的13大罪犯
科技史上最臭名昭著的13大罪犯
中美印日四国程序员比较
中美印日四国程序员比较
Java程序员必看电影
Java程序员必看电影
软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有