Concurrent generic data structure without deadlocks or resource starvation

You can set up a worker thread to process all requests in a deterministic way, so nobody gets starved. This strategy would be reasonably efficient and immune to livelock.

-- yes, this is a horrible name
createManagerFactory :: a -> IO ((IO a), IO (((a -> a) -> IO a)))

IO a is an action that safely and quickly queries the value with a read-only STM action. (a -> a) is a pure function that modifies the value, so ((a -> a) -> IO a) is an action that takes a modifier function, safely modifies the value, and returns the new value.

Run this once to initialize the factory.

(query, modifierFactory) <- createManagerVactory initValue

Then for each thread run this to generate a new modifier.

myModify <- modifierFactory

createManagerFactory would do the following:

• Create a TVar containing initValue (call it valueTVar).
• Create a TVar containing an empty collection of TVar (Either a (a
  -> a)) (call it the modifyTVarCollection)
• return (atomically $ readTVar valueTVar) as the ‘query’ result
• return a modifierFactory that knows about the modifyTVarCollection

modifierFactory would do this:

• Create a new TVar (Either a (a -> a)) (call it modifyTVar), initialize it to a (Left a) with the current value of the valueTVar, and add it to modifyTVarCollection
• return a modifier action that loads (Right (a -> a)) into the modifyTVar in one STM action, then in another STM action retries until the modifyTVar contains a (Left a) result value, then return that value.

The worker thread would run this loop:

• In one action, grab all the query TVars from the modifyTVarCollection, and check their values. If they all contain (Left a) values, retry (this would block until some other thread loaded their modifyTVar with a modifier function, or the modifierFactory created a new modifierTVar and added it to the collection). Return a list of all modifyTVars containing a Right (a -> a)
• Iterate over all the returned modifyTVars. For each TVar, perform an action that reads the modifier function, safely perform the modification, and puts the result back into the modifyTVar as a (Left a)