Синхронизация в Go с использованием примитивов параллелизма - пример из практики

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

1. Рутины и каналы
2. Примитивы, представленные в пакете sync, такие как sync.Map, sync.Mutex, sync.Cond и sync.WaitGroup.

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

Проблема

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

package main
import (
    "fmt"
    "time"
)
func main() {
    waitChan := make(chan bool)
    
    go func()  {
        var i int  = 1
        
        for true {
            fmt.Printf("%d\n", i)
            i += 3
            time.Sleep(time.Duration(1)*time.Second)
        }    
    }()
    
    go func()  {
        var i int  = 2
        
        for true {
            fmt.Printf("%d\n", i)
            i += 3
            time.Sleep(time.Duration(1)*time.Second)
        }
    }()
    
    go func()  {
        var i int  = 3
        
        for true {
            fmt.Printf("%d\n", i)
            i += 3
            time.Sleep(time.Duration(1)*time.Second)
        }
    }()
    
    <-waitChan
}

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

1. Первый выводит последовательность 1,4,7,…
2. Второй печатает последовательность 2, 5, 8,…
3. Третий печатает последовательность 3, 6, 9,…

Вот ссылка на код на игровой площадке Go. Если вы запустите его, вы увидите, что числа печатаются без определенного порядка.

Вот пример вывода.

3
2
1
5
4
6
8
9
7
12
...

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

Проблема в том, как вы синхронизируете рутинные операции, чтобы они выводили числа в правильном порядке в следующем порядке: 1,2,3,4,5…?

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

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

Решение №1 - Использование нескольких каналов

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

package main
import (
    "fmt"
    "time"
)
func main() {
    waitChan := make(chan bool)
    a := make(chan bool)
    b := make(chan bool)
    c := make(chan bool)
    
    go func()  {
        var i int  = 1
        
        for true {
            <-a
            fmt.Printf("%d\n", i)
            i += 3
            b<- true
            time.Sleep(time.Duration(1)*time.Second)
        }    
    }()
    
    go func()  {
        var i int  = 2
        
        for true {
            <-b
            fmt.Printf("%d\n", i)
            i += 3
            c <- true
            time.Sleep(time.Duration(1)*time.Second)
        }
    }()
    
    go func()  {
        var i int  = 3
        
        for true {
            <-c
            fmt.Printf("%d\n", i)
            i += 3
            a <- true
            time.Sleep(time.Duration(1)*time.Second)
        }
    }()
    a <- true // Kick things off
    <-waitChan
}

(Вот ссылка на код для игровой площадки Go)

Вы можете запустить код, скопировав и вставив его в локальном редакторе и в цепочке инструментов, или непосредственно на игровой площадке Go. Вы можете видеть, что он печатает числа в последовательности, как и ожидалось. Как это работает ?

Вот логика, объясненная по шагам.

1. Создаем три небуферизованных канала типа bool.
2. Мы создаем циклическую зависимость между процедурами, используя каналы.

• подпрограмма №1 ожидает на канале a и записывает на канал b
• подпрограмма № 2 ожидает на канале b и записывает на канал c
• подпрограмма № 3 ожидает на канале c и записывает на канал a

Отношения можно представить как

Вовлеченные взаимодействия:

1. go-подпрограмма №1 ожидает на канале a - канал a блокирует ее выполнение. В свою очередь, он блокирует рутину №2 через канал b.
2. go-подпрограмма №2 ожидает на канале b - канал b блокирует ее выполнение. В свою очередь, блокирует обычную процедуру №3 через канал c.
3. go-подпрограмма №3 ожидает на канале c - канал c блокирует ее выполнение. В свою очередь, он блокирует рутину №1 через канал a.

Следовательно, изначально система находится в тупиковом состоянии из-за этой циклической зависимости, вводимой через взаимозависимость каналов и программ. Мы нарушаем тупиковую блокировку и начинаем работу, записывая в канал a, который содержит статистику процедуры №1, который, в свою очередь, записывает в b и запускает процедуру №2, которая, в свою очередь, записывает в c и запускает процедуру №3. которые, в свою очередь… и выключаются, они входят в предсказуемый цикл, и теперь у нас есть синхронизированная система, которая будет выполнять подпрограммы в порядке 1,2,3,1,2,3,… и, следовательно, производить именно тот результат, который мы хотим.

Тупик

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

// Comment this line out and introduce a deadlock
// a <- true

Если вы попытаетесь запустить код, вы увидите что-то вроде следующего вывода (вывод через Go Playground)

fatal error: all goroutines are asleep - deadlock!

goroutine 1 [chan receive]:
main.main()
	/tmp/sandbox2063175924/prog.go:53 +0x17e

goroutine 34 [chan receive]:
main.main.func1()
	/tmp/sandbox2063175924/prog.go:20 +0x3b
created by main.main
	/tmp/sandbox2063175924/prog.go:16 +0xbd

