# Semaphores

## Definition

A **semaphore** is a synchronization mechanism, defined by a data type plus two atomic operations, **down** and **up**.

Data type:

<figure><img src="https://933056030-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FmDWmJ4LyRblScRPGY3di%2Fuploads%2FCYdEtGO9CUMtPjZe66Hk%2Fa.png?alt=media&#x26;token=f56ab6b8-86cd-4b36-92a3-5c7c966e2fbd" alt=""><figcaption></figcaption></figure>

Operations:

* **down**
  * block process if *val* is zero.
  * decrement *val* otherwise.
* **up**
  * if *queue* is not empty, wake up one waiting process (accordingly to a given policy).
  * increment *val* otherwise.

Note that *val* can only be manipulated through these operations.

* It is not possible to check the value of *val*.

## An implementation of semaphores

<figure><img src="https://933056030-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FmDWmJ4LyRblScRPGY3di%2Fuploads%2FyDDpyDGyfdzUSXmT9CTC%2Fa.png?alt=media&#x26;token=5ac9dd2d-2950-4e41-b208-be1fcc5c26c7" alt=""><figcaption></figcaption></figure>

Internally, the *block\_on\_sem* function must enable interruptions.

This implementation is typical of uniprocessor systems. Why?

Semaphores can be binary or not binary.

How to implement **mutual exclusion** using semaphores?

* Using a binary semaphore.

## Bounded-buffer problem

<figure><img src="https://933056030-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FmDWmJ4LyRblScRPGY3di%2Fuploads%2FgpZdDVCNRclry40iJFhv%2Fa.png?alt=media&#x26;token=0316921b-76c6-4536-816a-c73e101e0bc1" alt=""><figcaption><p>This solution can suffer <strong>race conditions</strong>.</p></figcaption></figure>

<figure><img src="https://933056030-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FmDWmJ4LyRblScRPGY3di%2Fuploads%2F1o1mc8CAvCFATdl83L7j%2Fa.png?alt=media&#x26;token=2d0828ad-9be5-467c-b31e-a105eb72ac2d" alt=""><figcaption><p>Mutual exclusion is guaranteed, but suffers from busy waiting</p></figcaption></figure>

<figure><img src="https://933056030-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FmDWmJ4LyRblScRPGY3di%2Fuploads%2FMAcjydVodTCl4PeHr1GM%2Fa.png?alt=media&#x26;token=74eac289-ddad-4726-b457-ced988146040" alt=""><figcaption></figcaption></figure>

How to implement using semaphores?

* guaranteeing mutual exclusion and absence of busy waiting.

<figure><img src="https://933056030-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FmDWmJ4LyRblScRPGY3di%2Fuploads%2FHa9EvVmVoCo5ZIPvGBdE%2Fa.png?alt=media&#x26;token=5eac8ee9-4da1-4d46-ada1-b67adabb5695" alt=""><figcaption></figcaption></figure>

*fifo.notEmpty()*&#x61;nd *fifo.notFull()* are no longer necessary. Why?

<figure><img src="https://933056030-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FmDWmJ4LyRblScRPGY3di%2Fuploads%2FIRLvofVFOVedhVZbMgzb%2Fa.png?alt=media&#x26;token=4fbb68cb-fb86-4d76-ba13-35e0e99915b4" alt=""><figcaption></figcaption></figure>

One can easily make a mistake.

What is wrong with this solution? It can cause **deadlock**.

## Analysis of semaphores

Concurrent solutions based on semaphores have advantages and disadvantages.

**Advantages:**

* **Support at the operating system level** – operations on semaphores are implemented by the kernel and made available to programmers as system calls.
* **General** – they are low level contructions and so they are versatile, being able to be used in any type of solution.

**Disadvantages:**

* **Specialized knowledge** – the programmer must be aware of concurrent programming principles, as race conditions or deadlock can be easily introduced.