Личный технический блог:www.zhenganwen.top

Видны ли переменные?

Видны ли общие переменные?

Сначала введите фрагмент кода, указывающий на проблему с моделью памяти Java: запустите два потока.t1，t2доступ к общим переменнымsharedVariable,t2Нить будет постепенноsharedVariableувеличить доMAX, спать каждый раз, когда он увеличивается500msОтказаться от выполнения ЦП, ожидая другого потока тем временемt1способен7-12Найдено во время опроса строкsharedVariableизменить и распечатать его

private static int sharedVariable = 0;
private static final int MAX = 10;

public static void main(String[] args) {
    new Thread(() -> {
        int oldValue = sharedVariable;
        while (sharedVariable < MAX) {
            if (sharedVariable != oldValue) {
                System.out.println(Thread.currentThread().getName() + " watched the change : " + oldValue + "->" + sharedVariable);
                oldValue = sharedVariable;
            }
        }
    }， "t1").start();

    new Thread(() -> {
        int oldValue = sharedVariable;
        while (sharedVariable < MAX) {
            System.out.println(Thread.currentThread().getName() + " do the change : " + sharedVariable + "->" + (++oldValue));
            sharedVariable = oldValue;
            try {
                Thread.sleep(500);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    }， "t2").start();

}

Но фактический результат выполнения вышеуказанной программы выглядит следующим образом:

t2 do the change : 0->1
t1 watched the change : 0->1
t2 do the change : 1->2
t2 do the change : 2->3
t2 do the change : 3->4
t2 do the change : 4->5
t2 do the change : 5->6
t2 do the change : 6->7
t2 do the change : 7->8
t2 do the change : 8->9
t2 do the change : 9->10

volatile может гарантировать видимость

Его можно найтиt1Нитки едва заметныt2каждая пара общих переменныхsharedVariableВнесены изменения и почему? Может кто подскажетsharedVariableдобавитьvolatileЭто просто прекрасно, действительно, это добавленоvolatileРезультат после этого соответствует нашим ожиданиям:

t2 do the change : 0->1
t1 watched the change : 0->1
t2 do the change : 1->2
t1 watched the change : 1->2
t2 do the change : 2->3
t1 watched the change : 2->3
t2 do the change : 3->4
t1 watched the change : 3->4
t2 do the change : 4->5
t1 watched the change : 4->5
t2 do the change : 5->6
t1 watched the change : 5->6
t2 do the change : 6->7
t1 watched the change : 6->7
t2 do the change : 7->8
t1 watched the change : 7->8
t2 do the change : 8->9
t1 watched the change : 8->9
t2 do the change : 9->10

Это также легче понять, сказал чиновник.volatileМожет гарантировать видимость общих переменных между потоками.

Гарантирует ли синхронизация видимость?

Однако кто-то может также сказать вам, что вы используетеsynchronized + wait/notifyМодель просто прекрасна: поместите все операции над общими переменными в синхронизированный блок, а затем используйтеwait/notifyКоординировать изменение и чтение общих переменных

private static int sharedVariable = 0;
private static final int MAX = 10;
private static Object lock = new Object();
private static boolean changed = false;

public static void main(String[] args) {
    new Thread(() -> {
        synchronized (lock) {
            int oldValue = sharedVariable;
            while (sharedVariable < MAX) {
                while (!changed) {
                    try {
                        lock.wait();
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                }
                System.out.println(Thread.currentThread().getName() +
                                   " watched the change : " + oldValue + "->" + sharedVariable);
                oldValue = sharedVariable;
                changed = false;
                lock.notifyAll();
            }
        }
    }， "t1").start();

    new Thread(() -> {
        synchronized (lock) {
            int oldValue = sharedVariable;
            while (sharedVariable < MAX) {
                while (changed) {
                    try {
                        lock.wait();
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                }
                System.out.println(Thread.currentThread().getName() +
                                   " do the change : " + sharedVariable + "->" + (++oldValue));
                sharedVariable = oldValue;
                changed = true;
                lock.notifyAll();
            }
        }
    }， "t2").start();

}

Вы найдете этот путь, даже не даваяsharedVariable,changedдобавлятьvolatile, но ониt1иt2Также кажется видимым между:

t2 do the change : 0->1
t1 watched the change : 0->1
t2 do the change : 0->2
t1 watched the change : 0->2
t2 do the change : 0->3
t1 watched the change : 0->3
t2 do the change : 0->4
t1 watched the change : 0->4
t2 do the change : 0->5
t1 watched the change : 0->5
t2 do the change : 0->6
t1 watched the change : 0->6
t2 do the change : 0->7
t1 watched the change : 0->7
t2 do the change : 0->8
t1 watched the change : 0->8
t2 do the change : 0->9
t1 watched the change : 0->9
t2 do the change : 0->10
t1 watched the change : 0->10

Гарантирует ли CAS видимость?

будетsharedVariableТип меняется наAtomicInteger,t2использование потокаAtomicIntegerкоторый предоставилgetAndSetCAS обновляет эту переменную, и вы обнаружите, что это обеспечивает видимость.

private static AtomicInteger sharedVariable = new AtomicInteger(0);
private static final int MAX = 10;

public static void main(String[] args) {
    new Thread(() -> {
        int oldValue = sharedVariable.get();
        while (sharedVariable.get() < MAX) {
            if (sharedVariable.get() != oldValue) {
                System.out.println(Thread.currentThread().getName() + " watched the change : " + oldValue + "->" + sharedVariable);
                oldValue = sharedVariable.get();
            }
        }
    }， "t1").start();

    new Thread(() -> {
        int oldValue = sharedVariable.get();
        while (sharedVariable.get() < MAX) {
            System.out.println(Thread.currentThread().getName() + " do the change : " + sharedVariable + "->" + (++oldValue));
            sharedVariable.set(oldValue);
            try {
                Thread.sleep(500);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    }， "t2").start();

}

ПочемуsynchronizedиCASВидимость тоже? На самом деле это потому, чтоsynchronizedизблокировка снятия-полученияиCAS Modification-Readесть иvolatileДоменпиши-читайимеют одинаковую семантику. Поскольку это так удивительно, давайте перейдем к модели памяти Java,synchronized/volatile/CASДавайте подробнее рассмотрим базовую реализацию!

CPU Cache

Чтобы понять видимость переменных между потоками, мы должны сначала понять модель чтения и записи процессора.Хотя это может быть скучно, это очень полезно для понимания параллельного программирования!

Основная память RAM и кэш

В ходе развития вычислительной техники,Скорость доступа к основной памяти всегда была намного медленнее, чем скорость работы процессора., что делает возможности ЦП высокоскоростной обработки невозможными для полноценной работы и влияет на эффективность работы всей компьютерной системы, поэтому современные процессоры обычно используют кэш-память (называемую кешем).

Скорость доступа к кэш-памяти может соответствовать скорости процессора, но емкость намного меньше, чем у основной памяти из-за высокой стоимости. в соответствии сПринцип локализации программы, когда ЦП пытается получить доступ к блоку в основной памяти (один блок памяти соответствует одному байту), существует большая вероятность того, что его соседние блоки будут использованы позже. Таким образом, когда ЦП обращается к блоку основной памяти, аппаратное обеспечение компьютера автоматически назначает набор блоков (называемый блоком памяти), который включает этот блок, дляblock, обычно непрерывные 64 байта) содержимое загружается в кеш, и блок основной памяти, к которому ЦП собирается получить доступ, скорее всего, будет в наборе блоков, только что загруженных в кеш. Таким образом, ЦП может напрямую обращаться к кешу. Во всем процессе обработки, если большинство операций ЦП, обращающихся к основной памяти, можно заменить обращением к кэш-памяти, скорость обработки компьютерной системы может быть значительно улучшена.

Термины, связанные с кэшем

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

Cache Line & Slot & Hot Data

Как упоминалось выше, когда ЦП запрашивает доступ к определенному блоку хранения в основной памяти, он вызывает группу блоков, включая блок хранения, в кэш. Эта группа блоков (которую мы обычно называем блоком памяти) будет храниться в кэш-строке (также называемой слотом) кэша. Кэш будет делить свою единицу хранения на несколько равных частей, и каждая равная часть представляет собой строку кеша.В настоящее время строка кеша массовых процессоров обычно составляет 64 байта (то есть, если размер кеша составляет 512 байт, то это соответствует 8 кешам). линии).

Кроме того, данные, кэшированные строкой кэша, называются горячими данными.

Cache Hit

Когда ЦП запрашивает доступ к данным через адрес данных, хранящийся в регистре (включая операции чтения и операции записи), он сначала выполняет поиск в кэше и, если находит, напрямую возвращает данные, хранящиеся в кэше, что называется попадание в кэш. , которое можно разделить на попадание в кэш чтения и попадание в кэш записи в зависимости от типа операции.

Cache Miss & Hit Latency

Соответственно попаданию в кеш, если оно не найдено, оно будет найдено в основной памяти через системную шину (System Bus), что называется промахом кеша (cache miss). Если происходит промах кэша, операция, которая должна была напрямую обращаться к основной памяти, теряет некоторое время из-за существования кэша, что называется задержкой попадания. Чтобы быть точным, задержка попадания означает время, необходимое для определения того, кэшируются ли целевые данные в кэше.

Классификация кэша

Если вы откроете диспетчер задач, чтобы проверить производительность процессора, вы можете обнаружить, что кеш автора имеет три области: L1 (кэш первого уровня, 128 КБ), L2 (кэш второго уровня, 512 КБ), L3 (общий кеш 3,0 МБ). :

Сначала реализация Cache имела только кеш первого уровня L1.В дальнейшем, с развитием науки и техники, с одной стороны, увеличение оперативной памяти привело к большему количеству горячих данных, которые необходимо кэшировать, и снижению производительности. полученное простым увеличением емкости L1 будет очень низким; с одной стороны, скорость доступа к L1 и скорость доступа к основной памяти дополнительно увеличиваются, и для буферизации необходим кэш, основанный на скорости доступа между ними. Основываясь на двух вышеуказанных пунктах, вводится кэш-память L2, скорость доступа к которой находится между L1 и основной памятью, а емкость доступа расширяется на основе L1.

Вышеупомянутые L1 и L2 обычно являются частными для процессора, что означает, что каждое ядро ​​​​ЦП имеет свои собственные L1 и L2 и не используется совместно с другими ядрами. В настоящее время, чтобы иметь область кэша, совместно используемую всеми ядрами, и предотвратить промахи кэша как в L1, так и в L2, а также еще больше повысить частоту попаданий в кэш, добавляется L3. Можно предположить, что скорость доступа L3 ниже, чем у L1 и L2, но пропускная способность больше.

Алгоритм замены кэша и конфликт строк кэша

Для обеспечения высокой частоты попаданий при обращении к процессору содержимое в кэше должно заменяться по определенному алгоритму. Более часто используемый алгоритм — это «наименее используемый алгоритм» (алгоритм LRU), который исключает строку, которая была наименее посещаемой за последний период времени. Поэтому необходимо установить счетчик для каждой строки.Алгоритм LRU очищает счетчик строки попадания и увеличивает счетчик других строк на 1. Когда требуется замена, строка данных с наибольшим счетчиком строк удаляется. Это эффективный и научный алгоритм.Процесс очистки счетчика может удалить из кэша некоторые данные, которые не нужны после частых вызовов (данные, соответствующие наибольшему значению счетчика), и улучшить использование кэша.

По сравнению с основной памятью емкость Cache крайне ограничена, поэтому как бы ни был реализован механизм хранения Cache (взаимоотношение с кэшем будет подробно объяснено позже), если подходящий алгоритм замены не будет принят, то с использованием Кэш-памяти неизбежно будет: Когда все Кэш-линии в Кэш-памяти заняты, Кэш-линия не может быть выделена, когда необходимо кэшировать новый блок памяти; или Кэш-строка, выделенная для блока памяти, используется в соответствии с Кэш-памятью. механизм хранения. Оба вышеуказанных пункта приведут к тому, что новый блок памяти будет сохранен без строки кэша, что называется конфликтом строки кэша.

Архитектура кэш-памяти процессора

Пока что мы можем примерно получить архитектуру кэша ЦП:

Как показано на рисунке, когда ЦП пытается получить доступ к данным через определенный адрес единицы хранения, он будет искать в L1, L2, L3 и основной памяти по очереди сверху вниз. соответствующий кэш вместо того, чтобы смотреть вниз. , если L1, L2 и L3 все пропустят кэш, тогда процессору придется обращаться к данным в основной памяти или на жестком диске через шину. А из тактового цикла (цикл, величина, обратная частоте ЦП, равна одному тактовому циклу), необходимой для каждой операции доступа к оборудованию, показанной на рисунке ниже, мы можем знать, что сверху вниз накладные расходы на доступ становятся все больше и больше, поэтому дизайн кеша. Необходимо максимально улучшить скорость попадания в кеш, иначе, если вам все равно придется обращаться к памяти в конце, это не будет стоить выигрыша.

Чтобы облегчить ваше понимание, автор выдержкикрутая оболочкаВыдержка из:

Мы знаем, что вычислительные данные компьютера должны быть запланированы с диска в память, затем в кэш-память L2, затем в кэш-память L1 и, наконец, в регистр ЦП для расчета.

Об этих параметрах я спросил у продавца компьютеров, когда покупал книги для жены в компьютерном городе. Жена не могла понять, поэтому я попросил объяснить ей. После объяснения жена сказала: «Оказывается, из-за того, что внутренняя часть компьютера так хлопотна, неудивительно, что компьютер всегда такой медленный, быстро оперировать памятью напрямую». Я тот пот.

Мне пришлось ей объяснять, что это для более быстрой обработки, и она была озадачена, поэтому я набрал следующую аналогию — это как будто мы кормим ребенка грудью:

• Процессор подобен молоку, который уже находится во рту ребенка и может быть проглочен непосредственно. занимает 1 секунду

• Кэш L1 подобен молоку, которое было приготовлено и налито в бутылочку, его можно давать в рот только тогда, когда ребенка берут на руки. Это занимает 5 секунд.

• Тайник L2 – это как сухое молоко в домашних условиях, его тоже нужно сначала промыть горячей водой, а потом брать в него ребенка и кормить. Это занимает 2 минуты.

• Память RAM это как сухое молоко в разных супермаркетах, эти супермаркеты расположены в разных уголках города, некоторые далеко, некоторые рядом, к ним надо сначала обратиться, а потом уже ехать в магазин за ними. Это занимает 1-2 часа.

• Жесткий диск ДИСК похож на склад, может быть, в далеком пригороде или даже заводской склад. Большие грузовики должны ездить по шоссе, чтобы добраться до города. Это занимает 2-10 дней.

Итак, в данном случае -

• Мы не можем не хранить дома сухое молоко. Только представьте, если ребенок проголодается, а потом пойдет в супермаркет за покупками, разве это не медленнее?

• Мы не можем поместить все сухое молоко в бутылку, потому что бутылки недостаточно. Также невозможно поставить все сухое молоко в супермаркет дома, потому что цена дома слишком высока, невозможно позволить себе такой большой дом.

• У нас невозможно разместить все вещи на складе в супермаркете, потому что стоимость этого слишком высока. А если полки в супермаркете только что раскуплены, то его нужно настраивать со склада или даже с завода производителя, это называется в расчете изменением страницы, и происходит это достаточно медленно.

Структура кеша и ассоциативность кеша

Если бы вас попросили спроектировать такой тайник, как бы вы его спроектировали?

Если вы не такой профессионал, как автор, то можете подумать, что использование хеш-таблицы — хороший выбор.Один блок памяти соответствует одной записи, используя в качестве ключа хеш-значение адреса блока памяти, а используя данные хранится в блоке памяти как значение.O(1)Завершите поиск внутри, просто и эффективно.

Но если вы хешируете адрес каждый раз, когда кэшируете блок памяти, требуемое время может быть намного больше, чем десятки тактовых циклов, необходимых для доступа к кэшу, и это не тот кэш памяти, который обычно используется нашими приложениями. Реализовать логику хеширования адресов памяти на аппаратном уровне немного похоже на то, чтобы спешить на полки.

На примере нашего общего чипа X86 структура Кэш-памяти показана на рисунке ниже: весь Кэш-память разбит на S групп, и каждая группа состоит из Е строк мельчайших единиц хранения — Кэш-линии, и одной Строка кэша Для хранения данных используется B (B=64) байтов, то есть каждая строка кэша может хранить 64 байта данных, и каждая строка кэша содержит дополнительный допустимый бит (valid bit),tотметьте биты (tag bit),вvalid bitиспользуется для обозначения того, чтоСтрока кэша действительна?;tag bitиспользовал кпомочь в решении,Уникально идентифицирует блок, хранящийся в строке кэша.;и64 байта в строке кэша на самом деле являются копией данных по соответствующему адресу памяти.. По структуре Кэша мы можем рассчитать, что размер каждого уровня Кэша равен B×E×S.

Ключевым решением при проектировании кэша является обеспечение того, чтобы каждый блок основной памяти мог храниться в любом одном слоте кэша или только в некоторых из них (в данном случае слот — это строка кэша).

Существует три способа сопоставления слотов кэша с блоками основной памяти:

1. Кэш с прямым отображениемКаждый блок памяти может быть сопоставлен только с определенным слотом кэша. Простое решение — сопоставить индекс блока block_index с соответствующим слотом (block_index % cache_slots). Два блока памяти, сопоставленные с одним и тем же слотом памяти, не могут быть перемещены в кэш одновременно. (Примечание: block_index можно рассчитать по байтам строки физического адреса/кэша)
2. N-way set associative cacheКаждый блок памяти может быть сопоставлен с любым из N-направленных слотов кэш-памяти. Например, в 16-канальном кэше каждый блок памяти может быть сопоставлен с 16 различными слотами кэша. Как правило, блоки памяти с одним и тем же адресом младшего бита будут совместно использовать 16-канальный слот кэш-памяти. (Примечание переводчика: один и тот же младший адрес указывает на непрерывную память, разделенную определенным размером единицы)
3. Полностью ассоциативный кешКаждый блок памяти может быть сопоставлен с любым слотом кэша. Эффект операции эквивалентен хеш-таблице.

Среди них N-сторонняя групповая ассоциация улучшена в соответствии с двумя другими методами и является текущей основной схемой реализации. Примеры этих трех методов приведены ниже.

Fully associative cache

Полностью ассоциативный, как следует из названия, полностью ассоциирован. То есть, чтобы блок памяти был кэширован, он может быть кэширован в любом слоте (т. е. в строке кэша) кэша. Возьмем в качестве примера 32-битную операционную систему (имеется в виду, что память адресуется через 32-битный адрес), например, есть0101...10 000000 - 0101...10 111111(Для сохранения схемы некоторые биты в старших 26 битах опущены. Этот интервал представляет 64 адреса с одинаковыми старшими 26 битами, но разными младшими 6 битами, то есть 64-байтовый блок памяти.) Блок памяти должен для кэширования, то он будет случайным образом храниться в доступном слоте и использовать старшие 26 бит в качестве слота.tag bit(Как упоминалось ранее, в дополнение к 64-байтовой строке кэша, в которой хранится блок памяти, каждая строка также имеет дополнительный бит, определяющий, является ли строка допустимой, и t битов в качестве уникального идентификатора строки. В этом примере t это 26). Таким образом, когда памяти необходимо получить доступ к адресу данных в пределах этого диапазона адресов, она сначала обратится к кэш-памяти, чтобы выяснить, кэшированы ли старшие 26 бит (tag bit)за0101...10Если слот найден, то он будет расположен в определенной ячейке памяти строки кэша в соответствии с младшими 6 битами адреса данных, младшие 6 бит называются смещением слова.

Может быть, вы думаете, что это не хеш-таблица? Это правда, что решение о том, в какой доступный слот поместить блок памяти, является случайным, но оно не хеширует адрес данных и не использует хэш-значение какtag bit, поэтому он существенно отличается от хеш-таблицы.

Причина, по которой этот метод не используется широко, заключается в том, что неизвестно, в какой слот будет помещен блок памяти, поэтому, когда ЦП ищет слот на основе адреса данных, ему необходимо поместить старшие биты адреса данных ( в данном случае старшие 26 бит) и кэш всех слотовtag bitЧтобы сделать линейный поиск, возьмем для примера мой L1 128Кб, там 128*1024/64=2048 Слотов, хотя параллельная обработка и может быть реализована на аппаратном уровне, но эффективность невелика.

Direct Mapped Cache

Этот метод заключается в том, чтобы сначала закодировать блок памяти в основной памяти и слот в кэше отдельно, чтобы получитьblock_indexиslot_index,Потомblock_indexправильноslot_indexВозьмите модуль, чтобы определить, в какой слот следует поместить блок памяти, как показано на следующем рисунке:

Ниже в качестве примера для анализа возьмем кэш L1 128 КБ и память 4 ГБ:

Адресуемый диапазон 4 ГБ памяти составляет000...000(32 нуля) до111...111(32 1s), учитывая 32-битный адрес данных, как определить, кэшируются ли данные этого адреса данных в кэше L1?

Сначала разделите 32-битный адрес на следующие три части:

В этом случае для заданного 32-битного адреса данных сначала, независимо от младших 6 бит, вынимается среднийslot offsetбитов, определите, какой это слот, а затем сравнитеtag bitСоответствует ли он оставшимся старшим битам адреса данных, если он совпадает, это означает попадание в кэш, и, наконец, найти конкретную единицу хранения из строки кэша слота для доступа к данным в соответствии с младшими 6 битами.

Недостаток кэш-памяти с прямым отображением заключается в том, что блоки памяти с одинаковым младшим порядком, но с разным старшим порядком будут отображаться в один и тот же слот (поскольку результат тот же после взятия модуля SlotCount). блоков памяти будет только один блок памяти, который может быть кэширован в соответствующем слоте в кэше, что означает вероятность возникновения конфликта строк кэша.

N-Way Set Associative Cache

N-сторонняя групповая ассоциация представляет собой комбинацию кэша с прямым отображением и полного ассоциативного кэша.Идея состоит не в том, чтобы решить, какой слот поместить на данный адрес данных.

Как и на приведенной выше схеме структуры кэша x86, сначала разделите кэш на S-группы, и в каждой группе есть E-слоты. Предположим, что мой кэш L1 128 КБ разделен на группу по 16 слотов, тогда количество групп равно:128 * 1024 / 64(Количество слотов) / 16 = 128 групп (мы называем каждую группу набором, представляющим набор слотов). В этом случае для заданного адреса данных он по-прежнему делится на следующие три части:

Отличие от кэша с прямым отображением заключается в том, что 11 средних битов, которые изначально указывали, какой слот был сопоставлен, были изменены на 7 битов, чтобы указать, на какой набор был сопоставлен.После того, как набор определен, блок памяти будет помещен в набор. слот является случайным (может быть, какой из них можно использовать в данный момент), а затем оставшиеся старшие 19 бит используются в качестве конечного хранилища блока памяти.tag bit.

Преимущество этого заключается в том, что для данного адреса данных он будет сопоставлен только с определенным набором, что значительно снижает вероятность конфликта строк кэша, а ЦП нужно только найти определенный набор при поиске слота. линейный поиск, количество слотов в наборе меньше (чем больше групп разбито, тем меньше слотов в каждой группе), поэтому временная сложность линейного поиска также приблизительно равна O(1).

Как писать программы, дружественные к кешу

Благодаря предыдущему пониманию модели чтения и записи ЦП мы знаем, что, как только ЦП захочет получить доступ к данным из памяти, произойдет большая задержка, и производительность программы будет значительно снижена.Так называемая дальняя вода не может спасти возле огня. По этой причине мы должны улучшить частоту попаданий в кэш, чтобы полностью использоватьпринцип локальности.

Локальность включает временную локальность и пространственную локальность.

• временная местность:заОдни и те же данные могут использоваться несколько раз, с момента первой загрузки в строку кэша последующие обращения могут выполняться из строки кэша несколько раз, тем самым увеличивая скорость чтения (вместо чтения из базового кэша).
• пространственная локализация: строка кэша имеет блоки по 64 байта, мы можемПолностью используйте 64-байтовое пространство, загружаемое за один раз, и загружайте все данные, к которым программа будет обращаться позже, за один раз., тем самым увеличивая частоту попаданий в Cache Line (вместо повторного переходаобращениечитать).

При чтении попытаться прочитать соседние адреса данных

Давайте сначала посмотрим на различные накладные расходы, связанные с двумя способами обхода двумерного массива:

static int[][] arr = new int[10000][10000];
public static void main(String[] args) {
    m1();		//输出 16
    m2();		//输出 1202	每次测试的结果略有出入
}
public static void m1() {
    long begin = System.currentTimeMillis();
    int a;
    for (int i = 0; i < arr.length; i++) {
        for (int j = 0; j < arr[i].length; j++) {
            a = arr[i][j];
        }
    }
    long end = System.currentTimeMillis();
    System.out.println(end - begin + "================");
}
public static void m2() {
    long begin = System.currentTimeMillis();
    int a;
    for (int j = 0; j < arr[0].length; j++) {
        for (int i = 0; i < arr.length; i++) {
            a = arr[i][j];
        }
    }
    long end = System.currentTimeMillis();
    System.out.println(end - begin + "================");
}

После многих тестов было обнаружено, что эффективность обхода столбца за столбцом значительно ниже эффективности обхода строки за строкой, так как адреса данных при обходе строки за строкой являются соседними, поэтому могут быть 16 последовательных обходов.intДоступ к переменной (16x4=64 байта) означает доступ к содержимому в той же строке кэша.intпеременную и добавить непрерывные 64 байта, включая ее, в Cache Line,intДоступ к переменной можно получить непосредственно из Cache Line, и никаких других избыточных операций не требуется. При переходе столбец за столбцом, если количество столбцов превышает 16, это означает, что в строке их больше 16.intпеременная, интервал между начальными адресами каждой строки превышает 64 байта, тоintПеременные не будут находиться в одной и той же строке кэша, что приведет к тому, что Cache Miss перезагрузит блок памяти в память, и каждое чтение через строку кэша будет стоить на одну задержку попадания больше, чем построчное чтение.

в примере вышеi,jвоплощает временную локальность,i,jПоскольку счетчики циклов используются часто, они будут храниться в регистрах, и ЦП сможет каждый раз получать к ним самый быстрый доступ, не обращаясь к ним из других мест, таких как кэш, оперативная память и т. д.

В то время как предпочтительный обход соседних элементов в строке использует пространственную локализацию, одновременная загрузка 64 байтов последовательных адресов в строку кэша способствует быстрому доступу к последующим соседним элементам адреса.

Cache Consistency & Cache Lock & False Sharing

Так бывает ли когда-нибудь, что работа с одной и той же строкой кеша более эффективна, чем работа с несколькими строками кеша? Универсального механизма нет, есть только наиболее подходящий для определенного сценария.Непрерывное и компактное выделение памяти (минимальной единицей хранения Cache является Cache Line) также имеет свои недостатки.

Этот недостаток вызван когерентностью кеша, так как каждое ядро ​​ЦП имеет свой собственный Кэш (обычно L1 и L2), и в большинстве случаев оно обращается к своему собственному Кэшу, что, вероятно, приводит к возникновению данных в каждом Кэше.Копия и общие данные в основной памяти разные.Иногда нам нужно вызвать каждый процессор для взаимодействия друг с другом.В это время мы должны взять общие данные в основной памяти в качестве критерия и синхронизировать каждый кэш с основной памятью.В это время время, что мы можем с этим поделать?

В это время вступает в действие протокол когерентности кеша: если (каждый ЦП) вы хотите, чтобы строка кеша и основная память были синхронизированы, вы должны изменить общие переменные в соответствии с моими правилами.

Это подсистема кэширования, отслеживающая состояние каждой строки кэша. В системе используется«Динамический мониторинг автобуса»Или метод, известный как «прослушивание шины»* для отслеживания всех транзакций, происходящих на системной шине, для обнаружения операций чтения или записи по адресу в кэше.

Когда эта подсистема кэша обнаруживает операцию чтения на системной шине из области памяти, загруженной в кэш, она изменяет состояние строки кэша на"общий". Если он обнаруживает запись по этому адресу, он изменяет состояние строки кэша на"недействителен".

Подсистема кэша хочет знать, содержит ли система уникальную копию данных в своем кэше, пока система отслеживает системную шину. Если данные обновляются собственным ЦП, эта подсистема кэширования изменит состояние строки кэша с"эксклюзив"изменить на"модифицированный". Если подсистема кэширования обнаруживает чтение другого процессора по адресу, она блокирует доступ, обновляет данные в системной памяти, а затем разрешает доступ процесса. Это также позволяет пометить статус этой строки кэша какshared.

Короче говоря, каждый ЦП будет контролировать другие ЦП посредством прослушивания шины.Как только ЦП изменяет общие переменные, кэшированные в его собственном кэше (предпосылка модификации заключается в том, что состояние строки кэша, в которой находится общая переменная, не является недопустимым. ), то это приведет к тому, что другие ЦП, кэшировавшие общую переменную, установят строку кэша, в которой находится переменная, в недопустимое состояние.В следующий раз, когда ЦП обращается к строке кэша в недопустимом состоянии, он сначала спросит ЦП, который изменил общая переменная для изменения переменной из кэша записывает обратно в основную память, а затем считывает последнюю общую переменную из основной памяти в свою собственную строку кэша.

Кроме того, протокол когерентности кэша проходитблокировка кешаДля обеспечения атомарности операции ЦП, изменяющей общую переменную в строке кеша и информирующей другие ЦП о недействительности соответствующей строки кеша, то есть, когда ЦП изменяет общую переменную, расположенную в его собственном кеше, он запрещает другим ЦП от кэширования общей переменной.ЦП переменной обращается к соответствующей строке кэша в своем собственном кэше и уведомляет эти ЦП о необходимости сделать соответствующую строку кэша недействительной до окончания блокировки кэша.

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

Хотя протокол когерентности кеша обеспечивает синхронизацию между кешем и основной памятью, он создает новую проблему: ложное совместное использование.

Как показано на рисунке ниже, данные X, Y и Z загружаются в одну и ту же строку кэша, поток A изменяет X на Core1, а поток B изменяет Y на Core2. Согласно МЭСИ (см. ссылку в конце статьи), предполагается, что Core1 является первым ядром ЦП, инициирующим операцию, а строка L1-кэша на Core1 переходит из состояния S (общий) в состояние M (модифицированный). , грязные данные) состояние, а затем информирует другое ядро ​​ЦП о ядре ЦП, легенда - Core2, строка кэша, относящаяся к тому же адресу, недействительна; когда Core2 инициирует операцию записи, это сначала заставляет Core1 записать X обратно в основной памяти, а статус Cache Line меняется с M на I (недействительный), а затем именно Core2 перечитывает содержимое адреса из основной памяти, состояние Cache Line меняется с I на E (эксклюзивный), и, наконец, изменяется операция Y, и строка кэша изменяется с E на M. Можно видеть, что несколько потоков работают с разными данными в одной и той же строке кэша и конкурируют друг с другом за одну и ту же строку кэша, заставляя потоки влиять друг на друга (такое поведение называется эффектом пинг-понга), который становится последовательной программой. и уменьшает параллелизм. На этом этапе нам нужно изолировать данные, совместно используемые несколькими потоками, чтобы они не находились в одной и той же строке кэша, тем самым повышая производительность нескольких потоков.

Два решения для ложного обмена Cache Line:

• Заполнение строки кэша за счет увеличения расстояния адресов двух переменных, чтобы они располагались в двух разных строках кэша, чтобы операции над общими переменными X и Y не влияли друг на друга.
• Поток не оперирует напрямую глобальной общей переменной, а считывает копию глобальной общей переменной в свою локальную переменную.Локальная переменная невидима между потоками, поэтому поиграйте со своим потоком, и, наконец, поток воспроизведет результат. вернуться к глобальной переменной.

Cache Line Padding

Известный гуру параллелизма Дуг Ли когда-то работал в JDK7.LinkedTransferQueueЭффективность работы очереди повышается за счет добавления байтов:

public class LinkedTransferQueue<E>{
    private PaddedAtomicReference<QNode> head;
    private PaddedAtomicReference<QNode> tail;
    static final class PaddedAtomicReference<E> extends AtomicReference<T{
        //给对象追加了 15 * 4 = 60 个字节
        Object p0, p1, p2, p3, p4, p5, p6, p7, p8, p9, pa, pb, pc, pd, pe;
        PaddedAtomicReference(T r){
            super(r);
        }
    }
}
public class AtomicReference<V> implements Serializable{
    private volatile V value;
}

Вы понимаете назначение строки 6? Это также начинается с размещения объектов в памяти.Люди, которые читали «Углубленное понимание виртуальной машины Java (второе издание)», должны знать, что расположение объектов, не являющихся массивами, выглядит следующим образом.

• заголовок объекта

  Заголовок объекта разделен на следующие три части:

  • Mark Word, который является 32-битным или 64-битным в зависимости от количества битов JVM, хранит хэш-код объекта, возраст поколения, флаг блокировки и т. д. Эту часть данных можно повторно использовать, чтобы указать на идентификатор смещенного потока, на слово метки смещения в стеке или на тяжеловесную блокировку.
  • Class Mete Data, указатель типа (также 32-битный или 64-битный), указывающий на информацию о типе, хранящуюся в области метода после того, как байт-код класса, к которому принадлежит объект, загружается в JVM.
  • Длина массива, если это объект массива, то будет эта часть данных.

• данные экземпляра

  Данные, содержащиеся в объекте среды выполнения, могут динамически изменяться и совместно использоваться всеми потоками.Эта часть данных состоит из следующих типов данных:

  • byte, char, short, int, float, занимают четыре байта (обратите внимание, что это тип данных в JVM, а не тип данных на уровне языка Java, они по-прежнему принципиально различаются из-за ограниченных инструкций JVM, поэтому Менее 4 собственных данных будут использовать серию инструкций int).
  • long, double, занимают 8 байт.
  • ссылка, в зависимости от реализации виртуальной машины, занимает 4 или 8 байт, но переменная ссылочного типа занимает 4 байта в 32-битной JVM.

• Выровнять отступы

  Эта часть данных не имеет существенной роли и предназначена только для того, чтобы занять место. Для Hotspot JVM управление памятью осуществляется в блоках по 8 байтов, а заголовок объекта, не являющегося массивом, составляет ровно 8 байтов (32-разрядная JVM) или 16 байтов (64-разрядная JVM), поэтому используется для заполнения выравнивания. когда данные экземпляра не кратны 8 байтам.

Разобравшись с расположением объектной памяти, давайте взглянем на приведенный выше код: в высокопроизводительной 32-битной JVM ссылочная переменная занимает 4 байта, поэтомуPaddedAtomicReferenceРаздел данных экземпляра объектного света типа содержитp0-pe15 ссылочных переменных, плюс от родительского классаAtomicReferenceВсего 16 эталонных переменных, унаследованных вheadиtailОн не должен загружаться в одну и ту же строку кэша, чтобы операции на головном узле и хвостовом узле очереди не были сериализованы из-за блокировки кеша, и не возникало пинг-понгового эффекта взаимного сдерживания, что улучшает параллелизм очереди.производительность.

Три элемента параллельного программирования

После крещения упомянутого выше CPU Cache мы, наконец, можем приступить к параллельному программированию на Java.Если вы действительно понимаете Cache, то понять модель параллелизма Java очень легко.

Три элемента параллельного программирования: атомарность, видимость и упорядоченность.

видимость

Невидимая проблема вызвана механизмом кэша ЦП. ЦП не имеет прямого доступа к основной памяти и большую часть времени оперирует кэшем. Поскольку каждый поток может выполнять переключение контекста на разных ядрах ЦП, можно понять, что каждый поток имеет его собственная «локальная память», конечно, эта локальная память не настоящая, это абстракция кэша ЦП:

если нитьThread-1Если копия общей переменной изменяется в собственной локальной памяти, она не сбрасывается в основную память вовремя и не уведомляется об этом.Thread-2Повторное чтение из основной памяти, затемThread-2не увидитThread-1Внесите изменения и продолжайте работать с копией общей переменной в собственной памяти. Это то, что мы часто называем моделью памяти Java (JMM).

Так как же потоки взаимодействуют с основной памятью? JMM определяет следующие 8 операций для обеспечения взаимодействия между потоками и основной памятью Реализация JVM должна удовлетворять следующим операциям для всех переменных, которые являются атомарными и неделимыми (для переменных типа double и long операции загрузки, сохранения, чтения, записи допускают исключения на некоторых платформах)

• lock, переменная, действующая на основную память, идентифицирует объект как состояние монопольного потока.
• разблокировка, переменная, которая воздействует на основную память, освобождает объект из заблокированного состояния.
• читать, читать переменную из основной памяти
• загрузить, загрузить переменную, прочитанную чтением, в локальную память
• use, который передает переменную в локальной памяти механизму выполнения, который выполняется всякий раз, когда JVM выполняет инструкцию байт-кода, которой необходимо прочитать значение переменной
• assign, присваивает значение, полученное от механизма выполнения, переменной в локальной памяти, что выполняется каждый раз, когда JVM выполняет инструкцию байт-кода, которая требует, чтобы переменной было присвоено значение.
• store, поток записывает переменные из локальной памяти обратно в основную память
• запись, основная память принимает запрос на обратную запись потока для обновления переменных в основной памяти

Если нужно взаимодействовать с основной памятью, то нужно выполнять последовательноread,loadинструкция, илиstore,writeИнструкции, обратите внимание, что порядок здесь не подразумевает непрерывных, то есть для общих переменныхa,bМогут происходить следующие операцииread a -> read b -> load b -> load.

Таким образом, вы можете понять результат работы первого примера кода в начале этой статьи, потому чтоt2выполнение потокаsharedVariable = oldValueТребуются три шага:assign -> store -> write, то естьt2После того, как поток изменит копию общей переменной в своей локальной памяти (assign),воплощать в жизньstore,writeПрежде чем записывать изменения обратно в основную память,t2Может быть подключен для чтения общих переменных. и даже еслиt2Записать модификацию обратно в оперативную память, если какой-либо механизм не уведомил об этомt1снова прочитать из основной памяти,t1Он по-прежнему будет охранять переменные в своей локальной памяти в оцепенении.

ПочемуvolatileМожно ли гарантировать видимость переменных в потоке? Поскольку JVM проходит черезvolatileМеханизм когерентности кеша мобилизуется, если используется параvolatileЕсли вы посмотрите на ассемблерный код, созданный после интерпретации JVM или JIT-компиляции, вы обнаружите, чтоvolatileдомен (поvolatileмодифицированная общая переменная), ассемблерная инструкция, сгенерированная операцией записи, будет иметьlockпрефикс, т.lockПрефикс указывает на то, что JVM отправит сигнал ЦП, который выполняет две функции:

• Перезаписи переменной немедленно сбрасываются в основную память (т.volatileЗапись поля приведет кassgin -> store -> writeатомарное исполнение)
• Уведомление других ЦП через шину о том, что общая переменная была обновлена.Для ЦП, который также кэширует общую переменную, если он получит уведомление, он сделает недействительной строку кэша, в которой общая переменная находится в его собственном кэше. В следующий раз, когда ЦП будет читать общую переменную, он обнаружит, что строка кэша была установлена ​​в недопустимое состояние, и будет повторно считана из основной памяти.

Вы обнаружите, что это протокол когерентности кеша, включенный под капотом. То есть добавляется общая переменнаяvolatileПосле этого каждый разvolatileЗапись в поле приведет к тому, что перезапись будет немедленно сброшена в основную память, а все последующиеvolatileЧтения полей — это все повторные чтения из основной памяти.

атомарность

Атомарность означает, что одна или несколько операций должны выполняться последовательно и не разлагаться. Как упоминалось выше, JMM предоставляет атомарные операции 8. Давайте рассмотрим несколько простых примеров, чтобы увидеть, какие операции являются атомарными на уровне кода.

заintпеременная типаaиb:

1. a = 1

   Эта операция атомарна, а инструкции байт-кодаputField,принадлежатьassignдействовать

2. a = b

   Эта операция не является атомарной и должна быть выполнена первой.getFieldчтение переменнойb, а затем выполнитьputFieldпарная переменнаяaсделать задание

3. a++

   по существуa = a + 1,Во-первыхgetFieldчтение переменнойa, затем выполнитеaddрассчитатьa + 1значение, наконец переданоputFieldприсвоить рассчитанное значениеa

4. Object obj = new Object()

   будет выполняться первымallocMemoryВыделите память для объекта, затем вызовите<init>Инициализация объекта и, наконец, возврат адреса памяти объекта более сложны и, естественно, не атомарны.

упорядоченность

Поскольку ЦП имеет несколько различных типов блоков выполнения инструкций, за один такт может выполняться несколько инструкций.Чтобы максимально улучшить параллелизм программы, ЦП распределяет различные типы инструкций по каждому исполнительному блоку для одновременного выполнения. Инструкции также могут быть переупорядочены во время компиляции.

Например:

a = 1;
b = a;
flag = true;

flag = trueможно переупорядочитьb = aчетноеa = 1раньше, но компилятор не будет переупорядочивать инструкции, которые имеют зависимости, например, не помещатьb = aпереупорядочитьa = 1, и компилятор также предотвратит переупорядочивание ЦП, вставив барьер инструкций.

Для двух инструкций с зависимостями компилятор может обеспечить порядок их выполнения. Но для инструкций, которые не имеют зависимостей, компилятор может только гарантировать, что первое, написанное впереди, встречается в написанном позже, напримерa = 1происходит доflag = true,ноa = 1существуетflag = trueВыполнено раньше, случается раньше только означаетa = 1Это поведениеflag = trueвидимый.

happens-before

В Java есть некоторые врожденные принципы предшествования для нашей справки.С помощью этих правил мы можем судить о порядке двух программ (то есть, есть ли связь, которая возникает раньше другой), а затем решить, нужно ли брать это.Синхронизировать.

• Правило порядка программ: в однопоточной среде, в соответствии с порядком написания программ, программа, написанная впереди, выполняется раньше, чем программа, написанная сзади.
• volatileПеременное правило: для одногоvolatileЗапись домена происходит перед последующей записью в тот же домен.volatileдомен читается.
• Правило монитора: поток освобождает объект блокировки, который он удерживает, происходит до того, как другие потоки (включая поток, который только что снял блокировку) заблокируют объект.
• Правило запуска потока: вызов потокаstartметод происходит перед выполнением этого потокаrunметод
• Правила завершения потока:t1вызов потокаt2.join,обнаруженоt2Выполнение потока завершается до того, какt1нить изjoinметод возвращает
• Правило прерывания потока: вызов потокаinterruptМетод происходит - до того, как этот поток ответит на прерывание
• Правила завершения объекта: создание объектаnewпроисходит до того, как этот объектfinalizeметод называется
• Переходный: если А происходит раньше В, а В происходит раньше С, то А происходит раньше С.

С помощью приведенных выше правил мы разрешаем сомнения, возникшие в начале этой статьи, почемуsynchronizedснятие блокировки, обновление CAS иvolatileЗаписи имеют одинаковую семантику (т. е. обе перезаписывают общие переменные, сразу видимые для всех потоков).

Выпуск блокировки имеет изменчивую семантику записи домена

new Thread(() -> {
    synchronized (lock) {
        int oldValue = sharedVariable;
        while (sharedVariable < MAX) {
            while (!changed) {
                try {
                    lock.wait();
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
            System.out.println(Thread.currentThread().getName() +
                               " watched the change : " + oldValue + "->" + sharedVariable);
            oldValue = sharedVariable;
            changed = false;
            lock.notifyAll();
        }
    }
}， "t1").start();

new Thread(() -> {
    synchronized (lock) {
        int oldValue = sharedVariable;
        while (sharedVariable < MAX) {
            while (changed) {
                try {
                    lock.wait();
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
            System.out.println(Thread.currentThread().getName() +
                               " do the change : " + sharedVariable + "->" + (++oldValue));
            sharedVariable = oldValue;
            changed = true;
            lock.notifyAll();
        }
    }
}， "t2").start();

1. заt2Одиночный поток использует правила порядка выполнения программы, стр.34общая переменная пары строкsharedVariableЗапись происходит перед разделом38Линия выходит из критической секции, чтобы снять блокировку.
2. заt1,t2параллельных операций,38Рядt2Снятие блокировки происходит до2Рядt1Приобретение замка.
3. Также согласно правилам процессуального порядка, первый2получение блокировки строки происходит до13общая переменная пары строкsharedVariableчитать.
4. Согласно приведенным выше 1, 2, 3 и транзитивности, мы можем получить первое34общая переменная пары строкsharedVariableЗапись происходит перед разделом13общая переменная пары строкsharedVariableчитать.

Резюме: блокируя запись-чтение общей переменной до и после, да, запись-чтение обычного поля имеет ту же семантику, что и запись-чтение изменчивого поля.

Обновления Atomic CAS имеют семантику записи в изменчивое поле.

Как упоминалось ранее, для чтения примитивных типов или ссылочных типов (use) и присвоение (assign), JMM требует реализации JVM для обеспечения атомарности. Поэтому нам не нужно беспокоиться об атомарности таких операций, но как гарантировать атомарность сложных операций?

Очень типичный пример, мы запускаем десять потоков на общих переменныхiВыполнить 10000 разi++Операция, может ли результат достичь ожидаемых 100 000?

private static volatile int i = 0;

public static void main(String[] args) throws InterruptedException {
    ArrayList<Thread> threads = new ArrayList<>();
    Stream.of("t0","t2","t3","t4","t5","t6","t7","t8","t9" ).forEach(
        threadName -> {
            Thread t = new Thread(() -> {
                for (int j = 0; j < 100; j++) {
                    i++;
                }
            }, threadName);
            threads.add(t);
            t.start();
        }
    );
    for (Thread thread : threads) {
        thread.join();
    }
    System.out.println(i);	
}

Я тестировал его несколько раз, и он не оправдал моих ожиданий.

может быть, вы бы сказалиiплюсvolatileЭто правда? Вы могли бы также попробовать это.

Если проанализировать рационально, даже добавивvolatileНи один. так какvolatileтолько убедитесь, что переменнаяiвидимость без гарантии атомарности его сложных операций.i++Это сложная операция, которую можно разбить на три шага: прочитать i, вычислить i+1 и присвоить результат вычисления i.

Чтобы оправдать ожидания, на этот разi++бывает - до следующегоi++, так как эта программа не может удовлетворить этому условию, то мы можем вручную добавить код, чтобы программа удовлетворяла этому условию. такой какi++Помещая в критическую секцию, это использование правил монитора, мы могли бы также проверить:

private static int i = 0;
private static Object lock = new Object();
public static void main(String[] args) throws InterruptedException {
    ArrayList<Thread> threads = new ArrayList<>();
    Stream.of("t0","t1","t2","t3","t4","t5","t6","t7","t8","t9" ).forEach(
        threadName -> {
            Thread t = new Thread(() -> {
                for (int j = 0; j < 10000; j++) {
                    synchronized (lock) {
                        i++;
                    }
                }
            }, threadName);
            threads.add(t);
            t.start();
        }
    );
    for (Thread thread : threads) {
        thread.join();
    }
    System.out.println(i);	//10000
}

Текущие результаты доказывают, что наша логика верна.В этом преимущество теоретической поддержки, так что у нас есть способ найти ее! Параллелизм — это не метафизика, пока у нас достаточно теоретической поддержки, мы можем легко писать качественный и точный код. Правильность — это первый элемент параллелизма! Имея это в виду, давайте поговорим об эффективности параллелизма.

Итак, давайте рассмотрим эффективность параллелизма в этом коде: есть ли способ улучшить ее? так какsynchronizedЭто приведет к тому, что только один поток из десяти потоков получит блокировку одновременно, а остальные девять будут заблокированы, а блокировка-пробуждение потока приведет к преобразованию из пользовательского режима в режим ядра (см.Как реализованы потокистатье), накладные расходы большие, и это только для выполнения следующихi++? Это приводит к напрасной трате ресурсов ЦП и общему падению пропускной способности.

Чтобы решить эту проблему, CAS родился.

CAS (Compare And Set) — это атомарная сложная операция с тремя параметрами: адрес данных, значение обновления и ожидаемое значение. Когда необходимо обновить общую переменную, CAS сначала сравнит, являются ли данные в адресе данных ожидаемым старым значением, и если да, обновит его, в противном случае сбой обновления не повлияет на данные по адресу данных.

CAS spin (циклическая операция CAS не выходит из цикла до тех пор, пока обновление не будет успешным) также называется оптимистической блокировкой.Он всегда думает, что степень параллелизма не так уж высока, поэтому, даже если на этот раз я не обновился успешно, я попытался еще несколько раз, и это было успешно Накладные расходы в несколько раз не так велики, как накладные расходы на блокировку потоков, поэтому производительность синхронизированного намного выше, чем у синхронизированного, когда фактическая степень параллелизма не высока. Но если степень параллелизма действительно высока, накладные расходы ЦП, вызванные длительным циклом CAS для нескольких потоков, не являются оптимистичными. Поскольку степень параллелизма в 80% случаев невелика, для повышения производительности вместо синхронизации часто используется CAS.

следующееUnsafeCAS спина в классе:

public final int getAndSetInt(Object var1, long var2, int var4) {
    int var5;
    do {
        var5 = this.getIntVolatile(var1, var2);
    } while(!this.compareAndSwapInt(var1, var2, var5, var4));

    return var5;
}

Операции CAS реализуются cmpxchg (Compare Exchange) на x86 (разные наборы инструкций различаются). Интерфейс CAS не представлен в Java, и CAS использует ``compareAndSetXxx的形式定义在Unsafe类（仅供Java核心类库调用）中。我们可以通过反射调用，但是JDK提供的Серия классов атомарных операций AtomicXxx уже отвечает большинству наших потребностей.

Итак, давайте посмотрим на запуск десяти потоков для выполнения 1000 000 раз.i++При использовании CAS и использованииsynchronizedРазница в производительности между двумя случаями:

CAS составляет около 200:

private static AtomicInteger i = new AtomicInteger(0);
public static void main(String[] args) throws InterruptedException {
    ArrayList<Thread> threads = new ArrayList<>();
    long begin = System.currentTimeMillis();
    Stream.of("t0","t1","t2","t3","t4","t5","t6","t7","t8","t9" ).forEach(
        threadName -> {
            Thread t = new Thread(() -> {
                for (int j = 0; j < 10000; j++) {
                    i.getAndIncrement();
                }
            }, threadName);
            threads.add(t);
            t.start();
        }
    );
    for (Thread thread : threads) {
        thread.join();
    }
    long end = System.currentTimeMillis();
    System.out.println(end - begin);	//70-90之间
}

использоватьsynchronizedОколо 480 или около того:

private static int i = 0;
private static Object lock = new Object();
public static void main(String[] args) throws InterruptedException {
    ArrayList<Thread> threads = new ArrayList<>();
    long begin = System.currentTimeMillis();
    Stream.of("t0","t1","t2","t3","t4","t5","t6","t7","t8","t9" ).forEach(
        threadName -> {
            Thread t = new Thread(() -> {
                for (int j = 0; j < 1000000; j++) {
                    synchronized (lock) {
                        i++;
                    }
                }
            }, threadName);
            threads.add(t);
            t.start();
        }
    );
    for (Thread thread : threads) {
        thread.join();
    }
    long end = System.currentTimeMillis();
    System.out.println(end - begin);
}

Но наш вопрос не решен, почему обновление CAS атомного классаvolatileСемантика письма? Только CAS может обеспечить толькоuse -> assginЭто атомарно.

Взгляните на исходный код атомарного класса, чтобы знать,AtomicInteger, остальные аналогичны:

public class AtomicInteger extends Number implements java.io.Serializable {
    private volatile int value;
    public final int getAndSet(int newValue) {
        return unsafe.getAndSetInt(this, valueOffset, newValue);
    }
}

Вы обнаружите, что атомарный класс инкапсулируетvolatileДомен, вдруг откроешь. CAS обновленvolatileдомен, мы знаемvolatileОбновление домена вызовет две вещи:

• Flush перезаписывает в основную память немедленно
• Уведомлять другие процессоры о аннулировании строк кэша

volatile запрещает изменение порядка

Другая семантика volatile состоит в том, чтобы запретить переупорядочивание команд, т.е.volatileсгенерированные инструкции по сборкеlockНаличие барьера инструкций предотвращает переупорядочивание инструкций перед барьером после барьера. Этот эффект идеально подходит для случая оптимизации параллелизма с использованием одноэлементного шаблона.

ленивый режим загрузки

Конструктор класса выполняется на этапе инициализации процесса загрузки класса (класс должен быть инициализирован немедленно, когда на него активно ссылаются)<clinit>В соответствии с характеристиками явно объявленной статической инициализации переменной. (Для активной ссылки, пассивной ссылки, конструктора классов и процесса загрузки классов см. «Углубленное понимание виртуальной машины Java (второе издание)»)

public class SingletonObject1 {

    private static final SingletonObject1 instance = new SingletonObject1();

    public static SingletonObject1 getInstance() {
        return instance;
    }

    private SingletonObject1() {

    }
}

Что такое активная ссылка на класс:

• new,getStatic,putStatic,invokeStaticДля классов, задействованных в четырех инструкциях байт-кода, соответствующий языковой уровень заключается в создании экземпляра класса, чтении статических полей класса, изменении статических полей класса и вызове статических методов класса.
• пройти черезjava.lang.reflectКогда метод пакета делает рефлексивный вызов класса
• При инициализации класса, если его родительский класс не был инициализирован, сначала инициализируйте его родительский класс
• Когда JVM запускается, она сначала инициализирует класс, в котором находится основная функция.

Что такое пассивная ссылка на класс:

• Доступ к статической переменной родительского класса через подкласс, подкласс не будет инициализирован сразу
• Классы, на которые ссылаются определения массивов, не инициализируются немедленно
• Доступ к константе класса, класс не будет немедленно инициализирован (поскольку после оптимизации распространения констант на этапе компиляции константа была скопирована в пул констант текущего класса)

Режим голодного человека 1

Создавайте экземпляры только при необходимости (это позволяет избежать преждевременной загрузки больших объектов памяти, которые не используются):

public class SingletonObject2 {

    private static SingletonObject2 instance = null;

    public static SingletonObject2 getInstance() {
        if (SingletonObject2.instance == null) {
            SingletonObject2.instance = new SingletonObject2();
        }
        return SingletonObject2.instance;
    }

    private SingletonObject2() {

    }
}

Режим голодного человека 2

Голодный режим в приведенном выше примере прекрасно работает в одном потоке, но когда он вызывается одновременноgetInstance,может появитьсяt1Поток только что завершил выполнение6Линия не успела создать объект,t2Поток выполняется до тех пор, пока6ОК, это приведет к тому, что несколько потоков придут к первому7линии и выполнить, в результате чегоSingletonObject2создается несколько раз, поэтому мы будем6-7линия черезsynchronizedСериализация:

public class SingletonObject3 {
    private static SingletonObject3 instance = null;

    public static SingletonObject3 getInstance() {
        synchronized (SingletonObject3.class) {
            if (SingletonObject3.instance == null) {
                SingletonObject3.instance = new SingletonObject3();
            }
        }
        return SingletonObject3.instance;
    }

    private SingletonObject3() {

    }

}

DoubleCheckedLocking

мы уже знаемsynchronizedЭто тяжеловесная блокировка. Если создается экземпляр синглтона, он должен получать блокировку каждый раз при получении экземпляра. В долгосрочной перспективе накладные расходы высоки, поэтому мы добавляем суждение при получении экземпляра. Если синглтон был создан экземпляр, пропустите его Действия для получения блокировок (конфликты возможны только при инициализации синглтона):

public class SingletonObject4 {

    private static SingletonObject4 instance = null;

    public static SingletonObject4 getInstance() {
        if (SingletonObject4.instance == null) {
            synchronized (SingletonObject4.class){
                if (SingletonObject4.instance == null) {
                    SingletonObject4.instance = new SingletonObject4();
                }
            }
        }
        return SingletonObject4.instance;
    }

    private SingletonObject4() {
        
    }
}

DCL2

Это действительно нормально? Это правда, что только один поток может войти в строку 9 для создания объекта одновременно, но не забывайтеnew Object()Его можно сломать! Соответствующие псевдоинструкции выглядят следующим образом:

allocMemory 	//为对象分配内存
<init>		    //执行对象构造器
return reference //返回对象在堆中的地址

И три вышеупомянутых шага не имеют зависимостей, что означает, что они могут быть переупорядочены следующим образом:

allocMemory 	//为对象分配内存
return reference //返回对象在堆中的地址
<init>		    //执行对象构造器

Это может привести кt1Поток выполняется до2линейное время,t1Оценка потокаinstanceСправочный адрес неnullТак что используйте этоinstance, а объект еще не построен! ! Это означает, что если объект может содержать ссылочные переменные какnullбез правильной инициализации, еслиt1Если поток просто обращается к переменной, будет выдано исключение нулевого указателя.

Поэтому мы используемvolatileзапретить<init>переупорядочитьinstanceПосле назначения:

public class SingletonObject5 {
    
    private volatile static SingletonObject5 instance = null;

    public static SingletonObject5 getInstance() {
        if (SingletonObject5.instance == null) {
            synchronized (SingletonObject5.class) {
                if (SingletonObject5.instance == null) {
                    SingletonObject5.instance = new SingletonObject5();
                }
            }
        }
        return SingletonObject5.instance;
    }

    private SingletonObject5() {
        
    }
}

InstanceHolder

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

public class SingletonObject6 {
    
    private static class InstanceHolder{
        public static SingletonObject6 instance = new SingletonObject6();    
    }

    public static SingletonObject6 getInstance() {
        return InstanceHolder.instance;
    }

    private SingletonObject6() {
        
    }

}

Конструктор экземпляра перечисления будет вызываться только один раз.

Это требуется спецификацией JVM и должно быть гарантировано реализацией JVM.

public class SingletonObject7 {
    
    private static enum Singleton{
        INSTANCE;

        SingletonObject7 instance;
        private Singleton() {
            instance = new SingletonObject7();
        }
    }

    public static SingletonObject7 getInstance() {
        return Singleton.INSTANCE.instance;
    }

    private SingletonObject7() {
        
    }

}

(Конец полного текста)

Ссылка на ссылку

• Очень подробная статья о ложном совместном использовании, заполнении строк кэша и кэшах ЦП.
• Что нужно знать о кэш-памяти процессора
• 7 примеров научно-популярного кэша ЦП -> Английский оригинал
• ложный обмен

Протокол согласованности кэша:

• MSI
• MESI