title: Concurrent generic data structure without deadlocks or resource starvation
body: <p>I've recently asked a number of questions regarding <code>TVar</code>, and I still have concerns about livelock.</p>
  
  <p>So I thought of this structure:</p>
  
  <ol>
  <li>Each transaction gets a unique priority (perhaps allocated in order of creation).  </li>
  <li>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).   </li>
  <li>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 <code>TVar</code>). B however keeps its current priority for the retry.  </li>
  <li>When a lock is freed and there are transactions waiting, it goes to the highest priority transaction, and the rest continue to wait.</li>
  </ol>
  
  <p>This system I believe prevents deadlocks, but also prevents starvation (unlike <code>TVar</code>). I was wondering if anyone has implemented such a system, as it seems fairly obvious and I don't want to reinvent the wheel.</p>
  
  <p>Of course, such an approach could easily be extended to allow the user to specify priorities.</p>
  
  <p>Priority could be the pair <code>(user_supplied_prio, auto_increment)</code>, with <code>user_supplied_prio</code> taking precedence, but equal priority tasks resolving in FIFO order.</p>
  
  <p><strong>Comment/Solution:</strong></p>
  
  <p>Actually, when I think about it, what I describe already exists in Haskell, simply by using one <code>IORef</code> wrapped around all the data, and only using <code>atomicModifyIORef</code>. The <code>atomicModifyIORef</code> 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.</p>
  
  <p>To explain this, consider an expensive function <code>f</code>. We are going to apply this to a <code>Data.Map</code> to the data with the key "foo".</p>
  
  <p>This replaces <code>(foo -&gt; x)</code> with <code>(foo -&gt; future(f x))</code>. This thread shall continue to work out what <code>(f x)</code> 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.</p>
  
  <p>No deadlocks, no starvation, eventually all transactions will be processed (roughly in the order they are received).</p>