[C]linux: programma didattico comunicazione tra thread vers2

[caralu]

Salve ragazzi! Avevo già postato un errore precedente, adesso sono andato molto più avanti ma mi sono bloccato su alcuni problemi.
Sto implementando un programmino didattico: sarebbe una emulazione del gioco di space invaders (ma molto grezzo!),con grafica scarna.
Il programma è quasi analogo al classico problema dei "produttori-consumatori": creo dei processi con relativi thread, che accedono ad un buffer condiviso (protetto da semafori), basandomi sulle librerie lpthread e lncurses.
Il problema in cui mi sono impantanato adesso è relativo forse alla sincronizzazione che non funziona: gli alieni ad un certo punto si bloccano e le bombe che lancia la mia nave con il tasto INVIO non capisco come mai non vengono bloccate (homesso un controllo per fare sparare due bombe per volta ma non lo rispetta). Non capisco se il problema sono i semafori!
Qualcuno può darmi una mano? Vi allego il codice:

/*
Autori: Carlo Buttu, Giovanni Bussu.
Versione Beta 0.1
Codice rilasciato su licenza GPL ( http://www.gnu.org/licenses/gpl-howto.html).
*/

#include <stdio.h>
#include <curses.h>
#include <time.h>
#include <stdlib.h>
#include <unistd.h>
#include <pthread.h>
#include <semaphore.h>

#define NUM_MAX_RIGHE 5
#define SINISTRA 68
#define DESTRA 67
#define N_INIZIALE_ALIENI 10
#define SPAZIO 2
#define SPAZIO_RIGHE 1
#define PASSO_X 2
#define PASSO_Y 1
#define MAX_BOMBE_NAVE 2
#define MAX_BOMBE_ALIENO N_INIZIALE_ALIENI * 2
#define DIM_BUFFER N_INIZIALE_ALIENI


struct pos {
char *c;
int x;
int y;
int xPrec;
int yPrec;
int index;
int id;
};

struct pos alieni[N_INIZIALE_ALIENI];
struct pos info_nave;
struct pos bombe_nave[MAX_BOMBE_NAVE];
struct pos bombe_alieno[MAX_BOMBE_ALIENO];
struct pos *info_elementi[DIM_BUFFER];

void *alieno(void *);
void *nave(void *);
void *controllo(void *);
void *sparaBomba(void *);
void bomba(struct pos, struct pos *);

pthread_t array_alieni[N_INIZIALE_ALIENI];
pthread_t threadNave;
pthread_t bombaNave[MAX_BOMBE_NAVE];
pthread_t bombaAlieno[MAX_BOMBE_ALIENO];

pthread_mutex_t semaforo = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t mutexBombeAlieni = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t mutexBombeNave = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t mutexAlieni = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t mutexNave = PTHREAD_MUTEX_INITIALIZER;

sem_t vuoto, pieno;
int dimAlieni, bufferScrittura, bufferLettura, nBombeNaveResidue, nBombeAlienoResidue, posDisponibileAlieno, posDisponibileNave;

int main() {
int i = 0, j = 1, k, nAlieniRiga;
initscr();
noecho();
curs_set(0);
bufferScrittura = 0;
bufferLettura = 0;
posDisponibileAlieno = 0;
posDisponibileNave = 0;
nBombeNaveResidue = MAX_BOMBE_NAVE;
nBombeAlienoResidue = MAX_BOMBE_ALIENO;
dimAlieni = 1;
nAlieniRiga = COLS / (dimAlieni + SPAZIO);
sem_init(&vuoto, 0, DIM_BUFFER);
sem_init(&pieno, 0, 0);

for (k = 0; k < N_INIZIALE_ALIENI; k++){
	i = k % nAlieniRiga;
	j =  (k / nAlieniRiga) + 1;
	
	alieni[k].x = i * (SPAZIO + 1);
	alieni[k].y =  j * (SPAZIO_RIGHE + 1);
	alieni[k].c = "#";
	alieni[k].index = k;
	pthread_create(&array_alieni[k], NULL, &alieno, &alieni[k]);
}

pthread_create(&threadNave, NULL, &nave, NULL);
controllo(NULL);
getchar();
endwin();
exit(0);
}

