Модель памяти Go

Версия от 6 июня 2022 года

Введение

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

Рекомендации

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

Для синхронизации доступа защищайте данные с помощью операций каналов или других примитивов синхронизации, таких как те, что находятся в пакетах sync и sync/atomic.

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

Не будьте хитрыми.

Неформальный обзор

Go подходит к своей модели памяти так же, как и остальная часть языка, стремясь сделать семантику простой, понятной и полезной. Этот раздел даёт общий обзор подхода и должен быть достаточным для большинства программистов. Модель памяти формально определена в следующем разделе.

Гонка данных определяется как запись в место в памяти, происходящая одновременно с другим чтением или записью в то же самое место, если только все доступы не являются атомарными, как предусмотрено пакетом sync/atomic. Как уже упоминалось, программистам настоятельно рекомендуется использовать соответствующую синхронизацию для избежания гонок данных. В отсутствие гонок данных, программы на Go ведут себя так, как если бы все горутины были мультиплексированы на одном процессоре. Это свойство иногда называют DRF-SC: программы без гонок данных выполняются в последовательно согласованном режиме.

Хотя программисты должны писать программы на Go без гонок данных, существуют ограничения на то, что реализация Go может сделать в ответ на гонку данных. Реализация всегда может отреагировать на гонку данных, сообщив о ней и завершив выполнение программы. В противном случае, каждое чтение одиночного слова или подслова памяти должно наблюдать значение, действительно записанное в это место (возможно, параллельно выполняющейся горутиной) и ещё не перезаписанное. Эти ограничения реализации делают Go похожим на Java или JavaScript, поскольку большинство гонок имеют ограниченное количество исходов, а не похожим на C и C++, где смысл любой программы с гонкой полностью не определён, и компилятор может делать всё, что угодно. Подход Go направлен на то, чтобы сделать ошибочные программы более надёжными и проще отлаживаемыми, сохраняя при этом убеждение, что гонки являются ошибками, а инструменты могут диагностировать и сообщать о них.

Модель памяти

Следующее формальное определение модели памяти Go тесно следует за подходом, представленным Хансом-Ж. Бёмом и Саритой В. Адве в статье “Основы памятной модели параллелизма в C++”, опубликованной на PLDI 2008. Определение программ без гонок данных и гарантия последовательной согласованности для таких программ эквивалентны тем, что представлены в этой работе.

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

Операция памяти моделируется четырьмя деталями:

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

Некоторые операции памяти являются читающими, включая чтение, атомарное чтение, блокировку мьютекса и получение из канала. Другие операции памяти являются пишущими, включая запись, атомарную запись, разблокировку мьютекса, отправку в канал и закрытие канала. Некоторые, такие как атомарная операция compare-and-swap, являются одновременно и читающими, и пишущими.

Выполнение горутины моделируется как набор операций памяти, выполняемых одной горутиной.

Требование 1: Операции памяти в каждой горутине должны соответствовать корректному последовательному выполнению этой горутины, учитывая значения, считанные из и записанные в память. Это выполнение должно быть согласовано с отношением sequenced before, определяемым как частичный порядок, установленный спецификацией языка Go для конструкций управления потоком выполнения Go, а также порядка оценки выражений.

Выполнение программы в Go моделируется как набор выполнений горутин, вместе с отображением W, которое указывает, из какой операции записи считывает каждая операция чтения. (Несколько выполнений одной и той же программы могут иметь разные выполнения программ.)

Требование 2: Для заданного выполнения программы отображение W, ограниченное синхронизирующими операциями, должно быть объяснимо некоторым неявным полным порядком синхронизирующих операций, который согласован с упорядочиванием и значениями, считанными и записанными этими операциями.

Отношение synchronized before — это частичный порядок над синхронизирующими операциями памяти, вытекающий из W. Если синхронизирующая операция чтения r наблюдает синхронизирующую операцию записи w (то есть, если W(r) = w), тогда w синхронизирована перед r. Формально, отношение synchronized before — это подмножество неявного полного порядка, упомянутого в предыдущем абзаце, ограниченное информацией, которую напрямую наблюдает W.

Отношение happens before определяется как транзитивное замыкание объединения отношений sequenced before и synchronized before.

Требование 3: Для обычного (несинхронизирующего) чтения данных r из памяти x, W(r) должно быть записью w, которая видима для r, где видимость означает, что выполняются оба следующих условия:

1. w происходит до r.
2. w не происходит до другой записи w' (в x), которая происходит до r.

Гонка данных read-write в памяти x состоит из операции чтения r и операции записи w в x, по крайней мере одна из которых не синхронизирующая, и которые не упорядочены отношением happens before (то есть, ни r не происходит до w, ни w не происходит до r).

