Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
Форум программистов > C/C++: Общие вопросы > Ассинхронное добавление, синхронное и ассинхронное |
Автор: neosapient 1.8.2007, 12:44 |
есть однонаправленый список элементы в него добавляются ассинхронно есть ещё два источника проверок и удаления элементов из списка: ассинхронный и синхронный Синхронный не дает жить элементам в списке дольше n секунд При этом синхронный проверяет список как можно чаще, но не чаще 0,1 секунды. Ассинхронный проверяет список по наступлению некоторого события, и может удалить элемент списка до истечения времени жизни. Как разграничить (синхронизировать) доступ к ячейкам списка? Боюсь за одновременную обработку и удаление (или множественное удаление) одного и того же элемента. Боюсь, что указатель взятый для обработки следующего эллемента, после возвращения управления в этот поток будет указывать на удаленную область. (два дня бьюсь ![]() ------------------ раньше было ассинхронное добавление и синхронное удаление раскажу как это происходило в старой концепции Ассинхронное добавление элементов с помощью функции Add если был список с началом в 1 1 2 3 то при Add(4) получим 4 1 2 3 а при следующем Add(5) получим 5 4 1 2 3 Синхронное удаление Check беру первый эллемент списка, проверяю и, если время вышло удаляю Допустим ассинхронно добавляется эллемент 6 получим 6 4 1 2 3 тогда следующим эллементом проверялся не 6, а 4, как следующий за 5 и его тоже удаляем получим 6 1 2 3 затем для проверки и удаления шел 1, как следующий за 4, но 1 пока рано удалять Допустим ассинхронно добавляется эллемент 7 получим 7 6 1 2 3 проверка (с возможным удалением) новых эллементов, ассинхронно добавленых на этом витке проверки, происходит только в новом витке, когда проверка элементов из предшествующего витка завершиться Вот такая была концепция теперь добавилось ассинхронное удаление и моя код в моей старой концепции не работает Есть идеи как организовать то же самое, с учетом ассинхронного удаления? Может кто видел исходник со схожим поведением, дайте, пожалуйста, посмотреть общую концепцию. ЗЫ оффтопик сделал ачепятку в одну букву, попал в какой-то поддомен http://forun.vingrad.ru/ кто знает, что здесь интеррестного и для чего создавался? |
Автор: bsa 1.8.2007, 13:14 |
Имхо, тебе надо блокировать весь список при каждой операции (добавление, проверка, удаление). Причем, если проверка показала, что надо удалить, то удаление должно происходить без разблокирования. |
Автор: neosapient 1.8.2007, 13:55 |
Думал я уже про это, но блокировка всего списка влечет зависание системы в целом :( Нужно чтоб разные ячейки списка обрабатылись одновременно, но при этом нужно избежать коллизий |
Автор: bsa 1.8.2007, 14:23 |
Rockie, со списками очень сложно. Смотри. вот процесс удаления нашел, что надо удалить элемент N. Для этого надо в элементе (N-1) поменять указатель. В этот момент обработчик доходит до элемента (N-1) и получает указатель на N. Процесс удаления меняет указатель на (N+1) и выполняет операцию delete для N. Обработчик переходит по ссылке на уже удаленный N... Дальше надо объяснять? Хотя с флагом это тоже вариант. В этом случае блокировать весь список надо только на момент фактического стирания/добавления. Но что-то мне подсказывает, что так легко это не решается. |
Автор: neosapient 1.8.2007, 14:40 | ||
bsa, вот отлично понял моё опасение:
а то мне простым языком объяснить не получалось --------------- есть ещё мысль создать контролера удалений: т.е. помечать какой элемент надо удалять, затем раз в секунду блокировать спикок и чистить - такой аля сборщик мусора, но как то не дорос. думаем дальше... ЗЫ хотя если в ассинхронном помечать на удаление, а в синхронном удалять... хм, синхронный удалил, а ассинхронный просматривает уже удаленный, всё таже проблема. |
Автор: bsa 1.8.2007, 14:51 |
Может тебе подойдет очередь (queue, например), а не список? |
Автор: zkv 1.8.2007, 14:54 |
мысль. Потоки ничего не удаляют, просто формируют список кандидатов на удаление, в отдельный список, в основном перебивают линки. С некоторой периодичностью списки блокируются, уничтожаем список кандидатов на удаление -> на следущую итерацию |
Автор: neosapient 1.8.2007, 14:57 |
Поясни что есть queue список нужен как временное хранилище данных, структура данных одна, но вот ячеек от нуля и до бесконечности теорретически. время жизни у разных объектов разное ассинхронное(ые) событие может не прийти, может придти но не удалить элемент |
Автор: bsa 1.8.2007, 15:32 |
http://www.sgi.com/tech/stl/queue.html - это очередь. В частности, FIFO (первым пришел, первым уйдешь). Правда, надо иметь в виду, что там только два вида деятельности - добавление в конец и чтение+удаление с начала. Поэтому только 2 потока возможны, добавляющий и обработчик/удалятель. О варианте с отдельным списком удаленных я думал уже - не выходит, если в какой-то момент обработчик попадет на объект, помещаемый в список удаленных, то дальше он пойдет уже по этому списку. |
Автор: Rockie 1.8.2007, 16:04 | ||
А зачем отдельный список, если можно каждому узлу добавить поле "кандидат на удаление" и в обработчике просто пропускать эти узлы. А удалять как предложил zkv, время от времени(например переводить обработчик в режим ожидания, удалять ненужные узлы и возвращать обработчик из sleep-а). |
Автор: neosapient 1.8.2007, 16:18 |
понял, короче у меня очередь FISOLW first in some out last wait ![]() |
Автор: zkv 1.8.2007, 19:41 | ||||
пусть идет, надо предусмотреть, чтобы в этом случае ниче5го страшного не случилось (кроме лишнего прохода по списку удаленных элементов), главное, что мы избежали обращения к освобожденной памяти.
можно, но думаю дешевле будет отдельный список формировать, иначе, боюсь, слишком много лишних проверок будет (на удален или нет будет проверяться каждый элемент, при каждом проходе) |