#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