Гонка данных write-write в памяти x состоит из двух операций записи w и w' в x, по крайней мере одна из которых не синхронизирующая, и которые не упорядочены отношением happens before.

Обратите внимание, что если не существует гонок данных read-write или write-write в памяти x, то любое чтение r в x имеет только одно возможное значение W(r): единственную запись w, которая непосредственно предшествует r в порядке happens before.

В более общем случае, можно показать, что любая программа на Go, свободная от гонок данных, то есть имеющая выполнения без гонок данных read-write или write-write, может иметь только результаты, объяснимые некоторым последовательно согласованным переключением выполнений горутин. (Доказательство аналогично разделу 7 статьи Бома и Адве, упомянутой выше.) Это свойство называется DRF-SC.

Цель формального определения — соответствовать гарантии DRF-SC, предоставляемой программам без гонок в других языках, включая C, C++, Java, JavaScript, Rust и Swift.

Некоторые операции языка Go, такие как создание горутины и выделение памяти, действуют как синхронизирующие операции. Эффект этих операций на частичный порядок synchronized-before описан в разделе «Синхронизация» ниже. Отдельные пакеты отвечают за предоставление аналогичной документации для своих собственных операций.

Ограничения реализации для программ, содержащих гонки данных

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

Любая реализация может, обнаружив гонку данных, сообщить о ней и остановить выполнение программы. Реализации, использующие ThreadSanitizer (доступен с помощью команды “go build -race”), делают именно это.

Чтение массива, структуры или комплексного числа может быть реализовано как чтение каждого отдельного подзначения (элемента массива, поля структуры или вещественной/мнимой составляющей), в любом порядке. Аналогично, запись в массив, структуру или комплексное число может быть реализована как запись каждого отдельного подзначения, в любом порядке.

Чтение r памяти по адресу x, хранящего значение, которое не превышает размер машинного слова, должно наблюдать некоторую запись w, такую что r не происходит до w и не существует записи w', такой что w происходит до w' и w' происходит до r. Иными словами, каждое чтение должно наблюдать значение, записанное предшествующей или параллельной записью.

Кроме того, наблюдение акаузальных и «из ниоткуда» записей запрещено.

Чтения памяти, размер которых превышает один машинный слово, поощряются, но не требуются для соблюдения тех же семантик, что и память размером в машинное слово, наблюдая единственную разрешённую запись w. По причинам производительности, реализации могут вместо этого рассматривать большие операции как набор отдельных операций над машинными словами в неопределённом порядке. Это означает, что гонки на многословарных структурах данных могут привести к несогласованным значениям, не соответствующим одной записи. Когда значения зависят от согласованности внутренних (указатель, длина) или (указатель, тип) пар, как это может быть в случае значений интерфейсов, карт, срезов и строк в большинстве реализаций Go, такие гонки могут привести к произвольной коррупции памяти.

Примеры неправильной синхронизации приведены в разделе «Неправильная синхронизация» ниже.

Примеры ограничений на реализации приведены в разделе «Неправильная компиляция» ниже.

Синхронизация

Инициализация

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

Если пакет p импортирует пакет q, завершение init функций q происходит до начала любого из p.

Завершение всех init функций синхронизировано перед началом функции main.main.

Создание горутин

Инструкция go, запускающая новую горутину, синхронизирована перед началом выполнения горутины.

Например, в этой программе:

var a string
func f() {
  print(a)
}
func hello() {
  a = "hello, world"
  go f()
}

вызов hello выведет "hello, world" в какой-то момент в будущем (возможно, после того как hello вернётся).

Уничтожение горутин

Выход из горутины не гарантируется синхронизацией перед любым событием в программе. Например, в этой программе:

var a string
func hello() {
  go func() { a = "hello" }()
  print(a)
}

присваивание a не сопровождается никаким событием синхронизации, поэтому не гарантируется, что оно будет замечено другой горутиной. На самом деле, агрессивный компилятор может удалить всю инструкцию go.

Если эффекты горутины должны быть замечены другой горутиной, используйте механизм синхронизации, такой как блокировка или передача по каналу, чтобы установить относительный порядок.

Каналы

Основным методом синхронизации между горутинами является коммуникация через каналы. Каждая отправка по определённому каналу сопоставляется с соответствующим получением из этого же канала, обычно в другой горутине.

Отправка по каналу синхронизируется до завершения соответствующего получения из этого же канала.

Эта программа:

var c = make(chan int, 10)
var a string
func f() {
  a = "hello, world"
  c <- 0
}
func main() {
  go f()
  <-c
  print(a)
}

гарантированно выводит "hello, world". Запись в a предшествует отправке по c, которая синхронизируется до завершения соответствующего получения по c, которое, в свою очередь, синхронизируется до выполнения print.

Закрытие канала синхронизируется до получения нулевого значения, потому что канал закрыт.

