Команда Go for Devs подготовила перевод статьи, в которой автор шаг за шагом решает классическую задачу об обедающих философах на Go. Вы узнаете, почему наивный подход ведёт к взаимной блокировке, как нарушить симметрию, чтобы избежать deadlock’а, и почему даже «рабочее» решение может оставить одного философа голодать вечно.

Недавно я углубленно изучал параллелизм и наткнулся на очень интересную и забавную задачу — проблему «Обедающих философов». Она может быть знакома тем, кто уже проходил курс параллельных вычислений. Изначально эту задачу предложил Эдсгер Дейкстра (да-да, тот самый, что придумал печально известный алгоритм Дейкстры для поиска кратчайшего пути) в качестве экзаменационного задания для своих студентов ?.

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

Постановка задачи

Задача состоит в следующем: у нас есть 5 философов, сидящих за круглым столом, и 5 палочек для еды (или вилок). Жизнь каждого философа — это бесконечный цикл размышлений и приёма пищи. Чтобы съесть лапшу, им нужны две палочки: одна слева и одна справа (в оригинальной версии Дейкстры использовались спагетти и две вилки). Чтобы пообедать, философ должен взять две палочки по обе стороны (левую и правую); когда он заканчивает есть, он кладёт обе палочки. Если у философа доступна только одна палочка, он не может есть и должен ждать, пока вторая палочка будет положена (этот вариант проблемы приписывается книге «Искусство многопроцессорного программирования»). 

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

Взаимное исключение и критические секции

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

Взаимное исключение — это механизм синхронизации, который предотвращает одновременный доступ двух или более потоков к общим ресурсам. В противном случае это может привести к повреждению данных, что является крайне нежелательной ситуацией, известной как состояние гонки. Чтобы лучше проиллюстрировать эту концепцию, представьте перекресток: он будет общим ресурсом, также известным в информатике как «критическая секция». Если считать каждый автомобиль потоком, то наша задача — избежать одновременного нахождения нескольких автомобилей на перекрестке. К счастью, для предотвращения таких опасных ситуаций существуют светофоры. Тот же принцип применим и к параллельному программированию, где алгоритмы помогают нам избежать одновременного доступа нескольких потоков к одному и тому же ресурсу.

Возвращаясь к программированию, представьте простую функцию, которая выполняется параллельно в нескольких потоках и просто увеличивает общий счетчик. Запустив такую функцию как поток или го-рутину в цикле из 100 итераций (с группой ожидания, чтобы избежать преждевременного выхода), мы могли бы ожидать, что итоговое значение счетчика будет равно 99, если начать с 0. Однако, скорее всего, это не так из-за состояний гонки.

Видите ли, инкремент — это не одна инструкция, а синтаксический сахар для трех операций: чтение счетчика, его изменение, а затем запись нового значения. Два или более потоков могут прочитать одно и то же значение (например, 42), прибавить единицу и записать 43 вместо 44. Это может произойти несколько раз за одно выполнение. Обратите внимание, что я выделил слова «может» и «вероятно», чтобы указать на вероятностный характер такого поведения — нам может повезти в одном выполнении, и состояния гонки не возникнет. Именно это делает параллелизм и совместное использование ресурсов inherently сложными: воспроизвести ошибки состояния гонки непросто, потому что планировщик сам решает, как запускать эти потоки/процессы/горутины, что делает нас частично слепыми в отношении порядка выполнения.

Для решения этой проблемы различные языки предоставляют различные механизмы синхронизации доступа к критическим секциям. В Go у нас есть отличный пакет sync из стандартной библиотеки, который предоставляет инструменты, упрощающие работу с параллелизмом и его осмысление. Основная структура, которую мы будем использовать для решения проблемы состояния гонки, — это sync.Mutex. Она блокирует доступ к определенной секции кода, так что только один поток может выполнять ее за раз, а затем разблокирует. Это похоже на то, как потоки по очереди получают токены перед выполнением своего кода. Давайте рассмотрим пример правильного параллельного инкремента в Go:

func main(){    
    var wg sync.WaitGroup
    counter := 0
    var mux sync.Mutex
    // Теперь правильно синхронизировано, чтобы избежать гонок данных
    for i := 0; i < 100; i++{
        wg.Add(1)
        go func(){
            defer wg.Done()
            mux.Lock()
            counter++
            mux.Unlock()
        }()
    }
    wg.Wait() // Гарантирует, что мы не выйдем из main преждевременно

    fmt.Printf("Counter: %d", counter) // Теперь корректно выводит 100
}

