Java5 Concurrent包中的锁机制

        JDK1.5以后加入了concurrent包，主要是为了提高多线程的开发效率，其中提供了很多支持并发的集合类，其中包括：ConcurrentHashMap。大家知道HashTable也是支持并发环境的，也就是说多线程安全的，那两者有什么区别呢？

分析

        其实简单的说是同步机制有区别，具体区别又在那里呢？

        请看HashTable的put方法：

/**
     * Maps the specified <code>key</code> to the specified
     * <code>value</code> in this hashtable. Neither the key nor the
     * value can be <code>null</code>. <p>
     *
     * The value can be retrieved by calling the <code>get</code> method
     * with a key that is equal to the original key.
     *
     * @param      key     the hashtable key
     * @param      value   the value
     * @return     the previous value of the specified key in this hashtable,
     *             or <code>null</code> if it did not have one
     * @exception  NullPointerException  if the key or value is
     *               <code>null</code>
     * @see     Object#equals(Object)
     * @see     #get(Object)
     */
    public synchronized V put(K key, V value) {
	// Make sure the value is not null
	if (value == null) {
	    throw new NullPointerException();
	}

	// Makes sure the key is not already in the hashtable.
	Entry tab[] = table;
	int hash = key.hashCode();
	int index = (hash & 0x7FFFFFFF) % tab.length;
	for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
	    if ((e.hash == hash) && e.key.equals(key)) {
		V old = e.value;
		e.value = value;
		return old;
	    }
	}

	modCount++;
	if (count >= threshold) {
	    // Rehash the table if the threshold is exceeded
	    rehash();

            tab = table;
            index = (hash & 0x7FFFFFFF) % tab.length;
	}

	// Creates the new entry.
	Entry<K,V> e = tab[index];
	tab[index] = new Entry<K,V>(hash, key, value, e);
	count++;
	return null;
    }

     代码中使用synchronized函数的方式进行同步，这个类的其他方法也是使用这个机制进行同步的。我们先来大致了解一下synchronized的机制：

     在多线程环境中，Java的对象都会隐式的包含有一个同步队列，其中类会有一个，然后每个类实例也会包含一个。如图：

 

class Foo {
      synchronized void doSomething(); // 把同步的线程放入类实例的同步队列
      synchronized static void doSomething(); //把同步的线程放入类的同步队列
}

 

 然后我们再来看看ConcurrentHashMap 的put方法：

//ConcurrentHashMap
public V put(K key, V value) {
        if (value == null)
            throw new NullPointerException();
        int hash = hash(key.hashCode());
        return segmentFor(hash).put(key, hash, value, false);
    }

//Segment内部类，继承至ReentrantLock
V put(K key, int hash, V value, boolean onlyIfAbsent) {
            lock();
            try {
                int c = count;
                if (c++ > threshold) // ensure capacity
                    rehash();
                HashEntry<K,V>[] tab = table;
                int index = hash & (tab.length - 1);
                HashEntry<K,V> first = tab[index];
                HashEntry<K,V> e = first;
                while (e != null && (e.hash != hash || !key.equals(e.key)))
                    e = e.next;

                V oldValue;
                if (e != null) {
                    oldValue = e.value;
                    if (!onlyIfAbsent)
                        e.value = value;
                }
                else {
                    oldValue = null;
                    ++modCount;
                    tab[index] = new HashEntry<K,V>(key, hash, first, value);
                    count = c; // write-volatile
                }
                return oldValue;
            } finally {
                unlock();
            }
        }

 

ReentrantLock就是Java Concurrent包提供的锁对象，Lock的使用方法大致如下：

     Lock l = ...;
     l.lock();
     try {
         // access the resource protected by this lock
     } finally {
         l.unlock();
     }

 

为什么使用Lock对象会比使用synchronized有更好的性能呢？我们再来看看ReentrantLock的实现：

public class ReentrantLock implements Lock, java.io.Serializable {
    private static final long serialVersionUID = 7373984872572414699L;
    /** Synchronizer providing all implementation mechanics */
    private final Sync sync;

    /**
     * Base of synchronization control for this lock. Subclassed
     * into fair and nonfair versions below. Uses AQS state to
     * represent the number of holds on the lock.
     */
    static abstract class Sync extends AbstractQueuedSynchronizer {
        private static final long serialVersionUID = -5179523762034025860L;
..........
...........

 我们从中看到ReentrantLock对象也维护着一个同步队列，性能差别就在于这个队列的实现上，我们再来看AbstractQueuedSynchronizer的代码：

 /**
     * Inserts node into queue, initializing if necessary. See picture above.
     * @param node the node to insert
     * @return node's predecessor
     */
    private Node enq(final Node node) {
        for (;;) {
            Node t = tail;
            if (t == null) { // Must initialize
                Node h = new Node(); // Dummy header
                h.next = node;
                node.prev = h;
                if (compareAndSetHead(h)) {
                    tail = node;
                    return h;
                }
            }
            else {
                node.prev = t;
                if (compareAndSetTail(t, node)) {
                    t.next = node;
                    return t;
                }
            }
        }
    }

/**
     * CAS head field. Used only by enq
     */
    private final boolean compareAndSetHead(Node update) {
        return unsafe.compareAndSwapObject(this, headOffset, null, update);//使用compare and swap方式
    }

