Reader Writer Lock supporting low priority writers

Question

I am trying to find (or implement) a Reader/Writer Lock which supports low-priority writers, but have been unsuccessful in researching any existing solutions.

What I mean by low-priority writer is: "will yield its place in line" to incoming readers or normal writers.

Certainly will lead to starvation if there is a constant stream of readers, but this could be solved either with a timed lock variant ("try timed low priority writer lock" and then switching to a normal lock on timeout) or by changing the way readers are issued (perhaps periodically halting reads for a short window).

If there is any literature describing something along these lines, I have not found it.

If there is a known (correct!) solution leveraging regular locks, I would would appreciate a description.

Answer 1

I don't know anything 100% like your proposal, but there's some existing interfaces that are close:

Many existing r/w lock APIs have a "try lock" interface, like pthread_rwlock_trywrlock() on UN*X systems. These are wait-free and will only acquire the lock if noone owns it nor waits for it already.

You'd normally use this spinning for the lock, and/or artificially delaying the try code (back off). I.e. have code like:

for (count = 0; count < MAX_SPINS && (locked = trywrlock(lock)); count++);
if (locked) {
    delay(some_backoff);
    wrlock(lock);         /* or try spinning loop above again ? */
}

Unfortunately this isn't exactly what you ask for; it'll get the lock late alright, but the low-prio writer will spin on CPU and/or get it in a delayed fashion due to the (possibly unnecessary) backoff.

The Solaris kernel has an interface rw_tryupgrade(9f) that can be used to test if the current thread is the only reader on the lock with no writer waiting and if so, upgrade the lock to exclusive/write, i.e. you'd code like:

if (!rw_tryenter(lock, RW_WRITER)) {
    rw_enter(lock, RW_READER);    /* this might wait for a writer */
    if (!rw_tryupgrade(lock)) {   /* this fails if >1 reader / writer waiting */
        /* do what you must to if you couldn't get in immediately */
    }
}

Which is a bit closer to what you ask for but still not quite the same - if it fails, you'd have to drop the readlock, possibly back off (wait), reaquire the readlock, try to upgrade. That process again amounts to spinning.

Also, many UNIX systems at least actually perform waiter wakeups in order of scheduling priority; so you'd have to make your thread lowest priority (if necessarily, artificially) before attempting an ordinary, waiting wrlock() call; whoever else wants the same writelock while your thread is waiting will get it before that, by virtue of how the scheduler works. Though on multiprocessor/core systems that's not necessarily guaranteed ...

Finally, SymbianOS (the Symbian^3 version) has a RRWlock class that can be made to prioritize readers over writers, so that it will deliberately starve writers if there are readers waiting / coming in. Again, not quite exactly the behaviour you want, as it affects all writers on a given lock, not just a specific one.

I'm afraid you'd have to write your own prioritized lock, with two writer wakeup queues.

Answer 2

Here what you are looking at is somewhat of prioritization between reader and writer, such that low priority writer always give first chance to high priority reader. This obviously could lead to a starvation for the low priority writer because of its generosity.

This can be achieved at two different level : 1. From application side : This is an usual approach, as normally mutex are not biased. Before threads contest for locking, the application logic should itself decides which thread is with higher priority and allow that thread to go for locking. This usually become application specific:

--> task executioner approach : executioner thread execute available task only based on priority. It resolves priority based execution at executioner level, but same issue pop up above that level. This works as long mutex implementation in FIFO based. This also need to resolve the issue with starvation.

2. Write a biased locking mechanism, which understand priority and allow higher priority thread to lock. This also need to ensure "No starvation". An improvised version of mutex is possible to be implemented.

Answer 3

Off the top of my head, you'd want something like this:

class PriorityRWLock
{ 
  int                rwcount;
  mutex              mtx;
  condition_variable cv;
  priority_queue<writer_info> writers;
};

... and PriorityRWLock::acquire_write_lock() would look something like:

lock_guard raii(mtx);

do {
if ( rwcount==0 ) // == no read or write locks
{
  if ( writers.top().thread == thread::self() )
  {  rwcount = -1; writers.pop_front(); break; } // == exclusive write access
  else 
  { 
     // wake up the waiting thread(s) and sleep
     writers.push( writer_info(thread::self(),priority) ); 
     cv.notify_all();
     cv.wait(mtx); 
  }
}
else
{ cv.wait(mtx); }  // sleep
} while ( true );

... or something close to that.

It isn't going to be overly efficient. You would really prefer to store rwcount in an atomic_int or similar but the need for the condition_variable precludes that.

A timed lock would be tricky because of the possible need to intermittently wait(). try_write_lock() should be doable tho.