Re[10]: vector и многопоточность
От: Дмитрий Наумов  
Дата: 22.04.03 10:44
Оценка: 13 (1)
Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, Дмитрий Наумов, Вы писали:


К>>>Теперь осталось только вспомнить, что у двусвязного списка соседом и головы, и хвоста является фиктивный узел, принадлежащий контейнеру... А в реализации STL от Dinkumware — это один и тот же узел. И поймем, что лочить придется все одним махом.


ДН>>Почему? ИМХО, не во всех случаях. Если вставляет/удаляется элемент из/в середину то можно обойтись моим способом. Если же этот финт проделываем с первым/последним элементом то лочим (для первого элемента) соседа справа, сам первый элемент и последний элемент... Разве я не прав?


А что если вбить в начало списка фиктивный элемент, таким образом можно будет выбирать из псевдоголовы (где псевдоголова будет след. за фиктивным элементом) и добавлять в конец без взаимных локов, то есть одновременно. А?
... << RSDN@Home 1.0 beta 6a >>
Re[4]: vector и многопоточность
От: Кодт Россия  
Дата: 22.04.03 09:33
Оценка: 1 (1)
Здравствуйте, Дмитрий Наумов, Вы писали:

ДН>В общем вы правы, но... немного связаны эти два вопроса — синхронизация и что использовать. Список (std::list) синхронизовать проще, я уже писал что надо лочить тока 3 элемента при изменении. С тем же вектором придется лочить намного больше (например при удалении элемента из середины)


И голова, и хвост списка (std::list) связаны с самим объектом-контейнером.
Так что для запихивания-выпихивания придется лочить контейнер как таковой.

Лочить внутреннее устройство контейнера — дело неблагодарное (не переписывать же STL, тем более, что у каждого поставщика он устроен по-разному).

Другое дело, что время запихивания-выпихивания у std::list и std::deque порядка O(1), а у std::vector — до O(N).


Можно, однако, сделать так: отдать права на модификацию очереди только пишущему потоку.
Читающий поток только отмечает, какие элементы он прочел. А пишущий, помимо заталкивания в очередь, периодически очищает ее.
Это даст рост производительности, но усложнит систему.
... << RSDN@Home 1.0 beta 6a >>
Перекуём баги на фичи!
Re[3]: to [moderator]
От: Дмитрий Наумов  
Дата: 23.04.03 10:20
Оценка: :)
Здравствуйте, Павел Кузнецов, Вы писали:

ПК>С другой стороны, в большинстве случаев, избыточное

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

Он то поправит... с вынесением предупреждения и лишением сладкого...
... << RSDN@Home 1.0 beta 6a >>
Re[4]: to [moderator]
От: Павел Кузнецов  
Дата: 23.04.03 11:13
Оценка: :)
Здравствуйте, Дмитрий Наумов, Вы писали:

ДН> Он то поправит... с вынесением предупреждения и лишением сладкого...


Тогда пиши в
Гарантирую: никаких предупреждений и лишения сладкого не будет.
Posted via RSDN NNTP Server 1.5 beta
Легче одурачить людей, чем убедить их в том, что они одурачены. — Марк Твен
vector и многопоточность
От: BioUnit Россия  
Дата: 21.04.03 14:20
Оценка:
Есть некоторый vector. Один поток добавляет элементы в его конец, а другой — выбирает из головы, т.е. своеобразная очередь. Понимаю, что вариантов синхронзации может быть множество, но среди этого разнообразия хотелось бы получить самый оптимальный, ведь задача то тривиальная.
Re: vector и многопоточность
От: TepMuHyc  
Дата: 21.04.03 14:24
Оценка:
Здравствуйте, BioUnit, Вы писали:

BU>Есть некоторый vector. Один поток добавляет элементы в его конец, а другой — выбирает из головы, т.е. своеобразная очередь.


...Тогда не вектор, а список — у него время добавления/удаления константное.
Вот здесь ( http://www.rsdn.ru/Forum/Message.aspx?mid=27370&amp;only=1
Автор: TepMuHyc
Дата: 07.02.02
) описание алгоритма очереди.
____________________
God obviously didn't debug, hasn't done any maintenance, and no documentation can be found. Truly amateur work.
Re[2]: vector и многопоточность
От: BioUnit Россия  
Дата: 21.04.03 14:39
Оценка:
Здравствуйте, TepMuHyc, Вы писали:

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


