Algorytm Petersona dla dwoch procesów

0

Witajcie,
Tutaj tworzę będę miał trzy procesy - jeden macierzysty, który tylko rodzi dwa procesy potomne, to właśnie te procesy będą współzawodniczyły o sekcję krytyczna.
Chcę prosić Was ocenę tego kodu. Czasem na konsoli widzę następujący przebieg:

jestem w sekcji krytycznej! 6041 
wyszedlem z sekcji krytycznej! 6039 
 #include <stdio.h>
#include <sys/types.h>
#include <unistd.h>

#define false 0
#define true 1

int chce1 = false, chce2 = false;
int kto_czeka = 1;

int main(){

	pid_t child_pid_1, child_pid_2;

	printf ("ID procesu głownego %d\n", (int)getpid());

	char *arg_list[] = {"ls", "/" } ;
	child_pid_1 = fork ();
	child_pid_2 = fork ();

	while (1){

			if (child_pid_1 != 0){
			while (1){
				chce1 = true;
				kto_czeka = 1;
					while (chce2 == true && kto_czeka == 1) { ;}

					{
						printf ("jestem w sekcji krytycznej! %d \n", (int) getpid());
					}
					printf ("wyszedlem z sekcji krytycznej! %d \n", (int)getpid());
					chce1 = false;
			}
				//printf ("process potomny %d\n", (int)getpid());
		}
		else if (child_pid_2 != 0){
			while (1){
				chce2 = true;
				kto_czeka = 2;
				while (chce1 == true && kto_czeka == 2) { ;}

				{
					printf ("jestem w sekcji krytycznej! %d \n", (int) getpid());				
				}
				printf ("wyszedlem z sekcji krytycznej! %d \n", (int)getpid());
				chce2 = false;
			}

			//printf ("process potomny %d\n", (int)getpid());
		}
		else{
			printf ("proces rodzica%d: \n", (int)getpid());
		}

	}

	return 0;
}

Zastanawiam się czy to na pewno oznacza błąd? Jeśli tak to jak go poprawić ?

1

Ten kod jest niestety do wyrzucenia z bardzo wielu powodów.

Przede wszystkim sugeruje zapoznać się z działaniem fork-a. W twoim kodzie są tworzone 4 procesy które nie współdzielą ze sobą żadnych danych. Krótko mówiąc każdy proces ma swój zestaw zmiennych 'chce' i 'kto_czeka':) Chyba nie o to chodziło, prawda?

To co przedstawiłeś jest pewnie jakoś tam oparte na kodzie algorytmu Petersona z wikipedii. To jest tylko kod poglądowy algorytmu! Rzeczywista implementacja wymaga ochrony współdzielonych zmiennych takich jak kto_czeka, chce1, chce2 przynajmniej przez volatile (nie mówiąc już o atomicach i innych cudach). Napisanie czegoś takiego jest z wielu powodów naprawdę trudne i zahacza o algorytmy lock-free/wait-free (przykładowa implementacja na stacku: http://stackoverflow.com/questions/11588514/a-tested-implementation-of-peterson-lock-algorithm).

Na twoim miejscu nie pchałbym się w to. Jeśli potrzebujesz sychronizacji skorzystaj z gotowych rozwiązań: muteksów, semaforów etc.

0

Faktycznie! Popełniłem błąd.
Bowiem fork działa tak, że tworzy proces potomny, z osobną pamięcią, ale przydziela pamięć tym samym zmiennym. Zaś sam proces potomny jest kontynuowany od kolejnej linii po fork-u.
Faktycznie powstaje więcej tych procesów!
Proces główny powoła do życia proces potomny.
Są dwa procesy. Następnie obydwa mają forka, a więc są cztery procesy.
Faktycznie są błędy poważne, zapomniałem o idei działania forka.

Zobacz proszę http://www.algorytm.org/wzajemne-wykluczanie/algorytm-petersona-dla-2-procesow/peterson2-c.html tutaj.
Do semaforów przejdę niebawem, teraz jednak chciałbym chociaż koncepcyjnie zrozumieć ten kod. Co tam się dzieje ? Co to za dziwne shmidy ? ? Bo sam Alg.P. rozumiem.

1

Kod znajdujący się pod http://www.algorytm.org/wzajem[...]la-2-procesow/peterson2-c.html jest błędny ponieważ dostęp do zmiennej *turn nie jest w żaden sposób chroniony.

Powtórze jeszcze raz to co napisałem w poprzednim poście. Aby algorytm Petersona zadziałał na współczesnych procesorach wymagane są dodatkowe zabiegi. W przypadku wersji dla procesów którą zamieściłeś trzeba zadbać o to żeby nie nastąpił jednoczesny zapis do turn. Jest o tym mowa np. tutaj http://wazniak.mimuw.edu.pl/index.php?title=Programowanie_wsp%C3%B3%C5%82bie%C5%BCne_i_rozproszone/PWR_%C4%86wiczenia_1 w sekcji "Przypomnijmy, że". Bez takiego zabezpieczenia program jest niepoprawny i zadziała np. 99 razy a za 100-tnym razem się zapętli. Poczytaj sobie o sequential consistency.

Co do shmget etc to służą do zarządzania pamięcią współdzieloną; http://wazniak.mimuw.edu.pl/images/7/72/Sop_11_lab.pdf

0

Ok, już rozumiem. Idealizowałem ten algorytm :)
Okazuje się, że może dojść do jednoczesnej zmiany tej samej zmiennej, bo mój procesor ma kilka rdzeni - czyli mam kilka procesorów.
W takim razie, spróbuję zamknąć sekcję krytyczną za pomocą semaforów. Jednakże najpierw chcialbym zapytać czy to jest też takie trudne ? Czy te semafory dostaję od systemu linux ? Może od jezyka C ?
A może sam muszę je pisać ? To takie wstępne pytania, ale znam ideę i budowę ich - ale może się okazać jak przy tym algorytmie :-)

0

Jednakże najpierw chcialbym zapytać czy to jest też takie trudne ? Czy te semafory dostaję od systemu linux ? Może od jezyka C ?

Semafory udostępnia linuks w nagłówku <sys/sem.h>. Czy są trudne? Na pewno łatwiejsze niż implementacja algorytmu Petersona.
Sugeruje najpierw zapoznać się z różnymi mechanizmami IPC linuksa, porobić proste przykłady (których jest mnóstwo w sieci), poczytać książki (np. książki Stevensa są b. dobre) i dopiero wrócić do Petersona.
Inaczej będziesz co chwila zadawał różne pytania tym bardziej że komunikacja międzyprocesowa/wielowątkowość to jedne z najtrudniejszych zagadnień informatyki.

1 użytkowników online, w tym zalogowanych: 0, gości: 1