[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]

Originariamente inviato da Hybr1d97

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!

[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]

Originariamente inviato da dyablo96

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(), read() e write().

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]

Originariamente inviato da 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(), read() e write().

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

[dyablo96]

oltre all'esempio molto utile di kwb ti lascio un link in cui spiegano come utilizzare i thread e i semafori clicca qui.

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]

Originariamente inviato da dyablo96

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 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]

Originariamente inviato da Hybr1d97

La clonazione in sè l'avevo capita, era il funzionamento della fork ad essermi un po' oscuro 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.