Пользователь
0,0
рейтинг
15 января 2014 в 09:32

Разработка → А как же всё-таки работает многопоточность? Часть II: memory ordering

картинка для привлечения внимания

Знание об управлении потоками, которое мы получили в прошлом топике, конечно, велико, но вопросов остаётся всё равно много. Например: «Как работает happens-before?», «Правда ли, что volatile — это сброс кешей?», «Зачем вообще было городить какую-то модель памяти? Нормально же всё было, что началось-то такое?»

Как и прошлая статья, эта построена по принципу «сначала кратко опишем, что должно происходить в теории, а потом отправимся в исходники и посмотрим, как это происходит там». Таким образом, первая часть во многом применима не только к Java, а потому и разработчики под другие платформы могут найти для себя что-то полезное.


Теоретический минимум

Всё возрастающая производительность железа возрастает не просто так. Инженеры, которые разрабатывают, скажем, процессоры, придумывают множество разнообразных оптимизаций, позволяющих выжать из вашего кода ещё больше абстрактных попугаев. Однако бесплатной производительности не бывает, и в этом случае ценой оказывается возможная контринтуитивность того, как выполняется ваш код. Разнообразных особенностей железа, скрытых от нас абстракциями, очень много. Рекомендую тем, кто этого ещё не сделал, ознакомиться с докладом Сергея Walrus Куксенко, который называется «Quantum Performance Effects» и отлично демонстрирует, как неожиданно ваши абстракции могут протечь. Мы не будем далеко ходить за примером, и взглянем на кеши.

Устройство кешей


Запрос к «основной памяти» — операция дорогая, и даже на современных машинах может занимать сотни наносекунд. За это время процессор мог бы успеть выполнить уйму инструкций. Чтобы избежать непотребства в виде вечных простоев, используются кеши. Простыми словами, процессор хранит прямо рядом с собой копии часто используемого содержимого основной памяти. Более сложными словами о различных типах кешей и их иерархиях можно почитать тут, а нас больше интересует то, как гарантируется актуальность данных в кеше. И если в случае с одним процессором (или ядром, в дальнейшем будет использоваться термин процессор) никаких проблем, очевидно, нет, то при наличии нескольких ядер (YAY MULTITHREADING!) уже начинают возникать вопросы.
Как процессор A может знать, что процессор B поменял какое-то значение, если у A оно закешировано?

Или, иными словами, как обеспечить когерентность кешей?

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

Протоколы когерентности кешей


Разнообразных протоколов существует много, и варьируются они не только от производителя железа к производителю железа, но и постоянно развиваются даже в рамках одного вендора. Тем не менее, несмотря на обширность мира протоколов, у большинства из них есть некоторые общие моменты. Несколько умаляя общность, будем рассматривать протокол MESI. Конечно, есть и подходы, которые кардинальным образом от него отличаются: например, Directory Based. Однако, в рамках данной статьи они не рассматриваются.

В MESI же каждая ячейка в кеше может находиться в одном из четырёх состояний:
  • Invalid: значения нет в кеше
  • Exclusive: значение есть только в этом кеше, и оно пока не было изменено
  • Modified: значение изменено этим процессором, и оно пока не находится ни в главной памяти, ни в кеше какого-либо другого процессора
  • Shared: значение присутствует в кеше более чем у одного процессора


Для перехода из состояния происходит обмен сообщениями, формат которого так же является частью протокола. Кстати, довольно иронично, что на столь низком уровне смена состояний происходит именно через обмен сообщениями. Problem, Actor Model Haters?

В целях уменьшения объёма статьи и побуждения читателя к самостоятельному изучению, я не буду описывать обмен сообщениями в деталях. Желающие могут выудить эту информацию, например, в замечательной статье Memory Barriers: a Hardware View for Software Hackers. Традиционно, более глубокие размышления на тему от cheremin можно почитать в его блоге.

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

Оптимизации для MESI и проблемы, которые они порождают


Store Buffers


Для того, чтобы что-то записать в ячейку памяти, находящуюся в состоянии Shared, необходимо отослать сообщение Invalidate и дождаться того, как все его подтвердят. Всё это время процессор будет простаивать, что невероятно печально, поскольку время, в течение которого дойдёт сообщение, как правило на несколько порядков выше, чем необходимо для выполнения простых инструкций. Чтобы избежать такой бессмысленной и беспощадной потери процессорного времени, придумали Store Buffers. Процессор помещает значения, которые хочет записать, в этот буфер и продолжает выполнять инструкции. А когда получены необходимые Invalidate Acknowledge, данные наконец отправляются в основную память.

Разумеется, тут есть несколько подводных граблей. Первые из них весьма очевидны: если до того, как значение покинет буфер, этот же процессор попытается его прочитать, он получит совсем не то, что только что записал. Это решается с помощью Store Forwarding: всегда проверяется, а не находится ли запрашиваемое значение в буфере; и если оно там, то значение берётся именно оттуда.

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

