Коротко и по делу.
Основные ошибки в упрощённом producer/consumer с флагом busy_wait:
- Гонки («глайд‑условия»): проверка условия и действие выполняются без синхронизации, поэтому два потока могут одновременно увидеть «вакантно» и испортить состояние буфера.
- Потеря уведомлений: сигнал может быть послан до того, как потребитель начнёт ждать → уведомление потеряно и поток будет ждать вечно.
- Высокая загрузка CPU: busy‑wait (цикл опроса флага) использует CPU, масштабируемость и энергопотребление плохи.
Корректные реализации
1) mutex + condition variables (bounded buffer ёмкости $N$, счётчик $count$, буфер FIFO):
- Переменные: mutex, cond_not_empty, cond_not_full, буфер, вместимость $N$, $count=0$.
- Producer:
lock(mutex)
while $(count==N)$ wait(cond_not_full, mutex)
enqueue(item); $count++$ signal(cond_not_empty) // или broadcast в специфичных случаях
unlock(mutex)
- Consumer:
lock(mutex)
while $(count==0)$ wait(cond_not_empty, mutex)
item = dequeue(); $count--$ signal(cond_not_full)
unlock(mutex)
Комментарии: обязательно использовать while (не if) — это защищает от спонтанных пробуждений и изменений условия между пробуждением и повторной проверкой. Сигнал должен посылаться после изменения состояния (под mutex или сразу после выхода из него), чтобы избежать race между сигналом и началом ожидания.
2) Семафоры (классический вариант):
- Инициализация: semaphore empty = $N$, semaphore full = $0$, mutex = 1
- Producer:
wait(empty)
wait(mutex)
enqueue(item)
post(mutex)
post(full)
- Consumer:
wait(full)
wait(mutex)
item = dequeue()
post(mutex)
post(empty)
Семафоры автоматически блокируют и не теряют «уведомления» в том смысле, как это бывает с флагом; схема проста и эффективна.
Проблемы справедливости и живучести (liveness) при разных планировщиках
- FIFO / fair scheduler: минимальный риск голодания, поведение ближе к ожидаемому (очередность ожидателей сохраняется, если примитивы это поддерживают).
- Round‑Robin: ливл‑время обычно гарантировано, но возможны convoy‑эффекты (один поток удерживает mutex, другие ждут).
- Приоритетный планировщик: возможна голодание низкоприоритетных потоков и priority inversion (низкоприоритетный захватил mutex, блокируя высокоприоритетный). Решения: priority inheritance, протоколы обхода приоритета.
- Condition variables и semaphores обычно не гарантируют строгой справедливости — порядок пробуждения может быть произвольным; если нужна гарантия FIFO, следует использовать реализации, которые выставляют очередь ожидания FIFO, или дополнительно реализовать очередь ожидателей.
- Deadlock/Starvation: возможны при неверной комбинации mutex/семафоров (например, нарушение порядка захвата нескольких mutex). Семафоры устраняют потерю уведомлений, но не автоматически справляются с приоритетами и справедливостью.
Рекомендации
- Не использовать busy‑wait для блокировки, использовать блокирующие примитивы.
- Всегда проверять условие в цикле while при использовании condvar.
- Для простого подсчёта/буфера — семафоры проще и эффективнее; для сложных предикатов — mutex+condvar.
- Если важна справедливость или работа в приоритетной системе — применять FIFO‑очереди ожидания или протоколы priority inheritance; при большом числе ожидающих думать о broadcast vs signal (thundering herd).
Если нужно, могу привести конкретный пример кода на pthreads или на языке C/C++/Python.