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

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

Я подумал об этой структуре.:

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

Я считаю, что эта система предотвращает тупиковые ситуации, но также предотвращает голодание (, в отличие от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», мы можем обработать это одновременно.

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