|
|
Ten dokument jest dost�pny w nast�puj�cych j�zykach: English Castellano Deutsch Francais Italiano Nederlands Russian Turkce Polish |
Leonardo Giordani <leo.giordani(at)libero.it> O Autorze: Student in�ynierii telekomunikacji na politechnice w Milan, pracuje jako administrator sieciowy i interesuje si� programownaiem
(g��wnie Asembler i C/C++).
Od 1999 pracuje prawie wy��cznie pod systemem Linux/Unix.
|
Notka:
Ta seria artyku��w ma na celu wprowadzenie czytelnika w zagadnienia programownaia wsp�bie�nego i jego implementacji na systemie Linux. Poczynaj�c od teoretycznego zarysu zagadnie� wspo�bie�nej pracy proces�w sko�czymy na napisaniu kompletnej aplikacji demonstruj�cej komunikacj� mi�dzy procesami opart� na prostym lecz skutecznym protokole komunikacji.
Mimimalne wymagania aby zrozumie� ten artyku� to:
Ta us�uga dostarczana przez system operacyjny ma fundamentalne znaczenie, jest to "kontroler" wykonywanych proces�w; dlatego wi�c, procesy s� wykonywane w odpowiednim �rodowisku. Utrata kontroli nad wykonywaniem tych proces�w powoduje powstanie nowego problemu - synchronizacji wykonywania proces�w, co mo�na podsumowa� pyaniem: jak to mo�liwe aby pozwoli� dwum niezale�nym procesom pracowa� razem?
Problem jest bardziej skomplikowany niz na to wyglada: to nie jest tylko kwestia synchronizacji w wykonywaniu proces�w, ale r�wnie� dzielenia danych zar�wno w trybie "read" jak i "read-write".
Rozwa�my teraz kilka klasycznych probem�w rownoczesnego dost�pu do danych; je�li dwa procesy czytaj� ten sam zestaw danych to oczywi�cie nie jest problem, i wtedy wykonywanie nast�puje w spos�b harmonijny. Niech teraz jeden z proces�w zmodyfikuje dane: drugi zwr�ci inne wyniki zale�nie od czasu kiedy je odczyta�, przed czy po ich modyfikacji przez pierwszy proces. Np.: mamy dwa procesy "A" i "B" i zmienna "d". Proces A zwieksza d o 1, a proces B wypisuje wartosc tej zmiennej. Zapisuj�c to w pseudo-j�zyku mo�emy t oprzedstawi� nast�puj�co:
A { d->d+1 } & B { d->wynik }
gdzie "&" oznacza wsp�bie�ne wykonywanie. Pierwsza mo�liweo�� wykonania to:(-) d = 5 (A) d = 6 (B) wynik = 6
ale je�li proces B wykona si� pierwszy otrzymamy:(-) d = 5 (B) wynik = 5 (A) d = 6
Teraz widzisz jak istotne jest odpowienie zarz�dzanie takimi sytuacjami: ryzyko nieodpowiedniego wykonania si� jest du�e i nie do zaakceptowanie. Pomy�l �e te dane reprezentuj� stan Twojego konta w banku i nigdy nie bedziesz w stanie stwierdzi� prawdziwego stanu konta.We wcze�niejszym artykule m�wili�my ju� o pierwszym rodzaju synchronizacji poprzez u�ycie funkcji waitpid(2), kt�ra pozwala procesowi czeka� na zako�czenie innego procesu zanim wykona si� dalej. W rzeczywisto�ci pozwala to nam rozwi�za� niekt�re z konflikt�w powsta�ych podczas odczytu i zapisu danych: jak tylko dane, na kt�rych pracowa� proces P1, zostana zapisane proces P2, kt�ry ma pracowa� na tych samych danych powinien zaczeka� na zako�czenie procesu P1 zanim zacznie si� wykonywa�.
Mowi�c ja�niej ta metoda reprezentuje pierwsze rozwi�zanie, ale jest daleka od idea�u, poniewa� P2 musi czeka� bezczynnie przez okres czasu, kt�ry mo�e by� bardzo d�ugi, czelaj�c a� P1 zako�czy dzia�anie, nawet je�li nie musi dzia��� na wsp�lnych danych. Dlatego musimy zwi�kszy� nasz� kontrol� nad dzia�aniem proces�w np.: ustali� zasady rz�dz�ce dost�pem do konkretnych danych. Rozwi�zaniem tego problemu jest zestaw podstawowych funkcji standardowej biblioteki znanej jako SysV IPC (System V InterProcess Communication).
key_t ftok(const char *pathname, int proj_id);
kt�ra u�ywa nazwy istniej�cego pliku (pathname) i liczby integer. Nie zapewnia nam to ze klucz jest niepowtarzalny, poniewa� parametry wzi�te z pliku(numer i-node i numer urz�dzenia) mog� wytworzy� identyczne kombinacje. Dobrym rozwi�zaniem jest stworzenie ma�ej biblioteki, kt�ra �ledzi zaznaczone klucze i unika duplikat�w.Semafory mog� by� u�yte do kontrolowania dost�pu do danych: warto�� semafora reprezentuje ilo�� proces�w jakie mog� dzia�a� jednocze�nie na danym zasobie; Za ka�dym razem jak proces korzysta z zasoby warto�� semafora powinna byc dekrementowana i inkrementowana po zowlnieniu zasobu przez proces. Je�li dost�p do zasobu jest wy��czny (np.: tylko jeden proces w danej chwili mo�e z niego korzysta�) warto�� pocz�tkowa semafora b�dzie r�wna 1.
Semafor mo�e spe�nia� r�wnie� inn� rol� - licznik zasob�w: warto�� jak� przedstawia w tym przypadku to ilo�� zasob�w dost�pnych (np.: ilo�� wolnych kom�rek pami�ci).
Rozwa�my rzeczywisty przypadek, w kt�rym semafory b�d� u�yte: mamy bufor, w kt�rym kilka proces�w S1,...,Sn mo�e zapisywa� ale tylko jeden proces L mo�e czyta�; cowi�cej, operacje nie mog� by� wykonywane w tym samym czasie (np.: tylko jeden proces mo�e w danym czasie operowa� na buforze). Oczywi�cie S proces�w mo�e zawsze pisa� poza przypadkiem gdy bufor jest pe�ny, a proces L mo�e czyta� tylko wtedy gdy bufor nie jest pusty. Dlatego potrzebujemy trzy semafory: pierwszy zarz�dzaj�cy dost�pem do zasob�w, drugi i trzeci b�dz� �ledzi� ile element�w znajduje si� w buforze (po�niej si� przekonamy dlaczego dwa semafory nie wystarcz�).
Bior�c pod uwag� ze dost�p do danych jest wy��czny pierwszy semafor b�dzie binarny (jego warto�� b�dzie r�wna 0 lub 1). Drugi i trzeci przyjm� warto�ci zale�ne od rozmiaru bufora.
Teraz zobaczymy jak semafory s� zaimplementowane w C z u�yciem SysV. Funkcja tworz�ca semafor to semget(2)
int semget(key_t key, int nsems, int semflg);
gdzie key to klucz IPC, nsems to ilo�� semafor�w jak� chcemy stworzy�, a semflg to kontrola dost�pu zaimplementowana na 12 bitach, pierwsze 3 s� zale�ne od metody tworzenia, a kolejne 9 prawa zapisu i odczytu dla u�ytkownika, grupy i innych (zauwa� podobie�stwo do systemu plik�w w Unix'ie). Szczeg�owy opis znajduje si� w manualu do ipc(5). Jak mog�e� ju� zauwa�y� SysV zarz�dza zestawem semafor�w zamiast pojedy�czym semaforem, co pozwala uzyska� bardziej zwarty kod.Stw�rzmy nasz pierwszy semafor
#include <stdio.h> #include <stdlib.h> #include <linux/types.h> #include <linux/ipc.h> #include <linux/sem.h> int main(void) { key_t key; int semid; key = ftok("/etc/fstab", getpid()); /* tworzy zestaw semafor�w z�o�ony tylko z jednego semafora */ semid = semget(key, 1, 0666 | IPC_CREAT); return 0; }Id�c dalej musimy si� nauczy� jak zarz�dza� semaforami i je usuwa�; zarz�dzanie semaforem jest uzyskiwane poprzez funkcj� semctl(2)
int semctl(int semid, int semnum, int cmd, ...)
,kt�ra dzia�a odpowiednio do akcji zidentyfikowanej przez cmd na zestawie semid i (je�li wymaga tego akcja) na pojedy�czym semaforze semnum. Wprowadzimy pewne opcje wraz z tym jak b�dziemy ich potrzebowa�, ale kompletna ich lista jest zawarta w manualu. Zale�nie od akcji cmd mo�e nast�pi� potrzeba podania dodatkowych argument�w dla funkcji, kt�rej typ tounion semun { int val; /* warto�� dla SETVAL */ struct semid_ds *buf; /* bufor dla IPC_STAT, IPC_SET */ unsigned short *array; /* tablica dla GETALL, SETALL */ /* cz�� zale�na od linuxa: */ struct seminfo *__buf; /* bufor dla IPC_INFO */ };Aby ustawi� warto�� semafora dyrektywa SETVAL powinna by� u�yta, a warto�� podana w unii semun; zmodyfikujmy poprzedni program ustawiaj�c warto�� semafora na 1
[...] /* tworzy zestaw semafor�w z�o�ony tylko z jednego semafora */ semid = semget(key, 1, 0666 | IPC_CREAT); /* ustawia warto�� semafora 0 na 1 */ arg.val = 1; semctl(semid, 0, SETVAL, arg); [...]Dalej musimy zwolni� seamfor dealokuj�c struktur� u�yt� do jego zarz�dzania; to zadanie zostanie wykonane przez dyrektyw� IPC_RMID dla semctl. Ta dyrektywa usuwa seamfor i wysy�a wiadomo�� do wszystkich proces�w czekaj�cych na uzyskanie dost�pu do zasobu. Ostatnia modyfikacja programu to
[...] /* ustawienie warto�ci semafora o numerze 0 na 1 */ arg.val = 1; semctl(semid, 0, SETVAL, arg); /* dealokacja semafora */ semctl(semid, 0, IPC_RMID); [...]Jak wida� tworzenie i zarz�dzanie struktur� do kontrolowania wspo�bie�nego wykonywania si� kodu nie jest trudne; kiedy wprowadzimy obs�ug� b��d�w stanie si� to nieco bardziej skomplikowane, ale tylko z punku widzenia z�o�ono�ci kodu.
Semafor mo�e teraz by� u�ywany przez funkcj� semop(2)
int semop(int semid, struct sembuf *sops, unsigned nsops);
gdzie semid to identyfikator zestawu, sops to tablica array zawieraj�ca operacje do wykonania i nsops to ilo�� tych operacji. Ka�da operacja jest reprezentowana przez struktur� sembuf.unsigned short sem_num; short sem_op; short sem_flg;
np.: przez nr semafora w zestawie (sem_num), operacje (sem_op) i flag� okre�laj�c� oczekiwanie; narazie niech sem_flg b�dzie r�wne 0. Operacje jakie mo�emy poda� s� dodtnimi numerami przydzielanymi wg nastepuj�cych zasad:Odczyt i Zapis to tylko wirtualne dzia�ania: dzieje si� tak dlatego, �e jak mowili�my w poprzednim artykule, ka�dy proces ma w�asn� przestrze� w pami�ci i nie mo�e uzyska� dost�pu do przestrzeni innego procesu. To powoduje niemo�liwe odpowiednie zarz�dzanie 5 proces�w, poniewa� ka�dy dziala na wlasniej kopii bufora. Zmieni si� to gdy zaczniemy m�wi� o pami�ci dzielonej ale narazie uczmy si� krok po kroku.
Dlaczego potrzebujemy 3 semafor�w? Pierwszy (numer 0) dzia�a jako stra�nik dost�pu do bufora i jego maksymalna warto�� to 1. Drugi i trzeci kontroluj� warunek niedope�nienia i przepe�nienia bufora. Pojedy�czy semafor nie mo�e obs�u�y� tych dw�ch sytuacji poniewa� semop dzia�a tylko w jedn� stron�.
Rozja�nijmy troch� sytuacj� z semaforem (zwanym O), kt�rego warto�� reprezentuje ilo�� wolnych kom�rek w buforze. Za ka�dym razem gdy S proces�w wrzuca co� do bufora warto�� semafora zmniejsza si� o 1 a� wreszcie osi�gnie warto�� 0. Np.: bufor jest pe�ny. Ten semafor nie mo�e obs�ugiwa� sytuacji niedope�nienia bufora: proces R mo�e w rzeczywisto�ci zwi�ksza� jego warto�� bez ko�ca. Potrzebujemy tego specjalnego semafora (zwanego U), kt�rego warto�� reprezentuje ilo�� element�w w buforze. Za ka�dym razem gdy proces W wrzuca element do bufora jednocze�nie zwi�ksza warto�� semafora U i zmniejsza warto�� semafora O. W przeciwie�stwie, proces R zmniejszy warto�� semafora U i zwi�kszy semafora O.
Przepe�nienie nast�puje wtedy gdy nie mo�emy zmniejszy� warto�ci semafora O, a niedope�nienie nast�puje gdy niemo�emy zmniejszy� warto�ci semafora U.
#include <stdio.h> #include <stdlib.h> #include <errno.h> #include <linux/types.h> #include <linux/ipc.h> #include <linux/sem.h> int main(int argc, char *argv[]) { /* IPC */ pid_t pid; key_t key; int semid; union semun arg; struct sembuf lock_res = {0, -1, 0}; struct sembuf rel_res = {0, 1, 0}; struct sembuf push[2] = {1, -1, IPC_NOWAIT, 2, 1, IPC_NOWAIT}; struct sembuf pop[2] = {1, 1, IPC_NOWAIT, 2, -1, IPC_NOWAIT}; /* Other */ int i; if(argc < 2){ printf("U�ycie: bufdemo [rozmiar]\n"); exit(0); } /* Semafory */ key = ftok("/etc/fstab", getpid()); /* Tworzy zestaw semafor�w z�o�ony z 3 semafor�w */ semid = semget(key, 3, 0666 | IPC_CREAT); /* Inicjacja semafora #0 na 1 - kontrola zasob�w */ arg.val = 1; semctl(semid, 0, SETVAL, arg); /* Inicjacja semafora #1 na buf_length - kontrola przepe�nienia */ /* Sem value is 'free space in buffer' */ arg.val = atol(argv[1]); semctl(semid, 1, SETVAL, arg); /* Inicjacja semafora #2 na buf_length - kontrola niedope�nienia */ /* Sem value is 'elements in buffer' */ arg.val = 0; semctl(semid, 2, SETVAL, arg); /* Fork */ for (i = 0; i < 5; i++){ pid = fork(); if (!pid){ for (i = 0; i < 20; i++){ sleep(rand()%6); /* Pr�ba zaj�cia zasobu - sem #0 */ if (semop(semid, &lock_res, 1) == -1){ perror("semop:lock_res"); } /* Zab�okowanie wolnej przestrzeni - sem #1 / wrzucenie elementu - sem #2*/ if (semop(semid, &push, 2) != -1){ printf("---> Process:%d\n", getpid()); } else{ printf("---> Process:%d BUFFER FULL\n", getpid()); } /* Zwolnij zas�b */ semop(semid, &rel_res, 1); } exit(0); } } for (i = 0;i < 100; i++){ sleep(rand()%3); /*Spr�buj zablokowa� zas�b - sem #0 */ if (semop(semid, &lock_res, 1) == -1){ perror("semop:lock_res"); } /* Odblokuj woln� przestrze� - sem #1 / pobierz element - sem #2 */ if (semop(semid, &pop, 2) != -1){ printf("<--- Process:%d\n", getpid()); } else printf("<--- Process:%d BUFFER EMPTY\n", getpid()); /* Zwolnij zas�b */ semop(semid, &rel_res, 1); } /* Kasuj semafory */ semctl(semid, 0, IPC_RMID); return 0; }Skomentujmy najbardziej interesuj�ce partie kodu:
struct sembuf lock_res = {0, -1, 0}; struct sembuf rel_res = {0, 1, 0}; struct sembuf push[2] = {1, -1, IPC_NOWAIT, 2, 1, IPC_NOWAIT}; struct sembuf pop[2] = {1, 1, IPC_NOWAIT, 2, -1, IPC_NOWAIT};Te 4 linie to akcje jakie mo�emy wykona� na zestawie semafor�w: pierwsze dwie to pojedy�cze akcje, a kolejne s� podw�jne. Pierwsza akcja, lock_res, pr�buje zabokowa� zas�b: zmniejsza warto�� pierwszego semafora (numer 0) o 1 (je�li jego warto�� nie jest r�wna zero) i dzia�anie proces�w je�li zas�b jest zaj�ty jest �adne (np.: the procesy czekaj�). Akcja rel_res jest identyczna lock_res ale zas�b jest zwalniany (warto�� jest dodatnia).
Akcje pobierz i po�� s� akcjami bitowymi. S� to tablice dw�ch akcji, pierwsza na semaforze 1 i druga na semaforze 2; gdy pierwszy si� zwi�ksza drugi maleje i na odwr�t, ale procesy ju� nie oczekuj�: IPC_NOWAIT zmusza proces do kontynuowania wykonywania je�li zas�b jest zaj�ty.
/* Inicjacja semafora #0 na 1 - kontrola zasob�w */ arg.val = 1; semctl(semid, 0, SETVAL, arg); /* Inicjacja semafora #1 na buf_length - kontrola przepe�nienia */ /* warto�� Sem to 'wolna przestrze� w buforze' */ arg.val = atol(argv[1]); semctl(semid, 1, SETVAL, arg); /* Inicjacja semafora #2 na buf_length - kontrola niedope�nienia */ /* warto�� Sem to 'element w buforze' */ arg.val = 0; semctl(semid, 2, SETVAL, arg);Tutaj inicjalizujemy warto�� semafor�w: pierwszy na 1 poniewa� kontroluje wy��czny dost�p do zasob�w, drugi na d�ugo�� bufora (podan� z lini komend) i trzeci na 0, jak wcze�niej napisa�em apropo przpe�enienia i niedope�nienia.
/* Pr�ba zablokowania zasobu - sem #0 */ if (semop(semid, &lock_res, 1) == -1){ perror("semop:lock_res"); } /* Zablokuj woln� przestrze� - sem #1 / wrzy� element - sem #2*/ if (semop(semid, &push, 2) != -1){ printf("---> Process:%d\n", getpid()); } else{ printf("---> Process:%d BUFFER FULL\n", getpid()); } /* Zwolnij zas�b */ semop(semid, &rel_res, 1);Proces W pr�buje zablokowa� zas�b poprzez akcj� lock_res; kiedy ju� to zrobi wywo�ywane jest wrzucenie elementu do bufora i wypisuje na standardowym wyj�ciu (monitor): je�li operacja nie mo�e by� wykonana wypisuje ze bufor jest pe�ny po czym zwalnia zas�b.
/* Pr�ba zablokowania zasobu - sem #0 */ if (semop(semid, &lock_res, 1) == -1){ perror("semop:lock_res"); } /* Zwolnij woln� przestrze� - sem #1 / odczytaj element- sem #2 */ if (semop(semid, &pop, 2) != -1){ printf("<--- Process:%d\n", getpid()); } else printf("<--- Process:%d BUFFER EMPTY\n", getpid()); /* Zwolnij zas�b */ semop(semid, &rel_res, 1);Proces R dzia�a mniejwi�cej jak proces W: blokuje urz�dzenie, pobiera element i zwalnia je.
W nast�pnym artykule om�wi� kolejki komunikat�w, inn� struktur� InterProcess Communication i synchroznizacj�. Jak zwykle je�li napiszecie co� prostego z wykorzystaniem tego czego si� dowiedzieli�cie z teog artyku�u wy�lijcie to do mnie wraz z imieniem i adresem email. B�d� szcz�sliwy mog�c to przeczyta�. Powodzenia!
|
Strona prowadzona przez redakcj� LinuxFocus
© Leonardo Giordani, FDL LinuxFocus.org |
t�umaczenie:
|
2002-12-23, generated by lfparser version 2.33