[原]CAS原理分析

标签: | 发表时间:2014-02-26 14:03 | 作者:HEYUTAO007
出处:http://blog.csdn.net/heyutao007

一、锁机制


常用的锁机制有两种:

1、悲观锁:假定会发生并发冲突,屏蔽一切可能违反数据完整性的操作。悲观锁的实现,往往依靠底层提供的锁机制;悲观锁会导致其它所有需要锁的线程挂起,等待持有锁的线程释放锁。

2、乐观锁:假设不会发生并发冲突,每次不加锁而是假设没有冲突而去完成某项操作,只在提交操作时检查是否违反数据完整性。如果因为冲突失败就重试,直到成功为止。乐观锁大多是基于数据版本记录机制实现。为数据增加一个版本标识,比如在基于数据库表的版本解决方案中,一般是通过为数据库表增加一个 “version” 字段来实现。读取出数据时,将此版本号一同读出,之后更新时,对此版本号加一。此时,将提交数据的版本数据与数据库表对应记录的当前版本信息进行比对,如果提交的数据版本号大于数据库表当前版本号,则予以更新,否则认为是过期数据。 

乐观锁的缺点是不能解决脏读的问题。

在实际生产环境里边,如果并发量不大且不允许脏读,可以使用悲观锁解决并发问题;但如果系统的并发非常大的话,悲观锁定会带来非常大的性能问题,所以我们就要选择乐观锁定的方法.

锁机制存在以下问题:

(1)在多线程竞争下,加锁、释放锁会导致比较多的上下文切换和调度延时,引起性能问题。
(2)一个线程持有锁会导致其它所有需要此锁的线程挂起。
(3)如果一个优先级高的线程等待一个优先级低的线程释放锁会导致优先级倒置,引起性能风险。


二、CAS 操作


JDK 5之前Java语言是靠synchronized关键字保证同步的,这是一种独占锁,也是是悲观锁。java.util.concurrent(J.U.C)种提供的atomic包中的类,使用的是乐观锁,用到的机制就是CAS,CAS(Compare and Swap)有3个操作数,内存值V,旧的预期值A,要修改的新值B。当且仅当预期值A和内存值V相同时,将内存值V修改为B,否则什么都不做。

现代的CPU提供了特殊的指令,允许算法执行读-修改-写操作,而无需害怕其他线程同时修改变量,因为如果其他线程修改变量,那么CAS会检测它(并失败),算法可以对该操作重新计算。而 compareAndSet() 就用这些代替了锁定。

以AtomicInteger为例,研究在没有锁的情况下是如何做到数据正确性的。

public class AtomicInteger extends Number implements java.io.Serializable {
    
    private volatile int value;


    
    public final int get() {
        return value;
    }
	
	public final int getAndIncrement() {
        for (;;) {
            int current = get();
            int next = current + 1;
            if (compareAndSet(current, next))
                return current;
        }
    }
    
