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
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
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.
Last updated