Добрый день!
Недавно подсмотрела в курсах интересный вариант работы со списками в многопоточной среде, обозвали эту модель там "тонкой синхронизацией". Суть состоит в том, что во время работы со списком блокируется доступ только к текущему и предыдущему элементу списка при любых операциях типа удаления/вставки, и при этом коллизий не возникает. Кто-нибудь использовал этот способ синхронизации на реальных задачах?
Вот приведенный в курсах пример добавления элемента к связному списку на псевдокоде :
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), и оставил исключения для исключительных ситуаций.
Комментариев нет:
Отправить комментарий