8

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

  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 в случае, когда:

  1. первый поток получил указатель на головной элемент списка,
  2. управление получил второй поток, и удалил головной элемент списка,
  3. управление вернулось к первому потоку, он пытается захватить мьютекс головного элемента списка, которого уже нет в живых...
    ?
12
  • Ага, верно подмечено. Я вот тоже на первой строке подвис, недочитав вопрос.
    – mega
    18 мар 2013 в 9:44
  • @margosh, а ведь нигде не сказано, что этот код должен работать при удалении элементов. Вероятно для реализации удаления нужна еще пара Ваших любимых (кстати, как они поживают) pthread_rwlock_wrlock/pthread_rwlock_rdlock. Поток вставки (тот что сейчас рассматриваем) должен сделать pthread_rwlock_rdlock перед первым prev.lock(); -- Реально здесь вопрос в другом. Все такие локи это дорогие операции и IMHO просто сожрут все время. Быстрее будет последовательно.
    – avp
    18 мар 2013 в 10:12
  • Наверняка использовали авторы идеи. Я бы просто обернул все операции с этим списком в критическую секцию и не собирал на г.. сметану
    – renegator
    18 мар 2013 в 10:20
  • 1
    @VladD, IMHO про обработку элемента здесь вообще речь не идет. Речь об изменении контейнера. А Ваш комментарий это, видимо, по поводу провести указанный тест? Суть там это обход (посещение), а не изменение. Хотел предложить именно простой в реализации тест, а так можно и на этих же списках проверить (если не лень), что однопоточный алгоритм будет быстрее на порядок.
    – avp
    18 мар 2013 в 11:47
  • 1
    @avp: я имел в виду алгоритм, который считает, что пока данные заблокированы, он имеет право их читать и записывать. В этом случае, если кто-то хочет удалить элемент, он обязан убедиться, что ни у кого нету блокировки на чтение данных -- то есть фактически взять самому эту блокировку. --- Хотя может быть тут нужен rwlock :-) r = доступ к данным (на чтение или запись), w = модификация структуры.
    – VladD
    18 мар 2013 в 12:58

1 ответ 1

6

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

В таких предположениях код, кажется, верен.

Инвариант алгоритма таков: для работы с элементом необходима блокировка как самого Node, так и его предшественника. Если у вас есть блокировка на Node или на его предшественника, ваш Node гарантированно жив.

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

9
  • т.е. head - "пограничный" элемент, иными словами.
    – mega
    18 мар 2013 в 10:38
  • Со второй строкой всё в порядке: покуда у нас есть lock на head, элемент head.next гарантированно жив.
    – VladD
    18 мар 2013 в 10:41
  • @mega: почему? prev -- просто указатель на предшествующий текущему элементу.
    – VladD
    18 мар 2013 в 10:43
  • >покуда у нас есть lock на head, элемент head.next гарантированно жив. Скорее всего, он гарантированно не меняется, а не жив :) Видимо, предполагается, что список непустой.
    – mega
    18 мар 2013 в 10:44
  • 1
    @margosh: Гарантии есть. Посмотрите внимательнее инвариант. Для того, чтобы элемент умер, другому потоку надо захватить блокировку и на этот, и на предыдущий элемент. А в тот момент, когда мы получали указатель на текущий элемент, предыдущий элемент был нами заблокирован.
    – VladD
    18 мар 2013 в 11:07

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.