c*********l
发帖数: 3438 | | s********r
发帖数: 403 | 2 rw lock 有很多变种。
最基本的，如果不考虑 writer blocked by reader -> starvation, 感觉用一个
mutex 控制 counter 就够了。
fair 一点，用２个 mutex. | n****r
发帖数: 120 | | s********r
发帖数: 403 | 4 我觉得大致是这样
[reader]:
get_mutex();
reader++;
release_mutex()
Read();
get_mutex();
reader--;
release_mutex()
[writer]:
for (;;)
{
get_mutex();
if (reader > 0)
{
release_mutex();
}
write();
release_mutex();
break; // Made it
}
如果想防止 reader block writer forever (starvation), 再加一个 mutex_wr, 当
writer 抢到 mutex_wr 后，阻止 reader++，直到 reader 全部释放，writer 能够拿
到第一个 mutex 进行写操作。
【在 n****r 的大作中提到】
: 求莎翁多讲点，给个码！
| c*********l
发帖数: 3438 | 5 这个writer 有bug吧. 少了continue
【在 s********r 的大作中提到】
: 我觉得大致是这样
: [reader]:
: get_mutex();
: reader++;
: release_mutex()
: Read();
: get_mutex();
: reader--;
: release_mutex()
: [writer]:
| s********r
发帖数: 403 | 6 对，你自己给补上。
最近连续睡眠太少，脑子有些不好使了。
面试前一定要想办法睡好
【在 c*********l 的大作中提到】
: 这个writer 有bug吧. 少了continue
| r*c
发帖数: 167 | 7 有人做了个, 没试过, 先贴上.
http://stackoverflow.com/questions/8635963/read-write-lock-impl
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 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 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_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);
}
}; | s********r
发帖数: 403 | 8 一般 google 搜到的就是这个。
看上去稍微长了些，reader / writer lock 本质就是控制一个 atomic counter, 外
加 block 操作和 一对多的 event signal |
| c**1
发帖数: 71 | 9 the code by sharkspear is so wrong, even after the "continue" is added. two
flaws are addressed by scanning it:
read_lock does not block when someone is writing
write_lock is essentially a busy wait loop, instead of going to sleep | s********r
发帖数: 403 | 10 [1] writer block reader
writer(),
一旦发现 reader == 0, 马上进入写操作不释放 mutex, 直到写完。
release_mutex() 发生在写完之后，release 之前 reader 无法占有 mutex 增加
counter,不能进入read 操作。
[2] 这个是最基本版，用来演示原理。考虑 performance，可以不用 reader / writer
lock，好的 option 针对具体 case 有的是。
另外，您觉得在多核系统中， goto sleep 是个好的 option 吗？
进程切换大约多少个时钟周期啊？
two
【在 c**1 的大作中提到】
: the code by sharkspear is so wrong, even after the "continue" is added. two
: flaws are addressed by scanning it:
: read_lock does not block when someone is writing
: write_lock is essentially a busy wait loop, instead of going to sleep
| | | c**1
发帖数: 71 | 11 #1: right writer can block reader
#2: of course I mean suspend the thread until being notified. condition
variable is needed to implement this, like the sample from stackoverflow.
infinite busy wait is never a good idea. consider these situations:
#1 single cpu system, writer has higher priority while it is in the busy
wait, reader will never has a chance to --reader, thus deadlock
#2 even in multi cpu system, when a reader is preempted after ++reader,
enough number of writers coming into the busy wait will still cause the
system to deadlock | s********r
发帖数: 403 | 12 #1 You are right about the notification by condition number.
My point is that using one mutex is the easiest way to explain what a basic
reader / writer lock is, before moving to more details.
#2 In certain situations, for SMP, local spin can be better, that is how
spinlock works in kernel.
【在 c**1 的大作中提到】
: #1: right writer can block reader
: #2: of course I mean suspend the thread until being notified. condition
: variable is needed to implement this, like the sample from stackoverflow.
: infinite busy wait is never a good idea. consider these situations:
: #1 single cpu system, writer has higher priority while it is in the busy
: wait, reader will never has a chance to --reader, thus deadlock
: #2 even in multi cpu system, when a reader is preempted after ++reader,
: enough number of writers coming into the busy wait will still cause the
: system to deadlock
| c**1
发帖数: 71 | 13 if an implementation is incorrect, it doesn't matter whether it is simple.
In user space, thread can go to sleep at any time, nothing can guarantee
that a spin can always get the lock, so all spinlocks in user space have a
limit on how long it can spin, and if it still does not get the lock, it
suspends itself, waiting for other to wake it up. It is impossible to use
only mutex to implement this suspend-and-wait-for-notify.
Even in kernel, it is very hard to get the guarantee that the lock holder
does not block on anything and will release the lock in a timely manner. | s********r
发帖数: 403 | 14 The semantics of reader / writer lock is:
[1] Allow multiple readers for read_op(), when reader reads, no writer can
write
[2] When writer perform write_op(), no reader can read_op() successfully.
Would you think that one mutex implementation can describe the above
semantics?
Besides, what do you mean:
"Even in kernel, it is very hard to get the guarantee that the lock holder
does not block on anything and will release the lock in a timely manner."
In Linux kernel, the spinlock works on hardware threads environment, one
hardware thread call spinlock() spins() on itself.
The concern from spinlock is not what you are talking about, it is mainly
from the perspective of cache consistence overhead. | c**1
发帖数: 71 | 15 any lock has an implicit requirement: no self deadlock. your implementation
does not meet this requirement.
what do you mean by "one hardware thread call spinlock affects itself"? any
lock involves multiple threads.
kernel uses spinlock because sometimes it is not safe to go to sleep. In
order for it to spin, every user of the lock has to be careful not to go to
sleep and release the lock quickly. | s********r
发帖数: 403 | 16 [1] That one mutex method shows what the reader / writer lock in semantics,
if you watch carefully, I did not provide the interface such as r_lock()
or w_lock().
That is sufficient to explain the functionality, if they do not try to hold
the mutex again, which does not make any sense. The write() operation only
do write job, it does not hold any mutex.
[2] spinlock() functions in hardware threads environment. It is pointless to
use spinlock() is a uniprocessor environment. And it is not used to hold
for long term. I think I have explain very clearly
"#2 In certain situations, for SMP, local spin can be better, that is how
spinlock works in kernel."
implementation
any
to
【在 c**1 的大作中提到】
: any lock has an implicit requirement: no self deadlock. your implementation
: does not meet this requirement.
: what do you mean by "one hardware thread call spinlock affects itself"? any
: lock involves multiple threads.
: kernel uses spinlock because sometimes it is not safe to go to sleep. In
: order for it to spin, every user of the lock has to be careful not to go to
: sleep and release the lock quickly.
| c**1
发帖数: 71 | 17 Regarding the deadlock, let me give the detail on when it can happen
#1, thread A start reading, it successfully increased read count, then gets
preeempted
#2, thread B comes to write, it starts busy wait loop
#3, in uni processor system, when B has higher priority, A will never be
scheduled again, hence a dead lock
even in a SMP, when enough number of writers got to busy loop, deadlock can
still happen
As I explained, in user space, no one can guarantee a timely free from
lock holder, so all spin locks need a limit on spin, and suspend it self if
still does not get the lock
Even in kernel, spin lock can only be used when there is a guarantee of
timely unlock from lock holder, and it is hard.
In order to show your criteria of rw lock is not sufficient, here is another
implementation, which meets your criteria, but nevertheless incorrect:
// ***NOTE**** incorrect implementation of rw lock
read_lock() {
while(1) { atomic_inc(&read_count); if (write_count) { atomic_dec(&read_
count); } else break; }
}
read_unlock() {atomic_dec(&read_count); }
write_lock() {
while(1) {
atomic_inc(&write_count);
if ( write_count > 1 || read_count > 0) {
atomic_dec(&write_count);
} else {
break;
}
}
write_unlock() { atomic_dec(&write_count); }
| s********r
发帖数: 403 | 18 这个不是我的 implementation, 一看就是不对的.
不应当在完成 write_lock() 之前 atomic_inc(&write_count)，逻辑上不正确。
Anyway, reader / writer lock 不是什么 undocumented technique,过多争论没有
mystery 的技术没什么意思。
当然，如果你写一个比 stackowerflow 上面更简练的 implmentation,bug free,
非常欢迎拿出来 share。大家或许能很快派上用场。 | c**1
发帖数: 71 | 19 Make sure you understand my implementation. It is incorrect, but the place
you point out is correct. the update of write_count has to happen before
checkinh whether it is safe to continue.
The point of my flawed implementation is to show that the two requirements
you gave are not sufficient.
The following is my answer in one of my interviews.
read_lock() { lock_guard lk(mutex); while(writing) condition.wait(); ++read_
count;}
read_unlock() { lock_guard lk(mutex); if (--read_count == 0) condition.
notify_all(); }
write_lock() { lock_guard lk(mutex); while(writing || read_count) condition.
wait(); writing = true; }
write_unlock() { lock_guard lk(mutex) ; writing = false; condition.notify_
all(); } | n*****u
发帖数: 465 | 20 >>> infinite busy wait is never a good idea.
Do not be so certain...this is used in real-time production systems when you
care about latency in micro seconds. Yes 100% CPU utilization but by design
.
【在 c**1 的大作中提到】
: #1: right writer can block reader
: #2: of course I mean suspend the thread until being notified. condition
: variable is needed to implement this, like the sample from stackoverflow.
: infinite busy wait is never a good idea. consider these situations:
: #1 single cpu system, writer has higher priority while it is in the busy
: wait, reader will never has a chance to --reader, thus deadlock
: #2 even in multi cpu system, when a reader is preempted after ++reader,
: enough number of writers coming into the busy wait will still cause the
: system to deadlock
| | | c**1
发帖数: 71 | 21 this is just a by-product of pointing out sharkspear's implementation is
wrong, hope you agree it.
As I indicated in the spin lock usage in kernel, busy wait requires the
guaranteed timely unlock from lock holder, which is impossible in normal
user space. | f*******b
发帖数: 520 | | n*****u
发帖数: 465 | 23 这完艺儿太费脑子,又没啥市场,有空刷刷 leetcode 更有用.
【在 c**1 的大作中提到】
: this is just a by-product of pointing out sharkspear's implementation is
: wrong, hope you agree it.
: As I indicated in the spin lock usage in kernel, busy wait requires the
: guaranteed timely unlock from lock holder, which is impossible in normal
: user space.
| Y********f
发帖数: 410 | 24 贴个我写的吧，C++，有点繁琐，write优先。
class rwlock
{
public:
rwlock();
void rdlock();
void wrlock();
void unlock();
private:
pthread_mutex_t mutex;
pthread_cond_t condRead;
pthread_cond_t condWrite;
int readerCount;
int writeWaitCount;
bool writeLock;
};
rwlock::rwlock() : readerCount(0), writeLock(false), writeWaitCount(0)
{
pthread_mutex_init(&mutex, NULL); //forget NULL
pthread_cond_init(&condRead, NULL);
pthread_cond_init(&condWrite, NULL);
}
void rwlock::rdlock()
{
pthread_mutex_lock(&mutex);
while (writeLock || writeWaitCount)
{
pthread_cond_wait(&condRead, &mutex);
}
readerCount++;
pthread_mutex_unlock(&mutex);
}
void rwlock::wrlock()
{
pthread_mutex_lock(&mutex);
writeWaitCount++;
while (readerCount > 0 || writeLock)
{
pthread_cond_wait(&condWrite, &mutex);
}
writeWaitCount--;
writeLock=true;
pthread_mutex_unlock(&mutex);
}
void rwlock::unlock()
{
pthread_mutex_lock(&mutex);
if (writeLock)
{
writeLock = false;
}
else
{
readerCount--;
}
if (writeWaitCount > 0)
{
pthread_cond_signal(&condWrite);
}
else
{
pthread_cond_broadcast(&condRead);
}
pthread_mutex_unlock(&mutex);
}
【在 c*********l 的大作中提到】
: 谢谢。
| c**1
发帖数: 71 | 25 Yellowleaf's implementation looks correct to me. some minor issue though.
* in c++, it is better to use RAII to lock / unlock mutex
* no need to signal if --readerCount != 0 |
|
