How priority propagation works on read/write lock?

[Daniel Eischen]

On Wed, 18 Jan 2006, rookie wrote:

> >> This approach fails beacause you need to propagate priority for any
> blocking
> >> thread for any owners (if needed).
>
> > I'm not sure I follow -- got a simple example?
> > A writer won't be able to get the write lock until _all_ of the
> > current read lock owners have released the lock.  It doesn't
> > matter which of the readers you propagate to, eventually all
> > of them will have their priority propagated.
> >
> > On a single CPU system, there is no advantage to propagating
> > priority to all of the current readers because only one can
> > run at a time.  On an SMP system, the disadvantage is that you
> > lose the ability for multiple read lock owners to run at the
> > same time.
>
> Let's say: threads A, B, C own a read lock (RW1).
>
> After a while:
> - A blocks on a write lock (D thread owns)
> - B blocks on a read lock (owned by other threads, we say E1, E2, E3)
> - C blocks on a mutex (owned by F)
> Now if a thread G blocks on RW1 and its priority is higher than A,B,C (which
> might have the same priority) priority propagation is needed to hit D, { E1,
> E2, E3 } and F. If you just do priority propagation for one of them the
> other would not be updated.

You will eventually do priority propagation for all of them
(A, B, and C) until G's priority is <= the priority of RW1.
It doesn't matter if you do one at a time or all of them
at once.  They all (A, B, C) have to release RW1 before
G can run.

>
> turnstiles don't hurts beacause some intrusive lists are defined involving
> turnstiles and threads so a sort of "chain" like that:
>
> turnstile->thread->turnstile->thread...
>
> is provided. In the case of multple thread we could have a situation like:
>                thread1                                thread1
> turnstile->thread2->turnstile--------------->thread2
>                thread3->turnstile->thread     thread3
>
> And so on.
>
> I did a recursive algorithm for a new primitive (rwblock) which correctly
> implements priority propagation for multiple owners mechanism but there are
> 2 problems:
>
> 1) this algorithm is recursive and it's enough hard to change
> 2) With a new primitive some work of integration between existing
> (turnstiles) might be provided.
>
> Currently I'm working on both these problematics and I hope to do something
> better next times.

-- 
DE