Безопасное прерывание сканирования

Question

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

1. Поддерживаются следующие операции: Вставка (набор, элемент), Удаление (набор, элемент) и ForAll (набор, операция)
2. Вставка и удаление - редкие операции. Обычно набор содержит только один элемент.
3. Реализация должна быть осуществимой в C; в частности, нет сборки мусора для вас.
4. ForAll должен быть безопасен для выполнения из обработчика асинхронного сигнала , вызов которого мог прервать вставку или удаление.

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

(Мне известны все проблемы с выполнением любого кода в обработчике сигналов; для целей этого вопроса давайте сосредоточимся на том, как сделать ForAll защищенным от сбоев и взаимоблокировок, когда он мог прерваться Вставить или Удалить.)

Answer 1

Если наборы обычно малы, так что линейный поиск по списку в методах «Вставка» и «Удалить» выполняется достаточно быстро, вы можете использовать реализацию связанного списка без блокировок, в которой используется сравнение и замена.Поиск дает ряд объяснений и примеров.

http://www.google.com/search?q=lock+free+linked+list

Все обновления списка выполняются как атомарные операции (сравнение и замена), поэтому прерывание не приведет кпроблема.

Answer 2

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

1. Прочитать указатель на текущую версиюструктура.
2. Сделайте копию этой версии и обновите ее.
3. Сравните и поменяйте местами в обновлении.Если CAS дает сбой, вернитесь к шагу 1.

Асинхронное сканирование тривиально - прочитайте и начните.Без сборки мусора вам нужно будет использовать что-то вроде SafeRead и Release из бумажной ссылки Джима.