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

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

This solution can suffer race conditions.

Mutual exclusion is guaranteed, but suffers from busy waiting.

Solving using semaphores

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

Wrong solution

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.