void *nave(void *args)
{
struct pos pos_nave;
struct pos pos_bomba;
pos_nave.c = "^";
pos_nave.x = COLS / 2;
pos_nave.yPrec = pos_nave.y = LINES - 1;
pos_nave.index = N_INIZIALE_ALIENI; //per ora è inutile...
sem_wait(&vuoto); //Segnala che è stata scritta un altra posizione nel buffer
pthread_mutex_lock(&semaforo); //equivale ad una wait su valore 1
info_elementi[bufferScrittura] = &pos_nave;
bufferScrittura = (bufferScrittura + 1) % DIM_BUFFER;
info_nave = pos_nave;
pthread_mutex_unlock(&semaforo);
sem_post(&pieno); //Segnala che c'è una posizione in più da leggere nel buffer
while(1)
	{
	pos_nave.xPrec = pos_nave.x;
	char c;
	switch(c = getch())
		{
		case SINISTRA: if(pos_nave.x > 1) pos_nave.x -= 1;
		break;
		case DESTRA: if(pos_nave.x < COLS - 1) pos_nave.x += 1;
		break;
		case ' ':
			pos_bomba.x = pos_bomba.xPrec = pos_nave.x;
			pos_bomba.y = LINES - 2;
			pos_bomba.c = "o";
			pthread_mutex_lock(&mutexBombeNave);
			if(nBombeNaveResidue > 0)
				{
				pthread_mutex_lock(&mutexNave);
				pthread_create(&bombaNave[posDisponibileNave], NULL, &sparaBomba, &pos_bomba);
				pthread_mutex_unlock(&mutexNave);
				}
			pthread_mutex_unlock(&mutexBombeNave);
		}
	if (c == DESTRA || c == SINISTRA)
		{
		sem_wait(&vuoto); //Segnala che è stata scritta un altra posizione nel buffer
		pthread_mutex_lock(&semaforo); //equivale ad una wait su valore 1
		info_elementi[bufferScrittura] = &pos_nave;
		bufferScrittura = (bufferScrittura + 1) % DIM_BUFFER;
		info_nave = pos_nave;
		pthread_mutex_unlock(&semaforo);
		sem_post(&pieno); //Segnala che c'è una posizione in più da leggere nel buffer
		}
	}
}

void *alieno(void *args)
{
struct pos pos_alieno = *(struct pos*) args;
pos_alieno.id = pthread_self();
int dir = 1, dx, dy;
srand((int) pos_alieno.id);
while(1)
	{
	pos_alieno.yPrec = pos_alieno.y;
	pos_alieno.xPrec = pos_alieno.x;
	dx = PASSO_X * dir;
	dy = 0;
	if (pos_alieno.x + dx >= COLS -1 || pos_alieno.x + dx <= 0)
		{
		if(dir > 0)
			pos_alieno.x = COLS - 1;
		else
			pos_alieno.x = 0;
		dir = -dir;
		dx = PASSO_X * dir;
		dy = PASSO_Y;
		}
	pos_alieno.x += dx;
	pos_alieno.y += dy;
	sem_wait(&vuoto); //Segnala che è stata scritta un altra posizione nel buffer
	pthread_mutex_lock(&semaforo); //equivale ad una wait su valore 1
	info_elementi[bufferScrittura] = &pos_alieno;
	bufferScrittura = (bufferScrittura + 1) % DIM_BUFFER;
	alieni[pos_alieno.index] = pos_alieno;
	pthread_mutex_unlock(&semaforo);
	sem_post(&pieno); //Segnala che c'è una posizione in più da leggere nel buffer
	int t = clock();
	if((rand() % 100) >= 65 - 1) // 1 qui equivale al livello....da aggiornare!
	{
		struct pos pos_bomba;
		pos_bomba.x = pos_bomba.xPrec = pos_alieno.x;
		pos_bomba.y = pos_alieno.y + 1;
		pos_bomba.c = "!";
		pthread_mutex_lock(&mutexBombeAlieni);
		if(nBombeAlienoResidue > 0)
			{
			pthread_mutex_lock(&mutexAlieni);
			pthread_create(&bombaAlieno[posDisponibileAlieno], NULL, &sparaBomba, &pos_bomba);
			pthread_mutex_unlock(&mutexAlieni);
			}
		pthread_mutex_unlock(&mutexBombeAlieni);
	}
	t = 1 - clock() - t;
	sleep((int)t);
	}
}
 
