Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Domenico Cotroneo » 13.Il costrutto Monitor


Il costrutto Monitor

Sommario

  • Il tipo Monitor: struttura e strategie di controllo
    • Monitor signal and wait
  • La soluzione di Hoare
  • Monitor signal and continue

Introduzione

Il monitor è un costrutto sintattico che associa un insieme di operazioni a un struttura dati (risorsa) comune a più processi.

E’ stato introdotto per facilitare la programmazione strutturata di problemi in cui è necessario controllare l’assegnazione di una o più risorse tra più processi concorrenti mediante apposite discipline di gestione.

Il costrutto Monitor è sintatticamente del tutto analogo al costrutto di class ma, mentre quest’ultimo viene utilizzato per definire tipi di risorse dedicate…

..il monitor viene utilizzato per definire tipi di risorse condivise.

Struttura di un TDA Monitor

Si configura come un “tipo di dato astratto”, in cui

  • le variabili membro (private), dette anche variabili locali, descrivono lo stato della risorsa controllata dal monitor;
  • le funzioni membro pubbliche costituiscono le uniche operazioni utilizzabili dai processi per “disciplinare” l’accesso alle variabili membro;
  • funzioni membro private, non invocabili dall’esterno.

Strategie di controllo

Lo scopo è quello di controllare l’assegnazione di una risorsa tra processi concorrenti in accordo a determinate politiche di gestione, secondo due livelli di controllo:

  1. un solo processo alla volta abbia accesso alle variabili locali;
  2. una disciplina di scheduling che stabilisca l’ordine con il quale i processi hanno accesso alla risorsa.

Separazione tra meccanismi e politiche!

Strategie di controllo

Al fine di garantire che un solo processo alla volta abbia accesso alle variabili locali, si impone che

  • le funzioni di accesso al monitor vengano eseguite in modo mutuamente esclusivo;
  • i processi che invocano una funzione di un oggetto monitor mentre un altro processo è attivo nell’istanza, devono essere ritardati.

Strategie di controllo

Al fine di garantire una disciplina che stabilisca l’ordine di accesso alla risorsa

  • l’ordinamento può essere ottenuto imponendo che un processo acceda alle variabili locali di un’istanza del monitor solo se è soddisfatta una condizione logica che assicura l’ordinamento stesso;
  • nel caso in cui ciò non si verifichi il processo viene sospeso, in modo da consentire ad un altro processo di accedere all’istanza.

Strategie di controllo (2.1)

La sospensione di un processo nel caso in cui la condizione non sia verificata, avviene utilizzando un nuovo tipo di variabile, detta variabile di tipo condition.

var_cond x;
x.wait;

…provoca la sospensione del processo fino a che un altro processo esegue x.signal;

NB: se non vi è alcun processo in attesa sulla variabile x, la signal non ha alcun effetto.

Semantiche dell’operazione signal

Sia P un processo sospeso su una variabile condition x e Q il processo che esegue la signal su tale variabile.

Proprietà del monitor violate!

Uno dei due processi deve essere pertanto sospeso.


Prima soluzione: signal and wait

Signal_and_wait prevede che il processo P risvegliato riprenda immediatamente l’esecuzione e che Q venga sospeso.

Q viene sospeso per evitare che possa modificare nuovamente la condizione di sincronizzazione.


La soluzione di Hoare

E’ un caso particolare della signal_and_wait, denominata signal_and_urgent_wait.

Prevede che il processo Q abbia la priorità su ogni altro processo che intende entrare nel monitor.

Ciò si può ottenere sospendendo il processo Q su un’apposita coda (urgent_queue).

Uso della primitiva wait

La semantica signal_and_wait privilegia il processo segnalato rispetto al segnalante.

Ciò implica che il segnalato, proseguendo la sua esecuzione, è certo di trovare vera la condizione per la quale è stato risvegliato.

Quindi lo schema tipico dell’invocazione di una wait è all’interno di un if:

if (!B) cond.wait(); //B è la condizione di sincronizz.

<accesso alla risorsa>

Seconda soluzione: signal and continue

Signal_and_continue (detto anche wait and notify) privilegia il processo segnalante rispetto al segnalato. Il processo Q segnalante prosegue la sua esecuzione, mantenendo l’accesso esclusivo al monitor, dopo aver risvegliato P.

Q prosegue l’esecuzione dopo aver risvegliato P.


Signal and continue

Il processo P segnalato viene trasferito alla coda associata all’ingresso del monitor.

Poiché in questa coda possono esistere altri processi, questi possono precedere l’esecuzione di P e quindi modificare il valore della condizione di sincronizzazione.

P dovrà pertanto testare nuovamente la condizione di sincronizzazione prima di proseguire.

Quindi, con una politica signal_and_continue lo schema tipico di uso della primitiva wait è all’interno di un while

while (!B) cond.wait()

<accesso alla risorsa>

La soluzione proposta può dar luogo ad inutili ripetute valutazioni della condizione di sincronizza., tuttavia elimina la complessità realizzativa insita nella politica signal_and_wait.

Signal and continue: signal_all

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.

Realizzazione di un tipo Monitor

Sono due le problematiche da risolvere:

  • accesso in mutua esclusione alle funzioni del monitor;
  • gestione delle politiche di sospensione e riattivazione dei processi sulle variabili condition (ci riferiremo alla soluzione di Hoare, sebbene non sia l’unica proposta in letteratura).

1) Accesso in mutua esclusione alle funzioni del monitor

Può essere semplicemente ottenuto associando ad ogni istanza del monitor un semaforo mutex inizializzato ad 1.

La richiesta di utilizzare il monitor equivale all’esecuzione di una wait(mutex);

Tale richiesta è nota con il termine di “ingresso al monitor”.

2) Sospensione/Attivazione Processi (soluzione di Hoare)

L’esigenza di garantire ai processi sospesi, non appena riattivati, la immediata ripresa della procedura interrotta, comporta la sospensione del processo che ha eseguito la signal sulla variabile condition.

Viene quindi introdotto un semaforo urgent (inizializzato a 0) sul quale i processi che hanno eseguito la signal si sospendono tramite una wait(urgent).

Prima di abbandonare il monitor è quindi necessario verificare che nessun processo sia in coda a tale semaforo.

Condizione di uscita di un monitor

Indicando con urgentcount un contatore (inizializzato a 0) del numero di processi sospesi sul semaforo urgent, l’uscita da una funzione del monitor sarà:

if (urgentcount>0)

signal(urgent);

else

signal(mutex);

Realizzazione di una var. condition

 CondVar

__________________________

 -condsem=0: semaphore
-condcount=0: int

__________________________
+wait()
+signal()

Signal_and_wait


Signal_and_urgent_wait


Signal_and_continue


Signal_and_return

Nell’ipotesi in cui la signal sia sempre eseguita come ultima operazione, è possibile una soluzione più semplice …

wait(){

condcount++;
signal(mutex);
wait(condsem);
condcount--;

}

signal(){

if (condcount>0)

signal(condsem);

else

signal(mutex);

}

I materiali di supporto della lezione

W. Stallings, “Operating Systems : Internals and Design Principles (6th Edition) ”, Pearson Education (Par. 5.5)

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion