Re: boost::condition question

From: bill_kempf (williamkempf_at_[hidden])
Date: 2002-02-25 11:50:26

--- In Boost-Users_at_y..., "svanechel" <svanechel_at_y...> wrote:
> [...]
> 
> > First, note that this scheme is very prone to starvation 
problems.  
> > If an operation "type" acquires the "lock" and there are several 
> > threads that will also acquire this same "type" in a loop, it may 
> > very well be that the "lock" is never relinquished for the 
> > other "types" to acquire it.  RW locks are a little tricky to 
> > implement because of this issue.
> > 
> 
> Can you elaborate a bit more on that one, help me to understand. Is 
> there any way out of this problem? How can I prevent it?

There are ways to work around this, but they are non-trivial.  I'm 
not sure I could give you an appropriate answer in a short posting, 
and I don't have a ready reference to point you towards either.  
However, a web search for "read write lock" should help you to locate 
some information on this topic.

> 
> [...]
> > 
> > You didn't use boost::condition incorrectly, you used the 
> > scoped_lock<> incorrectly.  Fixing this, though, still leaves you 
> > with a questionable synchronization scheme that's prone to 
> starvation.
> > 
> 
> Odly enough I alway use scoped_lock they way it is intended to be 
> used. I got a confused when reading through the documentation of 
> boost::condition and how condition::wait affects the lock. Thanks 
to 
> your comments I got it working and it behaves as I expect it would. 
I 
> would surely appreciate if you (or someone else) could futher 
clarify 
> the starvation problem.

Just to illustrate how it occurs in text:

Two threads are in a loop acquiring read locks (threads A & B).  A 
third thread is trying to acquire a write lock (thread C).  The 
following sequence shows that thread C may "starve" and never acquire 
the lock (similar to deadlock).

1. A acquires read lock.
2. C trys to acquire write lock and blocks.
3. B acquires read lock.
4. A relinquishes read lock.
5. A acquires read lock.
6. B relinquishes read lock.

3-6 repeat indefinately as thread A & B continue to loop.  Because at 
any given point in time there's a thread that owns a read lock, C 
never returns from it's attempt to acquire a write lock.  Fixing this 
generally requires adding some sort of priority ordering to groups of 
lock requests.  For instance, 3&5 above may result in a new priority 
level and will thus block until the lower level lock from 2 has been 
serviced.  Implementing this can be non-trivial.

Bill Kempf