[C]Spiegazione funzionamento fork() e wait

[Hybr1d97]

Studiando la clonazione dei processi in ambiente Linux, il libro riporta un esempio in cui si ha questa struttura:

struct UTENTE{
char denominazione[32];
char telefono[16];
};

struct UTENTE elenco[1000000];

Posto "elenco" come vettore non ordinato, volendo risparmiare tempo nel cercare sequenzialmente un nome in base al numero di telefono, adotta il multitasking, in questo modo:

int main(){
char numero[16];
int i, r, s;

printf("Inserire numero: ");
scanf("%s", numero);

r = fork();

if (r<0){
printf("Errore!\n");
return;
}
if (r>0){ //processo padre: ricerca nella 1° pt. del vettore
for (i = 0; i < 1000000 / 2; i++){
if (strcmp(numero, elenco[i].telefono) == 0){
printf("L'utente e' %s.\r\n", elenco[i].denominazione);
break;
}
}
wait(&s);
return;
}
else{ //processo figlio: ricerca nella 2° pt. del vettore
for (i = 1000000 / 2; i < 1000000; i++){
if (strcmp(numero, elenco[i].telefono) == 0){
printf("L'utente e' %s.\r\n", elenco[i].denominazione);
break;
}
return;
}
}
}


Ora, partendo dal fatto che non ho capito proprio bene la funzione wait, ho dei dubbi riguardo l'efficienza di questo programma: mettiamo infatti che il processo padre trovi il numero al primo tentativo, uscirebbe dal ciclo for ed aspetterebbe che, nel frattempo, finisca di cercare anche il processo figlio.

Questo non è uno spreco, se messo davanti a come sarebbe stata la ricerca senza multitasking?

Molto evidentemente mi sto sbagliando io per qualche mia incomprensione. Se è così, qualcuno può spiegarmelo?

[dyablo96]

1)Ora, partendo dal fatto che non ho capito proprio bene la funzione wait

2)ho dei dubbi riguardo l'efficienza di questo programma: mettiamo infatti che il processo padre trovi il numero al primo tentativo, uscirebbe dal ciclo for ed aspetterebbe che, nel frattempo, finisca di cercare anche il processo figlio.

Questo non è uno spreco, se messo davanti a come sarebbe stata la ricerca senza multitasking?

1)il wait detto in parole povere fa in modo che il padre a spetti il processo figlio che termina e poi termina anche lui.

2)mettiamo caso che il numero che cerchi si trova al primo posto dell'elenco, in quel caso il padre lo trova subito e quindi attenderà che il figlio faccia la sua ricerca.
in questo caso sarrebbe un pò uno spreco come dici tu.
ma mettiamo caso che invece il numero che cerchi è nella penultima posizione, in questo caso invece il padre scorre tutto il vettore senza trovarlo mentre il figlio lo trova al penultimo.
in questo caso la prallelizazione è molto efficace.

spero di essere stato abbastanza chiaro :)

[Hybr1d97]

Ma che senso ha in questo caso usare il fork? Qui si ha una complessità fissa di N (che poi in realtà impiega la metà quindi diciamo n/2), mentre con un processo singolo n/2 sarebbe stata la complessità media! :doh:

[kwb]

Il processo singolo avrebbe dovuto, nel caso peggiore, passare in rassegna l'intero vettore.
Così facendo invece i 2 processi si passano solo mezzo vettore a testa.

[Hybr1d97]

Ma non c'è un modo per far sì che l'altro processo si blocchi? Una sorta di "break" tra processi, ad esempio se il processo padre trova subito l'elemento allora fa in modo che il figlio blocchi la ricerca e si chiuda.

[kwb]

Credo si debbano utilizzare i segnali, includere quindi la libreria signal.h e utilizzare SIGKILL:

kill(pid, SIGKILL);


Devi anche salvarti il process ID del processo figlio.

EDIT: Così facendo però interrompi bruscamente la ricerca. Quindi in questo esempio penso funzioni bene, in caso di lettura/scrittura su file potrebbero insorgere diversi casini...

[Hybr1d97]

Effettivamente... Comunque grazie, ora ho tutto un po' più chiaro.
Ovviamente approfondirò ;)

[dyablo96]

Potresti utilizzare i semafori per bloccare uno dei due processi nel caso in cui l'altro trovi una corrispondenza

[Hybr1d97]

Potresti utilizzare i semafori per bloccare uno dei due processi nel caso in cui l'altro trovi una corrispondenza
Puoi farmi un esempio con codice?

[kwb]

Se proprio vuoi utilizzare un semaforo, puoi utilizzare un mutex: è un semaforo molto semplice ( il più semplice forse ) che permette di bloccare un processo. Richiede l'utilizzo delle funzioni pipe() (http://digilander.libero.it/uzappi/C/librerie/funzioni/pipe.html), read() (http://digilander.libero.it/uzappi/C/librerie/funzioni/read.html) e write() (http://digilander.libero.it/uzappi/C/librerie/funzioni/write.html).