void *controllo(void *args)
{
struct pos valore_letto;
int index;
do {
	sem_wait(&pieno); //Segnala che è stata letta una posizione dal buffer
	pthread_mutex_lock(&semaforo);
	valore_letto = *info_elementi[bufferLettura];
	bufferLettura = (bufferLettura + 1) % DIM_BUFFER;
	pthread_mutex_unlock(&semaforo);
	sem_post(&vuoto);
	move(valore_letto.yPrec, valore_letto.xPrec);
	printw(" ");
	move(valore_letto.y, valore_letto.x);
	printw("%s",valore_letto.c);
	move(0,0);
	printw("Bombe nave %d",nBombeNaveResidue);
	//move(1,0);
	//printw("Bombe alieno %d",nBombeAlienoResidue);
	refresh();
	}
while (true);
}

void *sparaBomba(void *args)
{
struct pos pos_bomba = *(struct pos*) args;
struct pos *posizione;
pos_bomba.id = pthread_self();
if(pos_bomba.c == "!") // è un alieno?
	{
	pthread_mutex_lock(&mutexBombeAlieni);
	if(nBombeAlienoResidue > 0)
		{
		nBombeAlienoResidue--;
		pos_bomba.index = posDisponibileAlieno; // per ora è inutile...
		posDisponibileAlieno = (posDisponibileAlieno + 1) % MAX_BOMBE_ALIENO;
		posizione = &bombe_alieno[posDisponibileAlieno];
		pthread_mutex_unlock(&mutexBombeAlieni);
		bomba(pos_bomba, posizione);
		pthread_mutex_lock(&mutexBombeAlieni);
		nBombeAlienoResidue++;
		posDisponibileAlieno = (posDisponibileAlieno - 1) % MAX_BOMBE_ALIENO;
		}
	pthread_mutex_unlock(&mutexBombeAlieni);
	}
	else
		if(pos_bomba.c == "o") //è una nave?
			{
			pthread_mutex_lock(&mutexBombeNave);
			if(nBombeNaveResidue > 0)
				{
				nBombeNaveResidue--;
				pos_bomba.index = posDisponibileNave; //per ora è inutile...
				posDisponibileNave = (posDisponibileNave + 1) % MAX_BOMBE_NAVE;
				posizione = &bombe_nave[posDisponibileNave];
				pthread_mutex_unlock(&mutexBombeNave);
				bomba(pos_bomba, posizione);
				pthread_mutex_lock(&mutexBombeNave);
				nBombeNaveResidue++;
				posDisponibileNave = (posDisponibileNave - 1) % MAX_BOMBE_NAVE;
				}
			pthread_mutex_unlock(&mutexBombeNave);
			}
}

