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

1 Sep 2014

      #9539: TQueue can lead to thread starvation
-------------------------------------+-------------------------------------
       Reporter:  jwlato             |                   Owner:
           Type:  bug                |                  Status:  new
       Priority:  normal             |               Milestone:
      Component:  libraries (other)  |                 Version:  7.8.2
       Keywords:  stm                |        Operating System:
   Architecture:  Unknown/Multiple   |  Unknown/Multiple
     Difficulty:  Unknown            |         Type of failure:
     Blocked By:                     |  None/Unknown
Related Tickets:                     |               Test Case:
                                     |                Blocking:
                                     |  Differential Revisions:
-------------------------------------+-------------------------------------
 For background, please see [http://stackoverflow.com/questions/25536604
 /huge-memory-consumption-for-simple-multithreaded-
 haskell/25560047#25560047 this SO question]

 When using TQueue, a sufficiently fast/persistent writer can result in the
 reader never getting scheduled, causing the queue to continually grow and
 lost concurrency.

 I believe the issue is caused by the definition of readTQueue:

 {{{
 readTQueue :: TQueue a -> STM a
 readTQueue (TQueue read write) = do
   xs <- readTVar read
   case xs of
     (x:xs') -> do writeTVar read xs'
                   return x
     [] -> do ys <- readTVar write
              case ys of
                [] -> retry
                _  -> case reverse ys of
                        [] -> error "readTQueue"
                        (z:zs) -> do writeTVar write []
                                     writeTVar read zs
                                     return z
 }}}

 Note that the last `case` needs to traverse the write-end of the queue
 within the STM transaction.  If the list is sufficiently large, a writer
 can commit a new transaction much more quickly, invalidating the read
 transaction.  If threads continue to write to the queue, the reader will
 never get an opportunity to commit (and the list will grow, exacerbating
 the problem).

 This alternative definition seems to fix the problem, but I don't know if
 there are other drawbacks to using it.

 {{{
 readTQueue' :: TQueue a -> STM a
 readTQueue' (TQueue read write) = do
   xs <- readTVar read
   case xs of
     (x:xs') -> do writeTVar read xs'
                   return x
     [] -> do ys <- readTVar write
              case ys of
                [] -> retry
                _  -> do writeTVar write []
                         let (z:zs) = reverse ys
                         writeTVar read zs
                         return z
 }}}

--
Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9539
GHC http://www.haskell.org/ghc/
The Glasgow Haskell Compiler