Прежде чем увеличить общий счетчик (критическая секция нашей программы), мы сначала блокируем выполнение с помощью mux.Lock(), увеличиваем счетчик, а затем разблокируем его с помощью mux.Unlock().

Взаимное исключение — обширная тема в проектировании параллельных систем, с множеством идей для изучения, но этого должно быть достаточно для решения проблемы обедающих философов. Тем не менее, этот механизм блокировки и разблокировки не является волшебным решением проблемы взаимного исключения — все еще могут возникать такие проблемы, как взаимные блокировки (deadlocks) и голодание (starvation).

Простой алгоритм:

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

Логическая последовательность действий для любого отдельно взятого философа выглядит так:

1. Запросить левую палочку для еды.

2. Запросить правую палочку для еды.

3. Есть в течение короткого периода.

4. Освободить левую палочку для еды.

5. Освободить правую палочку для еды.

6. Думать в течение короткого периода.

Этот цикл еды и размышлений определяет всю жизнь философа. Хотя эта последовательность кажется логичной, она содержит тонкий, но важный недостаток. Когда каждый философ пытается следовать одной и той же логике одновременно, они могут коллективно создать взаимную блокировку (deadlock).

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

Мы начнем с создания структуры Philosopher для хранения их ID и мьютексов для левой и правой палочек. Мы также определим методы Eat() и Think(), которые напрямую соответствуют шагам нашего алгоритма. Метод Live() затем будет служить оберткой для запуска этого цикла заданное количество раз.

Мы объединяем все это в функции main. Здесь мы обустроим обеденный стол, создав философов и палочки для еды. Мы используем оператор по модулю (%) при назначении правой палочки для создания круговой расстановки. Наконец, мы будем использовать sync.WaitGroup, чтобы гарантировать, что наша основная программа дождется завершения всех горутин философов, прежде чем выйти.

Вот полный, исполняемый код нашего первоначального решения:

package main

import (
	"fmt"
	"sync"
	"time"
)

// Philosopher хранит id и мьютексы для левой и правой палочек
type Philosopher struct {
	id             int
	leftChopstick  *sync.Mutex
	rightChopstick *sync.Mutex
}

// Think имитирует процесс размышлений
func (p *Philosopher) Think() {
	fmt.Printf("Философ %d размышляет.\n", p.id)
	time.Sleep(200 * time.Millisecond)
}

// Eat имитирует процесс еды, блокируя обе палочки
func (p *Philosopher) Eat() {
	p.leftChopstick.Lock()
	p.rightChopstick.Lock()

	fmt.Printf("Философ %d ест.\n", p.id)
	time.Sleep(200 * time.Millisecond)

	p.rightChopstick.Unlock()
	p.leftChopstick.Unlock()
}

// Live — это обёртка для действий Eat и Think на k циклов
func (p *Philosopher) Live(k int, wg *sync.WaitGroup) {
	defer wg.Done()
	for i := 0; i < k; i++ {
		p.Eat()
		p.Think()
	}
}

func main() {
	// Есть 5 философов и 5 палочек
	numPhilos := 5

	// Создаём палочки (мьютексы)
	chopSticks := make([]sync.Mutex, numPhilos)
	for i := 0; i < numPhilos; i++ {
		chopSticks[i] = sync.Mutex{}
	}

	// Создаём философов и назначаем им палочки
	philos := make([]Philosopher, numPhilos)
	for i := 0; i < numPhilos; i++ {
		philos[i] = Philosopher{
			id:             i + 1, // Используем индексацию с 1 для наглядности
			leftChopstick:  &chopSticks[i],
			rightChopstick: &chopSticks[(i+1)%numPhilos],
		}
	}

	numCycles := 3
	var wg sync.WaitGroup

	// Запускаем горутину для каждого философа
	for i := 0; i < numPhilos; i++ {
		wg.Add(1)
		go philos[i].Live(numCycles, &wg)
	}

	// Ждём, пока все философы закончат
	wg.Wait()
}

Подводный камень №1: Взаимные блокировки

