Plan

Typedef en C, lint

Mémoire partagée

Sémaphores

Synchronisation par le système de fichier (lock)

Pipes

Langages à flux de données

Séquentialité et select

Exercices.

Typedef en C -- lint

malloc permet d'allouer des objets dynamiques dans le tas (le heap de Pascal).

typedef autorise de nouveaux types

typedef int Length;

Lenth x, y[30];

qui peuvent être récursifs

typedef struct tnode *Treeptr;

typedef struct tnode {
    char *word;
    int count;
    Treeptr left;
    Treeptr right;
} Treenode;

Pb: comment faire un arbre sans les déclarations de pointeurs précédentes?

lint est un programme qui permet de faire des vérifications intermodules en C. Bien utile parfois pour trouver des erreurs de type. En principe, moins nécessaire avec C ANSI.

Communication entre processus par mémoire partagée

shmget, shmat opérations Système V.

Une mémoire partagée 2 fois dans un même processus

int shmid;

main()
{
    int i, *pint;
    char *addr1, *addr2;
    extern char *shmat();

    shmid = shmget(75, 128*1024, 0777|IPC_CREAT);
    addr1 = shmat(shmid, 0, 0);
    addr2 = shmat(shmid, 0, 0);
    printf ("addr1 0x%x, addr2 0x%x\n", addr1, addr2);

    pint = (int *) addr1;
    for (i = 0; i < 256; i++)
        *pint++ = i;
    *pint = 256;

    pint = (int *) addr2;
    for (i = 0; i < 256; i++)
        print ("index %d, value %d\n", i, *pint++);

    pause();
}

Communication entre processus par mémoire partagée

shmget, shmat opérations Système V.

Une mémoire partagée 2 fois dans un même processus

int shmid;

main()
{
    int i, *pint;
    char *addr;
    extern char *shmat();

    shmid = shmget(75, 64*1024, 0777);
    addr = shmat(shmid, 0, 0)

    pint= (int *) addr;
    while (*pint == 0)
        ;
    for (i = 0; i < 256; i++)
        printf ("%d\n", *pint++):
}

Duplication de file descriptors

Si on écrit un shell, on veut lancer des nouveaux programmes avec exec et avec l'entrée/sortie standard prédéfinie (à cause de < ou >). Or les file descriptors traversent exec. D'où

fd0 = open ("fichier1", 1);
fd1 = open ("fichier2", 2);
fd3 = open ("fichier3", 2);
if ((pid = fork()) == 0) {
    close (0); dup (fd1);
    close (1); dup (fd2);
    close (2); dup (fd3);
    execlp ("prog", ...);
    exit (1);
}

dup() duplique le file descriptor sur le premier disponible. On peut aussi utiliser dup2().

Réciproquement, on veut pouvoir remettre au terminal les file descriptors standards avec

