Сделать связанный список потоком безопасным

Question

Я знаю, что это было задано раньше (и я буду продолжать изучать), но мне нужно знать, как сделать определенную связанную функцию списка безопасным потоком. Моя текущая проблема заключается в том, что у меня есть один поток, который перебирает все элементы в связанном списке, а другой может добавить еще несколько элементов в конец этого списка. Иногда бывает, что один поток пытается добавить еще один элемент в список, в то время как первый занят итерацией через него (что вызывает исключение).

Я думал просто добавить переменную (логический флаг), чтобы сказать, что список в настоящее время занят, итерации, но как я могу проверить его и ждать со вторым потоком (это нормально, если он ждет, как первый поток работает довольно быстро). Единственный способ, которым я могу это сделать, - использовать цикл while, постоянно проверяющий этот флаг занятости. Я понял, что это была очень глупая идея, так как это заставило бы CPU усердно работать, не делая ничего полезного. И теперь я здесь, чтобы попросить лучшего понимания. Я читал о замках и т. Д., Но в моем случае это не кажется актуальным, но, возможно, я ошибаюсь?

В то же время я продолжу поиск в Интернете и отправлю обратно, если найду решение.

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

Итак, у меня есть класс со связанным списком в нем, который содержит элементы, требующие обработки. У меня есть один поток, который выполняет итерацию через этот список через вызов функции (назовем его «processElements»). У меня есть второй поток, который добавляет элементы для обработки недетерминированным способом. Однако иногда бывает так, что он пытается вызвать эту функцию addElement во время работы processElements. Это означает, что элемент добавляется в связанный список, когда он проходит через первый поток. Это невозможно и вызывает исключение. Надеюсь, это очистит его.

Мне нужна нить, которая добавляет новые элементы для вывода, пока процесс processElements не будет выполнен.

• Кому-то, кто наткнулся на эту проблему. Принятый ответ даст вам быстрое, простое решение, но посмотрите ответ Брайана Гидеона ниже для более полного ответа, который определенно даст вам больше понимания!

Answer 1

Исключение, скорее всего, результат того, что сбор изменилось в середине итерации с помощью IEnumerator. Существует несколько методов, которые можно использовать для обеспечения безопасности потоков. Я приведу их в порядке.

замок Все

Это, безусловно, самый простой и самый тривиальный способ для получения доступа к структуре данных потокобезопасна. Этот шаблон хорошо работает, когда количество операций чтения и записи одинаково сопоставимо.

LinkedList<object> collection = new LinkedList<object>(); 

void Write() 
{ 
    lock (collection) 
    { 
    collection.AddLast(GetSomeObject()); 
    } 
} 

void Read() 
{ 
    lock (collection) 
    { 
    foreach (object item in collection) 
    { 
     DoSomething(item); 
    } 
    } 
} 

Copy-Read Pattern

Это немного более сложная картина. Вы заметите, что перед его чтением создается копия структуры данных. Этот шаблон хорошо работает, когда количество операций чтения мало по сравнению с количеством записей и штрафом копии относительно невелико.

LinkedList<object> collection = new LinkedList<object>(); 

void Write() 
{ 
    lock (collection) 
    { 
    collection.AddLast(GetSomeObject()); 
    } 
} 

void Read() 
{ 
    LinkedList<object> copy; 
    lock (collection) 
    { 
    copy = new LinkedList<object>(collection); 
    } 
    foreach (object item in copy) 
    { 
    DoSomething(item); 
    } 
} 

Copy-Modify-Своп Pattern

И, наконец, у нас есть самый сложный и подвержен ошибкам шаблон. На самом деле я не рекомендую использовать этот шаблон, если вы не действительно знаете, что вы делаете. Любое отклонение от того, что у меня ниже, может привести к проблемам. Легко это испортить. На самом деле, я нечаянно ввернул это и в прошлом. Вы заметите, что копия структуры данных выполняется до всех изменений. Затем копия будет изменена и, наконец, исходная ссылка будет заменена новым экземпляром. В основном мы всегда рассматриваем collection, как если бы они были неизменными. Этот шаблон работает хорошо, когда количество операций записи мало по сравнению с количеством чтений и штраф за копию относительно невелик.

