Starvation - semaforo

[iL CaRDiNaLe]

salve

vi posto la traccia di un semplice programma java, nel caso potreste cortesemente darmi una mano:



Si vuole realizzare un sistema per controllare i semafori installati in un incrocio di 4 strade. Ogni direzione, fra N, S, E, O, è governata da un proprio semaforo e da un sensore di macchine in attesa di attraversare l'incrocio. Ogni semaforo, e il corrispondente sensore, è controllato da un client. In ogni momento uno solo dei quattro semafori può essere verde. Quando un semaforo passa da rosso a verde ci resta per 10 secondi. I quattro client sono collegati ad un server.

Scrivere il programma dei client per la gestione delle 4 direzioni, e il programma del server per la coordinazione dei client rispettando il seguente protocollo.

CLIENT
Un client può inviare al server i seguenti messaggi:
- CHIEDO_VERDE: per richiedere al server la possibilità di accendere la luce verde del semaforo che gestisce;
- DIVENTO_ROSSO: comunica al server che ha riacceso la luce rossa.

Se il client ad una richiesta di CHIEDO_VERDE riceve una risposta di ACK_VERDE, accende la luce verde, la tiene accesa per 10 secondi, quindi riaccende la luce rossa e lo comunica al server. (Utilizzare il metodo Thread.sleep(10) per creare un'attesa di 10 secondi).

SERVER
Il server quando riceve il messaggio CHIEDO_VERDE da un client può rispondere con:
- ACK_VERDE: se tutti i semafori in quel momento sono rossi;
- NACK_VERDE: se esiste già un semaforo con la luce verde accesa.

Il server, inoltre, memorizza per ogni direzione il numero di volte che è stata accesa la luce verde del corrispondente semaforo.

L’implementazione suggerita del semaforo può determinare situazioni di starvation (impossibilità da parte di alcuni semafori ad ottenere il verde). Spiegare perché, trovare una soluzione migliorativa ed implementarla.

Perchè si possono determinare situazioni di starvation?
Secondo voi quale potrebbe essere una soluzione migliorativa?

Grazie mille

[andbin]

Originariamente inviato da iL CaRDiNaLe
Perchè si possono determinare situazioni di starvation?

Dal momento che basta un semaforo già verde per dare NACK_VERDE a tutti gli altri .... un client "sfortunato" come tempistiche potrebbe non riuscire mai (o comunque per molto tempo) ad avere un ACK_VERDE perché gli altri client glielo "fregano".

Originariamente inviato da iL CaRDiNaLe
Secondo voi quale potrebbe essere una soluzione migliorativa?

Una "coda" che permetta di stabilire un ordine di attesa. Ma richiederebbe di (ri)valutare meglio il protocollo di comunicazione, perché con quello che hai detto (anche se non l'hai precisato) deduco che il NACK_VERDE venga dato dal server subito.
Se si mette una coda allora: o il client resta in attesa (in wait sul input dal server) per avere l'ok (in pratica non esiste più NACK_VERDE) oppure è il server che comunica al client in modo asincrono l'ok.

[iL CaRDiNaLe]

Salve

innanzitutto grazie mille per la risposta illuminante.

A questo link c'è la mia soluzione:
https://www.dropbox.com/sh/yokss21io...C3%A0/Semaforo

si tratta di una soluzione non migliorata e quindi con il protocollo descritto.

Per realizzare una soluzione utilizzando una coda, dato che ho poca conoscenza dei thread, come potrei implementarla?

[andbin]

Ho visto il tuo codice, purtroppo ci sono svariate cose che non vanno. Ti dico giusto quelle che sono più evidenti ed ho notato subito (dovrei analizzare tutto meglio ma non ho tanto tempo ora).

1) Quando si usano i socket TCP si dovrebbero sempre fare dei flush() per assicurarsi che i dati vengano davvero inviati. Nel tuo codice non ne ho visto neanche uno.

2) verificaStato va messo synchronized

3) Il wait in occupa() non va bene. wait va messo, parlando in generale, in un ciclo while che testa la condizione che deve "reggere" il concetto di attesa.

4) Anche ammettendo che tutto il resto sia corretto/appropriato, la parte:

if(incrocio.verificaStato() == 'L'){
    incrocio.occupa();
        // ......
}
else streamOut.writeChar('R');

non va bene e spiego anche il perché. Anche se verificaStato fosse synchronized, le due operazioni verificaStato e occupa sono sì "atomiche" prese singolarmente, ma l'insieme delle due no, non lo è. Cosa comporta? Che puoi avere una "race condition".

L'incrocio è libero, due thread cercano di occuparlo. Magari arrivano contemporaneamente a testare la condizione nel if. Per entrambi è "libero", ed entrambi entrano nel corpo del if. Siccome occupa è synchronized, solo il primo che riesce ad acquisire il lock occupa l'incrocio. L'altro thread (appena il primo esce da occupa) entra in occupa e va in wait. Insomma non invia subito 'R'.

In un'altra circostanza se un solo thread trova occupato, invia subito 'R'. Il tuo server si comporta diversamente a seconda delle tempistiche più o meno (s)fortunate dei thread.

E ripeto, ho solo indicato i problemi più evidenti.

[iL CaRDiNaLe]

Ho effettuate le correzioni indicate.

Il dubbio attuale è su come e dove creare la coda di richieste, in quanto ho modificato leggermente il protocollo: ora non invio più al semaforo il NACK_VERDE in caso di incrocio già occupato, ma il semaforo attende la disponibilità dell'incrocio.
Il problema è che anche attualmente si può verificare starvation, dato che dal wait set verrà eseguito un semaforo "a caso", giusto?

Il mio codice è al link seguente:
http://tinyurl.com/semaforo-v2

Grazie Mille per l'aiuto!