Sitemap

Open in app

Write

German Gorelkin

·
Follow publication

Research and Development

Follow publication

Top highlight

Deadlocks, Livelocks и Starvation

German Gorelkin

Follow

6 min read
·
Jan 27, 2020

41

2

Share

More

Продолжаем серию статей о проблемах многопоточности, параллелизме, concurrency и других интересных штуках.

Race condition и Data Race

Deadlocks, Livelocks и Starvation

Примитивы синхронизации в Go

Безопасная работа с каналами в Go

Goroutine Leaks

Deadlocks, Livelocks и Starvation

Продолжаем серию статей о проблемах многопоточности, параллелизме, concurrency и других интересных штуках. Race…

ubiklab.net

В 1965 году Эдсгер Дейкстра сформулировал задачу об обедающих философах. Задача была иллюстрацией проблем синхронизации при разработке параллельных алгоритмов и техник решения этих проблем.

В задачи были рассмотренный такие проблема, как deadlock, livelock, resource starvation.

Дейкстра, Эдсгер Вибе

Саму задачу и возможные решения можно посмотреть на wiki.

А мы рассмотрим проблемы синхронизации в контексте современных языков программирования.

Deadlock

fatal error: all goroutines are asleep - deadlock!

Что такое deadlock и как избежать таких ошибок?

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

Zoom image will be displayed

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

Пример

play.golang

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
}

Zoom image will be displayed

Zoom image will be displayed

fatal error: all goroutines are asleep — deadlock!

Отладка взаимных блокировок, как и других ошибок синхронизации, усложняется тем, что для их возникновения нужны специфические условия одновременного выполнения нескольких процессов. Если бы Процесс 1 успел захватить ресурс B до Процесса 2, то ошибка не произошла бы.

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

Zoom image will be displayed

https://www.cs.columbia.edu/~coffman/

Условия Коффмана

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

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

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

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

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

Диаграммы Холта (Holt).

Отслеживать возникновение взаимных блокировок удобно на диаграммах Холта (Holt). Диаграмма Холта представляет собой направленный граф, имеющий два типа узлов: процессы (показываются кружочками) и ресурсы (показываются квадратиками). Тот факт, что ресурс получен процессом и в данный момент занят этим процессом, указывается ребром (стрелкой) от ресурса к процессу. Ребро, направленное от процесса, к ресурсу, означает, что процесс в данный момент блокирован и находится в состоянии ожидания доступа к соответствующему ресурсу.

Критерий deadlock.

Deadlock имеет место быть, тогда и только тогда, когда диаграмма Холта, отражающая состояния процессов и ресурсов, содержит цикл.

Livelock

Livelock- это программы, которые активно выполняют параллельные операции, но эти операции никак не влияют на продвижение состояния программы вперед.

Ситуация, в которой два или более процессов непрерывно изменяют свои состояния в ответ на изменения в других процессах без какой-либо полезной работы. Это похоже на deadlock, но разница в том, что процессы становятся “вежливыми” и позволяют другим делать свою работу.

Выполнение алгоритмов поиска удаления взаимных блокировок может привести к livelock — взаимная блокировка образуется, сбрасывается, снова образуется, снова сбрасывается и так далее.

Жизненный пример такой ситуации:

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

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

Рассмотрим простой пример livelock, где муж и жена пытаются поужинать, но между ними только одна ложка. Каждый из супругов слишком вежлив, и передает ложку, если другой еще не ел.

play.golang

Ложка у которой есть хозяин:

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

Zoom image will be displayed

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.

На сегодня все. Спасибо!

Дополнительная информация

Concurrency in Go. by Katherine Cox-Buday

https://ru.wikipedia.org/wiki/Взаимная_блокировка

https://github.com/GermanGorelkin/go-patterns/tree/master/concurrency/problems/deadlocks-livelocks-and-starvation

Golang

Go

Software Development

Coding

Programming

41

41

2

Follow

Published in German Gorelkin

112 followers

·Last published Oct 21, 2023

Research and Development

Follow

Follow

Written by German Gorelkin

301 followers

·11 following

https://ubiklab.net/

Follow

Responses (2)

Kosha's thoughts

What are your thoughts?

Cancel
Respond

V N Sankov

Jan 18, 2022

много орфографических ошибок(

Reply

Konstantin Bezdetniy

Jul 9, 2021

Отличная серия статей!

Reply

More from German Gorelkin and German Gorelkin

In

German Gorelkin

by

German Gorelkin

Low Coupling и High Cohesion

Качественный дизайн обладает слабой связанностью (low coupling) и сильной связностью (high cohesion). Это значит, что программный…

Sep 24, 2019

428

4

In

German Gorelkin

by

German Gorelkin

Embedding в Go

Go предлагает механизм встраивания(embedding) в качестве альтернативы механизму наследования в традиционных объектно-ориентированных…

Oct 4, 2018

34

1

In

German Gorelkin

by

German Gorelkin

Gossip Protocol. Часть 1

Gossip (сплетник) — это группа протоколов в одноранговой компьютерной коммуникации, в которых распространение информации идёт способом…

Sep 28, 2023

In

German Gorelkin

by

German Gorelkin

Примитивы синхронизации в Go

Пакет sync содержит примитивы, которые наиболее полезны для низкоуровневой синхронизации доступа к памяти. WaitGroup. Mutex. RWMutex. Cond.

Feb 9, 2020

58

1

See all from German Gorelkin

See all from German Gorelkin

Recommended from Medium

Abhinav

Go Just Fixed Its Biggest Flaw — Quietly

If you’ve written real-world code in Go, you already know the pain.

Jul 24

302

6

Leapcell

Go’s Last Words on Error Handling Syntax

After three failed attempts, Go team confirms no future error handling syntax changes, focusing on tooling improvements.

Jul 20

83

4

Sohail Saifi

Why Japanese Developers Write Code Completely Differently (And Why It Works Better)

For the past three years, I have delved into the software development landscape in Japan, and one of the things I learned completely…

Jul 17

10.6K

277

Ömer Burak Demirpolat

Go Interfaces: When to Use Them and When to Skip Them

In this article, I will attempt to briefly answer the question of when to use an interface.

Jul 21

10

In

Stackademic

by

Pudari Madhavi

Writing != null? That’s What Junior Devs Do. Here’s the Senior Way!

If you’ve been working with Java for a while, chances are high that your codebase is littered with this little phrase: != null.

Jul 19

599

35

Quantum Anomaly

Decoding Redis

Redis (REmote DIctionary Server) is an open-source, in-memory, key-value data store, often used as a cache, message broker, real-time…

Jun 13

4

1

See more recommendations

Help

Status

About

Careers

Press

Blog

Privacy

Rules

Terms

Text to speech