Вы можете удивиться: зачем же разработчику ПО думать о механизме кэширования в CPU? Отвечу. С одной стороны, многие понятия из концепции когерентности кэша непосредственно применимы в распределённых системах и на уровнях изоляции СУБД. Например, представление реализации когерентности в аппаратных кэшах помогает лучше понять разницу в моделях согласованности (консистентности) — отличие строгой согласованности (strong consistency) от согласованности в конечном счёте (eventual consistency). У вас могут появиться новые идеи, как лучше обеспечить согласованность в распределённых системах, используя исследования и принципы из аппаратного обеспечения.
С другой стороны, неправильные представления о кэшах часто приводят к ложным утверждениям, особенно когда речь идёт о параллелизме и состоянии гонки. Например, часто говорят о трудности параллельного программирования, потому что «у разных ядер в кэшах могут быть разные/устаревшие значения». Или что квалификатор volatile в языках вроде Java нужен, чтобы «предотвратить локальное кэширование общих данных» и принудительно «читать/записывать только в основную память».
Такие заблуждения в основном безвредны (и могут быть даже полезны), но также ведут к плохим решениям при проектировании. Например, разработчики могут подумать, что они избавлены от вышеупомянутых ошибок параллелизма при работе с одноядерными системами. В действительности даже одноядерные системы подвержены риску ошибок параллелизма, если не используются соответствующие конструкции параллелизма.
Или ещё пример. Если переменные volatile действительно каждый раз пишутся/считываются из основной памяти, то они будут чудовищно медленными — ссылки в основной памяти в 200 раз медленнее, чем в кэше L1. На самом деле volatile-reads (в Java) часто настолько же производительны, как из кэша L1, и это развенчивает миф, будто volatile принуждает читает/записывать только в основную память. Если вы избегали volatile из-за проблем с производительностью, возможно, вы стали жертвой вышеуказанных заблуждений.
Важность согласованности
Но если у разных ядер собственный кэш, хранящий копии одних и тех же данных, не приведёт ли это к несоответствию записей? Ответ: аппаратные кэши в современных процессорах x86, как у Intel, всегда синхронизируются. Эти кэши не просто тупые блоки памяти, как многие разработчики, похоже, думают. Наоборот, очень сложные протоколы и встроенная логика взаимодействия между кэшами обеспечивает согласованность во всех потоках. И всё это происходит на аппаратном уровне, то есть нам, разработчикам программного обеспечения/компиляторов/систем, не нужно об этом думать.
Кратко объясню, что имеется в виду под «синхронизированными» кэшами. Здесь много нюансов, но в максимальном упрощении: если два разных потока в любом месте системы читают с одного и того же адреса памяти, то они никогда не должны одновременно считывать разные значения.
В качестве простого примера, как непротиворечивые кэши могут нарушить вышеупомянутое правило, просто обратитесь к первому разделу этого учебника. Ни один современный процессор x86 не ведёт себя так, как описано в учебнике, но глючный процессор, безусловно, может. Наша статья посвящена одной простой цели: предотвращению таких несоответствий.
Наиболее распространённый протокол для обеспечения согласованности между кэшами известен как протокол MESI. У каждого процессора своя реализация MESI, и у разных вариантов есть свои преимущества, компромиссы и возможности для уникальных багов. Однако у всех них есть общий принцип: каждая строка данных в кэше помечена одним из следующих состояний:
- Модифицированное состояние (M).
- Эти данные модифицированы и отличаются от основной памяти.
- Эти данные являются источником истины, а все остальные источники устарели.
- Эксклюзивное (E).
- Эти данные не модифицированы и синхронизированы с основной памятью.
- Ни в одном другом кэше того же уровня нет этих данных.
- Общее (S).
- Эти данные не модифицированы и синхронизированы.
- В других кэшах того же уровня тоже (возможно) есть те же данные.
- Недействительное (I).
- Эти данные устарели и не должны использоваться.
Если мы применяем и обновляем вышеуказанные состояния, то можно добиться согласованности кэша. Рассмотрим несколько примеров для процессора с четырьмя ядрами, у каждого из которых собственный кэш L1, а также глобальный кэш L2 на кристалле.
Запись в память
Предположим, что поток на core-1 хочет записать в память по адресу 0xabcd. Ниже приведены некоторые возможные последовательности событий.
Попадание в кэш
- В L1-1 есть данные в состоянии E или M.
- L1-1 производит запись. Всё готово.
- Ни в одном другом кэше нет данных, так что немедленная запись будет безопасной.
- Состояние строки кэша изменяется на M, поскольку она теперь изменена.
Промах локального кэша, попадание одноуровневого кэша
- В L1-1 есть данные в состоянии S.
- Это значит, что в другом одноуровневом кэше могут быть эти данные.
- Та же последовательность применяется, если в L1-1 вообще нет этих данных.
- L1-1 отправляет Request-For-Ownership в кэш L2.
- L2 смотрит по своему каталогу и видит, что в L1-2 сейчас есть эти данные в состоянии S.
- L2 отправляет snoop-invalidate в L1-2.
- L1-2 помечает данные как недействительные (I).
- L1-2 отправляет запрос Ack в L2.
- L2 отправляет Ack вместе с последними данными в L1-1.
- L2 проверяет, что в L1-1 эти данные хранятся в состоянии E.
- В L1-1 теперь последние данные, а также разрешение войти в состояние E.
- L1-1 осуществляет запись и изменяет состояние этих данных на M.
Чтение памяти
Теперь предположим, что поток на core-2 хочет считать с адреса 0xabcd. Ниже приведены некоторые возможные последовательности событий.
Попадание кэша
- L1-2 имеет данные в состоянии S, E или M.
- L1-2 считывает данные и возвращает в поток. Готово.
Промах локального кэша, промах кэша верхнего уровня
- L1-2 имеет данные в состоянии I (недействительное), то есть не может их использовать.
- L1-2 отправляет запрос Request-for-Share в кэш L2.
- В L2 тоже нет данных. Он считывает данные из памяти.
- L2 возвращает данные из памяти.
- L2 отправляет данные в L1-2 с разрешением войти в состояние S.
- L2 проверяет, что в L1-2 эти данные хранятся в состоянии S.
- L1-2 получает данные, сохраняет их в кэше и отправляет в поток.
Промах локального кэша, попадание кэша верхнего уровня
- В L1-2 есть данные в состоянии I.
- L1-2 отправляет запрос Request-for-S в кэш L2.
- L2 видит, что в L1-1 данные в состоянии S.
- L2 отправляет Ack в L1-2, вместе с данными и разрешением войти в состояние S.
- L1-2 получает данные, сохраняет их в кэше и отправляет в поток.
Промах локального кэша, попадание одноуровневого кэша
- В L1-2 есть данные в состоянии I.
- L1-2 отправляет запрос Request-for-S в кэш L2.
- L2 видит, что в L1-1 данные в состоянии E (или M).
- L2 отправляет snoop-share в L1-1
- L1-1 понижает состояние до S.
- L1-1 отправляет Ack в L2 вместе с модифицированными данными, если это применимо.
- L2 отправляет Ack в L1-2 вместе с данными и разрешением войти в состояние S.
- L1-2 получает данные, сохраняет их в кэше и отправляет в поток.
Вариации
Выше приведены лишь некоторые из возможных сценариев. На самом деле существует много вариаций и нет двух одинаковых реализаций протокола. Например, в некоторых конструкциях используется состояние O/F. В некоторых есть кэши обратной записи, а другие используют сквозную запись. Некоторые используют snoop-трансляции, а другие — snoop-фильтр. В некоторых инклюзивные кэши, а в других — эксклюзивные. Вариации бесконечны, а мы даже не затронули буферы хранения (store-buffers)!
Кроме того, в приведённом примере рассматривается простой процессор всего с двумя уровнями кэширования. Но обратите внимание, что этот же протокол можно применить рекурсивно. Легко добавляется кэш L3, который, в свою очередь, координирует несколько кэшей L2, используя тот же протокол, что приведён выше. У вас может быть многопроцессорная система с «домашними агентами», которые координируют работу нескольких кэшей L3 на совершенно разных чипах.
В каждом сценарии каждому кэшу нужно взаимодействовать только с кэшем верхнего уровня (для получения данных/разрешений) и его потомками (для предоставления/отмены данных/разрешений). Всё это происходит невидимо для программного потока. С точки зрения софта подсистема памяти выглядит как единый, консистентный монолит… с очень переменными задержками.
Почему синхронизация по-прежнему важна
Мы обсудили удивительную мощность и согласованность системы памяти компьютера. Остался один вопрос: если кэши настолько последовательны, то зачем вообще нужны volatile в языках вроде Java?
Это очень сложный вопрос, на который лучше ответить в другом месте. Позвольте только немного намекнуть. Данные в регистрах CPU не синхронизируются с данными в кэше/памяти. Программный компилятор выполняет всевозможные оптимизации, когда дело доходит до загрузки данных в регистры, записи их обратно в кэш и даже переупорядочивания инструкций. Всё это делается при условии, что код будет выполняться в одном потоке. Поэтому любые данные, подверженные риску состояния гонки, следует защищать вручную с помощью параллельных алгоритмов и языковых конструкций вроде atomic и volatile.
В случае квалификатора volatile в Java решение отчасти состоит в том, чтобы заставить все операции чтения/записи идти в обход локальных регистров, а вместо этого немедленно обращаться к кэшу для чтения/записи. Как только данные считаны/записаны в кэш L1, вступает в силу протокол аппаратного согласования. Он обеспечивает гарантированную согласованность во всех глобальных потоках. Таким образом, если несколько потоков читают/записывают в одну переменную, все они синхронизированы друг с другом. Вот как достигается координация между потоками всего за 1 наносекунду.
Комментарии (51)
topheracher
02.05.2018 14:29Но тут больше проблема подготовки данных и мастерства бенчмаркать эти вещи. А не «вы всё врёти». Тоесть вероятность того, что на собеседовании с вас спросят тайминги доступа к кешу и длину кеш-линии — нулевая. Только если вы не идете в какие-нибудь жуткие data oriented вещи, типа программирования графики/физики.
rzerda
02.05.2018 18:26Так они у каждого семейства разные, какой толк их спрашивать. А вот представлять, что процессор это не волшебная коробка, а вполне себе детерминированное устройство, очень полезно.
ToSHiC
02.05.2018 22:05А вот представлять, что процессор это не волшебная коробка, а вполне себе детерминированное устройство, очень полезно.
Правда Spectre/Meltdown показали, что процессоры — не слишком то уж детерменированные устройства :)khim
02.05.2018 22:29+1Правда Spectre/Meltdown показали, что процессоры — не слишком то уж детерменированные устройства :)
Как раз Spectre/Meltdown работают именно из-за детерменированности кешей. Если бы там времена доступа случайными были бы — ничего бы не работало…ToSHiC
02.05.2018 23:55+1Нене, с точки зрения обычного, нормального программиста, никакого meltdown в принципе существовать не может. А вот с точки зрения Интела да, кэш отработал отлично.
dimkrayan
02.05.2018 14:31+7Мне кажется, автор зря здесь упомянул Java. В данном контексте его утверждения просто опасны.
Да, на интеловых процессорах есть протокол когерентности кешей. Но java-приложение может работать на других процессорах. Этот протокол может быть выключен. В конце концов, есть распределенные java-машины.
Плюс, не забываем, что компилятор банально может такой код:
Integer x = 1; while(x > 0) { тут не изменяем x };
оптимизировать до
while(true) {...}
(справедливости ради, самые известные компиляторы, насколько я знаю, так не делают)
Ну и volatile — это болше чем просто запись\чтение мимо кешей. Это happens before.
В остальном — очень интересно.delfigamer
03.05.2018 08:00(справедливости ради, самые известные компиляторы, насколько я знаю, так не делают)
Если компилятор докажет, что x нигде не меняется — очень даже делает.dimkrayan
03.05.2018 08:581. Тут пример плохой (я ведь не статью писал). Здесь не очевидно, что в x может прилететь из другого треда. И вот тут и проблема: согласно java memory model, этого может никогда и не произойти. И компилятор имеет право так считать. А может и произойти.
2. Там же С++delfigamer
04.05.2018 08:48Здесь не очевидно, что в x может прилететь из другого треда. И вот тут и проблема: согласно java memory model, этого может никогда и не произойти. И компилятор имеет право так считать. А может и произойти.
Это называется undefined behavior, это когда чего-то делать нельзя, но программист всё равно это делает. Компилятор имеет право делать вид, будто UB никогда не происходит, что очень сильно развязывает ему руки в плане оптимизаций. Как следствие, когда программист пытается делать то, чего делать нельзя, в общем случае это заканчивается плохо.
2. Там же С++
А какая разница, оптимизация одна и та же — обычный constant propagation.dimkrayan
04.05.2018 09:51Понятно, что это UB. Речь шла о том, что на практике (не)делают самые популярные компиляторы java — оракловый и gnu.
Но как уже отметил товарищ из соседней ветки, что не делают компиляторы, делает jit.
0xd34df00d
05.05.2018 00:15Я не понимаю, почему для
f_atomicкомпилятор не имеет права сначала доказать, чтоterminateнигде не видно, и потом сделать тот же constant propagation.
А, я зачем-то смотрел только на вывод gcc. clang ровно это и делает. Теперь мне интересно, на самом ли деле он имеет на это право.
accipiter
03.05.2018 08:00+1Не знаю как в Java, но в C/C++ volatile просто говорит компилятору не пытаться оптимизировать операции с этой переменной. Т.е. каждый раз считывать значение переменной из памяти при обращении к ней. К кешам это никакого отношения не имеет.
dimkrayan
03.05.2018 09:03Так в статье же есть ссылка про сравнение
componenthouse.com/2016/12/28/comparing-the-volatile-keyword-in-java-c-and-cpp
mayorovp
03.05.2018 09:19Лично мне это кажется недоработкой Си/С++: отдельные языковая модель исполнения и «железная» модель памяти.
В Java и C# все намного проще: есть только одна модель исполнения и памяти, которой JVM/CLR следует; и видя ключевое слово volatile JIT не только отключает оптимизации операций над этим полем — но и сам расставляет барьеры чтобы процессор тоже ничего не напортачил. В частности, volatile read всегда дает барьер чтения, а volatile write — барьер записи.dimkrayan
03.05.2018 09:57+2Ну, так С\С++ гораздо ближе к железу. Это их «экологическая ниша». Они созданы для того, чтобы решать проблемы, которые в более высокоабстрактных (не знаю нужного термина) отсутствуют.
khim
03.05.2018 14:06На самом деле всё проще: C был создан для того, чтобы писать операционную систему (одну).
Когда вы пишите операционную систему, то вам нужно как-то общаться с железом, у которого регистры размапированы в память (собственно никаких других у PDP и не было).
То, что он оказался удачным и его приспособили в кучу разных других мест — совсем другая история. Хотя тот факт, что низкоуровный механизм, который полвека назад был очень даже к месту там, где его разработали, применили в последующем для кучу разных других задач… ну, плохо, конечно… а чего делать? Других механизмов долгое время не было.dimkrayan
03.05.2018 14:09Вообще-то, у С ноги растут из В и совсем другой ОС, Multics.
khim
03.05.2018 14:19Какая разница откуда у него «растут ноги»? Чтобы работать с «железом» на PDP вам нужно точно управлять тем, что и где вы читаете и пишите. Позже, во всемена DOS'а — это тоже было очень важное умение (всякие VGA и прочее просто-таки по спецификации так устроены — там можно записывать в одну и ту же ячейку памяти дважды и получать разные результаты).
А вот уже как раз когда появились Linux/Windows, кеши и многопоточность — требования изменились… а применяемый инструмент — остался.LynXzp
03.05.2018 21:23В embedded все так же актуальна возможность дважды записать по одному адресу одни и те же данные.
khim
05.05.2018 14:10В embedded другая проблема: для них зачастую очень полезно уметь писать код, использующий особенности железа. А не код, заточенный под PDP и при этом переносимый на миллион платформ.
Для этого C подходит плохо, но его используют за неимением лучшего.LynXzp
05.05.2018 15:59+1И чем простите мало подходит? Мне известно только то что нет операций работы с битами, приходиться возится с масками. На уровне железа это исправляет компилятор, а на уровне читаемости это исправляется макросами или инлайн функциями.
В embedded, как раз, как нигде важна переносимость на другие платформы. И совсем не понятно чем мешает «заточенность под PDP»khim
05.05.2018 18:50И чем простите мало подходит?
Там что до банальных вещей, которые процессор вычисляет «на раз» невозможно никак добраться. Ни до флага «overflow», ни до «carry», никуда.
Да, можно пытаться делать странные вещи и надеяться на то, что оптимизатор поймёт и сделает «как надо», как-нибудь так:
Вот только…#include <inttypes.h> struct pair { uint64_t low; uint64_t hi; }; pair add(pair& a, pair& b) { pair s; s.low = a.low + b.low; s.hi = a.hi + b.hi + (s.low < a.low); //carry return s; }
GCC5 — нормально
GCC6 — ай-ай-ай
GCC7 — всё ещё ай-ай-ай
GCC8 — пофиксили
И это — простейший пример! А если чего посложнее навернуть?
В embedded, как раз, как нигде важна переносимость на другие платформы.
Не знаю, не знаю, пока в основном видел жалобы на то, что попытки использовать низкоуровневое знание о том, как процессор устроен приводят к тому, что компилятор начинает «бузить».
И совсем не понятно чем мешает «заточенность под PDP»
К тому, что заточенность под «железо PDP» в видеvolatile,++/--и прочего — поддерживаются на всех платформах, а вот вещи, которые современные DSP умеют (скажем переменные с фиксированной точкой) — вынесены в зависящие от конмпилятора расширения (если вообще есть поддержка).LynXzp
05.05.2018 19:40Понятно, но тут или расширения для компилятора или разные языки для разных процессоров. Хотя в принципе могли и ввести в стандарт опциональные платформозависимые вещи, как ввели COMPLEX.
Но на PDP-11 Вы зациклились, volatile, INC, DEC нужны почти на всем (за DSP не ручаюсь).
mayorovp
03.05.2018 09:41(справедливости ради, самые известные компиляторы, насколько я знаю, так не делают)
Компиляторы — да, не делают. А вот JIT вполне может такое устроить...
dimkrayan
03.05.2018 10:55А откуда информация, что это именно jit?
mayorovp
03.05.2018 10:58Источник не приведу, но вроде как это общеизвестная информация. Во всех языках семейств JVM и .NET компиляторы генерируют байт-код без хитрых оптимизаций, а оптимизацией занимается уже JIT.
Это нужно хотя бы потому что только JIT знает целевую платформу в которой будет исполняться код, а также информацию которая доступна только в рантайме; то есть у него попросту больше возможностей оптимизации.dimkrayan
03.05.2018 11:06Да, спасибо. Я выключил jit — и все отработало.
Надо будет почитать на эту тему. Как оказалось, здесь я «плаваю».
lany
03.05.2018 04:25если два разных потока в любом месте системы читают с одного и того же адреса памяти, то они никогда не должны одновременно считывать разные значения.
Что-то после слова "одновременно" возникли сомнения в квалификации автора. Во многопоточной среде понятие одновременности довольно расплывчато и вообще не нужно.
Miron11
03.05.2018 06:28-1Одна из немногих статей, которые заставили меня улыбаться во время чтения; чистое удовольствие!
Автору спасибо.
RetroGuy
Что-то развенчаных мифов вопреки многообещающему заголовку негусто.
khim
Уж не говоря о том, что самая популярная вычислительная платформа устроена, мягко говоря, не совсем так, как описано в статье.
lorc
Ну почему же. На АРМах есть Cache Coherent Interconnect для обеспечения когерентности кешей между кластерами и вариация MESI в пределах кластера.
khim
В том-то и дело, что «вариации». На табличку смотрели? Хуже ARM'а — только Alpha…
0xd34df00d
Я бы не называл это «хуже» по ряду причин, начиная от очевидно более высокой достижимой производительности (чем компилятору/шедулеру больше позволено, тем лучше) и заканчивая, если хотите, дисциплинированием.
creker
Если говорить о современных армах в мобильниках, то там когерентность кэшей имеется. Может в каких-то древних реализациях и не было, не знаю. Чего в армах по-другому, так это memory ordering, но это кешей и не касается.
khim
А он сам по себе не возьмётся из ниоткуда, если у вас переменная как volatile не помечена.
creker
Каким образом перестановка операций чтения и записи касается когерентности кэшей? Барьеры ставят, чтобы соблюдать последовательность load/store операций как написал программист, а не как задумал процессор. Даже в amd64 с его гарантиями всего и вся есть барьеры, т.к. там допускается один вариант перестановки.
khim
В amd64 нормальные инструкции сюрпризов не преподносят, нужно использовать MOVNTxxx инструкции, чтобы «выстрелить себе в ногу». У ARMа же один список хинтов (все эти «inner shareable domain», «outer shareable domain», «point of unification» и прочее) как бы намекает на то, что не всё так так просто.
creker
Преподносят, когда даже обычные mov для load/store операций меняются местами bartoszmilewski.com/2008/11/05/who-ordered-memory-fences-on-an-x86 На арме просто еще хуже все.
mayorovp
Потому что когерентность кешей и соблюдение последовательности load/store операций — это эквивалентные проблемы.
0xd34df00d
Только при некоторых дополнительных предположениях. Вы можете убрать кеш, но реордеринг/elision это автоматически не уберёт.
mayorovp
Именно об этом я и говорю. Система в которой нет кеша но есть реордеринг имеет все те же самые проблемы что и система с некогерентными кешами но без реордеринга.
khim
Система с реордерингом, но без кешей — это такой «сферический конь в вакууме». В природе не встречается, насколько я знаю.
creker
Но ничего не мешает убрать когерентность кэшей и оставить реордеринг. Это совершенно не связанные между собой вещи. То, что они там программисту примерно теже самые проблемы создают, никакого значения особо не имеет. Статья о кэшах, поэтому и реордеринг в ней упоминать не по теме. Была бы статья о проблемах многопоточных программ с общим изменяемым состоянием, то можно было бы упоминать и то, и другое.
khim