Come ti spiega il link che ho messo sulla pipe, se chi legge trova la pipe vuota si blocca e attende che arrivi qualcosa.

Qui un esempio:

int main (int argc, const char * argv[])
{
int fd[2]; // Il file descriptor per la pipe. Su fd[1] si scrive, su fd[0] si legge
/*
** dummy1 e dummy2 sono vettori di un singolo carattere.
** Devo fare cosi' perche' le funzione read() e write() vogliono un puntatore
*/
char dummy1[1]={0}, dummy2[1]={0};

if((pipe(fd))== -1)
{
printf("Error in pipe\n");
return -1;
}

write(fd[1], "G", 1); //Scrivo un carattere per sbloccare tutti i processi

if(fork()==0) //Figlio 1
{
read(fd[0], dummy1, 1); //Prendo dalla pipe il carattere (se c'e')
write(fd[0], NULL, 1); //Svuoto l'uscita della pipe, cosi' nessun processo potra' partire

/*
** In questo punto del codice il figlio 1 ha il controllo completo.
** Gli altri processi sono bloccati finche' la pipe non viene rilasciata
*/

write(fd[1], "G", 1); //Sblocco gli altri processi
exit(0);
}
else if(fork()==0) //Figlio 2
{
read(fd[0], dummy2, 1);
write(fd[0], NULL, 1);

/*
** In questo punto del codice il figlio 2 ha il controllo completo.
** Gli altri processi sono bloccati finche' la pipe non viene rilasciata
*/

write(fd[1], "G", 1); //Sblocco gli altri processi
exit(0);
}
wait(NULL);
wait(NULL);
return 0;
}


EDIT: Devi aggiungere la libreria unistd.h come indicato nei link!!

[Hybr1d97]

Se proprio vuoi utilizzare un semaforo, puoi utilizzare un mutex: è un semaforo molto semplice ( il più semplice forse ) che permette di bloccare un processo. Richiede l'utilizzo delle funzioni pipe() (http://digilander.libero.it/uzappi/C/librerie/funzioni/pipe.html), read() (http://digilander.libero.it/uzappi/C/librerie/funzioni/read.html) e write() (http://digilander.libero.it/uzappi/C/librerie/funzioni/write.html).

Come ti spiega il link che ho messo sulla pipe, se chi legge trova la pipe vuota si blocca e attende che arrivi qualcosa.

Grazie per l'esempio e i link, me li studierò. Comunque, tutto sommato, se è vero che pure eseguendo il processo a 4 core la complessità è in media N/2 per il processo padre e sempre N per tutti gli altri processi, è anche vero che comunque il numero di controlli non supererà mai quello che sarebbe stato N/4 senza esecuzione in parallelo! Diciamo che sono due facce della stessa medaglia.

Comunque, il mio libro riporta questo:

La segnalazione di un evento a un processo diverso richiede infatti l'invocazione di specifiche funzioni API del sistema operativo - complessivamente denominate IPC, Inter-Process Communication - il cui studio sarà oggetto del prossimo volume.

Caspita, questo libro sa come lasciare suspense, sembra un film :cry:

[dyablo96]

oltre all'esempio molto utile di kwb ti lascio un link in cui spiegano come utilizzare i thread e i semafori clicca qui (https://computing.llnl.gov/tutorials/pthreads/#PthreadsAPI).

come diceva kwb ti conviene usare un semaforo mutex che è molto semplice.
immaginalo come se avesse un valore binario ovvero 0 o 1 il processo quando incontra questo semaforo controlla se può accedere all'area oppure viene bloccato.
possono essere utilizzati per impedire che più processi entrino in una parte critica di un programma in contemporanea.
ma nel tuo caso si può fare in modo che un processo blocchi l'altro.

all'inizio del programma crei il semaforo e lo imposti a verde (valore 0).

poi fai partire i due processi (il padre e il figlio)

all'interno del for prima di controllare se hanno trovato il valore giusto controlleranno che il semaforo sia ancora verde.

nel caso in cui uno dei due trovi il valore giusto allora porrà il semaforo a rosso in modo tale che neanche l'altro processo possa continuare.

[Hybr1d97]

immaginalo come se avesse un valore binario ovvero 0 o 1 il processo quando incontra questo semaforo controlla se può accedere all'area oppure viene bloccato.

all'inizio del programma crei il semaforo e lo imposti a verde (valore 0).

poi fai partire i due processi (il padre e il figlio)

all'interno del for prima di controllare se hanno trovato il valore giusto controlleranno che il semaforo sia ancora verde.