fd0 = open ("/dev/ttÿ, 1);
fd1 = open ("/dev/ttÿ, 2);
fd3 = open ("/dev/ttÿ, 2);
if ((pid = fork()) == 0) {
    close (0); dup (fd1);
    close (1); dup (fd2);
    close (2); dup (fd3);
    execlp ("prog", ...);
    exit (1);
}

Pipes

pipe() crée un tampon que l'on peut écrire d'un côté et lire de l'autre de manière asynchrone. Il renvoie 2 file descriptors pour lire et écrire.

char buf[1024];
int fds[2];

strcpy (buf, "Coucou!");
pipe(fds);
for (;;) {
    write (fds[1], buf, strlen ("Coucou!"));
    read (fds[0], buf, 1024);
}

En général, un pipe marche avec un fork()

pipe (fds);
if ((pid1 = fork()) == 0) {
    close (1); dup (fds[1]);
    ...
}
if ((pid2 = fork()) == 0) {
    close (0); dup (fds[0]);
    ...
}

Pipes -- 2

Les shells ne permettent que les pipes linéaires. En System V, pipes nommés. En C, graphes arbitraires de pipes: crible d'Erathosthène, générer les nombres de la forme 2^a 3^b 5^c sans omission, ni répétition (cf les programmes dataflow de Kahn et MacQueen, ou les langages LUSTRE de Halbwachs, LUCID de Ashcroft).

fopen() et fclose() permettent de prendre l'entrée ou la sortie standard d'une commande sur un pipe.

  FILE *fopen(
          const char *path,
          const char *mode);

Canaux de communication (CCS, CSP)

les canaux de communication ont une longueur de 1.

il faut des ``rendez vous'' entre émetteur et récepteur.

plus simple à implanter (Transputer).

très belle théorie CSP, CCS, pi-calcul, OCCAM.

version asynchrone avec des queues sur les canaux.

TIT     .Communication and concurrency
SLA     .Robin Milner. - New York ; London ; Toronto : Prentice Hall,
        .1989. - XI-260 p. ; 24 cm. - (Prentice Hall international
        .series in computer science).

TIT     .Communicating sequential processes
SLA     .C.A.R. Hoare. - Englewood Cliffs, NJ ; London ;
        .Mexico : Prentice-Hall, 1985. - VIII-256 p. ;
        .24 cm. - (Prentice-Hall international series
        .in computer science).

TIT     .Algebraic theory of processes
SLA     .Matthew Hennessy. - MIT Press, 1988.

Déterministes -- non déterminisme

Déterminisme ==> un seul résultat. Majorité des programmes.

while ((c = getchar ()) != EOF) {
...
}

Si on veut attendre à la fois un événement souris ou clavier, on veut une attente multiplexée, i.e.

while (((c = getchar ()) != EOF) 
     || ((e = MouseEvent() != NULL))) {
...
}

impossible car getchar() est bloquant, et comme on évalue alors de droite à gauche, on loupera les événements souris.

Une solution est d'avoir des entrées/sorties non bloquantes (en fait possibles en Unix), et on fait de l'attente active. Mais on gâche des cycles machine. (cf la fonction Button de MacPascal).

Une autre solution est d'avoir dans le noyau un driver d'événements qui multiplexe (et sérialise) les événements clavier-souris. C'est ce qu'ont la plupart des Unix qui veulent s'interfacer efficacement à un système de fenêtres. Mais c'est théoriquement insatisfaisant (changer le noyau), quoique très efficace en pratique.

Déterministes -- non déterminisme

Remarque: on peut avoir parallélisme et déterminisme: réseaux de Kahn-MacQueen, systèmes purement fonctionnels (confluence).

Kahn G. 
The semantics of a Simple Language for Parallel Programming,
Proc. of IFIP Congress 74, Amsterdam, North Holland, 1974.

Le non déterminisme est introduit par fork().

if (fork() == 0) {
    while ((c = getchar()) != EOF) {
        ...
    } else
    while ((e = MouseEvent() != NULL)) {
        ...
    }

La solution fork() marche bien (en supposant mémoire partagée), sauf si les événements arrivent en rafale. Alors les lectures se battent avec la communication de contexte des processus.

Primitive non séquentielle

Un appel-système nouveau select().

select() spécifie le nombre d'événements en attente dans les file descriptors décrits par les 3 masques. Un délai maximal peut être donné.

nfound = select(nfds, readfds, writefds, execptfds, timeout)

          fd_set *readfds,
          fd_set *writefds,
          fd_set *exceptfds,
          struct timeval *timeout) ;

select() regarde l'état des descripteurs fd_1, fd_2, ... fd_n, et indique si les lectures ou écritures sur ces descripteurs bloquent. Ainsi, on peut savoir s'il y a des caractères disponibles en input ou si une output est bloquée. Les descripteurs sont représentés par la fonction caractéristique de leur ensemble représentée par un tableau de bits. nfds est le nombre de bits de cet ensemble (donc le maximum (+1) de ces file descriptors).

Un bon exemple est le multiplexeur qui attend sur 2 canaux.

Non déterminisme dans d'autres langages.

En CCS, CSP ou OCCAM, il y a des gardes et on peut attendre sur plusieurs simultanément. Idem pour Esterel (Berry) et Squeak ( Pike & Cardelli).

Berry G., Couronne ' P., Gonthier G.. 
Synchronous programming of reactive systems: 
an introduction to Esterel. 
In K. Fuchi and M. Nivat, editors, 
Programming of Future Generation Computers, 
Elsevier Science Publisher B.V. (North Holland), 1988.
INRIA Report 647.

Pike R., Cardelli L., 
Squeak: a Language for Communicating with Mice. 
Proc of the ACM-SIGGRAPH Conference. 1985(?)

Certains systèmes autorisent des processus légers (Mach, Topaz, Chorus). Il y a donc un minifork() qui ne copie que les registres et pile (et pas tout l'espace data qui reste partagé. Alors select() devient moins utile, et on programme plus naturellement avec minifork() et entrées/sorties bloquantes, sans avoir les inconvénients de la commutation lourde entre processus et de la lourdeur de la communication.

Exercices en TD et à la maison

Débutants: manipuler quelques pipes pour un calcul à la Lustre, sauf le crible d'Erathosthène qui demande trop de processus.

Chevronnés 1: ajouter les pipes au shell et le traitement des signaux.

Chevronnés 2: faire la commande cpustate qui affiche constamment la charge du cpu. Il faut lire la mémoire à l'adresse de la bonne variable, qu'on obtient en regardant la table des symboles de /vmunix. Utiliser nlist().