void executedOnCpu0() {
    value = 10;
    finished = true;
}

void executedOnCpu1() {
    while(!finished);
    assert value == 10;
}

Казалось бы, что может пойти не так? Вопреки тому, как можно подумать, многое. Например, если окажется так, что к началу выполнения кода finished находится у Cpu0 в состоянии Exclusive, а value — в состоянии, например, Invalid, то value покинет буфер позже, чем finished. И вполне возможно, что Cpu1 прочитает finished как true, а value при этом окажется не равным 10. Такое явление называют reordering. Разумеется, reordering происходит не только в таком случае. Например, компилятор из каких-либо своих соображений вполне может поменять местами некоторые инструкции.

Invalidate Queues


Как можно легко догадаться, store buffers не бесконечны, и потому имеют тенденцию переполняться, в результате чего всё же приходится зачастую ждать Invalidate Acknowledge. А они иногда могут выполняться очень долго, если процессор и кеш заняты. Решить эту проблему можно, введя новую сущность: Invalidate Queue. Все запросы на инвалидацию ячеек памяти будут помещаться в эту очередь, а acknowledgement будет отправляться моментально. Фактически же значения будут инвалидированы тогда, когда процессору это будет удобно. При этом процессор обещает вести себя хорошо, и не будет отправлять никаких сообщений по этой ячейке до тех пор, пока её не инвалидирует. Чуете подвох? Вернёмся к нашему коду.

void executedOnCpu0() {
    value = 10;
    finished = true;
}

void executedOnCpu1() {
    while(!finished);
    assert value == 10;
}


Предположим, что нам повезло (или мы воспользовались неким тайным знанием), и Cpu0 записал ячейки памяти в нужном нам порядке. Гарантирует ли это то, что они попадут в кеш Cpu1 в том же порядке? Как вы уже могли понять, нет. Будем также считать, что сейчас ячейка value находится в кеше Cpu1 в состоянии Exclusive. Порядок происходящих действий тогда может оказаться таким:

# Cpu0 Cpu0:value Cpu0:finished Cpu1 Cpu1:value Cpu1:finished
0 (...) 0 (Shared) false (Exclusive) (...) 0 (Shared) (Invalid)
1
value = 10;
- store_buffer(value)
← invalidate(value)
0 (Shared)
(10 in store buffer)
false (Exclusive)
2
while (!finished);
← read(finished)
0 (Shared) (Invalid)
3
finished = true;
0 (Shared)
(10 in store buffer)
true (Modified)
4
→ invalidate(value)
← invalidate_ack(value)
- invalidate_queue(value)
0 (Shared)
(in invalidation queue)
(Invalid)
5
→ read(finished)
← read_resp(finished)
0 (Shared)
(10 in store buffer)
true (Shared)
6
→ read_resp(finished)
0 (Shared)
(in invalidation queue)
true (Shared)
7
> assert value == 10;
0 (Shared)
(in invalidation queue)
true (Shared)
Assertion fails
N
- invalidate(value)
(Invalid) true (Shared)


Многопоточность это просто и понятно, не правда ли? Проблема находится на шагах (4) — (6). Получив invalidate в (4), мы не выполняем его, а записываем в очередь. А в шаге (6) мы получаем read_response на запрос read, который был отправлен раньше того, в (2). Однако, это не заставляет нас инвалидировать value, и потому assertion падает. Если бы операция (N) выполнилась раньше, то у нас бы ещё был шанс, но сейчас эта чёртова оптимизация нам всё сломала! Но с другой стороны, она такая быстрая и даёт нам ультралоулэйтенси™! Вот ведь дилемма. Разработчики железа не могут заранее магически знать, когда применение оптимизации допустимо, а когда она может что-то сломать. И поэтому они передают проблему нам, добавляя: «It's dangerous to go alone. Take this!»

Hardware Memory Model


Волшебный меч, которым снабжают разработчиков, отправившихся сражаться с драконами — на самом деле вовсе не меч, а скорее Правила Игры. В них описано, какие значения может увидеть процессор при выполнении им или другим процессором тех или иных действий. А вот Memory Barrier — это уже что-то, гораздо больше похожее на меч. В рассматриваемом нами примере MESI бывают такие мечи:

Store Memory Barrier (также ST, SMB, smp_wmb) — инструкция, заставляющая процессор выполнить все store, уже находящиеся в буфере, прежде чем выполнять те, что последуют после этой инструкции

Load Memory Barrier (также LD, RMB, smp_rmb) — инструкция, заставляющая процессор применить все invalidate, уже находящиеся в очереди, прежде чем выполнять какие-либо инструкции load


Имея в распоряжении новое оружие, мы с лёгкостью можем починить свой пример:

void executedOnCpu0() {
    value = 10;
    storeMemoryBarrier();
    finished = true;
}

