Subj : Improving read-write lock
To   : comp.programming.threads
From : Rob
Date : Wed Feb 16 2005 03:50 pm

Hi,

Recently I have been debugging an (C++) application that contained a 
deadlock.
And it made me (and a colleague) think about an improved read-write lock.
The deadlock was caused by a function that took a read-lock and
somewhere further a write-lock without releasing the read-lock first.

void doStuff() {
     rl = list.getReadlock()
     foreach (item in list)
     {
         if (item found)
         {
             wl = list.getWritelock();
             list.removeByIndex(item index);
             wl.release()
             rl.release();
             return;
         }
     }
     rl.release();
}

This is a common mistake. 2 threads enter doStuff() and take the read-lock,
making it impossible for any thread to get a write-lock later.

The easiest way to solve the problem is to take a write-lock immediately.
However this will decrease the concurrency performance, even when no write
action will be take in the for loop (no item found).

Another way to solve it is to 'upgrade' the read-lock to a write-lock when
the item is found, by releasing the read-lock and taking a write-lock.
However care must be taken that the list is not altered between releasing a
read-lock and taking the write-lock. Otherwise the removeByIndex might 
remove
the wrong item. Putting this 'upgrade' in an atomic operation might 
solve this,
but it will cause the original dead-lock again.
Therefore after the lock has been 'upgraded' the entire list has to be 
searched
from the beginning again, causing a lot of overhead. See the code below:

void doStuff() {
     doStuff(list.GetReadLock());
}

void doStuff(lock) {
     foreach (item in list)
     {
         if (item found)
         {
             if (lock is read)
                 doStuff(lock.upgrade());
             else
             {
                 list.removeByIndex(item index);
                 lock.release();
                 return;
             }
         }
     }
     lock.release();
}


An idea my colleague has was to introduce a new kind of lock type: 
ReadPromotable.
The new lock could give 3 kind of locks:
- Read: for only reading. You would take this lock if you are sure you 
only need to read.
   Multiple read-locks can exist as usual.
- Write: for reading and writing. You would take this lock if you are 
sure you will need
   to do a lot of writing. Only one write-lock can exist, without any 
concurrent read-locks.
- ReadPromotable: for reading and possibility to upgrade to a write 
lock. You would
   take this lock in the doStuff() function above, because you need to 
read, but
   maybe need to write to without letting someone modify the object first.
   Only one ReadPromotable lock can exist, however multiple read-locks 
can exist at
   the same time as the ReadPromotable lock.

When the ReadPromotable lock is being upgraded to a write lock, it has 
to wait for any
read-locks to finish.

It's not a perfect situation of course, because only one ReadPromotable 
lock exists.
However I hope you can see the improved concurrency compared to a normal 
read-write lock.

I would like to know your thought about this.
Maybe something like this already exists and has been implemented. 
Please give
me some resources (url's) in that case.
Or maybe a much better improvement can be made and this idea is just 
stupid :)
Please let me know in that case too.

.