Кеш решил проблему доступа к данным для одного ядра: вместо ~100 нс на каждое обращение к RAM — ~1 нс из L1. Но в многоядерном процессоре у каждого ядра свой L1 и L2. Что происходит, когда два ядра работают с одним и тем же адресом?
Ядро 0 записывает counter = 1 в свой L1. Ядро 1 читает ту же переменную из своего L1, где по-прежнему counter = 0. Два ядра видят разные значения одного адреса — кеши рассогласованы. Без аппаратного механизма согласования многоядерность принципиально сломана: результат программы зависит от того, какое ядро когда прочитало свою копию.
Чтобы многоядерный процессор оставался предсказуемым, в железо встроен аппаратный протокол, который гарантирует: если одно ядро записало значение по адресу X, все остальные ядра при чтении того же адреса увидят это новое значение. Это и есть когерентность кешей (cache coherence, буквально «связность», «согласованность»). Каждое ядро видит актуальные данные, даже если физически они хранятся в L1 другого ядра.
Чтобы обеспечить эту гарантию, каждая кеш-линия должна нести состояние: кто ей владеет, кто может читать, была ли она изменена. Протокол MESI (Modified — изменённая, Exclusive — исключительная, Shared — разделяемая, Invalid — недействительная) кодирует это четырьмя состояниями.
Протокол MESI: четыре состояния кеш-линии
Каждая кеш-линия (64 байта данных) в L1/L2 каждого ядра помечена одним из четырёх состояний:
Modified (M, «изменённая») — линия изменена только в этом кеше. Копия в RAM устарела. Ни у одного другого ядра этой линии нет. Ядро — единоличный владелец и обязано записать данные в RAM (или передать другому ядру) при вытеснении.
Exclusive (E, «исключительная») — линия присутствует только в этом кеше и совпадает с RAM. Ни одно другое ядро её не кеширует. Отличие от Modified: данные чистые, при вытеснении записывать не нужно. Ключевое свойство: переход E → M происходит мгновенно — ядро уже единственный владелец, оповещать другие ядра не нужно.
Shared (S, «разделяемая») — линия может присутствовать в кешах нескольких ядер. Все копии совпадают с RAM. Чтение — бесплатно. Запись требует инвалидации всех остальных копий.
Invalid (I, «недействительная») — линия невалидна, данных в этом кеше нет. Любое обращение к этому адресу потребует загрузки из RAM или из кеша другого ядра.
Состояния кеш-линии в протоколе MESI ┌──────────┐ ┌──────────┐ ┌──────────┐ ┌──────────┐ │ Modified │ │Exclusive │ │ Shared │ │ Invalid │ │ │ │ │ │ │ │ │ │ только │ │ только │ │ несколько│ │ данных │ │ здесь, │ │ здесь, │ │ ядер, │ │ нет │ │ грязная │ │ чистая │ │ чистая │ │ │ └──────────┘ └──────────┘ └──────────┘ └──────────┘ запись: да запись: да запись: нет запись: нет чтение: да чтение: да чтение: да чтение: нет RAM актуальна: RAM актуальна: RAM актуальна: нет да да
MESI на практике: два ядра и один счётчик
Проследим сценарий с переменной counter шаг за шагом. Переменная находится по адресу 0x7f00, который попадает в кеш-линию, охватывающую адреса 0x7f00–0x7f3f (64 байта, выровненные по границе 64).
Шаг 1: Core 0 читает counter
Core 0 выполняет load [0x7f00]. Адреса нет ни в одном кеше. Core 0 посылает когерентный запрос на интерконнект (interconnect — общий канал связи между ядрами). В протоколе MESI такой запрос называется bus read (чтение через шину) — название сохранилось с эпохи, когда ядра были связаны общей шиной, хотя в современных процессорах топология другая. Ни одно ядро не кеширует эту линию, поэтому данные приходят из RAM. Кеш-линия загружается в L1 ядра 0 в состоянии Exclusive — только Core 0 имеет копию, и она совпадает с RAM.
Core 0 L1: [0x7f00-0x7f3f] состояние = E counter = 0Core 1 L1: --- состояние = IRAM: [0x7f00-0x7f3f] counter = 0
Чтение из Exclusive обходится в ~1 нс — обычный L1 hit.
Шаг 2: Core 1 читает counter
Core 1 выполняет load [0x7f00]. Адреса в его кеше нет. Core 1 посылает bus read. Core 0 видит этот запрос на интерконнекте (механизм snooping, буквально «подслушивание»: контроллер кеша каждого ядра отслеживает адреса всех транзакций на интерконнекте и сверяет их со своими кеш-линиями — если адрес совпадает, ядро реагирует по правилам MESI). Core 0 обнаруживает, что у него есть эта линия в состоянии E. Оба ядра переводят свои копии в Shared.
Core 0 L1: [0x7f00-0x7f3f] состояние = S counter = 0Core 1 L1: [0x7f00-0x7f3f] состояние = S counter = 0RAM: [0x7f00-0x7f3f] counter = 0
Теперь оба ядра могут читать counter за 1 нс. Данные идентичны. Пока линия остаётся в Shared, повторные чтения с обеих сторон не генерируют трафик на интерконнекте — каждое ядро работает с собственной копией в L1, и протокол не вмешивается.
Core 0 выполняет store [0x7f00], 1. Линия в состоянии Shared — значит, у другого ядра есть копия. Прежде чем записать, Core 0 посылает на интерконнект invalidate — сообщение «я буду писать по этому адресу, все остальные — сбросьте свои копии».
Core 1 видит invalidate, переводит свою копию в Invalid. Core 0 получает подтверждение инвалидации (invalidate acknowledgement), переводит свою линию в Modified и выполняет запись.
Core 0 L1: [0x7f00-0x7f3f] состояние = M counter = 1Core 1 L1: [0x7f00-0x7f3f] состояние = I (данные невалидны)RAM: [0x7f00-0x7f3f] counter = 0 (устарела!)
Обратите внимание: RAM не обновлена. В состоянии Modified свежие данные существуют только в L1 ядра 0 — RAM содержит устаревшую копию, пока ядро не отдаст линию (write-back).
Шаг 4: Core 1 читает counter
Cache-to-cache transfer
Cache-to-cache transfer — это передача актуальной кеш-линии напрямую из кеша одного ядра в кеш другого, без чтения из RAM. Она нужна, когда другое ядро уже держит более свежую копию линии, чем память. В нашем сценарии это происходит именно здесь.
Core 1 выполняет load [0x7f00]. Его копия — Invalid. Core 1 посылает bus read. Core 0 видит запрос через snooping и обнаруживает, что линия в состоянии Modified — значит, в RAM устаревшие данные. Core 0 отдаёт актуальную копию Core 1 напрямую (cache-to-cache transfer), минуя RAM. В чистом MESI при переходе M → S линия одновременно записывается в RAM — иначе нарушился бы инвариант состояния Shared «все копии совпадают с RAM». Обе копии переходят в Shared.
Core 0 L1: [0x7f00-0x7f3f] состояние = S counter = 1Core 1 L1: [0x7f00-0x7f3f] состояние = S counter = 1RAM: [0x7f00-0x7f3f] counter = 1 (обновлена при M->S)
Core 1 получил актуальное значение. Когерентность сработала: запись ядра 0 стала видна ядру 1.
sequenceDiagram
participant C0 as Core 0 / L1
participant BUS as Интерконнект
participant C1 as Core 1 / L1
participant RAM as RAM
C0->>BUS: bus read counter
BUS->>RAM: запрос линии
RAM-->>C0: данные
Note over C0: состояние: Exclusive
C1->>BUS: bus read counter
BUS-->>C0: snoop: bus read
C0-->>C1: копия линии
Note over C0,C1: обе копии: Shared
C0->>BUS: invalidate counter
BUS-->>C1: invalidate
C1-->>C0: подтверждение инвалидации
Note over C0: Modified, counter = 1
C1->>BUS: bus read counter
BUS-->>C0: snoop: bus read
C0-->>C1: cache-to-cache transfer
C0->>RAM: write-back counter = 1
Note over C0,C1: обе копии: Shared, counter = 1
Важный момент в этой последовательности: интерконнект нужен не для каждого чтения, а только в точках смены владения или когда другой кеш уже держит более свежую копию, чем RAM. Пока линия локальна и не оспаривается, чтения и записи обходятся в ~1 нс — обычный L1 hit без дополнительной задержки на когерентный протокол.
Обязательный write-back при каждом M → S — цена чистого MESI. Реальные процессоры (AMD, ARM) часто используют расширение MOESI: добавляется состояние Owned, позволяющее держать «грязную» линию разделяемой между ядрами без немедленного обновления RAM. Для модели протокола достаточно четырёх базовых состояний — дальнейшие оптимизации не меняют сути когерентности.
Полная диаграмма переходов MESI
Сценарий показал четыре основных перехода. Полная диаграмма собирает все восемь.
stateDiagram-v2
I --> E: load, линия только у нас (из RAM)
I --> S: load, линия есть у другого ядра
E --> M: store (бесплатно — уже единственный владелец)
E --> S: bus read от другого ядра
S --> I: другое ядро хочет писать (invalidate)
S --> M: store + invalidate всех остальных
M --> S: другое ядро читает (cache-to-cache transfer + write-back)
M --> I: другое ядро хочет писать (transfer + invalidate)
I: Invalid
S: Shared
E: Exclusive
M: Modified
Два ядра физически не могут одновременно держать одну линию в Modified — протокол это запрещает. Когерентность определяет порядок для одного адреса; порядок между записями в разные адреса — задача модели памяти.
Когерентность гарантирует видимость каждой отдельной записи. Но операция counter++ — это не одна запись, а три шага: load (прочитать текущее значение), add (прибавить 1), store (записать результат). Атомарная операция (atomic operation) — операция, которую процессор выполняет целиком, не позволяя другому ядру вмешаться между её шагами. Когерентность не даёт атомарности: она гарантирует, что каждый отдельный store станет виден, но не запрещает другому ядру вклиниться между load и store.
Когерентность здесь работает корректно: каждый store виден другим ядрам. Проблема в том, что последовательность load-add-store не атомарна — другое ядро может вклиниться между load и store. Эта ситуация называется гонкой (race condition) — результат зависит от того, в каком порядке ядра чередуют свои шаги.
Процессор предоставляет для этого атомарные инструкции: они выполняют read-modify-write как единое целое, не позволяя другим ядрам вмешаться. Поверх аппаратных атомарных инструкций строятся программные примитивы синхронизации, обеспечивающие неделимость произвольных блоков кода.
Цена когерентности в наносекундах
Порядок величин задержек на типичном серверном процессоре (~2020):
Операция Задержка──────────────────────────────────────────────────────L1 hit (локальная линия: E, M или S) ~1 нсL2 hit ~4 нсL3 hit (локально) ~12 нсЧтение линии Modified у другого ядра ~20-70 нс (cache-to-cache transfer)Запись в линию Shared ~20-50 нс (invalidate + подтверждение инвалидации)Промах по всем кешам (из RAM) ~80-100 нс
Запись в линию Shared из таблицы выше — это тот же обмен, что в шаге 3: ядро посылает invalidate, ждёт подтверждения инвалидации от всех кешей, где есть копия, и только потом получает линию в Modified.
Эти десятки наносекунд — цена передачи владения кеш-линией между ядрами. Она возникает всякий раз, когда линия перестаёт быть локальной: запись хочет изменить Shared-линию, атомарный read-modify-write требует эксклюзивного владения, или два ядра по очереди трогают одну и ту же линию. Подробный пример с атомарным инкрементом общего счётчика — в атомарных инструкциях; здесь важно общее правило: как только операция требует invalidate и подтверждения инвалидации, локальный доступ уровня L1 превращается в когерентную транзакцию на десятки наносекунд.
Store buffer: запись без ожидания
Таблица выше показывает полную цену когерентной транзакции. Но обычная запись не всегда платит её прямо на критическом пути. Для неатомарных stores процессор обходит это ожидание через store buffer — тот же самый буфер, которым иерархия памяти скрывает задержку L1, здесь выполняет аналогичную работу, но прячет уже не задержку кеша, а задержку когерентного протокола.
Ядро помещает запись в store buffer (порядка 56 записей на Intel Skylake) и продолжает выполнение. Когерентная транзакция — invalidate, ожидание подтверждения инвалидации, перевод линии в Modified — идёт в фоне. Когда она завершится, данные из буфера переместятся в кеш-линию. На практике это значит: обычный код, пишущий в общие данные, не останавливается на каждой записи, даже если другое ядро эту линию кеширует.
Но для атомарных инструкцийstore buffer не помогает — процессор обязан дождаться завершения когерентной транзакции, чтобы гарантировать неделимость. Поэтому атомарные операции над общей ячейкой, за которую одновременно борются несколько ядер, особенно хорошо проявляют цену когерентности; подробно этот случай разобран в атомарных инструкциях.
У этой оптимизации есть побочный эффект: на некоторых архитектурах (ARM, RISC-V) записи из store buffer могут стать видны другим ядрам не в программном порядке. Когда и почему это происходит — определяет модель памяти.
False sharing: ловушка скрытого разделения
Пинг-понг легко заметить на общем счётчике: оба ядра действительно записывают в один адрес. Но существует ситуация, когда два потока работают с разными переменными, и производительность всё равно деградирует в десятки раз. Это false sharing (ложное разделение) — одна из самых коварных проблем многоядерного программирования.
Два потока, каждый инкрементирует свой собственный счётчик. Логически — никакого разделения данных:
Каждый поток пишет в свою переменную. Никакой гонки данных. Можно ожидать, что два потока отработают за то же время, что один — каждое ядро инкрементирует свою переменную в своём L1.
На практике два потока с этой структурой работают в десятки раз медленнее одного потока. При полном отсутствии логического разделения данных.
Причина: кеш работает линиями, а не байтами
thread0_counter занимает байты 0-7 структуры, thread1_counter — байты 8-15. Размер структуры — 16 байт, а кеш-линия — 64. Допустим, c начинается по адресу 0x7f80 — началу кеш-линии. Тогда оба поля попадают в одну линию:
Протокол MESI оперирует целыми кеш-линиями. Когда Core 0 записывает в thread0_counter, он инвалидирует всю линию в кеше Core 1. Core 1 при следующей записи в thread1_counter обнаруживает, что линия в состоянии Invalid, и вынужден запрашивать актуальную копию у Core 0. Получает, переводит в Modified, записывает — и инвалидирует линию у Core 0. Пинг-понг, идентичный тому, что происходит с настоящим общим счётчиком.
flowchart LR
A["Одна кеш-линия:<br>thread0_counter + thread1_counter"] --> B["Core 0 пишет thread0_counter"]
B --> C["Линия -> Modified в Core 0<br>копия Core 1 -> Invalid"]
C --> D["Core 1 пишет thread1_counter"]
D --> E["Линия -> Modified в Core 1<br>копия Core 0 -> Invalid"]
E --> F["Следующая запись Core 0<br>снова требует передачу владения"]
F --> B
Процессор не знает и не может знать, что два потока пишут в разные байты одной линии. Гранулярность когерентности — 64 байта: для протокола это не «два независимых счётчика», а одна неделимая единица владения. Всё, что попало в одну линию, разделяется целиком.
Масштаб проблемы
С ростом числа ядер ситуация ухудшается: каждый invalidate требует подтверждения инвалидации от ядер, кеширующих эту линию, и когерентный трафик на интерконнекте растёт.
Устранение false sharing: выравнивание по кеш-линии
Решение — разнести переменные в разные кеш-линии. Если каждая переменная начинается с границы 64 байт, она гарантированно не делит линию ни с чем. Выравнивание (alignment) — размещение данных по адресам, кратным их размеру: четырёхбайтовый int по адресу, кратному 4. Подробнее — в ABI и размещении данных. Здесь тот же принцип, но цель не корректность доступа, а производительность.
В C с помощью _Alignas (C11):
struct counters { _Alignas(64) int64_t thread0_counter; // линия 0: байты 0-63 _Alignas(64) int64_t thread1_counter; // линия 1: байты 64-127};
Размер структуры вырос с 16 байт до 128 байт (две кеш-линии). Зато каждый поток работает со своей линией, пинг-понг прекращается, и время работы возвращается к ожидаемому — столько же, сколько один поток. Платёж — память: восьмикратный рост размера структуры ради двух 8-байтовых счётчиков. Поэтому выравнивание по кеш-линии оправдано для полей, в которые часто и независимо пишут разные ядра (горячие счётчики, очереди, per-CPU данные), а не для всех подряд. Аналогичные механизмы есть в Rust (#[repr(align(64))]), C++ (alignas(64)), Java (@Contended), Go (padding).
Как обнаружить false sharing: perf c2c и HITM
False sharing коварен тем, что код выглядит корректно: никаких гонок данных, никаких ошибок. Единственный симптом — необъяснимое замедление при увеличении числа потоков.
Инструменты: perf c2c (из семейства perf) на Linux показывает кеш-линии с высоким уровнем когерентного трафика между ядрами. Intel VTune выделяет «contested cache lines» в профиле. Ключевая метрика — HITM (Hit Modified): количество раз, когда ядро обнаруживало, что запрошенная линия находится в состоянии Modified в кеше другого ядра.
$ perf c2c record -a -- ./benchmark$ perf c2c report Shared Data Cache Line Table ───────────────────────────────────────────────── Total Remote LLC Store ... Records HITM Miss ───────────────────────────────────────────────── 52312 48901 112 51003 0x7f00 (struct counters)
Высокое значение Remote HITM на одном адресе — верный признак false sharing или истинного разделения. Дальше нужно смотреть, какие поля структуры по этому адресу модифицируют разные потоки.
Когда кеш становится накладным расходом
Все примеры выше — два ядра. На реальных процессорах ядер десятки, и иерархия — L1 → L2 → L3 (общий для всех ядер сокета) → RAM. Когерентный протокол живёт в этой иерархии: L3 берёт на себя роль координатора — встроенный в него snoop filter (фильтр слежения) знает, какие ядра кешируют какую линию, и направляет invalidate/bus read адресно, а не рассылает всем. Это снижает когерентный трафик, но не меняет картины для программиста: запись одного ядра становится видна другим через тот же протокол.
Закономерность, которая прошла через всю заметку: любая операция, требующая когерентной транзакции с другим ядром, стоит 20-70 нс — сопоставимо с промахом в RAM. Кеш помогает только когда данные локальны для ядра. Как только два ядра начинают писать в одну линию — настоящее разделение или false sharing — кеш превращается из ускорителя в накладной расход на передачу владения.
Мы многократно использовали «~100 нс из RAM» как данность — откуда берётся это число? Почему последовательное чтение из RAM в 50 раз быстрее случайного? Ответ — в устройстве DRAM: строках, столбцах, банках и таймингах, из которых складывается задержка каждого обращения.
См. также
Когерентность прикладных кешей — аналогичная проблема согласованности на уровне архитектуры: как поддерживать консистентность между локальным кешем приложения и источником данных
Sources
John L. Hennessy, David A. Patterson, 2017, Computer Architecture: A Quantitative Approach — Chapter 5: Memory Hierarchy Design, Section 5.2: Cache Coherence