BU>Есть некоторый vector. Один поток добавляет элементы в его конец, а другой — выбирает из головы, т.е. своеобразная очередь.


TMH>...Тогда не вектор, а список — у него время добавления/удаления константное.

TMH>Вот здесь ( http://www.rsdn.ru/Forum/Message.aspx?mid=27370&amp;only=1
Автор: TepMuHyc
Дата: 07.02.02
) описание алгоритма очереди.


Да, действительно, список лучше.
Но вот вопрос: когда в очереди одно задание, один поток начинает его выбирать, а другой поток в этот момент добавляет очередное задание. Не произойдет ли чего-нибудь непредвиденного?
Re[3]: vector и многопоточность
От: vvaizh http://izh-test.sourceforge.net/
Дата: 21.04.03 14:40
Оценка:
Здравствуйте, BioUnit, Вы писали:

BU>Но вот вопрос: когда в очереди одно задание, один поток начинает его выбирать, а другой поток в этот момент добавляет очередное задание. Не произойдет ли чего-нибудь непредвиденного?


Общепринято такое делать внутри именованного мутекса (и поиск в очереди кстати тоже)!

Удалено избыточное цитирование. -- ПК.
http://izh-test.sourceforge.net/russian/introduction.html
Re: vector и многопоточность
От: Михаил Можаев Россия www.mozhay.chat.ru
Дата: 21.04.03 14:42
Оценка:
Здравствуйте, BioUnit, Вы писали:

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


Встречный вопрос: выбор именно vector для организации этой очереди здесь окончательный?

Удаление элемента из начала вектора даст копирование почти всего содержимого на один эл-т к началу. Это и неоптимально по скорости и заставляет безусловно синхронизировать операции вставки и выемки элемента. Тут гораздо ближе либо deque (queue) либо list. Вопрос синхронизации останется и тут, но сама операция займет меньше времени и, соответственно, время простоя потока в ожидании доступа к очереди тоже сократится.
... << RSDN@Home 1.0 beta 6a >>
Re[4]: vector и многопоточность
От: Михаил Можаев Россия www.mozhay.chat.ru
Дата: 21.04.03 14:47
Оценка:
Здравствуйте, vvaizh, Вы писали:

V>Общепринято такое делать внутри именованного мутекса (и поиск в очереди кстати тоже)!


Можно и неименованным обойтись...
... << RSDN@Home 1.0 beta 6a >>
Re[3]: vector и многопоточность
От: TepMuHyc  
Дата: 21.04.03 14:48
Оценка:
Здравствуйте, BioUnit, Вы писали:

BU>Но вот вопрос: когда в очереди одно задание, один поток начинает его выбирать, а другой поток в этот момент добавляет очередное задание.


TMH>Не произойдет ли чего-нибудь непредвиденного?

Обязательно произойдет
Но, коль скоро то сообщение это была иллюстрацией работы с семафором, то эта малозначащая деталь была опущена
____________________
God obviously didn't debug, hasn't done any maintenance, and no documentation can be found. Truly amateur work.
Re[4]: vector и многопоточность
От: TepMuHyc  
Дата: 21.04.03 14:50
Оценка:
Здравствуйте, vvaizh, Вы писали:


V>Общепринято такое делать внутри именованного мутекса

А почему именно "именованного"?

V>(и поиск в очереди кстати тоже)!

Поиск, простите, в чем ?????
____________________
God obviously didn't debug, hasn't done any maintenance, and no documentation can be found. Truly amateur work.
Re[4]: vector и многопоточность
От: BioUnit Россия  
Дата: 21.04.03 14:50
Оценка:
Здравствуйте, TepMuHyc, Вы писали:

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


BU>Но вот вопрос: когда в очереди одно задание, один поток начинает его выбирать, а другой поток в этот момент добавляет очередное задание.


TMH>Не произойдет ли чего-нибудь непредвиденного?