void bomba(struct pos pos_bomba, struct pos *posizione)
{
int limite = (pos_bomba.c == "!") ? LINES - 1 : 0;
int dir = (pos_bomba.c == "!") ? 1 : -1;
	sem_wait(&vuoto); //Segnala che è stata scritta un altra posizione nel buffer
	pthread_mutex_lock(&semaforo); //equivale ad una wait su valore 1
	info_elementi[bufferScrittura] = &pos_bomba;
	bufferScrittura = (bufferScrittura + 1) % DIM_BUFFER;
	*posizione = pos_bomba;
	pthread_mutex_unlock(&semaforo);
	sem_post(&pieno); //Segnala che c'è una posizione in più da leggere nel buffer
while(pos_bomba.y != limite)
	{
	usleep(100000);
	pos_bomba.yPrec = pos_bomba.y;
	pos_bomba.y += dir;
	sem_wait(&vuoto); //Segnala che è stata scritta un altra posizione nel buffer
	pthread_mutex_lock(&semaforo); //equivale ad una wait su valore 1
	info_elementi[bufferScrittura] = &pos_bomba;
	bufferScrittura = (bufferScrittura + 1) % DIM_BUFFER;
	*posizione = pos_bomba;
	pthread_mutex_unlock(&semaforo);
	sem_post(&pieno); //Segnala che c'è una posizione in più da leggere nel buffer
	}
pos_bomba.c = " ";
sem_wait(&vuoto); //Segnala che è stata scritta un altra posizione nel buffer
pthread_mutex_lock(&semaforo); //equivale ad una wait su valore 1
info_elementi[bufferScrittura] = &pos_bomba;
bufferScrittura = (bufferScrittura + 1) % DIM_BUFFER;
*posizione = pos_bomba;
pthread_mutex_unlock(&semaforo);
sem_post(&pieno); //Segnala che c'è una posizione in più da leggere nel buffer
}

P.S. Compilare con le opzioni -lpthread & -lncurses, es:
gcc -o alieni alienThread.c -lncurses -lpthread

[sottovento]

Ciao,
non sono molto sicuro di quello che dico: il codice pubblicato e' lungo e richiede una analisi attenta, anche se scritto bene.

Mi sono fatto pero' un'idea facendo una semplice ricerca nel codice.
Ogni tanto, nel codice, si vedono delle acquisizioni di mutex innestate, del tipo:

			pthread_mutex_lock(&mutexBombeNave);
			if(nBombeNaveResidue > 0)
				{
				pthread_mutex_lock(&mutexNave);
				pthread_create(&bombaNave[posDisponibileNave], NULL, &sparaBomba, &pos_bomba);
				pthread_mutex_unlock(&mutexNave);
				}
			pthread_mutex_unlock(&mutexBombeNave);

Beh, direi che sono le prime cose che andrei a verificare: se acquisisci la prima mutex (mutexBombeName) mentre qualcun altro ha acquisito la mutexNave, hai un potenziale rischio di deadlock.

Il mio parere e' che il programma utilizzi troppi meccanismi di sincronizzazione: come hai scritto, e' proprio quello lo scopo del programma.
Tuttavia, i programmi troppo sincronizzati (per esperienza) hanno due problemi che all'universita' tendono a non segnalare (chissa' perche', poi...):
- entrano facilmente in deadlock, ed e' difficile trovare la soluzione;
- nel caso non entrino in deadlock, sono cosi' sincronizzati da avere un'esecuzione sequenziale. Ricorda che ogni volta che entri in quelle mutex, l'esecuzione e' potenzialmente sequenziale.

Ho controllato il codice molto velocemente, ti prego di scusarmi se ho preso una grande cantonata. Comunque il mio suggerimento e' di rivedere l'architettura e le interazioni dei vari tasks, e magari pubblicare uno schema su questo forum.


High Flying
Sottovento

[caralu]

Originariamente inviato da sottovento

Il mio parere e' che il programma utilizzi troppi meccanismi di sincronizzazione: come hai scritto, e' proprio quello lo scopo del programma.
Tuttavia, i programmi troppo sincronizzati (per esperienza) hanno due problemi che all'universita' tendono a non segnalare (chissa' perche', poi...):
- entrano facilmente in deadlock, ed e' difficile trovare la soluzione;
- nel caso non entrino in deadlock, sono cosi' sincronizzati da avere un'esecuzione sequenziale. Ricorda che ogni volta che entri in quelle mutex, l'esecuzione e' potenzialmente sequenziale.

