Semafori

[Edde]

Ciao

Devo fare questo programma sotto linux:

---------------------------------------------------------
Gioco del Tris (versione peer-to-peer)

Realizzazione di una versione elettronica del famoso "gioco del
Tris". In questa versione due processi (ognuno dei quali funge da
interfaccia con uno dei due giocatori) cooperano tra loro. Per prima
cosa decidono quale dei due processi deve iniziare (il meccanismo di
decisione e' lasciato alla discrezione dello studente), poi si accetta
come input una mossa, la si trasmette al secondo processo, e ci si
pone in attesa di una mossa da parte del secondo processo. Entrambi i
processi, ogni volta che ricevono una mossa (sia dal loro giocatore
che dall'altro processo) valutano se uno dei due giocatori ha vinto e
lo riferiscono al loro giocatore. Il canale di comunicazione tra i due
processi deve essere implementato tramite l'uso di memoria condivisa.
------------------------------------------------------------

La mia idea e' stata quella di usare 2 semafori binari (A =1 e B=0)

Il giocatore1 fa la wait su A, e alla fine la signal(B).
Il giocatore2 fa wait(B) e alla fine signal(A).

Questo per garantire non solo la mutua esclusione, ma anche l'alternaza stretta nell'accesso alla memoria.

Credo di aver fatto bene (anche perche' funziona), ma non sono convintissimo.
Pareri?

Grazie in anticipo a chi rispondera'

[cionci]

Dovrebbe andare bene...
In questo modo quando A è in azione B è fermo e viceversa...
E' come avere una coda produttore-consumatore di 1 elemento...

[mjordan]

Certo che se ogni volta devi sincronizzare due processi con dei semafori staremmo freschi. Io per esempio avrei usato delle pipe... Fin quando scrivi dati inferiori o uguali a PIPE_BUF come dimensione, non devi preoccuparti della sincronizzazione. Se poi l'esercizio chiedeva esplicitamente l'uso dei semafori è altro conto.

[fedo]

leggendo l'ultima riga del testo dell' esercizio ti consiglio di usare una di queste, NON i semafori (come ti ha fatto notare anche mj):

-Libreria MM Shared Memory
-MMap con flag per la memoria condivisa (non ricordo quale è)


sono due soluzioni molto semplici, la seconda soprattutto (però la prima è + performante)..

ciao

[Edde]

Grazie a tutti

Il fatto e' che noi, per quanto riguarda la comunicazione tra processi, abbiamo fatto solo mem condivisa, semafori e code di msg, e tutto in maniera abbastanza semplice (per un totale di una decina di chiamate di sistema).

Sinceramente le pipe non so neanche cosa siano

Il testo dell'esercizio e' quello li, e non chiede in maniera specifica di usare i semafori. Pero' alla fine si tratta di garantire mutua esclusione su quell'area di memoria, e mi e' sembrato naturale usare i semafori per farlo

Cmq, nell'ipotesi che si debbano usare i semafori, la soluzione che ho adottato e' corretta o si puo' fare di meglio?

Vi ascolto

[cionci]

Originariamente inviato da Edde
Cmq, nell'ipotesi che si debbano usare i semafori, la soluzione che ho adottato e' corretta o si puo' fare di meglio?

E' corretta...anche se basterebbe una mutex...

[mjordan]

Originariamente inviato da cionci
E' corretta...anche se basterebbe una mutex...

Anche perchè "semafori" e "mutex" sono la stessa cosa ...

[cionci]

Originariamente inviato da mjordan
Anche perchè "semafori" e "mutex" sono la stessa cosa ...

Sì, diciamo che il semaforo è una mutex generalizzata...ma ad esempio in Windows ci sono strutture diverse per i semfori e per le mutex...
La mutex serve per gestire un solo accesso ad una sola risorsa...mentre il semaforo risorse multiple, o accessi multipli alla stessa risorsa...

[mjordan]

Originariamente inviato da cionci
Sì, diciamo che il semaforo è una mutex generalizzata...ma ad esempio in Windows ci sono strutture diverse per i semfori e per le mutex...
La mutex serve per gestire un solo accesso ad una sola risorsa...mentre il semaforo risorse multiple, o accessi multipli alla stessa risorsa...

Concettualmente è sbagliato perchè con MUTEX nella letteratura classica accettata universalmente si indica una qualsiasi variabile semaforo condivisa fra N processi al fine di ottenere la sincronizzazione mutualmente esclusiva ...
Ecco perchè "accessi multipli ad una risorsa" con la parola MUTualEXclusion non va molto d'accordo...

Mah

[cionci]

Originariamente inviato da mjordan
Concettualmente è sbagliato perchè con MUTEX nella letteratura classica accettata universalmente si indica una qualsiasi variabile semaforo condivisa fra N processi al fine di ottenere la sincronizzazione mutualmente esclusiva ...
Ecco perchè "accessi multipli ad una risorsa" con la parola MUTualEXclusion non va molto d'accordo...

L'unica mutua esclusione presente nell'uso di un semaforo è quella sulla variabile che tiene il conteggio...
Io stavo dicendo PER COSA SI USANO i semfori e non PERCHé FUNZIONANO...
Parlo di accessi multipli ad una sola risorsa in questo senso:

Risorsa r;
Semaforo s(N);

s.wait();
r.uso();
s.signal();

All'istante /t all'interno di Risorsa::uso() ci possono essere un massimo di N processi...
Che poi uso tratti la mutua esclusione alle sue risorse come gli pare è un'altro discorso... Di fatto fra la wait e la signal ci sono N processi... Se il numero di processi in esecuzione sono M...M-N processi possono essere in attesa sulla wait...

[Edde]

Al di la delle disquisizioni filosofiche, non ho ben capito in che modo sia possibile usare un solo semaforo binario... In pratica entrambi i processi dovrebbero fare wait e signal sullo stesso semaforo?

A dire la verita' ci avevo provato, ma poi i 2 processi non entravano in sezione critica in alternanza stretta: il primo che entrava teneva sotto controllo la memoria fino alla sua morte (faceva la signal sul semaforo e subito dopo la wait sullo stesso: in pratica era assolutamente indipendente dall'altro e faceva un po' quello che voleva). Il secondo processo riusciva ad eccedere alla memoria solo dopo la morte del primo...

E' li che mi e' venuta l'idea di usarne 2, in modo tale da impredire completamente che uno potesse andare avanti prima che l'altro avesse fatto quello che doveva: anche perche' alla fine, e' dalle scelte di scheduling che dipende chi andra' avanti: se un processo e' in grado di continuare da solo, chi mi garantisce che venga mantenuta l'alternanza stretta?

[cionci]

Originariamente inviato da Edde
A dire la verita' ci avevo provato, ma poi i 2 processi non entravano in sezione critica in alternanza stretta: il primo che entrava teneva sotto controllo la memoria fino alla sua morte (faceva la signal sul semaforo e subito dopo la wait sullo stesso: in pratica era assolutamente indipendente dall'altro e faceva un po' quello che voleva). Il secondo processo riusciva ad eccedere alla memoria solo dopo la morte del primo...

E' li che mi e' venuta l'idea di usarne 2, in modo tale da impredire completamente che uno potesse andare avanti prima che l'altro avesse fatto quello che doveva: anche perche' alla fine, e' dalle scelte di scheduling che dipende chi andra' avanti: se un processo e' in grado di continuare da solo, chi mi garantisce che venga mantenuta l'alternanza stretta?

Nono....hai fatto bene così...intendevo due mutex al posto dei semafori... Una mutex è in effetti identica ad un semaforo binario...

[mjordan]

Ho capito ma quello che ti chiedevo prima è dove distingui il termine MUTEX dal termine SEMAFORO. O meglio (forse non mi sono spiegato bene) la differenza fra un SEMAFORO e un SEMAFORO MUTEX. . .

[cionci]

No...io non distinguo SEMFOFRO da SEMAFORO MUTEX...distinguo SEMAFORO da MUTEX...
Nel senso che per come l'abbiamo fatta noi...mutex è un caso particolare del semaforo...cioè il semaforo binario...
Non sono solamente io a fare questa distinzione...come già detto, su Windows esistono le API CreateMutex e CreateSemaphore...

[mjordan]

Ohhh... Vedi allora che avevo capito bene ... Il SEMAFORO MUTEX varia in uno spazio non logicamente definito. Ecco perchè è anche detto semaforo contatore ... Il semaforo binario non è la stessa cosa. Difatti i semafori binari hanno come valori esclusivamente i valori 0 e 1. Ma forse queste sono distinzioni prettamente accademiche:

SEMAFORO -- Variabile generica usata per sincroinizzare processi.
SEMAFORO MUTEX -- Semaforo in cui la variabile varia in uno spazio non definito. Detto anche spinlock perchè fa assumere alla macchina una condizione di busy waiting, laddove potrebbe impiegare il lavoro necessario per effettuare altri compiti.
SEMAFORO BINARIO -- Semaforo i cui valori sono esclusivamente 0 e 1. Dal binario è possibile implementare il MUTEX. Non presenta busy waiting, quindi niente spinlock.
MONITOR -- Arcana strategia implementata sul principio dei semafori per determinare la sezione critica di un processo.

Di chiu nin zo

[recoil]

Originariamente inviato da mjordan
MONITOR -- Arcana strategia implementata sul principio dei semafori per determinare la sezione critica di un processo.

da programmatore java dico: w i monitor

[mjordan]

Originariamente inviato da recoil
da programmatore java dico: w i monitor

Meglio se CRT, quelli TFT non mi fanno poi così impazzire

[Edde]

Riposto la specifica:

---------------------------------------------------------
Gioco del Tris (versione peer-to-peer)

Realizzazione di una versione elettronica del famoso "gioco del
Tris". In questa versione due processi (ognuno dei quali funge da
interfaccia con uno dei due giocatori) cooperano tra loro. Per prima
cosa decidono quale dei due processi deve iniziare (il meccanismo di
decisione e' lasciato alla discrezione dello studente), poi si accetta
come input una mossa, la si trasmette al secondo processo, e ci si
pone in attesa di una mossa da parte del secondo processo. Entrambi i
processi, ogni volta che ricevono una mossa (sia dal loro giocatore
che dall'altro processo) valutano se uno dei due giocatori ha vinto e
lo riferiscono al loro giocatore. Il canale di comunicazione tra i due
processi deve essere implementato tramite l'uso di memoria condivisa.
------------------------------------------------------------


Devo consegnare il programma il 17. Facendo gli ultimi ritocchi, mi e' caduto l'occhio sulla frase in neretto e mi e' venuto un dubbio atroce.....

Nella mia implementazione c'e' un processo padre (che si occupa delle inizializzazioni) e che a un certo punto crea 2 figli: il primo chiama la funzione "giocatore1", il secondo quella "giocatore2"....
Prima di fare questo chiede il nome ai due giocatori e, in maniera casuale, decide quale nominativo associare a "giocatore1" e quale invece a "giocatore2".

In questo modo, dall'esterno, sembra effettivamente che l'ordine con cui i due giocatori iniziano sia casuale, mentre in realta' il primo figlio giochera' sempre per primo, l'altro sempre per secondo...
Senza contare che tutto questo viene fatto dal padre e non, come sembrerebbe da quella frase, dai 2 processi che cooperano tra di loro....

Insomma, non sono sicuro che sia giusto il mio approccio (c'e' sempre la frase "il meccanismo di decisione e' lasciato alla discrezione dello studente", che potrebbe parzialmente pararmi le chiappe) e non ho neanche grandi idee per modificarlo....

Che ne pensate?
Vi preeeeeeego......