PDA

Visualizza la versione completa : [C][Esame Sistemi Operativi] Problema dei filosofi


Andrea Simonassi
04-01-2002, 12:59
philosophers.c


#include <sys/types.h>
#include <sys/ipc.h>
#include <sys/sem.h>
#include <stdio.h>
#include <string.h>
#include <unistd.h>
#include <time.h>
#include <signal.h>

#define N 5
#define MUTEX N
#define LOCK_STDOUT N + 1
#define POLL_INTERVAL 2

#define THINKING 0
#define HUNGRY 1
#define EATING 2

#if defined(__GNU_LIBRARY__) && !defined(_SEM_SEMUN_UNDEFINED)
/* union semun is defined by including <sys/sem.h> */
#else
/* according to X/OPEN we have to define it ourselves */
union semun {
int val; /* value for SETVAL */
struct semid_ds *buf; /* buffer for IPC_STAT, IPC_SET */
unsigned short int *array; /* array for GETALL, SETALL */
struct seminfo *__buf; /* buffer for IPC_INFO */
};
#endif

int semid;
int shmid;

struct statistica
{
int state;
time_t sec;
int eat;
}*State;

void down(int i);
void up(int i);
void think();
void eat ();
void poll_status();
void sigterm_hdl(int n);
void take_forks(int i);
void put_forks(int i);
void test(int i);
void philosopher(int i);

void poll_status()
{
int i;
int t;
char *messages[] = {"THINKING", "HUNGRY", "EATING"};

signal(SIGTERM, sigterm_hdl);
down(MUTEX);
printf("Processo poll pid %d\n", getpid());
up(MUTEX);
while(1)
{
down(MUTEX);
for(i=0; i<N;i++)
{
/*wmove(stdscr,i+1,1);*/
printf("filosofo %2d: %8s %6d", i, messages[State[i].state], State[i].eat);
if(State[i].state == HUNGRY)
printf(" %3d\n", time(NULL) - State[i].sec);
else
printf("\n");

/* wrefresh(stdscr);*/
}
printf("premere invio per terminare\n\n");
up(MUTEX);
sleep(POLL_INTERVAL);
}
}


void think ()
{
sleep(3);
}

void eat ()
{
sleep(3);
}


void down(int i)
{
struct sembuf g_lock_sembuf;
g_lock_sembuf.sem_num = i;
g_lock_sembuf.sem_op = -1;
g_lock_sembuf.sem_flg = 0;
if(semop(semid, &g_lock_sembuf, 1) == -1)
{
perror("semop fallita ");
exit(1);
}
if(i == MUTEX)
{
printf("*************** %d in sezione critica\n" , getpid());
fflush(stdout);
}
}

void up(int i)
{
struct sembuf g_lock_sembuf;
g_lock_sembuf.sem_num = i;
g_lock_sembuf.sem_op = 1;
g_lock_sembuf.sem_flg = 0;
if(semop(semid, &g_lock_sembuf, 1) == -1)
{
perror("semop fallita ");
exit(1);
}
if(i == MUTEX)
{
printf("+++++++++++++++ %d lascia sezione critica\n" , getpid());
fflush(stdout);
}
}
int main ()
{
ushort sems[N+1];
int i, j, ActiveProcesses=0;
pid_t PIDS[N+1];
int retcode = 0;

union semun {
int val;
struct semid_ds *stat;
ushort *array;
} ctl_arg;

semid = shmid = -1;

/*initscr();
wclear(stdscr);*/

srand(time(NULL));

ctl_arg.array = sems;

semid = semget(0, N+1, 0666 | IPC_PRIVATE);

if (semid == -1)
{
perror ("Impossibile ottenere semafori dal sistema.");
retcode = 1;
goto cleanup;
}
else
{
printf("semafori creati\n");
}

shmid = shmget(0, N*sizeof(struct statistica), 0666 | IPC_PRIVATE);

if(shmid == -1)
{
perror("Impossibile allocare memoria condivisa\n");
retcode = 2;
goto cleanup;
}
else
{
printf("memoria condivisa creata\n");
}

for(i=0; i<N+1; i++)
sems[i]=0;

if(semctl(semid, 0, SETALL, ctl_arg)==-1)
{
perror("Impossibile impostare i semafori");
retcode = 2;
goto cleanup;
}
else
{
printf("semafori inizializzati\n");
}

State = (struct statistica*) shmat(shmid, 0, 0);


printf("Processo main pid %d\n", getpid());


//il mutex è down i base all'inizializzazione

for(ActiveProcesses=0, i=0; i<N;i++, ActiveProcesses++)
{
PIDS[i] = fork();
{
if(PIDS[i]==-1)
{
fprintf(stderr, "Impossibile creare il processo %d\n", i);
retcode = 3;
goto cleanup;
}
else if(PIDS[i] == 0)
{
State[i].state = 0;
State[i].sec = 0;
State[i].eat = 0;
philosopher(i); //il filosofo non parte finchè mutex down
}
}
}

PIDS[i] = fork();
{
if(PIDS[i]==-1)
{
fprintf(stderr, "Impossibile creare il processo %d\n", i);
retcode = 3;
goto cleanup;
}
else if(PIDS[i] == 0)
{
poll_status(); /*Inizia il polling dello stato dei filosofi*/
}
}

ActiveProcesses++;
/*wmove(stdscr, i, 1); */
printf("Premere invio per terminare\n\n");
/*wrefresh(stdscr);*/
up(MUTEX);

getchar();
cleanup:



for(i=0;i<ActiveProcesses;i++) //raccoglie retcode di tutti i figli
{
kill(PIDS[i], SIGTERM); //avvisa tutti i figli di terminare
fprintf(stderr, "waitpid %d ", PIDS[i]);
if(waitpid(PIDS[i], &j, 0)==-1)
perror("waitpid fallita\n");
else
fprintf(stderr, "= %d\n", j);
}

if(semid!=-1 && semctl(semid, 0, IPC_RMID, 0)==-1) //rimuove semafori
perror("impossibile rimuovere set di semafori\n");
else printf("Semafori chiusi\n");

if(shmid!=-1 && shmctl(shmid, 0, IPC_RMID, 0)==-1) //rimuove memoria condivisa
perror("Impossibile rimuovere memoria condivisa\n");
else printf("Memoria condivisa liberata\n");

/*endwin();*/ //dealloca il terminale virtuale
return retcode;
}


