Re: Threads: rw_mutex design + sample implementation

From: dmoore99atwork (dmoore_at_[hidden])
Date: 2002-03-11 10:14:42

On the subject of priority inversion:

Dan'l Miller wrote:
 
> >   Intrinsic in these 3 choices is that the preference
> > applies only to threads with the same thread-priority
> > metric.  If a lower-priority thread acquires an exclusive
> > lock (i.e., the superior write lock in rwmutex), then
> > higher-priority threads request a shared lock (i.e., the
> > inferior read lock in rwmutex), then in many environments
> > (e.g., RTOSes, DBMSes) the over-all system can enter a state
> > where the lower-priority thread is never scheduled to run
> > and the higher-priority threads all block due to their
> > inferior lock requests, waiting for this never-scheduled
> > lower-priority thread to release its superior lock.  In some
> > system-states, the lower-priority thread will never be
> > scheduled to execute and thus will never be able to get
> > around to executing the code which releases its superior
> > lock.  Thus a deadlock situation occurs.  This case is
> > called priority inversion.

I do not have much experience with RTOSes, but I do have a question 
relating to this:

If the higher priority thread calls rw_mutex::do_sharedlock() and 
is "blocked" because the lock is exclusively held, then in general 
this is not a busy kind of waiting.  In particular, if the lock is 
not available, then the high priority thread will be waiting on an OS-
level mutex, semaphore, or condition variable, depending on 
implementation platform.  Wouldn't most OSes not even schedule the 
higher priority thread until the lock was released?  Again, pls. 
excuse my RTOS ignorance here.

Now, I can see where OTHER high priority threads in the same process 
who were -Not- contending for the lock could interfere with the low-
priority thread's ability to get its work done and release the lock.  
This could happen for ordinary locks/mutexes too, right?

However, short of a complete user-space scheduler implementation, I 
don't see what can be done in this case, save for the higher priority 
threads running a timed wait for the lock, then taking action in 
boosting/lowering priorities as needed.

Maybe acquiring the exclusive lock could include additional 
(optional) parameters indicative of the required priority boost?  It 
seems like for most practical uses of rw_mutex, you would want anyone 
holding the exclusive lock to get in & out as quickly as possible if 
contention is likely.

Of course, this type of solution would require help from 
boost::thread on priority levels, etc. which will be a nasty cross-
platform portability issue....

Thanks,
Dave