Ciao sottovento! Innanzitutto grazie per la risposta!
Si, penso proprio che il problema sia una situazione di deadlock. Il fatto è che realizzando un progetto di questo tipo in cui ho degli alieni, una nave (personaggio principale) e delle bombe nemiche e amiche, devo memorizzare queste strutture in un array condiviso e per bloccare l'accesso simultaneo utilizzo un mutex per ognuno di questi array, non saprei che altro fare. Ora controllo nuovamente tutto e vedo se riesco ad eliminare qualche sezione critica, così si elimina un po di casino e potenziali situazioni di stallo!

[sottovento]

Ciao,
non volevo certo dire che usare le sezioni critiche e' un errore! Magari ottimizzarne l'uso...
Sottolineavo poi il fatto che nel codice, all'interno di una sezione critica, ne vai ad acquisire un'altra!
Questa e' una delle principali operazioni candidate a generare deadlock!
Controlla prima quelle istruzioni: se sei in una sezione critica, ne chiedi un'altra, hai una grande probabilita' di creare deadlock perche' potrebbe essere che la seconda sezione e' bloccata e nessuno la puo' sbloccare a causa della prima.

High Flying
Sottovento

[caralu]

Originariamente inviato da sottovento

Ciao,
Sottolineavo poi il fatto che nel codice, all'interno di una sezione critica, ne vai ad acquisire un'altra!
Questa e' una delle principali operazioni candidate a generare deadlock!
Controlla prima quelle istruzioni: se sei in una sezione critica, ne chiedi un'altra, hai una grande probabilita' di creare deadlock perche' potrebbe essere che la seconda sezione e' bloccata e nessuno la puo' sbloccare a causa della prima.
Sottovento

Sai, avevi proprio ragione! Ho fatto un bel debug, era proprio un deadlock sulla funzione di controllo! Grazie del consiglio, adesso ci metto mano poi posto il codice modificato

[caralu]

Ho modificato il mio programma e ho corretto diversi errori ma il deadlock rimane..Il fatto è che il deadlock avviene solo in certe distribuzioni linux (slackware, ubuntu..) mentre in altre no (ad esempio mandriva...). Come mai??

[Azizel]

Originariamente inviato da caralu

