Help: Algoritmo del Fornaio

[::tony design]

Ciao a tutti, il 6 aprile ho l'orale di Sistemi Operativi! :eek:
Qualcuno sa spiegarmi per benino l'algoritmo del fornaio?

---------- ALGORITMO DEL FORNAIO ------------
do {
scelta[i] = true;
numero[i] = max(numero[0], numero[1], … , numero[n – 1]) + 1;
scelta[i] = false;
for (j = 0; j < n; j++)
{
while (scelta[j]) ;
while ((numero[j] != 0) && ((numero[j], j) < (numero[i], i))) ;
}

sezione critica

numero[i] = 0;

sezione non critica
} while (1);
--------------------------------------------------------


Poi vi chiederò anche per l'algoritmo dei filosofi!!
Cmq per adesso preferirei capire bene questo algoritmo del fornaio!!!

Grazie a tutti coloro che mi aiuteranno....

::tony

[Luc@s]

quello dei filosofi c'è sul mio Tannenbaum................quello del fornaio mi sembra di no.
Ma nn era ieri il tuo esame?

[::tony design]

Originariamente inviato da Luc@s
quello dei filosofi c'è sul mio Tannenbaum................quello del fornaio mi sembra di no.


Non sapresti spiegarmi uno dei due algoritmi!!
O quello dei filosofi o quello del fornaio!!

Ti ringrazio...

[Luc@s]

Originariamente inviato da ::tony design
Non sapresti spiegarmi uno dei due algoritmi!!
O quello dei filosofi o quello del fornaio!!

Ti ringrazio...

Ora me lo leggo e ti faccio una spiegazione

[::tony design]

Originariamente inviato da Luc@s
Ora me lo leggo e ti faccio una spiegazione


Ti ringrazio davvero tanto...

[Luc@s]

Nel 1965 Dijkstra formulò e risolse il problema dei filosofi a cena(dining philosopher problem).
Il problema puo essere formulato come segue:
5 filosofi sono seduti attorno ad un tavolo tondo e ciacuno ha un piatto di spaghetti;gli spaghetti sono cosi scivolosi che per poterli mangiare ogni filosofo deve avere 2 forchette;fra ogni coppia di piatti vi è una forchetta.
La vita dei filosofi alterna periodi in cui essi pensano ad altri in cui mangiano(questa è, in qualche modo, un'astrazione, persino per i filosofi, ma le altre attivita sono qui irrilevanti).
Quando un filosofo comincia ad avere fame, cerca di prendere possesso della forchetta che gli sta a sinistra e di quella che gli sta a destra, una alla volta ed in ordine arbitrario.
Qaulora riesca a prendere entrambe le forchette, mangia per un po' e, successivamente, depone le forchette e continua a pensare.

[Luc@s]

ora ti posto pure il mio cod di esempio

[Luc@s]

Una soluzione in C++


#define N 5 // i filosofi
#define SINISTRA (i + N - 1)%N // numero vicino di sinistra di i
#define DESTRA (i+1)%N // numero vicino di destra di i
#define PENSANTE 0
#define AFFAMATO 1
#define MANGIANTE 2

typedef int semaforo;
int stato[N];
semaforo mutex = 1; // esclusione mutua regione critica
semaforo s[N]; // semaforo x1 filosofo

void filosofo(int i)
{
while(TRUE)
{
pensa();
prendi_forchette(i);
mangia();
posa_forchette(i);
}
}

void prendi_forchette(int i)
{
down(&mutex); // entra regione critica
stato[i] = AFFAMATO;
test(i);
up(&mutex);// esce regione critica
down(&s[i]); // si blocca se forchette nn ottenute
}

void posa_forchette(int i)
{
down(&mutex); // entra regione critica
stato[i] = PENSANTE;
test(DESTRA); // vicino destra puo mangiare??
test(SINISTRA);// vicino sinistra puo mangiare??
up(&mutex);// esce regione critica
down(&s[i]); // si blocca se forchette nn ottenute
}

void test(int i)
{
if(stato[i] == AFFAMATO && stato[SINISTRA] != MANGIANTE && stato[DESTRA] != MANGIANTE)
{
stato[i] = MANGIANTE;
up(&s[1]);
}
}

[::tony design]

Guarda.. ora mi sbatto un po' e vedo per bene tutto l'algoritmo!!
Non sò come ringraziarti...

sei stati davero cortese!!Grazie

::tony;)

[Luc@s]

Originariamente inviato da ::tony design
Guarda.. ora mi sbatto un po' e vedo per bene tutto l'algoritmo!!
Non sò come ringraziarti...

sei stati davero cortese!!Grazie

::tony;)

Di nulla.
In + scrivendolo lo ho appreso meglio.
Cmq il cod prendilo con le pinze lo ho fatto in 2 minuti al notepad.

[Fenomeno85]

