[boost] Re: no semaphores in boost::thread
Jon Biggar wrote: [...] There is actually one case that needs a semaphore that has no reasonable alternative in pthreads. The only pthread synchronization operation that is asynch-reentrant safe (i.e. can be called from a signal handler) is signaling a pthread semaphore. There's no such thing as a pthread semaphore. In a *threaded* POSIX program you can use sigwait() and/or SIGEV_THREAD delivery. It would be nice if there was some abstraction available in boost threads that used this mechanism internally to get the needed behavior, but encapsulated to hide the error-proneness of a raw semaphore. Well, http://www.mail-archive.com/[EMAIL PROTECTED]/msg07519.html regards, alexander. -- http://www.ibm.com/servers/eserver/linux/fun ___ Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
[boost] Re: no semaphores in boost::thread
Beman Dawes wrote: I've expanded the FAQ entry to read: Why has class semaphore disappeared? Semaphore was removed as too error prone. The same effect can be achieved with greater safety by the combination of a mutex and a condition variable. Dijkstra (the semaphore's inventor), Hoare, and Brinch Hansen all depreciated semaphores and advocated more structured alternatives. [Andrews-83] summarizes typical errors as omitting a P or a V, or accidentally coding a P on one semaphore and a V on on another, forgetting to include all references to shared objects in critical sections, and confusion caused by using the same primitive for both condition synchronization and mutual exclusion. The [Andrews-83] reference is to Gregory R. Andrews, Fred B. Schneider, Concepts and Notations for Concurrent Programming, ACM Computing Surveys, Vol. 15, No. 1, March, 1983. http://www.acm.org/pubs/citations/journals/surveys/1983-15-1/p3-andrews/ I'v been using semaphores for years and can't think of what should be wrong with it. That's what most programmers said about goto when Dijkstra's Go To Statement Considered Harmful was published. If you go back and read his letter (http://www.acm.org/classics/oct95/), you could substitute semaphore for go to statement in the key sentence: The go to statement as it stands is just too primitive; it is too much an invitation to make a mess of one's program. Goto's work (or worked; how long since you've seen one in a program?) Semaphores work. But we are better off without both of them. There is actually one case that needs a semaphore that has no reasonable alternative in pthreads. The only pthread synchronization operation that is asynch-reentrant safe (i.e. can be called from a signal handler) is signaling a pthread semaphore. It would be nice if there was some abstraction available in boost threads that used this mechanism internally to get the needed behavior, but encapsulated to hide the error-proneness of a raw semaphore. -- Jon Biggar Floorboard Software [EMAIL PROTECTED] [EMAIL PROTECTED] ___ Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
[boost] Re: no semaphores in boost::thread
Victor A. Wagner, Jr. wrote: well, unless (likely given this biz) the words have changed meaning again, naked semaphore was described by Dijkstra way back when (1964??) http://www.cs.utexas.edu/users/EWD/index01xx.html But just a few years later (in 1971) Sir Tony Hoare (ironically, his current homepage is @ http://www.research.microsoft.com/~thoare) wrote the following in the ACKNOWLEDGMENTS section of his paper named TOWARDS A THEORY OF PARALLEL PROGRAMMING: ... It will be obvious to all how much this paper owes to the thought and writings of Professor E. W. Dijkstra, to whom I owe the concept of the critical region, and the semaphore, the deadly embracy and ... Less obvious but equally invaluable has been his constant encouragement in the search for a concept to 'replace' the semaphore ... ^^^ [...] btw, note that IF my definition is correct, then at a minimum a mutex must do more work than a semaphore (since it must establish ownership of the mutex). That's needed for recursive or error-check mutexes and things like priority inheritance protocol to fight the problem of unbounded priority inversion in the realtime appls. It isn't needed for the normal mutexes with or without priority protection protocol. regards, alexander. ___ Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: [boost] Re: no semaphores in boost::thread
William E. Kempf wrote: I haven't seen your code to say for sure, but from the limited description I believe there's a very high probability that this is the case. Hm... I'm ready to accept the argument that having two separate synchronization primitives to do logically one task can be error-prone in non-trivial schemes. However, from what I understand, Stefan uses his semas in roughly this way: // get single element from queue 1a. semaphore_acquire 2a. mutex_lock 3a. get_elem_from_queue (some equivalent of front+pop_front) 4a. mutex_unlock // put single element into queue 1b. mutex_lock 2b. put_elem_to_queue (some equivalent of push_back) 3b. mutex_unlock 4b. semaphore_release I understand that there is a period of time when the program is running (and therefore is subject to preemption) between 1a and 2a, and that similar period of time happens between 3b and 4b. But I do not see the problem -- in typical usage these two pseudocode sequences are *the only* places in the application where the queue is accessed. That means that the only effect of race condition (resulting from preemption between 1a and 2a or between 3b and 4b) is that at some times the queue will actually have more elements than the sema's counter value. It is *not* a danger in the sense that there is no possibility to pop from the empty queue (once you get green light in 1a, you are sure that 3a will succeed, you just do not care how many elements there are, there is at least one for sure). I think that the argument about race conditions is valid when there are other places in code where the queue is accessed in some way and I understand that two separate synchronization objects make it more probable to write flawed code. However, in this simple example, either: - the race condition does not matter, or - I miss something obvious On the other hand (and being frank, it has to be stated loudly), the above pseudocode does not show that semas should be preferred over condvars... I write it for the sake of argument and better understanding of the rationale. -- Maciej Sobczak http://www.maciejsobczak.com/ Distributed programming lib for C, C++, Python Tcl: http://www.maciejsobczak.com/prog/yami/ ___ Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: [boost] Re: no semaphores in boost::thread
well, unless (likely given this biz) the words have changed meaning again, naked semaphore was described by Dijkstra way back when (1964??) a mutex was a variant of a semaphore which restricted signalling (V()) to the task/process/thread/whatever that had successfully waited (P()) on it. often a mutex would allow the _same_ task/process/thread... to wait (P()) multiple times on the same mutex withOUT deadlock, but would have to signal (V()) the correct number of times before the mutex would be released. Now if the definitions have changed, I apologize for the mis-understanding. If you have some OTHER definition that discriminates between semaphore and mutex, I'd be happy to hear it. If not, why do we have two words for the same thing? btw, note that IF my definition is correct, then at a minimum a mutex must do more work than a semaphore (since it must establish ownership of the mutex). At Thursday 2003-06-05 09:48, you wrote: Victor A. Wagner, Jr. wrote: I'm baffled that they want to penalize (time and space) those for whom a naked semaphore works. Show me please an example illustrating naked semaphore in work. It's blatantly clear to anyone who's had to write a mutex that it's additional code on TOP of a semaphore. Optimization strategies aside for a moment (they are different for mutexes and semaphores) a binary semaphore can be used as normal POSIX mutex. ftp://gatekeeper.research.compaq.com/pub/DEC/SRC/research-reports/SRC-020.pdf Mutexes and semaphores A mutex is represented by a pair (Lock-bit, Queue). The Lock-bit is 1 if a thread is in a critical section protected by the mutex, and is 0 otherwise. In terms of the formal specification, the Lock-bit is 0 iff the mutex is NIL. The Queue contains the threads that are blocked in Acquire (awaiting its WHEN condition). The user code for Acquire and Release is designed for fast execution of a LOCK clause when there is no contention for its mutex. In this case an Acquire-Release pair executes a total of 5 instructions, taking 10 microseconds on a MicroVAX II. This code is compiled entirely in-line. Acquire consists of two sequential actions: test-and-set the Lock-bit (implemented atomically in the hardware); call a Nub subroutine if the bit was already set. The user code for Release is two sequential actions: clear the Lock-bit; call a Nub subroutine if the Queue is not empty. The Nub subroutine for Acquire (after acquiring the spin-lock) first adds the calling thread to the Queue. Then it tests the Lock-bit again. If it is still 1, this thread is de-scheduled and the general scheduling algorithm is invoked to determine what to do with this processor. On the other hand, if the Lock-bit is now 0, the thread is removed from the Queue, the spin-lock is released, and the entire Acquire operation (beginning at the test-and-set) is retried. The Nub subroutine for Release (after acquiring the spin-lock) checks to see if there are any threads in the Queue. If there are, it takes one, adds it to the ready pool, and invokes the general scheduling algorithm, which will assign the thread to a suitable processor if one is available. The implementation of semaphores is the same as mutexes: P is the same as Acquire and V is the same as Release. regards, alexander. ___ Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost Victor A. Wagner Jr. http://rudbek.com The five most dangerous words in the English language: There oughta be a law ___ Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: [boost] Re: no semaphores in boost::thread
Hi, Alexander Terekhov wrote: Show me some code. I mean something that shows why do you need counting semas. This wording is too strong. Going this way, we can *always* say that feature X is not deadly needed and can be replaced by two or more (probably lower-level) features Y. We could write assembly as well. The problem with semas is that many textbooks use them as a mean to describe some ideas. A lot of algorithms are explained in terms of semas and mutexes, and not in terms of mutexes and condvars. One could argue that every algorithm can be transformed to use only mutexes and condvars, but imposing this additional (and *this* is error-prone for sure) redesign work on programmers wanting to just get things done is *not* in the mission statement of any high level library and Boost in particular. The mission is to provide the programmers with the tools they want and IMHO semas fall into this category. If we rewrite all textbooks (starting with all those where 'Dijkstra' or 'Agrawal' appear), then maybe in the next century I will answer your question: I don't see any. If the library has no semas, then programmers will for sure roll their own, most likely flawed, implementations. It is much better to do it for them, as a joined effort of those who know how to do it well. (No, brain-dead pulsing events are not really needed. ;) ) -- Maciej Sobczak http://www.maciejsobczak.com/ Distributed programming lib for C, C++, Python Tcl: http://www.maciejsobczak.com/prog/yami/ ___ Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
[boost] Re: no semaphores in boost::thread
Stefan Seefeld wrote: Alexander Terekhov wrote: Show me some code. I mean something that shows why do you need counting semas. I'm using a bounded task queue (with the producer/consumer pattern), where the queue is implemented with std::queue, a mutex, and two semaphores. One semaphore counts the available tasks, the other the available slots for new tasks (as I said, the queue is bounded). I see that you're also not fond of following the links. Okay. copypaste This is far from elegant, because the queue data structure already knows the number of messages either implicitly or with an extra counter of its own. Usually, what is most relevant is whether or not the queue is empty. So the semaphore is coding redundant information. Note that at times, this information will be out of sync. For example, say you have this sequence of actions: lock(); append(item); unlock(); signal(semaphore); In between the append and signal operation, the queue has N+1 items, but the semaphore's value is out of date at N. A semaphore has an internal lock which protects incremnts and decrements of its internal counter. There is no way to extend that lock to cover additional data such as a queue. With a mutex and condition variable, the entire queue can be treated as a semaphore based on its *own* state! So really, the samephore provides only a kludgy solution to synchronization problems that are based on simple counting. /copypaste regards, alexander. -- http://google.com/groups?threadm=c29b5e33.0202011147.98b216e%40posting.google.com ___ Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
[boost] Re: no semaphores in boost::thread
Maciej Sobczak wrote: Hi, Alexander Terekhov wrote: Show me some code. I mean something that shows why do you need counting semas. This wording is too strong. Going this way, we can *always* say that feature X is not deadly needed and can be replaced by two or more (probably lower-level) features Y. We could write assembly as well. But C/C++ is nothing but modern assembly (more or less portable one). The problem with semas is that many textbooks use them as a mean to describe some ideas. Yeah. Well, I've got a suggestion for all semaphore lovers here. There's a GNU textbook dedicated to semas... how about starting an open source *boost* project to extend it with solutions based on mutexes and condition variables? You'll not only learn how to use condvars (and, believe me, you'll realize rather quickly that monitors based on MESA/POSIX condvars are much, much better than anything you could do with semas), but you'll also do something kinda useful for this little planet. A lot of algorithms are explained in terms of semas and mutexes, and not in terms of mutexes and condvars. http://terekhov.de/downey03semaphores.pdf regards, alexander. ___ Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: [boost] Re: no semaphores in boost::thread
Alexander Terekhov wrote: I see that you're also not fond of following the links. Okay. that's starting to get annoying... I did follow the links, I just don't happen to agree with what was said there. No need to paste it again here. This is far from elegant, because the queue data structure already knows the number of messages either implicitly or with an extra counter of its own. well, I need to know it explicitely when I want to extract the next one, so either the queue caches its length, or I have to count each time. Usually, what is most relevant is whether or not the queue is empty. So the semaphore is coding redundant information. Note that at times, this information will be out of sync. For example, say you have this sequence of actions: lock(); append(item); unlock(); signal(semaphore); In between the append and signal operation, the queue has N+1 items, but the semaphore's value is out of date at N. so what ? the 'real' queue length is kept private and doesn't matter much. It's the signaling of the semaphore that makes the change public. A semaphore has an internal lock which protects incremnts and decrements of its internal counter. There is no way to extend that lock to cover additional data such as a queue. With a mutex and condition variable, the entire queue can be treated as a semaphore based on its *own* state! I never said it can't. Besides, I'd like to argue about your description of the implementation of semaphores. There is no need for a lock around the internal counter, if the semaphore is implemented with atomic counters. Of course, that's true only on platforms that support atomic counters... And then there is the other semaphore I use to count the free slots, which you didn't comment on, probably because it didn't fit into your arguments... This is my last mail in this thread. It's not related to boost any more anyways. We have to agree to disagree. Regards, Stefan ___ Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: [boost] Re: no semaphores in boost::thread
Hi, Alexander Terekhov wrote: and, believe me, you'll realize rather quickly that monitors based on MESA/POSIX condvars are much, much better than anything you could do with semas I understand your point. I have been using Windows API *before* I got a chance to read Programming with POSIX Threads by David R. Butenhof (excellent book, BTW) and maybe my attitude derives from this background. I understand your response to Stefan Seefeld and I see your point that semas do not buy what they should buy and at the same time we have to pay for something that we do not really need. However. Some time ago I wanted to write a *portable* code (Windows included in the list of platforms), with queues between threads and so on. It was easier for me to write my own portable sema (and later use it in the high-level code) than to write portable condvar. Lurking into comp.programming.threads convinces me that it was a good decision, because from what I see there, implementing condvar for Windows is far from being straightforward. I believe that by going the easier way, I won the chance to have fewer bugs. Note that I did not want to depend on any third-party threading library (like Cygwin) at that time. Now, discussing Boost, the situation is different -- when writing *new* code, I would take your arguments into account and probably never missed semas. The problem is that there is existing codebase (also in terms of algorithms, not only as a plain code) depending on semas and this existing stuff cannot be flushed just because it is based on incorrect synchronization primitives. What about providing both (condvars and semas), but with documenting known pros and cons? http://terekhov.de/downey03semaphores.pdf Thanks for the link. -- Maciej Sobczak http://www.maciejsobczak.com/ Distributed programming lib for C, C++, Python Tcl: http://www.maciejsobczak.com/prog/yami/ ___ Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: [boost] Re: no semaphores in boost::thread
Stefan Seefeld said: Alexander Terekhov wrote: This is far from elegant, because the queue data structure already knows the number of messages either implicitly or with an extra counter of its own. well, I need to know it explicitely when I want to extract the next one, so either the queue caches its length, or I have to count each time. Usually, what is most relevant is whether or not the queue is empty. So the semaphore is coding redundant information. Note that at times, this information will be out of sync. For example, say you have this sequence of actions: lock(); append(item); unlock(); signal(semaphore); In between the append and signal operation, the queue has N+1 items, but the semaphore's value is out of date at N. so what ? the 'real' queue length is kept private and doesn't matter much. It's the signaling of the semaphore that makes the change public. This is a race condition. It also occurs when extracting data from the queue. Whether or not the 'real' queue length is private is not relevant, this race condition can lead to improper synchronization, such as trying to to extract data when there's no data left to extract. A semaphore has an internal lock which protects incremnts and decrements of its internal counter. There is no way to extend that lock to cover additional data such as a queue. With a mutex and condition variable, the entire queue can be treated as a semaphore based on its *own* state! I never said it can't. Besides, I'd like to argue about your description of the implementation of semaphores. There is no need for a lock around the internal counter, if the semaphore is implemented with atomic counters. Of course, that's true only on platforms that support atomic counters... That's still a form of a lock. And then there is the other semaphore I use to count the free slots, which you didn't comment on, probably because it didn't fit into your arguments... No, actually, it strengthens the argument, because you now have even more state that needs to be synchronized to ensure against race conditions. This is my last mail in this thread. It's not related to boost any more anyways. We have to agree to disagree. If you want semaphores to be added to Boost.Threads, the arguments are very much on topic here. -- William E. Kempf ___ Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
[boost] Re: no semaphores in boost::thread
Stefan Seefeld wrote: Alexander Terekhov wrote: I see that you're also not fond of following the links. Okay. that's starting to get annoying... Yeah. My wife also says that this is something I do best. ;-) I did follow the links, I just don't happen to agree with what was said there. No need to paste it again here. ... Here's one more (hopefully the last one) link for you. http://google.com/groups?selm=3DF79770.5DA1CD4E%40web.de (Subject: Re: [OT] Request for runnable exe file on producer consumer problem.) Replace .exe with .cpp for the source. regards, alexander. ___ Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: [boost] Re: no semaphores in boost::thread
William E. Kempf wrote:
so what ? the 'real' queue length is kept private and doesn't matter
much. It's the signaling of the semaphore that makes the change public.
This is a race condition. It also occurs when extracting data from the
queue. Whether or not the 'real' queue length is private is not
relevant, this race condition can lead to improper synchronization, such
as trying to to extract data when there's no data left to extract.
Can you elaborate ? I can manipulate the queue as much as I want, the
availability of tasks will be known to consumers only when they are
signaled, not when the queue is non-empty. Where is the race condition ?
(Same argument for the empty slots)
Oh, of course the queue needs a mutex, too (as I said in my original mail),
just to protect the queue's internal structure, so a task extraction
may look like that:
template typename T
T task_queue::consume()
{
my_tasks.wait(); // decrements 'tasks' counter
Prague::GuardMutex guard(my_mutex); // protects queue impl
T t = rep_type::front(); // copies next task (mustn't throw !)
rep_type::pop(); // removes task from queue impl
my_free.post();// announce availability of a free slot
return t; // return t
}
The only tricky thing here is to make sure T's copy constructor doesn't throw.
And then there is the other semaphore I use to count the free slots,
which you didn't comment on, probably because it didn't fit into your
arguments...
No, actually, it strengthens the argument, because you now have even more
state that needs to be synchronized to ensure against race conditions.
I don't understand this. The state in question is the difference between
the capacity of the queue and its current length. The only variable holding
this state is the semaphore ('my_free' in my code snippet). What do I need
to synchronize here ?
Regards,
Stefan
___
Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
[boost] Re: no semaphores in boost::thread
Stefan Seefeld wrote:
[...]
And then there is the other semaphore I use to count the free slots,
which you didn't comment on, probably because it didn't fit into your
arguments...
No, actually, it strengthens the argument, because you now have even more
state that needs to be synchronized to ensure against race conditions.
I don't understand this. The state in question is the difference between
the capacity of the queue and its current length. The only variable holding
this state is the semaphore ('my_free' in my code snippet). What do I need
to synchronize here ?
Hi again, Stefan. ;-)
http://google.com/groups?selm=3C3ACEB1.94085050%40web.de
(Subject: Re: Example C++ pthreads producers consumers project)
regards,
alexander.
--
http://google.com/groups?selm=3EE08DDC.A3A7A32D%40web.de
(Subject: std0X::expected_exceptionT())
___
Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
[boost] Re: no semaphores in boost::thread
Maciej Sobczak wrote: [...] What about providing both (condvars and semas), but with documenting known pros and cons? Personally, I'd have no problems with some *separate* Boost.Semas (for things meant to be done by the current POSIX/IPC semaphores: async- signal-safe unlock operation, memory-isolated synchronization) library with the attached sticker ala Intergalactic Surgeon General's Warning: DON'T USE IT FOR THREADING! (or something like that). Well, that would actually fit rather nicely into The POSIX++ Vision. ;-) regards, alexander. -- http://terekhov.de/your-next-book ___ Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: [boost] Re: no semaphores in boost::thread
Stefan Seefeld said:
William E. Kempf wrote:
so what ? the 'real' queue length is kept private and doesn't matter
much. It's the signaling of the semaphore that makes the change
public.
This is a race condition. It also occurs when extracting data from
the queue. Whether or not the 'real' queue length is private is not
relevant, this race condition can lead to improper synchronization,
such as trying to to extract data when there's no data left to
extract.
Can you elaborate ? I can manipulate the queue as much as I want, the
availability of tasks will be known to consumers only when they are
signaled, not when the queue is non-empty. Where is the race condition ?
(Same argument for the empty slots)
I can't elaborate easily, especially with out reference code.
Oh, of course the queue needs a mutex, too (as I said in my original
mail), just to protect the queue's internal structure, so a task
extraction may look like that:
template typename T
T task_queue::consume()
{
my_tasks.wait(); // decrements 'tasks' counter
Prague::GuardMutex guard(my_mutex); // protects queue impl
T t = rep_type::front(); // copies next task (mustn't
throw !) rep_type::pop(); // removes task from
queue impl my_free.post();// announce
availability of a free slot return t; //
return t
}
The only tricky thing here is to make sure T's copy constructor doesn't
throw.
As soon as synchronization relies on *BOTH* a mutex and a sema/event,
you've got a race condition.
And then there is the other semaphore I use to count the free slots,
which you didn't comment on, probably because it didn't fit into your
arguments...
No, actually, it strengthens the argument, because you now have even
more state that needs to be synchronized to ensure against race
conditions.
I don't understand this. The state in question is the difference between
the capacity of the queue and its current length. The only variable
holding this state is the semaphore ('my_free' in my code snippet). What
do I need to synchronize here ?
The semaphore only represents a logical count... the queue holds the
actual count (even if it's not publicly available). That's why you use a
mutex in your code... to protect the actual shared state. Semas/events
are only useful when the count/flag is the *only* state. Otherwise, you
have more synchronization to do, which can be very tricky to do with out
race conditions.
--
William E. Kempf
___
Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: [boost] Re: no semaphores in boost::thread
William E. Kempf wrote: As soon as synchronization relies on *BOTH* a mutex and a sema/event, you've got a race condition. hmm, I'm not sure I have the same definition for 'race condition' as you have. Of course I could write non-safe code that presents a race condition. Is your point that you want to make it impossible to write non-thread-safe code ? Or are you claiming that the code I have shown contains a race condition (which I still don't see) ? Regards, Stefan ___ Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: [boost] Re: no semaphores in boost::thread
Stefan Seefeld said: William E. Kempf wrote: As soon as synchronization relies on *BOTH* a mutex and a sema/event, you've got a race condition. hmm, I'm not sure I have the same definition for 'race condition' as you have. Of course I could write non-safe code that presents a race condition. Is your point that you want to make it impossible to write non-thread-safe code ? If only that were possible. No, that's not my point. But semas/events are certainly difficult enough to use in all but the simplest cases that they were removed from the library. Or are you claiming that the code I have shown contains a race condition (which I still don't see) ? I haven't seen your code to say for sure, but from the limited description I believe there's a very high probability that this is the case. -- William E. Kempf ___ Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: [boost] Re: no semaphores in boost::thread
I'm baffled that they want to penalize (time and space) those for whom a naked semaphore works. It's blatantly clear to anyone who's had to write a mutex that it's additional code on TOP of a semaphore. we always implemented semaphore first, then added the mutex wrapper for those who needed it. then again, the Ada committee saw fit to standardize on rendezvous which can be implemented trivially w/ 2 semaphores, but not the other way 'round. I've always believed that you made the basics available to others to make their own tools, and convenience wrappers for commonly used things. I've also never actually _seen_ the implementation of a semaphore with a mutex and a condition variable, and don't readily envision it. At Wednesday 2003-06-04 08:00, you wrote: Stefan Seefeld wrote: hi there, I'v been trying to find some info as to why semaphores are considered harmful by the boost::thread authors, without luck. Is there any concise text describing the problem ? Well, http://www.boost.org/libs/thread/doc/faq.html#question10 I'v been using semaphores for years and can't think of what should be wrong with it. http://google.com/groups?threadm=3CEB6073.ACBCFD17%40web.de http://google.com/groups?threadm=c29b5e33.0202011147.98b216e%40posting.google.com regards, alexander. ___ Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost Victor A. Wagner Jr. http://rudbek.com The five most dangerous words in the English language: There oughta be a law ___ Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: [boost] Re: no semaphores in boost::thread
a poor implementation is no reason to ass/u/me that the concept is poor At Wednesday 2003-06-04 12:23, you wrote: Nicolas Fleury wrote: [...] http://google.com/groups?selm=3CED3306.DF6DB829%40web.de (Subject: Re: many semaphores) Would it be possible to post some code that experience has shown to be error-prone using semaphores comparing with conditions/mutexes? Sure... thanks to the Microsoft Corp. http://msdn.microsoft.com/library/default.asp?url=/library/en-us/dndllpro/html/msdn_metrsect.asp Take a look at their brain-damaged metered section semaphore implementation. Note that MS auto-reset event is nothing but a binary sema (well, brain-dead pulsing aside for a moment). regards, alexander. -- http://google.com/groups?selm=c29b5e33.0201240132.3d78369f%40posting.google.com ___ Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost Victor A. Wagner Jr. http://rudbek.com The five most dangerous words in the English language: There oughta be a law ___ Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
[boost] Re: no semaphores in boost::thread
Victor A. Wagner, Jr. wrote: I'm baffled that they want to penalize (time and space) those for whom a naked semaphore works. It's blatantly clear to anyone who's had to write a mutex that it's additional code on TOP of a semaphore. Optimization stratergies aside (they are different for mutexes and semas) a binary semaphore can be used as normal POSIX mutex. ___ Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
[boost] Re: no semaphores in boost::thread
Victor A. Wagner, Jr. wrote: I'm baffled that they want to penalize (time and space) those for whom a naked semaphore works. Show me please an example illustrating naked semaphore in work. It's blatantly clear to anyone who's had to write a mutex that it's additional code on TOP of a semaphore. Optimization strategies aside for a moment (they are different for mutexes and semaphores) a binary semaphore can be used as normal POSIX mutex. ftp://gatekeeper.research.compaq.com/pub/DEC/SRC/research-reports/SRC-020.pdf Mutexes and semaphores A mutex is represented by a pair (Lock-bit, Queue). The Lock-bit is 1 if a thread is in a critical section protected by the mutex, and is 0 otherwise. In terms of the formal specification, the Lock-bit is 0 iff the mutex is NIL. The Queue contains the threads that are blocked in Acquire (awaiting its WHEN condition). The user code for Acquire and Release is designed for fast execution of a LOCK clause when there is no contention for its mutex. In this case an Acquire-Release pair executes a total of 5 instructions, taking 10 microseconds on a MicroVAX II. This code is compiled entirely in-line. Acquire consists of two sequential actions: test-and-set the Lock-bit (implemented atomically in the hardware); call a Nub subroutine if the bit was already set. The user code for Release is two sequential actions: clear the Lock-bit; call a Nub subroutine if the Queue is not empty. The Nub subroutine for Acquire (after acquiring the spin-lock) first adds the calling thread to the Queue. Then it tests the Lock-bit again. If it is still 1, this thread is de-scheduled and the general scheduling algorithm is invoked to determine what to do with this processor. On the other hand, if the Lock-bit is now 0, the thread is removed from the Queue, the spin-lock is released, and the entire Acquire operation (beginning at the test-and-set) is retried. The Nub subroutine for Release (after acquiring the spin-lock) checks to see if there are any threads in the Queue. If there are, it takes one, adds it to the ready pool, and invokes the general scheduling algorithm, which will assign the thread to a suitable processor if one is available. The implementation of semaphores is the same as mutexes: P is the same as Acquire and V is the same as Release. regards, alexander. ___ Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: [boost] Re: no semaphores in boost::thread
Hi, Victor A. Wagner, Jr. wrote: I've also never actually _seen_ the implementation of a semaphore with a mutex and a condition variable, and don't readily envision it. Well... My university background considering synchronization was based on Modula and some abstract course where semas and mutexes were used without assuming that one is better than another. My first real contact with multithreading was on M$ platform. Later, I've found it quite convenient to have both given on the plate in the M$ Windows API. This convenience, mixed with my unbiased theoretical background led me to this: when I started writing threaded programs on Linux, all I missed was a semaphore object, in addition to the mutex. Having mutex and condvar in the pthread library, I've implemented semaphore on top of these two and later used only mutexes and semas in the higher-level code. Am I freak? I will not bet my life that my implementation is correct in all aspects, but the code using it never caused any problems (yes, I know -- that's not a proof). Considering Boost... Having semas in the library would add some convenience for final users. MHO, of course. -- Maciej Sobczak http://www.maciejsobczak.com/ Distributed programming lib for C, C++, Python Tcl: http://www.maciejsobczak.com/prog/yami/ ___ Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: [boost] Re: no semaphores in boost::thread
Alexander Terekhov wrote: Victor A. Wagner, Jr. wrote: I'm baffled that they want to penalize (time and space) those for whom a naked semaphore works. It's blatantly clear to anyone who's had to write a mutex that it's additional code on TOP of a semaphore. Optimization stratergies aside (they are different for mutexes and semas) a binary semaphore can be used as normal POSIX mutex. yes, binary semaphores may be implemented with a mutex (though I think there is a subtle problem as POSIX mutex locks are owned, while semaphores are not). But binary semaphore are only a (small) subclass of semaphores, and I'd use semaphores mostly to represent value *and* lock, where the value's domain is larger than just 1/0. Stefan ___ Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
[boost] Re: no semaphores in boost::thread
Stefan Seefeld wrote: [...] But binary semaphore are only a (small) subclass of semaphores, and I'd use semaphores mostly to represent value *and* lock, where the value's domain is larger than just 1/0. Show me some code. I mean something that shows why do you need counting semas. regards, alexander. ___ Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: [boost] Re: no semaphores in boost::thread
Alexander Terekhov wrote: Show me some code. I mean something that shows why do you need counting semas. I'm using a bounded task queue (with the producer/consumer pattern), where the queue is implemented with std::queue, a mutex, and two semaphores. One semaphore counts the available tasks, the other the available slots for new tasks (as I said, the queue is bounded). Regards, Stefan ___ Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
[boost] Re: no semaphores in boost::thread
Stefan Seefeld wrote: hi there, I'v been trying to find some info as to why semaphores are considered harmful by the boost::thread authors, without luck. Is there any concise text describing the problem ? Well, http://www.boost.org/libs/thread/doc/faq.html#question10 I'v been using semaphores for years and can't think of what should be wrong with it. http://google.com/groups?threadm=3CEB6073.ACBCFD17%40web.de http://google.com/groups?threadm=c29b5e33.0202011147.98b216e%40posting.google.com regards, alexander. ___ Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: [boost] Re: no semaphores in boost::thread
Alexander Terekhov wrote: Stefan Seefeld wrote: hi there, I'v been trying to find some info as to why semaphores are considered harmful by the boost::thread authors, without luck. Is there any concise text describing the problem ? Well, http://www.boost.org/libs/thread/doc/faq.html#question10 well, that doesn't say anything but that it is error-prone. All I'm trying to find out is: why ? I'v been using semaphores for years and can't think of what should be wrong with it. http://google.com/groups?threadm=3CEB6073.ACBCFD17%40web.de http://google.com/groups?threadm=c29b5e33.0202011147.98b216e%40posting.google.com I'm still not convinced. You are comparing semaphores with mutexes, when you should compare semaphores with condition variables. At least when argueing about efficiency. Regards, Stefan ___ Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
[boost] Re: no semaphores in boost::thread
Stefan Seefeld wrote: [...] I'm still not convinced. http://google.com/groups?selm=3CED3306.DF6DB829%40web.de (Subject: Re: many semaphores) regards, alexander. ___ Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
[boost] Re: no semaphores in boost::thread
Alexander Terekhov wrote: Stefan Seefeld wrote: [...] I'm still not convinced. http://google.com/groups?selm=3CED3306.DF6DB829%40web.de (Subject: Re: many semaphores) Would it be possible to post some code that experience has shown to be error-prone using semaphores comparing with conditions/mutexes? Some code illustrating the problem with semaphores would be useful, and could maybe be added to the currently very short justification in Boost.Thread faq. Thx Regards, Nicolas Fleury ___ Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
[boost] Re: no semaphores in boost::thread
Nicolas Fleury wrote: [...] http://google.com/groups?selm=3CED3306.DF6DB829%40web.de (Subject: Re: many semaphores) Would it be possible to post some code that experience has shown to be error-prone using semaphores comparing with conditions/mutexes? Sure... thanks to the Microsoft Corp. http://msdn.microsoft.com/library/default.asp?url=/library/en-us/dndllpro/html/msdn_metrsect.asp Take a look at their brain-damaged metered section semaphore implementation. Note that MS auto-reset event is nothing but a binary sema (well, brain-dead pulsing aside for a moment). regards, alexander. -- http://google.com/groups?selm=c29b5e33.0201240132.3d78369f%40posting.google.com ___ Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
[boost] Re: no semaphores in boost::thread
Alexander Terekhov wrote: Nicolas Fleury wrote: [...] Would it be possible to post some code that experience has shown to be error-prone using semaphores comparing with conditions/mutexes? Sure... thanks to the Microsoft Corp. http://msdn.microsoft.com/library/default.asp?url=/library/en-us/dndllpro/html/msdn_metrsect.asp Take a look at their brain-damaged metered section semaphore implementation. Note that MS auto-reset event is nothing but a binary sema (well, brain-dead pulsing aside for a moment). Thx for the link, but I don't get it. How is Microsoft implementation of semaphore is showing that all implementations of semaphore should be avoided? Using semaphores versus using mutexes/conditions should be illustrable with few lines of code. I just want to understand what some developers think is error-prone about semaphores, whatever the implementation (or with the removed boost implementation). Thx. Regards, Nicolas Fleury ___ Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
[boost] Re: no semaphores in boost::thread
Nicolas Fleury wrote: Alexander Terekhov wrote: Nicolas Fleury wrote: [...] Would it be possible to post some code that experience has shown to be error-prone using semaphores comparing with conditions/mutexes? Sure... thanks to the Microsoft Corp. http://msdn.microsoft.com/library/default.asp?url=/library/en-us/dndllpro/html/msdn_metrsect.asp Take a look at their brain-damaged metered section semaphore implementation. Note that MS auto-reset event is nothing but a binary sema (well, brain-dead pulsing aside for a moment). Thx for the link, but I don't get it. How is Microsoft implementation of semaphore is showing that all implementations of semaphore should be avoided? It is showing that semas (e.g. bin-semas aka auto-reset events) are really error-prone. Their implementation of counting semaphore using a mutex (well, they actually use a totally brain-damaged dying spinlock) plus a binary semaphore is buggy (it contains erroneous synchronization). Now... you might to follow this link: http://google.com/groups?selm=3CE0BCD3.EF695748%40web.de (Subject: Re: The implementation of condition variables in pthreads-win32) regards, alexander. -- Pthreads win32 is just trying to be a general pupose condition variable as defined by the pthreads standard, suitable for any and all threads to go around calling pthread_cond_wait() and pthread_cond_signal() on. As a consequence the implementation contains several mutexes, semaphores etc, and a flow of control that will make your brains dribble out of your ears if you stare at the code too long (I have the stains on my collar to prove it ;-). Such are the joys of implementing condition variables using the Win32 synchronization primitives! -- http://tinyurl.com/b9vw ___ Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: [boost] Re: no semaphores in boost::thread
Alexander Terekhov wrote: It is showing that semas (e.g. bin-semas aka auto-reset events) are really error-prone. you seem to equate microsoft's implementation of semaphores with the concept of semaphores (which is what I'd like to get feedback on). If all that is wrong is that microsoft does a crappy job at implementing them, the response could be to provide a special implementation using mutexes and cv's *for the MS platforms*, and using native implementations when possible. As boost doesn't, there must clearly be other reasons for them not to do that. Regards, Stefan ___ Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: [boost] Re: no semaphores in boost::thread
Stefan Seefeld said: Alexander Terekhov wrote: It is showing that semas (e.g. bin-semas aka auto-reset events) are really error-prone. you seem to equate microsoft's implementation of semaphores with the concept of semaphores (which is what I'd like to get feedback on). No, you miss Alexander's point (which is easy to do, with his communication style... in this case he points you to a good example, but fails to explain why it's a good example). His point is that the MS concept of an auto-reset event is the same thing as a binary semaphore. The MeteredSection concept in this article was implemented using an auto-reset event (bin-semaphore), and on the surface looks like a reasonable implementation. However, if you do a thorough analysis of this implementation you'll find that it's prone to race conditions. Another great example is the attempts to implement a condition variable concept using semaphores, as has been done sooo many times on Windows. Nearly every attempt has been flawed, and the valid solutions are extremely complex. If all that is wrong is that microsoft does a crappy job at implementing them, the response could be to provide a special implementation using mutexes and cv's *for the MS platforms*, and using native implementations when possible. MS's actual semaphore is as valid an implementation as any other (Alexander will claim them to be brain damaged, but that's because of the design, not the implementation). As boost doesn't, there must clearly be other reasons for them not to do that. There is, but the explanations are long and quite complex. That's why the FAQ points you at a seminal paper on the subject, rather than attempting to explain it. Like I've said in numerous arguments about the Event concept, the problem with the concept isn't that it's broken or unusable, only that it's difficult to actually use correctly. Most users think their code is correct, when in fact they have race conditions waiting to bite them. When Mutexes and Condition variables provide everything that Semaphores and Events do, but in a way that's easier to use correctly, the choice to not include Event's or Semaphore's is reasonable. -- William E. Kempf ___ Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
[boost] Re: no semaphores in boost::thread
Nicolas Fleury wrote: [...] It is showing that semas (e.g. bin-semas aka auto-reset events) are really error-prone. Their implementation of counting semaphore How? Review the code. You'll see that it has many problems. One problem is precisely the thing that POSIX rationale is talking about -- the predicate checking -- With stateful primitives, such as binary semaphores, the wakeup in itself typically means that the wait is satisfied. The burden of ensuring correctness for such waits is thus placed on all signalers of the semaphore rather than on an explicitly coded Boolean predicate located at the condition wait. [...] But what's the relation between Microsoft implementation of semaphore, Damn. I should have called it metered section... without any mentioning that it's a counting semaphore. The point is that that code does illustrate the error-proness that POSIX rationale is talking about. pthread win32 implementation of condition http://groups.google.com/groups?selm=3CEA2764.3957A2C8%40web.de and the error-proness of semaphores versus mutexes/conditions in general? In general, you don't need semas for threading and you do need mutexes and condvars. Mutexes and condition variables together constitute an appropriate, sufficient, and complete set of inter- thread synchronization primitives. Is it simply a mather of preference and style, or is there a simple case to show why semaphores are error-prone instead of mutexes/conditions? Again, MS-metered section example IS a simple case to show why semaphores are error-prone instead of mutexes/conditions. regards, alexander. ___ Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
[boost] Re: no semaphores in boost::thread
Nicolas Fleury wrote: [...] What is the paper you have in mind to justify the absence of semaphores? I would like very much to understand and be convinced. It would also be nice if the #10 of the FAQ would point to this paper. It can be found here: http://www.amazon.com/exec/obidos/ASIN/0387954015/104-6312782-0737542 regards, alexander. -- http://groups.google.com/groups?selm=3D58D3BC.6D42748B%40web.de ___ Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
