1
Il monitor
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:
wait(mutex);
<A>;
wait(mutex); -> deadlock.
• etc.
3
èPer ovviare a problemi di questa natura si sono introdotti costrutti linguistici “a più alto livello” :
•regioni critiche semplici e condizionali
•monitor
Costrutti linguistici per la sincronizzazione
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.
5
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>
}
• 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).
7
tipo_risorsa ris;
ècrea una istanza del monitor, cioè una struttura dati organizzata secondo quanto indicato nella
dichiarazione dei dati locali.
ris.op
i(...);
èchiamata di una generica operazione dell’oggetto ris.
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
Uso del monitor
9
• 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.
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);
Variabili tipo condizione
11
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.
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 .
Q:
signal(cond);
P:
wait(cond);
signal(cond);
Semantiche dell’operazione signal
13
• 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).
entry queue
condition queue
esecuzione
Signal&Wait
Signal&Wait Signal&Continue
wait
Signal&Continue monitor libero
Semantiche della signal
call
monitor libero no
si
15
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.
Signal_and_urgent_wait
entry queue
condition queue
esecuzione
Signal&UrgentWait wait
monitor libero
urgent queue
P termina o si sospende Signal&UrgentWait
call monitor libero
no
si
• 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.
17
• 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>
signal_and_continue
• 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.
19
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.
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 */
21
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 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;
}
23
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.
Realizzazione del costrutto monitor tramite semafori
Prologo di ogni operazione public: P(mutex);
Epilogo di ogni operazione public: V(mutex);
wait(cond):
{ condcount++;
V(mutex);
P(condsem);
P(mutex);
}
signal(cond):
{ if (condcount>0) { condcount--;
V(condsem);
}
entry queue
condition queue
esecuzione
Signal&Continue wait
Signal&Continue
monitor libero call
Signal_and_ continue
25
Prologo di ogni operazione public P(mutex);
Epilogo di ogni operazione public V(mutex);
wait(cond):
{ condcount++;
V(mutex);
P(condsem);
}
signal(cond):
{ if (condcount>0) { condcount-- ;
V(condsem);
P(mutex);
} }
entry queue
condition queue
esecuzione
Signal&Wait
Signal&Wait
wait
monitor libero
call
Signal_and_ 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) V(urgent) else V(mutex);
wait(cond):
{ condcount++;
if (urgentcount>0) V(urgent);
else V(mutex);
P(condsem);
condcount-- ; } signal(cond):
{ if (condcount>0 { urgentcount++;
V(condsem);
P(urgent);
entry queue
condition queue
esecuzione
Signal&UrgentWait
wait
monitor libero
urgent queue P termina o si sospende
Signal&UrgentWait
call
Signal_and_urgent_wait
27
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);
}
Signal_and_return
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.
Ulteriori operazioni sulle variabili
condizione
29
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.
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
31
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...*/
/* ...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() }
33
Esempio di uso del costrutto monitor
L'algoritmo dell'ascensore (scan)
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.
35
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 le richieste sono servite secondo l’ordine di vicinanza alla richiesta corrente.
r 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.
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.
37
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.
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;
}
39 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*/
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();
}
