POSIX Tthread Programming/Conditional Variable
http://stackoverflow.com/questions/12033188/how-would-a-readers-writer-lock-be-implemented-in-c11
伪代码
read_lock() {
mutex.lock();
while (writer)
unlocked.wait(mutex);
readers++;
mutex.unlock();
}
read_unlock() {
mutex.lock();
readers--;
if (readers == 0)
unlocked.signal_all();
mutex.unlock();
}
write_lock() {
mutex.lock();
while (writer || (readers > 0))
unlocked.wait(mutex);
writer = true;
mutex.unlock();
}
write_unlock() {
mutex.lock();
writer = false;
unlocked.signal_all();
mutex.unlock();
}
That implementation has quite a few drawbacks, though.
Wakes up all waiters whenever the lock becomes available
If most of the waiters are waiting for a write lock, this is wastfull - most waiters will fail to acquire the lock, after all, and resume waiting. Simply usingsignal() doesn't work, because youdo want to wake up every waiting for a
read lock unlocking. So to fix that, you need separate condition variables for readability and writability.
No fairness. Readers starve writers
You can fix that by tracking the number of pending read and write locks, and either stop acquiring read locks once there a pending write locks (though you'll then starve readers!), or randomly waiting up either all readers or one writer (assuming you use
separate condition variable, see section above).
Locks aren't dealt out in the order they are requested
To guarantee this, you'll need a real wait queue. You could e.g. create one condition variable for each waiter, and signal all readers or a single writer, both at the head of the queue, after releasing the lock.
Even pure read workloads cause contention due to the mutex
This one is hard to fix. One way is to use atomic instructions to acquire read or write locks (usually compare-and-exchange). If the acquisition fails because the lock is taken, you'll have to fall back to the mutex. Doing that correctly is quite hard, though.
Plus, there'll still be contention - atomic instructions are far from free, especially on machines with lots of cores.
Conclusion
Implementing synchronization primitives correctly is hard. Implementing efficient and fair synchronization primitives iseven harder. And it hardly ever pays off. pthreads on linux, e.g. contains a reader/writer lock which
uses a combination of futexes and atomic instructions, and which thus probably outperforms anything you can come up with in a few days of work.
=========
另一个实现
http://stackoverflow.com/questions/8635963/read-write-lock-implementation-using-mutex-only
class rw_lock_t {
int NoOfReaders;
int NoOfWriters, NoOfWritersWaiting;
pthread_mutex_t class_mutex;
pthread_cond_t reader_gate;
pthread_cond_t writer_gate;
public:
rw_lock_t()
: NoOfReaders(0), NoOfWriters(0), NoOfWritersWating(0),
class_mutex(PTHREAD_MUTEX_INITIALIZER),
reader_gate(PTHREAD_COND_INITIALIZER),
writer_gate(PTHREAD_COND_INITIALIZER)
{}
~rw_lock_t()
{
pthread_mutex_destroy(&class_mutex);
pthread_cond_destroy(&reader_gate);
pthread_cond_destroy(&writer_gate);
}
void r_lock()
{
pthread_mutex_lock(&class_mutex);
//while(NoOfWriters>0 || NoOfWritersWaiting>0) //Writer Preference
while(NoOfWriters>0)
{
pthread_cond_wait(&reader_gate, &class_mutex);
}
NoOfReaders++;
pthread_mutex_unlock(&class_mutex);
}
void r_unlock()
{
pthread_mutex_lock(&class_mutex);
NoOfReaders--;
if(NoOfReaders==0 && NoOfWritersWaiting>0)
pthread_cond_signal(&writer_gate);
pthread_mutex_unlock(&class_mutex);
}
void w_lock()
{
pthread_mutex_lock(&class_mutex);
NoOfWritersWaiting++;
while(NoOfReaders>0 || NoOfWriters>0)
{
pthread_cond_wait(&writer_gate, &class_mutex);
}
NoOfWritersWaiting--;
NoOfWriters++;
pthread_mutex_unlock(&class_mutex);
}
void w_unlock()
{
pthread_mutex_lock(&class_mutex);
NoOfWriters--;
if(NoOfWritersWaiting>0)
pthread_cond_signal(&writer_gate);
//else //Writer Preference - don't signal readers unless no writers
pthread_cond_broadcast(&reader_gate);
pthread_mutex_unlock(&class_mutex);
}
};