Параллельная структура общих данных без взаимоблокировок или ресурсного голода

Недавно я задал несколько вопросов относительно TVar, и у меня все еще есть проблемы с livelock.

Итак, я подумал об этой структуре:

  • Каждая транзакция получает уникальный приоритет (возможно, выделен в порядке создания).
  • Транзакции пытаются получить блокировку чтения/записи для доступа к данным. Естественно, одновременные чтения в порядке, но одна блокировка записи исключает все остальные (как чтение, так и запись).
  • Скажите, что транзакция A имеет более высокий приоритет, чем транзакция B. Если A удерживает блокировку, B ждет, но если B удерживает блокировку, а A хочет ее, B загружается из блокировки, A получает ее, а транзакция B перезапускается (например, с TVar). Однако B сохраняет свой текущий приоритет для повтора.
  • Когда блокировка освобождается и ожидаются транзакции, она переходит на транзакцию с самым высоким приоритетом, а остальные продолжают ждать.

Эта система, я считаю, предотвращает взаимоблокировки, но также предотвращает голодание (в отличие от TVar). Мне было интересно, если кто-то реализовал такую ​​систему, как это кажется довольно очевидным, и я не хочу изобретать велосипед.

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

Приоритетом может быть пара (user_supplied_prio, auto_increment), с приоритетом user_supplied_prio, но равные приоритетные задачи, разрешающие в порядке FIFO.

Комментарий/Решение:

Собственно, когда я думаю об этом, то, что я описываю, уже существует в Haskell, просто используя один IORef, обернутый вокруг всех данных, и используя только atomicModifyIORef. atomicModifyIORef гарантирует, что транзакции будут применяться последовательно. Однако можно подумать, что это означает, что структура данных является последовательной (то есть эффективно ограничена одним потоком), но она фактически параллельна из-за лени.

Чтобы объяснить это, рассмотрим дорогостоящую функцию f. Мы собираемся применить это к Data.Map к данным с помощью ключа "foo".

Это заменяет (foo -> x) на (foo -> future(f x)). Этот поток должен продолжить работу над тем, что (f x) на самом деле, но в то же время мы можем применить g к "bar". Так как применение g к "bar" не нуждается в результате "foo", мы можем работать это одновременно.

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

Ответы

Ответ 1

Вы можете настроить рабочий поток для обработки всех запросов детерминированным способом, поэтому никто не голодает. Эта стратегия была бы разумно эффективной и невосприимчивой к livelock.

-- yes, this is a horrible name
createManagerFactory :: a -> IO ((IO a), IO (((a -> a) -> IO a)))

IO a - это действие, которое безопасно и быстро запрашивает значение с помощью действия STM только для чтения. (a → a) - это чистая функция, которая модифицирует значение, поэтому ((a → a) → IO a) - это действие, которое принимает модификаторную функцию, безопасно изменяет значение и возвращает новое значение.

Запустите это один раз, чтобы инициализировать factory.

(query, modifierFactory) <- createManagerVactory initValue

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

myModify <- modifierFactory

createManagerFactory выполнит следующее:

  • Создайте TVar, содержащий initValue (назовите его valueTVar).
  • Создайте TVar, содержащий пустую коллекцию TVar (либо a (a - > a)) (назовите это changeTVarCollection)
  • return (atomically $readTVar valueTVar) в качестве результата запроса
  • возвращает модификаторFactory, который знает о файле changeTVarCollection

modifierFactory сделал бы это:

  • Создайте новый TVar (либо a (a → a)) (вызовите его modifyTVar), инициализируйте его до (Left a) с текущим значением valueTVar и добавьте его для изменения TVarCollection
  • возвращает действие модификатора, которое загружает (Right (a → a)) в changeTVar за одно действие STM, затем в другое действие STM повторяет попытку до тех пор, пока файл changeTVar не будет содержать значение результата (Left a), затем верните это значение.

Рабочий поток выполнил бы этот цикл:

  • В одном действии, захватите все ТВ-запросы запроса из файла changeTVarCollection и проверьте их значения. Если все они содержат значения (Left a), повторите попытку (это будет блокировать до тех пор, пока какой-либо другой поток не загрузит их modifyTVar с помощью функции модификатора, или modifierFactory не создаст новый модификатор и не добавит его в коллекцию). Верните список всех модификаций, содержащих Right (a → a)
  • Итерации по всем возвращенным версиям. Для каждого TVar выполните действие, которое читает функцию модификатора, безопасно выполнит модификацию и вернет результат обратно в modifyTVar как (Left a)