Магистерский курс C++ (МФТИ, 2022-2023). Лекция 20. Очереди.

Лекции в магистратуре МФТИ по современному C++ на русском языке. Кафедра микропроцессорных технологий.

На прошлой лекции мы рассмотрели большую часть нашего инструментария. Давайте попробуем собрать из него очередь, убедиться что у нас остались проблемы, решить их и собрать ещё одну очередь. Далее мы сделаем важнейший шаг перейдя от очереди данных к очереди упакованных задач. Для этого нам придётся наладить каналы коммуникации с потоками, познакомиться с маршалингом исключений и рассмотреть несколько новых концепций по дороге. Но в итоге мы придём к цели. Или почти придём, следите за руками.

Лектор: Константин Владимиров.
Дата лекции: 29 марта 2023 года.
Съёмка и звук: Юлий Тарасов.

Timeline:
00:00 Введение: продолжаем сагу о sigatomic.
04:50 Ментальная модель мьютекса.
10:00 Ограниченная очередь
16:15 Небольшая проблема и её воспроизведение
24:10 Пробуждение в конце
28:50 Неограниченная очередь
35:20 Коммуникация с потоками: divide
45:00 Канал future/promise
49:00 Маршаллинг исключений и упакованные задачи
56:50 Joinable threads
59:40 Проблема барьера
01:06:40 Очередь упакованных задач
01:14:12 Задача-вызов и литература

Errata:
* Пока пусто

[kyberduk-youtube]

О последней задачке (что удалось увидеть сразу, может там еще что есть).
Два консьюмера одновременно проходят safe_empty().
Первый успевает сделать safe_pop().
А вот второму достанется пустая очередь - safe_pop() и бум.

[tilir]

Немного errata в отношении пока не замеченных в комментариях ошибок для bounded MPMC queue / stack.

(1) В случае multi-producer делать wake_and_done надо на всех продьюсеров один раз иначе бывает так что консьюмеры повыходили но не все продьюсеры ещё закончили.
(2) Саму функцию wait_and_pop надо делать с сигнатурой bool wait_and_pop(T &Data) чтобы понимать есть там что консьюмить или нет
(3) Внутри wait_and_pop условие должно выглядеть так:

CondCons.wait(Lk, [this] { return !empty() || done(); });
if (empty())
return false;

Даже если у нас сигнализирован done, задачи могут быть недоразобраны и поэтому критерий return false это только empty.

(4) Внутри push признак done вообще проверять не надо т.к. это признак отработки всех продьюсеров. Там играет роль только full.
(5) В интерфейсе необходим метод is_empty_and_done() чтобы по нему консьюмеры понимали когда начинать выходить.

Полу-финальные обновлённые версии bounded stack и bounded queue с тестами на то что они не теряют задач я выложил сюда:


Начну с этого следующую лекцию.

[makaedg]

Здравствуйте, Константин. Спасибо за интересную лекцию!

На слайде 42 (1:13:33) не должно ли быть std::forward_as_tuple вместо std::make_tuple?

[danielkeehl]

32:09
Почему мы делаем Q.wake_and_done() в consume? Мы точно знаем, что в produce он выполнится первым, и зачем-то пушим лимитеры второй раз. Или я что-то не так понял?

[АндрейШевелёв-гщ]

Здраствуйте, Константин. Хотел задать вопрос - будут ли выложены на ютуб лекции по языку С с первого курса? Очень хотелось бы увидеть на ютубе лекции по этому языку в вашем исполнении, уж слишком у вас шикарная манера подачи учебного материала)

[igorlugansky]

По unbounded_queue с 33-ей минуты есть вопрос.

void wait_and_pop(T& Data) {
...
Cond.wait(Lk, [this]{ return !Q.empty(); });
T Task = std::move(Q.front()); // а это корректно в случае лимитера? у нас не будет лимитер moved-from после того
// как первый из проснувшихся консюмеров его обработает?
...
}

Не правильнее ли будет сделать мув после проверки?

void wait_and_pop(T& Data) {

...
Cond.wait(Lk, [this]{ return !Q.empty(); });
T& Task = Q.front();

if (Task == Limiter<T>) {
...
}

...

Data = std::move(Task);
Q.pop();
}

[РоманМитин-пт]

Мне кажется очередь с 15:00 является на самом деле стеком

[navy]

Константин говорит о неком TLA который позволяет отследить, что многопоточный код работает верно. Речь об этом на 28 минуте. Можете кто нибудь поделится референсами на этот инструментарий ?

[dimon_ksi]

Мне кажется, что std::reference_wrapper можно принимать в функции просто by value

[ana_infinite_games]

Честно не знаю насколько хорошо плавают котята, но надеюсь фраза "всплывают 3 белых котенка" не несет зловещего смысла)