void philosopher (int i)
{
signal(SIGTERM, sigterm_hdl);
down(MUTEX);
printf("Salve, sono il filosofo %d con pid %d\n", i, getpid());
up(MUTEX);
while(1)
{
think();
take_forks(i);
eat();
put_forks(i);
}
}

void take_forks(int i)
{
down(MUTEX);
State[i].state = HUNGRY;
State[i].sec = time(NULL);
test(i);
up(MUTEX);
down(i);
}

#define LEFT (i-1)%N
#define RIGHT (i+1)%N

void put_forks(int i)
{
down(MUTEX);
State[i].state = THINKING;
test(LEFT);
test(RIGHT);
up(MUTEX);
}



void test(int i)
{
if(State[i].state == HUNGRY && State[LEFT].state!= EATING && State[RIGHT].state!=EATING)
{
State[i].state = EATING;
State[i].sec = 0;
State[i].eat ++;
up(i);
}
}


void sigterm_hdl(int n)
{
exit(0);
}

Andrea Simonassi
04-01-2002, 13:01
Ho pensato bene di risolvere il ben noto problema dei filosofi affamati di Dikstra.

Ho pensato bene di farlo in C su Linux, per motivi politico-universitari.

Ora odio i filosofi, crepassero di fame sti maiali.

Il problema è che ho N + 1 semafori che uso come mutex, ovvero mi servono per delimitare sezioni critiche, il questito è perchè non lo fanno? In pratica mi capita di avere 2 processi in sezione critica.

Vi posto il sorgente in modo possiate compilarlo e spero che qualche pio individuo abbia già risolto sto belin di problema.

Credo sia sbagliata la down oppure l'inizializzazione semctl, se qualcuno sa, mi aiuti.

Grazie.

Andrea Simonassi
04-01-2002, 13:03
E' interessante notare che cambiando le sleep nelle funzioni think e eat l'ultimo filosofo non muore di fame, ma ottiene il processore meno degli altri, in ogni caso.

Andrea Simonassi
04-01-2002, 15:13
A nu me voe aggiuttà nisciun?

sei propriu de legere :)

se qualcuno ha usato le sezioni critiche in Linux dovrebbe vedere se ho cappellato qualcosa, non so dove cercare l'errore se nella down, nella up, o dove altro.

M3xican
05-01-2002, 00:30
Ho il programma fatto x il mod B! :)
A parte gli scherzi, vedrò di compilarlo e di farti sapere.

M3xican
05-01-2002, 00:31
Io odio i filosofi...
sono solo dei parassiti!
Facile "pensare" soltanto!

Andrea Simonassi
05-01-2002, 00:50
Grazie M3xican, siccome ho fatto un milione di modifiche al codice per vedere cosa non va, c'era della roba di troppo che ho cancellato dal listato, spero che si compili lo stesso, ora lo provo.

Volevo anche dire che queste istruzioni di debug
if(i == MUTEX)
{
printf("+++++++++++++++ %d lascia sezione critica\n" , getpid());
fflush(stdout);
}