Давайте теперь посмотрим, как использовать примитивы из пакета sync для решения этой проблемы. Сначала мы рассмотрим решение, используя настоящий sync.Map.

Решение №2 - Использование sync.Map

Пакет sync предоставляет примитив Map, который похож на традиционный map, но является потокобезопасным.

Примитив sync.Map предоставляет методы Store, Load и Delete соответственно для размещения, получения и удаления пар ключ / значение с карты.

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

package main
import (
    "fmt"
    "sync"
    "time"
)
// Wait for a key to appear on the syncMap
func waitSync(syncMap *sync.Map, key string) {
    for true {
        if _, ok := syncMap.Load(key); ok {
            syncMap.Delete(key)
            break
        } else {
            time.Sleep(time.Duration(1) * time.Second)
        }
    }
}
func main() {
    var syncMap sync.Map
    waitChan := make(chan bool)
    go func() {
        var i int = 1
        for true {
            waitSync(&syncMap, "a")
            fmt.Printf("%d\n", i)
            i += 3
            syncMap.Store("b", true)
        }
     }()
    go func() {
        var i int = 2
        for true {
            waitSync(&syncMap, "b")
            fmt.Printf("%d\n", i)
            i += 3
            syncMap.Store("c", true)
        }
    }()
    go func() {
        var i int = 3
        for true {
            waitSync(&syncMap, "c")
            fmt.Printf("%d\n", i)
            i += 3
            syncMap.Store("a", true)
        }
    }()
    syncMap.Store("a", true) // Kick-start things
    <-waitChan
}

(Вот ссылка на код на игровой площадке Go)

Вот как работает код, по шагам.

1. sync.Map с именем syncMap используется в трех программах.
2. Функция waitSync ожидает на карте появления клавиши в цикле for, засыпая каждую секунду. Как только ключ найден, он удаляет ключ и выходит из цикла.
3. Циклическая зависимость между go-подпрограммами достигается ожиданием ключей с именами a, b и c на syncMap и сохранением ключей b, c и a соответственно тремя go-подпрограммами.
4. Мы начинаем с сохранения ключа a в syncMap. Это пробуждает go-подпрограмму # 1, которая затем распечатывает свой вывод и сохраняет ключ b на syncMap, который пробуждает go-процедуру # 2, которая распечатывает свой вывод и сохраняет ключ c на карте, которая, в свою очередь, пробуждает go-подпрограмму # 3, который выполняет свою работу и сохраняет ключ a на карте ... цикл повторяется, и действия синхронизируются.

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

Богатство, предлагаемое пакетом sync, на этом не заканчивается. Используя примитивы в этом пакете, есть по крайней мере еще несколько способов решить эту проблему. В этой статье я расскажу еще о двух.

Решение №3 - Использование объектов Condition

В пакете синхронизации есть объект Cond. Источником вдохновения для этого послужили исходные условия потоков POSIX, которые являются частью спецификации потоков POSIX (pthreads).

Объекты условия включают мьютекс (блокировку). Он поддерживает в основном следующие методы.

1. Подождите - это вызывается для объекта условия, мьютекс которого заблокирован. Он разблокирует мьютекс и ожидает (приостанавливает выполнение) вызывающей подпрограммы, пока она не проснется (см. Ниже).
2. Сигнал - этот метод пробуждает ровно одну (случайную) подпрограмму, ожидающую объекта условия.
3. Широковещательная рассылка - этот метод пробуждает все подпрограммы, ожидающие выполнения объекта условия.

Объект условия обычно используется в go-подпрограммах для синхронизации с определенным событием (или состоянием), которое должно быть достигнуто при их обработке. Ожидающие подпрограммы блокируют это (будущее) состояние, вызывая Wait для объекта условия - при этом обычно проверяя в цикле, было ли достигнуто состояние.

Как только состояние будет достигнуто, отдельный поток (обычно поток main или процедура перехода) будет активировать одну или все подпрограммы перехода, заблокированные по условию, путем вызова Signal или Broadcast соответственно.

Объект Condition является примитивом низкого уровня и обычно не используется в наши дни (за исключением, возможно, старых программистов, выросших на диете C и Unix, как автор!), Но он обеспечивает интересное решение этой проблемы.

package main
import (
    "fmt"
    "time"
    "sync"
)
func main() {
    waitChan := make(chan bool)
    a := sync.NewCond(new(sync.Mutex))
    b := sync.NewCond(new(sync.Mutex))
    c := sync.NewCond(new(sync.Mutex))
    go func()  {
        var i int  = 1
        
        for true {
            a.L.Lock()
            a.Wait()
            a.L.Unlock()
            fmt.Printf("%d\n", i)
            i += 3
        }    
    }()
    
    go func()  {
        var i int  = 2
        for true {
            b.L.Lock()         
            b.Wait()
            b.L.Unlock()           
            fmt.Printf("%d\n", i)
            i += 3
        }
    }()
    
    go func()  {
        var i int  = 3
        for true {
            c.L.Lock()
            c.Wait()
            c.L.Unlock()           
            fmt.Printf("%d\n", i)
            i += 3
        }
    }()
    for true {
        time.Sleep(time.Duration(1)*time.Second)        
        a.Signal()
        time.Sleep(time.Duration(1)*time.Second)
        b.Signal()
        time.Sleep(time.Duration(1)*time.Second)
        c.Signal()
    }
    
    <-waitChan
}

