Evenwijdig programmeren - communicatie tussen processen

ArticleCategory:

AuthorImage:

TranslationInfo:

original in it: Leonardo Giordani

it to en: Leonardo Giordani

en to nl: Guus Snijders

AboutTheAuthor:

Is student aan de faculteit van Telecommunicatie Engineering in Politnecnico in Milaan, werkt als netwerkbeheerder en is geïnteresseerd in programmeren (voornamelijk Assembly en C/C++).

Abstract:

Deze serie van artikelen heeft tot doel om de lezer te informeren over het concept van multitasking en de implementatie ervan in Linux. Te beginnen bij de theoretische concepten over de basis van multitasken, zullen we eindigen met het schrijven van een complete applicatie om de communicatie tussen processen te demonstreren, met behulp van een eenvoudig maar efficiënt communicatie protocol.

Vereisten voor het begrijpen van het artikel zijn:

• Enige kennis van de shell
• Basis kennis van C (syntax, loops, bibliotheken)

ArticleIllustration:

ArticleBody:

Introductie

Daar zijn we weer, worstelend met Linux multitasking. Zoals we zagen in het voorgaande artikel, zijn voor het forken van de uitvoering van een programma, een paar regels code voldoende, omdat het besturingssyteem de zorgt voor de initialisatie, beheer en timing van de processen die we creëeren.

Deze service, geleverd door het besturingssysteem is fundamenteel, het is 'de supervisie van proces' uitvoering; processen worden dus uitgevoerd in een toegewijde omgeving. Verlies van de controle over een proces levert de programmeur een synchronisatie probleem op, samengevat in de vraag: hoe is het mogelijk om twee onafhankelijke processen samen te laten werken?

Het probleem is complexer dan het lijkt: het is niet alleen een vraag over synchronisatie van de uitvoering van de processen, maar ook over het delen van data, zowel in lees- als in schrijfmodus.

Laten we het eens hebben over het klassieke probleem van concurrente toegang tot data: als twee processen dezelfde dataset lezen, is dit uiteraard geen probleem, en de uitvoering is CONSISTENT. Laat een van de twee processen de dataset aanpassen: de andere zal verschillende resultaten opleveren, afhankelijk van de tijd waarop de dataset wordt gelezen, voor of na het schrijven door het eerste proces. Voorbeeld: we hebben twee processen, "A" en "B", en een integer "d". Proces A verhoogt d met 1, proces B print deze. Geschreven in een meta taal kunnen we het zo weergeven

A { d->d+1 } & B { d->output }

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

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

In het voorgaande artikel hebben we reeds gesproken over een eerste vorm van synchronisatie door het gebruik van de waitpid(2) functie, welke een proces laat wachten op het stoppen van een andere, alvorens door te gaan. In feite staat dit ons toe om sommige van de conflicten met betrekking tot het lezen en schrijven van data op te lossen: als de dataset van proces P1 is gedefiniëerd, zal een proces P2, welke met dezelfde dataset werkt of een subset ervan, wachten op het stoppen van P1 alvorens door te gaan met zijn eigen uitvoering.

Het is duidelijk dat deze methode een eerste oplossing biedt, deze is echter nog ver van de beste, daar proces P2 idle dient te blijven, gedurende een periode die erg lang kan zijn, wachtend totdat P1 zijn uitvoering stopt, zelfs als deze geen bewerking meer uitvoert op de data. We moeten onze controle dus verfijnen, oftewel de de toegang tot enkele data of dataset regelen. De oplossing voor dit probleem ligt in een set primitieven van de standaard bibliotheek, bekend onder de naam SysV IPC (System V InterProcess Communicatie, de System V manier van communicatie tussen processen).

SysV keys

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

Semaforen

Semaforen kunnen gebruikt worden om de toegang tot bronnen te regelen: de waarde van de semafoor representeerd het aantal processen dat de bron kunnen benaderen; telkens als een proces de bron benaderd zal de waarde van de semafoor afnemen en weer toenemen als de bron wordt losgelaten. Als de bron exclusief is (als slechts een proces toegang kan krijgen) zal de initiële waarde van de semafoor 1 zijn.

Een andere taak kan ook volbracht worden door de semafoor, de bronteller: de waarde representeerd, in dit geval, de hoeveelheid beschikbare bronnen (bijvoorbeeld het aantal vrije geheugen cellen).

