Concurrency

Semaphore

Semaphore is used for limiting access to a collection of resources. Think of semaphore as having a limited number of permits to give out. If a semaphore has given out all the permits it has, then any new thread that comes along requesting a permit will be blocked till an earlier thread with a permit returns it to the semaphore.

Semaphores are a concurrency control mechanism based on a special variable used for signalling.

• Special variable called a semaphore is used for signaling
• If a process is waiting for a signal, it is suspended until that signal is sent
• Semaphore is a variable that has an integer value
• May be initialized to a nonnegative number

Two operations (atomic):

• Wait operation decrements— the semaphore value
  • Call this to receive a signal via semaphore s
• Signal operation increments++ semaphore value
  • Call this to transmit a signal via semaphore s

If the corresponding signal has not yet been transmitted, the process is suspended until the transmission takes place.

Semaphores can also be used for signalling among threads. This is an important distinction as it allows threads to work towards completing a task cooperatively. See Dijkstra.

To achieve the desired effect proposed by Dijkstra, we can view the semaphore as a variable that has an integer value upon which only three operations are defined:

1. A semaphore may be initialized to a nonnegative integer value.
2. The $semWait$ operation decrements the semaphore value. If the value becomes negative, then the process executing the $semWait$ is blocked. Otherwise, the process continues execution.
3. The $semSignal$ operation increments the semaphore value. If the resulting value is less than or equal to zero, then a process blocked by a $semWait$ operation, if any, is unblocked.

todo

Binary Semaphore

A more restricted version.

A binary semaphore may only take on the values 0 and 1 and can be defined by the following three operations:

1. A binary semaphore may be initialized to 0 or 1.
2. The $semWaitB$ operation checks the semaphore value. If the value is zero, then the process executing the $semWaitB$ is blocked. If the value is one, then the value is changed to zero and the process continues execution.
3. The $semSignalB$ operation checks to see if any processes are blocked on this semaphore (semaphore value equals 0). If so, then a process blocked by a $semWaitB$ operation is unblocked. If no processes are blocked, then the value of the semaphore is set to one.

Related to binary semaphore: Lock.

Difference between mutex and binary semaphore

The process that locks the mutex (sets the value to zero) must be the one to unlock it (sets the value to 1). It is possible for one process to lock a binary semaphore and for another to unlock it.

$semSignal$ increments the semaphore $s$ and sends a process from blocked queue to the ready queue?

$semWait$ sends the process currently running into the blocked queue and decrements the semaphore $s$.

With semaphores, we can implement Mutual Exclusion:

Two possible implementations of semaphores: