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