# Semaphores

## Definition

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

Data type:

```
typedef struct
{
    unsigned int val;    /* can not be negative */
    PROCESS *queue;      /* queue of waiting blocked processes */  
} SEMAPHORE;
```

Operations:

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

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%2FciGXjjbnLveBDniNYIRd%2Fa.png?alt=media&#x26;token=3b674dd8-ae29-4974-8940-0a0b4ff071da" alt=""><figcaption></figcaption></figure>

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

#### Problem statement

In this problem, a number of entities (producers) produce information that is consumed by a number of different entities (consumers).

Communication is carried out through a buffer with bounded capacity.

Assume that every producer and every consumer runs in a different process.

* Hence the FIFO must be implemented in **shared memory** so the different processes can access it.

How to guarantee that **race conditions** don’t arise?

* Enforcing **mutual exclusion** in the access to the FIFO.

#### Implementation

<figure><img src="https://933056030-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FmDWmJ4LyRblScRPGY3di%2Fuploads%2FrCp2iQ3p7xuUEt1jNggv%2Fa.png?alt=media&#x26;token=b9acb763-5c98-4487-8f21-4dc18c7480d0" 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%2FI87ODP02e5H44IrJCEIP%2Fa.png?alt=media&#x26;token=14d80693-f317-4bd7-bab5-cf9f6920c9cd" alt=""><figcaption><p><strong>Mutual exclusion</strong> is guaranteed, but suffers from <strong>busy waiting</strong>.</p></figcaption></figure>

### Solving using semaphores

<figure><img src="https://933056030-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FmDWmJ4LyRblScRPGY3di%2Fuploads%2F6jbUR2eb3oYL6la6Db4D%2Fa.png?alt=media&#x26;token=435e49d6-1b24-4fba-adea-8356cbeacbb9" alt=""><figcaption></figcaption></figure>

_fifo.notEmpty()_ and _fifo.notFull()_ are no longer necessary. Why?

### Wrong solution

<figure><img src="https://933056030-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FmDWmJ4LyRblScRPGY3di%2Fuploads%2Fen4kVZ6R1G44RcOW3bUP%2Fa.png?alt=media&#x26;token=5f895f6c-bd8c-4c06-ae59-99b142485602" 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 constructions 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.