TMH>Обязательно произойдет
TMH>Но, коль скоро то сообщение это была иллюстрацией работы с семафором, то эта малозначащая деталь была опущена

Именно эта "малозначащая деталь" меня и беспокоит от начала топика.
Re[3]: vector и многопоточность
От: Михаил Можаев Россия www.mozhay.chat.ru
Дата: 21.04.03 14:57
Оценка:
Здравствуйте, BioUnit, Вы писали:

BU>Но вот вопрос: когда в очереди одно задание, один поток начинает его выбирать, а другой поток в этот момент добавляет очередное задание. Не произойдет ли чего-нибудь непредвиденного?


Лучше не расчитывать на это. Посмотри, что написали сами разработчики о потокобезопасности:

Thread-safety for SGI STL:

...
Client must lock shared mutable containers
...


Thread safety (STLPort):


Причем, это для любого контейнера...
... << RSDN@Home 1.0 beta 6a >>
Re[5]: vector и многопоточность
От: TepMuHyc  
Дата: 21.04.03 14:58
Оценка:
Здравствуйте, BioUnit, Вы писали:

BU>Именно эта "малозначащая деталь" меня и беспокоит от начала топика.

Закрывать работу со списком мютексом надо ОБЯЗАТЕЛЬНО. Во избежание.
Причем именно мютексом а не Reader-Writer Lock'ом — т.к. и добавление и извлечение
элемента списка изменяет состояние этого списка.
____________________
God obviously didn't debug, hasn't done any maintenance, and no documentation can be found. Truly amateur work.
Re[5]: vector и многопоточность
От: vvaizh http://izh-test.sourceforge.net/
Дата: 21.04.03 14:59
Оценка:
Здравствуйте, TepMuHyc, Вы писали:

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



V>Общепринято такое делать внутри именованного мутекса

TMH>А почему именно "именованного"?
да, ошибся, вданном случае неименованный мутекс лучше хранить прямо рядом со списком/вектором..

V>(и поиск в очереди кстати тоже)!

TMH>Поиск, простите, в чем ?????
в контэйнере, или вы туда только класть хотите? а не читать?
http://izh-test.sourceforge.net/russian/introduction.html
Re[6]: vector и многопоточность
От: Михаил Можаев Россия www.mozhay.chat.ru
Дата: 21.04.03 15:07
Оценка:
Здравствуйте, vvaizh, Вы писали:

TMH>>Поиск, простите, в чем ?????

V>в контэйнере, или вы туда только класть хотите? а не читать?

Чтобы прочитать первый элемент последовательного контейнера поиск не требуется. Или я что-то не понимаю?
... << RSDN@Home 1.0 beta 6a >>
Re[4]: vector и многопоточность
От: BioUnit Россия  
Дата: 21.04.03 15:10
Оценка:
Здравствуйте, Михаил Можаев, Вы писали:

BU>Но вот вопрос: когда в очереди одно задание, один поток начинает его выбирать, а другой поток в этот момент добавляет очередное задание. Не произойдет ли чего-нибудь непредвиденного?


ММ>Лучше не расчитывать на это. Посмотри, что написали сами разработчики о потокобезопасности:


ММ>Thread-safety for SGI STL:

ММ>Thread safety (STLPort):

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

Удалено избыточное цитирование. -- ПК.
Re[7]: vector и многопоточность
От: vvaizh http://izh-test.sourceforge.net/
Дата: 21.04.03 15:12
Оценка:
Здравствуйте, Михаил Можаев, Вы писали:

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


TMH>>Поиск, простите, в чем ?????

V>в контэйнере, или вы туда только класть хотите? а не читать?

ММ>Чтобы прочитать первый элемент последовательного контейнера поиск не требуется. Или я что-то не понимаю?



Какая разница, чтение лучше тоже в мутекс загнать, даже первого элемента!
Для вектора — обязательно!
Для списка — если будут операции удаления..

А.. ещё вариант, что читать ту будешь точно уже после того как всё заполнено.. тогда действительно всё чисто..
http://izh-test.sourceforge.net/russian/introduction.html
Re[5]: vector и многопоточность
От: vvaizh http://izh-test.sourceforge.net/
Дата: 21.04.03 15:13
Оценка:
BU>Видимо все склоняются к неименованному мьютексу...