nella funzione up(int i) vanno spostate prima di tirare su il semaforo, me ne sono accorto rileggendo il codice.



void up(int i)
{
struct sembuf g_lock_sembuf;
g_lock_sembuf.sem_num = i;
g_lock_sembuf.sem_op = 1;
g_lock_sembuf.sem_flg = 0;

if(i == MUTEX)
{
printf("+++++++++++++++ %d lascia sezione critica\n" , getpid());
fflush(stdout);
}

if(semop(semid, &g_lock_sembuf, 1) == -1)
{
perror("semop fallita ");
exit(1);
}
}

Andrea Simonassi
08-01-2002, 00:55
Ci ho studiato su, il problema per cui l'ultimo filosofo moriva di fame era la sleep.

Prima blocco tutti i processi con il mutex e poi addormento il processo bloccante per 3 secondi! Poco saggio.
L'ho sostituito con un milione di moltiplicazioni di double.

Il motivo in cui non veniva rispettato il fatto che due filosofi adiacenti non potessero mangiare era un errore nella macro LEFT.

Infatti LEFT (i-1)%N se i=0 restituisce -1 è già tanto se non ho avuto segmentation fault. Il bello che quella macro l'ho copiata dal libro di Sistemi operativi, l'avessi fatta io forse me ne sarei accorto del casino.

sostituita con LEFT i==0?N-1:i-1

ora funziona.

Chi deve dare S.O. puo darci un'occhiata.

ah, ho sostituito il polling (poll_status) con delle chiamate selettive, quindi è bene che la think e la eat siano abbastanza lunghe se si vuole avere il tempo di leggere l'output.

Qua sotto il codice funzionante.

Adesso che sono in pace con i filosofi mi andro' a comprare "Il male" di San Tommaso.

Andrea Simonassi
08-01-2002, 00:58
#include <sys/types.h>
#include <sys/ipc.h>
#include <sys/sem.h>
#include <stdio.h>
#include <string.h>
#include <unistd.h>
#include <time.h>
#include <signal.h>

#define N 5
#define MUTEX N
#define POLL_INTERVAL 2

#define THINKING 0
#define HUNGRY 1
#define EATING 2
/* #define DDEBUG */

#define T_ITER 700 /* tempo in cui pensa = T_ITER^2 * T(moltiplicazione su double) */
#define E_ITER 700 /* tempo in cui mangia (in iterazioni)*/

#if defined(__GNU_LIBRARY__) && !defined(_SEM_SEMUN_UNDEFINED)
/* union semun is defined by including <sys/sem.h> */
#else
/* according to X/OPEN we have to define it ourselves */
union semun {
int val; /* value for SETVAL */
struct semid_ds *buf; /* buffer for IPC_STAT, IPC_SET */
unsigned short int *array; /* array for GETALL, SETALL */
struct seminfo *__buf; /* buffer for IPC_INFO */
};
#endif

int semid;
int shmid;
struct statistica
{
int state;
time_t sec;
int eat;
pid_t pid;
}*State;

void down(int i);
void up(int i);
void think();
void eat ();
void print_status();
void sigterm_hdl(int n);
void take_forks(int i);
void put_forks(int i);
void test(int i);
void philosopher(int i);

void print_status()
{
int i;
int t;
char *messages[] = {"THINKING", "HUNGRY", "EATING"};
printf("PID: %d\n", getpid());
for(i=0; i<N;i++)
{
printf("filosofo %2d [%d]: %8s %6d", i, State[i].pid, messages[State[i].state], State[i].eat);
if(State[i].state == HUNGRY)
printf(" %3d\n", time(NULL) - State[i].sec);
else
printf("\n");
}
printf("\n\n");
}

void think ()
{
int i;
int j;
double a=1.1, b=1.0;
for(i=0;i<T_ITER;i++)
for(j=0;j<T_ITER;j++)
a=a*b;
}

void eat ()
{
int i;
int j;
double a=1.1, b=1.0;
for(i=0;i<E_ITER;i++)
for(j=0;j<E_ITER;j++)
a=a*b;
}


void down(int i)
{
struct sembuf g_lock_sembuf;
g_lock_sembuf.sem_num = i;
g_lock_sembuf.sem_op = -1;
g_lock_sembuf.sem_flg = 0;
if(semop(semid, &g_lock_sembuf, 1) == -1)
{
perror("semop fallita ");
exit(1);
}
/* if(i == MUTEX)
{
printf("*************** %d in sezione critica\n" , getpid());
fflush(stdout);
}*/
}

