TExpr and TSem: A proposal that would allow STM to have fair bounded queues.
STM has a major advantage over MVar in it's ability to avoid deadlock and have ACID guarantees. However, it suffers an issue with fairness: a thread that is competing for a resource with other threads may never obtain it. This proposal proposes two features that together would make fair bounded queues possible, while retaining STM's benefits.
The two features are
TExpr allows a transaction to delay the reading of
TVars to commit time, exploiting laziness to ensure that no evaluation of the values in the
TVars need to be evaluated at commit time.
TSem will allow transactions to "precommit" if a resource is unavailable. Once the resource becomes available, if it is older than all the other transactions waiting for it, it can immediately transition from precommited to being fully committed. This does not risk the transaction diverging and locking the resource forever, because if it diverges it can not precommit in the first place.
TExpr works as follows. A value of type
TExpr a represents a value of type
a that depends on the values contained in
TExpr is an Applicative functor. The main functions are
readTVarExpr :: TVar a -> STM (TExpr a) and
writeTVarExpr :: TVar a -> TExpr a -> STM (), which read and write expressions to a
TVar. However, the
TVars are not read as the transaction is ran. This means that the transaction is not aborted if the
TVar is changed. Rather, at commit time, thunks are constructed for each of the
TExprs from the values in the
TVars. Since no evaluation occurs, this does not risk causing the commit step to diverge. This feature already allows writers in an unbounded queue to not compete with each other. For example:
writeToQueue :: TVar [a] -> a -> STM () writeToQueue t a = do q <- readTVarExpr t writeTVarExpr t $ fmap (++ [a]) q return ()
This has other applications, of course. You can make modifications to a
TVar (Map k v) without the transactions interfering with each other, for example.
Another useful function is
atomicallyExpr :: STM (TExpr a) -> IO a, which runs the transaction and returns a thunk representing the returned
TExpr's value. There is also
readTExpr :: TExpr a -> STM a. This peculiar function reads the expression. This causes all of the
TVars it depends on to be read, as if by
readTVar. Note that this will also happen if you write to a
writeTVarExpr and then read from the same
It is possible that
TExprs will be referenced outside the transaction that created. When this is done, they behave like
pure v, where
v is the value it had at commit time.
TSem actually can be implemented in terms of
TVar (see Control.Concurrent.STM.TSem), but in this proposal, it becomes a primitive notion. It represents a semaphore which can be increased and decreased in the
STM monad, and will retry if it the transaction attempts to cause it to go negative. However, it does so in a special way!
The key operations are
newTSem :: Natural -> STM TSem and
signalTSem :: TSem -> Integer -> STM ().
signalTSem adds a value to the
TSem, and can be negative to represent a decrease to the TSem. The overall value can never go negative, however. Here is the special part though: when doing the
signalTSem, it does not actually check if this will cause the
TSem to go negative. It makes a note of the effect, and continues the transaction. Once the transaction gets to the commit step, it will check if there are enough units in the semaphore for the
signalTSems it preformed. If there are, it can commit like normal, making the necessary changes to the
TSems. If not, it can not commit. Assuming it is otherwise fine to commit, it enters the "precommit" phase, and blocks. The precommit phase stores information about the changes that will be made once the transaction fully commits. If a
TVar it read is changed, it is aborted and loses its precommit status.
TSem is increased, the precommited transactions that are blocked on it can attempt to commit. However, unlike
TVar, they do not all get this chance at the same time. Rather, the oldest transaction (in terms of when the program entered its
atomically IO action) gets to try to commit first. If it fails, it continues in chronological order.
What makes this work for
TSem is that the transaction is already precommitted. The transaction does not need to be rerun; it only needs to check that there are now enough units in the
TSem and that the
TVars it read are still not changed. If there are not enough units in the
TSem, it is skipped over but keeps its precommit status. If the
TVars are changed, it is skipped, aborted, and restarted, losing its precommit status until it precommits again. This ensures that a diverging transaction can never prevent other transactions from committing; a diverging transaction can not precommit.
TExpr, this allows fair bounded queues. The queue stores both the number of items it contains and the amount of remaining capacity in
TSems are increased and decreased as needed when reads and writes occur. The read action returns
STM (TExpr a) for a queue storing items of type
a. Reads and writes will only block each other if the capacity of read or write semaphore hits zero, and then they resolve in chronological order (assuming they can precommit).
Here are some other caveats about
If a transaction uses more than one
TSem, it keeps track of which ones it is blocked on. If the
TSems it is blocked on are increased at the same time, it can attempt to commit.
In a transaction of the form
t1 <|> t2, if
t1basically defaults to
TVarbehavior. At the end of
t1, it checks if the
TSems it used had enough units, and if they do not,
t2is preformed instead. However, if it any point the
TSems are increased sufficiently that
t1could commit, the entire transaction is aborted and restarted.
When a transaction that is using
TSems attempts to commit, it must check if there are any precommitted transactions. If there are, it just precommits itself and waits in line, even if there are currently enough units in the
TSem, transactions can commit/precommit without ever reading the
TVars they depend on, allowing them to be processed in chronological order in some cases. This allows, among many other things, fair bounded queues that can operate in the
STM monad! A drawback is that attempting to compose these operations can result in a lose of fairness. However, atomic blocks that simply read or write from a single object are common, and when you do compose the operations, they still work; they just go back to the ordinary
STM behavior that currently exists.