[GHC] #9539: TQueue can lead to thread starvation

[GHC]

#9539: TQueue can lead to thread starvation
-------------------------------------+-------------------------------------
        Reporter:  jwlato            |                Owner:  (none)
            Type:  bug               |               Status:  new
        Priority:  normal            |            Milestone:
       Component:  Core Libraries    |              Version:  7.8.2
      Resolution:                    |             Keywords:  stm
Operating System:  Unknown/Multiple  |         Architecture:
                                     |  Unknown/Multiple
 Type of failure:  None/Unknown      |            Test Case:
      Blocked By:                    |             Blocking:
 Related Tickets:                    |  Differential Rev(s):
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by dfeuer):

 Sorry to be thinking out loud so long... I suspect the trick is for the
 read end and the write end to each have an ''estimate'' of the queue
 balance. Start with the usual Okasaki concept:

 {{{#!hs
 data PlainQueue a = PlainQueue !(TVar Int) !(TVar [a]) !(TVar [a])
 }}}

 where the `Int` is the difference in length between the front list (read
 end) and the rear list. We would rotate the queue when that counter goes
 to -1. But the `TVar Int` is a contention point. So let's try this:

 {{{#!hs
 data End a = End !Int [a]
 data Queue a = Queue
   { prev_len :: !(TVar Int)
   , front :: !(TVar (End a))
   , rear :: !(TVar (End a))}
 }}}

 When the queue is rotated, the `prev_len` counter is set to the length of
 the queue. The front of the queue holds a count of how many items have
 been ''removed'' (read) since the last rotation, while the rear holds a
 count of how many items have been ''added''. When we've added half as many
 items as we had at the last rotation, or we've removed half as many as we
 had at the last rotation, we rotate the queue. (Ratios subject to further
 analysis). The idea is that we can be sure that the balance factor will be
 in a fixed range when we rotate, even though neither end can see the
 other.

-- 
Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/9539#comment:16>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler