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

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

Введение. Пишем собственный Mutex

Самым популярным примитивом синхронизации как в Go так и в других ЯП является Mutex.

Мью́текс (англ. mutex, от mutual exclusion — «взаимное исключение») — примитив синхронизации, обеспечивающий взаимное исключение исполнения критических участков кода. (Википедия)

Как реализовать? Берем пакет atomic и пишем буквально 15 строчек

type SimpleMutex struct {
	v atomic.Int32
}

func (m *SimpleMutex) Lock() {
	for {
		if m.v.CompareAndSwap(0, 1) {
			return
		}
	}
}

func (m *SimpleMutex) Unlock() {
	m.v.Store(0)
}

Пакет atomic в Go и его аналоги в других ЯП - фундамент на котором реализуются concurrency примитивы. Без него невозможно реализовывать детерминированные и конкуррентные программы, поэтому мы тоже им воспользуемся. Ссылки на доп. материалы оставлю в конце статьи.

Раунд 1. CPU задача

Протестируем реализацию на простой задачке - счетчик с которым конкурентно работают N горутин:

// реализация планируется не одна, 
// поэтому я заранее описал интерфейсы для примитивов
type MutexI interface {
	Lock()
	Unlock()
}

type WaitGroupI interface {
	Add(delta int)
	Wait()
	Done()
}

func cpuTask(mu MutexI, wg WaitGroupI, goroutines int, iterations int) int {
	var count int

	wg.Add(goroutines)
	for i := range goroutines {
		go func(id int) {
			for range iterations {
				mu.Lock()
				count++
				mu.Unlock()
			}
			wg.Done()
		}(i)
	}

	wg.Wait()

	return count
}

func main() {
	goroutines := 1000
	iterations := 10000
	
    count := cpuTask(&SpinMutex{}, &sync.WaitGroup{}, goroutines, iterations)
    fmt.Println("GOMAXPROCS=", runtime.GOMAXPROCS(0), "passed:", count == goroutines*iterations)
}

Мьютекс работает корректно, и гарантирует взаимное исключение, а что по перформансу?

Время исполнения программы при разных значения GOMAXPROCS
Время исполнения программы при разных значения GOMAXPROCS
Как собрать такие же цифры со своей программы?

go build main.go

time GOMAXPROCS=1 ./main

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

Спинлоки и ресурсное голодание

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

Почему наш код c добавлением ресурсов работае только хуже? Все дело в параллелизме. С увеличением GOMAXPROCS горутины захватывают все больше ядер процессора и вхолостую расходуют ресурс процессора. Времени на синхронизацию требуется больше чем на основную логику программы. И это классическая проблема concurrency - ресурсное голодание (starvation).

Исправляем ресурсное голодание

Основная ошибка нашей реализации - горутины очень долго держат CPU вместо того чтобы его отпустить его. Чтобы это поправить можно вставить time.Sleep в нашу реализацию и точно станет полегче (имитацию усыпления потока). Будет работать корректно, но главный минус этого решения - выбор на сколько нам засыпать. И пропорционально этому значению наша программа будет медленнее или быстрее. Поэтому мы воспользуемся runtime.Gosched() и будем делегировать планировщику эту задачу.

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

type MutexWithPause struct {
	v atomic.Int32
}

func (m *MutexWithPause) Lock() {
	for {
		if m.v.CompareAndSwap(0, 1) {
			return
		}
		runtime.Gosched()
	}
}

func (m *MutexWithPause) Unlock() {
	m.v.Store(0)
}

И снова запустим нашу программу со счетчиком.

Результаты запуска программы с Gosched
Результаты запуска программы с Gosched

Видим что ресурсное голодание улетучилось и программа работает лучше.

Битва "велосипеда" и эталонной реализации

Попробуем оценить насколько быстрее или медленнее наша реализация по сравнению с sync.Mutex из стандартной библиотеки.

Sync.Mutex
Sync.Mutex
Gosched
Gosched

Программа с самописным мьютексом работает быстрее чем со стандартным. В чем причина? Sync.Mutex в отличии от нашей реализации взаимодействует с примитивами операционной системы и можно увидеть рост system time с ростом GOMAXPROCS.

Выглядит так что самое время делать contribution в гошку, или нет? :)

Раунд 2. I/O задача

А что если добавить в наш код паузу? Изменится ли результат или останется прежним? Для ускорения тестирования уменьшу количество горутин и итераций.

  • Горутин - 100

  • Итераций - 100

Итого: Эмулируем через time.Sleep I/O профиль нагрузки.

func ioTask(mu MutexI, wg WaitGroupI, goroutines int, iterations int) int {
	var count int

	wg.Add(goroutines)
	for i := range goroutines {
		go func(id int) {
			for range iterations {
				mu.Lock()

				count++
				time.Sleep(time.Millisecond) // Единственное отличие - эмулируем IO через принудительную паузу

				mu.Unlock()
			}
			wg.Done()
		}(i)
	}

	wg.Wait()

	return count
}

Результаты:

Gosched
Gosched
Sync Mutex
Sync Mutex

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

Выводы

Несмотря на то что в заметке есть тест в котором четко видно, что велосипед победил стандартную реализацию не стоит делать вывод о том что такой подход можно без оглядки и последствий затащить в production. Как мы увидели, со сменой профиля нагрузки эффективность нашей программы очень снизилась. В этом и есть магия реализации стандартных библиотек - она работает нормально при любой погоде :). В следующей части попробуем избавиться от недостатков нашей самопальной реализации, которые проявились на IO задаче.

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

Например в POSIX есть отдельная реализация спинлоков и ее можно использовать не велосипедируя собственную.

Если вам интересна тема конкурентноого программирования я приглашаю вас в свой Telegram. В прошлом году сделал большой цикл постов о том как concurrency работает на всех уровнях, начиная с железа и заканчивая виртуальными потоками языков программирования - CPU, Memory Models, Concurrency, Multiprocess, Multithreading и Async

В этом году я пишу продолжение - Concurrency, Synchronization and Consistency - о том как писать корректные и детерминированные конкурентные программы.

Большое спасибо что дочитали до конца, делитесь обратной связью в комментариях.