Я предлагаю вынести это в голосование..
http://izh-test.sourceforge.net/russian/introduction.html
Re: vector и многопоточность
От: jazzer Россия Skype: enerjazzer
Дата: 21.04.03 17:22
Оценка:
Здравствуйте, BioUnit, Вы писали:

BU>Есть некоторый vector. Один поток добавляет элементы в его конец, а другой — выбирает из головы, т.е. своеобразная очередь.


Вот и воспользуйся очередью (std:deque)
jazzer (Skype: enerjazzer) Ночная тема для RSDN
Автор: jazzer
Дата: 26.11.09

You will always get what you always got
  If you always do  what you always did
Re[6]: vector и многопоточность
От: Дмитрий Наумов  
Дата: 22.04.03 06:54
Оценка:
Здравствуйте, TepMuHyc, Вы писали:

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


BU>>Именно эта "малозначащая деталь" меня и беспокоит от начала топика.

TMH>Закрывать работу со списком мютексом надо ОБЯЗАТЕЛЬНО. Во избежание.
TMH>Причем именно мютексом а не Reader-Writer Lock'ом — т.к. и добавление и извлечение
TMH>элемента списка изменяет состояние этого списка.

В случае списка, во избежание падения перфоманса, можно лочить только три элемента — тот который удаляется/вставляется и два его соседа. К остальным элементам доступ на чтение в это время можно разрешать.
... << RSDN@Home 1.0 beta 6a >>
Re: vector и многопоточность
От: small_cat Россия  
Дата: 22.04.03 07:00
Оценка:
Здравствуйте, BioUnit, Вы писали:

Если это очередь — то лучше список. Ибо обращение к элементу означает также его удаление из очереди. Если это один процесс — то лучше юзать Critical Section
- Простите, профессор, не пса, а когда он уже был человеком.
— То-есть он говорил? Это еще не значит быть человеком. (с) Булгаков
Re[2]: vector и многопоточность
От: Дмитрий Наумов  
Дата: 22.04.03 07:03
Оценка:
Здравствуйте, small_cat, Вы писали:

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


SC>Если это очередь — то лучше список. Ибо обращение к элементу означает также его удаление из очереди. Если это один процесс — то лучше юзать Critical Section


Что вы этим хотели сказать?
... << RSDN@Home 1.0 beta 6a >>
Re[3]: vector и многопоточность
От: small_cat Россия  
Дата: 22.04.03 07:08
Оценка:
Здравствуйте, Дмитрий Наумов, Вы писали:

В смысле аналогично стеку. Типа Push/pop.
- Простите, профессор, не пса, а когда он уже был человеком.
— То-есть он говорил? Это еще не значит быть человеком. (с) Булгаков
Re[2]: vector и многопоточность
От: BioUnit Россия  
Дата: 22.04.03 07:27
Оценка:
Здравствуйте, jazzer, Вы писали:

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


BU>Есть некоторый vector. Один поток добавляет элементы в его конец, а другой — выбирает из головы, т.е. своеобразная очередь.


J>Вот и воспользуйся очередью (std:deque)


Вопрос не в том, чем воспользоваться, можно и списком и очередью, а в том, как синхронизировать доступ. В STL это ложиться на плечи программера.
Re[3]: vector и многопоточность
От: small_cat Россия  
Дата: 22.04.03 07:32
Оценка:
Здравствуйте, BioUnit, Вы писали:

BU>Вопрос не в том, чем воспользоваться, можно и списком и очередью, а в том, как синхронизировать доступ. В STL это ложиться на плечи программера.


кстати, о векторах. Для очереди не самый удачный выбор ввиду кривости операции извлечения из головы (точнее отсутсвия таковой операции). Поэтому ИМХО самый оптимальный вариант — std::queue + CRITICAL_SECTION
- Простите, профессор, не пса, а когда он уже был человеком.
— То-есть он говорил? Это еще не значит быть человеком. (с) Булгаков
Re[3]: vector и многопоточность
От: Дмитрий Наумов  
Дата: 22.04.03 07:36
Оценка:
Здравствуйте, BioUnit, Вы писали:

