Справка по списку без блокировки!

Question

Привет, я пытаюсь написать список без блокировки. Я получил добавочную часть, работающую, как он думает, но код, который извлекает объекты из списка, не работает на пользу: (

Ну, список не является обычным списком .. У меня есть интерфейс IWorkItem

interface IWorkItem
{
    DateTime ExecuteTime { get; }
    bool Cancelled { get; }
    void Execute(DateTime now);
}

и у меня есть список, куда я могу добавить это: P, и идеар - это когда я запускаю Get (); в списке он должен зацикливаться до тех пор, пока не найдет IWorkItem, который

If (item.ExecuteTime < DateTime.Now)

, удалите его из списка и верните. я выполнил тесты со многими потоками на моем двухъядерном процессоре, и кажется, что Add works до сих пор не удавалось, но функция Get теряет некоторые рабочие элементы, некоторые из которых у меня нет ни малейшего представления о том, что не так .....

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

Код здесь http://www.easy -share.com / 1903474734 / LinkedList.zip и если вы попытаетесь запустить его, вы увидите, что иногда он не сможет получить столько рабочих элементов, сколько это внесло в список ...

Редактировать: у меня есть список без блокировки, работающий быстрее, чем с использованием блокировки (obj), но у меня есть объект блокировки, который использует Interlocked, который все еще превосходит список без блокировки, я собираюсь попытаться создать массив без блокировки и SE, если я получу те же результаты там, когда я закончил плохо загрузить результат здесь ..

Answer 1

Проблема в вашем алгоритме: рассмотрим следующую последовательность событий:

Тема 1 вызывает list.Add(workItem1), что завершается полностью.

Статус:

first=workItem1, workItem1.next = null

Затем поток 1 вызывает list.Add(workItem2) и достигает места прямо перед вторым Replace (где у вас есть комментарий "// Давайте попробуем").

Статус:

first=workItem1, workItem1.next = null, nextItem=workItem1

В этот момент поток 2 вступает во владение и вызывает list.Get(). Предположим, что workItem1 executeTime теперь, поэтому вызов завершается успешно и возвращает workItem1.

После этого статуса:

first = null, workItem1.next = null

(а в другом потоке nextItem по-прежнему workItem1).

Теперь мы возвращаемся к первому потоку, и он завершает Add(), устанавливая workItem1.next:=workItem2.

Если мы сейчас позвоним list.Get(), мы получим null, хотя Add() успешно завершено.

Вероятно, вам стоит поискать реальный проверенный алгоритм блокировки связанного списка без блокировок. Я думаю, что стандартным является это Джона Валуа. Здесь есть реализация C ++ здесь . Эта статья о приоритетных очередях без блокировки также может быть полезна.

Answer 2

Так вы уверены, что он должен быть без блокировки? В зависимости от вашей рабочей нагрузки неблокирующее решение иногда может быть медленнее. Посмотрите эту статью MSDN , чтобы узнать больше. Также очень трудно доказать правильность структуры данных без блокировки.

Answer 3

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

параллелизм

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

Хотя, я думаю, есть некоторые дополнительные трудности при реализации этого в связанном списке. Пример базы данных подойдет для вектора, где вы знаете индекс массива того, что вы хотите. Однако в связанном списке вам может понадобиться пройтись по указателям - и структура списка может измениться во время поиска! Я думаю, вы могли бы решить это с помощью какого-то нюанса (или если вы просто хотите просмотреть «новый» список, как есть, ничего не делать), но это создает проблему. Попробуйте решить эту проблему, не вводя условие отката, которое ухудшает блокировку списка!

Answer 4

Я ни в коем случае не эксперт в данной области, но, насколько я понимаю, вам нужно либо сделать поле ExecutionTime в реализации IWorkItem изменчивым (конечно, это может быть так), либо вставить 1001 * memorybarrier либо после установки времени выполнения, либо до его прочтения.