Синхронизация доступа к двусвязному списку

Question

Я пытаюсь реализовать (особый вид) двусвязный список в C, в среде pthreads, но использую только C-упакованные инструкции синхронизации, такие как атомарный CAS и т. Д., А не примитивы pthread.(Элементы списка представляют собой фрагменты памяти фиксированного размера и почти наверняка не могут поместиться в них pthread_mutex_t и т. Д.) На самом деле мне не нужны полные произвольные методы списка с двойной связью, только:

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

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

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

Редактировать : В частности, я застрял на том, что делать, если соседние объекты должны быть удалены одновременно.Предположительно, при удалении объекта вам нужно получить блокировки как для предыдущего, так и для следующего объекта в списке и обновить их указатели next / prev, чтобы они указывали друг на друга.Но если любой из соседей уже заблокирован, это приведет к тупику.Я попытался найти способ, чтобы любое / все происходящее удаление могло пройти по заблокированной части списка и определить максимальный подсписок, который в данный момент находится в процессе удаления, а затем заблокировать узлы, смежные с этим подсписком, чтобывесь подсписок удаляется целиком, но моя голова начинает болеть ..: -P

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

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

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

Answer 1

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

Более сложное (но не обязательно более эффективное, зависит от вашего шаблона использования) решение будет использовать блокировку чтения-записи для чтения и записи соответственно.

---

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

---

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

---

В случае «локальной» блокировки (т. Е. Возможности заблокировать каждый элемент списка отдельно), идея состоит в том, чтобы сделать упорядоченные блокировки. Заказ замков гарантирует невозможность тупика. Итак, ваши операции таковы:

Удалить указателем p до предыдущего элемента:

1. блокировка p, проверка (используя, возможно, специальный флаг в элементе), что элемент все еще находится в списке
2. lock p-> next, проверьте, что это не ноль и в списке; таким образом вы гарантируете, что p-> next-> next не будет удалено за это время
3. блокировка p-> next-> next
4. установить флаг в p-> next, указывая, что его нет в списке
5. (p-> next-> next-> prev, p-> next-> prev) = (p, null); (p-> next, p-> next-> next) = (p-> next-> next, null)
6. отпустить замки

Вставить в начало:

1. головка замка
2. установить флаг в новом элементе, указывая, что он находится в списке
3. заблокировать новый предмет
4. блокировка головы-> далее
5. (head-> next-> prev, new-> prev) = (new, head); (новая-> следующая, голова) = (голова, новая)
6. отпустить замки

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

По сути, это делает список с двойной связью таким, как если бы он был списком с одной ссылкой.

---

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

Удалить по указателю c на удаляемый элемент:

1. блокировка c, проверьте, является ли она все еще частью списка (это должен быть флаг в элементе списка), если нет, операция завершится неудачно
2. получить указатель p = c-> prev
3. разблокировать c (теперь c может быть перемещен или удален другим потоком, p также может быть перемещен или удален из списка) [чтобы избежать освобождения c, вам нужно иметь что-то вроде общего указателя или как минимум вид пересчета для элементов списка здесь]
4. замок р
5. проверить, является ли p частью списка (его можно удалить после шага 3); если нет, разблокируйте p и перезапустите с начала
6. проверьте, равняется ли p-> next c, если нет, разблокируйте p и перезапустите с самого начала [здесь мы можем оптимизировать перезапуск, не уверен, что ATM)
7. lock p-> next; здесь вы можете быть уверены, что p-> next == c и не удаляется, потому что удаление c потребовало бы блокировки p
8. блокировка p-> next-> next; теперь все блокировки сняты, поэтому мы можем продолжить
9. установить флаг, что c не является частью списка
10. выполнить обычное (p-> next, c-> next, c-> prev, c-> next-> prev) = (c-> next, null, null, p)
11. снять все блокировки

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

---

Обратите внимание, что в последнем алгоритме число повторных попыток ограничено.Действительно, новые элементы не могут появляться слева от c (вставка находится в крайнем правом положении).Если наш шаг 5 завершается неудачно и, следовательно, нам нужна повторная попытка, это может быть вызвано только тем, что p будет удалено из списка.Такое удаление может произойти не более N-1 раз, где N - начальная позиция c в списке.Конечно, этот худший случай вряд ли случится.

Answer 2

