Editing Semaphore (programming) (section)

==Semantics and implementation==
Counting semaphores are equipped with two operations, historically denoted as P and V (see {{section link||Operation names}} for alternative names). Operation V increments the semaphore ''S'', and operation P decrements it.

The value of the semaphore ''S'' is the number of units of the resource that are currently available. The P operation [[busy waiting|wastes time]] or [[Sleep (system call)|sleeps]] until a resource protected by the semaphore becomes available, at which time the resource is immediately claimed. The V operation is the inverse: it makes a resource available again after the process has finished using it.
One important property of semaphore ''S'' is that its value cannot be changed except by using the V and P operations.

A simple way to understand {{mono|wait}} (P) and {{mono|signal}} (V) operations is:
* {{mono|wait}}: Decrements the value of the semaphore variable by 1. If the new value of the semaphore variable is negative, the process executing {{mono|wait}} is blocked (i.e., added to the semaphore's queue). Otherwise, the process continues execution, having used a unit of the resource.
* {{mono|signal}}: Increments the value of the 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.

Many operating systems provide efficient semaphore primitives that unblock a waiting process when the semaphore is incremented. This means that processes do not waste time checking the semaphore value unnecessarily.

The counting semaphore concept can be extended with the ability to claim or return more than one "unit" from the semaphore, a technique implemented in [[Unix]]. The modified V and P operations are as follows, using square brackets to indicate [[atomic operation]]s, i.e., operations that appear indivisible to other processes:

 '''function''' V(semaphore S, integer I):
     [S ← S + I]
 
 '''function''' P(semaphore S, integer I):
     '''repeat:'''
         ['''if''' S ≥ I:
         S ← S − I
         '''break''']

However, the rest of this section refers to semaphores with unary V and P operations, unless otherwise specified.

To avoid [[Resource starvation|starvation]], a semaphore has an associated [[queue (data structure)|queue]] of processes (usually with [[FIFO (computing and electronics)|FIFO]] semantics). If a process performs a P operation on a semaphore that has the value zero, the process is added to the semaphore's queue and its execution is suspended. 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. When processes have different priorities the queue may be ordered thereby, such that the highest priority process is taken from the queue first.

If the implementation does not ensure atomicity of the increment, decrement, and comparison operations, there is a risk of increments or decrements being forgotten, or of the semaphore value becoming negative. Atomicity may be achieved by using a machine instruction that can [[read-modify-write|read, modify, and write]] the semaphore in a single operation. Without such a hardware instruction, an atomic operation may be synthesized by using a [[Mutual exclusion#Software solutions|software mutual exclusion algorithm]]. On [[uniprocessor]] systems, atomic operations can be ensured by temporarily suspending [[preemption (computing)|preemption]] or disabling hardware [[interrupt]]s. This approach does not work on multiprocessor systems where it is possible for two programs sharing a semaphore to run on different processors at the same time. To solve this problem in a multiprocessor system, a locking variable can be used to control access to the semaphore. The locking variable is manipulated using a [[Test-and-set|test-and-set-lock]] command.