поучительная история про мальчика билли

[kodt_rsdn]

Три дня бился с зависанием, казалось бы, несложной двух-с-половиной-поточной программы.
(Один поток - UI, второй - рабочий, половинный - асинхронные колбеки непонятно откуда из MAPI).

Сперва сделал всё академически, на активных объектах, мониторах и условных переменных.

Comments

[mejedi]

В части условных переменных, это очень неполное описание.

Есть достаточно известная статья про имплементацию CV средствами WINAPI. Там последовательно разбирают разные варианты реализации, и находят в них баги.

ИМО это один из лучших материалов по CV.

[kodt_rsdn]

Естественно, я и не ставил цель раскрыть всю полноту CV (УП).
Тем более, моделировать работу именно позиксного планировщика потоков, ждущих УП.

Понятно, что наивная реализация (на одном эвенте) хорошо работает только в ситуации 1 поставщик - 1 потребитель. Как только у нас больше 2 потоков, незамедлительно встанет проблема голодания.

Но бродкаст и грамотная внутренняя очередь - это лишь половина мер против голодания.
Вторая половина - грамотная бизнес-логика.

Потому что в любом базисе синхрообъектов можно выразить любое поведение. В том числе, и любое проблемное.
Например, дедлок. Только его особенность будет в том, что мьютекс разблокирован. Просто потоки заснули в ожидании друг друга, и некому послать сигнал пробуждения.

[mejedi]

> Классическое и, я бы сказал, детское, решение: засунуть в критические секции только тот код, который непосредственно взаимодействует с общими данными.
Почему детское то?

[kodt_rsdn]

Детское - потому что это следование хорошо известному паттерну работы с виндовскими потоками.

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

Монитор - более высокоуровневая концепция, но как я показал на печальном опыте, тоже не серебряная пуля.

[mejedi]

По этой детской схеме реализовано ядро FreeBSD :)

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

В таких случаях просто определяют валидный lock order, и каждую операцию с объектами синхронизации проверяют на соответствие lock order (обычно только в дибаге).

Пример: есть очередь планировщика потоков (со своей блокировкой), и множество объектов, олицетворящих потоки (каждый со своей блокировкой). Запрещаем рекурсивно лочить один объект, запрещаем лочить больше одного потока, запрещаем лочить очередь планировщика, если уже залочен поток (наоборот можно).

Таким образом, если на какой-то ветке кода возможен дедлок, мы гарантированно его обнаружим при первом выполнении этой ветки кода, вне зависимости от того, как планировщик ОС распределил кванты процессорного времени между тредами. Разумеется, о compile-time проверке речи не идет, но хотя бы все детерминировано

[kodt_rsdn]

С мониторами идея в том, что если поток выходит за пределы монитора - как по return, так и по call, он должен снимать блокировку.
Примерно так:

void monitor1::foo()
{
lock lk(this->m_mutex);
.....
..... // здесь внутреннее состояние может быть каким угодно
.....

// к этому месту приводим объект в непротиворечивое состояние
{
unlock ulk(this->m_mutex);
mon2.bar();
}
// состояние непротиворечивое, но, возможно, изменившееся

.....
..... // продолжаем ковыряться в недрах
.....
}

Очень хорошо, если эта фича поддерживается на уровне языка. Вот надо бы взглянуть на Oberon - интересно, сделали они её или нет?

Собственно, ожидание условной переменной - частный случай такого временного покидания монитора.

А высокоуровневый дедлок завсегда можно получить, было бы желание :).
Поскольку на мониторах можно эмулировать семафоры, а на семафорах дедлок - как два пальца об асфальт.
На самом деле, для дедлока достаточно одного семафора (с рекурсивным захватом).

semaphore s