Продолжаем серию статей о проблемах многопоточности, параллелизме, concurrency и других интересных штуках.
- Race condition и Data Race
- Deadlocks, Livelocks и Starvation
- Примитивы синхронизации в Go
- Безопасная работа с каналами в Go
- Goroutine Leaks
В 1965 году Эдсгер Дейкстра сформулировал задачу об обедающих философах. Задача была иллюстрацией проблем синхронизации при разработке параллельных алгоритмов и техник решения этих проблем.
В задачи были рассмотренный такие проблема, как deadlock, livelock, resource starvation.
Саму задачу и возможные решения можно посмотреть на wiki.
А мы рассмотрим проблемы синхронизации в контексте современных языков программирования.
Deadlock
fatal error: all goroutines are asleep - deadlock!
Что такое deadlock и как избежать таких ошибок?
Deadlock или взаимная блокировка — это ошибка, которая происходит когда процессы имеют циклическую зависимость от пары синхронизированных объектов.
Deadlock — это программа, в которой все параллельные процессы ожидают друг друга. В этом состоянии программа никогда не восстановится без вмешательства извне.
Пример
func main() {
var wg sync.WaitGroup
printSum := func(v1, v2 *value) {
defer wg.Done()
v1.mu.Lock() // Процесс 1 блокирует А; Процесс 2 блокирует B
defer v1.mu.Unlock()
time.Sleep(2 * time.Second)
v2.mu.Lock() // Процесс 1 ожидает B; Процесс 2 ожидает А
defer v2.mu.Unlock()
fmt.Printf("sum=%v\n", v1.value+v2.value)
}
var a, b value
wg.Add(2)
go printSum(&a, &b) // Процесс 1
go printSum(&b, &a) // Процесс 2
wg.Wait()
}
type value struct {
mu sync.Mutex
value int
}
fatal error: all goroutines are asleep — deadlock!
Отладка взаимных блокировок, как и других ошибок синхронизации, усложняется тем, что для их возникновения нужны специфические условия одновременного выполнения нескольких процессов. Если бы Процесс 1 успел захватить ресурс B до Процесса 2, то ошибка не произошла бы.
Но все не так плохо, оказывается, есть несколько условий, которые должны присутствовать для возникновения взаимных блокировок, и в 1971 году Эдгар Коффман перечислил эти условия в своей статье System Deadlocks. Условия теперь известны как условия Кофмана и являются основой для методов, которые помогают обнаруживать, предотвращать и исправлять взаимные блокировки.
Условия Коффмана
-
Условие взаимного исключения. Каждый ресурс в данный момент или отдан ровно одному процессу, или доступен.
-
Условие удержания и ожидания. Процессы, в данный момент удерживающие полученные ранее ресурсы, могут запрашивать новые ресурсы.
-
Условие отсутствия принудительной выгрузки ресурса. У процесса нельзя принудительным образом забрать ранее полученные ресурсы. Процесс, владеющий ими, должен сам освободить ресурсы.
-
Условие циклического ожидания. Должна существовать круговая последовательность из двух и более процессов, каждый из которых ждет доступа к ресурсу, удерживаемому следующим членом последовательности.
Указанные условия являются необходимыми. То есть, если хоть одно из них не выполняется, то взаимных блокировок никогда не возникнет. Достаточность не имеет места быть: если выполняются все четыре условия, блокировка может и не произойти, например, если в системе нет процессов, претендующих на одновременное использование одних и тех же ресурсов.
Диаграммы Холта (Holt).
Отслеживать возникновение взаимных блокировок удобно на диаграммах Холта (Holt). Диаграмма Холта представляет собой направленный граф, имеющий два типа узлов: процессы (показываются кружочками) и ресурсы (показываются квадратиками). Тот факт, что ресурс получен процессом и в данный момент занят этим процессом, указывается ребром (стрелкой) от ресурса к процессу. Ребро, направленное от процесса, к ресурсу, означает, что процесс в данный момент блокирован и находится в состоянии ожидания доступа к соответствующему ресурсу.
Критерий deadlock
Deadlock имеет место быть, тогда и только тогда, когда диаграмма Холта, отражающая состояния процессов и ресурсов, содержит цикл.
Livelock
Livelock- это программы, которые активно выполняют параллельные операции, но эти операции никак не влияют на продвижение состояния программы вперед.
Ситуация, в которой два или более процессов непрерывно изменяют свои состояния в ответ на изменения в других процессах без какой-либо полезной работы. Это похоже на deadlock, но разница в том, что процессы становятся “вежливыми” и позволяют другим делать свою работу.
Выполнение алгоритмов поиска удаления взаимных блокировок может привести к livelock — взаимная блокировка образуется, сбрасывается, снова образуется, снова сбрасывается и так далее.
Жизненный пример такой ситуации:
Двое встречаются лицом к лицу. Каждый из них пытается посторониться, но они не расходятся, а несколько секунд сдвигаются в одну и ту же сторону.
Вы делаете телефонный звонок, но человек на другом конце тоже пытается вам позвонить. Вы оба повесите трубку и попробуйте снова через одно и то же время, что снова создаст такую же ситуацию. Это может продолжаться вечность.
Рассмотрим простой пример livelock, где муж и жена пытаются поужинать, но между ними только одна ложка. Каждый из супругов слишком вежлив, и передает ложку, если другой еще не ел.
Ложка у которой есть хозяин:
type spoon struct {
owner *diner
}
func (s spoon) use(){
fmt.Printf("%s has eaten!\n", s.owner.name)
}
type diner struct{
name string
isHungry bool
}
Процесс обеда. Ложка и партнер:
func (d *diner) eatWith(sp *spoon, spouse *diner) {
for d.isHungry {
// 1
if sp.owner != d {
time.Sleep(1 * time.Second)
continue
}
// 2
if spouse.isHungry {
fmt.Printf("%s: You eat first my darling %s!\n", d.name, spouse.name)
sp.owner = spouse
continue
}
// 3
sp.use()
d.isHungry = false
fmt.Printf("%s: I'm stuffed? my darling %s!\n", d.name, spouse.name)
sp.owner = spouse
}
}
Обедаем пока не утолим голод(isHungry=false).
- Если ложка сейчас не у нас, то подождем
- Если супруг(а) голодна, то уступим и передадим ложку ему/ей
- Используем ложку и наконец-то обедаем
Поесть этим им не суждено. До третьего блока выполнение не дойдет
На мой взгляд, обнаружить livelock труднее, чем deadlock, просто потому, что может показаться, что программа работает. Она может реагировать на сигналы, потреблять ресурсы и как то менять состояния, но выйти из цикла и завершить работу уже не в состоянии.
Livelock— это подмножество более широкого набора проблем, называемых Starvation.
Starvation
Starvation — это любая ситуация, когда параллельный процесс не может получить все ресурсы, необходимые для выполнения его работы.
При livelock все параллельные процессы одинаково “голодают”, и никакая работа не выполняется до конца.
В более широком смысле starvation обычно подразумевает наличие одного или нескольких параллельных процессов, которые несправедливо мешают одному или нескольким другим параллельным процессам выполнять работу настолько эффективно, насколько это возможно.
Пример
У нас будет два работника. Один жадный(greedyWorker), другой вежливый(politeWorker). Обоим дается одинаковое кол-во времени на их полезную работу — спать по 3 наносекунде.
greedyWorker жадно удерживает общий ресурс(sharedLock) на протяжении всего цикла работы, тогда как politeWorker пытается блокировать его только тогда, когда это необходимо.
greedyWorker := func() {
defer wg.Done()
var count int
for begin := time.Now(); time.Since(begin) <= runtime; {
sharedLock.Lock()
time.Sleep(3 * time.Nanosecond)
sharedLock.Unlock()
count++
}
fmt.Printf("Greedy worker was able to execute %v work loops.\n", count)
}
politeWorker := func() {
defer wg.Done()
var count int
for begin := time.Now(); time.Since(begin) <= runtime; {
sharedLock.Lock()
time.Sleep(1 * time.Nanosecond)
sharedLock.Unlock()
sharedLock.Lock()
time.Sleep(1 * time.Nanosecond)
sharedLock.Unlock()
sharedLock.Lock()
time.Sleep(1 * time.Nanosecond)
sharedLock.Unlock()
count++
}
fmt.Printf("Polite worker was able to execute %v work loops.\n", count)
}
Greedy worker was able to execute 14111 work loops.
Polite worker was able to execute 33301 work loops.
За одно и то же время, жадный работник получил почти вдвое больше возможностей выполнять свою работу и владеть общим ресурсом.
Конечно, lock\unlock медленные и в данном примере у politeWorker очень неэффективный код, но голодания может также применяться к процессору, памяти, файловым дескрипторам, соединениям с бд, к любому ресурсу, который должен использоваться совместно.
Если у вас есть параллельный процесс, который настолько жаден, что препятствует эффективно работать другим параллельным процессам, то у вас большая проблема.
Код примеров github.