Haskell: How does TVar work?

Question

How does TVar work? From what I read, he tries to start all transactions immediately after receiving them, however, the completion of the transaction invalidates other current transactions, which must then be restarted. How does TVar work?

If this were the case, if there were 1 ms transactions occurring every 100 ms, does this mean that a transaction that takes 200 ms to process will never end?

Answer 1

As long as two transactions have access to separate TVars , they can both be committed simultaneously without canceling each other.

Just to understand when a transaction is invalid, consider the following scenario:

• Suppose that t :: TVar Int initialized to 0 and read through readTVar t at the start of transaction A
• Meanwhile, transaction B starts in another thread, in which writeTVar t 1 is executed. Suppose B holds up to A The STM system checks for any inconsistencies and concludes that it is safe to commit B at the moment, so writeTVar t 1 is now in effect.
• This, however, invalidates transaction A , because at the beginning of A , the old value 0 of t was read. (If A was allowed to commit, we would get a violation of atomicity.)

The original article [1] about the STS Haskell system (see section 6.5) answers your question:

"Perhaps starvation. For example, a transaction that is performed for a very long time may repeatedly conflict with shorter transactions. We believe that starvation is unlikely to happen in practice, but we cannot say without additional experience."

[1] Tim Harris, Simon Marlowe, Simon Peyton Jones and Maurice Herlichi. ACM Conference on Principles and Practices of Parallel Programming 2005 (PPoPP'05).

Answer 2

If there were 1 ms transactions occurring every 100 ms, does this mean that a transaction that takes 200 ms to process will never end?

Transactions only conflict if they relate to the same TVar s, therefore, if some of the 1 ms transactions avoid all the variables affected by the 200 ms transactions, then they can complete 200 ms. Moreover, since the STM monad is pretty strict about what is allowed inside (only memory access and clean calculations!), It is very unusual to have such a mismatch between transaction durations; as a rule, they will be only for reading or writing several files, and all IO and other calculations will be performed outside the transaction. Moreover, regardless of whether a transaction is permanently blocked by other transactions, this is a planning problem; I am not 100% sure that it looks like a GHC scheduler, but it seems plausible that it prefers older (or higher speeds) transactions.

However, livelock is a very real problem with STM , and about the same insidious and just as difficult reason as a dead end in more traditional concurrency implementations.

How does TVar work?

You might like this article .