void executedOnCpu1() {
    while(!finished);
    loadMemoryBarrier();
    assert value == 10;
}


Прекрасно, всё работает, мы довольны! Можно идти и писать классный производительный и корректный многопоточный код. Хотя стоп…

Казалось бы, причём здесь Java?


Write Once @ Run Anywhere


Все эти разнообразные протоколы когерентности кешей, мембары, сброшенные кеши и прочие специфичные для платформы вещи, по идее, не должны волновать тех, кто пишет код на Java. Java ведь платформо-независима, верно? И действительно, в Модели Памяти Java нет понятия reordering.
NB: Если эта фраза вас смущает, не продолжайте читать статью, пока не поймёте, почему. И читайте, например, это.
А вообще, звучит интересно. Понятия «reordering» нет, а сам reordering есть. Власти явно что-то скрывают! Но даже если отказаться от конспирологической оценки окружающей действительности, мы останемся с любопытством и желанием знать. Утолим же его! Возьмём простенький класс, иллюстрирующий наш недавний пример:[github]

public class TestSubject {

    private volatile boolean finished;
    private int value = 0;

    void executedOnCpu0() {
        value = 10;
        finished = true;
    }

    void executedOnCpu1() {
        while(!finished);
        assert value == 10;
    }

}


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

В прошлый раз мы смотрели на сишный интерпретатор, который на самом деле не используется в production. В этот раз мы будем смотреть на то, как действует клиентский компилятор(C1). Я использовал для своих целей openjdk-7u40-fcs-src-b43-26_aug_2013.

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

$ javac TestSubject.java && javap -c TestSubject
void executedOnCpu0();
  Code:
     0: aload_0          // Толкаем в стек this
     1: bipush        10 // Толкаем в стек 10
     3: putfield      #2 // Записываем во второе поле this (value) значение с вершины стека(10)
     6: aload_0          // Толкаем в стек this
     7: iconst_1         // Толкаем в стек 1
     8: putfield      #3 // Записываем в третье поле this (finished) значение с вершины стека(1)
    11: return

void executedOnCpu1();
  Code:
     0: aload_0          // Толкаем в стек this
     1: getfield      #3 // Загружаем в стек третье поле this (finished)
     4: ifne          10 // Если там не ноль, то переходим к метке 10(цикл завершён)
     7: goto          0  // Переходим к началу цикла
    10: getstatic     #4 // Получаем статическое служебное поле $assertionsDisabled:Z
    13: ifne          33 // Если assertions выключены, переходим к метке 33(конец)
    16: aload_0          // Толкаем в стек this
    17: getfield      #2 // Загружаем в стек второе поле this (value)
    20: bipush        10 // Толкаем в стек 10
    22: if_icmpeq     33 // Если два верхних элемента стека равны, переходим к метке 33(конец)
    25: new           #5 // Создаём новый java/lang/AssertionError
    28: dup              // Дублируем значение на верхушке стека
    29: invokespecial #6 // Вызываем конструктор (метод <init>)
    32: athrow           // Кидаем то, что лежит на верхушке стека
    33: return

NB: Не стоит пытаться по байт-коду определить точное поведение программы в рантайме. После того, как JIT-компилятор сделает своё дело, всё может измениться очень сильно.
Что интересного мы здесь можем заметить? Первая мелочь, которую многие забывают — это то, что по умолчанию assertion-ы выключены. Включить их можно в рантайме с помощью ключика -ea. Но это так, ерунда. То, за чем мы сюда пришли, — имена инструкций getfield и putfield. Вы думаете о том же, о чём и я? (Конечно, Глеб! Только как мы построим Сферу Дайсона из бекона, вантуза и двух бюстгальтеров?!)

Down the Rabbit Hole


Обратив внимание на то, что для обоих полей используются одни и те же инструкции, посмотрим, где содержится информация о том, что поле является volatile. Для хранения данных о полях используется класс share/vm/ci/ciField.hpp. Нас интересует метод
176
bool is_volatile    () { return flags().is_volatile(); }
Для того, чтобы узнать, что C1 делает с доступом к volatile полям, можно найти все использования этого метода. Немного побродив по подземельями и собрав несколько Свитков с Древними Знаниями, мы оказываемся в файле share/vm/c1/c1_LIRGenerator.cpp. Как намекает нам его имя, он занимается генерацией низкоуровневого промежуточного представления (LIR, Low-Level Intermediate Representation) нашего кода.

C1 Intermediate Representation на примере putfield