object lockobj = new object(); 
volatile LinkedList<object> collection = new LinkedList<object>(); 

void Write() 
{ 
    lock (lockobj) 
    { 
    var copy = new LinkedList<object>(collection); 
    copy.AddLast(GetSomeObject()); 
    collection = copy; 
    } 
} 

void Read() 
{ 
    LinkedList<object> local = collection; 
    foreach (object item in local) 
    { 
    DoSomething(item); 
    } 
} 

Update:

Так я задал два вопроса в разделе комментариев:

• Почему lock(lockobj) вместо lock(collection) на стороне записи?
• Почему local = collection со стороны чтения?

В отношении первого вопроса рассмотрим, как компилятор C# будет расширять lock.

void Write() 
{ 
    bool acquired = false; 
    object temp = lockobj; 
    try 
    { 
    Monitor.Enter(temp, ref acquired); 
    var copy = new LinkedList<object>(collection); 
    copy.AddLast(GetSomeObject()); 
    collection = copy; 
    } 
    finally 
    { 
    if (acquired) Monitor.Exit(temp); 
    } 
} 

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

• Резьба A выполняет object temp = collection.
• Резьба B исполняет collection = copy.
• Резьба C исполняет object temp = collection.
• Резьба A приобретает замок с указанием .
• Резьба C приобретает замок с новый ссылка.

Очевидно, это было бы катастрофой! Записи будут потеряны, так как критический раздел вводится более одного раза.

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

void Read() 
{ 
    object x = collection.Last; 
    // The collection may get swapped out right here. 
    object y = collection.Last; 
    if (x != y) 
    { 
    Console.WriteLine("It could happen!"); 
    } 
} 

Проблема здесь заключается в том, что collection может получить выгружена в любое время. Это будет невероятно сложной ошибкой, чтобы ее найти. Вот почему я всегда извлекаю локальную ссылку на стороне чтения при выполнении этого шаблона. Это гарантирует, что мы используем такую ​​же коллекцию для каждой операции чтения.

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

Answer 2

Вот краткий пример того, как использовать замки для синхронизации доступа к списку:

private readonly IList<string> elements = new List<string>(); 

public void ProcessElements() 
{ 
    lock (this.elements) 
    { 
     foreach (string element in this.elements) 
      ProcessElement(element); 
    } 
} 

public void AddElement(string newElement) 
{ 
    lock (this.elements) 
    { 
     this.elements.Add(element); 
    } 
} 

lock(o) утверждение означает, что выполняющийся поток должен получить блокировку взаимного исключения на объекте o, выполнить блок оператора и, наконец, отпустить блокировку на o. Если другой поток пытается получить блокировку на o одновременно (либо для того же блока кода, либо для любого другого), он блокирует (ждать) до тех пор, пока блокировка не будет отпущена.

Таким образом, решающим моментом является то, что вы используете один и тот же объект для всех операторов lock, которые вы хотите синхронизировать. Фактический объект, который вы используете, может быть произвольным, если он согласован. В приведенном выше примере мы объявляем нашу коллекцию только для чтения, поэтому можем безопасно использовать ее в качестве нашей блокировки. Однако, если бы это было не так, то вы должны зафиксировать на другом объекте:

private IList<string> elements = new List<string>(); 

private readonly object syncLock = new object(); 

public void ProcessElements() 
{ 
    lock (this.syncLock) 
    { 
     foreach (string element in this.elements) 
      ProcessElement(element); 
    } 
} 

public void AddElement(string newElement) 
{ 
    lock (this.syncLock) 
    { 
     this.elements.Add(element); 
    } 
}