Дефекты Random при высоком уровне параллелизма и его оптимизация JUC

Java

Можно сказать, что Random — это класс, который знает и много использует каждый разработчик. см. мой блог больше. Но не все знают принцип Random, и должно быть меньше людей, которые знают о недостатках Random при высоком параллелизме. В этом блоге я проанализирую дефекты класса Random при параллелизме и его оптимизацию JUC.

Принцип и недостатки Random

    public static void main(String[] args) {
        Random random = new Random();
        System.out.println(random.nextInt(100));
    }

Когда я учился программированию, меня всегда недоумевали разработчики JDK: почему название метода для генерации случайных чисел: ""nextXXX"? Хотя мой английский остается только "nod yes, nod no, come is come, go is go ", но я знаю, что next означает "следующий". Если я назову его, он будет называться "создать", "сгенерировать", разве это не более "подходящее"? Почему разработчики JDK называют его "nextXXX"? может быть, они внезапно «не в словах» и не могут придумать ни одного слова, поэтому они просто придумали одно? Позже я понял, что случайное число, сгенерированное Random, на самом деле не случайное. начальное значение, которое соответствует начальному значению для расчета [следующего] значения, если начальное значение одинаково, то генерируемые им случайные числа также должны быть равными, то есть «определенный ввод производит определенный вывод».

Если вы мне не верите, давайте проведем эксперимент:

    public static void main(String[] args) {
        for (int i = 0; i < 10; i++) {
            Random random = new Random(15);
            System.out.println(random.nextInt(100));
        }
    }

В дополнение к предоставлению метода построения без параметров, класс Random также предоставляет параметризованный метод построения.Мы можем передать параметр типа int.Этот параметр называется "начальным числом", так что "начальное число" является фиксированным, а сгенерированный случайный Цифры те же:

41
41
41
41
41
41
41
41
41
41

Давайте кратко рассмотрим исходный код nextInt. Исходный код включает в себя алгоритм. Конечно, алгоритм не находится в центре внимания этого обсуждения в блоге. Мы можем упростить исходный код следующим образом:

    public int nextInt(int bound) {
        if (bound <= 0)
            throw new IllegalArgumentException(BadBound);
        //1.根据老的种子生成新的种子
        int r = next(31);
        //2.根据新的种子计算随机数
        ...
        return r;
    }

Первый заключается в создании нового начального числа на основе старого начального числа, а затем на основе нового начального числа вычисляется случайное число.Основной код nextXXX можно упростить за эти два шага. Теперь давайте подумаем над вопросом: если есть N потоков в случае высокого параллелизма и одновременно выполнить первый шаг: сгенерировать новое начальное число на основе старого начального значения, не будет ли полученное начальное число таким же? Поскольку вторым шагом является вычисление случайных чисел на основе нового начального числа, а этот алгоритм фиксирован, что происходит? Разве случайное число, в конечном итоге, не получается N нитями все равно? Очевидно, это не то, что мы хотим, поэтому об этом подумали разработчики JDK, давайте посмотрим, что происходит внутри следующего метода:

    protected int next(int bits) {
        long oldseed, nextseed;//定义旧种子，下一个种子
        AtomicLong seed = this.seed;
        do {
            oldseed = seed.get();//获得旧的种子值，赋值给oldseed 
            nextseed = (oldseed * multiplier + addend) & mask;//一个神秘的算法
        } while (!seed.compareAndSet(oldseed, nextseed));//CAS，如果seed的值还是为oldseed，就用nextseed替换掉，并且返回true，退出while循环，如果已经不为oldseed了，就返回false，继续循环
        return (int)(nextseed >>> (48 - bits));//一个神秘的算法
    }
  1. Определяет старое семя oldseed, следующее семя (новое семя) nextseed.
  2. Получите значение старого семени и назначьте его oldseed.
  3. Загадочный алгоритм, который вычисляет следующее начальное число (новое начальное число) и присваивает его nextseed.
  4. Используя операцию CAS, если значение seed все еще oldseed, замените его на nextseed и верните true, ! Если true равно false, выходим из цикла while; если значение seed больше не oldseed, это означает, что значение seed заменено, возвращаем false! false равно true, переходите к следующему циклу while.
  5. Таинственный алгоритм, вычисляющий случайное число на основе nextseed и возвращающий его.

