Потокобезопасное удаление узла связанного списка с использованием детального подхода

Question

Почему следующий фрагмент для удаления узла в связанном списке не является потокобезопасным?

edit: обратите внимание, что каждый узел имеет собственную блокировку

// ... lock acquisition here
// ... assumption found to be valid here
prev->next = p->next;
p->next = NULL;
p->deleted = 1;

Answer 1

Я предполагаю, что вы говорите о односвязном списке, поскольку вы никогда не назначаете 'prev' в своем удалении узла.Учитывая односвязный список узлов, каждый из которых защищен блокировкой, он может быть изображен следующим образом:

Head ==> A ==> B ==> C ==> D ==> Tail
               ^     ^
               |     |
        Thread 1     Thread 2

Предположим, что поток 1 собирается удалить узел B. По совпадению, поток 2 собирается попробоватьудалить узел C одновременно.Вы можете выполнить следующие шаги:

Thread 1                Thread 2
----------------------  ----------------------
Lock B                  Lock C
A->next = C or D; <=??  B->next = D;    <== B could be dead already
B->next = NULL;         C->next = NULL;
B->deleted = 1;         C->deleted = 1;
Unlock B                Unlock C

В этом случае результат непредсказуем.Если поток 2 выполняется немного впереди потока 1, то все должно быть хорошо.Вторая строка потока 1 будет выполнять «A-> next = D», поскольку поток 2 уже поменял бы B-> рядом с D. Однако, если поток 1 выполняется немного впереди потока 2, то A-> следующий указывает на мертвый узел Cмертвый узел B был изменен, а узел D. потерян.

Итак, вы можете попытаться заблокировать узел, который собираетесь удалить, а затем заблокировать «prev» перед его изменением.Шаги могут выполняться следующим образом:

Thread 1                Thread 2
----------------------  ----------------------
Lock B                  Lock C
Lock A                  waiting for B
A->next = C;            waiting for B
Unlock A                waiting for B
B->next = NULL;         waiting for B
B->deleted = 1;         waiting for B
Unlock B                Lock B         <= locking dead node
                        B->next = D;   <= assigning to dead node
                        Unlock B
                        C->next = NULL;
                        C->deleted = 1;
                        Unlock C

Таким образом, это все еще не является потокобезопасным.A-> следующий указывает на мертвый узел C, мертвый узел B был заблокирован и использован, а D потерян.Все, что мы сделали, - это удостоверимся, что описанный выше случай ошибки происходит надежно.

Решение здесь, по-видимому, требует блокировки на «prev» перед блокировкой удаляемого узла.

Thread 1                Thread 2
----------------------  ----------------------
Lock A                  Lock B
waiting for B           Lock C
waiting for B           B->next = D;
Lock B                  Unlock B  
A->next = D;            C->next = NULL;
Unlock A                C->deleted = 1;
B->next = NULL;         Unlock C
B->deleted = 1;         
Unlock B                

A-> рядом с D, и теперь B и C удалены.

Answer 2

Возможно, вы захотите взглянуть на эту презентацию . На слайде № 39 показано, как следует реализовать детальную блокировку связанного списка, в понятной и переносной форме (примечания к слайдам также содержат некоторые пояснения). Презентация основана на (или взята из ...) книге под названием Искусство многопроцессорного программирования .

Answer 3

Это является поточно-ориентированным, если предположить, что область вашей блокировки (то есть что она блокирует, ничего общего с официальным термином "область действия", используемым в C) достаточно велика.

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

Если она блокирует всю структуру, то да, она поточно-ориентирована.

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

Возможно, вам следует либо бесплатно p, либо добавить его в список бесплатных для повторного использования. Просто установив указатель next на ноль, а его флаг deleted на 1, вы не сможете найти его, когда вам потребуется его повторно использовать. Это приведет к утечке памяти. Может быть, код для этого просто не показан, но я решил упомянуть об этом, на всякий случай.

---

На основании ваших правок, где вы заявляете, что вы используете детальный подход (одна блокировка на узел):

При условии, что вы заблокируете все три «узла», которые вы используете или изменяете, и что вы блокируете их в согласованном направлении, это все еще поточно-ориентировано.

Я помещаю "узлы" в кавычки, поскольку это также относится к указателям head и tail. Например, если вы хотите удалить первый узел в списке из десяти узлов, вам нужно заблокировать переменную head, а также первый и второй узлы в указанном порядке. Чтобы удалить последний узел в списке с одним узлом, необходимо заблокировать как переменные head и tail, так и узел.

Блокировка всех трех «узлов» предотвратит отрицательное влияние потоков друг на друга.

Блокировка их в последовательном направлении (например, от head к tail) предотвратит взаимоблокировку.

Но вы должны заблокировать все три, прежде чем пытаться что-либо изменить.

Это даже предотвратит одновременные операции вставки, если вставка блокирует два «узла» по обе стороны от точки вставки и, конечно, блокирует их в одном направлении.

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

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

---

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