关于锁的一些思考

尽量减小因为引入锁而带来的影响,有以下几个思考点

尽量减小锁的范围

在实现跳表时,我定义的节点数据结构如下

1
2
3
4
5
6
class Node<K extends Comparable<K>, V> {
K key;
V value;
int level;
Node<K, V>[] next;
}

传统跳表结构示意图

在读写跳表,都要通过lock加锁,来进行链表节点的插入,删除等操作
而一个节点里,我还定义指向level个后续节点的指针数组next,插入步骤为:

  1. 在0~level-1层,寻找插入位置,并记录插入位置
  2. 执行单链表插值操作
    整个过程是加锁的,但是对读取操作来说,只关心key对应的value,也就是数据域
    但是加锁包含了数据域和level个指针域,这说明锁的范围过大了

那么jdk中的ConcurrentSkipListMap是如何构建数据结构的呢?

1
2
3
4
5
6
7
8
9
10
static final class Node<K,V> {
final K key; // currently, never detached
V val;
Node<K,V> next;
}
static final class Index<K,V> {
final Node<K,V> node; // currently, never detached
final Index<K,V> down;
Index<K,V> right;
}

Node明显是个单链表,它存储了数据域,也就是说它只存在第0层
Index是1-level层才有的,node指向了第0层的数据域,right指向后继,方便增删,down指向下一层的Index
这样数据域和指针域分离,配合cas这类无锁操作插入Node和Index,大大提升了并发度
jdk跳表结构示意图

锁只保护和竞态资源有关的代码

1
2
3
4
5
6
7
8
9
int count = 0;
Lock lok;
public void add() {
some code ...
lok.lock();
count++;
lok.unlock();
some code ...
}

认真思考锁要保护的竞态资源有哪些,每个有多大

如果有多个竞态资源, 又存在多个需要同步的代码块,那么需要考虑分解锁的粒度,比如
add1方法只需要获取lock1,add2方法只需要获取lock2
假如thread1调用add1, 就不应该应该thread2调用add2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int race1 = 0;
int race2 = 0;
Lock lock1; // for race1
Lock lock2; // for race2

public add1() {
lock1.lock();
race1++;
lock1.unlock();
}

public add2() {
lock2.lock();
race2++;
lock2.unlock();
}
文章作者: 紫夜
文章链接: https://greedypirate.github.io/2025/02/19/关于锁的一些思考/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 紫夜の博客