che bellezza l'avevamo visto l'anno scorso l'algoritmo dei filosofi :)

~§~ Sempre E Solo Lei ~§~

[Luc@s]

Originariamente inviato da Fenomeno85
che bellezza l'avevamo visto l'anno scorso l'algoritmo dei filosofi :)

~§~ Sempre E Solo Lei ~§~

Tu dove studi?

[Fenomeno85]

Originariamente inviato da Luc@s
Tu dove studi?

itis spe info ... fatto in sistemi con il libro .. sistemi operativi se non ricordo male il nome

~§~ Sempre E Solo Lei ~§~

[Luc@s]

Originariamente inviato da Fenomeno85
itis spe info ... fatto in sistemi con il libro .. sistemi operativi se non ricordo male il nome

~§~ Sempre E Solo Lei ~§~

2° anno liceo classico...............autodidatta :D

[Fenomeno85]

Originariamente inviato da Luc@s
2° anno liceo classico...............autodidatta :D

e va be :D

~§~ Sempre E Solo Lei ~§~

[::tony design]

Complimentoni Luc@s !!!

Io invece sono al secondo anno della Laurea in Informatica!!!

;)

[Luc@s]

cmq vedo se riesco a trovare info anche sull'altro algo:D

[Luc@s]

Originariamente inviato da Fenomeno85
e va be :D

~§~ Sempre E Solo Lei ~§~

va be cosa?:D

[Fenomeno85]

Originariamente inviato da Luc@s
va be cosa?:D

che saranno mai 2 anni di differenza :D

~§~ Sempre E Solo Lei ~§~

[::tony design]

Originariamente inviato da Luc@s
cmq vedo se riesco a trovare info anche sull'altro algo:D


Grazie Luc@s

[dr.stein]

lo scopo dell'algoritmo qual'e' ?

[Luc@s]

i thread e i processi ed evitare i deadlock credo :D

[cn73]

Evitare il deadlock ma anche la starvation (morte per fame, attesa indefinita) di uno dei processi... Una soluzione corretta deve evitare entrambe... Il problema dei filosofi è un classico :)

[cionci]

Comunque l'implementazione dei semafori nell'algo postato è puramente virtuale... I semafori devono essere realizzati con le system call del SO...

[cn73]

esatto...si presume che l'esercizio sia proposto per un sistema Unix o Linux, perciò vai di

man semget
man semctl
man semop

il C ti permette di usarle direttamente...

cionci mi puoi dare un ocio al topoc sull'IPC? :D

[Luc@s]

Originariamente inviato da cionci
Comunque l'implementazione dei semafori nell'algo postato è puramente virtuale... I semafori devono essere realizzati con le system call del SO...

infatti la mia implementazione era generica.
Il resto è lasciato all'autore dell post :D

[Luc@s]

come ' è andata poi?

[gokan]

Originariamente inviato da cionci
Comunque l'implementazione dei semafori nell'algo postato è puramente virtuale... I semafori devono essere realizzati con le system call del SO...
Infatti ho già chiesto a qualcuno di darmi una mano a scrivere il codice C "reale" e non virtuale e non ho ottenuto grandi aiuti!!!
Capire l'algoritmo non è complicato il problema è implementarlo realmente!!

X Lucas
Sei bravo a fare da autodidatta, però una cosa è capire, un'altra è scopiazzare dal testo del grande A.S Tanenbaum :sofico:

[Luc@s]

Originariamente inviato da gokan
X Lucas
Sei bravo a fare da autodidatta, però una cosa è capire, un'altra è scopiazzare dal testo del grande A.S Tanenbaum :sofico:

:p
Beccato.
Cmq grande A.S Tanenbaum :D :D

[gokan]

Vero, Tanenbaum è un grande, i suoi testi sono sempre molto chiari...
Ritornando in tema, riguardo il problema dei filosofi a cena, tutto il problema sta nel fare in modo che mangino almeno due filosofi e che quindi due thread non si "disturbino" a vicenda...
Diciamo che la non-soluzione (per restare in tema del Tanenbaum) l'ho implementata, la soluzione ottimale non sono riuscita a farla invece, non ho ancora capito bene il perchè, qualcuno di voi l'ha mai scritta in C?

Ciao

[khamel]

se interessa la soluzione dei filosofi in java, sia con i monitor che con i semafori ve la posto solo che è un po lunghina....

[Luc@s]

posta.:D

[khamel]

Soluzione con i monitor di hoare (in allegato le altre classi richieste) :

