Haskell: Как работает TVar?

Question

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

Если бы это было так, если бы транзакции длиной 1 мс совершались каждые 100 мс, значит ли это, что транзакция, для обработки которой требуется 200 мсек, никогда не завершится?

Answer 1

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

Просто чтобы прояснить, когда транзакция признана недействительной, давайте рассмотрим следующий сценарий:

1. Предположим, что t :: TVar Int инициализируется в 0 и читается через readTVar t в начале транзакции A,
2. Между тем, в другой ветке, транзакция B начинается в котором writeTVar t 1 выполнен. Предположим, что B совершает до A, Система STM проверит наличие каких-либо несоответствий и сделает вывод, что она безопасна для B совершить на этом этапе, так что теперь writeTVar t 1 становится эффективным.
3. Это, однако, вызывает транзакцию A быть признанным недействительным, так как старое значение 0 из t был прочитан в начале A, (Если A было разрешено совершать, мы бы получили нарушение атомарности.)

Оригинальная статья [1] по системе Haskell STM (см. Раздел 6.5) отвечает на ваш вопрос:

"Возможно голодание. Например, транзакция, которая выполняется очень долго, может многократно конфликтовать с более короткими транзакциями. Мы думаем, что голодание вряд ли произойдет на практике, но мы не можем сказать без дальнейшего опыта".

[1] Тим Харрис, Саймон Марлоу, Саймон Пейтон Джонс и Морис Херлихи. Конференция ACM по принципам и практике параллельного программирования 2005 (PPoPP'05).

Answer 2

Если бы транзакции продолжительностью 1 мс происходили каждые 100 мс, значит ли это, что транзакция, для обработки которой требуется 200 мсек, никогда не завершится?

Транзакции конфликтуют, только если они касаются одного и того же TVars, поэтому, если некоторые из транзакций в 1 мс избежали всех переменных, затронутых транзакциями в 200 мс, тогда 200 мс можно было бы завершить. Более того, так как STM Монада довольно строго относится к тому, что разрешено внутри (только доступ к памяти и чистые вычисления!), очень необычно иметь такое несоответствие между длиной транзакций; как правило, они будут иметь только несколько операций чтения / записи памяти, и все IO и другие вычисления будут выполняться вне транзакции. Более того, вопрос о том, заблокирована ли когда-либо конкретная транзакция навсегда другими транзакциями, является проблемой планирования; Я не уверен на 100%, как выглядит текущий планировщик GHC, но кажется вероятным, что он отдает предпочтение более старым (или с более высокой частотой отказов) транзакциям.

Тем не менее, livelock это очень реальная проблема с STMи столь же коварен и столь же труден для размышления, как и тупик в более традиционных реализациях параллельной блокировки.

Как работает TVar?

Вам, вероятно, понравится эта статья.