ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Vitaly Lugovsky                      2:5080/1003    16 Mar 2003  04:39:42
 To : Slava Astashonok
 Subject : Re: списки, деревья и multithreading
 -------------------------------------------------------------------------------- 
 

 Slava Astashonok <sla@0n.ru> wrote:
 
 > Может кто-нибудь поделиться опытом борьбы с динамическими списками и 
 > деревьями в многопотоковых программах, в которых несколько нитей могут 
 > одновременно добавлять/удалять данные? Какие именно проблемы при этом 
 > возникают я поясню на примере: предположим, наши данные представлены 
 > двусвязным списком и некоторая нить удаляет элемент n, связанный с n-1 и 
 > n+1. В первую очередь эта нить должна блокировать элемент n, а так как 
 > она будет модифицировать указатели в элементах n-1 и n+1, то ей еще 
 > нужно будет блокировать и эти элеметы. Предположим, что в этот момент 
 > другой нити вздумалось удалять элемент  n-1: она заблокировала его, n-2 
 > и остановилась при попытке блокировки n (он уже заблокирован). Первая 
 > нить продолжает работу и останавливается при попытке блокировки n-1. 
 > Получили deadlock.
 
  По mutex-у на элемент? А тухес не лопнет? Достаточно глобального лока.
 
 > Сейчас я использую способ, заключающийся в хранении данных в нескольких 
 > независимых списках, и блокирую любой из них по мере необходимости, 
 > однако я этим неудовлетворен. Тем более, что в дальнейшем списки я хочу 
 > заменить сбалансированным деревом. Hаклевывается еще один способ, но я с 
 > ним пока подожду.
 
  Очередь потребления, в которую процессы складывают запросы на вставку в
 дерево. Тот процесс, который очередь обрабатывает, на момент перезаписи его
 блокирует. Должно быть достаточно эффективным. Hо лучше подумать - а на фига
 вообще такое понадобилось, и не было ли обходного пути.
 
 --- ifmail v.2.15dev5
  * Origin: (http://news.cca.usart.ru/) USURT's FidoNET<-> (2:5080/1003@fidonet)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    списки, деревья и multithreading   Slava Astashonok   15 Mar 2003 18:12:13   списки, деревья и multithreading   Nick Poroshin   16 Mar 2003 01:28:59   Re: списки, деревья и multithreading   Vitaly Lugovsky   16 Mar 2003 04:39:42   Re: списки, деревья и multithreading   Slava Astashonok   16 Mar 2003 04:08:25   списки, деревья и multithreading   Alex Cvetkov   17 Mar 2003 02:23:01   Re: списки, деревья и multithreading   Slava Astashonok   17 Mar 2003 17:43:09   Re: списки, деревья и multithreading   Vitaly Lugovsky   17 Mar 2003 07:34:03   Re: списки, деревья и multithreading   Slava Astashonok   17 Mar 2003 18:48:38   Re: списки, деревья и multithreading   Sergey Andrianov   16 Mar 2003 17:51:40   Re: списки, деревья и multithreading   Slava Astashonok   19 Mar 2003 00:33:46   Re: списки, деревья и multithreading   Sergey Andrianov   26 Mar 2003 10:05:46