Обеспечивает ли STM точную блокировку существующих структур данных?

Прочитав фантастический сообщение в блоге Бартоша Милевски о STM, я был взволнован, прочитав следующий:

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

Однако, насколько я понимаю, такое поведение не является автоматическим, не так ли? Если я использую TVar (Map k a), не будет ли он действовать как единая глобальная блокировка на всей карте? И чтобы получить выгоду от этого мелкозернистого поведения, мне (или кому-то другому) пришлось бы реализовать замену карты (например, TMap), которая содержит TVars внутри, верно?

Это может показаться очевидным вопросом, но, читая о реализации STM, я запутался между чтением TVars и чтением ячеек памяти. Я просто хочу убедиться, что я прав!

Бартош продолжает:

Ручную блокировку для каждого узла трудно реализовать правильно из-за риска взаимоблокировок.

Насколько я понимаю, разница с STM заключается в том, что, хотя реализация STM фактически использует блокировки так же, как решение с ручной блокировкой, фактическое получение и освобождение блокировок обрабатывается средой выполнения, а не программистом - верно?


haskell stm
person Daniel Buckmaster    schedule 02.04.2014    source источник
comment
Это зависит от реализации, но существует множество способов реализации STM без блокировок (например, атомарное сравнение и обмен). Что касается вашего первого вопроса, да, вам понадобятся карты TVars, а не TVar (Map k v).   -  person Thomas M. DuBuisson    schedule 02.04.2014
comment
@ThomasM.DuBuisson спасибо за это. Вы имеете в виду, что у меня действительно может быть мелкозернистый Map, или мне нужно будет полностью переделать Map для внутреннего использования TVar?   -  person Daniel Buckmaster    schedule 02.04.2014
comment
Кроме того, я только что узнал, что «приобретение» на самом деле слово. Удачная догадка.   -  person Daniel Buckmaster    schedule 02.04.2014
comment
Вы можете просто иметь карту нормалей со значениями, равными TVars. Точнее, Map k (TVar v).   -  person Thomas M. DuBuisson    schedule 02.04.2014

Ответы (1)


arrow_upward
8
arrow_downward

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

writeTVar :: TVar a -> a -> STM ()

который создает действие SMT, заменяющее значение внутри изменяемой ячейки. Мы можем упорядочить несколько таких операций вместе, создав более крупное и сложное действие STM, а затем вызвать

atomically :: STM a -> IO a

для атомарной фиксации всего действия STM сразу. Это «транзакционная» часть транзакционной памяти программного обеспечения: другие потоки со своими собственными ссылками на эти изменяемые ячейки будут свидетелями только всего atomically-выполненного STM действия, без подчастей. Для этого Haskell может использовать блокировку или что-то более хитрое — это просто деталь реализации. Единственное, о чем STM просит вас знать, так это о том, что действия в вашем блоке STM могут выполняться многократно по мере необходимости, поэтому побочные эффекты, не связанные с модификацией некоторых ячеек общей памяти, запрещены.

Так как же нам добиться мелкозернистого параллелизма? Легко: мы просто предоставляем больше изменяемых ячеек для синхронизации различных потоков. Например, мы можем прочитать как минимум 3 разных типа Map.

TVar (Map k v)
Map k (TVar v)
TVar (Map k (TVar v))

Первый позволит параллельным потокам вносить изменения во все Map одновременно, так что никакие частичные изменения не будут видны. Второй допускает изменения в любом сохраненном значении, но утверждает, что структура самой карты — выбор ключей и выбор сохраненных значений — неизменяема, и изменения не могут быть легко распространены на другие потоки.

Окончательный выбор, TVar (Map k (TVar v)), является наиболее гибким. Мы можем вносить массовые изменения в Map, синхронизируя внешний TVar, и мы можем вносить изменения в значения, хранящиеся в карте, считывая значения-TVar и синхронизируя действия внутри них. Полный набор возможных семантик, доступных для такого дерева, бесчисленен, что позволяет одновременно использовать как «полную Map блокировку», так и «блокировку отдельных значений».

person J. Abrahamson    schedule 02.04.2014
comment
Фантастический ответ! Спасибо за объяснение. Так что, чтобы было ясно, даже TVar (Map k (TVar a)) не обеспечивает мелкозернистой блокировки, которую описывает Бартош, - это потребовало бы реализации совершенно новой структуры данных TMap, которая помещает TVars вокруг внутренних узлов дерева (если это действительно используемая структура хранения) , а не только листья. - person Daniel Buckmaster; 03.04.2014
comment
Да, ваша детализация точно такая же, как и местоположение ваших TVars. - person J. Abrahamson; 03.04.2014