|
Sperimentiamo anche i thread ed i semafori.
Il testo dell'esercizio è il seguente:
Scrivere un programma in C per giocare a guardie e ladri contro il calcolatore.
Il ladro sarà rapperesentata da un carattere $, che si sposta
casualmente sullo schermo, cercando di allontanarsi dalla guardia.
La guardia sarà rappresentata da un carattere #, che verrà
mosso sullo schermo con i tasti freccia dall'utente.
Quando la guardia ed il ladro si incontreranno, il gioco terminerà.
Useremo tre thread:
- Un primo thread (il padre) visualizzerà un cronometro e
controllerà l'incontro della guardia con il ladro, ponendo fine al gioco
- Un primo figlio che muoverà il ladro a caso, entro un raggio di 1
casella attorno alla posizione precedente, ad un ritmo di 5 spostamenti al secondo,
spostandosi però di più nella direzione opposta alla guardia.
- Un secondo figlio che leggerà la tastiera e sposterà di
conseguenza la guardia.
Questo processo comunicherà di tanto in tanto la sua posizione al ladro
(ad esempio ogni 10 spostamenti).
Useremo un semaforo per sincronizzare il thread principale con i movimenti
degli altri due thread, onde evitare che continui a fare confronti, anche quando nulla si
muove.
La guardia invierà di tanto in tanto la sua posizione, copiandola in una
apposita variabile globale, per avvisarlo della sua posizione.
Ogni thread visualizzerà i suoi dati. Per evitare problemi con le routine di
Curses, gli accessi saranno protetti da una sezione critica, realizzata con un
mutex.
Quando il gioco termina, il padre, che rileva la terminazione, setta un
flag, per far terminare i figli.
I figli controlleranno questo flag ad ogni ciclo e termineranno la loro
esecuzione all'arrivo del prossimo evento (il prossimo spostamente per il ladro,
il prossimo tasto per la guardia).
NOTE:
- La documentazione sui Posix Threads si trova nella pagine info
della libreria libc.
Per leggere la documentazione;
- aprire il Gnome Help Browser clickando sull'icona
oppure aprendo il menù di avvio
(icona ) scegliendo le voci Programs -> Help
System
- scrivere info:libc nella barra della Location
- selezionare Basic Thread Operations nella sezione POSIX Treads
- Per utilizzare i POSIX Threads occorrerà includere l'header file
pthread.h e linkare la libreria /usr/lib/libpthread.so aggiungendo al comando di compilazione il parametro -lpthread.
- Per generare thread in Linux si usa la funzione
int pthread_create (pthread_t *THREAD, pthread_attr_t *ATTR, void *(*START_ROUTINE)(void *), void *ARG);.
I parametri di questa funzione sono:
- pthread_t *THREAD
- puntatore al pthread_t che descriverà il nostro thread.
- pthread_attr_t *ATTR
- puntatore alla struttura pthread_attr_t che serve per impostare attributi
particolari per il thread. Se non si vogliono paricolari attributi, si può passare il
valore NULL.
- void *(*START_ROUTINE)(void *)
- routine da eseguire nel nuovo thread. Questa routine verrà eseguita concorrentemente
al thread principale che lo ha creato. Potrà ritornare al suo termine il puntatore ad una
struttura a piacere. Potremo passarle una struttura a piacere come parametro.
- void *ARG
- l'argomento da pasare alla funzione. Potremo passare il puntatore ad una qualunque
struttura, oppure NULL se non abbiamo argomenti da passare.
La funzione ritorna 0 se il thread è stato creato correttamente, un
codice di errore altrimenti.
- Tutti i thread condividono lo stesso ambiente. Un metodo semplice per farli
comunicare è quello di utilizzare le variabili globali come memoria
comune.
- Per fare in modo che i thread vedano sempre la versione aggiornata delle
variabili globali, dovremo dare l'attributo volatile alle variabili globali
usate per la comunicazione.
- Normalmente occorre proteggere la modifica delle varibili globali tramite una
sezione critica. Se però ogni sezione critica modificherebbe solamente una
variabile semplice od un solo campo di una struttura, si può evitare di utilizzare
sezioni critiche. Nel nostro caso non useremo sezioni critiche per proteggere le variabili
globali.
- Per fare un ritardo breve in maniera semplice possiamo usare la funzione
usleep (int microsecondi);. Come parametro indicheremo il numero di
microsecondi di ritardo che vogliamo fare.
- Il thread principale controlla l'incontro tra i personaggi e stampa una sorta
di cronometro. Per evitare che controlli continuamente dati che non variano,
sprecando tempo di CPU, è opportuno che si sincronizzi con i processi che
modificano i dati. Per ottenere questo è molto adatto un semaforo.
- Per creare un semaforo useremo la funzione
int sem_init(sem_t *SEM, int PSHARED, unsigned int VALUE).
Il parametro SEM punta al semaforo da inizializzare. Dato che questo semaforo
serve a sincronizzare i thread, sarà una variabile globale. Dato che il semaforo è
usato solo dal nostro task, per sincronizzare i thread, metteremo il parametro
PSHARED a 0. Dato che il semaforo deve essere normalmente rosso e
viene messo a verde dai figli, per fare partire il thread principale, metteremo
-1 nel paramtro VALUE.
La funzione ritorna 0 se và tutto bene, -1 se avviene un
errore. Il codice dell'errore verrà posto in ERRNO.
- La funzione int sem_wait(sem_t *SEM); verifica se il semaforo
è a 0. Se non lo è, sospende il processo fino a che non lo diventa,
quindi lo decrementa. Potremo usarla per attendere un segnale dagli altri thread.
- La funzione int sem_post(sem_t *SEM); incrementa il semaforo. La
potremo utilizzare per inviare un segnale all'altro thread. Non ci si deve preoccupare
che più di una sem_post blocchi il semaforo, mandandolo in uno stato
dal quale non può uscire, perché la variabile del semaforo è internamente
limitata.
- La funzione int sem_destroy(sem_t *SEM); serve per eliminare
il semaforo, quando non ne abbiamo più bisogno.
- Per la visualizzazione si useranno le funzioni di ncurses, come
spiegate nel relativo tutorial.
- Le funzioni di ncurses non sono rientranti, vale a dire, non possono
essere chiamate contemporaneamente da più thread, in quanto la seconda chiamata si
troverebbe le variabili di ncurses in uno stato non corretto. Occorrerà
quindi creare una sezione critica per proteggere le funzioni di ncurses. La realizzeremo
utilizzando un mutex.
- Per creare un mutex utilizzeremo la funzione
int pthread_mutex_init(pthread_mutex_t *MUTEX, const pthread_mutexattr_t *MUTEXATTR);.
Il parametro MUTEX punterà ad una struttura
pthread_mutex_t globale, in quanto dovrmo accedervi da tutti i thread.
Il parametro MUTEXATTR punta ad una struttura che definisce opzioni
particolari per il mutex. Dato che non ci servono queste opzioni potremo
passare il valore NULL.
- Prima di entrare in una sezione critica dovremo chiamare la funzione
int pthread_mutex_lock(pthread_mutex_t *mutex);.
Questa funzione sospenderà il thread fino a che il mutex
non sarà libero, quindi lo blochrà.
- All'uscita dalla sezione critica chiameremo la funzione
int pthread_mutex_unlock(pthread_mutex_t *MUTEX);.
Questa funzione sbloccherà il mutex.
- Una volta finito di utilizzare un mutex, useremo la funzione
int pthread_mutex_destroy(pthread_mutex_t *MUTEX); per eliminarlo.
- Per attendere la terminazione di un thread utilizzeremo la funzione
int pthread_join(pthread_t TH, void **thread_RETURN);.
Dovremo passare a questa funzione il riferimento al trhread da attendere, e
l'indirizzo di un puntatore nel quale verrà posto l'indirizzo della struttura
ritornata dalla funzione del thread.
La funzione ritorna 0 se non ci sono errori, altrimenti ritorna
un codice di errore.
- Per creare un movimento casuale potremo sommare un numero casuale che
vada da -RAGGIO a +RAGGIO ad entrambe le coordinate della
posizione corrente del ladro.
La funzione random(); ritorna un numero intero positivo compreso tra 0 e
MAXINT. Per ottenere quindi un numero casuale in un campo minore useremo
l'operatore modulo (ad esempio random () % MAX). Dato che noi vogliamo
un numero compreso tra -RAGGIO e RAGGIO, avremo
RAGGIO numeri negativi, RAGGIO numeri positivi e
lo 0, quindi 2*RAGGIO+1 possibili numeri, che otterremo con
random()%(RAGGIO*2+1).
Queste combinazioni sono per&ogravi tutte positive. Per averne RAGGIO negative, dovremo
sottrarre al numero ottenuto RAGGIO+1, quindi la formula definitiva
sarà random()%(RAGGIO*2+1)-(RAGGIO+1).
Se poi vogliamo che il movimento casuale porti comunque il ladro in una certa
direzione, possiamo caloclare il nonstro spostamento casuale non a partire dalla
vecchia posizione, ma da una posizione spostata nella direzione in cui vogliamo
muoverci.
Ammettiamo di avere un secondo punto e volerci allontanare da esso. Se sottraiamo alle nostre coordinate quelle di quel punto, avremo due numeri ognuno dei quali sarà:
- Positivo
- se la relativa coordinata del punto da sfuggire è inferiore alla nostra,
quindi per fuggire dovremo aumentare la nostra coordinata
- Uguale a 0
- se la relativa coordinata del punto da sfuggire è uguale alla nostra, quindi
per fuggire dovremo lasciare immutata la nostra coordinata e fuggire lungo l'altra
direzione
- Negativo
- se la relativa coordinata del punto da sfuggire è superiore alla nostra,
quindi per fuggire dovremo calare la nostra coordinata
Se noi limitiamo questi numeri al campo -1...1 ed aggiungiamo questi
numeri alle coordinate correnti del ladro nella formula precedente, esso tenderà a
muoversi nella direzione opposta al punto di riferimento.
- È necessario controllare che né la guardia né il ladro escano
dal campo.
Nel caso della guardia, occorrerà bloccarla quando raggiunge il bordo.
Per il ladro, invece, è opportuno invertire lo spostamento se questo
portasse fuori campo.
- È opportuno scrivere una funzione separata per il campo,
invece che includere tutto il codice nella funzione main.
Una possibile soluzione è la seguente:
/* guardieladrit.c
* Stefano Salvi - 21/9/02
* Gioco 'guardie e ladri'.
* Un 'ladro' (rappresentato da un '$') fugge a caso sullo schermo.
* Una 'guardia' (raprresentata da un '#') lo insegue, pilotato dai tasti del giocatore.
* Il gioco termina quando la guardia raggiunge il ladro.
*
* Per realizzare il gioco utilizzeremo tre thread:
* 1) thread 'padre'. Visualizza un contatore di mosse e verifica se la guardia ha preso il
* ladro.
* Quando il gioco e' terminato, imposta un flag, i figli, vedendolo terminano, il padre
* attende la loro terminazione.
*
* 2) thread 'figlio - ladro'. Genera casualmente uno spostamento e sposta il suo
* 'personaggio'. Genera lo spostamento a partire dalla posizione 'pubblicata' dalla guardia
*
* 3) thread 'figlio - guardia'. Legge la tastiera e calcola la nuova posizione, in base
* ai tasti letti. Visualizza il suo 'personaggio' e comunica periodicamente al ladro la
* sua posizione.
*
* I tre processi comunicano tramite variabili globali.
* Dato che le routine di curses non sono 'rientranti', e dato che tutti i tre thread le usano,
* le proteggeremo tramite un 'mutex'.
* Per evitare che il thread padre consumi troppo tempo di CPU, eseguendo controlli anche quando
* nessuno si e' mosso, sincronizzeremo questo thread agli altri con un semaforo.
*
* X compilare:
* gcc guardieladrit.c -o guardieladrit -lncurses -lpthread
*/
#include <stdio.h>
#include <curses.h>
#include <stdlib.h>
#include <unistd.h>
#include <pthread.h>
#include <semaphore.h>
#define RAGGIO 1 /* di quanto si sposta il ladro ad ogni ciclo */
#define SU 65 /* Freccia su */
#define GIU 66 /* Freccia giu */
#define SINISTRA 68 /* Freccia sinsitra */
#define DESTRA 67 /* Freccia destra */
#define MAXX 80 /* Numero di colonne */
#define MAXY 23 /* Numero di righe */
/* Struttura per la comunicazione tra figli e padre */
struct pos{
int x; //posizione x
int y; //posizione y
};
/* Variabili globali di comunicazione tra i thread */
volatile struct pos pladro; // Posizione corrente del ladro
volatile struct pos pguardia; // Posizione corrente della guardia
volatile struct pos showguardia; // Posizione corrente della guardia visibile al ladro
volatile int running; // Flag di programma non terminato
volatile int nmov; // Numero di movimenti della guardia (conta tempo)
/* Mutex e semaforo per la sincronizzazione tra i thread */
pthread_mutex_t semCurses; // Semaforo per l'accesso alle funzioni di ncurses
sem_t semGioco; // Semaforo per sincronizzare il campo con i 'giocatori'
/* Prototipi delle funzioni */
void *ladro (void *arg);
void *guardia (void *arg);
void campo (void);
int main()
{
pthread_t tLadro; // Pid del figlio 'ladro'
pthread_t tGuardia; // Pid del figlio 'guardia'
initscr(); // Inizializza curses
noecho(); // caratteristica della tastiera
curs_set(0); // elimina il cursore
running = TRUE; // Gioco non ancora finito
pthread_mutex_init (&semCurses, NULL); // Mutex di ncurses
sem_init (&semGioco, 0, -1); // Semaforo del gioco, inizialmente chiuso
/* Creo il thread del ladro */
if (pthread_create (&tLadro, NULL, ladro, NULL))
{
endwin(); // Torniamo in modalita' normale
printf ("Non riesco a creare il thread del ladro\n");
exit;
}
/* Creo il thread della guardia */
if (pthread_create (&tGuardia, NULL, guardia, NULL))
{
endwin(); // Torniamo in modalita' normale
printf ("Non riesco a creare il thread della guardia\n");
exit;
}
campo (); // Svolgo il lavoro del padre (gestire il campo)
/* Attendo la terminazione dei due thread */
pthread_join (tLadro, NULL);
pthread_join (tGuardia, NULL);
/* Elimino il mutex ed il semaforo */
pthread_mutex_destroy (&semCurses);
sem_destroy (&semGioco);
endwin(); // Torno in modalita' normale
return 0; // Termine del programma
}
/* Funzione 'ladro'.
* Genera un 'movimento casuale' in un raggio RAGGIO rispetto al punto corrente,
* nel campo di 80X24 caratteri e 'sposta' la guardia.
* Il movimento tende comunque a spostare il ladro lontano dalla guardia.
* La guardia comunica i suoi spostamenti al ladro, copiando periodicamente la sua
* posizione nella variabile globale showguardia
* Segala ogni spostamento al campo tramite il semaforo
*/
void *ladro (void *arg)
{
int deltax; // Spostamento orizzontale
int deltay; // Spostamento verticale
int fugax = 0,fugay = 0;// Spostamento del centro, per allontanarsi
nmov = 0; // Inizializza il contatore
// Posizione iniziale del ladro: in alto a sinistra.
pladro.x = 1;
pladro.y = 1;
// Posizione iniziale nota della guardia: il ladro sta' fermo.
showguardia.x = 1;
showguardia.y = 1;
while(running) // Ciclo fino a che 'campo' non dice basta
{
nmov ++; // Conta i cicli
pthread_mutex_lock (&semCurses); // Attendo che curses sia libero
mvaddch(pladro.y,pladro.x,' '); // Cancello la vecchia guardia
pthread_mutex_unlock (&semCurses); // libero curses
fugax = pladro.x - showguardia.x; // Individua la direzione della guardia
// normalizza fugax (-1, 0, 1)
if (fugax < 0)
{
fugax = -1;
}
else if (fugax > 0)
{
fugax = 1;
}
fugay = pladro.y - showguardia.y; // Individua la direzione della guardia
// normalizza fugay (-1, 0, 1)
if (fugay < 0)
{
fugay = -1;
}
else if (fugay > 0)
{
fugay = 1;
}
/* Calcola uno spostamento casuale da -RAGGIO ... RAGGIO.
* Abbiamo 2*RAGGIO+1 combinazioni (le RAGGIO negative, le RAGGIO positive e lo 0).
* 'random() % (RAGGIO*2+1)' ritorna combinazioni da 0 a 2*RAGGIO: quelle che servono
* ma tutte positive. Per averne RAGGIO negative, dovremo toglier RAGGIO+1
*/
deltax= ((random() % (RAGGIO*2+1)) - (RAGGIO + 1) + fugax);
// Se con lo spostamento esce, inverto lo spostamento
if(pladro.x + deltax < 1 || pladro.x + deltax >= MAXX)
{
deltax = -deltax; // Inverto lo spostamento
}
pladro.x += deltax; // Spostamento orizzontale
/* Calcola uno spostamento casuale da -RAGGIO ... RAGGIO.
* per l'algoritmo vedere il deltax
*/
deltay = ((random()%(RAGGIO*2+1)) - (RAGGIO + 1) + fugay);
// Se con lo spostamento esce, inverto lo spostamento
if(pladro.y + deltay < 1 || pladro.y + deltay >= MAXY)
{
deltay = -deltay;
}
pladro.y += deltay; // Spostamento verticale
pthread_mutex_lock (&semCurses); // Attendo che curses sia libero
mvaddch(pladro.y,pladro.x,'$'); // Disegno il ladro
refresh(); // Aggiorno le modifiche (canc. e disegno)
pthread_mutex_unlock (&semCurses); // libero curses
sem_post (&semGioco); // avviso il campo che c'e' stato un movimento
usleep(200000); // Pausa per 'dare il ritmo'
}
return NULL;
}
/* Funzione 'guardia'.
* Legge i tasti premuti dall'utente. Sposta la guardia nella direzione
* indicata dalle frecce. Si ferma ai bordi del campo di 80X24 caratteri.
* Segala ogni spostamento al campo tramite il semaforo
* Ogni 10 spostamenti il movimento viene anche comunicato al ladro tramite la
* variabile globale showguardia
*/
void *guardia (void *arg)
{
int i = 0;
// Posizione iniziale : in basso a destra
pguardia.x = MAXX - 1;
pguardia.y = MAXY - 1;
pthread_mutex_lock (&semCurses); // Attendo che curses sia libero
mvaddch(pguardia.y,pguardia.x,'#'); // Disegno la guardia inizialmente
pthread_mutex_unlock (&semCurses); // libero curses
while(running) // Ciclo fino a che 'campo' non dice basta
{
char c;
c = getch(); // Legge il tasto
pthread_mutex_lock (&semCurses); // Attendo che curses sia libero
mvaddch(pguardia.y,pguardia.x,' '); // Cancello la vecchia guardia
pthread_mutex_unlock (&semCurses); // libero curses
if (c==SU && pguardia.y > 0) // Freccia SU
{
pguardia.y-=1; // Cala la y
}
if(c==GIU && pguardia.y < MAXY - 1) // Freccia GIU
{
pguardia.y+=1; // Cresce la y
}
if((c==SINISTRA)&&pguardia.x > 0) // Freccia SINISTRA
{
pguardia.x-=1; // Cala la x
}
if(c==DESTRA && pguardia.x < MAXX - 1) // Freccia DESTRA
{
pguardia.x+=1; // Cresce la x
}
pthread_mutex_lock (&semCurses); // Attendo che curses sia libero
mvaddch(pguardia.y,pguardia.x,'#'); // Disegno la guardia
refresh(); // Aggiorno le modifiche (canc. e disegno)
pthread_mutex_unlock (&semCurses); // libero curses
sem_post (&semGioco); // avviso il campo che c'e' stato un movimento
i++;
if(!(i%10))
{
showguardia = pguardia; // Rendo visibile la posizione al ladro
}
}
return NULL;
}
/* Funzione di controllo (padre).
* Attende 'eventi' sul semaforo.
*
* Visualizza un 'contasecondi', stampando il numero di spostamente del ladro diviso
* per cinque (il ladro fa' 5 movimenti al secondo)
*
* Se la posizione della guardia corrisponde a quella del ladro, termina il gioco.
*/
void campo ()
{
while(running) // Ciclo finche' non viene azzerato il flag
{
sem_wait (&semGioco); // Attendo che un figlio si muova
if ((nmov % 5) == 0) // Ogni 5 movimenti del ladro
{
pthread_mutex_lock (&semCurses); // Attendo che curses sia libero
mvprintw (MAXY,0,"T = %03d",nmov / 5); // Scrivo il tempo nell'ultima riga
curs_set(0); // Rielimino il cursore
refresh(); // Aggiorno le modifiche (canc. e disegno)
pthread_mutex_unlock (&semCurses); // libero curses
}
if(pguardia.x==pladro.x&&pguardia.y==pladro.y)
{ // Il ladro ha raggiunto la guardia
running = FALSE;
}
}
}
|
Per provare il programma, scaricare il sorgente,
compilarlo con il comando cc guardieladrit.c -o guardieladrit -lncurses -lpthread ed
eseguirlo con il comando ./guardieladrit.
[Home Page dell'ITIS "Fermi"]
[Indice Quarta]
[Precedente]
[Successivo]
© Ing. Stefano Salvi - Released under GPL licence
|