Безопасно ли добавлять / удалять из двух потоков одновременно, при условии что вставка и удаление происходят в непересекающихся областях? Такое у меня чувство, что ничего страшного происходить не должно.

Здравствуйте, Garrett, Вы писали:

G>Безопасно ли добавлять / удалять из двух потоков одновременно, при условии что вставка и удаление происходят в непересекающихся областях? Такое у меня чувство, что ничего страшного происходить не должно.

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

Здравствуйте, dupamid, Вы писали:

D>Здравствуйте, Garrett, Вы писали:

G>>Безопасно ли добавлять / удалять из двух потоков одновременно, при условии что вставка и удаление происходят в непересекающихся областях? Такое у меня чувство, что ничего страшного происходить не должно.

D>Безопасность в этом случае не гарантируется. Более того, исходя из знания реализации, в самом списке есть счетчик числа элементов, как минимум он может обновляться не верно.

Ладно, щас начну играться и проверять.

Здравствуйте, Garrett, Вы писали:

G>Ладно, щас начну играться и проверять.

По закону подлости проверки могут пройти
В реальной ситуации нет
Зачем закладываться на такой стремный момент

Здравствуйте, Какая разница, Вы писали:

КР>Здравствуйте, Garrett, Вы писали:

G>>Ладно, щас начну играться и проверять.

КР>По закону подлости проверки могут пройти
КР>В реальной ситуации нет
КР>Зачем закладываться на такой стремный момент :xz:
Ну просто интересно стало. :) Может это можно использовать в качестве недокументированной фичи

Здравствуйте, Garrett, Вы писали:
G>Ну просто интересно стало. Может это можно использовать в качестве недокументированной фичи

И в лицензионном соглашении не забудь приписку сделать

Все баги обнаруженные в данном продукте являются фичами и ничем другим кроме фич

Здравствуйте, Garrett, Вы писали:

G>Ладно, щас начну играться и проверять.

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

Здравствуйте, bkat, Вы писали:

B>Здравствуйте, Garrett, Вы писали:

G>>Ладно, щас начну играться и проверять.

B>Да не проверяй и ничего не синхронизируй.
B>Зато потом будет интереснее баги искать :-)
B>Опыт поимеешь :-/

:)))

Здравствуйте, Garrett, Вы писали:

G>Безопасно ли добавлять / удалять из двух потоков одновременно, при условии что вставка и удаление происходят в непересекающихся областях? Такое у меня чувство, что ничего страшного происходить не должно.

Сделайте критические секции — в чём проблема-то?
Зачем нужен лишний геморой для проверки, что эти области действительно не пересекаются.

Здравствуйте, Alexey Borodin, Вы писали:

G>>Безопасно ли добавлять / удалять из двух потоков одновременно, при условии что вставка и удаление происходят в непересекающихся областях? Такое у меня чувство, что ничего страшного происходить не должно.

AB>Сделайте критические секции — в чём проблема-то?
AB>Зачем нужен лишний геморой для проверки, что эти области действительно не пересекаются.

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

Здравствуйте, dupamid, Вы писали:

D>Здравствуйте, Alexey Borodin, Вы писали:

G>>>Безопасно ли добавлять / удалять из двух потоков одновременно, при условии что вставка и удаление происходят в непересекающихся областях? Такое у меня чувство, что ничего страшного происходить не должно.

AB>>Сделайте критические секции — в чём проблема-то?
AB>>Зачем нужен лишний геморой для проверки, что эти области действительно не пересекаются.

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

хм, бывает конечно, но это не проблема cs а проблема их использования

Здравствуйте, dupamid, Вы писали:

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

Так ведь, по крайней мере на однопроцессорных системах, вся работа всё-равно будет последовательная. Я бы не советовал пытаться оптимизировать таким вот образом. Лучше уж потеря некоторой производительности, чем в один прекрасный момент вы узнаете, что ваша программа почему-то не работает. Или ещё хуже — работает, но в среднем около суток, а потом что-то случается.

Здравствуйте, dupamid, Вы писали:

