最近在阅读 Java 并发编程之美这本书,感觉学到了很多东西;所以我决定将从事书中学到的思想和一些经典的案例整理成博客的形式与大家分享和交流,如果对大家有帮助别忘了留下点赞和关注捏。
3.1)Random 类的局限性
在 JDK1.7 之前,java.util.Random 都是应用比较广泛的随机数生成工具,java.lang.Math 中的随机数生成也是使用的 Random 的实例。
写一段代码来测试一下 Random 实例:
public class RandomTest {
public static void main(String[] args) {
Random random = new Random();
for (int i = 1; i < 10; i++) {
// 输出 10 个在 0 到 5 之间的随机数,不包括 5
System.out.println(random.nextInt(5));
}
}
}
上面展示了一个随机数生成器,生成 10 个 0 到 5 之间的随机数,下面来看一下具体的实现:
public int nextInt(int bound) {
if (bound <= 0) // 参数检验
throw new IllegalArgumentException(BadBound);
int r = next(31); // 生成一个 31 位的随机正数 r
int m = bound - 1;
if ((bound & m) == 0) // 判断 bound 是不是 2 的幂次
r = (int)((bound * (long)r) >> 31); // 生成随机数
else {
for (int u = r;
u - (r = u % bound) + m < 0; // 不断对 bound 进行取模运算
u = next(31)) // 生成随机数
;
}
return r;
}
上面代码的操作逻辑是这样的:
nextInt(int bound)
方法接收一个整数参数bound
,表示生成的随机数的上限(不包括)。如果传入的bound
小于等于0,则抛出IllegalArgumentException
异常。int r = next(31);
生成一个31位的随机整数r
int m = bound - 1;
计算bound
减去1的值。if ((bound & m) == 0)
判断bound
是否是2的幂,即bound
和m
的按位与操作结果是否为0。如果是,说明bound
是2的幂,这时采用一种优化方法来生成随机数。- 如果
bound
是2的幂,则r
的计算方法为(int)((bound * (long)r) >> 31)
。这个式子的意思是将bound
乘以r
,然后右移31位,最终将结果转换为整数,这样就生成了一个在0到bound-1
之间的随机数r
。 - 如果
bound
不是2的幂,则进入else
分支。 - 在
else
分支中,使用循环来生成一个满足条件的随机数r
。循环中不断地生成新的随机数u
,然后对u
取模bound
,直到生成的r
落在0到bound-1
之间。 - 返回生成的随机数
r
。
通过上面的流程我们可以了解到,这个方法中生成随机数主要是调用了 next()
方法,下面看一下它的具体实现:
protected int next(int bits) {
long oldseed, nextseed;
AtomicLong seed = this.seed;
do {
oldseed = seed.get();
nextseed = (oldseed * multiplier + addend) & mask;
} while (!seed.compareAndSet(oldseed, nextseed));
return (int)(nextseed >>> (48 - bits));
}
这个方法用于升成一个指定位数的随机数:
- 首先,定义了两个
long
类型的变量oldseed
和nextseed
,用来存储随机数生成器的种子值。 AtomicLong seed = this.seed;
将当前对象中的seed
变量赋值给局部变量seed
,seed
可能是一个原子长整型变量。do-while
循环用于生成随机数,直到成功更新种子值。循环的条件是seed.compareAndSet(oldseed, nextseed)
,即当seed
的值与oldseed
相等时,将nextseed
的值赋给seed
,如果更新成功,则跳出循环,否则继续生成下一个随机数。- 在循环中,随机数的生成通过下面的计算完成:
nextseed = (oldseed * multiplier + addend) & mask;
。这里使用了线性同余算法来生成伪随机数,即将当前种子值乘以一个常数multiplier
,然后加上另一个常数addend
,最后对结果进行位与操作并截取低位以得到下一个种子值。 - 生成的随机数由
(int)(nextseed >>> (48 - bits))
计算得到。这里首先将nextseed
右移48 - bits
位,然后将结果强制转换为整数,得到指定位数的随机数。
随机数的生成依赖于种子 seed,在县城城的条件下不会有什么问题,但是如果是在多线程的情况下,存在潜在的种子重复的问题,多个线程仍然可能会在同一时刻读取到相同的种子值。
带着这个问题再来看 nextInt()
方法,当很多线程利用相同的种子进行更新的操作的时候,由于上面的操作是 CAS 操作,同时只有一个线程成功,会造成大量的线程重试,这就降低了并发的性能,所以 ThreadLocalRandom 应运而生。
3.2)ThreadLocalRandom
先写一段代码来展示如何使用它:
public class ThreadLocalRandomTest {
public static void main(String[] args) {
ThreadLocalRandom random = ThreadLocalRandom.current();
for (int i = 0; i < 10; i++) {
// 生成随机数
System.out.println(random.nextInt(5));
}
}
}
看到这个名字,很容易就能联想到 ThreadLocal,ThreadLocal 的原理是让每个线程复制一份变量,每个线程操作自己的副本,从而避免多个线程之间的同步问题,ThreadLocalRandom 同样也是这个原理,Random 的缺点就是多个线程使用一个 seed,从而引发竞争的情况;但如果每个线程都维护一个种子变量就不会存在并发的问题了,从而大大的提高了并发的性能。
ThreadLocalRandom 的继承关系是这样的,它继承了 Random 类并且重写了 nextInt 方法,ThreadLocalRandom 类中使用的种子存放在调用线程的 threadLocalRandomSeed 变量中,当线程调用了 ThreadLocalRandom 类的 current()
方法的时候,ThreadLocalRandom 会去初始化调用线程的 threadLocalRandomSeed 变量,也就是初始化种子。
public static ThreadLocalRandom current() {
if (UNSAFE.getInt(Thread.currentThread(), PROBE) == 0)
localInit();
return instance;
}
上面的方法就是 current 方法,它先通过 Unsafe 类获取到了当前线程偏移量为 PROBE 的值,如果发现其值为 0(没有被初始化过),就会调用了 localInit 方法来初始化,最终会返回一个 instance,这是一个 ThreadLocalRandom 的实例:
static final ThreadLocalRandom *instance* = new ThreadLocalRandom();
可以保证多个线程访问 current()
来生成 Random 调用的是相同的 ThreadLocalRandom 实例,在 ThreadLocalRandom 实例中只包含和线程无关的通用算法,所以它是线程安全的。
为什么说发现 PROBE 是 0 就说明没有被初始化呢?
在 Thread 类中可以一探究竟,这个属性的注解是这样的:Probe hash value; nonzero if threadLocalRandomSeed initialized,这是一个散列探测值,如果这个 threadLocalRandomSeed 被初始化,则它是非零的;这个值没被赋任何初始值,所以在类被实例化创建的时候会被初始化为默认值,也就是 0。
下面来看一下 localInit 的具体实现:
static final void localInit() {
int p = probeGenerator.addAndGet(PROBE_INCREMENT);
int probe = (p == 0) ? 1 : p; // skip 0
long seed = mix64(seeder.getAndAdd(SEEDER_INCREMENT));
Thread t = Thread.currentThread();
UNSAFE.putLong(t, SEED, seed);
UNSAFE.putInt(t, PROBE, probe);
}
方法中首先生成了 seed 和 probe(均为随机数生成过程中需要维护和更新的变量),然后将这两个变量分别赋值给对象中偏移量为 SEED 和 PROBE 的属性。
偏移量是 Java 中的 Unsafe 类用来直接操控内存中变量使用的一种标识,通过这个标示就能找到内存中对应的变量属性,这个偏移量通过
UNSAFE.objectFieldOffset(Field field)
来获得,下面代码中展示了获取这两个偏移量的方法:
// Unsafe mechanics
private static final sun.misc.Unsafe UNSAFE;
private static final long SEED;
private static final long PROBE;
private static final long SECONDARY;
static {
try {
UNSAFE = sun.misc.Unsafe.getUnsafe();
Class<?> tk = Thread.class;
SEED = UNSAFE.objectFieldOffset
(tk.getDeclaredField("threadLocalRandomSeed"));
PROBE = UNSAFE.objectFieldOffset
(tk.getDeclaredField("threadLocalRandomProbe"));
SECONDARY = UNSAFE.objectFieldOffset
(tk.getDeclaredField("threadLocalRandomSecondarySeed"));
} catch (Exception e) {
throw new Error(e);
}
}
3.3)nextInt() 方法
通过上面的讲解,大家对 ThreadLocalRandom 有了基本的理解,下面来看一下在 nextInt()
方法中究竟是如何实现线程之间独立的:
public int nextInt(int bound) {
// 参数校验
if (bound <= 0)
throw new IllegalArgumentException(BadBound);
// 根据当前线程中的种子计算新的种子
int r = mix32(nextSeed());
int m = bound - 1;
// 根据新的种子来计算随机数
if ((bound & m) == 0) // power of two
r &= m;
else { // reject over-represented candidates
for (int u = r >>> 1;
u + m - (r = u % bound) < 0;
u = mix32(nextSeed()) >>> 1)
;
}
return r;
}
可以看到和 Random 类中的实现方式几乎是完全相同,重点来关注一下 nextSeed()
方法。
final long nextSeed() {
Thread t; long r; // read and update per-thread seed
UNSAFE.putLong(t = Thread.currentThread(), SEED,
r = UNSAFE.getLong(t, SEED) + GAMMA);
return r;
}
拆分开来看,这个方法就是将线程中偏移量为 SEED 的属性的值变为了原本的种子值加上 GAMMA,然后将这个新的种子值返回,GAMMA 的注释为 The seed increment,也就是 seed 的增量。