How are they implemented especially in case of pthreads. What pthread synchronization APIs do they use under the hood? A little bit of pseudocode would be appreciated.
它们是如何实现的,尤其是在pthreads的情况下。他们在引擎盖下使用了什么pthread同步API?一点点伪代码将不胜感激。
2 个解决方案
#1
8
I haven't done any pthreads programming for a while, but when I did, I never used POSIX read/write locks. The problem is that most of the time a mutex will suffice: ie. your critical section is small, and the region isn't so performance critical that the double barrier is worth worrying about.
我有一段时间没有做任何pthreads编程,但是当我这样做时,我从未使用过POSIX读/写锁。问题是大多数情况下互斥锁就足够了:即。你的关键部分很小,而且这个区域并不那么重要,以至于双重障碍值得担心。
In those cases where performance is an issue, normally using atomic operations (generally available as a compiler extension) are a better option (ie. the extra barrier is the problem, not the size of the critical section).
在性能成为问题的情况下,通常使用原子操作(通常作为编译器扩展可用)是更好的选择(即,额外的障碍是问题,而不是关键部分的大小)。
By the time you eliminate all these cases, you are left with cases where you have specific performance/fairness/rw-bias requirements that require a true rw-lock; and that is when you discover that all the relevant performance/fairness parameters of POSIX rw-lock are undefined and implementation specific. At this point you are generally better off implementing your own so you can ensure the appropriate fairness/rw-bias requirements are met.
当你消除所有这些情况时,你会遇到需要真正的rw-lock的特定性能/公平性/ rw-bias要求的情况;并且当您发现POSIX rw-lock的所有相关性能/公平性参数未定义且特定于实现时。此时,您通常最好实施自己的,这样您就可以确保满足适当的公平/ rw偏差要求。
The basic algorithm is to keep a count of how many of each are in the critical section, and if a thread isn't allowed access yet, to shunt it off to an appropriate queue to wait. Most of your effort will be in implementing the appropriate fairness/bias between servicing the two queues.
基本算法是保持关键部分中每个人的数量的计数,并且如果还不允许访问线程,则将其分流到适当的队列以等待。您的大部分努力都是在为两个队列提供服务之间实现适当的公平/偏见。
The following C-like pthreads-like pseudo-code illustrates what I'm trying to say.
以下类似C-pthreads的伪代码说明了我想说的内容。
struct rwlock {
mutex admin; // used to serialize access to other admin fields, NOT the critical section.
int count; // threads in critical section +ve for readers, -ve for writers.
fifoDequeue dequeue; // acts like a cond_var with fifo behaviour and both append and prepend operations.
void *data; // represents the data covered by the critical section.
}
void read(struct rwlock *rw, void (*readAction)(void *)) {
lock(rw->admin);
if (rw->count < 0) {
append(rw->dequeue, rw->admin);
}
while (rw->count < 0) {
prepend(rw->dequeue, rw->admin); // Used to avoid starvation.
}
rw->count++;
// Wake the new head of the dequeue, which may be a reader.
// If it is a writer it will put itself back on the head of the queue and wait for us to exit.
signal(rw->dequeue);
unlock(rw->admin);
readAction(rw->data);
lock(rw->admin);
rw->count--;
signal(rw->dequeue); // Wake the new head of the dequeue, which is probably a writer.
unlock(rw->admin);
}
void write(struct rwlock *rw, void *(*writeAction)(void *)) {
lock(rw->admin);
if (rw->count != 0) {
append(rw->dequeue, rw->admin);
}
while (rw->count != 0) {
prepend(rw->dequeue, rw->admin);
}
rw->count--;
// As we only allow one writer in at a time, we don't bother signaling here.
unlock(rw->admin);
// NOTE: This is the critical section, but it is not covered by the mutex!
// The critical section is rather, covered by the rw-lock itself.
rw->data = writeAction(rw->data);
lock(rw->admin);
rw->count++;
signal(rw->dequeue);
unlock(rw->admin);
}
Something like the above code is a starting point for any rwlock implementation. Give some thought to the nature of your problem and replace the dequeue with the appropriate logic that determines which class of thread should be woken up next. It is common to allow a limited number/period of readers to leapfrog writers or visa versa depending on the application.
像上面代码这样的东西是任何rwlock实现的起点。考虑一下你的问题的本质,并用适当的逻辑替换dequeue,这些逻辑确定下一个应该唤醒哪个线程类。根据应用,允许有限数量/期限的读者超越作者或反之亦然是常见的。
Of course my general preference is to avoid rw-locks altogether; generally by using some combination of atomic operations, mutexes, STM, message-passing, and persistent data-structures. However there are times when what you really need is a rw-lock, and when you do it is useful to know how they work, so I hope this helped.
当然,我的一般偏好是完全避免rw-lock;通常使用原子操作,互斥体,STM,消息传递和持久数据结构的某种组合。然而,有时你真正需要的是一个锁定,当你这样做时,知道它们如何工作是有用的,所以我希望这有帮助。
EDIT - In response to the (very reasonable) question, where do I wait in the pseudo-code above:
编辑 - 响应(非常合理的)问题,我在哪里等待上面的伪代码:
I have assumed that the dequeue implementation contains the wait, so that somewhere within append(dequeue, mutex) or prepend(dequeue, mutex) there is a block of code along the lines of:
我假设dequeue实现包含wait,所以在append(dequeue,mutex)或prepend(dequeue,mutex)中的某个地方有一段代码:
while(!readyToLeaveQueue()) {
wait(dequeue->cond_var, mutex);
}
which was why I passed in the relevant mutex to the queue operations.
这就是为什么我将相关的互斥锁传递给队列操作。
#2
0
Each implementation can be different, but normally they have to favor readers by default due to the requirement by POSIX that a thread be able to obtain the read-lock on an rwlock multiple times. If they favored writers, then whenever a writer was waiting, the reader would deadlock on the second read-lock attempt unless the implementation could determine the reader already has a read lock, but the only way to determine that is storing a list of all threads that hold read locks, which is very inefficient in time and space requirements.
每个实现都可以不同,但由于POSIX要求线程能够多次获取rwlock的读锁定,因此默认情况下它们通常必须支持读者。如果他们喜欢编写者,那么只要编写者在等待,读者就会在第二次读取锁定尝试时死锁,除非实现可以确定读者已经有读锁定,但唯一的方法是确定存储所有线程的列表持有读锁,这在时间和空间要求上非常低效。
#1
8
I haven't done any pthreads programming for a while, but when I did, I never used POSIX read/write locks. The problem is that most of the time a mutex will suffice: ie. your critical section is small, and the region isn't so performance critical that the double barrier is worth worrying about.
我有一段时间没有做任何pthreads编程,但是当我这样做时,我从未使用过POSIX读/写锁。问题是大多数情况下互斥锁就足够了:即。你的关键部分很小,而且这个区域并不那么重要,以至于双重障碍值得担心。
In those cases where performance is an issue, normally using atomic operations (generally available as a compiler extension) are a better option (ie. the extra barrier is the problem, not the size of the critical section).
在性能成为问题的情况下,通常使用原子操作(通常作为编译器扩展可用)是更好的选择(即,额外的障碍是问题,而不是关键部分的大小)。
By the time you eliminate all these cases, you are left with cases where you have specific performance/fairness/rw-bias requirements that require a true rw-lock; and that is when you discover that all the relevant performance/fairness parameters of POSIX rw-lock are undefined and implementation specific. At this point you are generally better off implementing your own so you can ensure the appropriate fairness/rw-bias requirements are met.
当你消除所有这些情况时,你会遇到需要真正的rw-lock的特定性能/公平性/ rw-bias要求的情况;并且当您发现POSIX rw-lock的所有相关性能/公平性参数未定义且特定于实现时。此时,您通常最好实施自己的,这样您就可以确保满足适当的公平/ rw偏差要求。
The basic algorithm is to keep a count of how many of each are in the critical section, and if a thread isn't allowed access yet, to shunt it off to an appropriate queue to wait. Most of your effort will be in implementing the appropriate fairness/bias between servicing the two queues.
基本算法是保持关键部分中每个人的数量的计数,并且如果还不允许访问线程,则将其分流到适当的队列以等待。您的大部分努力都是在为两个队列提供服务之间实现适当的公平/偏见。
The following C-like pthreads-like pseudo-code illustrates what I'm trying to say.
以下类似C-pthreads的伪代码说明了我想说的内容。
struct rwlock {
mutex admin; // used to serialize access to other admin fields, NOT the critical section.
int count; // threads in critical section +ve for readers, -ve for writers.
fifoDequeue dequeue; // acts like a cond_var with fifo behaviour and both append and prepend operations.
void *data; // represents the data covered by the critical section.
}
void read(struct rwlock *rw, void (*readAction)(void *)) {
lock(rw->admin);
if (rw->count < 0) {
append(rw->dequeue, rw->admin);
}
while (rw->count < 0) {
prepend(rw->dequeue, rw->admin); // Used to avoid starvation.
}
rw->count++;
// Wake the new head of the dequeue, which may be a reader.
// If it is a writer it will put itself back on the head of the queue and wait for us to exit.
signal(rw->dequeue);
unlock(rw->admin);
readAction(rw->data);
lock(rw->admin);
rw->count--;
signal(rw->dequeue); // Wake the new head of the dequeue, which is probably a writer.
unlock(rw->admin);
}
void write(struct rwlock *rw, void *(*writeAction)(void *)) {
lock(rw->admin);
if (rw->count != 0) {
append(rw->dequeue, rw->admin);
}
while (rw->count != 0) {
prepend(rw->dequeue, rw->admin);
}
rw->count--;
// As we only allow one writer in at a time, we don't bother signaling here.
unlock(rw->admin);
// NOTE: This is the critical section, but it is not covered by the mutex!
// The critical section is rather, covered by the rw-lock itself.
rw->data = writeAction(rw->data);
lock(rw->admin);
rw->count++;
signal(rw->dequeue);
unlock(rw->admin);
}
Something like the above code is a starting point for any rwlock implementation. Give some thought to the nature of your problem and replace the dequeue with the appropriate logic that determines which class of thread should be woken up next. It is common to allow a limited number/period of readers to leapfrog writers or visa versa depending on the application.
像上面代码这样的东西是任何rwlock实现的起点。考虑一下你的问题的本质,并用适当的逻辑替换dequeue,这些逻辑确定下一个应该唤醒哪个线程类。根据应用,允许有限数量/期限的读者超越作者或反之亦然是常见的。
Of course my general preference is to avoid rw-locks altogether; generally by using some combination of atomic operations, mutexes, STM, message-passing, and persistent data-structures. However there are times when what you really need is a rw-lock, and when you do it is useful to know how they work, so I hope this helped.
当然,我的一般偏好是完全避免rw-lock;通常使用原子操作,互斥体,STM,消息传递和持久数据结构的某种组合。然而,有时你真正需要的是一个锁定,当你这样做时,知道它们如何工作是有用的,所以我希望这有帮助。
EDIT - In response to the (very reasonable) question, where do I wait in the pseudo-code above:
编辑 - 响应(非常合理的)问题,我在哪里等待上面的伪代码:
I have assumed that the dequeue implementation contains the wait, so that somewhere within append(dequeue, mutex) or prepend(dequeue, mutex) there is a block of code along the lines of:
我假设dequeue实现包含wait,所以在append(dequeue,mutex)或prepend(dequeue,mutex)中的某个地方有一段代码:
while(!readyToLeaveQueue()) {
wait(dequeue->cond_var, mutex);
}
which was why I passed in the relevant mutex to the queue operations.
这就是为什么我将相关的互斥锁传递给队列操作。
#2
0
Each implementation can be different, but normally they have to favor readers by default due to the requirement by POSIX that a thread be able to obtain the read-lock on an rwlock multiple times. If they favored writers, then whenever a writer was waiting, the reader would deadlock on the second read-lock attempt unless the implementation could determine the reader already has a read lock, but the only way to determine that is storing a list of all threads that hold read locks, which is very inefficient in time and space requirements.
每个实现都可以不同,但由于POSIX要求线程能够多次获取rwlock的读锁定,因此默认情况下它们通常必须支持读者。如果他们喜欢编写者,那么只要编写者在等待,读者就会在第二次读取锁定尝试时死锁,除非实现可以确定读者已经有读锁定,但唯一的方法是确定存储所有线程的列表持有读锁,这在时间和空间要求上非常低效。