Охранять простой список в многопоточном программировании? - PullRequest
Новая
       33

Охранять простой список в многопоточном программировании?

4 голосов
/ 31 января 2012

Я читаю книгу о потоках POSIX для некоторой практики, и я пытался решить, где мне понадобится мьютекс-защита в простом односвязном списке, как небольшая проблема для практики.Например, если у меня был список структур узлов: 

template <typename T>
struct Node
{
    Node<T>* next;
    T data;
};

Node<T>* head = NULL;

//Populate list starting at head...


[HEAD] --> [NEXT] --> [NEXT] --> [NEXT] --> [...] --> [NULL]

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

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

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

Кроме того, если бы это был двусвязный список, ситуация изменилась бы?

Ответы [ 2 ]

3 голосов
/ 31 января 2012

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

  1. Добавьте два дозорных узла в список для head и tail. Оба эти узла имеют связанные с ними блокировки, и каждый новый узел будет добавлен между ними.
  2. Для любой функции, которая пересекает список, вам нужно получить блокировку на следующем узле, прежде чем назначить его указателю current. Вы также не можете снять блокировку на текущем узле, пока не получите блокировку на следующем узле. Если вы также используете указатель prev для обхода, вы будете удерживать блокировку на этом «предыдущем» узле, пока не переназначите указатель prev на указатель current.
  3. Для добавления узла вам нужно заблокировать два узла, которые будут расположены по обе стороны от добавляемого узла. Так, например, у вас будет указатель узла prev и указатель узла current. Сначала нужно заблокировать мьютекс на узле prev, а затем заблокировать мьютекс на узле current и добавить новый узел между узлами prev и current.
  4. Если вы удаляете узел, вы снова блокируете мьютекс в узле prev и current (в этом порядке), а затем можете удалить узел current.

Имейте в виду, что шаги № 3 и № 4 работают из-за шага № 2, где для обхода списка требуется получение блокировок на узлах. Если вы пропустите этот шаг, вы в конечном итоге создадите висячие указатели и другие проблемы, связанные с неправильно назначенными указателями, поскольку другой поток меняет топологию списка под текущим потоком.

2 голосов
/ 31 января 2012

Поскольку блокировка одного узла не является поточно-ориентированной (один поток может попытаться вставить после него, а другой занят удалением следующего узла), ни одна из них не блокирует подмножество узлов.Лучше всего использовать глобальный мьютекс для всего списка, если вы не готовы приложить некоторые усилия для разработки read-write lock, который по крайней мере позволил бы нескольким потокам читать список одновременно.

Поскольку двусвязный список - еще более сложная структура, я бы придерживался того же совета.

...