Lock Writer Lock supporting low priority authors

Question

I am trying to find (or implement) a Lock / Writer Lock that supports low priority authors, but failed to investigate any existing solutions.

What I mean when using a low-priority writer is "will give way to incoming readers or ordinary writers."

Of course, this will lead to starvation if there is a constant stream of readers, but this can be solved either using a temporary lock option ("try to synchronize the lock with a low write priority" and then switch to the usual timeout lock) or by changing the way readers read ( possibly intermittent reading for a short window).

If there is any literature describing something in these lines, I did not find it.

If there is a known (right!) Solution using regular locks, I would appreciate a description.

Answer 1

I don’t know anything 100% as your suggestion, but there are some existing interfaces that are close:

Many existing r / w locking APIs have a try lock interface, for example pthread_rwlock_trywrlock() on UN * X systems. They are not available and will only receive a lock if no one owns it and is not waiting for it.

Usually you use this rotation to block and / or artificially delay the attempt code (backtracking). That is, to 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 is not quite what you are asking for; it will receive the lock in order, but the low priority writer will rotate around the processor and / or receive it with a delay due to the (possibly unnecessary) delay.

The Solaris kernel has an rw_tryupgrade(9f) interface that can be used to check if the current thread is the only reader on the lock without a writer waiting, and if so, update the lock to exclusive / write, i.e. The code will look like this:

 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 little closer to what you ask, but still not quite the same thing - if it fails, you will have to give up readlock, perhaps back out (wait), request a read, try to update. This process is twisted again.

In addition, many UNIX systems, at least in fact, execute waiter sessions in order of priority; therefore, you will need to make your thread the lowest priority (if necessary, artificially) before trying the usual pending call to wrlock() ; anyone else who wants the same log while your thread is waiting will receive it before that, due to the way the scheduler works. Although on multiprocessor / core systems that are not necessarily guaranteed ...

Finally, SymbianOS (version of Symbian ^ 3) has an RRWlock class that can be made to prioritize readers over writers, so that it deliberately starves writers if there are readers waiting / inbound. Again, the behavior you want is not entirely accurate, as it affects all authors of a given lock, not just a specific one.

I'm afraid you will have to write your own priority castle with two lines of awakening the writer.

Answer 2

On top of my head, you need something like this:

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

... and PriorityRWLock :: acquire_write_lock () will look something like this:

 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 will not be too effective. You really would prefer to store rwcount in atom_int or similar, but the need for condition_variable eliminates this.

Temporary locking will be difficult due to the possible need for intermittent wait (). try_write_lock () must be doable.