В прошлых постах мы разобрались, что из себя представляет термин lock-free. На очереди финальный босс - wait-free. Как всегда начинаем с определения:
Гарантия Wait-free - каждый поток завершает операцию за ограниченное число шагов, независимо от того, что делают другие потоки.Вспоминаем написанные ранее lock-free stack и queue. Попадают ли они под определение? Конечно нет. В коде операций вставки и чтения присутствуют бесконечные циклы - о предсказуемости речи быть не может.
🔵 Атомарный счетчик как пример wait-free кода
Базовый пример кода соответствующего гарантии wait-free это связка Atomic Int и операция Add:
type Counter struct {
value atomic.Int64
}
func (c *Counter) Add(delta int64) int64 {
return c.value.Add(delta)
}
func (c *Counter) Load() int64 {
return c.value.Load()
}Почему это wait-free: под капотом одна аппаратная инструкция (LOCK XADD на x86) и как следствие никаких циклов.
Без аппаратной поддержки нам бы пришлось писать что-то вроде:
type Counter struct {
value atomic.Int64
}
func (c *Counter) Add(delta int64) int64 {
for {
old := c.value.Load()
newVal := old + delta
if c.value.CompareAndSwap(old, newVal) {
return newVal
}
}
}
func (c *Counter) Load() int64 {
return c.value.Load()
}Как мы видим - снова бесконечный цикл и никакой предсказуемости😁
🔵 Продвинутые примеры Wait-Free алгоритмов
На самом деле тут ситуация двоякая. Есть 2 лагеря:
- Исследователи, ищущие универсальные пути построения алгоритмов без ожидания.
- Практики, создающие реальный софт.
И вот как я понимаю - пересечений маловато. Потому что практики обычно достигают wait-freedom в своих программах за счет явного проектирования и подстраивания под железо. По сути пишут код именно так чтобы конкуренции не было в принципе. И поэтому их программы тоже получаются wait-free.
То что придумывают теоретики это очень общие алгоритмы, которые сложно встроить полностью "с листа" в программу. Только выборочно, какие то конкретные идеи в конкретное место. Я сколько не ресерчил не нашел примеров чистых wait-free структур данных в проде (как например с lock-free). Обычно это были гибриды (wait-free на чтение / lock-free или вообще mutex на запись)
Например: упомянутый выше wait-free счетчик только по семантике wait-free, алгоритмически. А вот на практике с ростом количества ядер и потоков он будет работать все хуже и хуже (вспоминаем посты про синхронизацию кешей CPU). Отсюда и растут ноги у "шардируемых по количеству потоков счетчиков".
🔵 Wait-Free в реальном мире
Лучший пример из реальности который мне приходит в голову - обработка аудио в реальном времени. Если мы в программе работающем со звуком будем писать код без осознания дедлайнов то слушать музыку с комфортом будет невозможно😁
Если интересно почитать об этом подробнее - Real-time audio programming 101: time waits for nothing
Также wait-free механики встречаются в СУБД, Runtime, Linux. Но практически всегда это не академический wait-free a wait-free на осознанных трейдоффах.
На этом всё, в следующих постах попробую сообразить несколько примеров кода академического и практического. Так сказать увидим собственными глазами😊