Пора перейти от уровня ОС и низкоуровневых примитивов поближе к реальным задачам и челленджам. Сегодня нестареющая классика - задача о философах.
Пять философов сидят вокруг круглого стола, перед каждым стоит тарелка спагетти. На столе между каждой парой ближайших философов лежит по одной вилке.
Каждый философ может либо есть, либо размышлять. Приём пищи не ограничен количеством оставшихся спагетти — подразумевается бесконечный запас. Тем не менее, философ может есть только тогда, когда держит две вилки — взятую справа и слева.
Каждый философ может взять ближайшую вилку (если она доступна) или положить — если он уже держит её. Взятие каждой вилки и возвращение её на стол являются раздельными действиями, которые должны выполняться одно за другим.
Задача: разработать алгоритм, при котором ни один из философов не будет голодать, то есть будет вечно чередовать приём пищи и размышления.
🔵 Наивная реализация
Предлагаю сначала ничего не выдумывать, а просто закодировать то что первым приходит в голову.
Go Playground
package main
import (
"fmt"
"sync"
)
func main() {
const philosophers = 5
forks := make([]sync.Mutex, philosophers)
for p := range philosophers {
go philosopher(p, &forks[p], &forks[(p+1)%philosophers])
}
quit := make(chan struct{})
<-quit
}
func philosopher(p int, left *sync.Mutex, right *sync.Mutex) {
for {
left.Lock()
right.Lock()
fmt.Println("Philosopher", p, "Eating...")
left.Unlock()
right.Unlock()
fmt.Println("Philosopher", p, "ate :)")
}
}
Не самый сложный код. Но есть загвоздка - он неправильный. Вилок столько же сколько и философов и когда каждый хватает левую то на столе не остается вилок. Программа зависла навсегда. Конец. У этой проблемы даже есть название - взаимная блокировка.
Попробуем не вникая в глубокие теоретические рассуждения и алгоритмы решить задачу так как бы мы ее решали в реальной жизни.
🔵 Просим философов быть менее предсказуемыми
Чтобы устранить голодовую смерть можно изменить порядок взятия вилок со стола. Но не для всех философов одновременно, а например для одного. Этого будет достаточно.
Полный код: Go Playground
func philosopher(p int, left *sync.Mutex, right *sync.Mutex) {
for {
if p == 4 {
right.Lock()
left.Lock()
} else {
left.Lock()
right.Lock()
}
fmt.Println("Philosopher", p, "Eating...")
time.Sleep(time.Millisecond)
left.Unlock()
right.Unlock()
fmt.Println("Philosopher", p, "ate :)")
}
}🔵Добавляем официанта
Вместо того чтобы вносить хак в программу и делать поведение участников непохожим на остальных можно добавить помощника - официанта.
Это классический пример синхронизации через семафор. Каждый философ перед тем как хвататься за вилки просит разрешения у официанта. Если он принял запрос, значит доступ к вилкам есть у 3х или менее философов, а значит мы не попадем во взаимную блокировку.
Полный код: Go Playground
steward := make(chan int, philosophers-1)
...
func philosopher(p int, left *sync.Mutex, right *sync.Mutex, steward chan int) {
for {
steward <- p
left.Lock()
right.Lock()
fmt.Println("Philosopher", p, "Eating...")
time.Sleep(time.Millisecond)
left.Unlock()
right.Unlock()
<-steward
fmt.Println("Philosopher", p, "ate :)")
}
}
🔵 Итоги
В несколько этапов мы прошли путь от решения в лоб к двум корректным:
- с хаком в коде (у него есть название, кто знает пишите в комментарии)
- c семафором.
При этом не был рассмотрен вопрос - как реализовать справедливое решение, чтобы все кушали одинаково? Ставьте 🔥, если увижу ваш интерес - обязательно рассмотрим и этот вопрос.
На этом всё, буду рад вашей ОС и реакциям, особенно интересно - был ли пост понятен без предварительной теории. Её могло быть много, но я осознанно сфокусировался на практике😇
📖 Оглавление