problema dei 5 giocatori in C [Archivio]

paplo

11-04-2002, 15:43

Ciao,

sto cercando di risolvere il seguente problema in C ...

"
Si realizzi mediante thread e sincronizzazione con semafori un processo che
simula 5 giocatori, seduti ad un tavolo circolare, che giocano a carte. Si
supponga a questo proposito di avere un mazzo di 40 carte, la cui estrazione
sia ottenuta per mezzo di un generatore pseudocasuale. Il gioco consiste
nell'assegnare, durante la prima mano, una carta a testa per giocatore da
porre alla sua destra. Un giocatore per poter giocare la sua mano deve poter
disporre di entrambe le carte, alla sua destra e alla sua sinistra
(quest'ultima assegnata al giocatore sinistro). Se sono disponibili le
preleva (per cui non possono essere utilizzate contemporaneamente dai
giocatori che gli stanno accanto) e, quindi, estraendo una carta dal mazzo
ne fa la somma (modulo 40) con le due carte prelevate ai suoi lati e le
ripone sul tavolo. Si simuli la partita per un certo numero di mani.
"

Il problema è molto simile a quello dei 5 filosofi, e su questo problema mi sono basato per trovare una soluzione, ma il programma non funziona ancora.

per questo lancio un SOS.
quale l'errore nel listato e l'eventuale soluzione ???
(il listato è in allegato)

Vi ringrazio per qualsiasi aiuto mi vogliate dare!

Ciao e grazie,
Paplo

MickMacello

11-04-2002, 20:55

non mi è ben chiaro il funzionamento del gioco.

paplo

12-04-2002, 08:26

cosa non capisci???

cosa devono fare i giocatori !?

spero che le righe seguenti ti possano far capire ...
(se ti può consolare, neanche io capisco il prof! :D)

"Questo esempio è una variante del problema dei cinque filosofi che, nel caso in esame, può ribattezzarsi nel problema dei cinque giocatori. Ogni giocatore,
se lo può fare, prende la propria carta e quella del vicino e le sostituisce con le loro somme successive modulo Cards essendo Cards + 1 il numero di carte del
mazzo."

Ciao,
Paplo

a2000

12-04-2002, 10:33

solo in C eh ?

MickMacello

12-04-2002, 13:15

Esistono librerie fortran per scrivere programmi multiprocesso ?

/\/\@®¢Ø

12-04-2002, 15:40

L'errore che commetti e' che quando vuoi far prendere le carte al giocatore usi due wait.

In pratica il giocatore prende la prima carta , se non c'e' aspetta, quando ce l'ha prende la seconda , e se non c'e' aspetta.

Di conseguenza per come l'hai impostato tu, ogni giocatore prima prende la carta alla sua destra ( ad esempio ), e poi aspetta in eterno che il suo vicino molli la propria.

Cosa che non accadra' mai

Quindi devi prima limitarti a controllare se la carta e' disponibile , se non lo e' rinunciare, e se invece non lo e' prenderla. Stessa cosa per la seconda. Se riesce a pescarle tutte e due gioca, altrimenti molla l'eventuale carta presa e finisce il proprio turno

Non so il nome della funzione da invocare al posto di wait.
Con i pthread_mutex se non sbaglio c'e' la funzione pthread_mutex_trylock(), nel tuo caso probabilmente si chiamera' trywait()

paplo

12-04-2002, 17:11

ho indagato per trovare l'errore, e l'ho trovato ....

in pratica sbagliavo quando richiamavo LEFT e RIGHT.
la giusta sintassi infatti è LEFT(i) e RIGHT(i).

dopo aver risolto questo problema, ne abbiamo incontrati altri che abbiamo superato.

adesso il programma restituisce qualcosa, ma qualcosa che non è esatta.
infatti tutti i giocatori accedono al mazzo contemporaneamente e pescano la stessa carta.

penso che il problema sia il wait come dice /\/\@®¢Ø .

allego il listato modificato.
vi ringrazio se potete darci un'occhiata.

Ciao,
Paplo.

paplo

12-04-2002, 17:12

bè ... l'ho allego qui ....

paplo

12-04-2002, 17:16

Originariamente inviato da a2000
[B]solo in C eh ?

sì!!!!!

non in FCA o FORTRAN !!! :D

paplo

12-04-2002, 17:18

Originariamente inviato da /\/\@®¢Ø
[B]Quindi devi prima limitarti a controllare se la carta e' disponibile , se non lo e' rinunciare, e se invece non lo e' prenderla. Stessa cosa per la seconda. Se riesce a pescarle tutte e due gioca, altrimenti molla l'eventuale carta presa e finisce il proprio turno

ma se i giocatori a sinistra e a destra fossero più veloci del giocatore al centro, il giocatore al centro non giocherebbe mai?!

Ciao e grazie,
Paplo

/\/\@®¢Ø

12-04-2002, 18:37

Ah, devono giocare per forza in un dato turno ?
Io pensavo che semplicemente chi puo' gioca e gli altri "s'attaccano" :D
Un modo naïve può essere quello , con l'algoritmo che ti ho delineato, di continuare a provare fino a che uno non riesce a giocare:
Aspetta la prima carta ( qui va bene il wait ), e cerca poi di prendere la seconda ( trywait o quel che è ): se ce la fa gioca, altrimenti rimetti giu' la carta e riprova. Il discorso fondamentale è che o prendi su entrambi le carte o le lasci giu', non puoi tenerti in mano una sola carta e aspettare che si liberi la seconda, altrimenti non si riesce a giocare.
( sempre che abbia capito correttamente il gioco of course )

/\/\@®¢Ø

12-04-2002, 18:58

tanto per capirsi pensavo ad una cosa simile :

void take_cards(int i) /* i= numero del filosofo, 0.. N-1 */
{
bool ok=false;
while( ! ok )
{
if (i == 0){
wait(s[RIGHT(i)]);
printf("Il giocatore %d prende la carta destra.\n", i+1);
if ( trywait(s[LEFT(i)]) ) // controlla come funziona questo !
{
ok = true;
sleep(1); // simula una presa lenta per simulare il deadlock
}
else // la seconda carta non e' disponibile, rimettiamo a posto la prima e riproviamo
signal( s[RIGHT(i)]);

}
...

in questo caso ho ipotizzato che la trywait ritorni TRUE ( non zero ) se riesce a bloccare il semaforo, FALSE altrimenti, dovresti controllare in realta' se e' cosi' o meno

paplo

12-04-2002, 19:40

/\/\@®¢Ø, avevi capito bene prima.

questa mattina ho chiesto al prof. e in sostanza che prima arriva meglio alloggia.
cmq. è più semplice far saltare il turno ad un giocatore che tenere conto dellle mani, non è vero!?

cmq. nella prima soluzione che hai proposto sono superflui i semafori.
ovvero è neccessario soltanto un array che memorizzi gli stati delle carte.
ho inteso bene?

Ciao e grazie,
Paplo

/\/\@®¢Ø

12-04-2002, 20:40

No ! I semafori ti servono proprio per accedere a quell'array in modo sincronizzato.

Mi spiego meglio:
Supponiamo che nell'array tu memorizzi 1 se la carta e' disponibile 0 altrimenti. Se memorizzi solo lo stato puo' succedere che due giocatori cerchino di prendere la stessa carta contemporaneamente o quasi, ad esempio A vede 1 e decide di prendere la carta, in quel momento la cpu passa a B che vede anche lui 1, si ritorna ad A che imposta il valore a 0 ( si prende la carta ) , e la cpu ritorna a B che fa lo stesso. Due persone con la stessa carta in mano.
Se invece del contatore usi il semaforo ( che non e' altro che un contatore sincronizzato ) dopo che A "blocca" il semaforo ( la puoi considerare come una operazione "indivisibile" ) B si vede subito 0 e quindi non puo' prendersi la carta.
Spero di non averti confuso le idee ancora di piu' :)

a2000

12-04-2002, 22:33

Originariamente inviato da paplo
[B]

sì!!!!!

non in FCA o FORTRAN !!! :D

e in Excel ? :p

a2000

12-04-2002, 22:49

Originariamente inviato da MickMacello
[B]Esistono librerie fortran per scrivere programmi multiprocesso ?

disponibili fin dai primi anni '60:
vedi algoritmi per la risoluzione dell'equazione di Navier-Stokes ai volumi finiti e variabili segregate. :cool:

ragazzi col fortran non si gioca, si fa la guerra ! (e la pace) ;)

P.S.
mi sembra poi che, in generale, chi si occupa dei linguaggi di programmazione solo per gestire funzioni di macchina e flussi di dati abbia un certo ritardo culturale, diciamo un delay puro, come le palle dei cani :D :D

MickMacello

13-04-2002, 10:06

Originariamente inviato da a2000
[B]
P.S.
mi sembra poi che, in generale, chi si occupa dei linguaggi di programmazione solo per gestire funzioni di macchina e flussi di dati abbia un certo ritardo culturale, diciamo un delay puro, come le palle dei cani :D :D

Che ci vuoi fare, non ci sono più gli insegnanti di una volta...

paplo

13-04-2002, 14:45

Ciao,

vi chiedo un piccolo favore ancora ....

mi potreste inviare o postare questi file ...

pthread.h
semaphore.h
stdio.h
stdlib.h
time.h

putroppo non ho installato Linux ed il compilatore per Windows non li ha a disposizione.

la mia email è paplo@inwind.it

Vi ringrazio molto!

Ciao,
Paplo

/\/\@®¢Ø

13-04-2002, 16:13

pthread e' specifico di una libreria e non basta copiarle l'header la devi avere tutta.

Ho trovato un port dei pthread qui (http://sources.redhat.com/pthreads-win32/) , dovresti pure trovare le dll gia' precompilate. "semaphore.h" forse e' un header di linux , pero' nei pthreads ci sono pure i semafori , si tratta solo di cambiare i nomi delle funzioni.

Potresti in alternativa usare le api di win32 , pero' temo che per il tuo progetto non vada bene.

stdlib.h e stdio.h invece dovrebbero essere standard , strano che tu non le abbia.

Se usi un compilatore C++ invece che prova a includere cstdlib e cstdio.

Stessa cosa per time.h. Non so se e' standard, comunque ctime del C++ lo e'.

paplo

13-04-2002, 17:19

Originariamente inviato da /\/\@®¢Ø
[B]stdlib.h e stdio.h invece dovrebbero essere standard , strano che tu non le abbia.

credo anche io che siano standard, ma non ho avuto modo di sapere se vi sono perchè mi restituisce solo un errore per volta il compilatore.

Ciao e grazie,
Paplo

/\/\@®¢Ø

13-04-2002, 19:03

Che compilatore usi ?

Un'altra cosa non capisco... come mai nel file hai incluso i pthread ? Poi non li usi mi sembra ...

paplo

13-04-2002, 21:17

veramente non lo neanche io perchè includiamo pthread.h. evidentemente è stata una modifica in corso d'opera.

il compilatore che uso in Windows è ... LCC-Win32.

il problema è che il cambiamento di stato del semaforo a destra e a sinistra non viene mai effettuato.
e allora come posso modificare???

Ciao,
Paplo

P.S: l'ultima modifica è questa ...

MickMacello

13-04-2002, 22:19

scusa ma...se la memoria non mi inganna(ho studiato sta roba anni fa e da allora non ho più avuto occasione di usarla):
tu ridefinisci il tipo int come tipo semaphore.
definisci le funzioni wait e signal che usano il tuo tipo semaphore cioè un semplice int...
Ma queste non sono funzioni atomiche. Devi usare quelle fornite dal sistema operativo che nel caso di linux sono contenute nelle librerie
wait.h, signal.h, unistd.h pthread.h ecc ecc (in win non saprei). Altrimenti la sincronizzazione tra processi non funzionerà mai.

paplo

14-04-2002, 08:50

x MickMacello

non capisco quello che vuoi dire!?

cmq. per il mio programma ho preso spunto dal programma dei 5 filosofi.
ecco le funzioni wait e signal che ho trovato ...

"
void wait(semaphore s)
{
int junk;
if(read(s[0], &junk, 1) <= 0) {
printf("ERROR: wait() fallita in creazione semaforo!\n");
exit(1);
}
}

void signal(semaphore s)
{
if(write(s[1], "x", 1) <=0){
printf("ERROR: write() fallita nella creazione semaforo!\n");
exit(1);
}
}
"

cionci

14-04-2002, 11:23

Così non va bene...è solo una simulazione della wait e della signal in caso di singolo processo...

La wait e la signal come già datto da MickMacello devono essere operazioni atomiche ovvero devono essere system call che lavorando a livello del kernel non possono essere interrotte dallo scheduler (o da altri programmi)...

Poi hai implementato il blocco sulla wait come una funzione chiamata up...quella funzione non esiste perchè è già implementata dalla system call wait...

In pratica wait è così :

void wait(semaphore *s)
{
if ((*s)==0)
mi_metto_in_attesa_passiva(); //ovvero lo schedule mi mette in
//coda dei processi bloccati sul semaforo s
--(*s);
}

Mentre la signal è in pratica così :

void signal(semaphore *s)
{
++(*s);
}

Dirai simili alle tue...ma devono essere atomiche...quindi anche le interruzioni esterne devono essere disabilitate...e questo avviene solo per le system call...

Ad esempio lo scheduler ti toglie il processore suito dopo averti svegliato da una wait...prima di eseguire --s...un altro processo fa una wait (s in questo momento è a 1 perchè un altro processo ha fatto una signal per svegliare il processo in attesa sul semaforo)...la wait non blocca per questo processo e s va a 0...
Ora che succede, quendo al primo processo viene riassegnato il processore esegue --s...quindi il semaforo si porta in uno stato inconsistente e probabilmente non più recuperabile !!!

Quindi sia wait che signal devono essere atomiche...quindi system call !!!

cionci

14-04-2002, 11:36

Inoltre le varie funzioni up, down, wait e signal che ha usato sono concettualmente sbagliate perchè dovrebbero lavorare con puntatori...altrimenti il valore di s che viene cambiato all'interno delle funzioni è solo valido all'interno delle stesse (fai un passaggio deid ati per valore)...

/\/\@®¢Ø

14-04-2002, 12:12

azz... io non me n'ero accorto... pensavo usate chiamate di sistema !

paplo

14-04-2002, 14:23

x Cionci

ho effettuato le modifiche che mi hai suggerito, però ...
mi da questi errori ...

"passing arg 1 of 'wait' from incompatible pointer type"
"passing arg 1 of 'signal' from incompatible pointer type"

presumo da ciò che devo creare una funzione che crei un semaforo, è vero?!
ma come devo fare!?!? AIUTO!!!

inoltre ho modificato il tuo wait affinchè se il semaforo S non è verde esca, ovvero salti il turno

void wait(semaphore *s)
{
if ((*s)==0)
exit(1); //ovvero lo schedule mi mette in
//coda dei processi bloccati sul semaforo s
--(*s);
}

è corretto???

Grazie mille,
Paplo

P.S. ecco il listato ...

paplo

14-04-2002, 14:27

il listato precendete è errato.

ve lo rimando corretto ...

/\/\@®¢Ø

14-04-2002, 15:40

Ma ti e' richiesto di crearti tu i semafori ?
Non ti sarebbe piu' semplice utilizzare le chiamate che ti forniscono le librerie ?

cionci

14-04-2002, 16:03

Originariamente inviato da paplo
[B]x Cionci

ho effettuato le modifiche che mi hai suggerito, però ...
mi da questi errori ...
Attenzione io non ti ho suggerito delle modifiche...quella che ti ho data è la possibile implementazione della wait e della signal a livello di kernel...
Tu non puoi implementare wait e signal...devi usare quelle fornite dal sistema operativo perchè devono essere atomiche !!!

MickMacello

14-04-2002, 16:06

paplo cazzarola non ci siamo. Devi usare le chiamate di sistema.
Togli le definizioni di wait e signal e includi le librerie di sistema che le implementano.
Nel tuo file sorgente non devono comparire queste righe:

void wait(semaphore s);
void signal(semaphore s);

void wait(semaphore s)
{
if ((*s)==0)
exit(1); //ovvero lo schedule mi mette in
//coda dei processi bloccati sul semaforo s
--(*s);
}

void signal(semaphore s)
{
++(*s);
}

paplo

14-04-2002, 18:18

vi ringrazio per la pazienza.

appena posso vi riferiro il risultato!

paplo

14-04-2002, 18:21

Originariamente inviato da /\/\@®¢Ø
[B]Ma ti e' richiesto di crearti tu i semafori ?
Non ti sarebbe piu' semplice utilizzare le chiamate che ti forniscono le librerie ?

ho controllato il testo dell'esercizio e c'è scritto ...
"Gli esercizi proposti nel seguito devono essere realizzati in C utilizzando, laddove è necessario, le chiamate di sistema e le funzioni di libreria del caso. "

così è molto più facile! :D

(un'altra volta sono stato costretto a creare un metodo Random in java perchè il professore non voleva che utilizassimo quello della libreria Math)

Ciao,
Paplo

/\/\@®¢Ø

14-04-2002, 18:49

Originariamente inviato da paplo
[B]
così è molto più facile! :D

Piu' che altro indispensabile... :D

paplo

14-04-2002, 20:17

Originariamente inviato da /\/\@®¢Ø
[B]

Piu' che altro indispensabile... :D

no ... ho trovato anche il problema dei 5 filosofi con le funzioni wait, signal e make_semaphore funzionanti.

cionci

14-04-2002, 22:02

Originariamente inviato da paplo
[B]no ... ho trovato anche il problema dei 5 filosofi con le funzioni wait, signal e make_semaphore funzionanti.
Funzionante male ;)

Te l'ho detto...fidati... Ti può funzionare 10 volte, 100 volte, 1000 volte...ma sicuramente, per Murphy, ti andrà male proprio quando ti serve veramente !!!

Tutte le primitive di sincronizzazione DEVONO essere atomiche...o per lo emno devono appoggiarsi ad una primitiva di sincronizzazione atomica (ad esempio si possono implementare la wait e la signal con una mutex)...punto e basta...non ci sono alternative...
Altrimenti le puoi provare ad implementare come ti pare, ma saranno sempre errate...

paplo

15-04-2002, 08:39

Ciao,

ho provato ad utilizzare le funzioni atomiche, ma mi da cmq. errori ...

filosofi.c:19: warning: initialization makes pointer from integer without a cast
filosofi.c: In function `main':
filosofi.c:45: warning: assignment makes pointer from integer without a cast
filosofi.c: In function `put_cards':
filosofi.c:135: warning: passing arg 1 of `signal' makes integer from pointer without a cast
filosofi.c:135: too few arguments to function `signal'
filosofi.c:136: warning: passing arg 1 of `signal' makes integer from pointer without a cast
filosofi.c:136: too few arguments to function `signal'

putroppo non riesco a risolverli! :( :D

Ancora grazie per la disponibilità.

Ciao,
Paplo.

P.S.:il listato è ...