public class diningPhilosophers extends Monitor{
int[] state = new int[5];
static final int THINKING = 0;
static final int HUNGRY = 1;
static final int EATING = 2;
condition[] self = new condition[5];
public diningPhilosophers {
for (int i = 0; i < 5; i++)
state[i] = THINKING;
}
public void pickUp(int i) {
entraMonitor();
state[i] = HUNGRY;
test(i);
if (state[i] != EATING)
self[i].wait;
esciMonitor();
}

public void putDown(int i) {
entraMonitor();
state[i] = THINKING;
// verifica i vicini sinistro e destro
test((i + 4) % 5);
test((i + 1) % 5);
esciMonitor();
}

private void test(int i) {
if ( (state[(i + 4) % 5] != EATING) &&
(state[i] == HUNGRY) &&
(state[(i + 1) % 5] != EATING) ) {
state[i] = EATING;
self[i].signal;
}
}
}

[khamel]

Soluzioni con semafori :

utilizzando la classe allegata !!!

prendete quello con i monitor postato prima, sostuite ogni condition aggiungete un semaforo, in più aggiungete un semaforo per la mutua esclusione al posto del monitor...

[khamel]

naturalmente non è farina del mio sacco è la roba che ci spiegano all'università....

[gokan]

Peccato che sconosco complemetamente il Java, mi interessava la soluzione con i semafori :(

[cionci]

Se non ci dici per quale sistema operativo ti interessano le system call non possiamo aiutarti ;)

[gokan]

Sotto windows usando visual C.
In pratica il mio problema sta nel fatto, che sebbene regoli l'accesso alla regione critica con un mutex inizialmente in uno stato "signaled" (quindi libero), non riesco a fare mangiare mai nessun filosofo, in pratica ho un deadlock bello e buono.

hMutex=CreateMutex(NULL,true,"mutex");

Allego la mia attuale versione non funzionante.

[cionci]

Ecco qua...

[cn73]

Io l'ho appena scritta...in C puro però. Però non intenderei darla via come sae non fosse mia :D. Intendo dire, se hai qualche problema chiedi pure ;)

Ho semplicemente definito 2 funzioni:


int down(int semid, int sem) {

struct sembuf sops;
sops.sem_num = sem; /* operazione sul semaforo sem */
sops.sem_op = -1; /* decrementa il semaforo di 1 */
sops.sem_flg = 0; /* che fare: ?? */

return semop(semid,&sops ,1);
}

int up(int semid, int sem) {

struct sembuf sops;
sops.sem_num = sem; /* operazione sul semaforo sem */
sops.sem_op = 1; /* incrementa il semaforo di 1 */
sops.sem_flg = 0; /* che fare: ?? */

return semop(semid,&sops ,1);
}

L'algoritmo dei filosofi ti è stato escritto sopra...
Devi generare un processo padre che istanzia le risorse condivise (un array di semafori per i filosofi, un segmeno di memoria condivisa per i filosofi) e che lancia con delle exec N filosofi (il problema dei 5 filosofi e immediatamente generalizzabile a N filosofi... il numero di semafori che un array può contenere è dato dal sistema operativo, per Linux è 250).

[gokan]

Originariamente inviato da cionci
Ecco qua...
grazie Cionci, ho visto dove commettevo gli errori (grazie anche ai tuoi commenti).
Ho un piccolo dubbio nella prendiFork:

printf("il filosofo %d ha preso anche la forchetta sinistra e inizia a mangiare\n",c+1);
mangia(c);
ReleaseSemaphore(hforchetta[LEFT],1,NULL); //sbagliato qui
ReleaseSemaphore(hforchetta[RIGHT],1,NULL);//andavano rilasciati entrambi i semafori


Io non mettevo dopo la funzione mangia(c), il rilascio dei semafori, tu li hai messi
per fare in modo che venissero mollate le forchetta alla fine della "mangiata", giusto?

Spostare:
ReleaseSemaphore(hforchetta[LEFT],1,NULL); //sbagliato qui
ReleaseSemaphore(hforchetta[RIGHT],1,NULL);//andavano rilasciati entrambi i semafori

nella funzione lasciafork e precisamente facendo:

case WAIT_OBJECT_0:
ReleaseSemaphore(hforchetta[LEFT],1,NULL); //sbagliato qui
ReleaseSemaphore(hforchetta[RIGHT],1,NULL);//andavano rilasciati entrambi i semafori
printf("il filosofo %d sta per smetter di mangiare (lascia le forchette)\n",c+1);
printf("il filosofo %d sta iniziando a pensare\n",c+1);
stato[c]=THINKING; //il filosofo pensa

test(LEFT);
test(RIGHT);
ReleaseMutex(hMutex);
break;


Ottengo gli stessi risultati? Effettivamente eseguendo il codice sembra che non
cambi nulla, tu che ne dici? Forse è più corretto (più ordinato forse)
rilasciare i semafori nella lasciaFork ?

Grazie ancora, (cmq mi aspettavo peggio dal mio codice, qualcosa di giusto l'avevo
scritto :))

[cionci]

Sì...dovrebbe essere la stessa cosa...
L'errore principale è che avevi inizializzato la mutex a true e quindi nessuno poteva più prenderla...

[gokan]

Hai ragione ;)