Конкурентность в Go: общая память

Данная статья является переводом статьи Фредерико Биттенкарта (Frederico Bittencourt).

Original: https://levelup.gitconnected.com/concurrency-in-go-shared-memory-a2ef201b396b

Original link2: https://blog.fredrb.com/2022/10/15/go-concurrency-shared-memory/

Я поэкспериментировал с несколькими примерами для лучшего понимания как модель памяти в Go ведет себя в конкурентных программах. Я попробую объяснить, что я изучил по поводу порядка операций на мульти-ядерных CPU.

Пример, который я собираюсь показать – это расширение того примера передачи сообщений, написанного Расом Коксом в его посте Hardware Model. После его прочтения я захотел поэкспериментировать с поведением модели памяти и посмотреть на это поведение своими глазами. Данный пост – это результат этих экспериментов.

Алиса и Боб в офисе

Алиса и Боб делят офис. Их смены иногда пересекаются, но так же они могут начинать и заканчивать в разное время. Они приходят, выполняют свою работу и уходят. Однако, они имеют правило: последний кто уходит должен выключить свет. Проблема в том, что Алиса приходит очень рано и уходит перед тем, когда приходит Боб, так что когда Боб уходит он не знает если Алиса уже пришла или еще не ушла. Они придумали систему, чтобы дать друг другу знать, что их работа сделана: они ставят флаг на своей стороне офиса, когда уходят. Таким обрахом, каждый из них перед уходом может выключить свет и опустить оба флага, если видит, что флаг оппонента поднят.

Давайте смоделируем это в коде:

type Worker int

const (
	Alice Worker = iota
	Bob          = iota
)

type Office struct {
	// 0 => Alice's flag
	// 1 => Bob's flag
	flag [2]bool

	lights bool
}

func (f *Office) Work(w Worker, wg *sync.WaitGroup) {
	// Do work 
	// ...
  
	// Set your own flag up
	f.flag[w] = true

	// If both flags are up, turn the lights off and put the flags down
	if f.flag[w] && f.flag[1-w] {
		f.lights = false
		f.flag = []bool{false, false}
	}

	wg.Done()
}

Это неправильный код. Но почему он неправильный?..

Ради плавности повествования, давайте сейчас проигнорируем sync.WaitGroup. Суть этого примера – это подсветить где Go модель прерывается, так что мы можем лучше понимать как и почему конкурентно-безопасный код построен.

Этот прямолинейный код. Задано, что Office начинает свой день с включенным светом, После всех вызовов Work Office.lights должен быть выключен.

Логически, есть только 3 сценария:

Алиса выключает свет: горутина Боба завершается первой
Боб выключает свет: горутина Алисы завершается первой
Они оба выключают свет: они одновременно поднимают свои флаги

Условимся, что горутины ставятся в планировщик "честно", те. существует ряд взаимосвязанных операций, которые можно рассматривать как последовательные с внешней точки зрения. Каждое событие происходит в единой глобальной упорядоченности. Это делает 3-й сценарий возможным. В последовательно согласованной среде не может быть 4-го сценария, когда никто не выключил свет (почему?).

Для случая, когда Боб уходит последним и выключает за собой свет, предположим, что Боб – это последняя горутина, которая достигает выражения if. Мы знаем точно, что f.flog[Bob] установлен true, потому что он был только что установлен в горутине. Для того, чтобы Боб НЕ выключал свет, флаг f.flag[Alice] должен быть false, что значит Алиса не закончила свою работу. А это значит, что Боб не последний человек, уходящий из офиса – противоречие.

Давайте посмотрим на это в действии в следующем тесте:

func Test_WorkingDays(t *testing.T) {
	office := new(Office)
	// Lights on in the beginning of the day
	office.lights = true

	wg := sync.WaitGroup{}
	wg.Add(2)

	go office.Work(Alice, &wg)
	go office.Work(Bob, &wg)

	wg.Wait()

	if office.lights {
		t.Errorf("lights shouldn't be on after both finished their work")
	}
}

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

Чтобы проблема проявилась, я запустил этот тест 1 миллион раз:

$ go test -count=1000000 .
--- FAIL: Test_WorkingDays (0.00s)
    mem_test.go:49: lights shouldn\'t be on after both finished their work
--- FAIL: Test_WorkingDays (0.00s)
    mem_test.go:49: lights shouldn\'t be on after both finished their work
... (x15)
FAIL
FAIL	github.com/fredrb/concurrency/memory	10.114s
FAIL

Этот тест проваливался 17 раз, но прошёл 999983 раза. Как такое возможно?

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

Другой причиной является изменение порядка выполнения операций с целью оптимизации их выполнения на некоторых архитектурах, например arm (Прим. переводчика).

Если обе горутины запланированы на разные ядра, возможно следующее состояние флагов после выполнения программы (хотя и маловероятно):

поток 1: flag: [true, false] => свет выключен
поток 2: flag: [false, true] => свет выключен

Это может произойти, если:

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

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

Интересный способ доказать, что ЦП является причиной некорректного поведения программы – это проведение одинакового количества тестов только с одним процессором:

$ go test -cpu 1 -count=1000000 . 
ok github.com/fredrb/concurrency/memory	6.824s

Вы можете указать сколь угодно большое число итераций – тесты всегда будут проходить, если указан один CPU (потому что все горутины запланированы на один поток ОС).

Исправление программы

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

UPD. Как мне было указано, первоначальное решение, предложенное мною ниже, по-прежнему сопряжено с проблемами. Даже думая, что тесты пройдут, есть race condition при устанавке общих переменных в горутине – даже если нет никакой другой активной горутины. Плюс есть риск, что данные обновятся внутри блока if и эти обновления не будут замечены другими горутинами поскольку нет никакого механизма синхронизации. Вот оригинальное решение, которое содержит race condition:

func (f *Office) Work(w Worker, wg *sync.WaitGroup) {
  defer wg.Done()
	atomic.StoreUint32(&f.flag[w], 1)
	if atomic.LoadUint32(&f.flag[w]) == atomic.LoadUint32(&f.flag[1-w]) {
		// DATA RACE:
		f.lights = false
		f.flag = [2]bool{false, false}
	}
}

Это пока неправильное решение

Я пытался быть умным. Не будь умным.

Вот лучшее решение проблемы с использованием мьютекса:

type Office struct {
	flag     [2]bool
	flagLock sync.Mutex
	lights   bool
}

func (f *Office) DoWork(w Worker, wg *sync.WaitGroup) {
	defer wg.Done()
	// Do work
	// ...

	f.flagLock.Lock()
	defer f.flagLock.Unlock()
	f.flag[w] = true
	if f.flag[w] && f.flag[1-w] {
		f.lights = false
		f.flag = [2]bool{false, false}
	}
}

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

Дальнейшее чтение

Если вы нашли эту статью интересной и хотите узнать больше об этой теме, я использовал следующие ресурсы для понимания поведения моей программы:

Russ Cox Memory Models series: https://research.swtch.com/mm
Go’s memory model entry: https://go.dev/ref/mem
The Art of Multiprocess Programming (book): Chapter 7. Even though this chapter is specifically about locks, it offers some examples that are pretty close to the office example I showed above.

Алиса и Боб в офисе

Исправление программы

Дальнейшее чтение

You might also like...