Albero binario 2002-07-23

Scrivere un programma C così organizzato. Si generi innanzitutto un albero binario di processi di altezza ALTEZZA. Se ALTEZZA=1, l’albero è costituito dal solo processo principale. Se ALTEZZA > 1, il processo padre genera due processi, che corrispondono ai figli destro e sinistro. Ognuno dei figli genera due alberi binari di processi di altezza ALTEZZA-1. I processi foglia (quelli dell’ultimo livello) generano un numero casuale, utilizzando le funzioni rand(), e lo comunicano al processo genitore. Il processo genitore riceve i valori dai due processi figli, li somma e comunica il risultato al proprio genitore. Il procedimento termina quando il processo radice riceve i valori dai propri figli e li somma. I processi foglia devono stampare l’identificatore del processo e il valore generato. Tutti gli altri processi devono stampare il proprio identificatore, i valori ricevuti dai figli e la somma così ottenuta. Risolvere il problema utilizzando pipe. PS Per le prove, utilizzare valori bassi di altezza (3-4), per evitare di incorrere in limitazioni sul numero di processi.

Soluzione di Eddy

#include <stdlib.h>
#include <stdio.h>
#include <unistd.h>
#include <math.h>
#include <signal.h>

#define MAXVAL 20

void inputH (int argc, char **argv);
int treeGen (int h);

int main (int argc, char *argv[])
{
   int rv=0;
   inputH (argc, argv);
   treeGen (atoi(argv[1]));
   return rv;
}

void inputH (int argc, char **argv)
{
   if (argc != 2)
   {
      printf ("Usage: %s [ALTEZZA]\n", argv[0]);
      exit (EXIT_FAILURE);
   }
   else
   {
      int h = atoi(argv[1]);
      // maximum number of simultaneous processes per user ID.
      long cldMax = sysconf (_SC_CHILD_MAX);
      // NB. 2^h -1 processes in a binary tree
      if ( h < 1 || (int)pow(2, h)-1 > cldMax)
      {
         printf ("Invalid argument: ALTEZZA is too high/low\n");
         exit (EXIT_FAILURE);
      }
   }
}

int treeGen (int h)
{
   if (h<=1)
   {
      // if h==1 root is handled as a leaf
      // leaf: generates a random value
      int randV = 0;
      srandom ( (int) getpid());
      randV = random()% MAXVAL;
      printf ("**Leaf %d: number %d generated\n", getpid(), randV);
      return randV;
   }
   else
   {

      int lpipefd[2];
      int rpipefd[2];

      int cValue[2]={0,0}; //child values
      pid_t cld [2] = {-1,-1};

      pipe(lpipefd);
      pipe(rpipefd);

      // left cld fork
      cld[0] = fork ();

      if ( cld[0] == 0)
      {

         close(lpipefd[0]);          /* Close unused read end */
         cValue[0] = treeGen (h-1);
         write(lpipefd[1], &(cValue[0]), sizeof(int));
         close(lpipefd[1]);
         exit(EXIT_SUCCESS);

      }

      // right cld fork
      cld[1] = fork ();

      if (cld[1] ==0)
      {
         close(rpipefd[0]);          /* Close unused read end */
         cValue[1] = treeGen (h-1);
         write(rpipefd[1], &(cValue[1]), sizeof(int));
         close(rpipefd[1]);
         exit(EXIT_SUCCESS);

      }

      // parent
      if (cld[0] >0 && cld[1]>0) {
         int sum =0;
         close(lpipefd[1]);          /* Close unused write end */
         close(rpipefd[1]);          /* Close unused write end */

         wait();
         wait();
         printf ("##Node %d\n", getpid());

         while (read(lpipefd[0], &(cValue[0]), sizeof(int)) > 0);
         printf ("\t%d received from %d\n", cValue[0], cld[0]);
         while (read(rpipefd[0], &(cValue[1]), sizeof(int)) > 0);
         printf ("\t%d received from %d\n", cValue[1], cld[1]);

         sum = cValue[0] + cValue[1];
         printf ("\tsum: %d\n", sum);
         return sum;
      }

      // at least a fork returned -1
      if (cld[0] > 0) kill(cld[0] ,SIGCHLD);
      if (cld[1] > 0) kill(cld[1] ,SIGCHLD);

      exit (EXIT_FAILURE);
   }
}