LinuxFocus article number 287 http://linuxfocus.org

door Leonardo Giordani <leo.giordani(at)libero.it> Over de auteur: Hij is een student aan de faculteit voor telecommunicatieingenieurs in Politecnico van Milaan, hij werkt als netwerkbeheerder en is geïnteresseerd in programmeren (voornamelijk assembler en c/c++). Sinds 1999 werkt hij bijna uitsluitend nog met Linux/Unix. Vertaald naar het Nederlands door: Guus Snijders <ghs(at)linuxfocus.org>

Evenwijdig programmeren - Bericht wachtrijen (1) Kort: Deze serie artikelen heeft het doel om de lezer het concept van multitasking en de implementatie ervan in een Linux OS te introduceren. We beginnen met de theoretische concepten die aan de basis liggen van multitasking, en we zullen eindigen met het schrijven van een volledige toepassing om de communicatie tussen processen te demonstreren, met een simpel maar krachtig communicatieprotocol. Vereisten om dit artikel te begrijpen zijn: minimale kennis van de shell Basiskennis van de C taal (syntax, lussen, bibliotheken) Het is een goed idee om ook de andere artikelen in deze serie te lezen, welke verschenen in de laatste twee uitgaven van LinuxFocus (November2002 en January2002). _________________ _________________ _________________

Introductie

