Список без блокировки поможет!

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

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

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

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

If (item.ExecuteTime < DateTime.Now)

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

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

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

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


person Peter    schedule 24.01.2009    source источник
comment
Даже если я не люблю узнавать что-то новое и видеть, насколько это быстро/медленно!   -  person Peter    schedule 24.01.2009


Ответы (4)


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

Поток 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, поэтому вызов завершается успешно и возвращает workItem1.

После этого состояния:

first = null, workItem1.next = null

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

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

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

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

person Rasmus Faber    schedule 02.02.2009
comment
Большое спасибо за ваше время и помощь! плохо смотреть на все ссылки, которые вы разместили! - person Peter; 02.02.2009
comment
Список Валуа работает не очень хорошо — все эти промежуточные узлы. Бит удаления Харриса работает лучше. - person ; 04.04.2011

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

Параллелизм

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

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

person Overflown    schedule 01.02.2009

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

person Steve Severance    schedule 24.01.2009

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

person Rasmus Faber    schedule 24.01.2009
comment
Проблема не имеет ничего общего с ExecutionTime. Я теряю некоторые IWorkItem из списка где-то :) это происходит только тогда, когда Get и Add вызываются одновременно... - person Peter; 26.01.2009
comment
Как узнать, что вы теряете рабочие элементы? Я предполагаю, что это потому, что Get() не возвращает вставленный рабочий элемент, даже если его ExecuteTime должен был быть. Но в любом случае, не могли бы вы опубликовать полный пример, демонстрирующий проблему? Так вы, вероятно, получите больше ответов. - person Rasmus Faber; 29.01.2009