> For the complete documentation index, see [llms.txt](https://davidjosearaujo.gitbook.io/notes-miect/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://davidjosearaujo.gitbook.io/notes-miect/sistemas-de-operacao/semaphores-and-shared-memory/semaphores.md).

# 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&amp;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&amp;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&amp;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&amp;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&amp;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.