Concurrent generic data structure without deadlocks or resource starvation

Question

I've recently asked a number of questions regarding TVar, and I still have concerns about livelock.

So I thought of this structure:

1. Each transaction gets a unique priority (perhaps allocated in order of creation).
2. Transactions attempt to get read/write locks on data they access. Naturally, simultaneous reads are okay, but one write lock excludes all others (both read and write).
3. Say transaction A has higher priority than transaction B. If A holds the lock, B waits, but if B holds the lock and A wants it, B is booted from the lock, A obtains it, and transaction B restarts (like with TVar). B however keeps its current priority for the retry.
4. When a lock is freed and there are transactions waiting, it goes to the highest priority transaction, and the rest continue to wait.

This system I believe prevents deadlocks, but also prevents starvation (unlike TVar). I was wondering if anyone has implemented such a system, as it seems fairly obvious and I don't want to reinvent the wheel.

Of course, such an approach could easily be extended to allow the user to specify priorities.

Priority could be the pair (user_supplied_prio, auto_increment), with user_supplied_prio taking precedence, but equal priority tasks resolving in FIFO order.

Comment/Solution:

Actually, when I think about it, what I describe already exists in Haskell, simply by using one IORef wrapped around all the data, and only using atomicModifyIORef. The atomicModifyIORef will ensure transactions are applied in sequence. However, one may think that this means that the data structure is sequential (i.e. effectively limited to one thread) but it is actually parallel due to laziness.

To explain this, consider an expensive function f. We are going to apply this to a Data.Map to the data with the key "foo".

This replaces (foo -> x) with (foo -> future(f x)). This thread shall continue to work out what (f x) actually is, but in the meantime we can apply g to "bar". Since applying g to "bar" does not need the result of "foo", we can work this out at the same time.

No deadlocks, no starvation, eventually all transactions will be processed (roughly in the order they are received).

Answer 1

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)