|
|
Threads-Devel : |
From: Allen Pulsifer (pulsifer3_at_[hidden])
Date: 2007-08-04 06:07:14
> > If everyone unblocks, does that mean that after all
> existing readers
> > are done, one of the waiting readers can grab the mutex, then the
> > writer starts waiting again forcing all other readers to
> wait, so in
> > effect you have the possibility that one waiting reader goes at a
> > time, ad infinitum, for as long as readers continue to
> queue and grab
> > the mutex before a waiting writer?
>
> Yes, that's a possibility. It is up to the OS scheduler to
> ensure that threads don't wait for ever. If there are 49
> waiting readers and 1 waiting writer then there's a 1 in 50
> chance that the writer will wake first.
>
> It's done this way to prevent reader starvation. If writers
> have priority, then a waiting writer will prevent readers
> from proceeding until that writer is finished. If the writer
> is in a tight loop and reacquires the write lock soon after
> it is done, or there are multiple writers, then no readers
> will ever proceed. If waiting writers don't block the readers
> then the writer will starve. By unblocking all threads, the
> OS can decide which thread gets the lock. We had extensive
> discussions about this on the main boost list when I was
> developing the win32 implementation of this algorithm.
Hello Anthony,
I'm going to respectfully suggest that this needs to be rethought.
Let's start with this decision: if there are one or more waiting writers
then all new readers block. I'll not disagreeing with this decision, I just
want to point out its implications. The reason you make this decision is
because only one writer (and no readers) can access the resource at a time.
By making all new readers wait, you are allowing all existing readers to
finish, so the lock is then available For exclusive use by a writer. In
other words, the only reason for making all new readers wait is to allow the
writer to go. If your goal is not to allow the writer to go, then you might
as well have simply allowed the new readers to go immediately with shared
access instead of making them block.
Given that the whole reason for making the new readers wait is to allow the
writer to go, that's what the rwlock should do. If you do anything
different, or if due to OS interaction anything different happens (i.e., a
new reader goes instead of a writer), then I think its fair to say that the
lock has behaved poorly. Again, you would have been better off allowing
that particular new reader to go immediately instead of making it wait.
I agree this behavior could lead to reader starvation if there are a lot of
writers, but I think that would then either need a more sophisticated
implementation, or it would have to be handled at the application level.
The problem with the current new implementation is that its completely
unpredictable--it could lead to writer starvation, it could lead to
pathological behavior where only one reader goes at a time. We really don't
know until we test it on a particular OS, and we don't know what we need to
do at the application level to make it work. And if it does turn out that
the behavior is pathological, there is no way to fix it at the application
level. I would suggest that is not a very good behavior for a library.
If new readers always wait until all writers are done, then at least the
behavior is predicable and the same on all platforms, so it can be
anticipated and handled at the application level, which is a much better
situation IMHO, and a desired behavior for a general-purpose library.
At minimum I would suggest that the two approaches identified--"everyone
wakes up and its an OS free-for-all" vs. "readers wait until all writers are
done"-- should be a selectable option.
Allen