分段锁的原理

前言:在分析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

原文发布于微信公众号 - Spark学习技巧(bigdatatip)

原文发表时间:2018-04-02

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Spark学习技巧

Flink DataStream编程指南及使用注意事项。

Flink中的DataStream程序是对数据流进行转换的常规程序(例如,过滤,更新状态,定义窗口,聚合)。数据流的最初的源可以从各种来源(例如,消息队列,套接...

1.4K7
来自专栏codelang

React Native通信原生Android

1663
来自专栏北京马哥教育

shell十三问,为linux学习打基础(一)

本文整理并转自CU上的帖子[学习共享] shell 十三問?,此贴是2003年发表的,但却是相当不错的linux基础知识汇集贴,原帖主使用的台湾风格,本文加以简...

3554
来自专栏pangguoming

JS生成UUID

一、UUID是什么   UUID就是Universal Unique IDentifier的缩写,它是一个128位,16字节的值,并确保在时间和空间上唯一。 它...

6778
来自专栏Java开发者杂谈

For update带来的思考

​ 之所以想写这个专题,是因为最近在做一个抢占任务的实现。假设数据库很多个任务,在抢占发生之前任务的状态都是FREE。现在假设同时有一堆抢占线程开始工作,抢占线...

1173
来自专栏happyJared

Elasticsearch地理坐标类型(Geo-point)在Spring Data ES中的常见使用问题整理解答

  下文整理的几个问答,本人在实际应用中亲身经历或解决过的,主要涉及Elasticsearch地理坐标类型(Geo-point)在Java应用中的一些特殊使用场...

2481
来自专栏水击三千

UML学习-状态图

1.状态图概述 状态图(Statechart Diagram)主要用于描述一个对象在其生存期间的动态行为,表现为一个对象所经历的状态序列,引起状态转移的事件(E...

26710
来自专栏我杨某人的青春满是悔恨

Swift2网络操作和异常处理

相信写过Swift的人应该都知道Alamofire,它是AFNetworking的Swift版本,同一个作者写的。之前在项目中我也一直使用Alamofire,但...

951
来自专栏何俊林

Android Multimedia框架总结(九)Stagefright框架之数据处理及到OMXCodec过程

不知不觉到第九篇了,感觉还有好多好多没有写,路漫漫其修远兮 ,吾将上下而求索。先说福利吧,此前在关于我, ? 曾说过,不定期搞活动,vip,书啥的,都可以有,...

2256
来自专栏数值分析与有限元编程

Python IDLE关联.py文件

为进一步提升Python IDLE可操作性,本文介绍如何在windows操作系统下默认使用python自带的IDLE编辑器关联后缀名为.py的文件。

4031

扫码关注云+社区