LEZIONE del 26 Novembre

La presentazione del linguaggio C, iniziata con alcuni esempi che evidenziano la sua stretta correlazione con la shell di Unix e la facilità di accedere alla memoria del sistema, non può esaurirsi in poche lezioni. D'altra parte un'analisi esaustiva delle sue strutture dati e dei vari costrutti di controllo richiederebbe un corso intero.

Si continuerà, pertanto, con la discussione di esempi, avendo cura di riferirsi a quegli aspetti che più di altri lo caratterizzano come linguaggio di implementazione di sistema. Si analizzeranno le caratteristiche sintattiche salienti, eventualmente confrontandole con le analoghe di altri linguaggi imperativi. Gli esempi di programma proposti servono, fra l'altro, a mettere in evidenza tali cratteristiche nella pratica implementativa.

Per maggiori approfondimenti sull'impiego del C come linguaggio di programmazione e d'implementazione di sistema si rimanda ai molti manuali disponibili sull'argomento sia cartacei che on-line.

Introduzione al C: Terza parte

Come tutti i linguaggi evoluti di programmazione, anche il C ammette la possibilità di costruire strutture dati arbitrariaramente complesse a partire da un insieme iniziale semplice e non strutturato. Nella tabella seguente sono riportati i tipi di dati primitivi messi a disposizione dal C.

tipo byte
char 1
short int 2
unsigned short int 2
int 4
long int 4
float 4
double 8

In particolare, per ogno tipo predefinito, è stata evidenziata la corrispondente struttura in byte, esplicitando per ciascuno di essi il numero di byte che l'implementazione sottostante (il compilatore) fornisce.

STRUTTURE DATI

Il modo con cui è possibile costruire nuovi tipi a partire da quelli già esistenti è l'usuale meccanismo dei costruttori per gli array e i record con o senza varianti. Nella tabella seguente sono riportati tali costrutti

array element-type var-name[ dimension]
record struct var-name {
element-type element-name;
................
element-type element-name}
record
case
union var-name {
element-type tag-name;
................
element-type tag-name}
definizione
di tipo
typedef type-name
type-definition

E' possibile, anche, definire la dimensione di ciascun campo dei record in termini di "bit", come nell'esempio che segue,

  typedef unsigned int  uint;

  struct S {
    uint a : 4;
    uint b : 5, c : 7;
  }
dove una parola di 2 byte è stata suddivisa in tre campi di dimensione, rispettivamente, 4, 5 e 7 bit.

Un esempio di record con variante è quello riportato nell'esempio seguente in cui il valore memorizzato nella variabile value può essere visto come intero semplice (4 byte) oppure un reale a precisione doppia (8 byte).

  union value {
    int i;
    double d;
  }

La selezione fra una delle maschere con cui guardare tale valore avviene utilizzando l'appropriato campo. Ad esempio, nel semplice programma riportato di seguito, si considera una maschera in cui i 32 bit degli interi vengono raggruppati in modo diverso dall'usuale sequenza di 4 byte.


/*
* mask.c
       applica differenti maschere di lettura per un intero
*/

#include    <stdio.h>
#include    <stdlib.h>

  typedef unsigned int  uint;

  typedef struct {
    uint a : 4;
    uint b : 5, c : 7;
    uint d : 16;
  } Mask;

  typedef union {
    int i;
    Mask m;
  } Value;

int main(int argc, char **argv) {

  Value Z;
  int A, B, C;

  if (argc < 2) {
    printf("Insufficient Parameters\n");
    printf("Usage: mask <int>");
    exit(1); }

  Z.i = atoi(argv[1]);

  A = Z.m.a;
  B = Z.m.b;
  C = Z.m.c;

  printf("(%d)c + (%d)b + (%d)a \n", C, B, A);
  exit(0);
  }

Maschera di lettura di un intero

Nell'implementazione in esame si considerano solamente i 2 byte di ordine più basso; naturalmente, è immediato estendere il risultato dell'applicazione della maschera a tutti e 4 i byte.

COSTRUTTI DI CONTROLLO

Per quanto riguarda, invece le istruzioni, queste ammettono gli usuali costrutti della programmazione strutturata per ottenere istruzioni più complesse. Nella tabella seguente viene riportata la sintassi di alcune di esse. Si tenga presente che mancano, ad esempio, gli schemi che utilizzano e/o chiamano funzioni.

