Monitors
Introduction
A problem with semaphores is that they are used both to implement mutual exclusion and for synchronization between processes.
Being low level primitives, they are applied in a bottom-up perpective.
if required conditions are not satisfied, processes are blocked before they enter their critical sections.
this approach is prone to errors, mainly in complex situations, as synchronization points can be scattered throughout the program.
A higher level approach should followed a top-down perpective.
processes must first enter their critical sections and then block if continuation conditions are not satisfied.
A solution is to introduce a (concurrent) construction at the programming language level that deals with mutual exclusion and synchronization separately.
A monitor is a synchronization mechanism, independently proposed by Hoare and Brinch Hansen, supported by a (concurrent) programming language.
It is composed of an internal data structure, inicialization code and a number of accessing primitives.
Definition
An application is seen as a set of threads that compete to access the shared data structure.
This shared data can only be accessed through the access methods.
Every method is executed in mutual exclusion.
If a thread calls an access method while another thread is inside another access method, its execution is blocked until the other leaves.
Synchronization between threads is possible through condition variables.
Two operation on them are possible:
wait – the thread is blocked and put outside the monitor.
signal – if there are threads blocked, one is waked up.
Hoare monitor
What to do when signal occurs?
Hoare monitor – the thread calling signal is put out of the monitor, so the just waked up thread can proceed.
quite general, but its implementation requires a stack where the blocked thread is put.
Brinch Hansen monitor
Brinch Hansen monitor – the thread calling signal immediately leaves the monitor (signal is the last instruction of the monitor method).
easy to implement, but quite restrictive (only one signal allowed in a method).
Lampson / Redell monitor
Lampson / Redell monitor – the thread calling signal continues its execution and the just waked up thread is kept outside the monitor, competing for access.
easy to implement, but can cause starvation.
Bounded-buffer problem
Last updated
