分段锁的原理

分段锁的原理

前言:在分析ConcurrentHashMap的源码的时候,了解到这个并发容器类的加锁机制是基于粒度更小的分段锁,分段锁也是提升多并发程序性能的重要手段之一。

在并发程序中,串行操作是会降低可伸缩性,并且上下文切换也会减低性能。在锁上发生竞争时将通水导致这两种问题,使用独占锁时保护受限资源的时候,基本上是采用串行方式—-每次只能有一个线程能访问它。所以对于可伸缩性来说最大的威胁就是独占锁。

我们一般有三种方式降低锁的竞争程度:
1、减少锁的持有时间
2、降低锁的请求频率
3、使用带有协调机制的独占锁,这些机制允许更高的并发性。

在某些情况下我们可以将锁分解技术进一步扩展为一组独立对象上的锁进行分解,这成为分段锁。其实说的简单一点就是:容器里有多把锁,每一把锁用于锁容器其中一部分数据,那么当多线程访问容器里不同数据段的数据时,线程间就不会存在锁竞争,从而可以有效的提高并发访问效率,这就是ConcurrentHashMap所使用的锁分段技术,首先将数据分成一段一段的存储,然后给每一段数据配一把锁,当一个线程占用锁访问其中一个段数据的时候,其他段的数据也能被其他线程访问。

比如:在ConcurrentHashMap中使用了一个包含16个锁的数组,每个锁保护所有散列桶的1/16,其中第N个散列桶由第(N mod 16)个锁来保护。假设使用合理的散列算法使关键字能够均匀的分部,那么这大约能使对锁的请求减少到越来的1/16。也正是这项技术使得ConcurrentHashMap支持多达16个并发的写入线程。

当然,任何技术必有其劣势,与独占锁相比,维护多个锁来实现独占访问将更加困难而且开销更加大。

下面给出一个基于散列的Map的实现,使用分段锁技术。 import java.util.Map;

/**
* Created by louyuting on 17/1/10.
*/
public class StripedMap {
 //同步策略: buckets[n]由 locks[n%N_LOCKS] 来保护

 private static final int N_LOCKS = 16;//分段锁的个数
 private final Node[] buckets;
 private final Object[] locks;

 /**
  * 结点
  * @param <K>
  * @param <V>
  */
 private static class Node<K,V> implements Map.Entry<K,V>{
   final K key;//key
   V value;//value
   Node<K,V> next;//指向下一个结点的指针
   int hash;//hash值

   //构造器,传入Entry的四个属性
   Node(int h, K k, V v, Node<K,V> n) {
     value = v;
     next = n;//该Entry的后继
     key = k;
     hash = h;
   }

   public final K getKey() {
     return key;
   }

   public final V getValue() {
     return value;
   }

   public final V setValue(V newValue) {
     V oldValue = value;
     value = newValue;
     return oldValue;
   }

 }

 /**
  * 构造器: 初始化散列桶和分段锁数组
  * @param numBuckets
  */
 public StripedMap(int numBuckets) {
   buckets = new Node[numBuckets];
   locks = new Object[N_LOCKS];

   for(int i=0; i<N_LOCKS; i++){
     locks[i] = new Object();
   }

 }

 /**
  * 返回散列之后在散列桶之中的定位
  * @param key
  * @return
  */
 private final int hash(Object key){
   return Math.abs(key.hashCode() % N_LOCKS);
 }


 /**
  * 分段锁实现的get
  * @param key
  * @return
  */
 public Object get(Object key){
   int hash = hash(key);//计算hash值

   //获取分段锁中的某一把锁
   synchronized (locks[hash% N_LOCKS]){
     for(Node m=buckets[hash]; m!=null; m=m.next){
       if(m.key.equals(key)){
         return m.value;
       }
     }
   }

   return null;
 }

 /**
  * 清除整个map
  */
 public void clear() {
   //分段获取散列桶中每个桶地锁,然后清除对应的桶的锁
   for(int i=0; i<buckets.length; i++){
     synchronized (locks[i%N_LOCKS]){
       buckets[i] = null;
     }
   }
 }
}

上面的实现中:使用了N_LOCKS个锁对象数组,并且每个锁保护容器的一个子集,对于大多数的方法只需要回去key值的hash散列之后对应的数据区域的一把锁就行了。但是对于某些方法却要获得全部的锁,比如clear()方法,但是获得全部的锁不必是同时获得,可以使分段获得,具体的查看源码。

这就是分段锁的思想。

本文来源于网络,主要摘自:

https://blog.csdn.net/u010853261/article/details/54314486