28) Quali
protocolli di sincronizzazione con uso dei clock logici vengono usati?
Requisiti:
un insieme di N processi che devono accedere ad una risorsa
singola in mutua esclusione.
- la risorsa deve essere assegnata ad un processo per volta,
che la rilascia alla fine dell'uso.
- richieste diverse devono essere servite in ordine.
Protocollo di sincronizzazione con uso dei
clock logici:
Assunzioni:
- messaggi diversi da un processo ad un altro devono arrivare
nell'ordine di generazione.
- i messaggi possono essere ritardati ma non persi.
- la connessione tra i processi è completa e diretta.
Ogni processo ha una coda locale dei messaggi,
a cui i messaggi sono accodati, che contiene inizialmente, per tutti i processi,
il messaggio T0:P0, inferiore di ogni clock del sistema.
Azioni
- il processo Pi manda il messaggio Tm:Pi ad ogni altro processo
(anche alla propria coda) per segnalare l'intenzione di accedere alla risorsa.
- alla ricezione del messaggio Tm:Pi il processo Pj (nella
propria coda) invia una risposta con il proprio timestamp.
- la risorsa è data al processo Pi se sono verificate
le condizioni:
- c'è una richiesta Tm:Pi nella sua coda delle richieste
ordinata prima di ogni altra (relazione )
- il processo Pi ha nella sua coda delle richieste un messaggio
da ogni altro processo con Timestamp superiore a Tm
- il rilascio avviene rimuovendo il messaggio dalla propria
coda e inviando un messaggio di rilascio con il proprio timestamp ad ogni
processo
- un processo Pj riceve la richiesta di rilascio e rimuove
il messaggio di richiesta dalla propria coda
L'algoritmo è un algoritmo con nessuna
centralizzazione, è completamente distribuito.
Il numero di messaggi è 3 *
(N-1) per ogni azione sulla sezione critica.
Altro protocollo
di sincronizzazione con uso dei clock logici:
Azioni:
- il processo Pi manda il messaggio di richiesta ad ogni
altro processo per accedere alla risorsa
- alla ricezione del messaggio Tm:Pi il processo Pj invia
- un reply immediato se non necessita la risorsa o il richiedente
ha priorità superiore alla sua
- un reply ritardato se sta usando la risorsa
ci sono quindi N-1 messaggi dal richiedente ed N-1 da tutti
gli altri, per un totale di 2 * (N-1) per ogni azione sulla sezione critica
L'algoritmo è completamente distribuito
libero da deadlock a da starvation.
Problemi
- tolleranza ai guasti.
- necessità di conoscenza reciproca .