Мы видим, что ядро ​​находится на четвертом шаге, опишу его подробнее, во-первых, мы должны знать тип seed:

 private final AtomicLong seed;

Тип начального числа — AtomicLong, который является атомарным операционным классом, который может гарантировать атомарность. Переменная. Когда два потока одновременно входят в следующий метод, происходит следующее:

  1. Поток A и поток B одновременно получают значение seed и присваивают его переменной oldseed.
  2. Согласно таинственному алгоритму, nextseed вычисляется как XXX. Обратите внимание, что, поскольку этот алгоритм фиксирован, сгенерированное nextseed также должно быть исправлено.
  3. Введите цикл while: 3.1 Поток A, используя алгоритм CAS, обнаруживает, что значение seed все еще является oldseed, указывая на то, что значение seed не было заменено, и заменяет значение seed на nextseed, сгенерированное на втором шаге, замена прошла успешно, и возвращает истину! true в false, выйти из цикла while. 3.2 Поток B, используя алгоритм CAS, обнаруживает, что значение seed больше не является oldseed, потому что поток A заменил значение seed на nextseed, поэтому CAS терпит неудачу и может только снова зацикливаться. При повторном цикле seed.get() получает последнее начальное значение и снова получает nextSeed в соответствии с загадочным алгоритмом, CAS завершается успешно и выходит из цикла.

Все выглядит хорошо, но это не так Что произойдет, если параллелизм будет высоким? Большое количество потоков находится в цикле while, что довольно интенсивно использует ЦП, поэтому JUC представила ThreadLocalRandom для решения этой проблемы.

ThreadLocalRandom

Во-первых, давайте посмотрим, как используется ThreadLocalRandom:

    public static void main(String[] args) {
        for (int i = 0; i < 10; i++) {
            ThreadLocalRandom threadLocalRandom = ThreadLocalRandom.current();
            System.out.println(threadLocalRandom.nextInt(100));
        }
    }

Вы можете видеть, что использование немного изменилось.Давайте посмотрим на логику реализации основного кода ThreadLocalRandom:

current

    public static ThreadLocalRandom current() {
        if (UNSAFE.getInt(Thread.currentThread(), PROBE) == 0)
            localInit();
        return instance;
    }

Следует отметить, что, поскольку current является статическим методом, если этот метод вызывается несколько раз, возвращаемый объект ThreadLocalRandom будет одним и тем же.

Если PROBE текущего потока равен 0, это означает, что текущий метод вызывается в первый раз, тогда необходимо вызвать метод localInit, в противном случае сгенерированный экземпляр возвращается напрямую.

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);
    }

Сначала инициализируйте зонд и начальное значение, а затем вызовите метод класса UNSAFE, чтобы установить зонд и начальное значение для текущего потока, чтобы другие потоки не могли его получить.

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;
    }

Так же, как метод nextXXX в классе Random, он также генерирует новое начальное число на основе старого начального числа, а затем генерирует случайное число на основе нового начального числа Давайте посмотрим, что делает метод nextSeed:

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;
    }

Сначала используйте UNSAFE.getLong(t, SEED), чтобы получить SEED текущего потока, затем + GAMMA в качестве нового начального значения, а затем поместите новое начальное значение в текущий поток.

Суммировать

В этой статье сначала кратко анализируется принцип реализации Random и выявляется недостаток метода nextXXX при высокой степени параллелизма: ему необходимо конкурировать за атомарную переменную seed. Затем вводится использование и принцип ThreadLocalRandom. Из названия класса видно, что принцип реализации аналогичен ThreadLocal. Начальное число сохраняется в каждом потоке, а новое число вычисляется в соответствии с исходным значением в каждый поток. , тем самым избегая проблемы конкуренции.

Категории