相信看过之前几篇自旋锁实现的同学对设计一个自旋锁会有一定的感觉,有几个实现的要点很实用:
1. 使用AtomicBoolean原子变量的getAndSet(true)方法来实现并发情况下,找到第一个成功执行方法的线程。这个技巧经常使用,在并发编程中经常会遇到这种需求
2.经常会使用volatile boolean类型的变量在多个线程之间同步状态,需要注意的是,对volatile变量的修改只具有可见性,不具有原子性(比如++操作)。
3. 使用一个AtomicReference原子变量的getAndSet方法来创建一个虚拟的链表结构,原理也是CAS操作,在队列锁中经常使用
这篇结合一个实例来说说如何灵活地利用这些技巧实现无锁的能力。
在实际开发中会经常遇到“只创建一次”的场景,这里说的“只创建一次”不是说单实例模式。单实例模式也是解决只创建一次的问题,关于单实例模式有很多技巧来实现高并发情况下只创建一个对象的问题,这里不讨论。 单实例模式解决的问题是所有线程都公用一个静态的引用,可以用volatile变量来标示这个静态引用,从而在所有线程之间共享这个静态引用的状态是否已经改变。
这里说的“只创建一次”的场景是这个需要创建一次的对象不是直接被全局的引用所引用,而是间接地被引用。经常有这种情况,全局维护一个并发的ConcurrentMap, Map的每个Key对应一个对象,这个对象需要只创建一次。这个场景和单实例模式不一样,不能用volatile变量来维护这个局部对象的引用。
举个实际的例子,下面这段代码来自阿里的Dubbo框架的服务注册类AbstractRegistryFactory。 它维护了一个全局的ConcurrentHashMap来保存服务注册中心字符串和服务注册中心对象的映射,不同的key对应不同的Registry对象。
为了保证每个key对应的Registry对象只创建一次,Dubbo的实现是使用了可重入锁来保证串行性,每次都要先获取锁,然后get(key)来获得Registry对象,如果为空,那么就执行createRegistry()方法来创建唯一的Registry对象。
可重入锁和synchronzied一样,会阻塞线程,在高并发执行这个方法的时候,所有线程排队执行,性能肯定很差。
// 注册中心集合 Map<RegistryAddress, Registry> private static final Map<String, Registry> REGISTRIES = new ConcurrentHashMap<String, Registry>(); public Registry getRegistry(URL url) { url = url.setPath(RegistryService.class.getName()) .addParameter(Constants.INTERFACE_KEY, RegistryService.class.getName()) .removeParameters(Constants.EXPORT_KEY, Constants.REFER_KEY); String key = url.toServiceString(); // 锁定注册中心获取过程,保证注册中心单一实例 LOCK.lock(); try { Registry registry = REGISTRIES.get(key); if (registry != null) { return registry; } registry = createRegistry(url); if (registry == null) { throw new IllegalStateException("Can not create registry " + url); } REGISTRIES.put(key, registry); return registry; } finally { // 释放锁 LOCK.unlock(); } }
一种经常的做法是使用ConcurrentHashMap的putIfAbsent(key, value) 方法来保证并发Map里面的这个key只有唯一的值。但是这种做法会造成某些线程无谓地创建了对象,经管最后放入Map的是唯一的值。当createRegistry()是个很重的方法时,这种方法也不是最优的。
public Registry getRegistry(String registryAddress){ Registry registry = registries.get(registryAddress); if(registry == null){ // 第一次并发时可能有多个线程进入到这块代码,这些线程都执行创建对象 registry = createRegistry(); // 利用并发Map的putIfAbsent保证只有第一次创建的对象被放入Map registries.putIfAbsent(registryAddress, registry); // 再次获取一下,这时候是肯定不为空 registry = registries.get(registryAddress); } return registry; }
下面介绍一种利用自旋的方式来解决这个“只创建一次”的问题。
1. 由于在Map里面有多个key同时并发,而每个key对应的对象只创建一次,所以需要一个支持多个key同时并发时为每一个key找到第一个成功设置的线程的数据结构。可以用一个并发Map来实现这个功能
2. 需要为每一个key的都设置一个“自旋”状态,来控制每一个key对应的并发线程的同步状态。因为我们无法预知有多少个key,所以不能预先就创建这个状态,只有在进入并发段时才能创建。记录这个“自旋”状态需要保证这个状态是多线程可见的,所以可以是volatile变量,也可以是原子变量比如AtomicBoolean。如果使用volatile变量来记录这个状态,必须要创建一个对象来封装这个volatile状态,因为局部变量不能被声明为volatile。
3. 使用ConcurrrentMap的putIfAbsent()方式做CAS操作,只有第一个成功执行这个方法的线程拿到的返回值是null,后续的线程拿到的返回值是第一个成功放入的value。所以我们可以使用putAbsent(key, SpinStatus)做两个事情:
- 找到第一个成功执行方法的线程
- 有第一个成功执行方法的线程来设置一个共享的“自旋”状态的对象,后续线程执行putIfAbsent()方法后能拿到这个共享状态
4. 第一个成功执行putIfAbsent方法的线程来状态唯一的对象,创建成功后设置共享的“自旋”状态对象,释放其他自旋的线程。
5. 其他没有第一个成功执行putIfAbsent方法的线程在共享的“自旋”对象上自旋,直到被通知释放
6. 最后其他线程往下执行后再取一次registry的值,这时候并发Map能保证所有的线程能看到registry引用最新的状态
这个实现利用了自旋的一些技巧,无锁的解决了“只创建一次”的问题,并且真正的只创建了一次对象。只有第一次多个线程进入到(registry == null)这个分支时才会进行并发的同步,之后所有的请求会直接拿到创建成功的对象。是一个性能不错的实现。
// 记录自旋状态的轻量级类,只封装了一个volatile状态 public static class SpinStatus{ volatile boolean released; } // 辅助并发控制的Map,用来找出每个key对应的第一个成功进入的线程 private ConcurrentMap<String, SpinStatus> raceUtil = new ConcurrentHashMap<String, SpinStatus>(); // 无锁实现单实例Registry的创建 public Registry getRegistry(String registryAddress){ Registry registry = registries.get(registryAddress); // 第一次创建 if(registry == null){ // 需要为并发的线程new一个自旋状态,只有第一个成功执行putIfAbsent方法的线程设置的SpinStatus会被共享 SpinStatus spinStatus = new SpinStatus(); SpinStatus oldSpinStatus = raceUtil.putIfAbsent(registryAddress, spinStatus); // 只有第一个执行成功的线程拿到的oldSpinStatus是null,其他线程拿到的oldSpinStatus是第一个线程设置的,可以在所有线程中共享 if(oldSpinStatus == null){ // 创建对象 registry = createRegistry(); // 放入共享的并发Map,后续线程执行get()方法后可以直接拿到非null的引用返回 registries.put(registryAddress, registry); // 释放其他自旋的线程,注意,对第一个成功执行的线程使用的是spinStatus的引用 spinStatus.released = true; }else{ // 其他线程在oldSpinStatus引用所指向的共享自旋状态上自旋,等等被释放 while(!oldSpinStatus.released){}; } // 再次获取一下,这时候是肯定不为空 registry = registries.get(registryAddress); } return registry; }
我们设计一个测试用例来测试这个无锁的实现方式是否真的能够为Map里的每一个key对应的value创建唯一的对象。
1. 10个线程并发的设置key "One", 10个线程并发的设置key "Two"。结果要求One和Two对应的对象只能被创建一次
2. 要保证所有20个线程都执行了
所以设计了一个SingletonObject类来记录了它对应的key信息和Count信息,10个线程创建key为One的SingletonObject对象,10个线程创建key为Two的SingletonObject对象。
其他和上面的例子一样,创建轻量级的一个SpinStatus类来记录自旋状态,使用一个并发Map辅助并发控制
package com.lock.test; import java.util.concurrent.ConcurrentHashMap; import java.util.concurrent.ConcurrentMap; import java.util.concurrent.atomic.AtomicBoolean; import java.util.concurrent.atomic.AtomicInteger; public class MultiEntrySingletonTest { // 记录自旋状态的轻量级类,只封装了一个volatile状态 public static class SpinStatus{ volatile boolean released; } // 辅助并发控制的Map,用来找出每个key对应的第一个成功进入的线程 private ConcurrentMap<String, SpinStatus> raceUtil = new ConcurrentHashMap<String, SpinStatus>(); private ConcurrentMap<String, Singleton> map = new ConcurrentHashMap<String, MultiEntrySingletonTest.Singleton>(); public Singleton creataeObjectOneTime(String key){ Singleton obj = map.get(key); if(obj == null){ System.out.println("Multiple threads concurrent race for key: " + key); // 需要为并发的线程new一个自旋状态,只有第一个成功执行putIfAbsent方法的线程设置的SpinStatus会被共享 SpinStatus spinStatus = new SpinStatus(); SpinStatus oldSpinStatus = raceUtil.putIfAbsent(key, spinStatus); // 只有第一个执行成功的线程拿到的oldSpinStatus是null, //其他线程拿到的oldSpinStatus是第一个线程设置的,可以在所有线程中共享 if(oldSpinStatus == null){ // 创建对象 obj = new SingletonObject(key); // 放入共享的并发Map,后续线程执行get()方法后可以直接拿到非null的引用返回 map.put(key, obj); // 释放其他自旋的线程,注意,对第一个成功执行的线程使用的是spinStatus的引用 spinStatus.released = true; }else{ // 其他线程在oldSpinStatus引用所指向的共享自旋状态上自旋,等等被释放 while(!oldSpinStatus.released){}; } obj = map.get(key); } return obj; } public static void main(String[] args){ final MultiEntrySingletonTest lockFree = new MultiEntrySingletonTest(); for(int i = 0; i < 10; i++){ Thread t = new Thread(new Runnable() { @Override public void run() { Singleton s = lockFree.creataeObjectOneTime("One"); s.printCount(); } }); t.start(); } for(int i = 0; i < 10; i++){ Thread t = new Thread(new Runnable() { @Override public void run() { Singleton s2 = lockFree.creataeObjectOneTime("Two"); s2.printCount(); } }); t.start(); } } private static class SingletonObject{ AtomicInteger count = new AtomicInteger(0); String key; public SingletonObject(String key){ this.key = key; System.out.println("Object created for key: " + key); } public void printCount(){ System.out.println("Count " + count.incrementAndGet() + " for key: " + key); } } }
测试结果中可以看到Key One和Two对应的对象都只创建了一次,并且有多个线程同时进入了竞争段。计数器显示了所有的线程都并发执行了这个方法,这里不需要保证先来先服务的公平性,所以Count的顺序是无序的,但是每个线程的Count都执行了。
证明这种无锁的设计是正确的。
Multiple threads concurrent race for key: One Multiple threads concurrent race for key: One Multiple threads concurrent race for key: One Multiple threads concurrent race for key: One Multiple threads concurrent race for key: One Multiple threads concurrent race for key: One <strong>Object created for key: One</strong> Count 2 for key: One Count 4 for key: One Count 3 for key: One Count 6 for key: One Count 1 for key: One Count 5 for key: One Count 7 for key: One Count 8 for key: One Count 9 for key: One Count 10 for key: One Multiple threads concurrent race for key: Two <strong>Object created for key: Two</strong> Count 1 for key: Two Multiple threads concurrent race for key: Two Count 2 for key: Two Multiple threads concurrent race for key: Two Count 4 for key: Two Count 3 for key: Two Count 5 for key: Two Count 6 for key: Two Count 7 for key: Two Count 8 for key: Two Count 9 for key: Two Count 10 for key: Two
http://blog.csdn.net/iter_zc