Недавно я задал несколько вопросов относительно 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", мы можем работать это одновременно.
Без взаимоблокировок, без голода, в конечном итоге все транзакции будут обработаны (примерно в том порядке, в котором они получены).
