потоки

> Возникла странная ситуация:

Это не странная, а типовая ситуация.

Задачка почти из FAQ, на семафорах решается просто, обсуждали не так давно:

http://www.linux.org.ru/view-message.jsp?msgid=1200047

Огромное спасибо! А я думал это что-то у меня такое приключилось ;)

>Как можно это правильно реализовать

Совсем правильно(IMHO и если памяти хватает) - не "обновлять" структуру, а генерировать рядом новую. Тогда блокировки не нужны вообще.

А ещё есть "транзакционная память" - но пока мало где AFAIK.

> Это не странная, а типовая ситуация.

> Задачка почти из FAQ, на семафорах решается просто, обсуждали не так давно:

> http://www.linux.org.ru/view-message.jsp?msgid=1200047

Немного странно, что никто не упомянул решение с использованием
pthread_rwlock_init() и связанных с этим функций которые собственно
и придуманы для r/w-locks.
Этот API уже был в SUSv2 и AFAIK поддерживался уже Solaris 8 (а то и
Solaris 7).
На Linux я правда этот API напрямую не использовал но AFAIK в NPTL
это должно работать(?).

HTH

Ну так в любом случае в момент подмены старой структуры новой (что я и собираюсь делать), нельзя чтобы по старой бродили читатели

Маны нашел только на на opengroup.org, это то что мне нужно. Кто-нибудь может поделить своими мыслями по поводу использования этого механизма ? Или лучше делать классическим способом на семафорах?

> Совсем правильно(IMHO и если памяти хватает) - не "обновлять"
> структуру, а генерировать рядом новую.

не сказал бы, что это "совсем" правильно. у этого подхода
наряду с достоинствами есть и недостатки. собственно, это
RCU (read-copy-update).

> Тогда блокировки не нужны вообще.

только для "читателей".

Так все таки, насколько безопасно использовать rwlock? Как я понял они не является станадртом NPTL, защищены __USE_UNIX98..

>в момент подмены старой структуры новой (что я и собираюсь делать), нельзя чтобы по старой бродили читатели

Почему нельзя? Если поток начал обработку со старыми данными, он должен её с ними закончить(*). Потому читатели должны иметь возможность ходить по старой столько, сколько им нужно. А момент подмены - это запись одного указателя, операция скорее всего атомарная, потому блокировка не нужна - просто какие-то потоки ещё немножко поработают со старыми, считай обновление для некоторых потоков произошло на долю секунды позже. Время относительно:-)

(*) Или пересчитать с новыми - но это другая тема.

>наряду с достоинствами есть и недостатки

Это у всех есть. У блокировок с inplace модификацией совсем плохо с масштабируемостью - они склонны сводить на нет паралельность железа. А тут всего лишь *O(log N).

Хм .. помоему даже если они плохо переносимы, можно самим написать реализацию... это не так сложно (все на мьютексе и счетчике), я делал и у Стивенса есть примерчик =)

> Это у всех есть.

разумеется

> А тут всего лишь *O(log N).

откуда взялась эта оценка, и что она в данном случае
означает - совершенно непонятно.

кроме того, не надо забывать, что все spin lock реализации
одинаковы, те отличаются на O(1), и это "O" реально мало.
в случае же RCU это не так. по той простой причине, что для
начала нужно как-то определить, что мы подразумеваем под
grace period. иначе аналог rcu_read_lock() будет вряд ли
много легче read_lock().

короче - я не верю, что автору это нужно (и у него еще должна
быть какая-то реализация, что не факт). более того, очень
часто spin_lock() работает лучше и быстрее, чем read/write
locks. и дело даже не в том, что последние примитивы не имеет
смысла использовать если lock на чтение берется на "короткое"
время.

часто read/write locks нужны для реализации определенной
семантики, например в ядре есть rwlock_t и seqlock_t.
последний - в сущности - тот же rwlock_t, но не допускает
writer starvation.

так что дело не только в производительности и в ее оценках,
тем более что, как правило, чем проще - тем лучше.

To anonymous (*) (04.03.2006 19:06:52)

> Так все таки, насколько безопасно использовать rwlock?

Что значит "безопасно" в данном контексте? От кого/чего безопасно?
Более-менее удовлетворительную безопасность обеспечивают
презервативы ;-)

> Как я понял они не является станадртом NPTL, защищены __USE_UNIX98..

NPTL - не стандарт. Это реализация threads, претендующая на
соответствие стандарту POSIX и SUS.

AFAIK, реализации rwlock в Solaris и AIX вполне себе работоспособны,
с чего бы им и в Linux не работать (с точность до багов)?

Впрочем если есть причины не использовать pthread_rwlock имплементация
"руками" достаточно тривиальна, да и у Стивенса посмотреть можно
как уже указали выше.

HTH

Под безопасностью я имел ввиду сырость этого кода и т.п. (ведь почему то rwlock защищены, в отличие от других __USE_UNIX98). Ok, спасибо, тогда вопросов не имею. Большое спасибо за помощь. А можно название книжки Стивенса? Их вообще вроде 2 автора. А то все по инету до по форумам, бумаги нет совсем

>откуда взялась эта оценка, и что она в данном случае означает - совершенно непонятно.

Средне-отпотолочная оценка overhead-а. Памяти будет съедено больше (в худшем случае в несколько раз - но от автора не требуется именно худшая реализация:-) Ну и на распределение/чистку памяти нужно несколько процессорного времени.

>spin_lock() работает лучше и быстрее

Не спорю. Медленно работают не блокировки, а программа в случае большого их количества, и программист, вынужденый об этом думать:-)

>в случае же RCU это не так

Я имел ввиду немножко другого зверя: http://en.wikipedia.org/wiki/Data_structure_persistance

>я не верю, что автору это нужно

Я тоже. Но ему стоит знать, что существует жизнь без [видимых] блокировок.

>если lock на чтение берется на "короткое" время

Возник бы этот вопрос у автора, если бы это было легко в общем случае?

>как правило, чем проще - тем лучше

O! Алгоритм, работающий в среде "неизменяемых" данных, вообще может не знать об потоках и при этом идеально паралелится. Это и есть _проще_.

> > в случае же RCU это не так
>
> Я имел ввиду немножко другого зверя:
> http://en.wikipedia.org/wiki/Data_structure_persistance

да то же самое это. все равно нам нужно как-то определить,
что на вот эту "старую" data structure никто не смотрит и
можно ее вычистить. ну garbage collection можно использовать,
так ведь это тоже не так просто добавить.

> я не верю, что автору это нужно
>
> Я тоже. Но ему стоит знать, что существует жизнь без [видимых]
> блокировок.

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

> O! Алгоритм, работающий в среде "неизменяемых" данных, вообще
> может не знать об потоках и при этом идеально паралелится.
> Это и есть _проще_.

не согласен. я немножко с этим работаю. жизнь (и то не всегда!)
упрощается для read side. writer как правило должен быть более
внимателен. к тому же, в реальных задачах это перемешано с
блокировками других типов (ну хотя бы потому, что "писателям"
нужно защищаться друг от друга), что зачастую приводит к весьма
нетривиальным проблемам. одно только добавление необхолимых
memory barriers чего стоит.

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

>да то же самое это

Почти. И вид сбоку:-)

>garbage collection ... не так просто добавить

В некоторых случаях его не так просто убрать:-)

>... что такой подход лучше всегда и везде.

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