Talk:Semaphore (programming)
Page contents not supported in other languages.
| This is thetalk page for discussing improvements to theSemaphore (programming) article. This isnot a forum for general discussion of the subject of the article. |
Article policies |
| Find sources: Google (books ·news ·scholar ·free images ·WP refs) ·FENS ·JSTOR ·TWL |
 | This article is ratedStart-class on Wikipedia'scontent assessment scale. It is of interest to the followingWikiProjects: | |||||||||||||||||||||||||||
| ||||||||||||||||||||||||||||
Can anyone pls tell me which assembly language instruction supports construction of semaphores ?- Computer Freak
Yes. Use XCHG in x86, or use SWP in ARM architectures. There are other synchronization instructions at hardware level, each one with slight different designs.— Precedingunsigned comment added by187.95.110.228 (talk)23:45, 10 June 2014 (UTC)[reply]
--Coyote25 (talk)19:35, 11 February 2008 (UTC)[reply]
You don't need to disable/enable interrupts if your ISA supports memory-interlocked atomic operations. On x86/x64, look into the LOCK prefix.Jeh (talk)10:59, 3 March 2016 (UTC)[reply]
Could anyone provide supporting information for the statements in the "semaphores today" section?
I fail to understand why semaphores should be considered as bad as goto.
The only info I was able to google did not clarify it (such as: preferring the synchronize keyword for the Java language, the difficulty of the use of semaphore).
Thanks!
--Fr3d3r1c 17:50, 27 Feb 2005 (UTC)
Actually the text does not say semaphores are as bad as GOTO. The comparison between semaphores and GOTO is that both seemed to be good ideas in the beginning. A personal view is that a semaphore is just the simplest implementation which does the job and employs 'atomic' or 'atomicised' instructions. More modern alternatives will do the same job by the same underlying means, but will wrap them up differently for easier application to a programming problem. Much like a roller makes it possible to move heavy loads without sliding friction and a wheel is a better implementation of the same idea, because you don't need to keep moving rollers from behind to the front.
VLwhat is top down,structure,modular and object oriented progamming—Precedingunsigned comment added by117.242.156.26 (talk)05:04, 25 March 2010 (UTC)[reply]
I'm sorry to ask stupid questions, but I don't fully understand the example:
...It (thread A) then posts a DBDataRequest to both the threads(B,C) and adds a reference to the semaphore as well in the request it posted. After this it immediately does P(S) and blocks. The other two threads meanwhile take their own time to obtain the information and post the responses back and also do a V(S) on the passed semaphore. Only after both threads have done their part of V(S) will the first thread be able to continue. This is exactly what we wanted as well. A semaphore used in this way is called a "counting semaphore".
If the pseudocode in thread A is something like
read data from Bread data from CP(S)
then won't it proceed as soon as either B or C has done V(S)? Should there be two calls to P(S)? I'm reading the example text like there is only one call to P(S)... ~Samuli
I would like to get rid of the C# example. My feeling is that it is way too long for an illustrative source snippet and makes the article unreadable. Any comments?Abelsson10:14, 23 January 2006 (UTC)[reply]
Shouldnt the above article be excluded as it is not freely availble?
Yes, Dijkstra really wrote "try-and-decrease," not "try-to-decrease." That's an idiomatic English expression; for example, "I'm going to try and improve this article a bit." However, "try-to-decrease" is a much less ambiguous phrase. (A non-native English speaker, or even a paranoid native speaker, might sensibly ask, "Trywhat, and (then) decrease?") So I've made the change in the article. I don't think it's appropriate to keeponly the "try-to-decrease" translation, since that's not what Dijkstra actually wrote. --Quuxplusone07:18, 3 March 2006 (UTC)[reply]
@Quuxplusone:
Where did Dijkstra write "try-and-decrease"? He wrote all his papers in Dutch. If you got it fromhttp://www.cs.utexas.edu/users/EWD/transcriptions/EWD00xx/EWD51.html, I think the translations were added by the transcriber, they do not appear in the original document:http://www.cs.utexas.edu/users/EWD/ewd00xx/EWD51.PDF
Someone should mention why semaphores can't handle deadlocks: because a random thread gets unblocked when V is called (so the threads don't wake up in FIFO order; it is theoretically possible that a thread never wakes up if other threads call P all the time and get woken up first). --Bernard François17:39, 4 January 2007 (UTC)[reply]
No, I don't believe that is why. That would actually have to do with processor scheduling and is called starvation, not deadlock. Deadlock is basically when processes are waiting on each other. Like below:
Process A Process B--------- -----------wait(a); wait(b);wait(b);//critcal//codesignal(b);signal(a);
—Precedingunsigned comment added by24.111.186.45 (talk)02:07, 21 February 2008 (UTC)[reply]
21-Oct-2007: The article had been tagged here as "too technical" with template {{technical}}, so I have simplified as follows:
Those changes are mainly intended to add more general-reader phrases as clarification of descriptions, and remove excessive terms (such as the hatnote's "mutual exclusion") which could further confuse general readers. I have removed tag "{{technical}}" and suggested detailing any other confusing issues here. -Wikid7706:14, 21 October 2007 (UTC)[reply]
What's is up with the dutch example? I understand this might refer to the original article introducing these semaphores, but these names are not used anywhere anymore that I know of. I have been an a teacher for 5 years in multiprogramming, and we have used 3 different books. All the books use signal() and wait() instead of P and V. Could we please update it to reflect modern and more self-documenting code?Carewolf (talk)12:26, 11 December 2007 (UTC)[reply]
As written, the counting semaphore admits deadlocks if three separate threads each attempt to acquire then release N permits and the semaphore has less than 2N available. A problematic sequence of operations is:
Semaphore SInit(S, 3) // s == 3Thread 1 calls P(S, 2)Thread 1 passes the first waitThread 1 decrements S by 2 (S == 1)Thread 1 passes the second waitThread 2 calls P(S, 2)Thread 3 calls P(S, 2)Thread 2 passes the first waitThread 3 passes the first waitThread 2 decrements S by 2 (S == -1)Thread 3 decrements S by 2 (S == -3)Thread 1 calls V(S, 2)Thread 1 increments S by 2 (S == -1)Thread 2 blocks at the second waitThread 3 blocks at the second wait
After this sequence of operations, the semaphore is permamently blocked, and threads 2 and 3 will never continue. The paragraph describing the counting semaphore seems to assume that there is some implicit synchronization happening similar to java's synchronized methods.
I propose that the example be rewritten with a condition variable to explicitly provide synchronization, or something similar. If nobody objects, I may do it myself.Hurkyl (talk)09:22, 1 January 2008 (UTC)[reply]
P (Semaphore s, unsigned int n){ if (s->count >= n) s->count -= n; else { if (s->first == false) wait_on (s->q0); s->first = true; s->needed = n; wait_on (s->q1); s->count -= n; s->first = false wakeup (s->q0); }}V (Semaphore s, unsigned int n){ s->count += n; if (s->first == true) { if (s->count >= s->needed) wakeup (s->q1); }}Velco (talk)22:27, 13 November 2008 (UTC)[reply]
In the following code snippet:
P(Semaphore s) // Acquire Resource { wait until s > 0, then s := s-1; /* must be atomic because of race conditions */ }Is it the entire function that is atomic or just the statements := s-1?
--AlanH (talk)23:56, 2 May 2009 (UTC)[reply]
I think the examples do a pretty good job of explaining the use of Semaphores, but the use of the operator (colon, equals) := seems to be confusing to me. After digging a little bit online I've found that the := operator is used in Delphi. Perhaps I'm missing something? If this is the case, perhaps it should be explicitly stated that this is in fact an example written in Delphi.—Precedingunsigned comment added by216.254.69.105 (talk)19:06, 11 June 2009 (UTC)[reply]
The code snippets for P and V are inaccurate and imply busy waiting while in fact, semaphores do not busy wait. Nor is the order of events entirely accurate. No mention is wait of queuing waiting threads. Formal definition of P and V is as follows. They are assumed to be atomic.
void P(Semaphore s) { s.count--; if (s.count < 0) { <place process in s.queue> <block this process> } } void V(Semaphore s) { s.count++; if (s.count <= 0) { <remove a process P from s.queue> <place process P on ready list> } }Actually making these atomic requires hardware support, such as the testset instruction. An example implementation would be
void P(Semaphore s) { while (!testset(s.flag)) <do nothing>; s.count--; if (s.count < 0) { <place process in s.queue> <block this process and set flag to 0> } else { s.flag = 0; } } void V(Semaphore s) { while (!testset(s.flag)) <do nothing>; s.count++; if (s.count <= 0) { <remove a process P from s.queue> <place process P on ready list> } s.flag = 0; }s.flag is used to ensure mutual exclusion. testset(x) is atomic and returns true if the x could be set (if x was 0), otherwise it returns false. This does use busy waiting, but since both P and V take very little time that does not pose a real problem.
Source: Operating Systems, by William Stallings—Precedingunsigned comment added by193.190.253.160 (talk)01:02, 18 June 2009 (UTC)[reply]
I didn't understand this part:
"It should be noted that the semaphore count is not necessarily equal to the buffers available in the pool. The checking and waiting twice for the s >= 0 condition in P is needed to guarantee that as multiple processes are added to the semaphore's waiting list they do not disturb each other's request: a process does not change the semaphore's count until it is next in the queue. In real implementations it is done without actually activating up the waiting process for the intermediate step."
where were we "checking and waiting twice for the s >= 0 condition in P"? thanksBayle Shanks (talk)23:47, 18 November 2009 (UTC)[reply]
with Public parking lot (cars waiting in queue for free resource) or Restaurant (people waiting for tables)
Thanks, Zvika13:50, 13 January 2010 (UTC)—Precedingunsigned comment added by212.25.124.163 (talk)
The public toilet analogy is much better than the library analogy in the article at present. Imagine a public toilet with a counter outside showing the number of free cubicles. Someone arriving at the toilets invokes Wait(), that is checks the counter. If the counter is > 0, the person continues to a free cubicle and the act of locking the door decrements the counter. If the counter is 0, the person waits (process/thread joins a sleep queue). Someone leaving unlocks the door (incrementing the counter) and signals to someone waiting to look to find a free cubicle (the process/threas signals to a process/thread in the sleep queue to wake - might be a FIFO queue). Simple and vivid.Burraron (talk)11:01, 8 November 2022 (UTC)[reply]
This is not an especially important problem, as everyone will understand the meaning, but I think we should consider rewriting the phrase
If several diners simultaneously arrive, the maître d will seat them in the order of arrival
I understand that the diners would not literally arrive simultaneously, but it still sounds a bit strange, worded as above.
-
94.192.173.115 (talk)15:54, 4 March 2010 (UTC)[reply]
I flagged the following statements as contradictory:
"(A mutex is really a semaphore with two values.)""Mutexes are usually more efficient than binary semaphores."
More information needs to be presented, otherwise these statements are confusing. If a mutex is a semaphore with 2 values (a binary semaphore) then it cannot be more or less efficient than the same. If interpreting the meaning of "a semaphore with 2 values" as a binary semaphore is incorrect, then that only further supports the need for elaboration.
Tseiff (talk)18:22, 28 October 2010 (UTC)[reply]
Actually, the concept of a Mutex should be clarified. It prevents race conditions on the *same* process. [[[User:Desavera|Desavera]] (talk)19:40, 1 February 2011 (UTC)][reply]
I find it extremely difficult to believe that Dijkstra could be the inventor of this concept, since it would have been an essential part of any complex operating system well prior to 1965, especially in multiprocessing environments. What proof is there that nobody else had ever thought of it previously? Information technology is a domain in which the wheel is regularly and routinely reinvented.Agateller (talk)20:14, 10 January 2011 (UTC)[reply]
I do not think there were multiprocessing environs at that time at all;multi-programming, yes. The proof is publications. Dijkstra published before someone else did. I maybe wrong though. -Sri— Precedingunsigned comment added by71.70.253.160 (talk)08:50, 13 December 2013 (UTC)[reply]
I have been reading Tanenbaum's "Modern Operating Systems" lately and saw that his solution to this problem uses one more semaphore, as follows:
produce: P(emptyCount) P(useQueue) putItemIntoQueue(item) V(useQueue) V(fullCount)
The consumer does the following repeatedly:-
consume: P(fullCount) P(useQueue) item ← getItemFromQueue() V(useQueue) V(emptyCount)
The idea is that we need a third semaphore to handle mutual exclusion to the queue, whereas emptyCount and fullCount manage synchronisation issues having to do with the limits of using the queue (not using it when it is full or empty, respectively). I think that this is indeed needed, but wanted to raise the point before making the addition.—Precedingunsigned comment added by188.4.182.33 (talk)21:48, 20 March 2011 (UTC)[reply]
The description for a semaphore is inaccurate and confused with the "mutex" concept. In analogy withFlag Semaphore a Semaphore in programming is a simple mechanism for inter process communication, or signalling. It is not inherently an access control mechanism, although it can be used to implement some access control mechanisms.
In the citedpaper byEdsger Dijkstra the concept is introduced in section 3.2 under the heading "The Synchronizing Primitives" and is described as
a) among the common variables special purpose integers, which we shall call "semaphores".
b) among the repertoire of actions, from which the individual processes have to be constructed, two new primitives, which we call the "P-operation" and the "V-operation" respectively. The latter operations always operate upon a semaphore and represent the only way in which the concurrent processes may access the semaphores.
In addition the primitives are described as "indivisible" or atomic.
The concept was developed byEdsger Dijkstra to address a particular type of synchronisation problem. Namely the "Producer - Consumer" problem. Semaphores can be used to implement Mutual Exclusion.
--Dopey68 (talk)06:31, 25 November 2011 (UTC)[reply]
The description of signal is incorrect:
signal(): It increments the value of semaphore variable by 1. After the increment if the value is negative, it transfers a blocked process from the semaphore's queue to the ready queue.
The blocked process from the queue would be awoken when the counter goes positive.
65.113.40.1 (talk)00:56, 8 December 2011 (UTC)[reply]
Most coding examples I have run across use the value of 0, not -1, as the value that means the semaphore is out of permits, i.e. resources. Thus, the statements:
Should be amended to
— Preceding comment added byYonemo (talk) 21:02, 27 June 2012 (UTC)Yonemo (talk •contribs)20:54, 27 June 2012 (UTC)[reply]
To me, this is confusing: A semaphore should never have a negative value. It is only decreased by I if S >= I.
Thus, the text reading
should be
But is this additional explanation really needed in this context? The "library example" explains it more clearly, imho. I suggest deleting the paragraph "A simple way to understand ... to the ready queue." from the section "Semantics and implementation".
Stencil19 (talk)12:03, 7 September 2015 (UTC)[reply]
Totorigolo (talk)10:56, 15 October 2018 (UTC)[reply]
I agree that the current description of wait and signal doesn't seem to be correct. Take this simple example with 2 threads A and B, using the current description (as of 9:46, 15 October 2018 (UTC)):
IMO a correct version would be (this is a simplified version of theFrench article's description):
Also, it should be mentioned that these two operations are atomic.
I find the intro's claim that semaphores are used in parallel processing to seem to (by omission) not include the computers which have a single-threaded CPU and yet allow multi-user processing. Users may hold a resource for an extended period of time and semaphores are used to block subsequent users from accessing the resource, until the first user process is complete. This is not parallel processing, the CPU only works on a single task at a time.Wjhonson (talk)18:16, 6 November 2012 (UTC)[reply]
According to the article, "a semaphore is a variable or abstract data type that provides a simple but useful abstraction for controlling access, by multiple processes, to a common resource". That is not what a semaphore is. That's amutex. Semaphores are used for syncronisation between processes. Semaphores and mutexes may be implemented by the operating system in similar ways (using a counter variable), but they are used in different ways. This article blurs the distinction between them. A major article overhaul is needed. --Frederico1234 (talk)18:23, 2 August 2013 (UTC)[reply]
I revertedthis edit. However I then started looking more closely at the "simple way to understand." I corrected the wait() function, but signal() is still missing something. Since wait() never decrements the counter if it's already negative, the counter will never be less than -1. Suppose there are three waiters; the value will still be -1. So, when signal() is called, it will "increment the value by 1" - now the counter is zero. Since the old value was negative it will release one waiter, but subsequent calls to signal() will not release any.
I know how this works, but I'm not certain of the best way to phrase it in English.Jeh (talk)09:42, 5 March 2015 (UTC)[reply]
I already described my complaints with this material in the edit summary for my revert, so it would actually be up to@Dipankarpal5050: to open the dialog here if s/he wants to. However...
in other words An integer value used for signaling among processes.
This "sentence" has no subject. And it describes an implementation detail that is, at once, too detailed for the lede and not complete enough for the body (not just any "integer value" will do).
Only three operations may be performed on a semaphore, all of which areatomic: initialize, decrement, and increment.
This is also too detailed for the lede, and the first claim is not always true. True, this is the list offundamental operations of a semaphore but others may be implemented.
The decrement operation may result in the blocking of a process, and the increment operation may result in the unblocking of a process.
Nothing requires this particular "polarity". It also invites the question of "may result? When would it, and when would it not?" Too much for the lede.
Also known as acounting semaphore or a general semaphore.
This "sentence" too has no subject. More seriously, the term "counting semaphore" is already mentioned later in the lede. "General semaphore" is not mentioned anywhere else in the article, therefore should not be in the lede.
The grammar issues could be easily fixed, of course, but the factual and organizational problems remain. The lede is sufficient as it was.Jeh (talk)08:54, 3 March 2016 (UTC)[reply]
Prior content in this article duplicated one or more previously published sources. The material was copied from:https://freefundkenotes.files.wordpress.com/2014/02/william-stallings-operating-system.pdf. Copied or closely paraphrased material has been rewritten or removed and must not be restored,unless it is duly released under a compatible license. (For more information, please see"using copyrighted works from others" if you are not the copyright holder of this material, or"donating copyrighted materials" if you are.)
Forlegal reasons, we cannot acceptcopyrighted text or images borrowed from other web sites or published material; such additions will be deleted. Contributors may use copyrighted publications as a source ofinformation, and, if allowed underfair use, may copy sentences and phrases, provided they are included in quotation marks andreferenced properly. The material may also be rewritten, providing it does not infringe on the copyright of the originalorplagiarize from that source. Therefore, such paraphrased portions must provide their source. Please see ourguideline on non-free text for how to properly implement limited quotations of copyrighted text. Wikipedia takes copyright violationsvery seriously, and persistent violatorswill beblocked from editing. While we appreciate contributions, we must require all contributors to understand and comply with these policies. Thank you.Jeh (talk)09:36, 5 March 2016 (UTC)[reply]
In the preamble the following line appears:
"A useful way to think of a semaphore as used in the real-world systems is as a record of how many units of a particular resource are available, coupled with operations to adjust that record safely (i.e. to avoid race conditions) as units are required or become free, and, if necessary, wait until a unit of the resource becomes available."
This line is too long and very unclear. If an expert will reword it to make simpler to understand, perhaps by dividing it into segments, it will be very useful.
Thanks!Wilkn (talk)18:17, 31 October 2017 (UTC)[reply]
Regardless of the various expert debates and refinements still possible, this is a good article in my eyes, good job!Maxorazon (talk)20:36, 4 February 2022 (UTC)[reply]
IBM from OS/360 on, uses WAIT/POST, named after the two macro instructions, and theEvent Control Block to synchronize operations. It is used for I/O and for task synchronization. I am not sure it is exactly the same as described here. If it isn't, then it should have its own article. Otherwise it should be explained here.Gah4 (talk)23:22, 10 July 2023 (UTC)[reply]