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