Il monitor

Il monitor
1
Costrutti linguistici per la sincronizzazione
è
I semafori costituiscono un meccanismo molto potente per la
sincronizzazione dei processi. Tuttavia, il suo uso può risultare
troppo “a basso livello”.
Possibilità di errori
Esempio: mutua esclusione
• scambio tra wait e signal:
signal(mutex);
<A>;
wait(mutex);
più processi possono operare nella sezione critica.
• utilizzo erroneo di wait e signal:
• etc.
wait(mutex);
<A>;
wait(mutex); -> deadlock.
2
1
Costrutti linguistici per la
sincronizzazione
èPer ovviare a problemi di questa natura si sono
introdotti costrutti linguistici “a più alto livello” :
•regioni critiche semplici e condizionali
•monitor
3
Il costrutto monitor [Hoare 74]
Definizione: Costrutto sintattico che associa un
insieme di operazioni (public o entry) ad una
struttura dati comune a più processi, tale che:
• Le operazioni entry sono le sole operazioni
permesse su quella struttura.
• Le operazioni entry sono mutuamente esclusive: un
solo processo per volta può essere attivo nel
monitor.
4
2
monitor tipo_risorsa {
<dichiarazioni variabili locali>;
<inizializzazione variabili locali>;
public void op1 ( ) {
<corpo della operazione op1 >;
}
---------public void opn ( ) {
<corpo della operazione opn>;
}
<eventuali operazioni non public>
}
5
• Le variabili locali sono accessibili solo entro il monitor.
• Le operazioni public (o entry) sono le sole operazioni che
possono essere utilizzate dai processi per accedere alle
variabili locali. L'accesso avviene in modo mutuamente
esclusivo.
• Le variabili locali mantengono il loro valore tra successive
esecuzioni delle operazioni del monitor (variabili
permanenti).
• Le operazioni non dichiarate public non sono accessibili
dall’esterno. Sono usabili solo all'interno del monitor (dalle
funzioni public e da quelle non public).
6
3
Uso del monitor
tipo_risorsa ris;
ècrea una istanza del monitor, cioè una struttura dati
organizzata secondo quanto indicato nella
dichiarazione dei dati locali.
ris.opi(...);
èchiamata di una generica operazione dell’oggetto ris.
7
Uso del monitor
Scopo del monitor è controllare l’accesso a una risorsa da
parte processi concorrenti in accordo a determinate
politiche. Le variabili locali definiscono lo stato della
risorsa associata al monitor.
L’accesso alla risorsa avviene secondo due livelli di
controllo:
1. Il primo garantisce che un solo processo alla volta possa aver
accesso alle variabili comuni del monitor. Ciò è ottenuto
garantendo che le operazioni public siano eseguite in modo
mutuamente esclusivo (eventuale sospensione dei processi
nella entry queue).
2. Il secondo controlla l’ordine con il quale i processi hanno
accesso alla risorsa. La procedura chiamata verifica il
soddisfacimento di una condizione logica (condizione di
sincronizzazione) che assicura l’ordinamento (eventuale
sospensione del processo in una coda associata alla
8
condizione e liberazione del monitor).
4
• Nel caso in cui la condizione non sia verificata, la
sospensione del processo avviene utilizzando
variabili di un nuovo tipo, detto condition
(condizione).
• La condizione di sincronizzazione è costituita da
variabili locali al monitor e da variabili proprie del
processo passate come parametri.
9
Variabili tipo condizione
La dichiarazione di una variabile cond di tipo
condizione ha la forma:
condition cond;
• Ogni variabile di tipo condizione rappresenta una coda
nella quale i processi si sospendono.
Operazioni sulle variabili condition:
• Le operazioni del monitor agiscono su tali variabili
mediante le operazioni:
wait(cond);
signal(cond);
10
5
wait:
• L’esecuzione dell’operazione wait(cond) sospende il
processo, introducendolo nella coda individuata dalla
variabile cond, e il monitor viene liberato.
signal:
• L’esecuzione dell’operazione signal(cond) rende attivo
un processo in attesa nella coda individuata dalla
variabile cond.
11
Semantiche dell’operazione signal
Q:
signal(cond);
signal(cond);
P:
wait(cond);
Come conseguenza della signal entrambi i processi, quello
segnalante Q e quello segnalato P, possono concettualmente
proseguire la loro esecuzione.
Possibili strategie:
signal_ and_ wait. P riprende immediatamente l’esecuzione ed
il processo Q viene sospeso.
signal_ and_ continue. Q prosegue la sua esecuzione
mantenendo l’accesso esclusivo al monitor, dopo aver
risvegliato il processo .
12
6
• Con la signal_ and_ wait si evita la possibilità che
Q, proseguendo, possa modificare la condizione di
sincronizzazione rendendola non più vera per P.
• Q si sospende nella coda dei processi che
attendono di usare il monitor (entry queue).
13
Semantiche della signal
condition
queue
Signal&Continue
Signal&Wait
wait
monitor libero
entry
queue
esecuzione
Signal&Continue
no
call
monitor
libero
Signal&Wait
si
14
7
Signal_and_urgent_wait
E` una variante della signal_and_wait.
signal_and_urgent_wait. Q ha la priorità rispetto agli altri processi
che aspettano di entrare nel monitor. Viene quindi sospeso in una
coda interna al monitor (urgent queue). Quando P ha terminato la
sua esecuzione (o si è nuovamente sospeso), trasferisce il controllo
a Q senza liberare il monitor.
condition
queue
Signal&UrgentWait
wait
Signal&UrgentWait
monitor libero
entry queue
urgent
queue
esecuzione
no
call
monitor
libero
P termina o si sospende
si
15
• Un caso particolare della signal _and_urgent_wait (e
della signal_and_wait) si ha quando essa corrisponde
ad una istruzione return: signal_and_return.
• Il processo completa cioè la sua operazione con il
risveglio del processo segnalato. Cede ad esso il
controllo del monitor senza rilasciare la mutua
esclusione.
16
8
signal_and_continue
• Il processo segnalato P viene trasferito dalla coda
associata alla variabile condizione alla entry_queue e
potrà rientrare nel monitor una volta che Q l’abbia
rilasciato.
• Poiché altri processi possono entrare nel monitor prima di
P, questi potrebbero modificare la condizione di
sincronizzazione (lo stesso potrebbe fare Q).
• E’ pertanto necessario che quando P rientra nel monitor
ritesti la condizione:
while(!B) wait (cond);
<accesso alla risorsa>
17
• E’ possibile anche risvegliare tutti i processi sospesi
sulla variabile condizione utilizzando la :
signal_all
che è una variante della signal_and_continue.
èTutti i processi risvegliati vengono messi nella
entry_queue dalla quale, uno alla volta potranno
rientrare nel monitor.
18
9
Esempio: monitor come gestore di
risorse (mailbox)
Utilizziamo il monitor per risolvere il problema della
comunicazione tra processi (“produttori e
consumatori”):
r il monitor rappresenta il buffer dei messaggi
(gestito in modo circolare)
r i processi Produttori (o Consumatori)
inseriranno (o preleveranno) i messaggi
mediante le funzioni entry Send (o Receive)
definite nel monitor.
r la struttura dati che rappresenta il buffer fa
parte delle variabili locali al monitor e quindi
le operazioni Send e Receive possono accedere
solo in modo mutuamente esclusivo a tale
struttura.
19
monitor buffer_circolare{
messaggio buffer[N];
int contatore=0; int testa=0; int coda=0;
condition non_pieno;
condition non_vuoto;
/* procedure e funzioni entry: */
public void send(messaggio m){ /*proc. entry -> mutua esclusione*/
if (contatore==N) non_pieno.wait;
buffer[coda]=m;
coda=(coda + 1)%N;
++contatore;
non_vuoto.signal;
}
public messaggio receive(){ /*proc. entry -> mutua esclusione*/
messaggio m;
if (contatore == 0) non_vuoto.wait;
m=buffer[testa];
testa=(testa + 1)%N;
--contatore;
non_pieno.signal;
return m;}
}/* fine monitor */
20
10
Esempio: monitor come allocatore
di risorse
Utilizziamo il monitor per garantire l’accesso esclusivo
ad una risorsa comune da parte dei processi.
r La struttura dati gestita dal monitor rappresenta lo
stato (libero,occupato) della risorsa.
r Le operazioni Richiesta e Rilascio del monitor sono
utilizzate solo per garantire l’accesso esclusivo alla
risorsa da parte dei processi.
r La mutua esclusione tra le operazioni Richiesta e
Rilascio garantisce che lo stato della risorsa venga
esaminato in modo mutuamente esclusivo dai
processi.
r Una volta guadagnato l’accesso alla risorsa i singoli
processi potranno accedere direttamente ad essa
21
all’esterno del monitor.
monitor allocatore
{ boolean occupato = false;
condition libero;
public void Richiesta()
{
if (occupato) libero.wait;
occupato = true;
}
public void Rilascio()
{
occupato = false;
libero.signal;
}
}
allocatore A; /* istanza del tipo monitor*/
void processo() /*codice di un generico processo */
{
A.Richiesta;
<uso della risorsa>;
A.Rilascio;
}
22
11
Realizzazione del costrutto monitor tramite
semafori
Il compilatore assegna ad ogni istanza di un monitor:
• un semaforo mutex inizializzato a 1 per la mutua
esclusione delle operazioni del monitor:
• la richiesta di un processo di eseguire
un’operazione public equivale all’esecuzione di una
P(mutex).
Il compilatore assegna a ogni variabile cond di tipo
condition:
• un semaforo condsem inizializzato a 0 sul quale il
processo si può sospendere tramite una
wait(condsem).
• un contatore condcount inizializzato a 0 per tenere
conto dei processi sospesi su condsem.
23
Signal_and_ continue
Prologo di ogni operazione public: P(mutex);
Epilogo di ogni operazione public: V(mutex);
wait(cond):
{
condcount++;
V(mutex);
P(condsem);
P(mutex);
}
Signal&Continue
call
signal(cond):
{
if (condcount>0)
{
condcount--;
V(condsem);
}
}
condition
queue
entry queue
wait
esecuzione
monitor libero
Signal&Continue
24
12
Signal_and_ wait
Prologo di ogni operazione public P(mutex);
Epilogo di ogni operazione public V(mutex);
wait(cond):
{
condcount++;
V(mutex);
P(condsem);
}
condition
queue
signal(cond):
{
if (condcount>0)
{
condcount-- ;
V(condsem);
entry
P(mutex);
queue
}
call
}
Signal&Wait
wait
monitor libero
esecuzione
Signal&Wait
25
Signal_and_urgent_wait
urgent: semaforo per la sospensione del processo segnalante (v.iniz. 0)
urgentcount: contatore dei processi sospesi su urgent
Prologo di ogni operazione: P(mutex);
Epilogo di ogni operazione: if(urgentcount>0)
wait(cond):
{
condcount++;
if (urgentcount>0)
V(urgent);
else V(mutex);
P(condsem);
condcount-- ; }
call
V(urgent) else V(mutex);
condition
queue
Signal&UrgentWait
wait
entry
queue
signal(cond):
{
if (condcount>0
{ urgentcount++;
V(condsem);
P(urgent);
urgentcondcount-- ;
}
}
monitor libero
esecuzione
Signal&UrgentWait
P termina o si sospende
urgent
queue
26
13
Signal_and_return
Prologo di ogni operazione: P(mutex);
Epilogo di ogni operazione:
•se la funzione non contiene signal allora : V(mutex)
•altrimenti signal(cond) (vedi sotto).
wait(cond):
{
condcount++;
V(mutex);
P(condsem);
condcount-- ;
}
signal(cond):
{
if (condcount>0)
V(condsem);
else V(mutex);
}
27
Ulteriori operazioni sulle variabili
condizione
Sospensione con indicazione della priorità:
wait(cond, p);
èi processi sono accodati rispettando il valore (crescente o
decrescente) di p e vengono risvegliati nello stesso
ordine.
Verifica dello stato della coda:
queue(cond);
èfornisce il valore vero se esistono processi sospesi nella
coda associata a cond , true altrimenti.
28
14
Esempio: allocazione di risorse in uso esclusivo
Si vuole che la risorsa venga assegnata a quello tra tutti i processi sospesi che
la userà per il periodo di tempo inferiore :
monitor allocatore
{ boolean occupato = false;
condition libero;
public void Richiesta(int tempo)
{
if (occupato) libero.wait(tempo);
occupato = true;
}
public void Rilascio()
{
occupato = false;
libero.signal;
}
}
I processi sono inseriti nella coda secondo l’ordine crescente di p e quindi il
primo processo risvegliato è quello che richiede meno tempo.
29
Esempio: lettori e scrittori
Si supponga di voler realizzare la seguente politica di
allocazione della risorsa:
1. un nuovo lettore non può acquisire la risorsa se c’e’ uno
scrittore in attesa
2. tutti i lettori sospesi al termine di una scrittura hanno
priorità sul successivo scrittore
Soluzione: uso del monitor con le seguenti variabili locali:
•
•
•
num-lettori: il numero di processi lettori attivi sulla risorsa
occupato: una variabile logica che indica se la risorsa è
occupata da uno scrittore (occupato=true)
ok-lettura , ok-scrittura : due variabili condizione sulle
quali si sospendono rispettivamente i processi lettori e
scrittori
30
15
monitor lettori_scrittori
{ int num-lettori=0,occupato=0;
condition ok_lettura,ok_scrittura;
public void inizio_lettura()
{
if (occupato || ok_scrittura.queue)
ok_lettura.wait;
num_lettori++;
ok_lettura.signal;
}
public void fine_lettura()
{
num_lettori-- ;
if (num_lettori==0)
ok_scrittura.signal;
}
public void inizio_scrittura()
{
if ((num_lettori!=0)|| occupato)
ok_scrittura.wait;
occupato=1;
}
/* continua...*/
31
/* ...continua */
public void fine_scrittura()
{
occupato=0;
if (ok-lettura.queue)
ok-lettura.signal;
else
ok-scrittura.signal;
}
}/* fine monitor */
lettori_scrittori LS; /* istanza del monitor*/
void lettore() /*codice di un generico lettore */
{
LS.inizio_lettura();
<lettura>;
LS.fine_lettura()
}
void scrittore() /*codice di un generico scrittore */
{
LS.inizio_scrittura();
<scrittura>;
LS.fine_scrittura()
}
32
16
Esempio di uso del costrutto
monitor
L'algoritmo dell'ascensore (scan)
33
Algorimo scan
• In un edificio a N piani, l'ascensore deve servire le
richieste di utenti che competono per usare
l'ascensore, con l'obiettivo di spostarsi a un piano
diverso.
• L'ascensore puo` servire una richiesta alla volta.
• Movimento: l'ascensore si puo` spostare tra gli N
piani [0,..N-1] nelle due direzioni:
r dal basso verso l'alto (SU);
r nella direzione opposta (GIU);
• L'algoritmo SCAN e` una possibile politica di
scheduling delle richieste di uso dell'ascensore,
che ha come obiettivo la minimizzazione del
numero dei cambiamenti di direzione.
34
17
SCAN
Politica:
r
in ogni istante, all'ascensore e` associata una direzione corrente
(SU, GIU) e una posizione corrente (piano associato alla prossima
richiesta da servire).
r
ogni richiesta e` caratterizzata da una destinazione T (che
individua il piano di destinazione richiesto dall'utente in attesa):
• se l'ascensore sta salendo (direzione SU), verranno servite tutte le
richieste con T raggiungibile in quella direzione (T> posizione corrente)
• se l'ascensore sta scendendo (direzione GIU), verranno servite tutte le
richieste con T raggiungibile in quella direzione (T< posizione corrente).
r
r
le richieste sono servite secondo l’ordine di vicinanza alla richiesta
corrente.
Quando nella direzione scelta non ci sono più richieste da servire, la
direzione dell'ascensore viene invertita ed il procedimento è
ripetuto.
N.B.Viene servita una richiesta alla volta.
35
Soluzione: monitor
• Modelliamo ogni utente dell'ascensore con un processo (thread)
concorrente.
• Definiamo un monitor, il cui compito e` realizzare la politica di
servizio mediante le due procedure entry:
r
Richiesta(T): viene invocata dai processi per ottenere la
fermata dell'ascensore al piano T:
• se l'ascensore è occupato, la richiesta del processo viene
accodata in funzione dello stato corrente del'ascensore
(direzione e richiesta corrente) in una coda associata ad una
direzione in modo da rispettare la politica.
r
Rilascio: viene invocata da ogni processo arrivato a
destinazione per rilasciare l'ascensore:
• se vi sono richieste in attesa sulla stessa direzione, verra`
risvegliata la prima (la piu` vicina alla posizione corrente
dell'ascensore); altrimenti, la direzione verra` invertita e verra`
risvegliato il primo processo in attesa nella nuova direzione.
N.B.Viene servita una richiesta alla volta.
36
18
Monitor
• Il monitor e` caratterizzato dalle seguenti
variabili:
r occupato: indica se l'ascensore sta servendo
una richiesta;
r direzione: indica la direzione corrente
dell'ascensore (SU, GIU);
r posizione: indica la destinazione corrente;
r dir_SU, dir_GIU: condition associate alle due
direzioni, sulle quali si sospenderanno i processi
in attesa di servizio.
37
typedef int piano;
typedef enum{SU,GIU}dir;
monitor movimento_ascensore
{ piano posizione=0; /*inizialmente al piano terra..*/
boolean occupato=false;
/* inizialmente libero..*/
dir direzione=SU;
condition dir_SU,dir_GIU;
public void Richiesta(piano dest)
{ if (occupato==true)
if ((direzione==SU)&& (dest<=posizione))
dir_GIU.wait(dest);
else dir_SU.wait(N-dest);
occupato=true;
posizione=dest;
}
38
19
public void Rilascio
{ occupato=false;
if (direzione==SU)
if (dir_SU.queue)
dir_SU.signal;
else{
direzione=GIU;
dir_GIU.signal; }
else
if (dir_GIU.queue)
dir_GIU.signal;
else{
direzione=SU;
dir_SU.signal; }
}
} /* fine monitor*/
39
movimento_ascensore A; /* istanza del monitor*/
void Utente() /*codice di un generico utente */
{
piano P;
<assegnamento valore di P>
A.Richiesta(P);
<uso dell'ascensore>;
A.Rilascio();
}
40
20