А вообще — если Вы сможете гарантировать, что области использования не пересекаются, то проблем не должно быть.
Тот же размер для list обычно не нужен, более важно — есть в нём элементы или нет.
А если у Вас есть две области, которые не пересекаются, то очевидно, размер списка всегда больше 0, то есть список никогда не бывает пустым.
Вставка-удаление элемента в список должна влиять только на соседние элементы.

Здравствуйте, Alexey Borodin, Вы писали:

AB>Вставка-удаление элемента в список должна влиять только на соседние элементы.

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

Здравствуйте, Alexey Borodin, Вы писали:

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

AB>Так ведь, по крайней мере на однопроцессорных системах, вся работа всё-равно будет последовательная. Я бы не советовал пытаться оптимизировать таким вот образом. Лучше уж потеря некоторой производительности, чем в один прекрасный момент вы узнаете, что ваша программа почему-то не работает. Или ещё хуже — работает, но в среднем около суток, а потом что-то случается.

Я бы не стал сейчас делать такой упор на однопроцессорных системах. Многоядерность неизбежна и софт, который разрабатывается сейчас будет работать, скорее всего, на системах с настоящей мультипоточностью. Именно из-за того, что часто всё просто обкладывают критическими секциями, программы плохо масштабируются и могут возникать взаимные блокировки. Это не значит, что не нужно синхронизовать, просто не всегда синхронизация должна быть на уровне всего объекта (или еще какой-то сущности высокого уровня) иногда нужно очень детально управлять блокировкой. Мне показалось, что вопрос возник именно применительно к таким системам.

> AB>Вставка-удаление элемента в список должна влиять только на соседние элементы.
>
> Этого досточно, чтобы задуматься о критических секция.
> Очень наивно надеятся, что поток, итерирующий элементы списка,
> никогда не наткнется на элемент, который другой поток удаляет.
> Попытка достичь этого без использования тех же критических секций или аналогов
> только запутает код и сделает его очень глючным.

Насколько я помню, неблокирующие списки традиционно реализуются на примитивах типа compare-and-swap (InterlockedCompareExchange в widows), называть которые аналогами критических секций просто смешно.

Здравствуйте, Sergey, Вы писали:


>> AB>Вставка-удаление элемента в список должна влиять только на соседние элементы.
>>
>> Этого досточно, чтобы задуматься о критических секция.
>> Очень наивно надеятся, что поток, итерирующий элементы списка,
>> никогда не наткнется на элемент, который другой поток удаляет.
>> Попытка достичь этого без использования тех же критических секций или аналогов
>> только запутает код и сделает его очень глючным.

S>Насколько я помню, неблокирующие списки традиционно реализуются на примитивах типа compare-and-swap (InterlockedCompareExchange в widows), называть которые аналогами критических секций просто смешно.

А ты сравни интерфейсы, которые предоставляют std::list и неблокирующие списки...
Это совершенно разные по способу использования структуры данных.

Здравствуйте, dupamid, Вы писали:

D>Я бы не стал сейчас делать такой упор на однопроцессорных системах. Многоядерность неизбежна и софт, который разрабатывается сейчас будет работать, скорее всего, на системах с настоящей мультипоточностью. Именно из-за того, что часто всё просто обкладывают критическими секциями, программы плохо масштабируются и могут возникать взаимные блокировки. Это не значит, что не нужно синхронизовать, просто не всегда синхронизация должна быть на уровне всего объекта (или еще какой-то сущности высокого уровня) иногда нужно очень детально управлять блокировкой. Мне показалось, что вопрос возник именно применительно к таким системам.

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

>>> AB>Вставка-удаление элемента в список должна влиять только на соседние элементы.
>>>
>>> Этого досточно, чтобы задуматься о критических секция.
>>> Очень наивно надеятся, что поток, итерирующий элементы списка,
>>> никогда не наткнется на элемент, который другой поток удаляет.
>>> Попытка достичь этого без использования тех же критических секций или аналогов
>>> только запутает код и сделает его очень глючным.
>
> S>Насколько я помню, неблокирующие списки традиционно реализуются на примитивах типа compare-and-swap (InterlockedCompareExchange в widows), называть которые аналогами критических секций просто смешно.
>
> А ты сравни интерфейсы, которые предоставляют std::list и неблокирующие списки...

Ну разные, и что с того?

> Это совершенно разные по способу использования структуры данных.

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

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

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