Пожалуйста, не принимайте этот ответ резко, но не делайте этого.

Вы почти наверняка столкнетесь с ошибками и очень сложными ошибками.Используйте примитивы блокировки pthreads.Они ваши друзья и были написаны людьми, которые глубоко понимают модель памяти, предоставляемую выбранным вами процессором.Если вы попытаетесь сделать то же самое с CAS и атомарным приращением и т.п., вы почти наверняка совершите небольшую ошибку, которую не обнаружите, пока не станет слишком поздно.

Вот небольшой пример кода, который поможетпроиллюстрировать смысл.Что не так с этой блокировкой?

volatile int lockTaken = 0;

void EnterSpinLock() {
  while (!__sync_bool_compare_and_swap(&lockTaken, 0, 1) { /* wait */ }
}

void LeaveSpinLock() {
  lockTaken = 0;
}

Ответ таков: при снятии блокировки нет барьера памяти, а это означает, что некоторые из операций записи, выполненных в блокировке, могли не произойти до того, как следующий поток попадет взамок.Хлоп!(Вероятно, есть и много других ошибок, например, функция не обеспечивает доходность, соответствующую платформе внутри цикла вращения, и поэтому чрезвычайно расточительна из циклов ЦП. & C.)

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

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

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

Answer 3

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

Таким образом, если несколько потоков пытаютсячтобы удалить соседние узлы одновременно (скажем, узлы B и C в цепочке ABCD), то тот поток, который первым получит блокировку для узла B, будет первым, кто отсоединится первым.Поток 1 заблокирует A, затем B, затем C, а поток 2 заблокирует B, затем C, затем D. Есть только соревнование за B, и нет никакого способа, которым поток 1 может удерживать блокировку, ожидая блокировки, удерживаемой потоком.2 и пока поток 2 ожидает блокировки, удерживаемой потоком 1 (т.е. тупик).

Answer 4

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

Вы можете избежать случая удаления из середины, введя другой уровень косвенности - если списокузлы просто содержат указатель next и указатель payload, причем фактические данные указываются в другом месте (вы говорите, что выделение памяти невозможно в точке вставки, поэтому вам просто нужно выделить структуру узла списка вто же самое, что вы выделяете саму полезную нагрузку).

В случае удаления из середины вы просто устанавливаете указатель payload на NULL и оставляете потерянный узел в списке.Если операция FIFO pop встречает такой пустой узел, она просто освобождает его и пытается снова.Эта отсрочка позволяет вам использовать односвязный список, а реализацию списка без замков с односвязной связью значительно легче понять.

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

Answer 5

Вы не можете уйти без блокировки для всего списка.Вот почему:

Вставить в пустой список

Потоки A и B хотят вставить объект.

Поток A проверяет список, находит его пустым

Произошло переключение контекста.

Поток B проверяет список, находит его пустым и обновляет голову и хвост, указывая наего объект.

Происходит переключение контекста

Поток A обновляет голову и хвост, чтобы указывать на его объект.Поток объекта B. потерян.

Удалить элемент из середины списка

Поток A хочет удалить узел X. Для этого ему сначала нужно заблокировать Xпредшественник, сам X и преемник X, так как все эти узлы будут затронуты операцией.Чтобы заблокировать предшественника X, вы должны сделать что-то вроде

spin_lock(&(X->prev->lockFlag));

Несмотря на то, что я использовал синтаксис вызова функции, если spin_lock - функция, вы мертвы в воде, потому что для этого требуется как минимум три операции перед вами.фактически иметь блокировку:

• поместить адрес флага блокировки в стек (или в регистр)
• вызвать функцию
• сделать атомный тест иset

Там есть два места, где поток A может быть заменен, и другой поток может войти и удалить предшественника X без потока A, зная, что предшественник X изменился.Таким образом, вы должны реализовать сам спин-замок атомарно.то есть вы должны добавить смещение к X, чтобы получить x-> prev, затем разыменовать его, чтобы получить * (x-> prev), и добавить смещение к нему, чтобы получить lockFlag, а затем выполнить элементарную операцию в одном элементарном блоке.В противном случае всегда есть возможность что-то проникнуть после того, как вы взяли на себя обязательство заблокировать определенный узел, но до того, как вы фактически заблокировали это.

Answer 6

Две идеи.

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

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

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

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