A3. Producer–consumer

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

Мета

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

Після цієї роботи ви зможете:

написати обмежений буфер на м’ютексі й двох умовних змінних, який не губить і не дублює елементи за будь-якої кількості потоків;
пояснити, чому умову перевіряють у while, а не в if, і чому споживачі зависають, коли їх нікому розбудити;
написати кільцевий буфер на атомарних індексах із правильними memory_order;
прочитати вивід ThreadSanitizer і назвати рядок, у якому гонитва;
показати на власних замірах, коли версія без блокувань виграє, а коли ні.

Ті самі дві конструкції стоять за чергами в пулах потоків, логерах і мережевих серверах, де «lock-free швидше» повторюють без уточнення умов.

Завдання

Написати на C дві програми з однаковим інтерфейсом, pc-mutex і pc-lockfree: виробники кладуть числа в обмежений буфер, споживачі забирають і підсумовують.

./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

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

Що має вміти:

приймати аргументи --producers, --consumers, --items, --capacity;
працювати за будь-якого співвідношення потоків: 1:1, 4:4, 8:2, 2:8;
працювати з буфером на один елемент і з кількістю елементів, меншою за кількість потоків, зокрема з одним елементом на чотирьох споживачів;
завершуватися з кодом 0, коли виробники закінчили і буфер порожній; прогін довший за 30 секунд перевірка вважає зависанням;
давати правильну суму п’ять прогонів поспіль, бо гонитва проявляється не щоразу;
pc-mutex мовчить під ThreadSanitizer.

Обмеження. У pc-lockfree немає м’ютексів, спін-блокувань і семафорів: лише атомарні операції з <stdatomic.h>. Обидві версії збираються gcc з -pthread.

Чого робити не треба. Обробляти елементи по-справжньому не треба: виробник кладе число, споживач додає його до суми. Варіант із роботою над елементом потрібен лише для замірів (Aside «Що саме порівнюєте»).

Що записати у звіт:

вивід ThreadSanitizer для pc-mutex або підтвердження, що він мовчить;
таблицю замірів: 1, 2, 4 і 8 потоків з кожного боку, малий і великий буфер, обидві версії, медіана кількох прогонів; кількість ядер машини;
пояснення, чому на 1:1 різниця мала, а на 8:8 велика, і чому за дуже малого буфера версія без блокувань може програти;
окремий замір із роботою над елементом і висновок, чи лишилася різниця.

Готово, коли:

./check.sh ./pc-mutex ./pc-lockfree проходить усі вісімнадцять перевірок, по дев’ять на кожну програму, і ThreadSanitizer мовчить;
у звіті є таблиця замірів і відповіді на три запитання вище.

Перед початком

Прочитайте в модулі 9 розділи «Інструменти», «Модель пам’яті» і «Класичні задачі», а в модулі 8 розділ «Що потоки ділять».
Розпакуйте архів курсу: перевірка лежить у labs/a3-producer-consumer/check.sh. ThreadSanitizer вона запускає, лише якщо pc-mutex.c лежить у каталозі, з якого викликано скрипт.
Знадобиться gcc з -fsanitize=thread. Підійде будь-який Linux, зокрема контейнер і WSL2; для замірів потрібні кілька ядер, у Vagrant-машині їх два.

Етапи

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

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

Умову перевіряйте у циклі while, не в if (модуль 9).
Перевірка санітайзером.
Terminal window
```
gcc -O2 -pthread -fsanitize=thread pc-mutex.c -o pc-tsan && ./pc-tsan
```
ThreadSanitizer має мовчати. Якщо він знаходить гонитву, а програма при цьому дає правильну відповідь, то «працює» тут нічого не доводить.
Коректне завершення.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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