Реализация «поточно-ориентированного» связанного списка

Question

Я пишу заявку, в которой более одного списка ссылок разделены между потоками. Операции над связанным списком выполняются как обычно: поиск, вставка, удаление, изменение содержимого узла. Я наткнулся на реализацию ann, чтобы сохранить всю процедуру работы со списком ссылок «поточно-ориентированной». http://www.cs.cf.ac.uk/Dave/C/node31.html#SECTION003100000000000000000

Но мне было интересно, смогу ли я сделать это следующим образом:

lock(mutex)
  link list operation
unlock(mutex)

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

Был бы благодарен за взгляды

Answer 1

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

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

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

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

Answer 2

Зависит.Если ваши потоки будут в основном выполнять поиск по спискам, не изменяя их, возможно, стоит реализовать блокировку чтения / записи.Нет причин препятствовать чтению информации другими потоками, если никто из них не изменяет ее.Однако, если наиболее распространенные операции включают в себя изменение списков или информации в них, выиграть может не так уж и много, поэтому простая схема блокировки / выполнения операций / разблокировки должна работать точно так же.