[Generale] Implementazione mutua esclusione tramite message passing

[Dani88]

Ciao a tutti
Sto cercando di capire come implementare l'accesso ad una zona critica contenente una o più risorse in modo che un solo processo per volta possa accedervi, ovvero la mutua esclusione come molti di voi sapranno
I processi devono però comunicare tramite messaggi e non con variabili condivise.

Supponendo di avere "n" processi P1..Pn, io al momento ho pensato una cosa del tipo:
- io Pi chiedo a tutti gli altri: "ho bisogno della risorsa è libera?"
- via via che rispondono gli altri n-1 processi, se rispondono
>> SI: gli dico "la prendo io, ora è occupata" in modo che ognuno sappia che serve a me
>> NO: rinuncio per ora ad entrare e mando un messaggio a tutti gli altri dicendo che ho abbandonato l'intenzione di entrare

Se riesco ad entrare (ovvero tutte risposte SI) quando esco mando un messaggio a tutti dicendo "ho finito, la risorsa è libera"

Forse la cosa potrebbe essere resa più semplice se ogni processo se qualcuno sta usando la risorsa (settando a true ad esempio) così quando chiedo ottengo subito un no dal primo processo che risponde.
Se invece ottengo un si dicendogli che voglio usarla io l'altro setta a true la variabile che dice se la risorsa è in uso.

Sto dicendo delle cavolate o il metodo potrebbe funzionare, magari un po rivisto per migliorare fairness e prestazioni?
Se qualcuno riuscisse a darmi due dritte mi farebbe un favore enorme
Grazie in anticipo a tutti!!

[marco.r]

Originariamente inviato da Dani88

Ciao a tutti
Sto cercando di capire come implementare l'accesso ad una zona critica contenente una o più risorse in modo che un solo processo per volta possa accedervi, ovvero la mutua esclusione come molti di voi sapranno
I processi devono però comunicare tramite messaggi e non con variabili condivise.

Supponendo di avere "n" processi P1..Pn, io al momento ho pensato una cosa del tipo:
- io Pi chiedo a tutti gli altri: "ho bisogno della risorsa è libera?"
- via via che rispondono gli altri n-1 processi, se rispondono
>> SI: gli dico "la prendo io, ora è occupata" in modo che ognuno sappia che serve a me
>> NO: rinuncio per ora ad entrare e mando un messaggio a tutti gli altri dicendo che ho abbandonato l'intenzione di entrare

Se riesco ad entrare (ovvero tutte risposte SI) quando esco mando un messaggio a tutti dicendo "ho finito, la risorsa è libera"

Forse la cosa potrebbe essere resa più semplice se ogni processo se qualcuno sta usando la risorsa (settando a true ad esempio) così quando chiedo ottengo subito un no dal primo processo che risponde.
Se invece ottengo un si dicendogli che voglio usarla io l'altro setta a true la variabile che dice se la risorsa è in uso.

Sto dicendo delle cavolate o il metodo potrebbe funzionare, magari un po rivisto per migliorare fairness e prestazioni?
Se qualcuno riuscisse a darmi due dritte mi farebbe un favore enorme
Grazie in anticipo a tutti!!

Non so se e' il tipo di soluzione che stai cercando, cmq io vedrei piu' "naturale" dedicare un processo alla gestione della risorsa condivisa. L'accesso viene regolato mandando al processo gestore dei messaggi , che verranno smaltiti sequenzialmente.
Il contenuto del messaggio puo' essere l'operazione da effettuare sulla risorsa condivisa e il mittente, il risultato (se c'e') verra' mandato indietro in modo analogo.

[Dani88]

Eh non posso farlo in quel modo li purtroppo, avevo letto tale implementazione però non posso farlo con un gestore della risorsa.
Si in questo caso avrei un "master" che dice a tutti gli altri processi se la risorsa è disponibile o meno, però io devo implementarlo solamente con i i processi diciamo tutti "uguali", non deve esserci un master...

[Dani88]

Nessuno sa come si possa fare?
Pensando a quanto avevo descritto sopra potrebbe esserci un problema di sincronizzazione iniziale con possibile rischio di starvation forse...

[PGI-Bis]

il discorso è lungo e noioso ma per farla breve - ma non divertente - il punto della mutua esclusione è l'esistenza di un ordine parziale tra le operazioni di accesso.

L'idea di inviare una prenotazione a tutti gli altri in tanto funziona in quanto tu sia in grado di stabilire che tra N prenotazioni incrociate tutte occorrenti nel medesimo istante una prevarrà sulle altre.

La regola in base a cui determini questa prevalenza ti da poi la misura di fairness e liveness ma questi arrivano dopo.

Su quali basi tu possa creare questa regola dipende dal tuo protocollo. Ad esempio puoi stabilire che i processi abbiano un id numerico e dire che le richieste proveniente da un processo di ID maggiore prevalgono sempre sulle altre. Funziona ma non è "fair". Allora potresti dire che ogni prenotazione ha un ID e un tempo e la priorità è determinata dall'antecedenza temporale o dal valore dell'ID quando la prima sia identica.

[Dani88]

Dunque si i processi hanno un loro id, ovvero posso sapere il PID, però come dicevi dare la priorità ad alcuni non garantisce un comportamento fair sulla risorsa condivisa.

Ho trovato leggendo su internet, la gestione tramite token, ovvero chi ha il token può accedere alla rirsorsa condivisa, poi lo passa ad un altro...
Questo potrebbe funzionare, mi sembra anche a livello di fairness, o sbaglio?

[PGI-Bis]

Può essere una soluzione valida. A seconda di come comunicano i tuoi processi potrebbe tuttavia essere un macigno per la liveness - il biglietto non usato deve circolare rapidamente.