Hi all, I'm in need to have a reader/writer mutex with no starvation (I'd say a fair mutex), before to make a my own implementation I have checked the boost one to see if it makes starvation or not, and I'm a bit puzzled about the behave: I'm experiencing this: reader 1 start ... writer 1 running ... reader 2 start ... writer 2 running ... writer 1 start << blocked reader 3 start << blocked reader 4 start << blocked until now it seems that reader 3 and reader 4 are waiting because there is a writer waiting and then the writer will run before reader 3 and 4, unfortunately this is not the case, the execution continues like this: reader 1 ends reader 2 ends ... writer 3 running ... ... writer 4 running ... reader 3 ends reader 4 ends ... writer 1 running ... writer 1 ends isn't that a waste? Why make reader 3 and 4 waiting and then make those running before the writer? The code to reproduce that is at the end. Regards Gaetano Mendola #include <iostream> #include <boost/thread.hpp> typedef boost::shared_mutex TMutex; TMutex theMutex; struct Writer { Writer(const size_t anId) : theId(anId) { } void operator()() { std::cout << "writer " << theId << " start" << std::endl; boost::unique_lock<TMutex> myLock(theMutex); std::cout << " ... writer " << theId << " running ..." << std::endl; ::sleep(7); std::cout << "writer " << theId << " ends" << std::endl; } size_t theId; }; struct Reader { Reader(const size_t anId) : theId(anId) { } void operator()() { std::cout << "reader " << theId << " start" << std::endl; boost::shared_lock<TMutex> myLock(theMutex); std::cout << " ... writer " << theId << " running ..." << std::endl; ::sleep(7); std::cout << "reader " << theId << " ends" << std::endl; } size_t theId; }; int main (int argc, char** argv) { Reader r1(1), r2(2), r3(3), r4(4); Writer w(1); boost::thread myR1(boost::ref(r1)); ::sleep(1); boost::thread myR2(boost::ref(r2)); ::sleep(1); boost::thread myW1(boost::ref(w)); ::sleep(1); boost::thread myR3(boost::ref(r3)); ::sleep(1); boost::thread myR4(boost::ref(r4)); myW1.join(); myR1.join(); myR2.join(); myR3.join(); myR4.join(); }
On 08/10/2010 01:11 PM, Gaetano Mendola wrote:
Hi all, I'm in need to have a reader/writer mutex with no starvation (I'd say a fair mutex), before to make a my own implementation I have checked the boost one to see if it makes starvation or not, and I'm a bit puzzled about the behave:
I'm experiencing this:
reader 1 start ... writer 1 running ... reader 2 start ... writer 2 running ... writer 1 start << blocked reader 3 start << blocked reader 4 start << blocked
until now it seems that reader 3 and reader 4 are waiting because there is a writer waiting and then the writer will run before reader 3 and 4, unfortunately this is not the case, the execution continues like this:
reader 1 ends reader 2 ends ... writer 3 running ... ... writer 4 running ... reader 3 ends reader 4 ends ... writer 1 running ... writer 1 ends
isn't that a waste? Why make reader 3 and 4 waiting and then make those running before the writer? The code to reproduce that is at the end.
Regards Gaetano Mendola
#include <iostream> #include <boost/thread.hpp>
typedef boost::shared_mutex TMutex; TMutex theMutex;
struct Writer { Writer(const size_t anId) : theId(anId) { }
void operator()() { std::cout << "writer " << theId << " start" << std::endl; boost::unique_lock<TMutex> myLock(theMutex); std::cout << " ... writer " << theId << " running ..." << std::endl; ::sleep(7); std::cout << "writer " << theId << " ends" << std::endl; }
size_t theId; };
struct Reader { Reader(const size_t anId) : theId(anId) { }
void operator()() { std::cout << "reader " << theId << " start" << std::endl; boost::shared_lock<TMutex> myLock(theMutex); std::cout << " ... writer " << theId << " running ..." << std::endl; ::sleep(7); std::cout << "reader " << theId << " ends" << std::endl; }
size_t theId; };
int main (int argc, char** argv) {
Reader r1(1), r2(2), r3(3), r4(4); Writer w(1);
boost::thread myR1(boost::ref(r1)); ::sleep(1); boost::thread myR2(boost::ref(r2)); ::sleep(1); boost::thread myW1(boost::ref(w)); ::sleep(1); boost::thread myR3(boost::ref(r3)); ::sleep(1); boost::thread myR4(boost::ref(r4));
myW1.join(); myR1.join(); myR2.join(); myR3.join(); myR4.join(); }
There is a typo in the reader body it should be "reader running", anyway the problem is the same, readers in wait for a writer are scheduled before the writer then a waste. Regards Gaetano Mendola
Zitat von Gaetano Mendola <mendola@gmail.com>:
Hi all, I'm in need to have a reader/writer mutex with no starvation (I'd say a fair mutex), before to make a my own implementation I have checked the boost one to see if it makes starvation or not, and I'm a bit puzzled about the behave:
I'm experiencing this:
reader 1 start ... writer 1 running ... reader 2 start ... writer 2 running ... writer 1 start << blocked reader 3 start << blocked reader 4 start << blocked
until now it seems that reader 3 and reader 4 are waiting because there is a writer waiting and then the writer will run before reader 3 and 4, unfortunately this is not the case, the execution continues like this:
reader 1 ends reader 2 ends ... writer 3 running ... ... writer 4 running ... reader 3 ends reader 4 ends ... writer 1 running ... writer 1 ends
isn't that a waste? Why make reader 3 and 4 waiting and then make those running before the writer? The code to reproduce that is at the end.
I don't think Boost.Thread specifies this behaviour, so it is probably platform-dependent. I'm guessing readers 3 and 4 have to wait because the writer thread requested an exclusive lock (and otherwise the writer thread would be starved), but once all locks have been released it is a decision of the OS scheduler which thread is then woken up first and can acquire a lock - one of the reader threads in this case apparently.
On 08/10/2010 04:28 PM, Stefan Strasser wrote:
isn't that a waste? Why make reader 3 and 4 waiting and then make those running before the writer? The code to reproduce that is at the end.
I don't think Boost.Thread specifies this behaviour, so it is probably platform-dependent. I'm guessing readers 3 and 4 have to wait because the writer thread requested an exclusive lock (and otherwise the writer thread would be starved), but once all locks have been released it is a decision of the OS scheduler which thread is then woken up first and can acquire a lock - one of the reader threads in this case apparently.
Right, if you want an "order preserving shared mutex", you have to write it yourself.
On 08/10/2010 05:05 PM, Roland Bock wrote:
On 08/10/2010 04:28 PM, Stefan Strasser wrote:
isn't that a waste? Why make reader 3 and 4 waiting and then make those running before the writer? The code to reproduce that is at the end.
I don't think Boost.Thread specifies this behaviour, so it is probably platform-dependent. I'm guessing readers 3 and 4 have to wait because the writer thread requested an exclusive lock (and otherwise the writer thread would be starved), but once all locks have been released it is a decision of the OS scheduler which thread is then woken up first and can acquire a lock - one of the reader threads in this case apparently.
Right, if you want an "order preserving shared mutex", you have to write it yourself.
That was clear to me, still I think, I don't know who fault is, having a reader waiting and then being scheduled is a waste :D I guess I'll write one my self. Regards Gaetano Mendola
Zitat von Gaetano Mendola <mendola@gmail.com>:
On 08/10/2010 05:05 PM, Roland Bock wrote:
On 08/10/2010 04:28 PM, Stefan Strasser wrote:
isn't that a waste? Why make reader 3 and 4 waiting and then make those running before the writer? The code to reproduce that is at the end.
I don't think Boost.Thread specifies this behaviour, so it is probably platform-dependent. I'm guessing readers 3 and 4 have to wait because the writer thread requested an exclusive lock (and otherwise the writer thread would be starved), but once all locks have been released it is a decision of the OS scheduler which thread is then woken up first and can acquire a lock - one of the reader threads in this case apparently.
Right, if you want an "order preserving shared mutex", you have to write it yourself.
That was clear to me, still I think, I don't know who fault is, having a reader waiting and then being scheduled is a waste :D
I guess I'll write one my self.
don't you need OS support for this kind of scheduling? I guess you can write a mutex in userspace that only "preserves order", but as long as you still want threads to be scheduled based on workload/time slices Í think you need an OS scheduler supporting shared mutexes to improve this situation.
On Tue, Aug 10, 2010 at 6:03 PM, Stefan Strasser <strasser@uni-bremen.de>wrote:
[...]
That was clear to me, still I think, I don't know who fault is, having a
reader waiting and then being scheduled is a waste :D
I guess I'll write one my self.
don't you need OS support for this kind of scheduling? I guess you can write a mutex in userspace that only "preserves order", but as long as you still want threads to be scheduled based on workload/time slices Í think you need an OS scheduler supporting shared mutexes to improve this situation.
Actually, I think you don't need OS scheduler support. Rethinking of that idiom might help. Imagine, you have tasks to be executed by a thread pool. What you get from the thread pool are the futures to the task execution. If so you only need to write a scheduler how the tasks are re-arranged in the thread-pool-queue after being enqued. It might become more difficult or even impossible to do some kind of pre-emption, e.g. what should happen if some task (with 'lower prio' or 'higher id') was enqued in the wrong order and started the execution. Now the task which should execute before was enqued. What do you do? Preempt? It might be impossible to preempt the lower-prio task. The only possibility I can imagine is to introduce explicit check points in the task itself and pause the execution when signalled and let the higher prio task run. Even if it is possible, the low prio task must free shared resources, like mutex-es, since otherwise there might happen a priority inversion or even deadlock. In you special case you can do smth' like: Introduce 2 priority queues: Q1 for the reading tasks Q2 for the writing tasks Using reader-writer-lock, you are able to execute as many reader as there are thread in the pool or only one writer. Now the logic is: A: if Q2 is empty execute all reading tasks that are possible from Q1 B: if Q2 is !empty compare heads of Q1 and Q2. If Q1 has reader with lesser id execute all reading tasks that possible, otherwise execute a single writing task and goto point A. This is simplified logic, since you have to ensure that no readers else are running, if you are going to execute a wirter and that no reads are scheduled if writer is pending. That's it. Regards, Ovanes
participants (2)
-
Gaetano Mendola -
Ovanes Markarian -
Roland Bock -
Stefan Strasser