Talk:Semaphore (programming)

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)

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 what is top down,structure,modular and object oriented progamming —Preceding unsigned comment added by 117.242.156.26 (talk) 05:04, 25 March 2010 (UTC)

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

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)

Article "Design patterns for semaphores" needs ACM membership

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

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

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)

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)

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)

I suggest making acquire and release the 'official' verbs on this page (to be used in examples etc.), since they are probably the most descriptive and widely used words associated with semaphores and the likes. P and V are pretty much the worst names you can use on an encyclopedic page, regardless of their historical value. --93.125.228.122 (talk) 09:40, 4 September 2009 (UTC)

I'd be very happy with acquire and release. P and V are remarkably unhelpful. Dan aka jack (talk) 17:43, 25 April 2011 (UTC)

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)

The problem is that the code as is possesses one of the necessary conditions for a deadlock - the process, attempting to decrement the semaphore simultaneously holds resources (it decrements the count) and attempts to acquire more resources (waits until the negative count becomes zero or positive). This can be avoided by making the process in all cases decrement the semaphore with the full value of the second parameter to P. One possible solution, which needs two wait queues (a.k.a. condition variables) and some auxiliary variables is this:

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)

Ambiguity on atomicity of P

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 statement s := s-1?

--AlanH (talk) 23:56, 2 May 2009 (UTC)

I updated this with the idea that the answer to my question is "just the incrementing statement" as that (a) makes sense and (b) is reflected in the "howmany" code. —Preceding unsigned comment added by AlanH (talk • contribs) 00:00, 3 May 2009 (UTC)

Programming Examples

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. —Preceding unsigned comment added by 216.254.69.105 (talk) 19:06, 11 June 2009 (UTC)

Accuracy of description of P and V

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 —Preceding unsigned comment added by 193.190.253.160 (talk) 01:02, 18 June 2009 (UTC)

Don't understand this part

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"? thanks Bayle Shanks (talk) 23:47, 18 November 2009 (UTC)

Suggesting to replace public toilet analogy

with Public parking lot (cars waiting in queue for free resource) or Restaurant (people waiting for tables)
Thanks, Zvika 13:50, 13 January 2010 (UTC) —Preceding unsigned comment added by 212.25.124.163 (talk)

Rewording of Anecdote

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)

Inconsistent statements in Mutex vs. Semaphore need elaboration.

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)

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)]

"Invented" by Dijkstra?

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)

Producer/Consumer example

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. —Preceding unsigned comment added by 188.4.182.33 (talk) 21:48, 20 March 2011 (UTC)

I came to the talk page looking for this very point: the pointers to the head and tail of the queue are a shared resource as well, which need to be protected from multiple access. --76.126.236.172 (talk) 01:36, 21 March 2011 (UTC)

As another note, the language is never specified. I presume that it is C# given the other references to it in the talk page here, but as I do not program in said language (although this page was helpful in terms of qualitative details), I was a little confused with the code examples in the article (although they are not so difficult to understand except for the syntax, which I am unfamiliar with). Even just a "The following C# example illustrates _____" would suffice. 72.54.101.10 (talk) 17:31, 19 July 2011 (UTC)

Description Inaccuracy

The description for a semaphore is inaccurate and confused with the "mutex" concept. In analogy with Flag 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 cited paper by Edsger 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 by Edsger 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)