nel caso in cui uno dei due trovi il valore giusto allora porrà il semaforo a rosso in modo tale che neanche l'altro processo possa continuare.
Sì la logica l'avevo intuita, grazie comunque per il chiarimento ed i link!

[Hybr1d97]

Una domanda che non c'entra con il caso della ricerca ma che ha comunque a che vedere con la fork: mettiamo che siamo nel processo figlio, se da esso generiamo un altro processo figlio non dovremmo avere errore? Mi spiego:

int main(int argc, char *argv[]) {
//Processo iniziale
int r, s;
r = fork();
. . .
if (r == 0){ //Processo figlio
r = fork();
if(r>0) //???
. . .
}

return 0;
}

Se noi sappiamo di trovarci nel processo figlio è perchè la fork in questo caso ha restituito 0. Quindi, in sostanza, il figlio fa la prima fork perchè il codice è condiviso, la sua r assume valore 0 e quindi sappiamo che siamo nel figlio. Ma se il figlio rifà la fork, la r non dovrebbe riassumere valore 0 (e quindi impedire la creazione di un figlio di un altro figlio)?

[kwb]

Siccome sono anni che ho dato questo esame, non ricordo più bene.
Però secondo me il tuo errore sta nel fatto che utilizzi sempre la variabile r mentre io personalmente se volessi salvare il PID del figlio, utilizzerei una seconda variabile.

Come vedi nell'esempio che ti ho messo, io scrivo semplicemente:

if(fork()==0)

E non salvo il valore di ritorno ( perchè non mi serve ).
La funziona fork(), come sai, ritorna un numero maggiore di zero se ti trovi nel padre, ma ricorda che un padre può essere un figlio di un altro padre ( come in questo caso ).

[Hybr1d97]

Ma non credo nemmeno che sia un errore, il codice che ho messo è una sintesi di quello che sta sul libro, ed usa sempre r. Quello che io non ho capito è: se ci troviamo nel figlio A, perchè prima la fork ritorna 0 (senza creare nulla) e dopo, quando la reinvochiamo, crea il figlio di A (chiamiamolo B) e restituisce il pid di B ad A? Mi sembra di aver capito che alla prima chiamata la fork interpreta A come processo figlio, restituendogli 0, mentre alla seconda lo interpreta come padre, crea il figlio e gli restituisce >0.

[kwb]

Perchè non sai se una volta chiama la fork() il nuovo processo prenderà controllo della CPU o meno.
Il problema di fondo dei processi è che non hai il controllo su quale parte di codice viene eseguita dopo una fork: non sai se fatta la fork venga dato il controllo della cpu al processo nuovo o se invece l'esecuzione sia tenuta sempre da quello vecchio.

Questa parte:

r = fork();
if(r>0)

Significa: se r > 0 vuol dire che ci troviamo dentro il padre (A) del figlio che abbiamo creato (B).
La fork() a meno che non ritorni -1 funziona sempre. Il problema è che ti devi salvare il valore di ritorno se vuoi capire dove ti trovi ( in quale processo ).

Inoltre, ma questo è tutto da verificare perchè non mi ricordo, la variabile r è presente sia nel figlio che nel padre: quindi fatto il secondo fork() è come se avessi 3 variabili r, infatti:
(1) r > 0 -> Processo padre del programma
(2) r = 0 prima del secondo fork() e r > 0 dopo il secondo fork() -> Processo figlio (A)
(3) r = 0 -> Processo figlio (B)

[dyablo96]

non è sbagliato fare più fork uno all'interno dell'altro, immaginatelo come una scala gearchica

processo padre A -> processo figlio B

processo padre B -> processo figlio C

B sarà sempre figlio di A ma allo stesso tempo padre di C.

poi sta a te gestirli in modo tale che B prima di chiudersi attenda suo figlio e la stessa cosa per A che deve attendere la terminazione di B.

immagina di dover risolvere questa espresione: 5*(2+(4-1))

ora il processo padre cioè A avrà tutta l'espresione ma per facilitargli il lavoro andiamo a fare un fork che crea il processo B ora B l'avorerà solo sulla prima sottoespressione cioè 2+(4-1).
a sua volta B troverà una sottoespressione e crea il figlio C per risolverlà.
C lavorerà sull'ultima sottoespressione cioè 4-1
C troverà il primo risultato cioè 3 e termina lasciando però il valore a B
B sostituisce il valore nella sua espressione, 2+3, la risolve, il risultato è 5, passa il risultato in modo tale che A possa leggerlo e termina.
A sostituisce il valore e si ritrova con un'espressione molto semplice che è 5*5.
il risultato dell'espressione è 25

[Hybr1d97]