При создании IR в C1 наша инструкция putfield в итоге обрабатывается здесь. Рассмотрим особые действия, которые выполняются для volatile полей и довольно быстро наткнёмся на знакомые слова:
1734
1735
1736
if (is_volatile && os::is_MP()) {
    __ membar_release();
}
Здесь __ — это макрос, который раскрывается в gen()->lir()->. А метод membar_release определён в share/vm/c1/c1_LIR.hpp:
1958
void membar_release()                          { append(new LIR_Op0(lir_membar_release)); }
Фактически, эта строка добавила в промежуточное представление нашего кода инструкцию membar_release. После этого происходит следующее:
1747
1748
1749
if (is_volatile && !needs_patching) {
    volatile_field_store(value.result(), address, info);
}
Реализация метода volatile_field_store уже платформо-зависима. На x86 (cpu/x86/vm/c1_LIRGenerator_x86.cpp), например, действия происходят довольно простые: проверяется, не является ли поле 64-битным, и если это так, то используется Чёрная Магия для того, чтобы гарантировать атомарность записи. Все же помнят, что в при отсутствии модификатора volatile поля типа long и double могут быть записаны неатомарно?

И, наконец, в самом конце, ставится ещё один membar, на этот раз без release:
1759
1760
1761
if (is_volatile && os::is_MP()) {
    __ membar();
}
1956
void membar()                                  { append(new LIR_Op0(lir_membar)); }
NB: Я, конечно, коварно скрыл некоторые происходящие действия. Например, манипуляции, связанные с GC. Изучить их предлагается читателю в качестве самостоятельного упражнения.


Преобразование IR в ассемблер


Мы проходили только ST и LD, а тут встречаются новые типы барьеров. Дело в том, что то, что мы видели раньше — это пример барьеров для низкоуровнего MESI. А мы уже перешли на более высокий уровень абстракции, и термины несколько изменились. Пусть у нас есть два типа операций с памятью: Store и Load. Тогда есть четыре упорядоченные комбинации из двух операций: Load и Load, Load и Store, Store и Load, Store и Store. Две категории мы рассмотрели: StoreStore и LoadLoad — и есть те самые барьеры, что мы видели, говоря о MESI. Остальные две тоже должны быть довольно легко усваиваемыми. Все load, произведённые до LoadStore, должны завершиться прежде, чем любой store после. Со StoreLoad, соответственно, наоборот. Более подробно об этом можно почитать, например, в JSR-133 Cookbook.

Кроме того, выделяют понятия операции с семантикой Acquire и операции с семантикой Release. Последняя применима к операциям записи, и гарантирует, что любые действия с памятью, идущие до этой операции, обязаны завершиться до её начала. Иными словами, операцию с семантикой write-release нельзя reorder-ить с любой операцией с памятью, идущей до неё в тексте программы. Такую семантику нам может обеспечить комбинация LoadStore + StoreStore memory barrier. Acquire же, как можно догадаться, имеет противоположную семантику, и может быть выражена с помощью комбинации LoadStore + LoadLoad.

Теперь мы понимаем, какие мембары расставляет JVM. Однако, пока мы видели это только в LIR, который, хоть и Low-level, но всё ещё не является нативным кодом, который должен сгенерировать нам JIT. Исследование того, как именно C1 преобразует LIR в нативный код, выходит за пределы этой статьи, потому мы без лишних оговорок отправимся прямиком в файлик share/vm/c1/c1_LIRAssembler.cpp. Там и происходит всё превращение IR в ассемблерный код. Например, в очень зловещей строке рассматривается lir_membar_release:
665
666
667
case lir_membar_release:
      membar_release();
      break;
Вызываемый метод уже платформо-зависим, и исходный код для x86 лежит в cpu/x86/vm/c1_LIRAssembler_x86.cpp:
3733
3734
3735
3736
void LIR_Assembler::membar_release() {
  // No x86 machines currently require store fences
  // __ store_fence();
}
Шикарно! Благодаря строгой модели памяти (в том числе, TSO — Total Store Order), на этой архитектуре все записи и так имеют семантику release. А вот со вторым membar всё немного сложнее:
3723
3724
3725
3726
void LIR_Assembler::membar() {
  // QQQ sparc TSO uses this,
  __ membar( Assembler::Membar_mask_bits(Assembler::StoreLoad));
}

Тут макрос __ разворачивается в _masm->, а метод membar лежит в cpu/x86/vm/assembler_x86.hpp и выглядит так:
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
1263
void membar(Membar_mask_bits order_constraint) {
  if (os::is_MP()) {
    // We only have to handle StoreLoad
    if (order_constraint & StoreLoad) {
        // All usable chips support "locked" instructions which suffice
        // as barriers, and are much faster than the alternative of
        // using cpuid instruction. We use here a locked add [esp],0.
        // This is conveniently otherwise a no-op except for blowing
        // flags.
        // Any change to this code may need to revisit other places in
        // the code where this idiom is used, in particular the
        // orderAccess code.
        lock();
        addl(Address(rsp, 0), 0);// Assert the lock# signal here
    }
  }
}
Выходит, на x86 на запись каждой volatile переменной мы ставим дорогой StoreLoad барьер в виде lock addl $0x0,(%rsp). Операция дорогая, поскольку она заставляет нас выполнить все Store в буфере. Однако она даёт нам тот самый эффект, что мы ожидаем от volatile — все остальные потоки увидят как минимум значение, бывшее актуальным на момент её исполнения.

