[LinuxFocus-icon]
Strona G��wna  |  Mapa Serwisu  |  Indeks  |  Szukaj

Nowo�ci | Archiwum | Linki | O Nas
Ten dokument jest dost�pny w nast�puj�cych j�zykach: English  Castellano  Deutsch  Francais  Italiano  Nederlands  Russian  Turkce  Polish  

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

Translated to English by:
Mariusz Koz�owski <sp3fxc(at)linuxfocus.org>

Zawarto��:


 

Programowanie wsp�bie�ne - komunikacja mi�dzy procesami

[run in paralell]

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:

Powiniene� przeczyta� pierwszy artyku� z tej serii poniewa� jest on wprowadzeniem do tego artyku�u: November 2002, article 272.
_________________ _________________ _________________

 

Introduction

I oto znowu zmagamy si� z wspo�bie�no�ci� w systemie Linux. Jak ju� wcze�niej widzieli�my we wcze�niejszym artykule u�ywanie "fork" wymaga tylko kilku lini kodu, poniewa� system sam przejmuje kontrole nad inicjalizacj� i zarz�dzaniem proces�w przez nas tworzonych.

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).  

klucze SysV

Zanim zajmiemy si� rzeczami �ci�le zwi�zanymi z teori� wspo�bie�noo�ci i jej implementacj� pozw�lcie na ma�e wprowadzenie w typow� struktur� kluczy SysV IPC. Klucz IPC jest to numer u�ywany do jednoznacznej identyfikacji struktury IPC (control structure opisanej p�zniej), ale r�wnie� mo�e by� u�yty do generowania podstawowych identyfikator�w, np.: do organizacji struktur spoza IPC. Klucz mo�e by� utwo�ony przez funkcj� ftok(3)

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

Idea semaforu dla ruchu samochodowego mo�e by� u�yta bez wi�kszych modyfikacji dla kontrolowania dost�pu do danych. Semafor to specyficzna struktura zawieraj�ca warto�ci wi�ksz lub r�wne zeru, kt�ra zarz�dza kolejk� proces�w czekaj�cych na wyst�pienie odpowiednich warunk�w w semaforze. Nawet je�li wydaje si� to prste semafory s� bardzo dobrym rozwi�zaniem. Na pocz�tek pominiemy obs�ug� b��d�w: do�o�ymy to do naszego kodu gdy zaczniemy pisa� bardziej skomplikowany program.

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 to
union 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:
  1. sem_op < 0
    Je�li ca�kowita warto�� semafora jest r�wna b�dz wi�ksza od warto�ci sem_op to operacja jest wykonywana i sem_op jest dodane do warto�ci semafora (w�a�ciwie jest odejmowana ujemna warto��). Je�li ca�kowita warto�� sem_op jest mniejsza od warto�ci semafora proces jest wprowadzany w stan u�pienia az taka liczba zasob�w jest dost�pna.
  2. sem_op = 0
    Proces �pi przez czas gdy warto�� semafora wynosi 0.
  3. sem_op > 0
    Warto�� sem_op jest dodawana do warto�ci semafora, zwalniaj�c zasoby uprzednio zaj�te.
Poni�szy program pokazuje jak u�ywa� semafor�w implementuj�c poprzedni przyk�ad z buforem: stworzymy 5 proces�w zwanych W (writers) i proces R (reader). Ka�dy proces W pr�buje uzyska� dost�p do zasob�w (bufor) blokuj�c go przez semafor i, je�li bufor nie jest pe�ny, umieszcza element w nim i zwalnia zas�b. Proces R pr�buje uzyska� dost�p do zasob�w i bierze element je�li bufor nie jest pusty i odblokowuje zas�b.

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!  

Warto przeczyta�

 

Dyskusja dotycz�ca tego artyku�u

Komentarze do dyskusji:
 Strona talkback 

Strona prowadzona przez redakcj� LinuxFocus
© Leonardo Giordani, FDL
LinuxFocus.org
t�umaczenie:
it --> -- : Leonardo Giordani <leo.giordani(at)libero.it>
it --> en: Leonardo Giordani <leo.giordani(at)libero.it>
en --> pl: Mariusz Koz�owski <sp3fxc(at)linuxfocus.org>

2002-12-23, generated by lfparser version 2.33