есть однонаправленый список
элементы в него добавляются ассинхронно
есть ещё два источника проверок и удаления элементов из списка: ассинхронный и синхронный
Синхронный не дает жить элементам в списке дольше 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/
кто знает, что здесь интеррестного и для чего создавался?

Имхо, тебе надо блокировать весь список при каждой операции (добавление, проверка, удаление). Причем, если проверка показала, что надо удалить, то удаление должно происходить без разблокирования.

Думал я уже про это, но блокировка всего списка влечет зависание системы в целом :(

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

1) А если воспользоваться какими-то флагами, например  и выставлять его перед удалением. А в другой функции проверять его. 

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

Rockie, со списками очень сложно.
Смотри.
вот процесс удаления нашел, что надо удалить элемент N. Для этого надо в элементе (N-1) поменять указатель. В этот момент обработчик доходит до элемента (N-1) и получает указатель на N. Процесс удаления меняет указатель на (N+1) и выполняет операцию delete для N. Обработчик переходит по ссылке на уже удаленный N... Дальше надо объяснять?

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

bsa, вот отлично понял моё опасение:

а то мне простым языком объяснить не получалось

---------------
есть ещё мысль создать контролера удалений: т.е. помечать какой элемент надо удалять, затем раз в секунду блокировать спикок и чистить - такой аля сборщик мусора, но как то не дорос.

думаем дальше...

ЗЫ 
хотя если в ассинхронном помечать на удаление, а в синхронном удалять...
хм, синхронный удалил, а ассинхронный просматривает уже удаленный, всё таже проблема. 

Может тебе подойдет очередь (queue, например), а не список?

мысль. Потоки ничего не удаляют, просто формируют список кандидатов на удаление, в отдельный список, в основном перебивают линки. С некоторой периодичностью списки блокируются, уничтожаем список кандидатов на удаление -> на следущую итерацию

Поясни что есть queue
список нужен как временное хранилище данных, структура данных одна, но вот ячеек от нуля и до бесконечности теорретически.
время жизни у разных объектов разное
ассинхронное(ые) событие может не прийти, может придти но не удалить элемент

queue - это очередь. В частности, FIFO (первым пришел, первым уйдешь). Правда, надо иметь в виду, что там только два вида деятельности - добавление в конец и чтение+удаление с начала. Поэтому только 2 потока возможны, добавляющий и обработчик/удалятель.

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

А зачем отдельный список, если можно каждому узлу добавить поле "кандидат на удаление" и в обработчике просто пропускать эти узлы. А удалять как предложил zkv, время от времени(например переводить обработчик в режим ожидания, удалять ненужные узлы и возвращать обработчик из sleep-а).

понял,
короче у меня очередь FISOLW first in some out last wait  

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


можно, но думаю дешевле будет отдельный список формировать, иначе, боюсь, слишком много лишних проверок будет (на удален или нет будет проверяться каждый элемент, при каждом проходе)