В предыдущем примере, заменив c <- 0 на close(c), получается программа с тем же гарантированным поведением.

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

Эта программа (как и выше, но с переставленными инструкциями отправки и получения и использованием небуферизованного канала):

var c = make(chan int)
var a string
func f() {
  a = "hello, world"
  <-c
}
func main() {
  go f()
  c <- 0
  print(a)
}

также гарантированно выводит "hello, world". Запись в a предшествует получению по c, которое синхронизируется до завершения соответствующей отправки по c, которая, в свою очередь, синхронизируется до выполнения print.

Если канал был бы буферизованным (например, c = make(chan int, 1)), то программа не гарантированно вывела бы "hello, world". (Могла бы вывести пустую строку, вызвать ошибку или сделать что-то другое.)

k-е получение данных из канала с ёмкостью C синхронизируется до завершения k+C-й отправки в этот же канал.

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

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

var limit = make(chan int, 3)
func main() {
  for _, w := range work {
    go func(w func()) {
      limit <- 1
      w()
      <-limit
    }(w)
  }
  select{}
}

Блокировки

Пакет sync реализует два типа данных блокировки: sync.Mutex и sync.RWMutex.

Для любой переменной sync.Mutex или sync.RWMutex l и n < m, вызов n метода l.Unlock() синхронизируется до завершения вызова m метода l.Lock().

Эта программа:

var l sync.Mutex
var a string
func f() {
  a = "hello, world"
  l.Unlock()
}
func main() {
  l.Lock()
  go f()
  l.Lock()
  print(a)
}

гарантированно выводит "hello, world". Первый вызов l.Unlock() (в функции f) синхронизируется до завершения второго вызова l.Lock() (в функции main), который, в свою очередь, синхронизируется до выполнения print.

Для любого вызова l.RLock на переменной sync.RWMutex l, существует такое n, что n-й вызов l.Unlock синхронизируется до завершения вызова l.RLock, а соответствующий вызов l.RUnlock синхронизируется до завершения вызова n+1 метода l.Lock.

Успешный вызов l.TryLock (или l.TryRLock) эквивалентен вызову l.Lock (или l.RLock). Неудачный вызов вообще не оказывает синхронизирующего эффекта. С точки зрения модели памяти, l.TryLock (или l.TryRLock) может быть рассмотрен как способный возвращать false, даже если мьютекс l разблокирован.

Once

Пакет sync предоставляет безопасный механизм инициализации в присутствии нескольких горутин с использованием типа Once. Несколько потоков могут выполнять once.Do(f) для конкретного f, но только один из них выполнит f(), а остальные вызовы заблокируются до возврата из f().

Завершение одного вызова f() из once.Do(f) синхронизировано до возврата любого вызова once.Do(f).

В этой программе:

var a string
var once sync.Once
func setup() {
  a = "hello, world"
}
func doprint() {
  once.Do(setup)
  print(a)
}
func twoprint() {
  go doprint()
  go doprint()
}

вызов twoprint вызовет setup ровно один раз. Функция setup завершится до любого вызова print. Результатом будет печать "hello, world" дважды.

Атомарные значения

API в пакете sync/atomic представляют собой совокупность «атомарных операций», которые могут использоваться для синхронизации выполнения различных горутин. Если эффект атомарной операции A наблюдается атомарной операцией B, то A синхронизирована перед B. Все атомарные операции, выполненные в программе, ведут себя так, как будто они выполнены в некотором последовательно согласованном порядке.

Приведённое выше определение имеет ту же семантику, что и последовательно согласованные атомики в C++ и переменные volatile в Java.

Финализаторы

Пакет runtime предоставляет функцию SetFinalizer, которая добавляет финализатор для вызова, когда конкретный объект больше не достижим программой. Вызов SetFinalizer(x, f) синхронизирован перед вызовом финализации f(x).

Дополнительные механизмы

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

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

Неправильная синхронизация

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

В этой программе:

var a, b int
func f() {
  a = 1
  b = 2
}
func g() {
  print(b)
  print(a)
}
func main() {
  go f()
  g()
}

может произойти, что g напечатает 2, а затем 0.

Этот факт опровергает несколько распространённых идиом.

Двойная проверка блокировки — это попытка избежать накладных расходов синхронизации. Например, программа twoprint может быть неправильно написана следующим образом:

var a string
var done bool
func setup() {
  a = "hello, world"
  done = true
}
func doprint() {
  if !done {
    once.Do(setup)
  }
  print(a)
}
func twoprint() {
  go doprint()
  go doprint()
}

но не существует гарантии, что в doprint, наблюдая запись в done, мы также наблюдаем запись в a. Эта версия может (неправильно) напечатать пустую строку вместо "hello, world".

