Talk:Semaphore (programming)

Assembly language instruction

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. — Preceding unsigned comment added by 187.95.110.228 (talk) 23:45, 10 June 2014 (UTC)

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

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)

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

• Actually, he wrote many but not all of his early papers in Dutch, and his later papers predominantly in English. There are multiple explanations for what P is in the record; the oldest Dijkstra paper I can find (EWD35) gives it as "passeren" which is Dutch for "to pass". It also explains that the terminology comes from railroads. That fits; the block system of railroads uses signposts (semaphores) that admit one train at a time into a "block", and in the process of entering, the signal changes from green to red, just what the P operation does. I've updated the article to reflect this older reference. Paul Koning (talk) 21:33, 16 December 2014 (UTC)

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)

It's perfectly fine to use newer terminology in addition to the original. But the original is P and V, for the reasons given. Yes, those aren't all that helpful (unless you speak Dutch). But the article needs to talk about history from the beginning. It should not limit itself to the descriptive terms and in the process lose part of the history. Paul Koning (talk) 21:09, 18 August 2015 (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)

The whole function. If you made just s := s-1 atomic, someone could set s to 1, then two threads might see that s > 0 and both do the decrement. If the decrement is atomic the answer would then reliably be -1 (instead of being either 0 or -1) but the operation of the P function would still be wrong. Paul Koning (talk) 21:37, 16 December 2014 (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)

Whether you do busy waiting or rescheduling is an implementation optimization detail. Busy waiting is valid (the result is correct) and in some situations may well be the best answer in practice. In any case, the description given is a minimal description of the correct behavior, not a detailed program for a particular implementation. Paul Koning (talk) 21:39, 16 December 2014 (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)

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)

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)

 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  — Preceding unsigned comment added by 71.70.253.160 (talk) 08:50, 13 December 2013 (UTC) 

The oldest publication I can find is by Dijkstra in either 1962 or 1963, the article now cites that one. As for "any complex operating system well prior to 1965", if you know of any that use this sort of mechanism, please propose a citation. Have you looked at operating systems that old? I have some experience with CDC mainframe operating systems whose origin is around 1964; those don't use semaphores or anything even remotely like it. His famous paper Dijkstra, Edsger W. The structure of the THE operating system (EWD-196) (PDF). E.W. Dijkstra Archive. Center for American History, University of Texas at Austin. (transcription) was a seminal paper in 1968; it was among the first, if not the first, descriptions of an operating system structure in terms of cooperating processes with explicit synchronization. So yes, I find the evidence compelling, especially in the absence of anything to contradict it. Paul Koning (talk) 21:46, 16 December 2014 (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)

Agreed, this is a terrible example...the current code in the article is bogus. To anyone who reads this message, there is no need to let the article rot away for over a year. If you see something wrong in a Wikipedia article, please do take the time to at least mark it with a template indicating the problem, for example "this section appears to contradict itself". I'll merge in the corrected version in a little bit... 173.239.78.54 (talk) 04:00, 21 May 2012 (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)

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)

Semaphore == 0 or negative?

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:

A simple way to understand wait() and signal() operations is:

wait(): Decrements the value of semaphore variable by 1. If the value becomes negative, the process executing wait() is blocked, i.e., added to the semaphore's queue.

signal(): Increments the value of semaphore variable by 1. After the increment, if the value was negative (meaning there are processes waiting for a resource), it transfers a blocked process from the semaphore's waiting queue to the ready queue.

Should be amended to

A simple way to understand wait() and signal() operations is:

wait(): Decrements the value of semaphore variable by 1. If the value becomes zero, the process executing wait() is blocked, i.e., added to the semaphore's queue.

signal(): Increments the value of semaphore variable by 1. After the increment, if the value goes from zero to 1 (meaning there are processes waiting for a resource), it transfers a blocked process from the semaphore's waiting queue to the ready queue.