Получается, что read на x86 должен быть самым обычным read. Беглый осмотр метода LIRGenerator::do_LoadField говорит нам, что после чтения, как мы того и ожидали, выставляется membar_acquire, который на x86 выглядит так:
3728
3729
3730
3731
void LIR_Assembler::membar_acquire() {
  // No x86 machines currently require load fences
  // __ load_fence();
}
Это, конечно, ещё не значит, что volatile read не привносит никакого оверхеда по сравнению с обычным read. Например, хоть в нативный код ничего и не добавляется, наличие барьера в самой IR запрещает компилятору переставлять некоторые инструкции. (иначе можно поймать забавные баги). Есть и множество других эффектов от использования volatile. Почитать об этом можно, например, вот в этой статье.

Проверка на вшивость


PrintAssembly


Сидеть и гадать на исходниках — благородное занятие, достойное любого уважающего себя философа. Однако, на всякий случай мы всё же заглянем в PrintAssembly. Для этого добавим в подопытного кролика много вызовов нужных методов в цикле, отключим инлайнинг (чтобы было легче ориентироваться в сгенерированном коде) и запустимся в клиентской VM, не забыв включить assertions:

$ java -client -ea -XX:+UnlockDiagnosticVMOptions -XX:+PrintAssembly -XX:MaxInlineSize=0 TestSubject
...
  # {method} 'executedOnCpu0' '()V' in 'TestSubject'
...
  0x00007f6d1d07405c: movl   $0xa,0xc(%rsi)
  0x00007f6d1d074063: movb   $0x1,0x10(%rsi)
  0x00007f6d1d074067: lock addl $0x0,(%rsp)     ;*putfield finished
                                                ; - TestSubject::executedOnCpu0@8 (line 15)
...
  # {method} 'executedOnCpu1' '()V' in 'TestSubject'
...
  0x00007f6d1d061126: movzbl 0x10(%rbx),%r11d   ;*getfield finished
                                                ; - TestSubject::executedOnCpu1@1 (line 19)
  0x00007f6d1d06112b: test   %r11d,%r11d
...

Вот и славно, всё выглядит ровно так, как мы и предсказали. Осталось проверить, действительно ли при отсутствии volatile что-то может пойти не так. Ранее в своей статье TheShade демонстрировал сломанный Double-Checked Locking, но мы тоже хотим немного поизвращаться, и потому попробуем сломать всё сами. Ну, или почти сами.

Демонстрация поломки без volatile


Проблема демонстрации такого реордеринга заключается в том, что вероятность его происхождения в общем случае не очень-то и велика, а на отдельных архитектурах HMM его и вовсе не позволит. Потому нам нужно либо разжиться альфой, либо положиться на реордеринг в компиляторе. И, кроме того, запустить всё много-много-много раз. Как хорошо, что нам не придётся изобретать для этого велосипед. Воспользуемся замечательной утилитой jсstress. Если говорить совсем просто, то она многократно выполняет некоторый код и собирает статистику по результату выполнения, делая всю грязную работу за нас. Включая и ту, о необходимости которой многие и не подозревают.

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

static class State {
    int x;
    int y; // acq/rel var
}

@Override
public void actor1(State s, IntResult2 r) {
    s.x = 1;
    s.x = 2;
    s.y = 1;
    s.x = 3;
}

@Override
public void actor2(State s, IntResult2 r) {
    r.r1 = s.y;
    r.r2 = s.x;
}


У нас есть два потока: один меняет состояние, а второй — читает состояние и сохраняет результат, который увидел. Фреймворк за нас агрегирует результаты, и проверяет их по некоторым правилам. Для нас интересны два результата, которые может увидеть второй поток: [1, 0] и [1, 1]. В этих случаях мы прочли y == 1, но при этом мы либо не увидели вообще никаких записей в x (x == 0), либо увидели не самую последнюю на момент записи y, то есть x == 1. Согласно нашей теории, такие результаты должны встречаться. Проверим это:

$ java -jar tests-all/target/jcstress.jar -v -t ".*UnfencedAcquireReleaseTest.*"
...

Observed state Occurrence      Expectation                                            Interpretation
 [0, 0]          32725135        ACCEPTABLE       Before observing releasing write to, any value is OK for $x.
 [0, 1]             15           ACCEPTABLE       Before observing releasing write to, any value is OK for $x.
 [0, 2]             36           ACCEPTABLE       Before observing releasing write to, any value is OK for $x.
 [0, 3]           10902          ACCEPTABLE       Before observing releasing write to, any value is OK for $x.
 [1, 0]           65960    ACCEPTABLE_INTERESTING Can read the default or old value for $x after $y is observed.
 [1, 3]          50929785        ACCEPTABLE       Can see a released value of $x if $y is observed.
 [1, 2]             7            ACCEPTABLE       Can see a released value of $x if $y is observed.