BU>Вопрос не в том, чем воспользоваться, можно и списком и очередью, а в том, как синхронизировать доступ. В STL это ложиться на плечи программера.


В общем вы правы, но... немного связаны эти два вопроса — синхронизация и что использовать. Список (std::list) синхронизовать проще, я уже писал что надо лочить тока 3 элемента при изменении. С тем же вектором придется лочить намного больше (например при удалении элемента из середины)
... << RSDN@Home 1.0 beta 6a >>
Re[4]: vector и многопоточность
От: small_cat Россия  
Дата: 22.04.03 07:54
Оценка:
Здравствуйте, Дмитрий Наумов, Вы писали:

ДН>В общем вы правы, но... немного связаны эти два вопроса — синхронизация и что использовать. Список (std::list) синхронизовать проще, я уже писал что надо лочить тока 3 элемента при изменении. С тем же вектором придется лочить намного больше (например при удалении элемента из середины)


Что то не понятно. А зачем в очереди лочить что либо кроме хвоста и головы?


template<class T> class CSafeQueue
{
    std::queue<T> myQueue;
    CRITICAL_SECTION cs;
public:    
    CSafeQueue(){InitializeCriticalSection(&cs);}
    CSafeQueue(){DeleteCriticalSection(&cs);}
    void Push_back(const T& elem){
                   EnterCriticalSection(&cs);
                   myQueue.push(elem);
                   LeaveCriticalSection(&cs);
    }
    void Pop_front(T& elem){
                   EnterCriticalSection(&cs);
                   elem = myQueue.front();
                   myQueue.pop();
                   LeaveCriticalSection(&cs);
    }
};

Ну или типа того... Зачем остальные элементы лочить?
- Простите, профессор, не пса, а когда он уже был человеком.
— То-есть он говорил? Это еще не значит быть человеком. (с) Булгаков
Re[5]: vector и многопоточность
От: Дмитрий Наумов  
Дата: 22.04.03 08:07
Оценка:
Здравствуйте, small_cat, Вы писали:

ДН>>В общем вы правы, но... немного связаны эти два вопроса — синхронизация и что использовать. Список (std::list) синхронизовать проще, я уже писал что надо лочить тока 3 элемента при изменении. С тем же вектором придется лочить намного больше (например при удалении элемента из середины)


SC>Что то не понятно. А зачем в очереди лочить что либо кроме хвоста и головы? <...>

SC>Ну или типа того... Зачем остальные элементы лочить?

Я писал про вектор, с вектором ваш номер не пройдет
... << RSDN@Home 1.0 beta 6a >>

Удалено избыточное цитирование. -- ПК.
Re[3]: vector и многопоточность
От: Павел Кузнецов  
Дата: 22.04.03 08:26
Оценка:
Здравствуйте, BioUnit, Вы писали:

B> как синхронизировать доступ. В STL это ложиться на плечи программера


В любом случае должна присутствовать внешняя синхронизация. См., например,
http://rsdn.ru/forum/Message.aspx?mid=104040
Автор: Павел Кузнецов
Дата: 22.09.02
Posted via RSDN NNTP Server 1.5 beta
Легче одурачить людей, чем убедить их в том, что они одурачены. — Марк Твен
Re[5]: vector и многопоточность
От: Anatoliy Elsukov Украина  
Дата: 22.04.03 09:40
Оценка:
Здравствуйте, Кодт, Вы писали:

К>Лочить внутреннее устройство контейнера — дело неблагодарное (не переписывать же STL, тем более, что у каждого поставщика он устроен по-разному).

Если очень важна производительность да и только в одном контейнере, то это вполне оправдно.
... << RSDN@Home 1.0 beta 6a >>
Re[7]: vector и многопоточность
От: Кодт Россия  
Дата: 22.04.03 09:42
Оценка:
Здравствуйте, Дмитрий Наумов, Вы писали:

ДН>В случае списка, во избежание падения перфоманса, можно лочить только три элемента — тот который удаляется/вставляется и два его соседа. К остальным элементам доступ на чтение в это время можно разрешать.


