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