Тут мы можем видеть, что в 65960 случаях из 83731840 (примерно 0.07%) мы увидели y == 1 && x == 0, что явно говорит о произошедшем реордеринге. Ура, можно завязывать.

У читателя теперь должно быть достаточно хорошее понимание происходящего, чтобы ответить на вопросы, заданные в начале статьи. Напомню:

  • Как работает happens-before?
  • Правда ли, что volatile — это сброс кешей?
  • Зачем вообще было городить какую-то модель памяти?

Ну что, всё встало на свои места? Если нет, то, стоит попробовать вникнуть в соответствующий раздел статьи ещё раз. Если это не помогает, добро пожаловать в комментарии!

And one more thing ©

Выполнять преобразования над исходным кодом может не только железо, но и вся среда исполнения. Для соблюдения требований JMM ограничения накладываются на все компоненты, где что-то может поменяться. Например, компилятор в общем случае может перестанавливать какие-то инструкции, однако многие оптимизации ему может запретить делать JMM.

Разумеется, серверный компилятор(С2) существенно умнее, чем С1, рассмотренный нами, и некоторые вещи в нём сильно отличаются. Например, семантика работы с памятью абсолютна иная.

В кишках многопоточности OpenJDK во многих местах используется проверка os::is_MP(), что позволяет улучшить производительность на однопроцессорных машинах, не выполняя некоторые операции. Если с помощью Запрещённых Искусств заставить JVM думать во время старта, что она исполняется на одном процессоре, то проживёт она не долго.

Большое спасибо доблестным TheShade, cheremin и artyushov за то, что они (вы|про)читали статью перед публикацией, убедившись тем самым, что я не принесу в массы вместо света какую-то бредовню, наполненную тупыми шутками и очепатками.
Вы что-нибудь поняли?

Проголосовало 276 человек. Воздержалось 115 человек.

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