    /**
     * CAS tail field. Used only by enq
     */
    private final boolean compareAndSetTail(Node expect, Node update) {
        return unsafe.compareAndSwapObject(this, tailOffset, expect, update);//使用compare and swap方式
    }

 

到了Unsafe.java这里就要通过本地代码实现了，下面是kaffe里面的本地代码实现：

/**
 * Helper macro, defining a sun.misc.Unsafe compare and swap function 
 * with a given NAME tail and TYPE of arguments.
 */
#define KAFFE_UNSAFE_COMPARE_AND_SWAP(NAME, TYPE)
JNIEXPORT jboolean JNICALL Java_sun_misc_Unsafe_compareAndSwap ## NAME(JNIEnv* env, jobject unsafe UNUSED, jobject obj, jlong offset, TYPE expect, TYPE update) 
{ 
  volatile TYPE * address = getFieldAddress(env, obj, offset); 
  if (sizeof(TYPE) == sizeof(gint)) 
    return g_atomic_int_compare_and_exchange((volatile gint *) address, (gint) expect, (gint) update); 
  else if (sizeof(TYPE) == sizeof(gpointer)) 
    return g_atomic_pointer_compare_and_exchange((volatile gpointer *) address, (gpointer) expect, (gpointer) update); 
  else 
    if (*address == expect) { 
      *address = update; 
      return JNI_TRUE; 
    } 
    else 
      return JNI_FALSE; 
} 

再看glib的代码：

gboolean g_atomic_int_compare_and_exchange (volatile gint *atomic, 
				   gint           oldval, 
				   gint           newval)
{
  gint result;
 
  __asm__ __volatile__ ("lock; cmpxchgl %2, %1"
			: "=a" (result), "=m" (*atomic)
			: "r" (newval), "m" (*atomic), "0" (oldval)); 

  return result == oldval;
}

 AT&T汇编，

一条指令总会是原子性的了吧

 

总结

