A3. Producer–consumer

середнійспирається на модуль 8, модуль 9

Мета

Обмежений буфер є моделлю будь-якої черги задач: пулу потоків, черги з’єднань, конвеєра обробки. Ви реалізуєте його двічі й самі побачите, за яких умов версія без блокувань виграє, а за яких програє.

Друга частина тут важливіша за першу. Твердження «lock-free швидше» поширене й без уточнення умов неправильне, а ви отримаєте власні числа.

Що має вийти

Дві програми з однаковим інтерфейсом:

./pc-mutex    --producers 4 --consumers 4 --items 1000000 --capacity 1024
./pc-lockfree --producers 4 --consumers 4 --items 1000000 --capacity 1024

--items — загальна кількість елементів, поділена порівну між виробниками. Елементи нумеруються від 1 до items, тому очікувана контрольна сума завжди items × (items + 1) / 2. Споживачі підсумовують те, що отримали.

Останній рядок виводу зафіксований, на нього спирається автоперевірка:

checksum=500000500000 expected=500000500000 elapsed_ms=412

Сума мусить збігатися завжди. Незбіг означає, що елементи губляться або дублюються, і жоден вимір швидкості після цього не має сенсу.

Етапи

1. Версія з м’ютексом і умовними змінними.

   Буфер фіксованої місткості, один м’ютекс, дві умовні змінні: «є місце» і «є елемент». Виробник чекає на першій, споживач на другій.

   Умову перевіряйте у циклі while, не в if (модуль 9).

2. Перевірка санітайзером.

   gcc -O2 -pthread -fsanitize=thread pc-mutex.c -o pc-tsan && ./pc-tsan

   ThreadSanitizer має мовчати. Якщо він знаходить гонитву, а програма при цьому дає правильну відповідь — це саме той випадок, коли «працює» нічого не доводить.

3. Коректне завершення.

   Споживачі мають вийти, коли виробники закінчили і буфер порожній. Найчастіша помилка курсу — споживач назавжди зависає в wait, бо його вже нікому будити.

4. Версія без блокувань.

   Кільцевий буфер на атомарних індексах читання й запису. Публікація елемента — compare_exchange на індексі, потім запис значення, потім атомарне оновлення позначки готовності.

   Порядок операцій тут не косметика: без правильних memory_order споживач побачить індекс раніше за дані (модуль 9).

5. Замір.

   Прогоніть обидві версії на 1, 2, 4 і 8 потоках з кожного боку, з малим і великим буфером. Побудуйте таблицю.

   Поясніть письмово, чому на одному виробнику й одному споживачі різниця мала, а на восьми — велика; і чому за дуже малого буфера версія без блокувань може програти.

Що саме порівнюєте

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

Замірюйте «порожній» варіант — і окремо варіант із роботою. Висновок, що за реального навантаження різниця зникає, теж є результатом, і саме він пояснює, чому lock-free застосовують рідше, ніж обговорюють.

Автоперевірка

Перевірка лежить в архіві з файлами курсу, і команди нижче виконуються з розпакованого каталогу.

cd labs/a3-producer-consumer
./check.sh ./pc-mutex ./pc-lockfree

Перевірка ганяє обидві версії на різних співвідношеннях потоків, звіряє контрольні суми й ловить зависання за таймаутом.

Часті помилки

Втрачені або задвоєні елементи. Контрольна сума не збігається. Майже завжди причина в тому, що індекс оновлено не атомарно або що перевірка місця й запис розділені.

Програма зависає наприкінці. Або немає сигналу завершення для споживачів, або broadcast замінили на signal там, де чекає кілька потоків.

if замість while навколо wait. Працює рівно доти, доки споживач один.

Заміри без прогріву. Перший прогін включає створення потоків і холодні кеші, тож робіть кілька повторів і беріть медіану.

Далі, якщо цікаво

Порівняти з чергою на двох м’ютексах (окремо для голови й хвоста) і з pthread_spinlock — і побачити, що середина між двома крайнощами часто виграє в обох.