分段锁的原理

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

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

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

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Java面试官最爱的volatile关键字

    在Java相关的岗位面试中,很多面试官都喜欢考察面试者对Java并发的了解程度,而以volatile关键字作为一个小的切入点,往往可以一问到底,把Java内存模...

    Spark学习技巧
  • Java 性能优化的 45 个细节

    在JAVA程序中,性能问题的大部分原因并不在于JAVA语言,而是程序本身。养成良好的编码习惯非常重要,能够显著地提升程序性能。

    Spark学习技巧
  • 面试 | Java8 HashMap原理

    基于Map接口实现、允许null键/值、非同步、不保证有序(比如插入的顺序)、也不保证顺序不随时间变化。

    Spark学习技巧
  • [LeetCode]Merge Sorted Array 合并排序数组 [LeetCode]Merge Sorted Array 合并排序数组

    链接:https://leetcode.com/problems/merge-sorted-array/description/ 难度:Easy 题目:88...

    尾尾部落
  • Leetcode Golang 88. Merge Sorted Array.go

    版权声明:原创勿转 https://blog.csdn.net/anakinsun/article/details/88935287

    anakinsun
  • ACM算法基础

    N3/6-N2/2+N/3 ~ N3/6。使用 ~f(N) 来表示所有随着 N 的增大除以 f(N) 的结果趋近于 1 的函数。

    爱撸猫的杰
  • 视频负载测试

    本篇是来自Video @Scale 2019的演讲,演讲者是来自亚马逊Resilience Engineering部门的Olga Hall,演讲题目为“Vide...

    用户1324186
  • LeetCode刷题DAY 22:合并两个有序数组

    给定两个有序整数数组 nums1 和 nums2,将nums2合并到nums1中,使nums1成为一个有序数组。如:

    三猫
  • Python range() 函数

    range()是python的内置函数,用的地方挺多的,目前我经常会在for循环中作为循环的次数来使用,其实range()的用法不仅仅如此,本文给大家介绍下。

    py3study
  • 我潜入清华神秘实验室,用脑机接口写了两句诗

    量子位

扫码关注云+社区

领取腾讯云代金券