     concurrent包中大量使用了新的锁机制，新的Lock机制最终归结到一个原子性操作上，所以会比使用synchronized关键字有更高的性能。

 

 

参考

关于Java多线程的一个PPT

评论

19 楼 fei33423 2014-06-14  

楼主为啥不根据评论改下文章..不然会误导很多人的..

18 楼 harry 2009-02-23  

pior 写道

并发真是很头疼的问题`有时候出的很莫名其妙``````不想面对`但又不得不去面对``

遵寻一些模式，使用一些封装好的库（特别是JDK中自带的一些类库），减少代码量，应该会好很多

17 楼 pior 2009-02-23  

并发真是很头疼的


问题`有时候出的很莫名其妙``````



不想面对`但又不得不去面对``

16 楼 llq056 2009-02-23  

佩服

15 楼 rmn190 2009-02-20  

佩服楼主对问题群追猛大,一直"杀"到的底的魄力!

14 楼 ahuaxuan 2009-02-17  

引用

The allowed concurrency among update operations is guided by the optional concurrencyLevel constructor argument (default 16), which is used as a hint for internal sizing. The table is internally partitioned to try to permit the indicated number of concurrent updates without contention. Because placement in hash tables is essentially random, the actual concurrency will vary. Ideally, you should choose a value to accommodate as many threads as will ever concurrently modify the table. Using a significantly higher value than you need can waste space and time, and a significantly lower value can lead to thread contention. But overestimates and underestimates within an order of magnitude do not usually have much noticeable impact. A value of one is appropriate when it is known that only one thread will modify and all others will only read. Also, resizing this or any other kind of hash table is a relatively slow operation, so, when possible, it is a good idea to provide estimates of expected table sizes in

这个是ConcurrentHashMap类注释的一部分,注意这个词"concurrencyLevel"它的默认值是16.

锁分离是并发编程中比较常用技术,但是将锁分离用在hashmap上是有一定难度的,hashmap是数组+链表(桶)实现的,而且随着元素的增多,还会产生rehash操作,这样每把分离锁的作用域也会改变,对并发没有一定见地的人是写不出来的

13 楼 AlwenS 2009-02-17  

julyboxer 写道

ConcurrentHashMap的性能优异的原因是把Map分离成多份，这样更新的时候只要锁定其中一份，而不需要全部锁住。就像数据库中只需要锁定其中一行，而不需要锁住全表的道理类似。。

正解!

12 楼 aidown 2009-02-17  

你可以这么理解

synchronized是jvm内部实现的;
而Concurrent是用Java语言写出来的(就是用java语言把synchronized在jvm内部实现写出来);依靠cpu的cas实现,感觉像乐观锁;

segments那个只是concurrentHashMap里面的一种优化

上面是仅仅是个人理解,

11 楼 sdh5724 2009-02-17  

synchronize写程序很麻烦， 不容易操作 并发包解决了这些问题。

10 楼 beneo 2009-02-17  

dennis_zane 写道

harry 写道

dennis_zane 写道

似乎没有证据表明synchronize的内部锁最后转化的不是一个原子性操作？
就我所知，ReentrantLock跟synchronize在jdk1.6上的性能差距已经极小，ReentrantLock更多应用在需要细粒度控制加锁范围和特殊加锁功能（tryLock、超时等）的场景下。ConcurrentHashMap的性能优异更多的原因是采用了分离锁的策略带来的，而非是这个方面的区别。

分离锁的策略是指？

就是二楼所说的策略，ConcurrentHashMap是将内部的数组分成了16份，用16个锁来分别同步，这样并发的put、get可以大大加快，但是对于整个map的独占访问将变的更昂贵(如size())。

曾今在IBM DEV上面看到類似的文章，一個人寫的Java理论与实践專題裡面。

9 楼 harry 2009-02-17  

dennis_zane 写道

harry 写道dennis_zane 写道
似乎没有证据表明synchronize的内部锁最后转化的不是一个原子性操作？
就我所知，ReentrantLock跟synchronize在jdk1.6上的性能差距已经极小，ReentrantLock更多应用在需要细粒度控制加锁范围和特殊加锁功能（tryLock、超时等）的场景下。ConcurrentHashMap的性能优异更多的原因是采用了分离锁的策略带来的，而非是这个方面的区别。

分离锁的策略是指？

就是二楼所说的策略，ConcurrentHashMap是将内部的数组分成了16份，用16个锁来分别同步，这样并发的put、get可以大大加快，但是对于整个map的独占访问将变的更昂贵(如size())。

3KU，刚仔细的研究了一下，确实是这样的。
ConcurrentHashMap内部的数组分成若干个Segment，每个Segment持有一个数组，通过segmentFor知道位于那个Segment中

final Segment<K,V> segmentFor(int hash) {
        return segments[(hash >>> segmentShift) & segmentMask];
    }

8 楼 dennis_zane 2009-02-17  

harry 写道

dennis_zane 写道

似乎没有证据表明synchronize的内部锁最后转化的不是一个原子性操作？
就我所知，ReentrantLock跟synchronize在jdk1.6上的性能差距已经极小，ReentrantLock更多应用在需要细粒度控制加锁范围和特殊加锁功能（tryLock、超时等）的场景下。ConcurrentHashMap的性能优异更多的原因是采用了分离锁的策略带来的，而非是这个方面的区别。

分离锁的策略是指？

就是二楼所说的策略，ConcurrentHashMap是将内部的数组分成了16份，用16个锁来分别同步，这样并发的put、get可以大大加快，但是对于整个map的独占访问将变的更昂贵(如size())。

7 楼 srdrm 2009-02-17  

楼主给我们展现了concurrenthashmap 的不少内幕，感谢。至少我一直以为这个类是 lock-free 的， 原来不是。。。

6 楼 harry 2009-02-17  

dennis_zane 写道

似乎没有证据表明synchronize的内部锁最后转化的不是一个原子性操作？
就我所知，ReentrantLock跟synchronize在jdk1.6上的性能差距已经极小，ReentrantLock更多应用在需要细粒度控制加锁范围和特殊加锁功能（tryLock、超时等）的场景下。ConcurrentHashMap的性能优异更多的原因是采用了分离锁的策略带来的，而非是这个方面的区别。

分离锁的策略是指？

5 楼 harry 2009-02-17  

julyboxer 写道

ConcurrentHashMap的性能优异的原因是把Map分离成多份，这样更新的时候只要锁定其中一份，而不需要全部锁住。就像数据库中只需要锁定其中一行，而不需要锁住全表的道理类似。。

这个没注意，我再去研究一下，呵呵

4 楼 whaosoft 2009-02-17  

学习一下!~!~

3 楼 galaxystar 2009-02-16  

典型的 CAS 原语使用场景.

2 楼 julyboxer 2009-02-16  

ConcurrentHashMap的性能优异的原因是把Map分离成多份，这样更新的时候只要锁定其中一份，而不需要全部锁住。就像数据库中只需要锁定其中一行，而不需要锁住全表的道理类似。。

1 楼 dennis_zane 2009-02-16  

似乎没有证据表明synchronize的内部锁最后转化的不是一个原子性操作？
就我所知，ReentrantLock跟synchronize在jdk1.6上的性能差距已经极小，ReentrantLock更多应用在需要细粒度控制加锁范围和特殊加锁功能（tryLock、超时等）的场景下。ConcurrentHashMap的性能优异更多的原因是采用了分离锁的策略带来的，而非是这个方面的区别。