— Preceding comment added by Yonemo (talk) 21:02, 27 June 2012 (UTC)Yonemo (talk • contribs) 20:54, 27 June 2012 (UTC)

This is not correct. A value of 0 does mean that the semaphore is out of resources. But we're talking about the value before the wait() call. So if wait() decrements the counter from one to zero, we still had a resource (and the requesting thread can use it), but now there are no more free. Jeh (talk) 09:31, 5 March 2015 (UTC)

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

wait(): If the value of semaphore variable is not negative, decrements it by 1. If the semaphore variable is now negative, the process executing wait() is blocked (i.e., added to the semaphore's queue) until the value is greater or equal to 1. Otherwise, the process continues execution, having used a unit of the resource.

signal(): Increments the value of semaphore variable by 1. After the increment, if the pre-increment value was negative (meaning there are processes waiting for a resource), it transfers a blocked process from the semaphore's waiting queue to the ready queue.

should be

wait(): If the value of the semaphore variable would become negative by decrementing it by 1, the process executing wait() is blocked (i.e., added to the semaphore's queue). Prior to resuming or continuing execution of the process, the variable is decremented by 1, the process having used a unit of the resource.

signal(): Increments the value of the semaphore variable by 1. After the increment, if the pre-increment value was zero and if there are processes waiting for a resource, a blocked process is transferred from the semaphore's waiting queue to the ready queue.

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)

Implementations may use -1, 0, and positive in order to take advantage of negative and zero condition bits in the processor status. Jeh (talk) 00:49, 8 September 2015 (UTC)

Totorigolo (talk) 10:56, 15 October 2018 (UTC)

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

• initially, the semaphore variable is 1 (let's call it v).
• A executes wait(). v=1 isn't negative so v'=0. v' isn't negative so A continues execution.
• B executes wait(). Since v=0 isn't negative, v'=-1. v' is negative so B is blocked.
• A executes signal(). v=-1 -> v'=0. v is negative so B is placed in the ready queue.
• B is in the ready queue, but since v=0 B is still blocked because of this statement: "until v is greater or equal to 1".

IMO a correct version would be (this is a simplified version of the French article's description):

• wait: if the value of semaphore variable is negative or zero, add the process executing wait to the semaphore's queue and set its state to blocked. Then, decrement the value by one.
• signal: increment the value of the semaphore variable by one. If the semaphore's queue isn't empty, awake the process in the head of the queue and pop it from the queue.

Also, it should be mentioned that these two operations are atomic.

Multi User

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)

Article fails to explain what a semaphore is

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 a mutex. 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)

A Mutex is a type of semaphore. Specifically a binary one. Carewolf (talk) 22:01, 25 August 2014 (UTC)

"A simple way to understand" is not complete... I don't think

I reverted this 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)

• signal() when the value is -1 will increment it to zero, unblock a waiter, who will decrement it again to -1. So the next signal will do the same. Paul Koning (talk) 15:17, 14 April 2015 (UTC)

Recent edits to lede by Dipankarpal5050

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 are atomic: 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 of fundamental 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 a counting 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)

Further investigation showed that the material added was a clear COPYVIO. I've removed it. Jeh (talk) 09:30, 5 March 2016 (UTC)

Copyright problem removed

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

For legal reasons, we cannot accept copyrighted text or images borrowed from other web sites or published material; such additions will be deleted. Contributors may use copyrighted publications as a source of information, and, if allowed under fair use, may copy sentences and phrases, provided they are included in quotation marks and referenced properly. The material may also be rewritten, providing it does not infringe on the copyright of the original or plagiarize from that source. Therefore, such paraphrased portions must provide their source. Please see our guideline on non-free text for how to properly implement limited quotations of copyrighted text. Wikipedia takes copyright violations very seriously, and persistent violators will be blocked 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)

Unclear preamble

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)

Re-estimated article quality at last

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)

WAIT/POST

IBM from OS/360 on, uses WAIT/POST, named after the two macro instructions, and the Event 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)