Есть некоторый vector. Один поток добавляет элементы в его конец, а другой — выбирает из головы, т.е. своеобразная очередь. Понимаю, что вариантов синхронзации может быть множество, но среди этого разнообразия хотелось бы получить самый оптимальный, ведь задача то тривиальная.
Здравствуйте, BioUnit, Вы писали:
BU>Есть некоторый vector. Один поток добавляет элементы в его конец, а другой — выбирает из головы, т.е. своеобразная очередь.
Здравствуйте, TepMuHyc, Вы писали:
TMH>Здравствуйте, BioUnit, Вы писали:
BU>Есть некоторый vector. Один поток добавляет элементы в его конец, а другой — выбирает из головы, т.е. своеобразная очередь.
TMH>...Тогда не вектор, а список — у него время добавления/удаления константное. TMH>Вот здесь ( http://www.rsdn.ru/Forum/Message.aspx?mid=27370&only=1
Да, действительно, список лучше.
Но вот вопрос: когда в очереди одно задание, один поток начинает его выбирать, а другой поток в этот момент добавляет очередное задание. Не произойдет ли чего-нибудь непредвиденного?
Здравствуйте, BioUnit, Вы писали:
BU>Но вот вопрос: когда в очереди одно задание, один поток начинает его выбирать, а другой поток в этот момент добавляет очередное задание. Не произойдет ли чего-нибудь непредвиденного?
Общепринято такое делать внутри именованного мутекса (и поиск в очереди кстати тоже)!
Здравствуйте, BioUnit, Вы писали:
BU>Есть некоторый vector. Один поток добавляет элементы в его конец, а другой — выбирает из головы, т.е. своеобразная очередь. Понимаю, что вариантов синхронзации может быть множество, но среди этого разнообразия хотелось бы получить самый оптимальный, ведь задача то тривиальная.
Встречный вопрос: выбор именно vector для организации этой очереди здесь окончательный?
Удаление элемента из начала вектора даст копирование почти всего содержимого на один эл-т к началу. Это и неоптимально по скорости и заставляет безусловно синхронизировать операции вставки и выемки элемента. Тут гораздо ближе либо deque (queue) либо list. Вопрос синхронизации останется и тут, но сама операция займет меньше времени и, соответственно, время простоя потока в ожидании доступа к очереди тоже сократится.
Здравствуйте, BioUnit, Вы писали:
BU>Но вот вопрос: когда в очереди одно задание, один поток начинает его выбирать, а другой поток в этот момент добавляет очередное задание.
TMH>Не произойдет ли чего-нибудь непредвиденного?
Обязательно произойдет
Но, коль скоро то сообщение это была иллюстрацией работы с семафором, то эта малозначащая деталь была опущена
____________________
God obviously didn't debug, hasn't done any maintenance, and no documentation can be found. Truly amateur work.
Здравствуйте, TepMuHyc, Вы писали:
TMH>Здравствуйте, BioUnit, Вы писали:
BU>Но вот вопрос: когда в очереди одно задание, один поток начинает его выбирать, а другой поток в этот момент добавляет очередное задание.
TMH>Не произойдет ли чего-нибудь непредвиденного? TMH>Обязательно произойдет TMH>Но, коль скоро то сообщение это была иллюстрацией работы с семафором, то эта малозначащая деталь была опущена
Именно эта "малозначащая деталь" меня и беспокоит от начала топика.
Здравствуйте, BioUnit, Вы писали:
BU>Но вот вопрос: когда в очереди одно задание, один поток начинает его выбирать, а другой поток в этот момент добавляет очередное задание. Не произойдет ли чего-нибудь непредвиденного?
Лучше не расчитывать на это. Посмотри, что написали сами разработчики о потокобезопасности:
simultaneous read access to the same container from within separate threads is safe;
simultaneous access to distinct containers (not shared between threads) is safe;
user must provide synchronization for all accesses if any thread may modify shared container.
Здравствуйте, BioUnit, Вы писали:
BU>Именно эта "малозначащая деталь" меня и беспокоит от начала топика.
Закрывать работу со списком мютексом надо ОБЯЗАТЕЛЬНО. Во избежание.
Причем именно мютексом а не Reader-Writer Lock'ом — т.к. и добавление и извлечение
элемента списка изменяет состояние этого списка.
____________________
God obviously didn't debug, hasn't done any maintenance, and no documentation can be found. Truly amateur work.
Здравствуйте, TepMuHyc, Вы писали:
TMH>Здравствуйте, vvaizh, Вы писали:
V>Общепринято такое делать внутри именованного мутекса TMH>А почему именно "именованного"?
да, ошибся, вданном случае неименованный мутекс лучше хранить прямо рядом со списком/вектором..
V>(и поиск в очереди кстати тоже)! TMH>Поиск, простите, в чем ?????
в контэйнере, или вы туда только класть хотите? а не читать?
Здравствуйте, Михаил Можаев, Вы писали:
BU>Но вот вопрос: когда в очереди одно задание, один поток начинает его выбирать, а другой поток в этот момент добавляет очередное задание. Не произойдет ли чего-нибудь непредвиденного?
ММ>Лучше не расчитывать на это. Посмотри, что написали сами разработчики о потокобезопасности:
ММ>Thread-safety for SGI STL: ММ>Thread safety (STLPort):
Именно с этого я и начал свои изыскания. И первично вопрос был как раз о том, как лучше организовать такую синхронизацию.
Видимо все склоняются к неименованному мьютексу...
Здравствуйте, Михаил Можаев, Вы писали:
ММ>Здравствуйте, vvaizh, Вы писали:
TMH>>Поиск, простите, в чем ????? V>в контэйнере, или вы туда только класть хотите? а не читать?
ММ>Чтобы прочитать первый элемент последовательного контейнера поиск не требуется. Или я что-то не понимаю?
Какая разница, чтение лучше тоже в мутекс загнать, даже первого элемента!
Для вектора — обязательно!
Для списка — если будут операции удаления..
А.. ещё вариант, что читать ту будешь точно уже после того как всё заполнено.. тогда действительно всё чисто..
Здравствуйте, BioUnit, Вы писали:
BU>Есть некоторый vector. Один поток добавляет элементы в его конец, а другой — выбирает из головы, т.е. своеобразная очередь.
Здравствуйте, TepMuHyc, Вы писали:
TMH>Здравствуйте, BioUnit, Вы писали:
BU>>Именно эта "малозначащая деталь" меня и беспокоит от начала топика. TMH>Закрывать работу со списком мютексом надо ОБЯЗАТЕЛЬНО. Во избежание. TMH>Причем именно мютексом а не Reader-Writer Lock'ом — т.к. и добавление и извлечение TMH>элемента списка изменяет состояние этого списка.
В случае списка, во избежание падения перфоманса, можно лочить только три элемента — тот который удаляется/вставляется и два его соседа. К остальным элементам доступ на чтение в это время можно разрешать.
Если это очередь — то лучше список. Ибо обращение к элементу означает также его удаление из очереди. Если это один процесс — то лучше юзать Critical Section
- Простите, профессор, не пса, а когда он уже был человеком.
— То-есть он говорил? Это еще не значит быть человеком. (с) Булгаков
Здравствуйте, small_cat, Вы писали:
SC>Здравствуйте, BioUnit, Вы писали:
SC>Если это очередь — то лучше список. Ибо обращение к элементу означает также его удаление из очереди. Если это один процесс — то лучше юзать Critical Section
Здравствуйте, jazzer, Вы писали:
J>Здравствуйте, BioUnit, Вы писали:
BU>Есть некоторый vector. Один поток добавляет элементы в его конец, а другой — выбирает из головы, т.е. своеобразная очередь.
J>Вот и воспользуйся очередью (std:deque)
Вопрос не в том, чем воспользоваться, можно и списком и очередью, а в том, как синхронизировать доступ. В STL это ложиться на плечи программера.
Здравствуйте, BioUnit, Вы писали:
BU>Вопрос не в том, чем воспользоваться, можно и списком и очередью, а в том, как синхронизировать доступ. В STL это ложиться на плечи программера.
кстати, о векторах. Для очереди не самый удачный выбор ввиду кривости операции извлечения из головы (точнее отсутсвия таковой операции). Поэтому ИМХО самый оптимальный вариант — std::queue + CRITICAL_SECTION
- Простите, профессор, не пса, а когда он уже был человеком.
— То-есть он говорил? Это еще не значит быть человеком. (с) Булгаков
Здравствуйте, BioUnit, Вы писали:
BU>Вопрос не в том, чем воспользоваться, можно и списком и очередью, а в том, как синхронизировать доступ. В STL это ложиться на плечи программера.
В общем вы правы, но... немного связаны эти два вопроса — синхронизация и что использовать. Список (std::list) синхронизовать проще, я уже писал что надо лочить тока 3 элемента при изменении. С тем же вектором придется лочить намного больше (например при удалении элемента из середины)
Здравствуйте, Дмитрий Наумов, Вы писали:
ДН>В общем вы правы, но... немного связаны эти два вопроса — синхронизация и что использовать. Список (std::list) синхронизовать проще, я уже писал что надо лочить тока 3 элемента при изменении. С тем же вектором придется лочить намного больше (например при удалении элемента из середины)
Что то не понятно. А зачем в очереди лочить что либо кроме хвоста и головы?
Здравствуйте, small_cat, Вы писали:
ДН>>В общем вы правы, но... немного связаны эти два вопроса — синхронизация и что использовать. Список (std::list) синхронизовать проще, я уже писал что надо лочить тока 3 элемента при изменении. С тем же вектором придется лочить намного больше (например при удалении элемента из середины)
SC>Что то не понятно. А зачем в очереди лочить что либо кроме хвоста и головы? <...> SC>Ну или типа того... Зачем остальные элементы лочить?
Я писал про вектор, с вектором ваш номер не пройдет
Здравствуйте, Дмитрий Наумов, Вы писали:
ДН>В общем вы правы, но... немного связаны эти два вопроса — синхронизация и что использовать. Список (std::list) синхронизовать проще, я уже писал что надо лочить тока 3 элемента при изменении. С тем же вектором придется лочить намного больше (например при удалении элемента из середины)
И голова, и хвост списка (std::list) связаны с самим объектом-контейнером.
Так что для запихивания-выпихивания придется лочить контейнер как таковой.
Лочить внутреннее устройство контейнера — дело неблагодарное (не переписывать же STL, тем более, что у каждого поставщика он устроен по-разному).
Другое дело, что время запихивания-выпихивания у std::list и std::deque порядка O(1), а у std::vector — до O(N).
Можно, однако, сделать так: отдать права на модификацию очереди только пишущему потоку.
Читающий поток только отмечает, какие элементы он прочел. А пишущий, помимо заталкивания в очередь, периодически очищает ее.
Это даст рост производительности, но усложнит систему.
Здравствуйте, Кодт, Вы писали:
К>Лочить внутреннее устройство контейнера — дело неблагодарное (не переписывать же STL, тем более, что у каждого поставщика он устроен по-разному).
Если очень важна производительность да и только в одном контейнере, то это вполне оправдно.
Здравствуйте, Дмитрий Наумов, Вы писали:
ДН>В случае списка, во избежание падения перфоманса, можно лочить только три элемента — тот который удаляется/вставляется и два его соседа. К остальным элементам доступ на чтение в это время можно разрешать.
Теперь осталось только вспомнить, что у двусвязного списка соседом и головы, и хвоста является фиктивный узел, принадлежащий контейнеру... А в реализации STL от Dinkumware — это один и тот же узел. И поймем, что лочить придется все одним махом.
Либо делать свой контейнер с известной структурой.
Здравствуйте, Кодт, Вы писали:
К>Теперь осталось только вспомнить, что у двусвязного списка соседом и головы, и хвоста является фиктивный узел, принадлежащий контейнеру... А в реализации STL от Dinkumware — это один и тот же узел. И поймем, что лочить придется все одним махом.
Почему? ИМХО, не во всех случаях. Если вставляет/удаляется элемент из/в середину то можно обойтись моим способом. Если же этот финт проделываем с первым/последним элементом то лочим (для первого элемента) соседа справа, сам первый элемент и последний элемент... Разве я не прав?
Здравствуйте, Дмитрий Наумов, Вы писали:
К>>Теперь осталось только вспомнить, что у двусвязного списка соседом и головы, и хвоста является фиктивный узел, принадлежащий контейнеру... А в реализации STL от Dinkumware — это один и тот же узел. И поймем, что лочить придется все одним махом.
ДН>Почему? ИМХО, не во всех случаях. Если вставляет/удаляется элемент из/в середину то можно обойтись моим способом. Если же этот финт проделываем с первым/последним элементом то лочим (для первого элемента) соседа справа, сам первый элемент и последний элемент... Разве я не прав?
Но мы же говорили про очередь... Зачем работать с серединой списка?
TMH>Закрывать работу со списком мютексом надо ОБЯЗАТЕЛЬНО. Во избежание...
skip
В случае списка, во избежание падения перфоманса, можно лочить только три элемента — тот который ...
Если все же подразумевалось использование списка (std::list) для организации очереди без доступа к середине, то я извиняюсь за то что не врубился и полез в тему.
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, Дмитрий Наумов, Вы писали:
К>>>Теперь осталось только вспомнить, что у двусвязного списка соседом и головы, и хвоста является фиктивный узел, принадлежащий контейнеру... А в реализации STL от Dinkumware — это один и тот же узел. И поймем, что лочить придется все одним махом.
ДН>>Почему? ИМХО, не во всех случаях. Если вставляет/удаляется элемент из/в середину то можно обойтись моим способом. Если же этот финт проделываем с первым/последним элементом то лочим (для первого элемента) соседа справа, сам первый элемент и последний элемент... Разве я не прав?
А что если вбить в начало списка фиктивный элемент, таким образом можно будет выбирать из псевдоголовы (где псевдоголова будет след. за фиктивным элементом) и добавлять в конец без взаимных локов, то есть одновременно. А?
Здравствуйте, Дмитрий Наумов, Вы писали:
ДН>А что если вбить в начало списка фиктивный элемент, таким образом можно будет выбирать из псевдоголовы (где псевдоголова будет след. за фиктивным элементом) и добавлять в конец без взаимных локов, то есть одновременно. А?
Прикольный способ!
Однако остается возможность того, что следующий за (псевдо)головой элемент — это (псевдо)хвост.
Поэтому, либо у каждого элемента будет свой собственный мутекс, либо опять придется лочить всю систему.
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, Дмитрий Наумов, Вы писали:
ДН>>А что если вбить в начало списка фиктивный элемент, таким образом можно будет выбирать из псевдоголовы (где псевдоголова будет след. за фиктивным элементом) и добавлять в конец без взаимных локов, то есть одновременно. А?
К>Прикольный способ! К>Однако остается возможность того, что следующий за (псевдо)головой элемент — это (псевдо)хвост. К>Поэтому, либо у каждого элемента будет свой собственный мутекс, либо опять придется лочить всю систему.
К>
Я бы не так сказал, весь список будет залочен (нужно лочить) в случае если очередь пуста, то есть след. элемент за псевдоголовой это хвост. В остальных же случаях будет лучше. ИМХО, это прикольней чем просто напрямую лочить одним мутексом( или whatever you choose) весь список.
Здравствуйте, BioUnit, Вы писали:
BU>Есть некоторый vector. Один поток добавляет элементы в его конец, а другой — выбирает из головы, т.е. своеобразная очередь. Понимаю, что вариантов синхронзации может быть множество, но среди этого разнообразия хотелось бы получить самый оптимальный, ведь задача то тривиальная.
А почему бы не воспользоватся очередью сообщений из Windows да и вдругих есть аналоги. Собственно проблема синхронизации там уже решена. Или пайпом или еще чем-нибудь. Способов достаточно. Или нужна именно мультиплатформенности и именно STL?
Здравствуйте, BioUnit, Вы писали:
BU>Да, действительно, список лучше. BU>Но вот вопрос: когда в очереди одно задание, один поток начинает его выбирать, а другой поток в этот момент добавляет очередное задание. Не произойдет ли чего-нибудь непредвиденного?
Обязательно произойдет
Вообще в стандарте ничего не написано по поводу многопоточности STL
так что она НЕ многопоточная.
Надо смотреть конкретные реализации.
Но вот в STL Port например есть некая документация по этому поводу.
Заявляется что сколько угодно потоков могут читать из контейнера,
(использовать константные функции), но когда начинаешь его изменять
надо синхрогизировать.
Остальные реализации возможно так же возможно хуже.
Любая проблема дизайна может быть решена введением дополнительного абстрактного слоя, за исключением проблемы слишком большого количества дополнительных абстрактных слоев
Re[7]: vector и многопоточность
От:
Аноним
Дата:
22.04.03 14:38
Оценка:
Здравствуйте, Дмитрий Наумов, Вы писали:
ДН>В случае списка, во избежание падения перфоманса, можно лочить только три элемента — тот который удаляется/вставляется и два его соседа. К остальным элементам доступ на чтение в это время можно разрешать.
Здравствуйте, BioUnit, Вы писали:
BU>Есть некоторый vector. Один поток добавляет элементы в его конец, а другой — выбирает из головы, т.е. своеобразная очередь.
Не "своеобразная очередь" а просто очередь. То что вы описали — классическая задача "читатели-писатели" с одним разделяемым ресурсом — очередью. Давно решена и описана в книжках по операционным системам. Смотрите из современных Таненбаум "Современные операционные системы" — серия "Классика computer science" или Столлингс "Операционные системы". Там она детально описана с использованием семафоров, но можно использовать и mutex в Win32
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Здравствуйте, <Аноним>, Вы писали:
ДН>>В случае списка, во избежание падения перфоманса, можно лочить только три элемента — тот который удаляется/вставляется и два его соседа. К остальным элементам доступ на чтение в это время можно разрешать.
А>как это предполагается реализовать технически?
Павел, подскажите пожалуйста, вот например я отправил сообщение, потом смотрю там, например, ошибка, опечатка, не дописал что то, или просто избыточное цитирование забыл удалить (как в моем случае) — какие у меня есть возможности исправить? Модерирование вроде позволяет только убить сообщение...
Здравствуйте, Дмитрий Наумов, Вы писали:
ДН> Павел, подскажите пожалуйста, вот например я отправил сообщение, ДН> потом смотрю там, например, ошибка, опечатка, не дописал что то, или ДН> просто избыточное цитирование забыл удалить (как в моем случае) - ДН> какие у меня есть возможности исправить?
К сожалению, в настоящий момент редактирование сообщений доступно только
модераторам. Тем не менее, возможность внести исправления в собственное
сообщение имеется: достаточно написать на
с обязательным указанием ссылки на сообщение и желаемых изменений,
либо же ответить на собственное сообщение с указанием необходимых исправлений.
В случае запроса через кто-нибудь из
модераторов внесет исправления, как только позволит время; пользоваться
этой возможностью следует, если допущена грубая ошибка, требующая скорейшего
исправления.
В случае ответа на собственное сообщение исправления будут внесены в порядке
обычного модерирования форумов, т.е. обычно чуть медленнее, чем через почту;
существенным плюсом является то, что исправления видны читателям, даже если
модератор еще не исправил оригинальное сообщение, кроме того, подобные
изменения видны тем, кто читает форум через почту или nntp.
Posted via RSDN NNTP Server 1.5 beta
Легче одурачить людей, чем убедить их в том, что они одурачены. — Марк Твен
Здравствуйте, Павел Кузнецов, Вы писали:
ДН>> избыточное цитирование забыл удалить
P.S. В случае избыточного цитирования наиболее подходящими вариантами
являются удаление собственного сообщения ("удалить как ошибочное")
с последующим размещением исправленного варианта, либо же письмо на . С другой стороны, в большинстве случаев, избыточное
цитирование не является проблемой, требующей срочного вмешательства, и, скорее
всего, модератор и без этого поправит его при очередном просмотре форума.
Posted via RSDN NNTP Server 1.5 beta
Легче одурачить людей, чем убедить их в том, что они одурачены. — Марк Твен
Здравствуйте, Павел Кузнецов, Вы писали:
ПК>С другой стороны, в большинстве случаев, избыточное ПК>цитирование не является проблемой, требующей срочного вмешательства, и, скорее ПК>всего, модератор и без этого поправит его при очередном просмотре форума.
Он то поправит... с вынесением предупреждения и лишением сладкого...
Здравствуйте, Дмитрий Наумов, Вы писали:
ДН> Он то поправит... с вынесением предупреждения и лишением сладкого...
Тогда пиши в
Гарантирую: никаких предупреждений и лишения сладкого не будет.
Posted via RSDN NNTP Server 1.5 beta
Легче одурачить людей, чем убедить их в том, что они одурачены. — Марк Твен
Re[9]: vector и многопоточность
От:
Аноним
Дата:
23.04.03 14:21
Оценка:
Здравствуйте, Дмитрий Наумов, Вы писали:
ДН>>В случае списка, во избежание падения перфоманса, можно лочить только три элемента — тот который удаляется/вставляется и два его соседа. К остальным элементам доступ на чтение в это время можно разрешать.
А>как это предполагается реализовать технически?
ДН>А в чем проблема? Никаких трудностей не вижу...
не понимаю я, как одновременно залочить ровно три эл-та из произвольного множества. может объяснишь?
если лочить их не одновременно, получишь потенциальный дедлок.
Здравствуйте, <Аноним>, Вы писали:
А>не понимаю я, как одновременно залочить ровно три эл-та из произвольного множества. может объяснишь? А>если лочить их не одновременно, получишь потенциальный дедлок.
Если лочить их везде в одном порядке, то никакого дедлока не будет.
... << RSDN@Home 1.0 beta 6a >>
Re[9]: vector и многопоточность
От:
Аноним
Дата:
23.04.03 14:51
Оценка:
Здравствуйте, Дмитрий Наумов, Вы писали:
ДН>А в чем проблема? Никаких трудностей не вижу...
Ну как же? Как проверять факт блокировки именно этих трех элементов? Для большинства приложений будет совершенно неадекватная "организационная" нагрузка. На нее можно пойти лишь если время блокировки значительно.
Удалено избыточное цитирование. -- ПК.
Re[11]: vector и многопоточность
От:
Аноним
Дата:
24.04.03 11:34
Оценка:
Здравствуйте, Михаил Можаев, Вы писали:
ММ>Здравствуйте, <Аноним>, Вы писали:
А>не понимаю я, как одновременно залочить ровно три эл-та из произвольного множества. может объяснишь? А>если лочить их не одновременно, получишь потенциальный дедлок.
ММ>Если лочить их везде в одном порядке, то никакого дедлока не будет.
у тебя есть куча тредов, вставляющих эл-ты в список. как они должны лочить нужные им эл-ты, чтобы избежать дедлоков?
Здравствуйте, <Аноним>, Вы писали:
ММ>>Если лочить их везде в одном порядке, то никакого дедлока не будет. А>у тебя есть куча тредов, вставляющих эл-ты в список. как они должны лочить нужные им эл-ты, чтобы избежать дедлоков?
Если эти потоки меняют состав множества, то, думаю, не получится.
Если бы состав множества (кол-во и порядок элементов в нем) не менялся, то все было бы просто.
Я имел в виду именно второй случай.