Threads et synchronisation avec sémaphores¶

Objectifs¶

• Mettre en oeuvre des programmes multithreadés
• Mettre en oeuvre des mécanismes de synchronisation de programmes multithreadés reposant sur les sémaphores

Remarques préliminaires¶

• La commande make permet de compiler un programme dont les sources sont réparties sur plusieurs fichiers. Pour une description simple et suffisante pour nos séances de make et des fichiers makefile, on peut lire ce tutoriel.
• Il existe de nombreux outils très utiles au développement regroupés dans le projet GNU. Vous pouvez lire ce document d'introduction aux outils de développement GNU.
• Dans la suite de l'énoncé on appellera bibliothèque un ensemble composé d'un fichier .c et d'un fichier .h pouvant contenir des définitions de type, des fonctions et des procédures mais pas de fonction main().
• Consigne générale :
  • on écrira un makefile permettant de compiler chacun des programmes demandés.
  • À la fin du TD, le fait d'exécuter la commande make devra recompiler chacun des exercices de ce TD.
  • Avant toute programmation, vous devez lire l'énoncé de l'exercice jusqu'au bout !

I - Threads, données partagées et synchronisation de threads¶

Afin de paralléliser les traitements il est souvent intéressant de diviser un programme en plusieurs fils d’exécution. Dans cet exercice, on considère le cas d'un serveur devant transmettre des messages. On trouvera un (ou plusieurs) thread(s) pour lire dans une (ou plusieurs) source(s) et un (ou plusieurs threads) chargé(s) de transmettre des données. Dans ce contexte les threads chargés de la lecture et ceux chargés de l'écriture doivent partager une zone de la mémoire. On a donc le schéma simplifié suivant :

L'objectif de cet exercice est d'implanter le schéma ci-dessus. L'étape 1 du thread 1 et l'étape 2 du thread 2 seront réalisées avec la bibliothèque permettant de lire et écrire des lignes dans un fichier implémentée lors du TD-machine 1 de l'unité de systèmes d'exploitation. Lors de ce TD vous avez ainsi du obtenir deux fichiers sources qui ressemblent fortement à ceux-ci :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

#ifndef _GESTION_FICHIERS_H
#define _GESTION_FICHIERS_H

#define TAILLEBUF 8191

/* attention, realise une allocation dynamique de la chaine retournée 
 * penser à libérer la mémoire !
*/
char * litLigne(int fd);

/* prend une chaine de caractère, et l'écrit dans fd suivi d'un retour à la ligne
 * retourne -1 en cas d'echec */
int ecritLigne(char* chaine,int fd);

#endif

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

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

#include "gestionFichiers.h"

char * litLigne(int fd)
{
    int i;
    int nbr;
    char buf[TAILLEBUF];
    char * s;

    for(nbr = 0 ; nbr < TAILLEBUF ; nbr++){
        int rc = read(fd, buf+nbr,1);
        if( rc == 0  ){ /*  fin de fichier */
            return NULL;
        }
        if(rc== -1){/* erreur */
            perror("erreur de lecture dans litLigne");
            return NULL;
        }

        if(buf[nbr]=='\n')break;
    } 

    s=(char*)malloc(nbr+1);
    if(s==NULL){
        perror("alocation issue in litLigne");
        return NULL;
    }

    for(i=0;i<nbr;i++)
        s[i]=buf[i];
    s[i] = '\0';
    return s;
}

/* retourne -1 en cas d'echec, taille de la chaine sinon */
int ecritLigne(char* chaine,int fd)
{

    int size_s = strlen(chaine);
    int nbw=0;
    int tmp;

    while(nbw!=size_s){
        tmp = write(fd,chaine+nbw,size_s-nbw);
        if(tmp==-1){
            perror("write issue in ecritLigne");
            return -1;
        }
        nbw+=tmp;
    }
    tmp = write(fd,"\n",1);/* on ne met pas le \n dans chaine car ne marcherait pas avec une chaine statique */
    if(tmp==-1){
        perror("write issue in ecritLigne");
        return -1;
    }
    return nbw;

}

La source sera le fichier texte

1
2
3

Je suis le premier message.
Le second c'est moi.
Le troisieme message est le dernier !

et la destination sera un fichier texte Destination.txt.

A. Implémentation brute force¶

Implantez le schéma ci-dessus.

La mémoire partagée sera un buffer de char déclaré comme variable globale par :

char buffer[MAX];

Si vous êtes en avance vous pouvez proposer une solution où le buffer est alloué dynamiquement dans le fils d'exécution principal et transmis aux threads concurrents via les paramètres de leur routine d'exécution.

B. On réfléchit¶

Quel est le problème de la solution A ? Proposez (sans l'implémenter) un schéma de solution au problème de A avec un mutex.

C. On réfléchit encore puis on programme¶

Quel est le problème avec votre solution précédante ? Proposez une solution avec deux sémaphores.

Attention, votre programme doit fonctionner quelque soit la taille du buffer d'échange partagé entre les thread. Si le buffer d'échange est plus petit que la taille d'une ligne, cela veut dire que le thread 2 doit pouvoir lire les caractères un par un dans le buffer partagé, sans pour autant les écrire (puisqu'il écrit avec ecritLigne() une ligne entière). Il faudra certainement penser à utiliser un buffer local supplémentaire dans le thread 2... De plus le thread 2 doit pouvoir se terminer lorsque le thread 1 n'écrit plus. Pour cela le thread 1 pourra terminer par un ajout du caractère spécial EOF dans le buffer partagé.

II - Threads concurrents¶

On a 3 threads \(P_1\), \(P_2\), et \(P_3\) concurrents. Le code indépendant de chaque thread \(P_i\) (i=1,2,3) est le suivant :

1
2

for(j = 0; j < 10; j++)
    printf("Affichage %d du thread %d\n", j+1, i); // Thread Pi avec i = 1, 2, 3

A. Réflexion¶

Indiquez comment synchroniser les threads P1, P2 et P3 avec des sémaphores pour obtenir l'affichage suivant :

Affichage 1 du thread 1
Affichage 1 du thread 2 
Affichage 1 du thread 3 
Affichage 2 du thread 1 
Affichage 2 du thread 2
Affichage 2 du thread 3
Affichage 3 du thread 1
Affichage 3 du thread 2
Affichage 3 du thread 3 
...

B. Action¶

Programmez la solution décrite à la question précédente.