одновременный доступ и свободный от структуры данных

Question

Проблема такая:

У меня есть массив из 500 указателей, которые указывают на 500 элементов в двусвязном списке. Есть 10 потоков, которые работают параллельно. Каждый поток выполняет 50 циклов и пытается освободить некоторый элемент в списке.

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

struct node
{
   int key;         // Key used to search this nodes
   int x,y,z;       // Satellite data
   struct node *prev;
   struct node *right;
};

Проблема легко решаема, если я просто заблокирую список перед поиском / удалением. Но это слишком грубо. Как мне синхронизировать эти потоки, чтобы улучшить параллелизм?

редактирует:

1. Это не домашнее задание. Я не принадлежу к академии.
2. Массив, содержащий 500 указателей, кажется странным. Я сделал это так, чтобы визуализировать свои проблемы с наименьшей возможной сложностью.

Answer 1

Можно рассмотреть связанный список без блокировки, используя операцию CompareAndSwap.

ссылка на бумагу

Answer 2

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

1. пометить, но не удалять

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

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

2. подлинное удаление со списком без блокировки

Согласно статье в ответе Пеееша; аналогичные требования к платформе или компилятору для CAS, и требуется значительная осторожность. Такие опции, как refcounts или указатели опасности, могут позволить подлинному удалению узла, когда никто не смотрит на него. Вы можете обнаружить, что вам нужно заменить ваши предыдущие / следующие указатели на short индексы, которые вы можете упаковать в одно слово для работы CAS: это означает ограничение числа узлов и их размещение в массиве.

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

Answer 3

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

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