Laten we een praktisch voorbeeld nemen, waarbij de semafoor types gebruikt zullen worden: stel dat we een buffer hebben, waarin verchillende S1,...,Sn kunnen schrijven, maar welke alleen een proces L kan lezen; verdere operaties kunnen niet worden gelijktijdig worden uitgevoerd (oftewel, op ieder moment kan slechts een proces bewerkingen uitvoeren op de buffer). Vanzelfsprekend kunnen S processen altijd schrijven, tenzij de buffer vol is, terwijl alleen proces L kan lezen als de buffer niet leeg is. Dus hebben we 3 semaforen nodig: de eerste houdt de toegang tot de buffer bij, de tweede en derde houden bij hoeveel elementen zich in de buffer bevinden (we zullen later zien waarom twee semaforen niet voldoen).

Houd in gedachten dat daar de toegang tot de buffer exclusief is, de eerste semafoor een binaire zal zijn (waarde 1 of 0), terwijl de tweede en derde waardes zullen aannemen die gerelateerd zijn aan de dimensie van de buffer.

Laten we eens kijken hoe semaforen zijn geïmplenteerd in C met gebruik van SysV primitieven. De functie om een semafoor te creëeren is semget(2);

int semget(key_t key, int nsems, int semflg);

Laten we onze eerste semafoor creëeren

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

  /* create a semaphore set with only 1 semaphore: */
  semid = semget(key, 1, 0666 | IPC_CREAT);

  return 0;
}

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

union semun {
 int val;                  /* value for SETVAL */
 struct semid_ds *buf;     /* buffer for IPC_STAT, IPC_SET */
 unsigned short *array;    /* array for GETALL, SETALL */
                           /* Linux specific part: */
 struct seminfo *__buf;    /* buffer for IPC_INFO */
};

[...]

  /* create a semaphore set with only 1 semaphore */
  semid = semget(key, 1, 0666 | IPC_CREAT);

  /* set value of semaphore number 0 to 1 */
  arg.val = 1;
  semctl(semid, 0, SETVAL, arg);

[...]

[...]

  /* set value of semaphore number 0 to 1 */
  arg.val = 1;
  semctl(semid, 0, SETVAL, arg);

  /* deallocate semaphore */
  semctl(semid, 0, IPC_RMID);

[...]

De semafoor kan nu gebruikt worden door de functie 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
   Als de absolute waarde van de semafoor groter of gelijk aan die van sem_op is, gaat de operatie en sem_op wordt toegevoegd aan de waarde van de semafoor (eigenlijk is het een afgetrokken, negatief nummer). Als de absolute waarde van sem_op groter is dan de waarde van de semafoor, valt het proces in een slaap staat tot het aantal bronnen beschikbaar is.
2. sem_op = 0
   Het proces slaapt tot de waarde van de semafoor 0 bereikt.
3. sem_op > 0
   De waarde van sem_op wordt toegevoegd aan de waarde van de semafoor, de vorig gebruikte bronnen loslatend.

Lezen en schrijven van de buffer zijn slechts virtueel: dit gebeurt omdat, zoals gezien in het vorige artikel, ieder proces zijn eigen geheugen ruimte heeft en niet dat van een ander proces kan benaderen. Dit maakt correct beheer van de buffer met 5 processen onmogelijk, omdat ieder zijn eigen kopie van de buffer ziet. Dit zal veranderen als we het over gedeeld geheugen (shared memory) hebben, maar laten we de dingen stap voor stap leren.

Waarom hebben we 3 semaforen nodig? De eerste (nummer 0) gedraagt zich als een buffer toegangs slot (lock) en heeft een maximale waarde van 1, terwijl de andere 2 de overflow (vollopen) en underflow (leegraken) condities beheren, omdat semop een kant op functioneerd.

Laten we dit toelichten met een semafoor (genaamd 0), waarvan de waarde het aantal lege ruimtes in de buffer weergeeft. Ieder keer als een S proces iets in de buffer plaatst, neemt de waarde van de semafoor met 1 af, totdat de waarde 0 bedraagt, of te wel, totdat de buffer vol is. Deze semafoor kan geen underflow conditie aan: het R proces kan zijn waarde verhogen zonder limiet. We hebben dus een speciale semafoor (genaamd U) nodig, waarvan de waarde het aantal elementen in de buffer weergeeft. Iedere keer dat een W proces een een element in de buffer plaatst, zal de waarde van de semafoor U afnemen en de waarde van de O semafoor toenemen.

