Boost logo

Boost Users :

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
> > 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
> your comments I got it working and it behaves as I expect it would.
> would surely appreciate if you (or someone else) could futher
> 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

Boost-users list run by williamkempf at, kalb at, bjorn.karlsson at, gregod at, wekempf at