Если запустить эту программу несколько раз, мы столкнемся с ошибкой: Go сообщит о взаимной блокировке (deadlock). Взаимная блокировка — это ситуация в параллельном ПО, когда один поток ожидает или спит, пока другой поток не освободит блокировку ресурса, в то время как второй поток также ожидает освобождения ресурса первым потоком, что приводит к циклическому ожиданию. Взаимные блокировки — довольно распространенная проблема при написании параллельного кода, и их следует учитывать при проектировании таких систем. Формальный набор условий для распознавания взаимных блокировок известен как условия Коффмана, о которых я рекомендую почитать.

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

К счастью, существует очень простое решение этой проблемы: мы можем нарушить симметрию задачи, заставив хотя бы одного философа начать есть, взяв сначала правую вилку. Мы можем сделать это, заставив первого философа начать с правой палочки (таким образом, мьютекс rightChopstick блокируется первым), нарушая симметрию.

Немного жаргона: взаимная блокировка (deadlock) возникает, когда два потока или процесса ждут друг друга, не достигая реального прогресса; тупик (gridlock) — то же самое, но применительно к нескольким потокам/процессам. Живая блокировка (livelock) — это когда потоки ждут друг друга, но при этом каждый из них продолжает работать самостоятельно.

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

Подводный камень №2: Голодание

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

Голодание — это еще одна проблема в конкурентных системах; однако, она более тонкая по сравнению со взаимными блокировками. Оно возникает, когда процессу постоянно отказывают в необходимых ресурсах для продолжения работы. В то время как некоторые потоки в системе прогрессируют, другие застревают в ожидании на неопределенный срок и, следовательно, «голодают».

В нашем сценарии с обедом голодание может возникнуть в следующей ситуации: представьте трех философов, сидящих рядом друг с другом: A, B и C. Если A начинает есть, он блокирует палочку между собой и B. Теперь B должен ждать, пока A закончит. Но как только A заканчивает, C (с другой стороны от B) начинает есть до того, как B получит шанс, блокируя другую палочку B. Это может произойти, например, если планировщик постоянно отдает предпочтение A и C перед «более медленным» философом B. Этот цикл может продолжаться бесконечно, что приведет к постоянному голоданию B.

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

Два известных примера — алгоритм Петерсона и алгоритм пекарни Лампорта.

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

• Алгоритм пекарни Лампорта, предложенный Лесли Лэмпортом, обобщает это на N потоков. Он работает точно так же, как люди ждут в пекарне: поток получает номер билета перед входом в критическую секцию. Поток с наименьшим номером билета получает право пройти первым. Если два потока получают один и тот же номер, их уникальный идентификатор процесса используется для разрешения ничьей. Эта система обеспечивает справедливость и свободна как от взаимных блокировок, так и от голодания.

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

Подводный камень №2.1: Модели памяти и оптимизации компилятора

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

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

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

• Модель памяти Go не является последовательно согласованной. Однако она предоставляет четкую гарантию "happens-before" (происходит до того, как), что по сути означает: если событие B было вызвано событием A, то A выполнится до B. Кроме того, примитивы из пакета sync, такие как мьютексы и каналы, создают явные точки синхронизации. При правильном их использовании гарантируется, что операции с памятью до "отправки" (например, mutex.Unlock()) будут видны операциям после соответствующего "получения" (например, mutex.Lock()). Это позволяет писать корректный параллельный код, не беспокоясь о низкоуровневых деталях переупорядочивания памяти. Если вы хотите глубже погрузиться в модель памяти Go, советую прочитать эту отличную статью из блога Laisky.

• C++ и Java также имеют слабые модели памяти. Они предоставляют такие инструменты, как std::atomic (C++) и volatile или java.util.concurrent (Java), которые позволяют программистам при необходимости накладывать более строгие ограничения на порядок операций с памятью. Однако это не является поведением по умолчанию и может привести к проблемам с производительностью при высокой нагрузке.

Русскоязычное Go сообщество

Друзья! Эту статью подготовила команда «Go for Devs» — сообщества, где мы делимся практическими кейсами, инструментами для разработчиков и свежими новостями из мира Go. Подписывайтесь, чтобы быть в курсе и ничего не упустить!

Конкурентность — это сложно, но…

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

Полный исходный код можно найти на Github.