A semaphore is a protected variable (or abstract data type) and constitutes the classic method for restricting access to equivalent shared resources (e.g. storage) in a multiprogramming environment. They were invented by Edsger Dijkstra and first used in the THE operating system. The value of the semaphore is initialized to the number of equivalent shared resources it is implemented to control. In the special case where there is a single equivalent shared resource, the semaphore is called a binary semaphore. The general case semaphore is often called a counting semaphore. Semaphores are the classic solution to the dining philosophers problem, although they do not prevent all deadlocks. Semaphores can only be accessed using the following operations: P(Semaphore s) { await s > 0, then s := s-1; /* must be atomic once s > 0 is detected */ } V(Semaphore s) { s := s+1; /* must be atomic */ } Init(Semaphore s, Integer v) { s := v; } Notice that incrementing the variable s must not be interrupted, and the P operation must not be interrupted after s is found to be nonzero. This can be done by special instruction (if the architecture's instruction set supports it) or by ignoring interrupts in order to prevent other processes from becoming active. The canonical names P and V come from the initials of Dutch words. V stands for verhoog, or "increase." Several explanations have been given for P (including passeer "pass," probeer "try," and pakken "grab"), but in fact Dijkstra wrote that he intended P to stand for the made-up portmanteau word prolaag,[1] short for probeer te verlagen, or "try-and-decrease."[2][3] (A less ambiguous English translation would be "try-to-decrease.") This confusion stems from the unfortunate characteristic of the Dutch language that the words for increase and decrease both begin with the letter V, and the words spelled out in full would be impossibly confusing for non–Dutch-speakers. The value of a semaphore is the number of units of the resource which are free. (If there is only one resource, a "binary semaphore" with values 0 or 1 is used.) The P operation busy-waits (or maybe sleeps) until a resource is available, whereupon it immediately claims one. V is the inverse; it simply makes a resource available again after the process has finished using it. Init is only used to initialize the semaphore before any requests are made. The P and V operations must be atomic, which means that no process may ever be preempted in the middle of one of those operations to run another operation on the same semaphore. In English textbooks, and in the programming language ALGOL 68, the P and V operations are sometimes called, respectively, down and up. In software engineering practice they are called wait and signal, or take and release, or pend and post. To avoid busy-waiting, a semaphore may have an associated queue of processes (usually a FIFO). If a process performs a P operation on a semaphore which has the value zero, the process is added to the semaphore's queue. When another process increments the semaphore by performing a V operation, and there are processes on the queue, one of them is removed from the queue and resumes execution.