【java并发】基于JUC CAS原理,自己实现简单独占锁

synchronized的基本原理回顾

在jvm内部，所有对象都含有单一的锁，jvm负责跟踪监视被加锁次数,叫做对象监视器。当线程第一次给对象加锁的时候，计数器会加1，离开时会减1.同样任务是可重入的，每次重入也是加1，离开减1. 
synchronized是独占式的，拿到对象锁才能继续，没有获取到锁就会阻塞。

JUC CAS乐观锁基本原理

synchronized就是一种独占锁，会导致其它所有需要锁的线程挂起，等待持有锁的线程释放锁。

乐观锁就是假设没有冲突而去完成某项操作，如果因为冲突失败就重试。
原理有点类似于在数据库记录字段增加一个版本号，每次更新的时候做两个事情：

1.检查数据库记录当前的版本号和读取到的版本号是否一致，不一致说明数据已不是最新，更新失败需要重试.

2.如果版本号一致，更新成功，同时将版本号加1.
在jdk1.5开始，Doug Lea在JUC类库里提供了类似的乐观锁的机制叫CAS.
CAS简介:compareAndSet的意思，就是先比较是否是期望值(是期望值，说明没人更改过，当然也有可能有ABA情况),如果是再设值，不是就设值失败，线程阻塞。如果是基于这个，就要保证比较和设值这两个动作是原子性的，如何保证呢？这个是借助于JNI，利用CPU硬件支持来完成的。利用硬件提供swap和test_and_set指令，单CPU下同一指令的多个指令周期不可中断，SMP中通过锁总线支持这两个指令的原子性。

volilate关键字
Java语言规范允许线程保存共享成员变量的私有拷贝，当线程进入或者离开同步代码块时才与共享成员变量的原始值对比。这样就延伸出可见性的一个问题。
CAS解决了比较和更新的原子性，但是还有另外一个问题就是要保证可见性。Volatile修饰的成员变量在每次被线程访问时，都强迫从共享内存中重读该成员变量的值。而且，当成员变量发生变化时，强迫线程将变化值回写到共享内存。这样在任何时刻，两个不同的线程总是看到某个成员变量的同一个值。
volatile关键字有两层含义：
1.对于这个成员变量不能保存它的私有拷贝，而应直接与共享成员变量交互。
2.volatile前后的代码不能重排

其他话题
volilate和cas只能乐观锁保证的状态控制的正确，而在设置状态失败的时候，仍然需要阻塞线程。juc里提供了LockSupport的park和unpark方法用于阻塞线程。而不同的场景下需要不同的等待策略和锁共享策略，juc提供了AbstractQueuedSynchronizer（AQS）为基类的一序列不同的锁，底层都是基于CAS、LocakSupport和Queue来管理，后续有时间细细分析。

juc基于的CAS，提供了带有原子性的基本类型封装类，如AtomicInteger、AtomicLong等。
AtomicInteger原理：
如自增：

    /**
     * Atomically increments by one the current value.
     *
     * @return the previous value
     */
    public final int getAndIncrement() {
        for (;;) {
            int current = get();
            int next = current + 1;
            if (compareAndSet(current, next))  //cas
                return current;
        }
    }

 compareAndSet的实现如下：

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

 

 

 

自己实现简单乐观独占锁

基于cas，本人简单实现了一个乐观独占锁，代码如下：

 

基于CAS简单乐观独占锁

 

package lock.test;

import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.atomic.AtomicBoolean;
import java.util.concurrent.locks.LockSupport;

/**
 * 简单乐观独占锁
 */
public class OptimisticExclusiveLock {

    /**
     * 独占锁标记 true 锁不可用 false 锁可用
     */
    private AtomicBoolean state = new AtomicBoolean(false);
    List<Thread>          queue = new ArrayList<Thread>();//阻塞队列

    public boolean lock() {
        if (!state.get()&&state.compareAndSet(false, true)) {//取锁成功不会阻塞，程序会继续执行
            return true; // 利用CAS
        } else {
            queue.add(Thread.currentThread());//加入阻塞队列
            LockSupport.park();//阻塞线程
            return false;
        }
    }

    public boolean unLock() {
        if (state.get()) {
            queue.remove(Thread.currentThread());//从队列里移除
            if (state.compareAndSet(true, false)) {// 利用CAS
                if(!queue.isEmpty()){
                    LockSupport.unpark(queue.get(0));//唤醒第一个等待线程
                }
                return true;
            }
            return false;
        } else {
            return false;
        }
    }
}

 

简单乐观独占锁测试

 

package lock.test;

/**
 * @author Administrator 独占锁测试
 */
public class OptimisticExclusiveLockTest {

    public static OptimisticExclusiveLock lock = new OptimisticExclusiveLock(); // 独占锁
    public static volatile int            i    = 0;                            // 保证可见性

    public class Task implements Runnable {