La clonazione in sè l'avevo capita, era il funzionamento della fork ad essermi un po' oscuro :D Comunque mi sembra di aver capito che è meglio evitare cose tipo A padre di B padre di C padre di D, ma preferire piuttosto A padre di B, C e D.

[kwb]

La clonazione in sè l'avevo capita, era il funzionamento della fork ad essermi un po' oscuro :D Comunque mi sembra di aver capito che è meglio evitare cose tipo A padre di B padre di C padre di D, ma preferire piuttosto A padre di B, C e D.
Ma no. Se lo vuoi fare lo puoi fare. Quello che diventa difficile da seguire ( almeno per me ) è lo sdoppiamento del codice e delle variabili.

[Hybr1d97]

Quello che diventa difficile da seguire ( almeno per me ) è lo sdoppiamento del codice e delle variabili.
Cosa che in Windows non avviene, solo che poi si entra nella programmazione concorrente ed è un po' più difficile da gestire.

[dyablo96]

Cosa che in Windows non avviene

non credo che faccia differenza il sistema operativo che usi, i linguaggi come il c, java ecc. ecc. hanno standard per fare in modo che non ci siano differenze

[Hybr1d97]

non credo che faccia differenza il sistema operativo che usi, i linguaggi come il c, java ecc. ecc. hanno standard per fare in modo che non ci siano differenze
Beh sì, ma nativamente Windows usa i thread, che condividono tutto il codice, a differenza di Linux che all'inizio non li supportava pienamente (ma ora ci sono le NPTL che lo fanno).

[kwb]

Beh sì, ma nativamente Windows usa i thread, che condividono tutto il codice, a differenza di Linux che all'inizio non li supportava pienamente (ma ora ci sono le NPTL che lo fanno).

non credo che faccia differenza il sistema operativo che usi, i linguaggi come il c, java ecc. ecc. hanno standard per fare in modo che non ci siano differenze
Ha ragione hybrid. Le librerie per i thread e i processi non fanno parte dell'ansi C perché vengono gestite in maniera diversa..
Con altri linguaggi non c'è problema ma con c sono sicuro che ci sono dei problemi.

@hybrid: io ho fatto sistemi operativi prendendo come case-study Linux.
Tu stai studiando su Windows?

[Hybr1d97]

@hybrid: io ho fatto sistemi operativi prendendo come case-study Linux.
Tu stai studiando su Windows?
E' complicato da spiegare. Il libro che abbiamo usato quest'anno non siamo riusciti a finirlo, così ciò che non abbiamo fatto me lo sto studiando in questi giorni. Il capitolo in questione tratta di processi e thread in Windows e Linux, spiegando come funziona sia per Linux (usando la clonazione) sia per Windows (usando i Thread), ma non scendendo molto del dettaglio. Essendo un libro di terzo, introduce dei concetti che poi saranno affrontati più dettagliatamente nel libro di quarto (infatti ha parlato di IPC e programmazione concorrente che poi saranno discussi nell'altro volume). Mi piace l'approccio di questo libro, nel senso che per ogni cosa mostra le differenze che ci sono tra Windows e Linux. Dopo c'è un capitolo di 25 pagine sulla gestione dell'I/O seriale, non vedo l'ora :D

(Preciso che non faccio l'università (ho 17 anni), parlo dell'itis!)

[kwb]

Capisco. Lo studio che ho fatto io è stato molto incentrato su Linux. Nel caso avessi dubbi su Windows mi sa che non posso aiutarti perché non conosco.

[Hybr1d97]

Capisco. Lo studio che ho fatto io è stato molto incentrato su Linux. Nel caso avessi dubbi su Windows mi sa che non posso aiutarti perché non conosco.
Tranquillo, non fa nulla. Del resto, quando si fa sul serio, è meglio concentrarsi su un solo sistema e conoscerlo come le proprie tasche, piuttosto che studiarne tanti per poi conoscerli solo approssimativamente.

[kwb]

Quello che ti posso dire per esperienza è: il codice che leggi, provalo. Reimplementalo, modificalo. Specialmente su questo argomento il codice non funziona come credi di aver capito, è quindi buona cosa provare, capire dove sta l'errore, correggere e apprendere.

[Hybr1d97]

Infatti l'informatica è una delle migliori dimostrazioni che "sbagliando s'impara". Insomma, ci vuole tanta pazienza ed esperienza. Ma ti dà delle soddisfazioni uniche :D

[dyablo96]

io invece sto andando in quinta all'itis e queste cose le ho fatte questanno ma abbiamo lavorato principalmente su linux e non credevo cambiasse su windows :D

comunque ti consiglio di provare vari eserci magari prima lo fai con i fork e poi provi la stessa cosa coi thread e i semafori.

io ho lavorato principalmente con i fork in c mentre ho sviluppato molto in java utilizzando i thread e i semafori.