Выборочная синхронизация потоков.

Здравствуйте, есть потоки работающие с общим двунаправленным связанным списком, все потоки кроме одно только читают информацию из списка , один поток "основной" добавляет и удаляет записи из списка, сейчас я синхронизирую чтение/запись через мутекс который захватывается всеми читающими потоками и также основным потоком при необходимости удаления удалении записи. По идеи все читающие потоки должны синхронизироваться только с "основным" потоком но не между собой, так как ошибка доступа возможна лишь при удалении записи и одновременном чтении из нее. Вот и возник вопрос как синхронизировать доступ к области памяти только между "Основным" потоком и всеми читающими, т.е. производить блокировку читающих потоков только при необходимости удаления.

Сейчас делаю так:

Все читающие потоки:
В начале чтения ждем захвата общего мутекса
читаем
освобождаем мутекс

"Основной поток"
чтение и добавление производим без захват мутекса
при удалении захватываем мутекс.
удаляем
освобождаем мутеск.

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

 

Читающий тред:
1. Инкремент счётчика потоков, обращающихся к ресурсу.
2. Проверяем переменную W. Если TRUE, то ждём на эвенте W.
3. Читаем ресурс.
4. Декремент счётчика потоков.
5. Если счётчик потоков = 0, то сигнализируем евент R.

Пишущий тред:
1. Устанавливаем переменную W в TRUE.
2. Проверяем счётчик потоков, если отличен от нуля, то ждём на эвенте R.
3. Пишем ресурс.
4. Устанавливаем переменную W в FALSE и сигнализируем эвент W.

Пара эвентов - это обьект EventPair.

 

Смотрите технику RCU (Read-Copy-Update) + атомарность операций. Проблемы возможны, как вы правильно отметили, только при удалении элемента -- здесь используйте Mutex или лучше его самописный аналог, т.к. Mutex'ы достаточно медленны.

 

Техника понятна правда инкремент счетчика тоже придется синхронизировать (через префикс lock возможно?(lock inc))?
Спасибо.
П.С. Возможна ошибка?: если два треда Читающий и Пишущий пойдут одновременно с п1. то оба зависнут в ожидании события W/R навсегда.

 

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

 

Ну так отслеживайте когда потоки завершаются, это ж ваш код надеюсь

 

Sercher
Если совместимость с версиями ниже Vista не планируется, можно использовать SRWLock - облегчённый вариант критической секции, специально разработан для подобных случаев.

 

А вы с переменными условиями не сталкивались?

 

в основном XP ,2000, (вист и 7 меньше половины)

 

Не используйте ExitThread(), используйте try-блоки и будет вам счастье

 

А по топику есть у кого какие идеи?

 

klzlk
a) Приходит читающий поток, выполняет свой п.1.
Переключение потока.
b) Приходит пишущий поток, выполняет свои п.1, п.2 и виснет на событии R, т.к. счётчик потоков превышает нуль.
Возобновление читающего потока.
с) Читающий поток видит, что W установлена и виснет на событии W.

His majesty, deadlock.

 

l_inc
Ну да, я забыл местами поменять первые пункты. Проверка и изменение атомарны - lock cmpxchg. Аналогично как в критических секциях например.

 

klzlk

Ну и какой тогда правильный вариант получится, если поменять? Хочу посмотреть, что Вы без матчасти придумаете. А то не стоило ведь бросать универ. Reader-Writer cooperation, знаете ли, в программу первых двух лет входит (у нас на теории ОС на третьем семестре было).

У Вас в алгоритмах нету проверки и измения одной и той же переменной в пределах одного пункта. Так что lock cmpxchg применить не к чему.

 

l_inc
Это псевдокод. Можно стопяцот причин найти, почему он не будет работать. Псевдокод это максимально краткое описание алгоритма.

Вам студентик наверно обьяснили что такое Event Pair..

 

klzlk

Ага. К тому же неправильный. Первая причина есть. А за правильным псевдокодом предлагаю обратиться к Таненбауму (Операционные системы. Разработка и реализация).

Event pair студентику не нужно, т.к. не является базовым примитивом синхронизации. А специфические объекты ядра Windows к базовому образованию не относятся.

 

l_inc
Говорю же, поменяйте два первых пункта местами.

Без оси ваше образование никому нафиг не нужно. Дифференцируйте дальше.)

 

klzlk

Спрашиваю же, что получится. Какие первые два менять? У читающего? У пишушего? У обоих?
В любом случае будет нарушение условий взаимоисключающего доступа.

 

Я уже давно об этом написал см. выше в п.с.
Сейчас для осей выше ХР юзаю srwlock(прекрасная штука!), для остальных версий ОС,пока ищу ...

 

Sercher

Да-да. Пару часов после моего поста я заметил. Но, т.к. klzlk заметил свою ошибку только после моего поста, пост стоил повторения.

Что искать? Я ж уже предложил глянуть у Таненбаума. Предложение предназначалось в основном Вам.