Strona Główna  |  Mapa Serwisu  |  Indeks  |  Szukaj

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ść: Introduction klucze SysV Semafory Warto przeczytać Dyskusja dotycząca tego artykułu

Programowanie współbieżne - komunikacja między procesami

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:

• Podstawowa znajaomość powłoki
• Podstawowa znajomość programowania w języku C (składnia, pętle, biblioteki)

Introduction

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 }

(-) d = 5 (A) d = 6 (B) wynik = 6

(-) d = 5 (B) wynik = 5 (A) d = 6

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

key_t ftok(const char *pathname, int proj_id);

Semafory

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

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;
}

int semctl(int semid, int semnum, int cmd, ...)

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 */
};

[...]

  /* 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);

[...]

[...]

  /* ustawienie wartości semafora o numerze 0 na 1 */
  arg.val = 1;
  semctl(semid, 0, SETVAL, arg);

  /* dealokacja semafora */
  semctl(semid, 0, IPC_RMID);

[...]

Semafor może teraz być używany przez funkcję semop(2)

int semop(int semid, struct sembuf *sops, unsigned nsops);

unsigned short sem_num; short sem_op; short sem_flg;

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.

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;
}

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};

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

/* 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);

/* 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);

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ć

• Silberschatz, Galvin, Gagne, Operating System Concepts - Sixth Edition, Wiley&Sons, 2001
• Tanenbaum, WoodHull, Operating Systems: Design and Implementation - Second Edition, Prentice Hall, 2000
• Stallings, Operating Systems - Fourth Edition, Prentice Hall, 2002
• Bovet, Cesati, Understanding the Linux Kernel, O'Reilly, 2000
• The Linux Programmer's Guide: http://www.tldp.org/LDP/lpg/index.html
• Linux Kernel 2.4 Internals http://www.tldp.org/LDP/lki/lki-5.html

Dyskusja dotycząca tego artykułu

2002-12-23, generated by lfparser version 2.33