E si, mi sa proprio che stiamo facendo lo stesso progetto! :-)
Io al controllo (come puoi vedere dal codice che ho postato) faccio aggiornare tutti gli oggetti in movimento, però ad ogni oggetto associo un thread (un thread per ciascuna bombaNave, bombaAliena, nave, e alieni) creato nelle rispettive funzioni...
Il problema che sto avendo è quello che nel gestire i diversi array condivisi di ciascun oggetto ho implementato molti semafori e questo mi causa una situazione di stallo..Non riesco a trovare dove sia questo maledetto deadlock!
Tu hai fatto un'array per ogni struttura diversa oppure hai messo tutto in un'unico array condiviso??
(puoi rispondere pure nel mio post, mi sa che è più attinante all'argomento!)

Ti rispondo qua...
Io molto semplicemente associo ad ogni thread una struttura dati con la posizione attuale (x e y), ogni thread si occupa di muovere, cioè cambiare le coordinate x e y(se è il giocatore le prende da input) e ridisegnare sul terminale l'oggetto (alieno o giocatore) nella nuova posizione.
Nella realtà dei fatti io ho tutte le strutture dati "visibili" e "accessibili" dagli altri, quindi non ho problemi per comunicare le posizioni (accedo direttamente alla struttura...).
Quindi una volta che un oggetto ha effettuato la sua mossa fa un sem_post che attiva il controllo, il quale si occupa di fare il check delle collisioni (un pèaio di cicli for e un if) ed eventualmente killare il thread "colpito"(nella struttura dati di ogni oggetto ho un intero alive che mi indica se è vivo o no, mi basta metterlo a 0...), oppure crearne uno nuovo se ce n'è bisogno, in seguito questo passa il controllo al thread seguente (che sarà un alieno o un giocatore) con una post sull'altro semaforo.
Per i missili io non creo nuovi thread(all'inizio avevo fatto così, poi diventava troppo difficile la gestione), ma semplicemente il giocatore quando preme la barra aggiunge ad una struttura dati(un array ad esempio) un nuovo fire, che verrà disegnato e "mosso" direttamente nel thread del giocatore ad ogni ciclo, quindi il missile è sincronizzato e legato al giocatore stesso...idem per gli alieni (che però generano i missili casualmente).
Il mio approccio è un pò diverso dal tuo, diciamo che io con 2 semafori e una mutex (forse 2 devo ancora vedere..) faccio tutto, il problema è che non so se al docente gli basta...speriamo...

Tieni conto che i miei alieni per ora si muovono da una parte all'altra dello schermo e quando ne viene ucciso uno dopo tot secondi ne viene generato un altro...non ci sono "livelli", AI o quant'altro...diciamo che esula dallo scopo del progetto per ora(lunedì devo presentarlo...)

Poi ho notato una cosa nel tuo codice, tu tieni un buffer con le posizioni...quando arriva il controllo stampa la prima posizione letta del buffer..ma se per caso il controllo avviene più lentamente dell'aggiornamento delle posizioni?? ti vanno a remengo le posizioni inserite nel frattempo? In pratica stampi una posizione che in realtà è già cambiata...o ho capito male io?


Magari prova a spiegare a parole quello che vuoi implementare, perchè secondo me stai facendo la stessa identica cosa che ho fatto io (ho paura che tutti quei mutex fanno in modo da sincronizzare il tutto proprio come fa il mio programma, cioè uno alla volta passano la mano al thread di controllo, anche se in modo caotico) solamente complicando esponenzialmente le cose...

Ciao

[caralu]

Poi ho notato una cosa nel tuo codice, tu tieni un buffer con le posizioni...quando arriva il controllo stampa la prima posizione letta del buffer..ma se per caso il controllo avviene più lentamente dell'aggiornamento delle posizioni?? ti vanno a remengo le posizioni inserite nel frattempo? In pratica stampi una posizione che in realtà è già cambiata...o ho capito male io?


Magari prova a spiegare a parole quello che vuoi implementare, perchè secondo me stai facendo la stessa identica cosa che ho fatto io (ho paura che tutti quei mutex fanno in modo da sincronizzare il tutto proprio come fa il mio programma, cioè uno alla volta passano la mano al thread di controllo, anche se in modo caotico) solamente complicando esponenzialmente le cose...

Ho corretto il progetto eliminando 2 mutex (avevo una gestione troppo appesantita che portava ad un deadlock) ed inoltre c'era anche un'errore di inizializzazione del generatore di numeri pseudo-casuali (avevo inizializzato srand() all'interno di una funzione mentre è buona norma inizializzarlo nel main ).
Comunque il mio progetto mi sembra abbastanza simile al tuo (a parte i livelli e un nuovo thread per ogni bomba del mio applicativo)...
Il problema che dici tu della sincronizzazione pare che non esista dato che nella creazione di ogni alieno ho inserito una usleep() quindi ne crea uno ogni tot di Msecondi, inevitabilmente accede prima la funzione di controllo..
Grazie comunque per l'aiuto!

[Azizel]

Sisi infatti il mio funziona anche senza sincronizzarlo in questo modo(tranne per la mutex sulle librerie di ncurses), perchè "solitamente" gli alieni hanno un certo ordine di creazione e il controllo è molto più veloce, il problema è che non si può dire a priori quanto a lungo ci mette il thread a fare il suo ciclo, metti che il controllo ci metta qualche ms in più e il gioco va a quel paese...:P Comunque l'importante è che funzioni(almeno per l'esame...eheh)! poi ogni implementazione avrà i suoi vantaggi/svantaggi...

[caralu]

Comunque l'importante è che funzioni(almeno per l'esame...eheh)! poi ogni implementazione avrà i suoi vantaggi/svantaggi...

Parole sante! Lo sto implementando solo per l'esame, poi rilascio il codice e se qualcuno lo vuole migliorare faccia pure, ho pochissimo tempo a disposizione!