        @Override
        public void run() {
            while (true) {
                try {
                    lock.lock();//加锁
                    i += 2;
                    System.out.println("thread name:" + Thread.currentThread().getName() + " i=" + i);
                } finally {
                    lock.unLock();//释放锁
                    try {
                        Thread.currentThread().sleep(10);
                    } catch (InterruptedException e) {
                        // TODO Auto-generated catch block
                        e.printStackTrace();
                    }
                }
            }
        }
    }

    public void runTask() {
        for (int i = 0; i < 100; i++) {
            Thread t = new Thread(new Task(), "thread" + i);
            t.start();
        }
    }

    public static void main(String[] args) {
        OptimisticExclusiveLockTest test = new OptimisticExclusiveLockTest();
        test.runTask();

    }
}

 

 这里实现的简单乐观独占锁很简单，但是能保证并发性。

 JUC里面基于CAS实现了很多的锁，主要是基于AQS实现，如ReentrantLock,CountDownLatch,Semaphore,FutureTask等，适用于不同的锁场景。

 

 

 

评论

7 楼 njzhxf 2012-04-16  

刚才晕了 看了一下我这个实现也是不行的 必须确保 入队列+park/unpark这两个步骤合并起来的原子性才可以 楼主忽略我吧。。。

6 楼 njzhxf 2012-04-16  

singleant 写道

njzhxf 写道

看了一下代码，你的乐观独占锁是否有可能出现starvation.

假设如下情况：
线程A占有了锁时，
当线程B尝试lock时执行到22,23行之间的时候（在queue.add(Thread.currentThread());这句前）

恰好之前的线程A此时释放了锁，因为此时线程B还没有把自己加入队列中，所以线程A执行到 LockSupport.unpark(queue.get(0));这句的时候并没有唤醒任何线程。

所以当线程A的unlock执行完毕后，有可能线程B仍然处于等待状态。

你好，你说得是对的，还需要对队列的所有操作都加一个锁。
等待队列不能简单的使用一个ArrayList，真正在实现juc的AQS里是使用一个CHL队列，该队列非阻塞，且没有这个问题。
本文是为了探讨java乐观锁的实现机理，例子可能有不完美之处，谢谢提示。

假设ArrayList改成了线程安全的实现后
再将lock方法改成如下，是否可以解决问题？


    public boolean lock(){ 
        if (!state.get()&&state.compareAndSet(false, true)) {//取锁成功不会阻塞，程序会继续执行 
            return true; // 利用CAS 
        } else { 
        do{
        if(state.get()){
        queue.add(Thread.currentThread());//加入阻塞队列 
        LockSupport.park();//阻塞线程 
        }
        }while(state.compareAndSet(true, true));
        return false; 
        } 
    } 

5 楼 singleant 2012-04-16  

njzhxf 写道

看了一下代码，你的乐观独占锁是否有可能出现starvation.

假设如下情况：
线程A占有了锁时，
当线程B尝试lock时执行到22,23行之间的时候（在queue.add(Thread.currentThread());这句前）

恰好之前的线程A此时释放了锁，因为此时线程B还没有把自己加入队列中，所以线程A执行到 LockSupport.unpark(queue.get(0));这句的时候并没有唤醒任何线程。

所以当线程A的unlock执行完毕后，有可能线程B仍然处于等待状态。

你好，你说得是对的，还需要对队列的所有操作都加一个锁。
等待队列不能简单的使用一个ArrayList，真正在实现juc的AQS里是使用一个CHL队列，该队列非阻塞，且没有这个问题。
本文是为了探讨java乐观锁的实现机理，例子可能有不完美之处，谢谢提示。

4 楼 njzhxf 2012-04-16  

我上面所说的情况是基于arraylist已经被替换成了线程安全的实现后（如vector） 仍然存在的问题

3 楼 njzhxf 2012-04-16  

看了一下代码，你的乐观独占锁是否有可能出现starvation.

假设如下情况：
线程A占有了锁时，
当线程B尝试lock时执行到22,23行之间的时候（在queue.add(Thread.currentThread());这句前）

恰好之前的线程A此时释放了锁，因为此时线程B还没有把自己加入队列中，所以线程A执行到 LockSupport.unpark(queue.get(0));这句的时候并没有唤醒任何线程。

所以当线程A的unlock执行完毕后，有可能线程B仍然处于等待状态。

2 楼 singleant 2012-02-21  

learnworld 写道

不错的总结。

有个疑问，在基于CAS简单乐观独占锁简单实现里，采用ArrayList做阻塞队列，会有线程安全问题的，因为unlcok实现里queue.isEmpty()和唤醒阻塞队列不是原子操作，可能导致阻塞的队列无法被唤醒。

提醒的是  实验不够严谨 arraylist可以换成vector

1 楼 learnworld 2012-02-18  

不错的总结。

有个疑问，在基于CAS简单乐观独占锁简单实现里，采用ArrayList做阻塞队列，会有线程安全问题的，因为unlcok实现里queue.isEmpty()和唤醒阻塞队列不是原子操作，可能导致阻塞的队列无法被唤醒。