--- title: "Конкурентные структуры, барьеры памяти, false sharing" description: "Самый прямой способ сделать структуру данных безопасной для нескольких потоков — обернуть её мьютексом. Такую структуру называют потокобезопасной (thread-safe): ей можно…" canonical: https://graphlms.ru/os/book/concurrent-structures course: "Операционные системы" updated: 2026-10-12 lang: ru publisher: GraphLMS --- # Конкурентные структуры, барьеры памяти, false sharing > Источник: https://graphlms.ru/os/book/concurrent-structures — курс «Операционные системы», GraphLMS. ## Один мьютекс на всё и почему он тормозит Самый прямой способ сделать структуру данных безопасной для нескольких потоков — обернуть её мьютексом. Такую структуру называют **потокобезопасной** (thread-safe): ей можно пользоваться из многих потоков одновременно, и данные не испортятся. ```go type SafeMap struct { mu sync.Mutex m map[string]int } func (s *SafeMap) Inc(key string) { s.mu.Lock() s.m[key]++ s.mu.Unlock() } ``` Это корректно, и с этого почти всегда стоит начинать. Но представьте кэш сессий в сервисе на 32 ядрах процессора: каждый запрос делает `Get` или `Set`, и все они проходят через один `s.mu`. В каждый момент внутри может быть только одна горутина, остальные ждут. Ситуация, когда много потоков одновременно хотят один и тот же лок, называется **contention** (борьба за лок). При сильной борьбе параллельный код вырождается в последовательный: ядер 32, а работает фактически одно. Плюс каждое ожидание — это спин или парковка, которые мы разбирали в [предыдущей главе](/os/book/locks-hardware). Как увидеть contention в Go: профиль блокировок `pprof` с `runtime.SetMutexProfileFraction` показывает, на каких мьютексах горутины ждут дольше всего. Это первое, что стоит снять, прежде чем что-то оптимизировать. ## Шардирование: много маленьких локов Если ключи независимы, им не нужен общий замок. Разобьём map на N частей (шардов), у каждой свой мьютекс. Ключ попадает в шард по хешу. ```text ключ "user:42" ── hash % 16 = 5 ──► shard[5] (свой lock) ключ "order:7" ── hash % 16 = 12 ──► shard[12] (свой lock) ┌────────┬────────┬────────┬─────┬─────────┐ │ shard0 │ shard1 │ shard2 │ ... │ shard15 │ у каждого свой mutex └────────┴────────┴────────┴─────┴─────────┘ ``` Две горутины с разными ключами почти всегда попадают в разные шарды и не мешают друг другу. Этот приём называют **striped locks** или **sharding**, а в общем виде говорят о **гранулярности блокировок**: крупная (один лок на всё) проще, мелкая (много локов на части) лучше масштабируется. ```go type ShardedMap struct { shards [16]struct { mu sync.Mutex m map[string]int } } func (s *ShardedMap) shard(key string) int { h := fnv.New32a() h.Write([]byte(key)) return int(h.Sum32() % 16) } ``` У мелкой гранулярности есть цена. Операции «по всей структуре» (посчитать `Len`, обойти все элементы, сделать снимок) теперь должны пройти по всем шардам и взять все локи, и если брать их в разном порядке, можно получить [взаимоблокировку](/os/book/deadlock). А если ключи распределены неравномерно (один горячий ключ), шардирование не поможет: все запросы всё равно упрутся в один шард. В стандартной библиотеке Go есть `sync.Map`. С Go 1.24 внутри у неё конкурентное хеш-дерево (hash trie), где разные ключи живут в разных узлах, то есть по сути та же идея мелкой гранулярности. Документация по-прежнему советует её для двух сценариев: ключ записывается один раз и много раз читается, или разные горутины работают с непересекающимися наборами ключей. В остальных случаях обычная типизированная map с мьютексом проще и не хуже по скорости. ## Lock-free: CAS вместо замка Иногда без лока можно обойтись совсем. Нужна операция **compare-and-swap** (CAS) из [прошлой главы](/os/book/locks-hardware): «запиши новое значение, если там всё ещё старое». На ней строится цикл повторов: ```go func incr(cnt *atomic.Int64) { for { old := cnt.Load() if cnt.CompareAndSwap(old, old+1) { return } // между Load и CAS кто-то успел изменить cnt — пробуем снова } } ``` ```text A: Load → 5, CAS(5→6) успех B: Load → 5, CAS(5→6) неудача (там уже 6) → Load → 6, CAS(6→7) успех ``` Такие структуры называют **lock-free**: ни один поток не держит замок, и если какой-то поток уснул на полпути, остальные всё равно продвигаются. Чем это отличается от мьютекса: - при неудаче мьютекс со временем усыпит поток, а CAS-цикл сразу пробует снова, без похода в ядро ОС; - при слабой борьбе это быстрее; при сильной потоки тратят CPU на повторы, которые всё равно проиграют. Частое заблуждение: «`atomic.AddInt64` внутри — такой же CAS-цикл». Нет. Для сложения у процессоров есть отдельная атомарная инструкция: на amd64 Go компилирует `Add` в `LOCK XADD`, на arm64 с расширением LSE — в `LDADDAL`. Цикл повторов появляется только там, где такой инструкции нет. CAS-цикл нужен, когда новое значение вычисляется сложнее, чем «плюс n»: например, «увеличить, но не больше лимита». Ловушка lock-free структур на указателях — **ABA-проблема**. Поток прочитал указатель на узел A и собирается сделать CAS. Пока он медлил, другой поток снял A, снял B, освободил их и положил новый узел, который аллокатор разместил по тому же адресу, что был у A. CAS видит «там A, как и было» и проходит, хотя структура уже совсем другая. Лечат счётчиком версий рядом с указателем или отложенным освобождением памяти. В Go ABA встречается реже, потому что сборщик мусора не отдаст адрес узла, пока на него кто-то ссылается, но для индексов в массиве (вместо указателей) проблема остаётся. Практическое правило: lock-free пишут для одной-двух горячих переменных (счётчики, флаги, указатель на текущий конфиг через `atomic.Pointer`). Lock-free очередь или map собственной разработки на ревью почти всегда хуже готового мьютекса. ## Барьеры памяти: запись не обязана стать видна в том порядке Теперь коварная часть. Один поток готовит данные и поднимает флаг, второй ждёт флаг и читает данные: ```text Поток 1 Поток 2 data = 42 while ready == 0 { } ready = 1 print(data) ``` Кажется очевидным, что раз поток 2 увидел `ready == 1`, то `data` уже 42. Это не так. Переставлять операции имеют право двое. **Компилятор.** Для потока 1 порядок двух независимых записей неважен, и оптимизатор может их поменять. Он же может прочитать `ready` в цикле потока 2 один раз и крутиться на значении из регистра вечно. **Процессор.** Здесь всё зависит от архитектуры. На x86 действует довольно строгая модель (TSO): записи становятся видны другим ядрам в том порядке, в каком их сделал поток, и чтения тоже не обгоняют друг друга. Единственная разрешённая перестановка — более поздняя загрузка может выполниться раньше предыдущей записи (запись в это время ждёт в **store buffer** — очереди записей ядра, которые ещё не дошли до кэша). На ARM и POWER модель слабее: и записи, и чтения могут стать видны в другом порядке. Код, который «всегда работал» на ноутбуке с Intel, иногда ломается на сервере с ARM (Graviton, Ampere) или на Mac с Apple Silicon. Запрещает перестановки **барьер памяти** (memory barrier, fence) — инструкция, через которую операции не переносятся: всё, что до барьера, станет видно раньше всего, что после. Барьер нужен с обеих сторон: у пишущего (не выпустить `ready` раньше `data`) и у читающего (не прочитать `data` раньше `ready`). В Go барьеры руками не ставят. Их вставляют операции синхронизации: атомики, мьютексы, каналы. Модель памяти Go описывает это через отношение **happens-before**: если запись в канал случилась до чтения из канала, то всё, что горутина сделала до отправки, видно горутине после приёма. То же для `Unlock` → следующий `Lock` и для атомарной записи → атомарного чтения, которое её увидело. Подробно — в главе [модель памяти Go](/go/book/memory-model). Правильный вариант примера: ```go var ( data int ready atomic.Bool ) // поток 1 data = 42 ready.Store(true) // публикация: data станет видна вместе с флагом // поток 2 for !ready.Load() { runtime.Gosched() } fmt.Println(data) // гарантированно 42 ``` Обычный `bool` вместо `atomic.Bool` — это гонка данных, и `go run -race` её поймает. Синхронизация нужна не только чтобы «не толкаться» в критической секции, но и чтобы записи одного потока стали видны другому в правильном порядке. ## Как ядра процессора договариваются о кэшах: MESI В этом разделе и следующем «ядро» — всегда ядро процессора (core), а не ядро ОС. Откуда вообще берётся проблема видимости? У каждого ядра свои кэши L1 и L2 — быстрые локальные копии кусков памяти. Обмениваются ядра не байтами, а **кэш-линиями** (cache line): на x86 линия 64 байта, на Apple M1/M2 и некоторых серверных ARM — 128. Чтобы два ядра не держали разные значения одной ячейки, они соблюдают протокол **когерентности**. Классический вариант — **MESI**, по первым буквам четырёх состояний линии в кэше ядра: ```text M (Modified) — линия есть только у меня, я её изменил, в памяти старое E (Exclusive) — линия только у меня, совпадает с памятью S (Shared) — копии у нескольких ядер, все только читают I (Invalid) — моя копия устарела, пользоваться нельзя Ядро 0 хочет записать в линию, которая есть у ядра 1: ядро 0 рассылает invalidate → у ядра 1 линия становится I ядро 0 получает линию в M и пишет ядро 1 при следующем чтении заново запрашивает линию ``` Главное следствие: запись в линию, которую держат другие ядра, не бесплатна. Это обмен сообщениями между ядрами и ожидание ответов, десятки наносекунд вместо одной. Чем больше ядер пишут в одну линию, тем больше этого трафика. Поэтому один атомарный счётчик, который инкрементируют все ядра, масштабируется плохо, хотя никаких локов в нём нет. ## False sharing Теперь неочевидный случай. Два счётчика логически независимы: каждый инкрементирует своё ядро. Но если они лежат в памяти рядом и попали в одну кэш-линию, ядра всё равно гоняют линию друг другу: ```text ┌──────────────── одна кэш-линия ────────────────┐ │ counterA (8 Б) │ counterB (8 Б) │ ... │ └────────────────────────────────────────────────┘ ▲ ядро 0 пишет ▲ ядро 1 пишет ядро 0 пишет A → линия у ядра 1 становится I ядро 1 пишет B → линия у ядра 0 становится I ... линия скачет между кэшами, хотя A и B не связаны ``` Это **false sharing** (ложное разделение): данные не общие, а линия общая. Лечится **padding** (набивкой): между переменными вставляют пустые байты, чтобы каждая заняла свою линию. Проверим на бенчмарке. Четыре горутины, каждая инкрементирует свой счётчик. В первом варианте счётчики лежат вплотную, во втором каждый добит до 128 байт. ```go package fs import ( "sync" "sync/atomic" "testing" ) const workers = 4 type packed struct { n [workers]atomic.Int64 // 4 × 8 байт подряд, одна линия } type padded struct { n [workers]struct { v atomic.Int64 _ [120]byte // 8 + 120 = 128 байт: своя линия и на x86, и на ARM } } func BenchmarkPacked(b *testing.B) { var c packed var wg sync.WaitGroup for w := 0; w < workers; w++ { wg.Add(1) go func(w int) { defer wg.Done() for i := 0; i < b.N; i++ { c.n[w].Add(1) } }(w) } wg.Wait() } func BenchmarkPadded(b *testing.B) { var c padded var wg sync.WaitGroup for w := 0; w < workers; w++ { wg.Add(1) go func(w int) { defer wg.Done() for i := 0; i < b.N; i++ { c.n[w].v.Add(1) } }(w) } wg.Wait() } ``` На ноутбуке с Apple M2 Pro (`go test -bench .`, Go 1.25) получилось так: ```text BenchmarkPacked-10 10033843 115.4 ns/op BenchmarkPadded-10 289468153 4.270 ns/op ``` Разница почти в 30 раз, а код отличается одним полем. Для сравнения: если все четыре горутины честно инкрементируют один общий счётчик, выходит те же ~115 нс. То есть с точки зрения железа «четыре независимых счётчика в одной линии» ничем не лучше одного общего. На вашей машине числа будут другими, но порядок разницы обычно сохраняется. Где это встречается в Go: шардированные счётчики метрик, массивы per-worker-состояний, статистика по ядрам. Для набивки есть готовый тип `cpu.CacheLinePad` в пакете `golang.org/x/sys/cpu` (размер под текущую архитектуру). Рантайм Go внутри делает то же самое для своих структур на P. Частая ошибка — паддить «на 64 байта» вслепую: на ARM-серверах и Mac линия может быть 128 байт, и тогда набивка не помогает. ## Что выбрать на практике | Симптом | Что на самом деле | Что делать | |---|---|---| | Сервис не ускоряется с ростом ядер, в mutex-профиле один горячий лок | contention | шардирование, сократить критическую секцию | | Значение «иногда не видно» другой горутине | нет синхронизации, гонка данных | atomic, mutex или канал; прогнать с `-race` | | Независимые счётчики тормозят под нагрузкой | false sharing | padding до размера кэш-линии | | Один общий atomic-счётчик стал горячим | трафик когерентности | шардированный счётчик, суммировать при чтении | Порядок действий: начать с обычного мьютекса; если профиль показал contention — шардировать или уменьшить критическую секцию; атомики — для одиночных горячих переменных; padding — когда независимые данные пишутся с разных ядер. > Квиз по разделу: см. вопросы в конце документа или на https://graphlms.ru/os/book/concurrent-structures ## Частые ошибки - Оптимизировать без профиля: заменять мьютекс на lock-free структуру, не увидев contention в mutex-профиле. - Использовать обычную переменную как флаг между горутинами «потому что на x86 работает». Это гонка данных; на ARM и после оптимизаций компилятора она проявится. - Считать, что `atomic.AddInt64` — это CAS-цикл и потому медленный под нагрузкой; медленным его делает борьба за кэш-линию. - Паддить до 64 байт вслепую: на Apple Silicon и части ARM-серверов линия 128 байт. - Ожидать, что шардирование поможет при одном горячем ключе. ## Проверьте себя 1. Почему 32 горутины с одним общим мьютексом работают не быстрее одной? 2. Что может переставить процессор x86, а что — ARM, в примере с `data` и `ready`? 3. Почему четыре независимых atomic-счётчика, лежащих рядом, работают так же медленно, как один общий? 4. В бенчмарке из главы замените `[120]byte` на `[56]byte`. На x86 с 64-байтной линией результат почти не изменится, а на Apple Silicon вариант станет примерно вдвое медленнее варианта со `[120]byte`, хотя и намного быстрее `packed`. Сколько счётчиков теперь делят одну линию? Ответы. (1) В каждый момент внутри только одна, остальные ждут: работа сериализуется. (2) x86 сохраняет порядок записей и порядок чтений, поэтому там переставляет только компилятор; ARM может переставить и записи, и чтения в железе. (3) Они в одной кэш-линии, и каждая запись инвалидирует линию у остальных ядер (false sharing). (4) Структура стала 64 байта, а линия 128, поэтому линию делят два счётчика: ложного разделения меньше, чем у `packed`, но оно есть. ## Что спрашивают на собесе - **Чем плох один мьютекс на всю структуру?** При сильной борьбе горутины стоят в очереди, работа сериализуется. Лечится шардированием (striped locks) и сокращением критической секции. - **Как сделать lock-free счётчик на CAS и в чём ловушка?** Цикл «Load → вычислить → CAS → при неудаче повторить». Ловушка структур на указателях — ABA. И уточнение: простой `atomic.Add` на amd64/arm64 — одна инструкция, а не цикл. - **Зачем барьеры памяти, если есть мьютекс?** Мьютекс как раз и даёт барьеры. Синхронизация обеспечивает не только взаимное исключение, но и порядок видимости записей (happens-before). - **Что x86 может переупорядочить?** Только запись с последующим чтением другого адреса (store buffer). ARM переупорядочивает больше, поэтому баги видимости чаще всплывают там. - **Что такое MESI?** Протокол когерентности кэшей: Modified, Exclusive, Shared, Invalid. Запись требует инвалидировать чужие копии, отсюда цена записи в общую линию. - **Что такое false sharing и как лечить?** Независимые переменные в одной кэш-линии, ядра гоняют линию друг другу. Лечится padding до размера линии (64 байта на x86, 128 на части ARM). ## Вопросы для самопроверки **Квиз «Конкурентные структуры и память»** 1. Почему один глобальный мьютекс на всю структуру плохо масштабируется на многоядерном сервере? - Мьютекс не защищает от гонок - Мьютекс работает только на одном ядре физически - Мьютекс занимает слишком много памяти - Все потоки сериализуются на одном замке — параллелизма нет (contention) (верно) - Пояснение: При одном замке в каждый момент работает только один поток, остальные стоят в очереди. Это contention/сериализация: сколько бы ни было ядер, реального параллелизма нет. 2. Что делает приём striped (sharded) locks? - Делит структуру на N кусков, у каждого свой замок — потоки на разных кусках не сталкиваются (верно) - Ускоряет один замок аппаратно - Заменяет мьютекс на спинлок - Полностью убирает блокировки - Пояснение: Sharding раздаёт каждому шарду свой лок. Потоки, попавшие в разные шарды, работают параллельно, contention резко падает. 3. Как устроен lock-free инкремент на CAS? - Захватываем лок, увеличиваем, отпускаем - Просто пишем new в память без проверок - Читаем old, считаем new, делаем CAS; если кто-то опередил — повторяем цикл (верно) - Усыпляем поток до освобождения значения - Пояснение: Это CAS-retry: прочитал old, посчитал new, сделал compare-and-swap; если значение успели поменять, цикл повторяется. По такой схеме пишут lock-free структуры. Простой счётчик в Go (atomic.AddInt64) на x86 обходится одной инструкцией LOCK XADD, но идея та же: изменение происходит атомарно, без замка. 4. Мьютекс защищает данные от одновременной записи. Какую ещё гарантию даёт цепочка «unlock в одном потоке, затем lock в другом» (happens-before)? - Оба потока окажутся на одном ядре и будут видеть один кэш - Второй поток увидит все записи, сделанные первым до unlock, и процессор с компилятором не переставят их через эту границу (верно) - Записи первого потока сразу попадут на диск - Второй поток не будет ждать на lock - Пояснение: Без барьеров процессор и компилятор вправе переставлять операции, а записи одного ядра не сразу видны другому. Unlock/lock (как и atomic, и операции с каналом) ставят барьеры, поэтому после захвата замка вы видите состояние, которое оставил предыдущий владелец. Это и есть happens-before: порядок, на который можно положиться. 5. Что такое false sharing? - Две независимые переменные лежат в одной кэш-линии, и ядра дерутся за линию (верно) - Мьютекс захвачен дважды одним потоком - Два потока пишут в одну и ту же переменную - Поток читает значение до его инициализации - Пояснение: Логически независимые переменные физически попали в одну 64-байтную линию. Запись одного ядра аннулирует линию у другого — линия пинг-понгует между кэшами, скорость падает. 6. Сколько байт обычно занимает одна кэш-линия на x86? - Ответ: 64 - Пояснение: Кэш-линия — минимальная единица обмена между кэшами ядер, на типичных x86 это 64 байта. Поэтому padding до 64B лечит false sharing. 7. Чем CAS-цикл (lock-free) отличается от мьютекса при провале попытки? - CAS усыпляет поток, мьютекс крутится - CAS крутится и пробует снова (busy retry), мьютекс может усыпить поток (верно) - Разницы нет - CAS всегда быстрее независимо от нагрузки - Пояснение: При неудаче CAS просто повторяет цикл, не уходя в ядро — выгодно при малой конкуренции. Мьютекс при провале усыпляет поток. При высокой конкуренции CAS жжёт CPU на ретраях.