[Thread] order of shared_lock and unique_lock acquisitions
Hi, I am trying to use shared_lock and unique_lock on a shared_mutex to allow read-functions to access a certain resource in parallel, but write functions use the resource exclusively. Is there a way to determine the order in which the (shared) locks are acquired? I tried testing with the attached program and got rather weird and (seemingly) non-deterministic results. In the test program (see attachment), I start 9 threads of readers(r) and writers(w). Before doing anything else, the sleep and wake up in groups. rrww rr w rr There is one second delay between the groups I would expect to see them working in this order: rr w w rr w rr The first group could be scrambled of course since they race for the lock. But at least I would expect the order of groups to be maintained. I get quite different results, though, and the results differ from run to run. The weirdest result I saw until now is attached. rr rrr (these do not start before the first group is finished) w w w (the last writer is handled in second position btw) r This I do not understand at all. The readers are using the shared mutex. Why is the second group waiting for the first to be finished? And how can the last writer be handled in second place? I am at a total loss here... System information: ------------------- boost-1.36 Ubuntu-8.04 gcc-4.2.4 Intel Quad Core processor Thanks in advance, Roland reader(0) at 0 sleeping 5 reader(1) at 0 sleeping 5 writer(2) at 0 sleeping 5 writer(3) at 0 sleeping 5 reader(4) at 0 sleeping 6 reader(5) at 0 sleeping 6 writer(6) at 0 sleeping 7 reader(7) at 0 sleeping 8 reader(8) at 0 sleeping 8 reader(0) at 5 trying to acquire lock reader(0) at 5 got lock reader(1) at 5 trying to acquire lock reader(1) at 5 got lock writer(2) at 5 trying to acquire lock writer(3) at 5 trying to acquire lock reader(4) at 6 trying to acquire lock reader(5) at 6 trying to acquire lock writer(6) at 7 trying to acquire lock reader(7) at 8 trying to acquire lock reader(8) at 8 trying to acquire lock reader(0) at 10 finished reader(1) at 10 finished reader(4) at 10 got lock reader(5) at 10 got lock reader(7) at 10 got lock reader(4) at 15 finished reader(5) at 15 finished reader(7) at 15 finished writer(3) at 15 got lock writer(3) at 20 finished writer(6) at 20 got lock writer(6) at 25 finished writer(2) at 25 got lock writer(2) at 30 finished reader(8) at 30 got lock reader(8) at 35 finished
AMDG Roland Bock wrote:
Hi,
I am trying to use shared_lock and unique_lock on a shared_mutex to allow read-functions to access a certain resource in parallel, but write functions use the resource exclusively.
Is there a way to determine the order in which the (shared) locks are acquired? I tried testing with the attached program and got rather weird and (seemingly) non-deterministic results.
In the test program (see attachment), I start 9 threads of readers(r) and writers(w). Before doing anything else, the sleep and wake up in groups.
<snip>
This I do not understand at all. The readers are using the shared mutex. Why is the second group waiting for the first to be finished? And how can the last writer be handled in second place?
First off, there is a race calculating the sleep times. There is absolutely no guarantee that the readers and writers get any particular distribution of wait times. For instance all the readers could get the early read times. Not to mention that it is possible for all the threads to wait for 5 seconds. In addition, while the reader or the writer does the second sleep, (while still holding the lock) all the other threads come out of their initial sleeps. In Christ, Steven Watanabe
Steven, thanks for the answer!
First off, there is a race calculating the sleep times. There is absolutely no guarantee that the readers and writers get any particular distribution of wait times. For instance all the readers could get the early read times. Not to mention that it is possible for all the threads to wait for 5 seconds.
According to the log, none of this does happen, but you are right, this could happen (and it does sometimes).
In addition, while the reader or the writer does the second sleep, (while still holding the lock) all the other threads come out of their initial sleeps.
OK, and then Zeljko's answer comes into play which says that Mutexes are not FIFO. Still, I wonder why I got two readers in parallel, and the next readers do not acquire the shared lock before the first two release the shared lock (and no writer in between)? Also, are any preferred orders, like writers having precedence over readers (in order to avoid writer starvation)? Thanks and regards, Roland
On Fri, Jan 09, 2009 at 01:02:36PM +0100, Roland Bock wrote:
Is there a way to determine the order in which the (shared) locks are acquired? I tried testing with the attached program and got rather weird and (seemingly) non-deterministic results.
Threads are by their nature non-deterministic; all ordering must be implemented manually. Even with a single, ordinary, lock, there are no guarantees on the order in which waiters are being scheduled upon unlock.
This I do not understand at all. The readers are using the shared mutex. Why is the second group waiting for the first to be finished?
Probably because the mutex implementation noticed that there have appeared new writers. This is just a wild guess, I haven't looked at your program. RW mutex implementation has to be careful not to starve readers nor writers.
And how can the last writer be handled in second place?
That's perfectly normal, mutexes are not FIFO. Now that you've mentioned RW-locks, I remembered a nice article on concurrency: http://queue.acm.org/detail.cfm?id=1454462
Roland Bock <rbock@eudoxos.de> writes:
Hi,
I am trying to use shared_lock and unique_lock on a shared_mutex to allow read-functions to access a certain resource in parallel, but write functions use the resource exclusively.
Is there a way to determine the order in which the (shared) locks are acquired? I tried testing with the attached program and got rather weird and (seemingly) non-deterministic results.
In the test program (see attachment), I start 9 threads of readers(r) and writers(w). Before doing anything else, the sleep and wake up in groups.
rrww rr w rr
There is one second delay between the groups I would expect to see them working in this order:
rr w w
rr
w
rr
The first group could be scrambled of course since they race for the lock. But at least I would expect the order of groups to be maintained.
I get quite different results, though, and the results differ from run to run. The weirdest result I saw until now is attached.
rr
rrr (these do not start before the first group is finished)
w w w (the last writer is handled in second position btw)
r
This I do not understand at all. The readers are using the shared mutex. Why is the second group waiting for the first to be finished? And how can the last writer be handled in second place?
The implementation detects that there are waiting writers, and so prevents further shared locks being acquired. Once all the existing shared locks are released, then all currently-waiting threads compete for the lock. In this case, three readers got in before the writers woke. The lock acquisition is not FIFO. The OS decides which of the waiting threads acquires the lock next. Anthony -- Anthony Williams Author of C++ Concurrency in Action | http://www.manning.com/williams Custom Software Development | http://www.justsoftwaresolutions.co.uk Just Software Solutions Ltd, Registered in England, Company Number 5478976. Registered Office: 15 Carrallack Mews, St Just, Cornwall, TR19 7UL, UK
Antony, Thanks for the answer. This also answers the follow-up questions I had for Steven and Zeljko. Thanks and regards, Roland Anthony Williams wrote:
Roland Bock <rbock@eudoxos.de> writes:
Hi,
I am trying to use shared_lock and unique_lock on a shared_mutex to allow read-functions to access a certain resource in parallel, but write functions use the resource exclusively.
Is there a way to determine the order in which the (shared) locks are acquired? I tried testing with the attached program and got rather weird and (seemingly) non-deterministic results.
In the test program (see attachment), I start 9 threads of readers(r) and writers(w). Before doing anything else, the sleep and wake up in groups.
rrww rr w rr
There is one second delay between the groups I would expect to see them working in this order:
rr w w
rr
w
rr
The first group could be scrambled of course since they race for the lock. But at least I would expect the order of groups to be maintained.
I get quite different results, though, and the results differ from run to run. The weirdest result I saw until now is attached.
rr
rrr (these do not start before the first group is finished)
w w w (the last writer is handled in second position btw)
r
This I do not understand at all. The readers are using the shared mutex. Why is the second group waiting for the first to be finished? And how can the last writer be handled in second place?
The implementation detects that there are waiting writers, and so prevents further shared locks being acquired. Once all the existing shared locks are released, then all currently-waiting threads compete for the lock. In this case, three readers got in before the writers woke.
The lock acquisition is not FIFO. The OS decides which of the waiting threads acquires the lock next.
Anthony
participants (4)
-
Anthony Williams -
Roland Bock -
Steven Watanabe -
Zeljko Vrba