Теперь осталось только вспомнить, что у двусвязного списка соседом и головы, и хвоста является фиктивный узел, принадлежащий контейнеру... А в реализации STL от Dinkumware — это один и тот же узел. И поймем, что лочить придется все одним махом.

Либо делать свой контейнер с известной структурой.
      CONTAINER
BeforeHead  AfterTail
L=null R=H  L=T R=null

item_0
L=BeforeHead
R=item_1

item_1
L=item_0
R=item_2

...

item_N
L=item_N1
R=AfterTail
... << RSDN@Home 1.0 beta 6a >>
Перекуём баги на фичи!
Re[8]: vector и многопоточность
От: Дмитрий Наумов  
Дата: 22.04.03 09:56
Оценка:
Здравствуйте, Кодт, Вы писали:

К>Теперь осталось только вспомнить, что у двусвязного списка соседом и головы, и хвоста является фиктивный узел, принадлежащий контейнеру... А в реализации STL от Dinkumware — это один и тот же узел. И поймем, что лочить придется все одним махом.


Почему? ИМХО, не во всех случаях. Если вставляет/удаляется элемент из/в середину то можно обойтись моим способом. Если же этот финт проделываем с первым/последним элементом то лочим (для первого элемента) соседа справа, сам первый элемент и последний элемент... Разве я не прав?
... << RSDN@Home 1.0 beta 6a >>
Re[9]: vector и многопоточность
От: Кодт Россия  
Дата: 22.04.03 10:14
Оценка:
Здравствуйте, Дмитрий Наумов, Вы писали:

К>>Теперь осталось только вспомнить, что у двусвязного списка соседом и головы, и хвоста является фиктивный узел, принадлежащий контейнеру... А в реализации STL от Dinkumware — это один и тот же узел. И поймем, что лочить придется все одним махом.


ДН>Почему? ИМХО, не во всех случаях. Если вставляет/удаляется элемент из/в середину то можно обойтись моим способом. Если же этот финт проделываем с первым/последним элементом то лочим (для первого элемента) соседа справа, сам первый элемент и последний элемент... Разве я не прав?


Но мы же говорили про очередь... Зачем работать с серединой списка?
... << RSDN@Home 1.0 beta 6a >>
Перекуём баги на фичи!
Re[10]: vector и многопоточность
От: Дмитрий Наумов  
Дата: 22.04.03 10:36
Оценка:
Здравствуйте, Кодт, Вы писали:

TMH>Закрывать работу со списком мютексом надо ОБЯЗАТЕЛЬНО. Во избежание...


skip

В случае списка, во избежание падения перфоманса, можно лочить только три элемента — тот который ...


Если все же подразумевалось использование списка (std::list) для организации очереди без доступа к середине, то я извиняюсь за то что не врубился и полез в тему.
... << RSDN@Home 1.0 beta 6a >>
Re[11]: vector и многопоточность
От: Кодт Россия  
Дата: 22.04.03 10:54
Оценка:
Здравствуйте, Дмитрий Наумов, Вы писали:

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


Прикольный способ!
Однако остается возможность того, что следующий за (псевдо)головой элемент — это (псевдо)хвост.
Поэтому, либо у каждого элемента будет свой собственный мутекс, либо опять придется лочить всю систему.
... << RSDN@Home 1.0 beta 6a >>
Перекуём баги на фичи!
Re[12]: vector и многопоточность
От: Дмитрий Наумов  
Дата: 22.04.03 11:02
Оценка:
Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, Дмитрий Наумов, Вы писали:


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


К>Прикольный способ!

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

К>


Я бы не так сказал, весь список будет залочен (нужно лочить) в случае если очередь пуста, то есть след. элемент за псевдоголовой это хвост. В остальных же случаях будет лучше. ИМХО, это прикольней чем просто напрямую лочить одним мутексом( или whatever you choose) весь список.
... << RSDN@Home 1.0 beta 6a >>
Re: vector и многопоточность
От: adb Россия  
Дата: 22.04.03 12:20
Оценка:
Здравствуйте, BioUnit, Вы писали:

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