void up(int i)
{
struct sembuf g_lock_sembuf;
g_lock_sembuf.sem_num = i;
g_lock_sembuf.sem_op = 1;
g_lock_sembuf.sem_flg = 0;

/* if(i == MUTEX)
{
printf("+++++++++++++++ %d lascia sezione critica\n" , getpid());
fflush(stdout);
}*/
if(semop(semid, &g_lock_sembuf, 1) == -1)
{
perror("semop fallita ");
exit(1);
}

}

int main ()
{
ushort sems[N+1];
int i, j, ActiveProcesses=0;
pid_t PIDS[N+1];
int retcode = 0;

union semun {
int val;
struct semid_ds *stat;
ushort *array;
} ctl_arg;

semid = shmid = -1;

/*initscr();
wclear(stdscr);*/

srand(time(NULL));

ctl_arg.array = sems;

semid = semget(0, N+1, 0666 | IPC_PRIVATE);

if (semid == -1)
{
perror ("Impossibile ottenere semafori dal sistema.");
retcode = 1;
goto cleanup;
}
else
{
printf("semafori creati\n");
}

shmid = shmget(0, N*sizeof(struct statistica), 0666 | IPC_PRIVATE);

if(shmid == -1)
{
perror("Impossibile allocare memoria condivisa\n");
retcode = 2;
goto cleanup;
}
else
{
printf("memoria condivisa creata\n");
}

for(i=0; i<N+1; i++)
sems[i]=0;

if(semctl(semid, 0, SETALL, ctl_arg)==-1)
{
perror("Impossibile impostare i semafori");
retcode = 2;
goto cleanup;
}
else
{
printf("semafori inizializzati\n");
}

State = (struct statistica*) shmat(shmid, 0, 0);


printf("Processo main pid %d\n", getpid());


printf("premi un tasto");
getchar();
fflush(stdin);
fflush(stdout);


//il mutex è down i base all'inizializzazione

for(ActiveProcesses=0, i=0; i<N;i++, ActiveProcesses++)
{
PIDS[i] = fork();
{
if(PIDS[i]==-1)
{
fprintf(stderr, "Impossibile creare il processo %d\n", i);
retcode = 3;
goto cleanup;
}
else if(PIDS[i] == 0)
{
State[i].state = 0;
State[i].sec = 0;
State[i].eat = 0;
philosopher(i); //il filosofo non parte finchè mutex down
}
}
}
printf("Premere invio per terminare\n\n");
up(MUTEX);

getchar();
cleanup:



for(i=0;i<ActiveProcesses;i++) //raccoglie retcode di tutti i figli
{
kill(PIDS[i], SIGTERM); //avvisa tutti i figli di terminare
fprintf(stderr, "waitpid %d ", PIDS[i]);
if(waitpid(PIDS[i], &j, 0)==-1)
perror("waitpid fallita\n");
else
fprintf(stderr, "= %d\n", j);
}

if(semid!=-1 && semctl(semid, 0, IPC_RMID, 0)==-1) //rimuove semafori
perror("impossibile rimuovere set di semafori\n");
else printf("Semafori chiusi\n");

if(shmid!=-1 && shmctl(shmid, 0, IPC_RMID, 0)==-1) //rimuove memoria condivisa
perror("Impossibile rimuovere memoria condivisa\n");
else printf("Memoria condivisa liberata\n");

/*endwin();*/ //dealloca il terminale virtuale
return retcode;
}


void philosopher (int i)
{
signal(SIGTERM, sigterm_hdl);
down(MUTEX);
printf("Salve, sono il filosofo %d con pid %d\n", i, getpid());
up(MUTEX);
State[i].pid = getpid();
while(1)
{
think();
take_forks(i);
eat();
put_forks(i);
}
}

void take_forks(int i)
{
down(MUTEX);
State[i].state = HUNGRY;
State[i].sec = time(NULL);
test(i);
print_status();
up(MUTEX);
down(i);
}

#define LEFT i==0?N-1:i-1
#define RIGHT (i+1)%N

void put_forks(int i)
{
down(MUTEX);
State[i].state = THINKING;
test(LEFT);
test(RIGHT);
print_status();
up(MUTEX);
}



void test(int i)
{
#ifdef DDEBUG
printf("i=%d left=%d, right=%d\n",i, LEFT, RIGHT);
#endif
if(State[i].state == HUNGRY && State[LEFT].state!= EATING && State[RIGHT].state!=EATING)
{
State[i].state = EATING;
State[i].sec = 0;
State[i].eat ++;
up(i);
}
}


void sigterm_hdl(int n)
{
exit(0);
}

M3xican
08-01-2002, 01:35
Nn avevo ancora trovato il tempo di compilare il vecchio sorgente perkè sono impegnato in un dannato progetto di un dannatissimo vocabolario x delle dannatissime parole crociate.
Vedrò di compilare la tua ultima release :)

Loading