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).

Landward

I'm unaware of any such system existing in Haskell. It seems overly complex for most users, and rather fiddly to implement. In particular, invalidating an assigned lock would require either polling (somewhat tedious to code) or asynch exceptions (a whole other can of worms). I would suggest that you just try STM for your implementation and see how it works; STM algorithms are usually simple enough that it wouldn't be a significant time investment if you need to replace it. – Bonfire

Speaking from the STM viewpoint, adding a priority mechanism to the runtime (similar to the one you mentioned based on date) will solve the livelock issue I believe. However, it might seriously limit the choices of the scheduler, which might even be the reason why there's no such mechanism in the current STM runtime. PS: you might want to mark some of the answers to your previous questions as "accepted answer", to let the community know whether the question has been resolved. – Grecian

What are the performance requirements? You can get what you want through sufficiently coarse-grained means such as a global ticket lock (en.wikipedia.org/wiki/Ticket_lock), or by enqueueing all actions to be executed serially by a single thread. Sophisticated synchronization methods tend to have higher overhead. If global synchronization is not a bottleneck for a given workload, it's probably faster. – Verret

Just to make sure: have you considered MVars? Threads are guaranteed queued fairly in FIFO fashion when blocked on an MVar, so if you only want to prioritize based on creation time, that seems logical. Can you give a simple use case that would illustrate the problem you're looking to solve with your structure? – Aldridge

I don't think STMs can suffer from livelocks -- bad performance, yes. Do you have a reference for that? – Omni

You should put your comment/solution into an answer and accept your own answer so stackoverflow will have one less unanswered question :). I thought about c&ping into an answer, changing to pronouns and submitting but that didn't seem sporting. – Nierman

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)

Ilium