(Вот ссылка на код на игровой площадке Go)

Вот что происходит в этом коде.

1. Мы используем три объекта условий, а именно a, b и c - по одному для каждой процедуры.
2. В этом случае нет циклической зависимости между выполняемыми процедурами. С другой стороны, каждый объект состояния начинает свою жизнь заблокированным и ожидающим пробуждения.
3. Основная функция (go-подпрограмма) после настройки всего продолжает пробуждать объекты состояния - и тем самым их блокирующие подпрограммы перехода одну за другой в цикле, специально вызывая Signal для соответствующих объектов состояния.
4. Подпрограммы go просыпаются, печатают свой номер и возвращаются к блокировке и ожиданию своих объектов состояния, пока они снова не проснутся в следующей итерации цикла for.

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

Теперь давайте завершим этот пример, рассмотрев окончательный подход с использованием другого sync примитива пакета, а именно WaitGroup.

Решение №4 - Использование sync.WaitGroup

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

Хороший способ думать о WaitGroup - это что-то вроде счетчика на финише беговой гонки.

1. Группа бегунов, количество которых известно (скажем «n»), начинает забег.
2. Они соревнуются друг с другом и приходят к финишу в разное время.
3. Забег считается завершенным только после того, как последний бегун пересечет финишную черту.

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

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

WaitGroup предоставляет следующие методы.

1. Добавить - увеличивает счетчик группы ожидания на переданное значение.
2. Подождите - любая подпрограмма, вызывающая этот метод, будет блокироваться в группе ожидания до тех пор, пока ее счетчик не станет равным нулю. (Это ошибка, если счетчик уже равен нулю или меньше).
3. Готово - уменьшает счетчик групп ожидания на единицу. Обычно это вызывается после того, как ожидание завершено и рутина выполнила свою работу.

Вот решение с использованием групп ожидания.

package main
import (
    "fmt"
    "time"
    "sync"
)
func main() {
    var a sync.WaitGroup
    var b sync.WaitGroup  
    var c sync.WaitGroup
    
    waitChan := make(chan bool)
    a.Add(1)
    b.Add(1)
    c.Add(1)
    
    go func()  {
        var i int  = 1
        
        for true {
            a.Wait()
            a.Add(1)
            fmt.Printf("%d\n", i)
            time.Sleep(time.Duration(1)*time.Second)                        
            b.Done()
            
            i += 3
        }    
    }()
    
    go func()  {
        var i int  = 2
        for true {
            b.Wait()
            b.Add(1)          
            fmt.Printf("%d\n", i)
            time.Sleep(time.Duration(1)*time.Second)                        
            c.Done()
            
            i += 3          
        }
    }()
    
    go func()  {
        var i int  = 3
        for true {
            c.Wait()
            c.Add(1)          
            fmt.Printf("%d\n", i)
            time.Sleep(time.Duration(1)*time.Second)                        
            a.Done()
            
            i += 3                      
        }
    }()
    a.Done() // Kick things off !
    <-waitChan
}

(Вот ссылка на код на игровой площадке Go)

Как это работает ? Вот пошаговое руководство.

1. Мы создаем три WaitGroup экземпляра - по одному для каждой процедуры. Мы инициализируем их счетчики на единицу, вызывая Add(1) для каждого из них.
2. Подпрограммы начинают свою жизнь с ожидания соответствующих групп ожидания. Затем они добавляют один обратно в счетчик и продолжают печатать свои значения и немного спят.
3. Как только их работа сделана, они вызывают Done в группу ожидания, которую ожидает следующая процедура выполнения. Это создает циклическую зависимость между процедурами.
4. Первоначально все подпрограммы зашли в тупик, поскольку они ожидают в группах ожидания, счетчик которых ›равен нулю.
5. Мы запускаем процесс, вызывая Done в первой группе ожидания a, которая уменьшает счетчик до нуля.
6. Это вызывает пробуждение подпрограммы №1, которая добавляет один к себе и выполняет свою работу, распечатывая его значение. Затем он пробуждает подпрограмму № 2, вызывая Done в своей группе ожидания b, которая затем выполняет аналогичные действия и, в свою очередь, пробуждает подпрограмму № 3, вызывая выполнение на c, которая, в свою очередь, пробуждает подпрограмму № 1. … Это продолжается и продолжается.

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

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

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