De overflow conditie wordt dus geïdentificeerd door de onmogelijkheid van het verlagen van een O semafoor en de underflow conditie door de onmogelijkheid van het verlagen van de U semafoor.

#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("Usage: bufdemo [dimensione]\n");
    exit(0);
  }
  
  /* Semaphores */
  key = ftok("/etc/fstab", getpid());

  /* Create a semaphore set with 3 semaphore */
  semid = semget(key, 3, 0666 | IPC_CREAT);

  /* Initialize semaphore #0 to 1 - Resource controller */
  arg.val = 1;
  semctl(semid, 0, SETVAL, arg);

  /* Initialize semaphore #1 to buf_length - Overflow controller */
  /* Sem value is 'free space in buffer' */
  arg.val = atol(argv[1]);
  semctl(semid, 1, SETVAL, arg);

  /* Initialize semaphore #2 to buf_length - Underflow controller */
  /* 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);
	/* Try to lock resource - sem #0 */
	if (semop(semid, &lock_res, 1) == -1){
	  perror("semop:lock_res");
	}
	/* Lock a free space - sem #1 / Put an element - sem #2*/
	if (semop(semid, &push, 2) != -1){
	  printf("---> Process:%d\n", getpid());
	}
	else{
	  printf("---> Process:%d  BUFFER FULL\n", getpid());
	}
	/* Release resource */
	semop(semid, &rel_res, 1);
      }
      exit(0);
    }
  }
  
  for (i = 0;i < 100; i++){
    sleep(rand()%3);
    /* Try to lock resource - sem #0 */
    if (semop(semid, &lock_res, 1) == -1){
      perror("semop:lock_res");
    }
    /* Unlock a free space - sem #1 / Get an element - sem #2 */
    if (semop(semid, &pop, 2) != -1){
      printf("<--- Process:%d\n", getpid());
    }
    else printf("<--- Process:%d  BUFFER EMPTY\n", getpid());
    /* Release resource */
    semop(semid, &rel_res, 1);
  }
  
  /* Destroy semaphores */
  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};

De push en pop acties zijn een beetje bijzonder. Het zijn arrays van twee acties, de eerste op semafoor nummer 1 en de tweede op semafoor nummer 2; terwijl de eerste wordt verhoogd, wordt de tweede verlaagd en viceversa, maar het beleid is niet meer om te wachten: IPC_NOWAIT forceert het proces om door te gaan met de uitvoering als de bron bezig is.

/* Initialize semaphore #0 to 1 - Resource controller */
arg.val = 1;
semctl(semid, 0, SETVAL, arg);

/* Initialize semaphore #1 to buf_length - Overflow controller */
/* Sem value is 'free space in buffer' */
arg.val = atol(argv[1]);
semctl(semid, 1, SETVAL, arg);

/* Initialize semaphore #2 to buf_length - Underflow controller */
/* Sem value is 'elements in buffer' */
arg.val = 0;
semctl(semid, 2, SETVAL, arg);

/* Try to lock resource - sem #0 */
if (semop(semid, &lock_res, 1) == -1){
  perror("semop:lock_res");
}
/* Lock a free space - sem #1 / Put an element - sem #2*/
if (semop(semid, &push, 2) != -1){
  printf("---> Process:%d\n", getpid());
}
else{
  printf("---> Process:%d  BUFFER FULL\n", getpid());
}
/* Release resource */
semop(semid, &rel_res, 1);

/* Try to lock resource - sem #0 */
if (semop(semid, &lock_res, 1) == -1){
  perror("semop:lock_res");
}
/* Unlock a free space - sem #1 / Get an element - sem #2 */
if (semop(semid, &pop, 2) != -1){
  printf("<--- Process:%d\n", getpid());
}
else printf("<--- Process:%d  BUFFER EMPTY\n", getpid());
/* Release resource */
semop(semid, &rel_res, 1);

In het volgende artikel zullen we spreken over message queues (wachtrijen voor berichten), een andere structuur voor InterProcess Commnunicatie en synchronisatie. Zoals altijd, als je iets eenvoudigs schijft naar aanleiding van je geleerd hebt van dit artikel, stuur het naar me, met je naar en e-mail adres, ik zal het graag bekijken. Goed werk!

Aanbevolen lezingen

• 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