Главная
Блог разработчиков phpBB
 
+ 17 предустановленных модов
+ SEO-оптимизация форума
+ авторизация через соц. сети
+ защита от спама

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

Anna | 3.06.2014 | нет комментариев
Познание об управлении потоками, которое мы получили в прошлом топике, безусловно, огромно, но вопросов остаётся всё равно много. Скажем: «Как работает 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. А они изредка могут выполняться дюже длинно, если про>

Многопоточность это легко и ясно, не правда ли? Задача находится на шагах (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 (как, однако и для того, кочное представление нашего кода инструкцию 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. Тогда есть четыре упорядоченные комбинации из 2-х операций: 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;
}

У нас есть два потока: один меняет состояние, а 2-й — читает состояние и сберегает итог, тот, что увидел. Фреймворк за нас агрегирует итоги, и проверяет их по некоторым правилам. Для нас увлекательны два итога, которые может увидеть 2-й поток: [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 думать во время старта, что она исполняется на одном процессоре, то проживёт она не длинно.

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

Источник: programmingmaster.ru

Оставить комментарий
Форум phpBB, русская поддержка форума phpBB
Рейтинг@Mail.ru 2008 - 2017 © BB3x.ru - русская поддержка форума phpBB