Страницы

Поиск по вопросам

четверг, 11 октября 2018 г.

“тонкая синхронизация” в односвязном списке

Добрый день! Недавно подсмотрела в курсах интересный вариант работы со списками в многопоточной среде, обозвали эту модель там "тонкой синхронизацией". Суть состоит в том, что во время работы со списком блокируется доступ только к текущему и предыдущему элементу списка при любых операциях типа удаления/вставки, и при этом коллизий не возникает. Кто-нибудь использовал этот способ синхронизации на реальных задачах? Вот приведенный в курсах пример добавления элемента к связному списку на псевдокоде : Node prev = head; prev.lock(); Node curr = prev.next; curr.lock();
try{ while(curr.key < key){ prev.unlock(); prev = curr; curr = curr.next; curr.lock(); } if(key == curr.key) return false; else{ node = new Node(key,item); node.next = curr; pred.next = node; return true; } } finally{curr.unlock();pred.unlock();} Если переложить этот пример на С, то я должна создать список, элементами которого будут экземпляры некой структуры, содержащей мьютекс. Вот на этом месте у меня возникает вопрос, как реализовать хотя бы первую строку данного кода без риска поймать segfault в случае, когда: первый поток получил указатель на головной элемент списка, управление получил второй поток, и удалил головной элемент списка, управление вернулось к первому потоку, он пытается захватить мьютекс головного элемента списка, которого уже нет в живых... ?


Ответ

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

Комментариев нет:

Отправить комментарий