Het synchroniseren van processen betekend het klokken van hun werk, niet in een absoluut referentie systeem (het geven van een exacte tijd waarop een proces z'n werk zou moeten beginnen) maar in een relatieve, waar we kunnen opgeven welk proces het eerste zou moeten werken en welke daarna.

Als je hiervoor semaforen gebruikt, blijkt al snel dat dit erg complex en beperkt kan worden: complex omdat ieder proces een semafoor dient te beheren voor ieder ander proces waarmee het zich synchroniseert. Beperkt omdat het ons niet toestaat om parameters tussen de processen uit te wisselen. Stel je bijvoorbeeld het creëren van een nieuw proces voor: deze gebeurtenis zou bekend moeten worden gemaakt bij alle werkende processen, maar semaforen staan een proces niet toe om zulke informatie te versturen.

De controle op de toegang tot gedeelde bronnen door semaforen kan bovendien leiden tot het continue blokkeren van van een proces, als een van de andere betrokken processen een bron vrijgeeft en vervolgens weer reserveerd voordat anderen er gebruik van kunnen maken: zoals we al zagen is het in de wereld van evenwijdig programmeren niet mogelijk om van te voren te weten welk proces wanneer wordt uitgevoerd.

Deze korte notities maken ons duidelijk dat semaforen een inadequate manier zijn om complexe synchronisatie problemen op te lossen. Een elegante oplossing voor dit probleem is het gebruik van bericht rijen (message queues): in dit artikel zullen we de theory van deze interproces communicatie voorziening bestuderen en een klein programma schrijven met behulp van SysV primitieven.

De theory van Bericht Rijen

Het gebruik van rijen is dus een simpele implementatie van een mail systeem tussen processen: ieder proces heeft een adres waarmee het onderscheiden kan worden van andere processen. Het proces kan dan de berichten die in zijn box zijn afgeleverd lezen in een volgorde naar voorkeur, en aansluitend reageren op wat er werd verteld.

De synchronisatie van twee processen kan dus gebeuren door simpelweg berichten te gebruiken tussen de twee: de gedeelde bronnen zullen nog steeds semaforen bevatten om de processen hun status te laten weten, maar de timing tussen processen zal direct plaatsvinden. We kunnen onmiddelijk zien dat het gebruik van bericht wachtrijen zo het probleem sterk vereenvoudigd, waar het eerst een extreem complex probleem was.

Voordat we de bericht wachtrijen in C kunnen implementeren, moeten we het eerst hebben over een ander probleem, gerelateerd aan synchronisatie: de behoefte aan een communicatie protocol.

Een Protocol Creëren

Dit is een erg simpel voorbeeld van een protocol dat gebaseerd is op bericht uitwisseling: twee processen A en B worden gelijktijdig uitgevoerd en verwerken verschillende data; als ze klaar zijn met het verwerken van de data, moeten ze de resultaten samenvoegen. Een eenvoudig protocol om hun interactie te beheersen zou het volgende kunnen zijn

PROCES B:

• Werk met je data
• Zodra je klaar bent, stuur een bericht naar A
• Zodra A antwoord, begin met het sturen van resultaten

• Werk met je data
• wacht op een bericht van B
• Beantwoord het bericht
• Ontvang data en meng ze met de jouwe

Dit protocol is eenvoudig uit te breiden met mogelijkheid van n processen: ieder proces, behalve A, werkt met zijn eigen data en stuurt dan een bericht naar A. Als A antwoord, stuurt ieder proces zijn resultaten: de structuur van de individuele processen (behalve A) is niet gewijzigd.

System V Bericht Wachtrijen

De structuur aan de basis van het systeem om een bericht te beschrijven is genaamd msgbuf ;en wordt gedeclareerd in linux/msg.h

/* message buffer for msgsnd and msgrcv calls */
struct msgbuf {
        long mtype;         /* type of message */
        char mtext[1];      /* message text */
};

struct message {
        long mtype;         /* message type */
        long sender;        /* sender id */
        long receiver;      /* receiver id */
        struct info data;   /* message content */
        ...
};

Om een nieuwe wachtrij te creëren, moet een proces de msgget() functie aanroepen:

int msgget(key_t key, int msgflg)

IPC_CREAT | 0660

Net als in de vorige artikelen zullen we aannemen dat er geen fouten zullen optreden, zodat we de code eenvoudig kunnen houden, zelfs als we het in een toekomstig artikel zullen hebben over veilige IPC code.

Om een bericht naar een rij te sturen van welke we de identifier kennen, dienen we gebruik te maken van de msgsnd() primitieve

int msgsnd(int msqid, struct msgbuf *msgp, int msgsz, int msgflg)

length = sizeof(struct message) - sizeof(long);

Om de berichten te lezen die zich in een rij bevinden, gebruiken we de msgrcv() system call

int msgrcv(int msqid, struct msgbuf *msgp, int msgsz, long mtype, int msgflg)

Het verwijderen van een wachtrij kan gedaan worden met de msgctl() primitieve met de flag IPC_RMID

msgctl(qid, IPC_RMID, 0)

#include <stdio.h>
#include <stdlib.h>
#include <linux/ipc.h>
#include <linux/msg.h>

/* Redefines the struct msgbuf */
typedef struct mymsgbuf
{
  long mtype;
  int int_num;
  float float_num;
  char ch;
} mess_t;

int main()
{
  int qid;
  key_t msgkey;

  mess_t sent;
  mess_t received;

  int length;

  /* Initializes the seed of the pseudo-random number generator */
  srand (time (0));

  /* Length of the message */
  length = sizeof(mess_t) - sizeof(long);

  msgkey = ftok(".",'m');

  /* Creates the queue*/
  qid = msgget(msgkey, IPC_CREAT | 0660);

  printf("QID = %d\n", qid);

  /* Builds a message */
  sent.mtype = 1;
  sent.int_num = rand();
  sent.float_num = (float)(rand())/3;
  sent.ch = 'f';

  /* Sends the message */
  msgsnd(qid, &sent, length, 0);
  printf("MESSAGE SENT...\n");

  /* Receives the message */
  msgrcv(qid, &received, length, sent.mtype, 0);
  printf("MESSAGE RECEIVED...\n");

  /* Controls that received and sent messages are equal */
  printf("Integer number = %d (sent %d) -- ", received.int_num,
         sent.int_num);
  if(received.int_num == sent.int_num) printf(" OK\n");
  else printf("ERROR\n");

  printf("Float numero = %f (sent %f) -- ", received.float_num,
         sent.float_num);
  if(received.float_num == sent.float_num) printf(" OK\n");
  else printf("ERROR\n");

  printf("Char = %c (sent %c) -- ", received.ch, sent.ch);
  if(received.ch == sent.ch) printf(" OK\n");
  else printf("ERROR\n");

  /* Destroys the queue */
  msgctl(qid, IPC_RMID, 0);
}

De code die ik heb geschreven creëert een rij die door het zoon proces wordt gebruikt om zijn data naar de vader te sturen: de zoon genereert random (willekeurige) nummers, stuurt deze naar de vader en beide printen ze uit op de standaard output.

#include <stdio.h>
#include <stdlib.h>
#include <linux/ipc.h>
#include <linux/msg.h>
#include <sys/types.h>

/* Redefines the message structure */
typedef struct mymsgbuf
{
  long mtype;
  int num;
} mess_t;

int main()
{
  int qid;
  key_t msgkey;
  pid_t pid;

  mess_t buf;

  int length;
  int cont;

  length = sizeof(mess_t) - sizeof(long);

  msgkey = ftok(".",'m');

  qid = msgget(msgkey, IPC_CREAT | 0660);

  if(!(pid = fork())){
    printf("SON - QID = %d\n", qid);

    srand (time (0));

    for(cont = 0; cont < 10; cont++){
      sleep (rand()%4);
      buf.mtype = 1;
      buf.num = rand()%100;
      msgsnd(qid, &buf, length, 0);
      printf("SON - MESSAGE NUMBER %d: %d\n", cont+1, buf.num);
    }

    return 0;
  }

  printf("FATHER - QID = %d\n", qid);

  for(cont = 0; cont < 10; cont++){
    sleep (rand()%4);
    msgrcv(qid, &buf, length, 1, 0);
    printf("FATHER - MESSAGE NUMBER %d: %d\n", cont+1, buf.num);
  }

  msgctl(qid, IPC_RMID, 0);

  return 0;
}

Aangeraden leesstof

• 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
• Web page of the #kernelnewbies IRC channel http://www.kernelnewbies.org/
• The linux-kernel mailing list FAQ http://www.tux.org/lkml/

2005-01-14, generated by lfparser_pdf version 2.51