Еще один неправильный идиоматический прием — это активное ожидание значения, как в следующем примере:

var a string
var done bool
func setup() {
  a = "hello, world"
  done = true
}
func main() {
  go setup()
  for !done {
  }
  print(a)
}

Как и раньше, нет никакой гарантии, что в main наблюдение за записью в done подразумевает наблюдение за записью в a, поэтому эта программа может также напечатать пустую строку. Хуже того, нет гарантии, что запись в done будет когда-либо замечена main, поскольку между двумя горутинами нет событий синхронизации. Цикл в main не гарантированно завершится.

Существуют более тонкие варианты этой идеи, например, следующая программа.

type T struct {
  msg string
}
var g *T
func setup() {
  t := new(T)
  t.msg = "hello, world"
  g = t
}
func main() {
  go setup()
  for g == nil {
  }
  print(g.msg)
}

Даже если main замечает g != nil и выходит из цикла, нет гарантии, что будет замечено инициализированное значение для g.msg.

Во всех этих примерах решение одинаково: используйте явную синхронизацию.

Неправильная компиляция

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

Все следующие примеры предполагают, что *p и *q ссылаются на памятные области, доступные нескольким горутинам.

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

*p = 1
if cond {
  *p = 2
}

То есть, компилятор не должен переписывать программу в следующий вариант:

*p = 2
if !cond {
  *p = 1
}

Если cond равно false и другая горутина читает *p, то в оригинальной программе другая горутина может наблюдать только любое предыдущее значение *p и 1. В переписанной программе другая горутина может наблюдать 2, что ранее было невозможно.

Не введение гонок данных также означает, что нельзя предполагать, что циклы завершаются. Например, компилятор обычно не должен перемещать обращения к *p или *q впереди цикла в следующей программе:

n := 0
for e := list; e != nil; e = e.next {
  n++
}
i := *p
*q = 1

Если list указывает на циклический список, то оригинальная программа никогда не будет обращаться к *p или *q, но переписанная программа будет. (Перемещение *p вперёд будет безопасно, если компилятор сможет доказать, что *p не вызовет паники; перемещение *q вперёд также потребует доказательства того, что никакая другая горутина не может получить доступ к *q.)

Не введение гонок данных также означает, что нельзя предполагать, что вызываемые функции всегда возвращаются или не содержат операций синхронизации. Например, компилятор не должен перемещать обращения к *p или *q впереди вызова функции в следующей программе (по крайней мере, не без прямого знания точного поведения f):

f()
i := *p
*q = 1

Если вызов никогда не вернётся, то снова оригинальная программа никогда не будет обращаться к *p или *q, но переписанная программа будет. И если вызов содержит синхронизационные операции, то оригинальная программа может установить связи «происходит до» перед обращениями к *p и *q, но переписанная программа не сможет.

Не позволять одному чтению наблюдать несколько значений означает не перезагружать локальные переменные из общей памяти. Например, компилятор не должен отбрасывать i и перезагружать его второй раз из *p в следующей программе:

i := *p
if i < 0 || i >= len(funcs) {
  panic("invalid function index")
}
... complex code ...
// compiler must NOT reload i = *p here
funcs[i]()

Если сложный код требует множество регистров, компилятор для однотонных программ может игнорировать i, не сохраняя копию, а затем перезагрузить i = *p непосредственно перед funcs[i](). Компилятор Go не должен этого делать, поскольку значение *p могло измениться. (Вместо этого компилятор может вытолкнуть i на стек.)

Запрет на то, чтобы одна запись могла записывать несколько значений, также означает, что нельзя использовать память, в которую будет записана локальная переменная, как временное хранилище перед записью. Например, компилятор не должен использовать *p как временное хранилище в этой программе:

*p = i + *p/2

То есть, он не должен переписывать программу в следующий вариант:

*p /= 2
*p += i

Если i и *p изначально равны 2, исходный код выполняет *p = 3, поэтому гоняющаяся горутина может прочитать только 2 или 3 из *p. Переписанная программа выполняет *p = 1 и затем *p = 3, что позволяет гоняющейся горутине прочитать и 1.

Обратите внимание, что все эти оптимизации разрешены в компиляторах C/C++: компилятор Go, разделяющий бэкенд с компилятором C/C++, должен убедиться, что отключены оптимизации, которые недопустимы для Go.

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

n := 0
for i := 0; i < m; i++ {
  n += *shared
}

в:

n := 0
local := *shared
for i := 0; i < m; i++ {
  n += local
}

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

Заключение

Программисты Go, пишущие программы без гонок данных, могут полагаться на последовательное выполнение таких программ, как и в практически всех других современных языках программирования.

Когда дело доходит до программ с гонками, как программисты, так и компиляторы должны помнить совет: не будьте хитрыми.