А почему бы не воспользоватся очередью сообщений из Windows да и вдругих есть аналоги. Собственно проблема синхронизации там уже решена. Или пайпом или еще чем-нибудь. Способов достаточно. Или нужна именно мультиплатформенности и именно STL?
Re: [moderator] vector и многопоточность
От: Павел Кузнецов  
Дата: 22.04.03 13:26
Оценка:
Подветка CriticalSection vs. Mutex
Автор: small_cat
Дата: 22.04.03
перенесена в WIN API.
Легче одурачить людей, чем убедить их в том, что они одурачены. — Марк Твен
Re[3]: vector и многопоточность
От: Anatolix Россия https://www.linkedin.com/in/anatolix/
Дата: 22.04.03 13:52
Оценка:
Здравствуйте, BioUnit, Вы писали:

BU>Да, действительно, список лучше.

BU>Но вот вопрос: когда в очереди одно задание, один поток начинает его выбирать, а другой поток в этот момент добавляет очередное задание. Не произойдет ли чего-нибудь непредвиденного?

Обязательно произойдет

Вообще в стандарте ничего не написано по поводу многопоточности STL
так что она НЕ многопоточная.

Надо смотреть конкретные реализации.
Но вот в STL Port например есть некая документация по этому поводу.
Заявляется что сколько угодно потоков могут читать из контейнера,
(использовать константные функции), но когда начинаешь его изменять
надо синхрогизировать.

Остальные реализации возможно так же возможно хуже.
Любая проблема дизайна может быть решена введением дополнительного абстрактного слоя, за исключением проблемы слишком большого количества дополнительных абстрактных слоев
Re[7]: vector и многопоточность
От: Аноним  
Дата: 22.04.03 14:38
Оценка:
Здравствуйте, Дмитрий Наумов, Вы писали:

ДН>В случае списка, во избежание падения перфоманса, можно лочить только три элемента — тот который удаляется/вставляется и два его соседа. К остальным элементам доступ на чтение в это время можно разрешать.


как это предполагается реализовать технически?

Удалено избыточное цитирование. -- ПК.
Re: vector и многопоточность
От: LaptevVV Россия  
Дата: 22.04.03 15:57
Оценка:
Здравствуйте, BioUnit, Вы писали:

BU>Есть некоторый vector. Один поток добавляет элементы в его конец, а другой — выбирает из головы, т.е. своеобразная очередь.


Не "своеобразная очередь" а просто очередь. То что вы описали — классическая задача "читатели-писатели" с одним разделяемым ресурсом — очередью. Давно решена и описана в книжках по операционным системам. Смотрите из современных Таненбаум "Современные операционные системы" — серия "Классика computer science" или Столлингс "Операционные системы". Там она детально описана с использованием семафоров, но можно использовать и mutex в Win32
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Re[8]: vector и многопоточность
От: Дмитрий Наумов  
Дата: 23.04.03 06:21
Оценка:
Здравствуйте, <Аноним>, Вы писали:

ДН>>В случае списка, во избежание падения перфоманса, можно лочить только три элемента — тот который удаляется/вставляется и два его соседа. К остальным элементам доступ на чтение в это время можно разрешать.


А>как это предполагается реализовать технически?


А в чем проблема? Никаких трудностей не вижу...
... << RSDN@Home 1.0 beta 6a >>
to [moderator]
От: Дмитрий Наумов  
Дата: 23.04.03 06:25
Оценка:
Павел, подскажите пожалуйста, вот например я отправил сообщение, потом смотрю там, например, ошибка, опечатка, не дописал что то, или просто избыточное цитирование забыл удалить (как в моем случае) — какие у меня есть возможности исправить? Модерирование вроде позволяет только убить сообщение...
... << RSDN@Home 1.0 beta 6a >>
Re: to [moderator]
От: Павел Кузнецов  
Дата: 23.04.03 07:19
Оценка:
Здравствуйте, Дмитрий Наумов, Вы писали:

ДН> Павел, подскажите пожалуйста, вот например я отправил сообщение,

ДН> потом смотрю там, например, ошибка, опечатка, не дописал что то, или
ДН> просто избыточное цитирование забыл удалить (как в моем случае) -
ДН> какие у меня есть возможности исправить?

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

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