COSTRUTTO
SINTASSI

Ciclo For

for ( expr1; expr2; expr3 )
statement
for ( expr1; expr2; expr3 ) {
statement-block;
}

Alternativa-1

if ( bool-expr )
statement
if ( bool-expr1 ) {
statement-block;
}

Alternativa-2

if ( bool-expr )
statement1 else
statement2
if ( bool-expr1 ) {
statement-block1;
} else {
statement-block2;
}

Assegnazione

varname = expression

Selezione

switch ( bool-expr ) {
case item1 : statement1;
break;
case item2 : statement2;
break;
.............
case itemn : statementn;
break;
default : statementn+1;
break;

Ciclo While

while ( bool-expr)
statement
while ( bool-expr ) {
statement-block;
}

Ciclo Repeat

do
statement;
while ( bool-expr)

Inoltre, il simbolo sintattico = è usato solamente per l'assegnazione e, quindi, non può apparire nelle espressioni booleane come operatore di eguaglianza per il quale, invece, il simbolo è ==, ossia, il doppio uguale.

ARRAY E PUNTATORI

Nel linguaggio C, i puntatori e gli array sono strettamente correlati: basta pensare gli elementi di un array come locazioni successive di memoria. Ad esempio, nel seguente codice C

 
int VETTORE[10], VALUE;
   int *pVETTORE;
 
   pVETTORE = &VETTORE[0];
       /* pVETTORE punta all'indirizzo di VETTORE[0] */
 
   VALUE = *pVETTORE;
       /* VALUE = contenuto di pVETTORE */
si vede che il primo elemento funge da base address della sequenza di locazioni di memoria dove è allocato il vettore. Dalla rappresentazione in memoria dell'array, delineata nella figura seguente

fig.1 : Array e Puntatori

si capisce facilmente quale sia la relazione fra l'indice del vettore e l'indirizzo di offset nella corrispondente area di memoria. Per estrarre l'informazione dal vettore usando i puntatori si deve impiegare un'istruzione del tipo

pVETTORE + N*i == VETTORE[i]

dove N rappresenta la dimensione in byte di ciascun elemento del vettore e che dipende dalla struttura dati dichiarata per ciascun elemento. Si deve fare molta attenzione, comunque, al fatto che non viene fatto alcun controllo sull'indice degli array e sui puntatori per cui si può superare tranquillamente i limiti dello spazio di memoria allocato per il vettore. Nel C tale legame, fra array e puntatori, è ancora più sottile di quanto non appaia a prima vista perchè gli array sono visti e implementati come una sequenza contigua di celle di memoria.


/*
* vector.c
*      accesso agli elementi di un vettore
*/

#include    <stdio.h>
#include    <stdlib.h>

#define     vSize    40
#define     N        4    /* int = 4 byte */

   int VETTORE[vSize];
   void *vBase;
   int *pVETTORE;
   int k, Value;
   int nSize;
 
int main(int argc, char **argv) {

  if (argc < 2) {
    printf("Insufficient Parameters\n");
    printf("Usage: vector <int> [<int>*]\n");
    exit (1); }

  vBase = &VETTORE[0];
       /* vBase punta all'indirizzo di VETTORE[0] */

#ifdef DEBUG
  printf("-------------------------------------------------\n");
  printf("                Debug Information\n");
  printf("-------------------------------------------------\n");
#endif
  for (k = 1; k < argc; k++) {
    pVETTORE = vBase + N*(k - 1);
    *pVETTORE = atoi(argv[k]);
       /* il contenuto di pVETTORE e' il k-esimo parametro */
#ifdef DEBUG
    printf("@%d = VETTORE[%d] <- %d\n", pVETTORE, k-1, *pVETTORE );
#endif
  }
#ifdef DEBUG
  printf("-------------------------------------------------\n");
#endif
  nSize = argc - 1;
  for (k = 0; k < nSize; k++) {
    Value = VETTORE[k];
    printf("VETTORE[%d] = %d\n", k, Value); }
}

Implementazione degli Array

Nell'esempio proposto viene mostrato un vettore di interi il cui primo elemento funge anche da indirizzo base di tutti gli altri allocati successivamente e raggiungibili sia in base al loro indice che all'occupazione di memoria (4 byte) di ciascuno. La compilazione con la traccia degli indirizzi degli elementi del vettore si ottiene col comando

gcc -DDEBUG -o vector vector.c

dopodichè si lancia l'applicazione vector seguita da un certo numero di parametri interi che rappresentano gli elementi del vettore in questione. A questo punto l'esecuzione del comando in esame produce sia gli indirizzi che il loro contenuto.

ORDINAMENTO DI UN VETTORE

Nell'esempio che segue viene proposto il ben noto algoritmo di ordinamento bubble sort, realizzato come comando di shell i cui parametri rappresentano la lista di interi da ordinare. L'implementazione fa uso di un vettore che, dopo l'inizializzazione con i numeri passati come parametri nell'ordine in cui appaiono, vengono riarrangiati in ordine ascendente prima di essere stampati sullo standard output.

/*
* bubble.c
*      sort the integer list passed as arguments
*/

#include    <stdio.h>
#include    <stdlib.h>
#include    <errno.h>

#define     lSize  100

  int dP, fP;
  int pList[lSize];

  void Clear (int lsize, int A[]) {
    int i;
    for (i=0; i<lsize; i++) {
      A[i] = 0;}
    dP = 0;
    fP = 0;
  }

  void Deposit (int lsize, int A[], int K) {
     A[dP] = K;
     dP++;
  }

  int Fetch (int lsize, int A[]) {
     int K;
     K = A[fP];
     fP++;
     return K;
  }

  void bubbleSort(int lsize, int A[], const int N) {
    int i, j;
    int T;
    for (i = N - 1; i > 0; i--)
      for (j = 0; j < i; j++)
        if (A[j] > A[j + 1]) {
          T = A[j];
          A[j] = A[j + 1];
          A[j + 1] = T; }
  }

  int main(int argc, char **argv) {

    int N, k, data;

    if (argc < 2) {
         printf("insufficient parameters\n");
         printf("Usage: bubble int [int]*\n");
         exit(1); }

    Clear(lSize, pList);
    N = argc;
    for (k=1; k<N; k++) {
      data = atoi(argv[k]);
      Deposit(lSize, pList, data);
    }

    bubbleSort(lSize, pList, dP);

    data = Fetch(lSize, pList);
    printf("%d", data);
    for (k=1; k<dP; k++) {
      data = Fetch(lSize, pList);
      printf(", %d", data); }
    printf("\n");
    exit(0);
  }
Si noti, fra l'altro, la simulazione della classe pList con i metodi Clear, Deposit e Fetch.

INPUT/OUTPUT ASINCRONO

Nel seguito viene proposto un esempio di codice C che utilizza risorse del sistema alle quali accede mediante le opportune chiamate di sistema. Nel caso specifico viene controllato in modo asincrono l'input/output mediante accesso diretto ai descrittori dello stdin (valore 0) e stdout (valore 1) e l'utilizzo delle interruzioni (signal) le quali, pertanto, devono essere controllate esplicitamente dal programma.

/*
 * Copy standard input to standard output, using asynchronous I/O.
 */

#include     <stdio.h>
#include     <stdlib.h>
#include     <signal.h>
#include     <fcntl.h>

#define      LINESIZE        80
#define      FALSE           0
#define      TRUE            1
#define      stdIN           0
#define      stdOUT          1

int          sigFLAG;

main() {
  int       n;
  char      Msg[LINESIZE];
  void      sigio_handler();

signal(SIGIO, sigio_handler);

if (fcntl(stdIN, F_SETOWN, getpid()) < 0)
  perror("F_SETOWN error");

if (fcntl(stdIN, F_SETFL, FASYNC) < 0)
  perror("F_SETFL FASYNC error");

while (TRUE) {
  sigblock(sigmask(SIGIO));
  while (sigFLAG == 0) sigpause(0);    /* wait for a signal */
  /*
  * We're here if (sigflag != 0). Also, we know that the
  * SIGIO signal is currently blocked.
  */
  if ((n = read(stdIN, Msg, LINESIZE)) > 0) {
    if (write(stdOUT, Msg, n) != n) perror("write error"); } 
  else if (n < 0)  perror("read error");
       else if (n == 0) exit(0);       /* EOF */

  sigFLAG = 0;                         /* turn off our flag */
  sigsetmask(0);                       /* and reenable signals */
  }
}

void sigio_handler() {
  sigFLAG = 1;                         /* just set flag and return */
}
Si noti anche la definizione della funzione sigio_handler() necessaria all'implementazione della routine di risposta delle interruzioni.

Gestione dei Thread e Sincronizzazione

L'estensione all'impiego delle coroutine nei linguaggi permette di avere a disposizione uno strumento semplice e potente di gestione delle chiamate di procedura per cui è possibile riprendere l'esecuzione di una procedura, precedentemente sospesa, senza richiedere la preventiva terminazione di quella correntemente in esecuzione.

Analogamente nel C per Unix, uno schema multithread, si basa sulla presenza simultanea di più flussi computazionali in cui accade che uno solo è attivo essendo gli altri sospesi in attesa del verificarsi di certi eventi.

La gestione dei thread e la relativa sincronizzazione è ottenuta con la seguente coppia di file. Il primo, kernel.h, contiene le necessarie definizioni le quali dipendono, in generale, dal tipo di piattaforma utilizzata. Ciò si ottiene scrivendo codice C per la compilazione condizionata, resa possibile dal C PreProcessor

/*
 *  file kernel.h
 */

#include   <stdio.h>
#include   <stdlib.h>
/*-------------------------------------------------------------------
|                   definizioni per Unix Solaris                    |
-------------------------------------------------------------------*/
#ifdef Solaris
#include   <thread.h>
#include   <synch.h>

typedef    thread_t       process ;
typedef    sema_t         semaphore ;
#endif

/*-------------------------------------------------------------------
|                      definizioni per Linux                        |
-------------------------------------------------------------------*/
#ifdef Linux
#include   <pthread.h>
#include   <semaphore.h>

typedef    pthread_t      process ;
typedef    sem_t          semaphore ;
#endif


#define Procedure(X) void *(*X)(void *)

typedef    long int       integer ;
typedef    unsigned int   value ;


extern void NewThread(Procedure(proc), integer StackSize, process *TID);
extern int JoinThread(process TID, process Target);
extern int Thread(process *TID);

extern void Assign(semaphore *s, value k);
extern void Suspend(semaphore *s);
extern void Awake(semaphore *s);
extern void Score(semaphore *s, int * sval);

Il secondo, denominato kernel.c contiene il codice specifico che implementa sia la creazione e la gestione dei processi che le funzioni per la manipolazione dei semafori.

/*
 *  file kernel.c
 */

#include "kernel.h"

/*-------------------------------------------------------------------
|                creazione e gestione dei processi                  |
-------------------------------------------------------------------*/

void NewThread(Procedure(proc), integer StackSize, process *TID)
{
#ifdef Solaris
  if (thr_create(NULL, StackSize, proc, NULL, THR_NEW_LWP, TID))
    *TID = -1;
#endif
#ifdef Linux
  if (StackSize == 0) {
    if (pthread_create(TID, NULL, proc, NULL))
      *TID = -1; }
  else {
    fprintf(stderr, "thread cannot be created\n") ;
    exit(2) ;}
#endif
};


int JoinThread(process TID, process Target)
{
#ifdef Solaris
   return thr_join(TID, &Target, NULL);
#endif
#ifdef Linux
   return pthread_join(TID, NULL);
#endif
};

int Thread(process *TID) {
#ifdef Solaris
  return thr_self();
#endif
#ifdef Linux
  return pthread_self();
#endif
};

/*-------------------------------------------------------------------
|                        gestione dei semafori                      |
-------------------------------------------------------------------*/

void Assign(semaphore *s, value k)
{
  /* initialize the semaphore */

#ifdef Solaris
  sema_init(s, k, USYNC_THREAD, 0) ;
#endif
#ifdef Linux
  sem_init(s, 0, k) ;
#endif
} ;

void Suspend(semaphore *s)
{
#ifdef Solaris
  sema_wait( s ) ;
#endif
#ifdef Linux
  sem_wait( s ) ;
#endif
} ;

void Awake(semaphore *s)
{
#ifdef Solaris
  sema_post( s ) ;
#endif
#ifdef Linux
  sem_post( s ) ;
#endif
} ;

void Score(semaphore *s, int * sval)
{
#ifdef Solaris
  sema_getvalue( s, sval ) ;
#endif
#ifdef Linux
  sem_getvalue( s, sval ) ;
#endif
} ;

Si noti come il primo debba essere necessariamente incluso nel secondo per poter guidare il compilatore nella corretta generazione del codice oggetto delle procedure.

Impiego di Thread e Semafori

Facendo riferimento alle funzioni e procedure appena viste, nel seguito viene discusso un semplice esempio di programma nel quale sono attivati e gestiti due thread. In base alla definizione di thread si tratta di processi leggeri in grado di essere eseguiti dal kernel, indipendentemente l'uno dall'altro grazie al meccanismo per il quale, sebbene all'interno dello stesso processo, ciascuno di essi dispone di un proprio stack privato per l'esecuzione al "runtime".

Se i thread devono utilizzare variabili condivise diventa esplicita responsabilità del programmatore impiegare meccanismi di sincronizzazione per controllarne l'ordine di accesso. Il semaforo è uno degli strumenti a disposizione del programmatore per controllare la sincronizzazione.

/*
 *  file coroutine.c
 */

#include   <stdio.h>
#include   <stdlib.h>
#include   "kernel.h"

void *attendi();
void *avanza();

typedef enum {Old, New} Tag;
typedef unsigned int uint;
typedef union {
  int p;
  struct {
    uint mask : 11;
    uint tid : 12;
    uint indx : 9;
  } m;
} Mask;

  process T0, T1, T2, T3;
  semaphore mutex;
  int N;
  int sec;

int Gettid(Tag Idx, process *Pid) {
  Mask M;
  switch (Idx) {
    case Old: M.p = Thread(Pid); break;
    case New: M.p = *Pid; break; }
  return M.m.tid;
}


int main(int argc, char **argv) {

  int Tid;

  if (argc < 3) {
    printf("Insufficient Parameter\n");
    printf("Usage: sample <int> <sec>\n");
    exit(1); }

  N = atoi(argv[1]);
  sec = atoi(argv[2]);
  Tid = Gettid(Old, &T0 );
  printf("Main thread = %d\n", Tid);

  Assign(&mutex, 0);    /* inizializzato a 0,

      /* crea due processi "leggeri" */

  NewThread( attendi, 0, &T1 );
  if (T1 == -1)
    fprintf(stderr, "Can't create thread 1\n"), exit(1);
  printf("Nuovo processo %d\n", Gettid(New, &T1));

  NewThread( avanza, 0, &T2 );
  if (T2 == -1)
    fprintf(stderr, "Can't create thread 2\n"), exit(1);
  printf("Nuovo processo %d\n", Gettid(New, &T2));

      /* ricongiungi i due flussi */

  if (JoinThread(T1, T2))
    fprintf(stderr, "thr_join error\n"), exit(2);
  printf("Thread %d terminated.\n", Gettid(New, &T1));
  printf("Thread %d terminated.\n", Gettid(New, &T2));

      /* termina */

  printf("Parent PID(%d): exiting...\n", getpid());
  exit(0);
}


void *attendi()  {
    integer j;

    for (j = 0; j < N; j = j + 1) {
       printf("Child PID(%d): waiting...\n", Gettid(Old, &T1));
       Suspend(&mutex);

       printf("Child PID(%d): decrement semaphore.\n", Gettid(Old, &T1));}
}

void *avanza()  {
    integer i;

    sleep(2);

    for (i = 0; i < N; i = i + 1) {
       printf("Parent PID(%d): increment semaphore.\n", Gettid(Old, &T2));
       Awake(&mutex);

       sleep(sec);}
}
Per la compilazione in ambiente Linux si utilizzi il comando
   
gcc -DLinux -lpthread -o sample coroutine.c kernel.c
e lo si lanci eseguendo il comando
   
sample Ncycles secs
dove Ncycles è il numero di cicli da eseguire mentre secs è il tempo di attesa in secondi fra un ciclo e il successivo del thread avanza. Si noti l'utilizzo della libreria di sistema pthread per la creazione e la gestione dei thread, e l'impiego dei semafori.