Глеб Смирнов @gvsmirnov
карма
118,5
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (44)

  • +2
    А почему в демонстрации поломки не было воспроизведено значение [1, 1]?
    • +2
      А я ждал этого вопроса! Строго говоря, потому что я ленивый хрыщ. Это совсем редкий случай, и чтобы его добиться, скорее всего, нужно помочь компилятору быть более усердным, используя ключики -XX:+StressLCM и -XX:+StressGCM. Они рандомизируют instruction scheduling.
  • +3
    Отсутствие комментариев меня столь раздосадовало, что я добавил в конец опрос относительно усвоения материала. Пожалуйста, ответьте на него.
    • НЛО прилетело и опубликовало эту надпись здесь
      • +2
        :)
      • +2
        Ты ж сам знаешь всех кто так сделал ;)
        • НЛО прилетело и опубликовало эту надпись здесь
      • +1
        Не уверен, что кто-то будет (или даже должен) знать всё за пределами лабораторий, работающих с JVM или что-то оптимизирующих на низком уровне. Разве что, кто-то копался ради любопытства (но тогда и CV не так уж важно, если человек сам прошел так глубоко).

        На практике же, описанный уровень абстракции интересен и любопытен, но не более того. Я много раз сталкивался с многопоточными проблемами, но не вижу ни единой, где знание, полученное из этой статьи можно применить. Везде было достаточно чуть высшего уровня абстракции (т.е. там где объясняется, что такое happens-before, без подробностей, что стоит за этим). Вернее, даже так: сама java и ее библиотеки и формируют уровень абстракции, который скрывает эти детали. Возможно это может пригодиться в случае совсем уж экзотических багов или в случае взаимодействия через JNI.

        Я не пытаюсь сказать, что статья не найдет своего читателя. Просто всё знать невозможно, поэтому каждый человек по любой теме выбирает ту степень абстракции, в которую он готов вложить своё время (ожидая, что это окупит себя). Людей, которые действительно могут применить полученные знания на практике — я думаю, будут, единицы. И совсем, маловероятно, что найдутся те, кто «и так всё знал».
        • НЛО прилетело и опубликовало эту надпись здесь
          • 0
            Мне кажется это не такое уж редкое качество. А вот подсказки как правильно читать исходники были очень полезны. Я вот, например, тоже в сишном интерпретаторе копался. Оказывается, зря…
    • +6
      Одно дело прочитать, другое дело продумать и укрепить в глубине памяти :)

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

      Это не TLDR, но это отличная справочная статья, чтобы ее прочитать в общих чертах и при случае возвращаться для уточнения деталей.
  • +2
    Отличная статья. Стоит еще упомянуть следующее:

    Кэши процессора поделены на блоки (cache lines, CL),
    для современных Intel I7 размер CL на всех уровнях (L1, L2, L3) равен 64 байтам.
    MESI протокол работает в терминах CL. Из за этого может возникнуть эффект false sharing,
    когда не связанные в исходном коде участки памяти занимают 1 CL:

    class fs {
    	volatile long l1;
    	volatile long l2;
    }
    

    если переменные l1 и l2 попали в одну CL, то запись в любую из них повлечет за собой MESI invаlidate.

    Если поток 1 на CPU1 постоянно обновляет l1, а поток 2 на CPU2 постоянно обновляет l2, то производительность сильно упадет, поскольку оба CPU будут конкурировать за одну CL.

    Позволю себе упомянуть свою статью на эту тему: False sharing в многопоточном приложении на Java.
    • +1
      Только нужно заметить, что false sharing имеет чисто перформансный эффек, и не влияет на корректность.
      А вот объяснить людям, зачем нужна JMM и какие там могут быть эффекты на уровне железа — ИМХО более важно.
      • –1
        Полностью согласен. Но как показала моя практика, мелочей в случае многопоточных систем не бывает :)
    • +1
      Да, действительно. Это ещё одно место, где протекают абстракции, хотя это отражается только на производительности, но не на корректности.
    • 0
      Кстати как там дела обстоят с @Contended? Может быть присутствующие в треде TheShade знает?
      • НЛО прилетело и опубликовало эту надпись здесь
        • 0
          Спасибо за ответ. То есть дальше вот этого не пошло? Лежит в sun.misc, без -XX:-RestrictContended использовать нельзя… Какое-то ощущение незавершённости осталось.
  • +1
    Я так понимаю, что при заполнении Invalidate Queue, происходит принудительная инвалидация? Если да, то как часто это происходит (или что нужно сделать, чтобы это произошло)? И как сильно это тормозит приложение?
    • +1
      Я всё надеялся, что ответит Walrus, но, похоже, не судьба. Как гарантированно добиться подобного поведения — не очень ясно. Можно, наверное, организовать contention сразу на много-много полей, но всё равно не факт, что дойдёт до переполнения Invalidation Queue. Насколько сильно это может затормозить — хороший вопрос. Спекулировать я не стану, потому что тут слишком много факторов, которые на это влияют. Нужно мерить, а для этого нужно научиться стабильно воспроизводить.
      • +1
        Тут возникают детали, которых я просто уже не знаю. На самом деле, если Invalidation Queue заполнена — мы очевидно не будем посылать acknowledgement и ожидающее ядро будет стоять и ждать.
        Как часто это встречается? Думаю очень редко, ибо я нигде не видел упоминания такой проблемы.
  • +2
    Поясните пожалуйста, почему используется более тяжелый lock addl $0x0,(%rsp), вместо sfence/lfence? Или sfence/lfence используются когда доступены, просто это не было указано в статье?
    • НЛО прилетело и опубликовало эту надпись здесь
      • –1
        Немного не верится, т.к. в ядре Linux по возможности используются именно fence.

        У вас нет еще одной статьи на тему что быстрее (желательно от производителей CPU), а то пока получается слово Oracle против слова Linux (а последнему я верю чуть больше!).
    • +3
      Software Optimization Guide for AMD Family 15h Processors (Bulldozer):

      11.5.1 Locked Instructions as Memory Barriers
      Optimization
      Use locked instructions to implement Store/Store and Store/Load barriers.
      Application
      Applies to programs running on multicore processors or on multiple single core processors.

      Rationale

      On AMD family 15h processors, the SFENCE and MFENCE instructions are serializing. This stalls
      the pipeline and the processor core cannot begin processing any further instructions until all previous
      instructions are completed and any outstanding memory operations (such as prefetches and stores)
      have completed. (This stall applies only to the individual integer unit of the compute unit where the
      MFENCE or SFENCE instruction is executed.) Architecturally serializing instructions such as
      CPUID have the same pipeline stall behavior as the MFENCE and SFENCE instructions. The
      LOCKed instructions do not stall the pipeline and, thus, allow more instruction-level parallelism.
      • 0
        Спасибо! Нашёл ещё следующее:

        Intel® 64 and IA-32 Architectures Software Developer’s Manual Volume 3A: System Programming Guide, Part 1 ()
        8.3 SERIALIZING INSTRUCTIONS

        The following instructions are memory-ordering instructions, not serializing instructions.
        These drain the data memory subsystem. They do not serialize the instruction
        execution stream
        :*
        • Non-privileged memory-ordering instructions — SFENCE, LFENCE, and
        MFENCE.
        The SFENCE, LFENCE, and MFENCE instructions provide more granularity in controlling
        the serialization of memory loads and stores

        * LFENCE does provide some guarantees on instruction ordering. It does not execute until all prior
        instructions have completed locally, and no later instruction begins execution until LFENCE completes

        +8.2.3.8 Locked Instructions Have a Total Order

        Итого:
        * на AMD пока лучше использовать lock addl $0x0,(%rsp)
        * LFENCE в теории может/должен позволять переупорядочивать инструкции (как минимум в одном направлении), но и на Intel пока сделано не особо оптимально. Что оптимальнее sfence/lfence или lock addl $0x0,(%rsp) — из документации непонятно.
        * когда процессоры научатся правильно переупорядочивать, sfence/lfence будет оптимальнее.

        P.S.: В «кровавых подробностях» к статье, данной TheShade, сравниваются mfence и lock addl $0x0,(%rsp), а не sfence/lfence и lock addl $0x0,(%rsp). Тут есть разница! И как раз из-за этой разницы непонятно будут ли sfence/lfence оптимальнее lock addl $0x0,(%rsp) на Intel.
  • 0
    1. Сходил по ссылке в JDK-7170145, а там в прилинкованном баге:

    Мем годный, предлагаю зафорсить в узких кругах.

    2. У Walrus'а есть более полное и новое видео про микроэффекты в камнях, чем то, на которое ты ссылаешься:


    3. Статья прекрасная, жаль что ждать её пришлось так долго.

    4. Очень здорово видеть, как и здесь и в cuncurrency-interest дискуссия эволюционирует от понятия реордеринга к понятию валидных/невалидных по JMM трасс.
    • 0
      хотя нет, насчёт последнего пункта я погорячился. Всё же в статье серьёзный уклон сделал в сторону именно имплементации, а не спецификации. Со спекой вообще есть проблемы, но есть серьёзные надежды (в том числе мои, как JCK-инженера), что в JMM9 ситуация улучшится.
  • 0
    Я что-то на LoadLoad / StoreStore уже начал тупить, спасибо, что пояснил в частном порядке — думаю стоит явно пояснить еще раз для умных и таких тупых как я что именно это значит.
    • 0
      Читайте барьер XY как «Все операции X, произведённые до барьера, должны завершиться прежде, чем любая операция Y после».
  • 0
    Проголосовал «Чувак, я нихрена не понял из того ...», но читать было действительно интересно. Видимо буду перечитывать, пока не вникну. Интересно бы было прочитать подобную статью для .NET. Хотя там, как понимаю, проблем намного меньше.
  • 0
    Спасибо за статью, очень интересно. И полезно не только в свете JVM. В нашей JIT VM рано или поздно придется переходить на mark&sweep сборщик, а там уже без барьеров не обойтись. Ваши статьи будут как нельзя кстати.

    Не возражаете, если буду вас пытать вопросами по поводу барьеров памяти? =)

    P.S.: Вы случайно не знаете, каким образом работают интринсики gc барьеров в LLVM?

    P.P.S.: В следующих статьях очень хотел бы послушать про особенности работы GC в MP окружении.
    • 0
      Какая у вас интересная VM. Пытать можно, но я, конечно, не гарантирую, что смогу точно ответить на все вопросы и за разумное время :) Пишите на почту: me [на] gvsmirnov.ru.

      Насчёт кишок LLVM ничего сказать не могу. Неужели вам не интересно заглянуть самостоятельно? :)
      • 0
        Спасибо за ответ!

        Насчёт кишок LLVM ничего сказать не могу. Неужели вам не интересно заглянуть самостоятельно? :)
        К сожалению, LLVM не идеален, так что заглядывать приходится и довольно часто. Просто думал что вы сможете ответить быстрее, если вдруг знакомы с его нутром.

        Какая у вас интересная VM.
        Да ну, пока ничего особенного :) Вот когда по-настоящему заработает суперкомпиляция, тогда будет интересно, да.
    • +1
      Тут есть один нюанс, которые люди часто путают. А именно memory barriers & gc barriers. Еще больше путаницы добавляется когда gc-шные барьеры начинают называть по их специализации, т.е. read-barrier & write-barrier. :)
      Так вот — это совершенно разные вещи. Совпадение слова барьер там и там совершенно случайно.
      Если у вас не concurrent gc — gc-шные барьеры вам совсем не нужны.
      • 0
        Спасибо за комментарий! Действительно про отличия нигде не пишут. Сейчас у нас банальный блокирующий Бейкер и никакой многопоточности, так что все верно. Я спрашивал на будущее.
        • +1
          Если у вас будет частично concurrent gc — то скорее всего вы только mark фазу будете делать конкаррентно с мутаторами, а собственно чистку в стоп-фазу. Тогда опять же мемори барьеры не нужны. ;) Зато полностью и с размаху наступите на false sharing. :) А вот когда вы начнете делать полностью concurrent gc — я уже вам никаких советов давать не смогу за ненадобностью ;)
  • +1
    Когда речь заходит о когерентности кешей, всегда вспоминаю хорошую статью Paul McKenney Memory Barriers
    • 0
      Да, статья отличная. На неё даже уже есть ссылка в этом топике, но разместить её ещё раз не помешает :)

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.