CN29

29) Quali protocolli di sincronizzazione con uso di token vengono usati?

Protocollo con Token che circola tra i processi membri.

Solo chi ha il token può entrare nella sezione critica

Architettura ad Anello logico (Ring): ogni processo è organizzato con un precedente ed un successivo

Chi riceve il token:

verifica che sia diretto a lui.
eventualmente lo usa.
si prepara ad indirizzarlo al successivo.

Un solo processo accede alla risorsa, quindi non è possibile starvation, se il ring viene percorso in un verso solo.

Numero di messaggi N-1 per il passaggio del token.

Se ogni processo può tenere il token solo per un intervallo limitato (si fissa il massimo), il ricevimento del token avviene entro un tempo predefinibile dipendente solo da N

Guasti: un guasto può fare perdere il token, quindi si vuole evitare la situazione senza token o con più di un token circolante.

Ne è derivato un protocollo che fa uso del concetto di elezione. Un’elezione è una procedura che ha lo scopo di scegliere un unico processo da un gruppo, per esempio per assumere il ruolo di processo che rigenera il token:

Ogni nodo ha un timer, con un tempo di attivazione che dipende dal numero dei nodi (N) e dal tempo di permanenza massimo del token per nodo. Il timer viene attivato quando il token è inviato al vicino.
Al risveglio, il processo P crea un token di elezione (ET) con il nome del processo ed entra in stato di elezione
se P riceve il normale token prima che l'ET generato sia tornato, l’elezione era inutile (non c’è bisogno di rigenerare il token) ed è terminata (ET distrutto al ritorno)
se ogni altro processo riceve un ET, lo registra in una lista di elezioni, insieme con l'identità del processo che l'ha generato e lo passa nel ring, ma se aveva già generato un token ET ne verifica la priorità statica assunta
se P riceve il suo ET ancora in fase di elezione, lo rimuove e verifica la lista di registrazione: P genera il nuovo token, se P è il nodo di indice minimo (priorità) nella lista di registrazione

Il massimo del tempo di rigenerazione del token può essere calcolato, controllando anche i vicini, per non incorrere in blocchi

Sequencer: il token può anche portare un distributore di indicatori di ordinamento (ticket)

I ticket rappresentano un modo di ordinare in modo globale tutti gli eventi nel sistema: ticket (S) ritorna al chiamante un valore intero, e poi incrementa il sequenziatore.

il sequencer è spesso usato con EVENTCOUNT. Oggetto astratto per garantire l'ordinamento direttamente ai processi, senza passare attraverso la mutua esclusione. Tenendo conto degli eventi rilevanti nel sistema

primitive

advance(E): aumenta il valore dell'oggetto E. Il processo che ha fatto la advance diventa il segnalante
read(E): riporta il valore dell'oggetto E
await(E, v): sospende il processo che la esegue finché il valore di E raggiunge v

Le primitive possono avvenire insieme: una advance può avvenire insieme con read, quindi le read possono riportare il valore precedente o successivo.

Non si usa mutua esclusione

esempio di sincronizzazione:

valore iniziale di E = 0

Processo A Processo B

<sezione 1> await (E,1); poiché E=0, B aspetta che E diventi 1

advance(E); <sezione B> A ha finito e porta E=1; B può sbloccarsi

esempio di sincronizzazione : problema del produttore e del consumatore, buffer lungo N, due contatori (IN, OUT):

Processo Produttore Processo Consumatore

for i=1 by 1 do begin for i=1 by 1 do begin

await (OUT, i-N); await (IN, i);

produci(buff [ i mod N]); consuma(buff [ i mod N]);

advance (IN); advance (OUT);

end; end;

non ci sono problemi per la realizzazione in memoria condivisa, ma nel distribuito, con message passing, ci possono essere ritardi di comunicazione sui nuovi valori, con possibili advance contemporanee. Comunque esistono implementazioni nel distribuito.

Back

Index