Talk:Semaphore (programming)

From Wikipedia, the free encyclopedia

 This article is within the scope of WikiProject Computer science, which aims to create a comprehensive computer science reference for Wikipedia. Visit the project page for more information and to join in on related discussions.
Start rated as start-Class on the assessment scale
High rated as high-importance on the assessment scale

This is the talk page for discussing improvements to the Semaphore (programming) article.
Article policies

Contents

[edit] Assembly language instruction

Can anyone pls tell me which assembly language instruction supports construction of semaphores ? - Computer Freak

@computer freak. There is no assembly instruction. You need an instruction to dis-/enable interrupts. Then you can make 'atomic' pieces of code.
The P is short for 'Prolaag' which means try to decrement. The V is short for Verhoog which means increment. Please check it in the original document: http://www.cs.utexas.edu/users/EWD/ewd00xx/EWD74.PDF
Lex Meuldijk
@Lex. "Prolaag" doesn't mean anything -- it is not a dutch word. It is probably a shorthand for 'proberen te verlagen' which means 'try to decrement'. Which would make sense because the other operation is indeed "verhogen", which means "increment".
Jan David Mol
@computer freak. Of course that you can always make semaphore in other forms, without requiere the dis-/enable interrupts, by using mutexes to do it. And them use other way to do the mutexes.

--Coyote25 (talk) 19:35, 11 February 2008 (UTC)

[edit] Supporting information

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.

VL

[edit] I don't understand the example

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 B
read data from C
P(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

Because there is a problem with the example. The call to "init(S,0)" SHOULD BE "init(S, -1)".
Thread A calls P(S), which will hang, or wait, until the semaphore is > 0. And the semaphore will only be > 0 when there have been at least 2 V(S) calls.
Hope this helps. - Jeremiah

[edit] C# example

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? Abelsson 10:14, 23 January 2006 (UTC)

I agree. -dkeithley
As there were no objections in over a week, I've removed it now. Abelsson 08:49, 1 February 2006 (UTC)

[edit] Article "Design patterns for semaphores" needs ACM membership

Shouldnt the above article be excluded as it is not freely availble?

[edit] Try-and-decrease

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, "Try what, and (then) decrease?") So I've made the change in the article. I don't think it's appropriate to keep only the "try-to-decrease" translation, since that's not what Dijkstra actually wrote. --Quuxplusone 07:18, 3 March 2006 (UTC)

@Quuxplusone:

Where did Dijkstra write "try-and-decrease"? He wrote all his papers in Dutch. If you got it from http://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

[edit] deadlocks

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çois 17:39, 4 January 2007 (UTC)


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 //code

signal(b); signal(a); —Preceding unsigned comment added by 24.111.186.45 (talk) 02:07, 21 February 2008 (UTC)

[edit] Simplifying techno style

21-Oct-2007: The article had been tagged here as "too technical" with template {{technical}}, so I have simplified as follows:

  • reduced top yada-yada-hatnote to "For other uses, see: Semaphore" (Long hatnotes invite tweaking with more techno words, via creeping featurism, so keep them short); the hatnote had creeped into further confusing general readers as:
This article is about the computer science application of mutual exclusion which comes up before the original, i.e., for other uses, see Semaphore.
  • expanded intro, noting "in computer science" plus simple wording "used by multiple programs to control shared resources, such as shared memory, files or devices" dropping word "storage" which means "U-store-it bins" for general readers;
  • added alternate Dutch-to-English translation "probe-to-lessen" to not force readers with a single translation;
  • clarified other phrases, such as "multi-resource deadlock" to emphasize problem of deadlocks;
  • per WP:GUIDE, put simple sections "Notes" and "References" as used in many other articles;
  • added years "Edsger Dijkstra (1930-2002)" to reduce commercial-ties assumption.

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. -Wikid77 06:14, 21 October 2007 (UTC)

Good work, Wikid77! I did revert these two, though:
  • "Probe-to-lessen" is an interesting translation in that it uses the English cognate "probe" instead of "try", but it doesn't make much sense as a translation. In English, you don't "probe to" do something; you "try to" do it.
  • I don't know what you mean by "commercial-ties assumption". Do you think the reader might assume that "Edsger Dijkstra" is the name of a corporation, like "Merrill Lynch", instead of a person's name? I don't think we need to worry; the reader can click on the link to read more about Dijkstra if he cares to. Dijkstra's birthdate isn't relevant to the study of semaphores. :) --Quuxplusone 08:29, 21 October 2007 (UTC)
I think that instead of making this article less technical, someone should instead make something in Simple English, and link it to the different pages about the topic
Coyote25 (talk) 19:40, 11 February 2008 (UTC)

[edit] P and V ???

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)

I agree that P and V are bad function names. But signal() and wait() are more associated with condition variables, aren't they? (also notify() instead of signal() as a variant) There is also acquire(...) and release(...) (e.g. java.util.concurrent.Semaphore), and probably lots of other names. But this is exposition code, not library code -- we should probably select more verbose, descriptive names, such as WaitForUnits(s, n) and ReturnUnits(s, n). (And maybe include a short list of names for them commonly seen in libraries) Hurkyl (talk) 04:37, 29 December 2007 (UTC)
Ah, I see there is already a short list; I missed it while skimming the page. Maybe it should be made more prominent? Hurkyl (talk) 04:40, 29 December 2007 (UTC)

[edit] Counting semaphore wrong

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 S
Init(S, 3) // s == 3
Thread 1 calls P(S, 2)
Thread 1 passes the first wait
Thread 1 decrements S by 2  (S == 1)
Thread 1 passes the second wait
Thread 2 calls P(S, 2)
Thread 3 calls P(S, 2)
Thread 2 passes the first wait
Thread 3 passes the first wait
Thread 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 wait
Thread 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)