В случае ответа на собственное сообщение исправления будут внесены в порядке
обычного модерирования форумов, т.е. обычно чуть медленнее, чем через почту;
существенным плюсом является то, что исправления видны читателям, даже если
модератор еще не исправил оригинальное сообщение, кроме того, подобные
изменения видны тем, кто читает форум через почту или nntp.
Posted via RSDN NNTP Server 1.5 beta
Легче одурачить людей, чем убедить их в том, что они одурачены. — Марк Твен
Re[2]: to [moderator]
От: Павел Кузнецов  
Дата: 23.04.03 07:25
Оценка:
Здравствуйте, Павел Кузнецов, Вы писали:

ДН>> избыточное цитирование забыл удалить


P.S. В случае избыточного цитирования наиболее подходящими вариантами
являются удаление собственного сообщения ("удалить как ошибочное")
с последующим размещением исправленного варианта, либо же письмо на
. С другой стороны, в большинстве случаев, избыточное
цитирование не является проблемой, требующей срочного вмешательства, и, скорее
всего, модератор и без этого поправит его при очередном просмотре форума.
Posted via RSDN NNTP Server 1.5 beta
Легче одурачить людей, чем убедить их в том, что они одурачены. — Марк Твен
Re[9]: vector и многопоточность
От: Аноним  
Дата: 23.04.03 14:21
Оценка:
Здравствуйте, Дмитрий Наумов, Вы писали:

ДН>>В случае списка, во избежание падения перфоманса, можно лочить только три элемента — тот который удаляется/вставляется и два его соседа. К остальным элементам доступ на чтение в это время можно разрешать.


А>как это предполагается реализовать технически?


ДН>А в чем проблема? Никаких трудностей не вижу...


не понимаю я, как одновременно залочить ровно три эл-та из произвольного множества. может объяснишь?
если лочить их не одновременно, получишь потенциальный дедлок.
Re[10]: vector и многопоточность
От: Михаил Можаев Россия www.mozhay.chat.ru
Дата: 23.04.03 14:33
Оценка:
Здравствуйте, <Аноним>, Вы писали:

А>не понимаю я, как одновременно залочить ровно три эл-та из произвольного множества. может объяснишь?

А>если лочить их не одновременно, получишь потенциальный дедлок.

Если лочить их везде в одном порядке, то никакого дедлока не будет.
... << RSDN@Home 1.0 beta 6a >>
Re[9]: vector и многопоточность
От: Аноним  
Дата: 23.04.03 14:51
Оценка:
Здравствуйте, Дмитрий Наумов, Вы писали:

ДН>А в чем проблема? Никаких трудностей не вижу...


Ну как же? Как проверять факт блокировки именно этих трех элементов? Для большинства приложений будет совершенно неадекватная "организационная" нагрузка. На нее можно пойти лишь если время блокировки значительно.

Удалено избыточное цитирование. -- ПК.
Re[11]: vector и многопоточность
От: Аноним  
Дата: 24.04.03 11:34
Оценка:
Здравствуйте, Михаил Можаев, Вы писали:

ММ>Здравствуйте, <Аноним>, Вы писали:


А>не понимаю я, как одновременно залочить ровно три эл-та из произвольного множества. может объяснишь?

А>если лочить их не одновременно, получишь потенциальный дедлок.

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


у тебя есть куча тредов, вставляющих эл-ты в список. как они должны лочить нужные им эл-ты, чтобы избежать дедлоков?
Re[12]: vector и многопоточность
От: Михаил Можаев Россия www.mozhay.chat.ru
Дата: 24.04.03 11:48
Оценка:
Здравствуйте, <Аноним>, Вы писали:

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

А>у тебя есть куча тредов, вставляющих эл-ты в список. как они должны лочить нужные им эл-ты, чтобы избежать дедлоков?

Если эти потоки меняют состав множества, то, думаю, не получится.
Если бы состав множества (кол-во и порядок элементов в нем) не менялся, то все было бы просто.
Я имел в виду именно второй случай.
... << RSDN@Home 1.0 beta 6a >>
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.