    public final boolean compareAndSet(int expect, int update) {
		return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
    }


字段value需要借助volatile原语,保证线程间的数据是可见的(共享的)。这样在获取变量的值的时候才能直接读取。然后来看看++i是怎么做到的。getAndIncrement采用了CAS操作,每次从内存中读取数据然后将此数据和+1后的结果进行CAS操作,如果成功就返回结果,否则重试直到成功为止。而compareAndSet利用JNI来完成CPU指令的操作。

public final boolean compareAndSet(int expect, int update) {   
    return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
 }


整体的过程就是这样子的,利用CPU的CAS指令,同时借助JNI来完成Java的非阻塞算法。其它原子操作都是利用类似的特性完成的。
而整个J.U.C都是建立在CAS之上的,因此对于synchronized阻塞算法,J.U.C在性能上有了很大的提升。

CAS第一个问题是会导致“ABA问题”。
aba实际上是乐观锁无法解决脏数据读取的一种体现。CAS算法实现一个重要前提需要取出内存中某时刻的数据,而在下时刻比较并替换,那么在这个时间差类会导致数据的变化。比如说一个线程one从内存位置V中取出A,这时候另一个线程two也从内存中取出A,并且two进行了一些操作变成了B,然后two又将V位置的数据变成A,这时候线程one进行CAS操作发现内存中仍然是A,然后one操作成功。尽管线程one的CAS操作成功,但是不代表这个过程就是没有问题的。如果 链表的头在变化了两次后恢复了原值,但是不代表链表就没有变化。因此AtomicStampedReference/AtomicMarkableReference就很有用了。


AtomicMarkableReference 类描述的一个<Object,Boolean>的对,可以原子的修改Object或者Boolean的值,这种数据结构在一些缓存或者状态描述中比较有用。这种结构在单个或者同时修改Object/Boolean的时候能够有效的提高吞吐量。 


AtomicStampedReference 类维护带有整数“标志”的对象引用,可以用原子方式对其进行更新。对比AtomicMarkableReference 类的<Object,Boolean>,AtomicStampedReference 维护的是一种类似<Object,int>的数据结构,其实就是对对象(引用)的一个并发计数(标记版本戳stamp)。但是与AtomicInteger 不同的是,此数据结构可以携带一个对象引用(Object),并且能够对此对象和计数同时进行原子操作。



             
作者:HEYUTAO007 发表于2014-2-26 14:03:07 原文链接
阅读:4 评论:0 查看评论

相关 [cas 原理 分析] 推荐:

[原]CAS原理分析

- -
1、悲观锁:假定会发生并发冲突,屏蔽一切可能违反数据完整性的操作. 悲观锁的实现,往往依靠底层提供的锁机制;悲观锁会导致其它所有需要锁的线程挂起,等待持有锁的线程释放锁. 2、乐观锁:假设不会发生并发冲突,每次不加锁而是假设没有冲突而去完成某项操作,只在提交操作时检查是否违反数据完整性. 如果因为冲突失败就重试,直到成功为止.

CAS实现SSO单点登录原理

- - 非技术 - ITeye博客
CAS实现SSO单点登录原理. CAS ( Central Authentication Service ) 是 Yale 大学发起的一个企业级的、开源的项目,旨在为 Web 应用系统提供一种可靠的单点登录解决方法(属于 Web SSO ). CAS 开始于 2001 年, 并在 2004 年 12 月正式成为 JA-SIG 的一个项目.

cas配置单点登录

- - 开源软件 - ITeye博客
        最近一段时间研究的cas,不知道是什么原因,可能自己最近太浮躁了,没有沉下心来去研究,所以一直拖着,将近拖了一周半的时间,上周的周总结,确保一定要解决的问题,今天还是横下心来,处理完这个问题,我是一个对于技术痴迷的人,对于现在研究出来这个结果非常高兴,与大家分享一下:.        注明:本文所讲的至少怎么配置,但是具体的原理和细节会在稍后的时间里更新给大家,如有不对的地方希望大家指出来,共同学习和探讨一下.

shiro-cas 单点退出

- - 互联网 - ITeye博客
shiro与CAS集成以后的单点退出. 效果任何一个应用退出以后 所有应用都要重新登录. 实现思路shiro退出系统以后重新定向到cas的退出. 1.重新配置shiro的登出跳转.   shiro退出以后跳转到cas的退出.   cas退出以后通过service参数跳转回应用界面. 2.覆盖shiro的默认退出实现 .

NumericField&NumericRangeQuery原理分析

- - 搜索引擎技术博客
NumericField和NumericRangeQuery是Lucene. 针对数值型区间查询的优化方案. 和NumbericRanageQuery. 的实现原理之前,对于Lucene范围查询的实现和概念可以参考博文《TermRangeQuery源码解析》一文.       从Lucene 2.9 开始,提供对数字范围的支持,然而欲使用此查询,必须使用NumericField 添加域,使用Lucene原生API:.

CAS解决单点登录SSO

- - CSDN博客推荐文章
关于CAS很多的原理和基础的配置启动,网上是很多的,我更多是结合我的实践和心得. 需要了解CAS的原理,认证协议,认证流程,可以参考以下文章. 让CAS支持客户端自定义登陆页面——客户端篇. CAS原理与配置-基于CAS的单点登陆的研究(上). 单点登录(SSO)是企业开发的重要问题,在我的毕设项目中,由于要和系统其他开发模块共用用户认证模块,方便共享用户资源,所以需要一个好的SSO解决方案.

CAS和Shiro在spring中集成

- - CSDN博客架构设计推荐文章
shiro是权限管理框架,现在已经会利用它如何控制权限. 为了能够为多个系统提供统一认证入口,又研究了单点登录框架cas. 因为二者都会涉及到对session的管理,所以需要进行集成. Shiro在1.2.0的时候提供了对cas的集成. 因此在项目中添加shiro-cas的依赖. Shiro对cas集成后,cas client的配置更加简单了.

CAS 4.0 单点登录教程

- - ITeye博客
单点登录(Single Sign On),简称为 SSO,是目前比较流行的企业业务整合的解决方案之一. SSO的定义是在多个应用系统中,用户只需要登录一次就可以访问所有相互信任的应用系统. 耶鲁大学(yale)开发的单点登录(Single Sign On)系统称为CAS(Central Authentication Service)被设计成一个独立的Web应用程序(cas.war).

CAS单点登录(SSO)完整教程

- - 互联网 - ITeye博客
CAS单点登录(SSO)完整教程(2012-02-01更新). 教程目的:从头到尾细细道来单点登录服务器及客户端应用的每个步骤. 单点登录(SSO):请看百科解释. 本教程使用的SSO服务器是Yelu大学研发的CAS(Central Authentication Server),. CAS Server版本:cas-server-3.4.3.1、cas-server-3.4.10.

基于CAS实现单点登录(SSO):cas client端的退出问题

- - CSDN博客架构设计推荐文章
自从CAS 3.4就很好的支持了单点注销功能,配置也很简单. 之前版本因为在CAS服务器通过HttpClient发送消息时并未指定为POST方式,所以在CAS客户端的注销Filter中没有收到POST请求(要知道Filter只对Post请求起作用),也就没有做session销毁处理. 两个业务系统APP1和APP2.