Utente:LoStrangolatore/Stubs/Guida alla programmazione/Monitor
Nella programmazione dei computer, un monitor è una tecnica di sincronizzazione dell'accesso a un risorsa condivisa tra due o più task (cioè, processi o thread).
Mutua esclusione
modificaUn monitor consiste in:
- Un insieme di procedure che consentono l'interazione con la risorsa condivisa.
- Un blocco di mutua esclusione (lock).
- Le variabili associate alla risorsa.
- Un'invariante di monitor che definisce le assunzioni necessarie per evitare conflitti.
Una procedura di monitor prende il blocco prima di fare ogni altra cosa, e lo tiene finché o finisce o entra in attesa di una condizione (spiegata sotto). Se ogni procedura garantisce che l'invariante è vero prima di rilasciare il blocco, allora nessun task può mai trovare la risorsa in uno stato che potrebbe condurre a un conflitto.
Come semplice esempio, si consideri un monitor per eseguire transazioni su un conto bancario.
monitor conto {
int saldo := 0
function preleva(int importo) {
if importo < 0 then error "L'importo non puù essere negativo"
else if saldo < importo then error "Fondi insufficienti"
else saldo := saldo - importo
}
function deposita(int importo) {
if importo < 0 then error "L'importo non può essere negativo"
else saldo := saldo + importo
}
}
L'invariante del monitor in questo caso dice semplicemente che il saldo deve riflettere tutte le operazioni eseguite prima che un'altra operazione possa cominciare. Non si afferma nel codice può essere spiegato nei commenti. Il blocco viene aggiunto dal compilatore. Ciò rende i monitor più sicuri e affidabili delle tecniche che richiedono al programmatore di inserire a mano le operazioni di blocco e sblocco, siccome il programmatore se ne può dimenticare.
Le variabili condizione
modificaPer evitare il busy waiting, i task devono poter segnalarsi a vicenda gli eventi che li riguardano. I monitor forniscono questa funzionalità tramite le variabili condizione. Quando una procedura di monitor richiede che una particolare condizione sia vera prima di poter procedere, attende su una variabile condizione associata. Attendendo, abbandona il blocco e viene rimossa dall'insieme dei task pronti. Ogni task che in seguito rende vera la condizione può allora usare la variabile condizione per notificare la nuova situazione ai task in attesa sulla condizione. Un task che è stato notificato riottiene il blocco e può procedere.
Il seguente monitor usa le variabili condizione per implementare un canale di comunicazione tra task che può immagazzinare solo un intero.
monitor canale {
int contenuto
boolean pieno := false
condition invio
condition ricezione
function invia(int inviato) {
if pieno then wait(ricezione)
contenuto := inviato
pieno := true
notify(invio)
}
function ricevi() {
var int ricevuto
if not pieno then wait(invio)
ricevuto := contenuto
pieno := false
notify(ricezione)
return ricevuto
}
}
Si noti che siccome attendendo su una condizione si perde il blocco, l'attendente deve assicurarsi che l'invariante del monitor sia soddisfatta prima di attendere. Nell'esempio sopra, vale lo stesso per la notifica.
Nelle prime implemetazioni dei monitor, la notifica di una variabile condizione faceva sì che un task in attesa ricevesse il blocco e andasse immediatamente in esecuzione, garantendo così che la condizione rimanesse vera. Implementare questo comportamento è complicato e comporta un elevato appesantimento (overhead). Inoltre, è un comportamento incompatible con gli scheduler che possono interrompere un task in qualunque momento. Per queste ragioni, i ricercatori hanno preso in considerazione altre semantiche per le variabili condizione.
Nelle implementazioni più moderne, la notifica non porta via il controllo dal task in esecuzione, si limita a rendere pronto qualche task in attesa.
Il task notificante continua a tenere il blocco fino a quando abbandona la funzione di monitor.
Gli effetti collaterali di questa tecnica sono che il task notificante non deve far valere l'invariante del monitor prima di notificare, e il task in attesa deve fare una seconda verifica sulla condizione che stava aspettando.
Specificamente, if test then wait(cv) diventa while test do wait(cv). Le implementazioni forniscono anche un'operazione "notifyAll" che notifica tutti i task in attesa su una data condizione.
Questa operazione è utile, per esempio, quando più task stanno aspettando che diventino disponibili diverse quantità di memoria. Il rilascio della memoria può permettere ad alcuni task di procedere e ad altri no, ma lo scheduler non sa quali.
Esempi
modificaAdesso mostreremo qualche esempio di monitor per chiarire meglio le idee.
Questo primo esempio illustra come sia possibile simulare i semafori con un monitor.
Monitor Semaforo {
int s=0; //invariante che s>=0
condizione p; //si può fare la signal quando s>0
Procedure Psem() {
while(s==0)
wait(p);
s--;
}
Procedure Vsem() {
s++;
signal(p);
}
}
Con questo monitor non è assicurato il fatto che si abbia una coda di processi sulla condizione p del tipo w:FIFO (First-In-First-Out) se adottiamo una politica del tipo Signal-And-Continue. Mostriamo ora quest'esempio che illustra come sia possibile simulare un semaforo con coda FIFO con qualunque shedulatore.
Monitor Semaforo {
int s=0; //invariante che s>=0
condizione p; //si può fare la signal quando s>0
Procedure Psem() {
if(s==0) //se s=0 il processo viene messo in wait
wait(p);
else
s--;
}
Procedure Vsem() {
if(isEmpty(p)) //se non c'è nessun processo in wait su p si incrementa il semaforo
s++;
else //se vi sono processi in attesa su wait li andiamo a svegliare direttamente
signal(p);
}
}
Mostriamo ora un esempio del paradigma del Produttore-Consumatore.
Monitor Produttore-Consumatore {
int n; //dimensione del buffer;
int buffer[n]; //buffer di dimensione n
int celle_piene=0; //contatore che indica il numero di celle piene
int prima_cella_piena=0; //indica l'indice della prima cella piena
int prima_cella_vuota=0; //indica l'indice della prima cella vuota
condizione non_pieno; //si può fare la signal quando celle_piene<n
condizione non_vuoto; //si può fare la signal quando celle_piene>0
Procedure Produci(int el) {
while(celle_piene==n)
wait(non_pieno); //se il buffer è pieno si attende sino a quando è non_pieno
buffer[prima_cella_vuota]=el; //si deposita l'elemento el prodotto nel buffer
prima_cella_vuota=(prima_cella_vuota++)%n; //si incrementa l'indice della prima_cella_vuota
celle_piene++;
signal(non_vuoto); //si fa la signal su non_vuoto
}
Procedure int Consuma {
while(celle_piene==0)
wait(non_vuoto); //se il buffer è vuoto si attende sino a quando è non_vuoto
int el=buffer[prima_cella_piena];
prima_cella_piena=(prima_cella_piena++)%n; //si incrementa l'indice della prima_cella_piena
celle_piene--;
signal(non_pieno); //si fa la signal su non_pieno
return el;
}
}
Mostriamo adesso un esempio del paradigma Lettori-Scrittori. Prima di implementare il paradigma vogliamo ricordare che il monitor servirà semplicemente a stabilire se un processo può leggere (scrivere) o meno sul database. Non può controllare direttamente l'accesso al database in quanto implicitamente il monitor ha la mutua esclusione il che non permetterebbe la lettura del database da parte di più processi in simultanea.
Monitor Lettori-Scrittori {
int numero_lettori=0;
int numero_scrittori=0;
condizione posso_leggere;
condizione posso_scrivere;
Procedure Richiesta_Lettura {
if(numero_scrittori>0)
wait(posso_leggere);
numero_lettori++;
}
Procedure Rilascio_Lettura {
numero_lettori--;
if(numero_lettori==0)
signal(posso_scrivere);
}
Procedure Richiesta_Scrittura {
if(numero_lettori>0 or numero_scrittori>0)
wait(posso_scrivere);
numero_scrittori++;
}
Procedure Rilascio_Scrittura {
numero_scrittori--;
if(numero_scrittori==0) {
signal(possoScrivere);
signalToAllProcess(possoLeggere);
}
}
}
Storia
modificaPer Brinch Hansen fu il primo a descrivere e implementare i monitor, basandoli sulle idee di C. A. R. Hoare. Hoare successivamente ne sviluppò la teoria e ne dimostrò l'equivalenza ai semafori.
Tra i linguaggi di programmazione che supportano nativamente per i monitors ci sono:
Il linguaggio C# non ha i monitor come caratteristica del linguaggio, sebbene il framework .NET contiene una classe che facilita l'implementazione a mano di monitor analoghi a quelli di Java. Anche l'interfaccia pthreads di POSIX supporta l'implementazione di monitor.