深入理解 ReentrantLock

本文是对 ReentrantLock 源码的分析以及总结，详细介绍了其是实现公平与非公平锁的加解锁的原理、其与 AbstractQueuedSynchronizer 的关联。 简介 可重入锁是 JUC 包中提供的一种可重入的互斥锁，其实现基于 [[AbstractQueuedSynchronizer]] ， Java 源码的注释很好的说明了 ReentrantLock 是什么： ReentrantLock 和 Java synchronized 的语义一致，但包含更多的功能。 A reentrant mutual exclusion Lock with the same basic behavior and semantics as the implicit monitor lock accessed using synchronized methods and statements, but with extended capabilities. 代码结构 AQS 和其实现类之间的关系属于模板方法：AQS 提供基础的算法框架，实现类实现抽象方法来实现自己独特的功能和语义。 AbstractQueuedSynchronizer 的源码注释中有这么一段话，很好地说明了 AQS 与 JUC 包中具体同步器之间的关系： Subclasses should be defined as non-public internal helper classes that are used to implement the synchronization properties of their enclosing class.

AbstractQueuedSynchronizer 简介

本文主要介绍了 JUC 中的 AbstractQueuedSynchronizer 的实现基础、其和 CLH 队列锁之间的关联、独占锁模式及共享锁模式加解锁的过程等。不包含 ConditionObject 的分析。 简介 AQS 提供了实现同步阻塞队列的基本框架，是 juc 包中其他众多同步原语和锁实现的基础。 Provides a framework for implementing blocking locks and related synchronizers (semaphores, events, etc) that rely on first-in-first-out (FIFO) wait queues. This class is designed to be a useful basis for most kinds of synchronizers that rely on a single atomic int value to represent state. Subclasses must define the protected methods that change this state, and which define what that state means in terms of this object being acquired or released.

深入理解 CLH Queue Lock

JUC 包中的很多同步原语是基于 AbstractQueuedSynchronizer（以下简称 AQS） 实现的，而 AQS 的实现又是基于 CLH 队列锁（CLH queued lock），因此学习并理解 CLH 队列锁对我们学习 JUC 中的各种同步原语非常有帮助。本文将阐述 CLH 队列锁的实现和原理。 CLH Queue Lock CLH 队列锁是由 Craig, Landin, Hagersten 三位大佬提出的，因此被称为 CLH 队列锁，它是一种自旋公平锁，基于虚链表实现（virtual linked list）。 《The Art of Multiprocessor Programming》7.5.2 节给出了 CLH 可能的一种 Java 语言实现： public class CLHLock implements Lock { AtomicReference<QNode> tail; ThreadLocal<QNode> myPred; ThreadLocal<QNode> myNode; public CLHLock() { tail = new AtomicReference<QNode>(new QNode()); myNode = new ThreadLocal<QNode>() { protected QNode initialValue() { return new QNode(); } }; myPred = new ThreadLocal<QNode>() { protected QNode initialValue() { return null; } }; } public void lock() { QNode qnode = myNode.

LeetCode 笔记 5：Search in Rotated Sorted Array

今天要讲的题目都使用到了二分查找（或者和二分查找紧密相关），同时又都是基于一个 Rotated Sorted Array。那么先从 Rotated Sorted Array 的特点讲起吧。 Rotated Sorted Array 的定义是这样子的： There is an integer array nums sorted in ascending order (with distinct values). nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). 就拿 int[] nums = new int[]{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; 举例好了，如果 nums 在 nums[4] 位置进行旋转，那么它将变成： {4, 5, 6, 7, 8, 9, 10, 0, 1, 2, 3} ，那么我们能够观察到几个特性：

深入理解 B+ Tree

B+ 树的定义和 B 树是类似的，B+ 树在数据结构上进行了一定的改进，它的特性使得它的某些场景下教 B 树有了显著的优势。本文笔者将对 B+ 树的定义、特点以及应用进行详细解析。 定义 B+ 树和 B 树的定义是类似的，它们都是平衡多路搜索树，在文件系统和数据库系统中都有大量的应用。只不过 B+ 树有以下几点独特的属性： B+ 树的非叶子结点不包含值（value），只存储键（key） B+ 树的叶子结点之间是互相连接的，B+ 树叶子结点这一层构成了一个双向链表（Doubly linked list） B+ 树的叶子结点这一层存储了所有数据的 key-links pairs，而 B 树的所有数据是散布在整棵树中的，B 树的叶子结点这一层只存储了数据全集的一部分。 B+ 树的查找、添加、删除算法和 B 树是类似的，可以参考笔者的上一篇博客进行了解：深入理解 B-Tree | caffcen’s blog，在此不在赘述。 特性 对于阶数为 m 的 B+ 树，它拥有如下性质： 每个节点最多有 m 个子节点。 每个节点最多有 m-1 个键值。 每个内部节点至少有 ⌈m/2⌉ 个子节点，根节点除外。 根节点至少有 2 个子节点。 所有叶子节点出现在同一层级上，叶子结点与叶子结点之间有双向引用，叶子结点这一层构成了一条双向链表。 一个具有 k 个子节点的非叶节点包含 k-1 个键值。 叶子结点这一层存储了所有数据（所有的 key-link pairs） B-Tree vs. B+ Tree B 树和 B+ 树的区别对比，可以参考 Stack Overflow 这个问题：database - What are the differences between B trees and B+ trees?