Semaphores

Definition

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

Data type:

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

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

This solution can suffer race conditions.

Mutual exclusion is guaranteed, but suffers from busy waiting

How to implement using semaphores?

• guaranteeing mutual exclusion and absence of busy waiting.

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

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.