Список блокировок, помогите!

StackOverflow https://stackoverflow.com/questions/475776

  •  19-08-2019
  •  | 
  •  

Вопрос

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

Ну, список не является обычным списком. У меня есть интерфейс 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, если я получу те же результаты там, когда я закончил плохо загрузить результат здесь ..

Это было полезно?

Решение

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

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

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

first = null, workItem1.next = null

(а в другой теме Add() по-прежнему workItem1.next:=workItem2).

Теперь вернемся к первому потоку, и он завершает null установкой <=>.

Если мы позвоним <=> сейчас, мы получим <=>, даже если <=> успешно завершено.

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

Другие советы

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

Параллелизм

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

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

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

Я ни в коем случае не являюсь экспертом в этой области, но, насколько я понимаю, вам нужно либо сделать поле ExecutionTime в реализации IWorkItem изменчивым (конечно, это может быть так), либо вставить < a href = "http://msdn.microsoft.com/en-us/library/system.threading.thread.memorybarrier.aspx" rel = "nofollow noreferrer"> memorybarrier либо после установки времени выполнения, либо перед Вы читаете это.

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top