Gestion des sémaphores pour synchronisation tampon circulaire (produit-consommateur)

Ce document présente une série d'exercices corrigés sur la gestion des sémaphores pour la synchronisation dans le cadre du problème classique du producteur-consommateur et d'autres scénarios de synchronisation concurrente. Il s'agit d'un examen ou d'un devoir qui évalue la compréhension des mécanismes de synchronisation, la capacité à concevoir des solutions correctes utilisant des sémaphores, ainsi que la maîtrise des concepts de section critique, d'interblocage, de famine et de moniteurs.

Solution 1

On demande d'identifier les sémaphores utilisés et de comprendre leur rôle dans la synchronisation de deux tampons circulaires entre plusieurs processus.

a. Les sémaphores sont :

• mutex0 et mutex1 pour contrôler l'accès exclusif aux tampons respectifs.
• Vide0, Vide1, Plein0 et Plein1 pour bloquer un processus lorsque le tampon est vide ou plein.

b. Initialisation des sémaphores :

mutex1 = 1, mutex0 = 1, Vide0 = N, Vide1 = N, Plein0 = 0, Plein1 = 0;

Les processus P0, P1 et P2 fonctionnent ainsi :

P1
int icp=0;
Répéter
{
    P(Plein0);
    P(Vide1);
    P(mutex0);
    P(mutex1);
    T1[icp] = T0[icp];
    V(mutex1);
    V(mutex0);
    icp = (icp + 1) mod N;
    V(Plein1);
    V(Vide0);
}

P0
Message m, mc;
int ip=0;
Répéter
{
    m = lire();
    mc = Encrypter(m);
    P(Vide0);
    P(mutex0);
    T0[ip] = mc;
    V(mutex0);
    ip = (ip + 1) mod N;
    V(Plein0);
}

P2
Message mc;
int ic=0;
Répéter
{
    P(Plein1);
    P(mutex1);
    mc = T1[ic];
    V(mutex1);
    ic = (ic + 1) mod N;
    V(Vide1);
    Envoyer(mc);
}

Réponse : Les sémaphores sont correctement utilisés pour assurer la synchronisation entre les producteurs et consommateurs sur deux tampons circulaires, avec protection mutuelle et gestion des états plein/vide.

Solution 2

On étudie un producteur et un consommateur utilisant un tampon circulaire de taille N avec des sémaphores pour gérer l'accès et la synchronisation.

Le producteur lit un tableau de caractères, puis dépose les caractères un par un dans le tampon, en utilisant les sémaphores Vide, Plein et Mutex pour la synchronisation.

char T[N]; // tableau de N caractères
Semaphore Plein = 0, Vide = N, Mutex = 1;

Producteur {
    int ip = 0, M;
    char ch[N];
    Répéter {
        M = Lire(ch, N);
        Pour i = 1 à M pas 1 faire P(Vide);
        P(Mutex);
        Deposer(ch, M, ip);
        V(Mutex);
        Pour i = 0 à M-1 pas 1 faire V(Plein);
        ip = (ip + M) % N;
    }
}

Consommateur {
    int ic = 0;
    char c;
    Répéter {
        P(Plein);
        P(Mutex);
        c = Retirer(ic);
        V(Mutex);
        V(Vide);
        ic = (ic + 1) % N;
    }
    Traiter(c);
}

1. Risque de famine : Le risque de famine existe si un processus est constamment bloqué par un autre qui monopolise le sémaphore. Ici, la gestion FIFO des sémaphores n'est pas explicitée, donc la famine est possible si le producteur ou le consommateur est favorisé.

2. Moniteur : Un moniteur regroupe toutes les sections critiques d'un problème donné dans une seule structure, gérant automatiquement l'accès exclusif. Cela facilite la compréhension et l'implémentation du code de synchronisation.

Solution 3

On traite le problème des philosophes mangeant avec un sémaphore binaire pour garantir qu'un seul philosophe mange à la fois.

1. Un sémaphore binaire mutex = 1 suffit :

Semaphore mutex = 1;
Fonction Shaolin(i in [0,2]) {
    P(mutex);
    PrendreFourchettes(i);
    Manger();
    ReposerFourchettes(i);
    V(mutex);
}

2. Gestion de plusieurs buffers avec sémaphores :

#define NB_BUFF 2
#define BUFF_SIZE 4
sem_t sem_libre[NB_BUFF];
sem_t sem_occupe[NB_BUFF];
int tab[NB_BUFF][BUFF_SIZE];

void *ordonnanceur(void *inutilise) {
    int i[NB_BUFF], buff;
    for(buff = 0; buff < NB_BUFF; buff++) i[buff] = 0;
    buff = 0;
    while (1) {
        if (sem_trywait(&sem_libre[buff]) == -1) {
            buff = (buff + 1) % NB_BUFF;
            continue;
        }
        tab[buff][i[buff]++ % BUFF_SIZE] = prochainProc();
        sem_post(&sem_occupe[buff]);
    }
}

Réponse : L'utilisation des sémaphores permet de gérer plusieurs buffers circulaires en évitant les conflits d'accès et en assurant la synchronisation entre producteurs et consommateurs.

Solution 4

On analyse un système avec trois processus synchronisés par des sémaphores pour exécuter des cycles en séquence.

1. Initialisation :

Semaphore S1=1, S2=1, S13=0, S23=0;

Les processus P1, P2 et P3 s'exécutent en boucle :

P1() {
    int n=0;
    while(true) {
        P(S1);
        printf("cycle %d de %d", n++, i);
        V(S13);
    }
}

P2() {
    int n=0;
    while(true) {
        P(S2);
        printf("cycle %d de %d", n++, i);
        V(S23);
    }
}

P3() {
    int n=0;
    while(true) {
        P(S13);
        P(S23);
        printf("cycle %d de %d", n++, i);
        V(S1);
        V(S2);
    }
}

2. Extension à 10 producteurs et 10 consommateurs avec une liste infinie.

3. Séquencement avec 3 sémaphores pour la gestion des feux de circulation et des threads producteurs/consommateurs.

Réponse : La synchronisation est assurée par des sémaphores de séquencement et des mutex pour éviter les conflits et garantir l'ordre d'exécution.

Solution 5

On présente une communication entre deux processus A et B avec des sémaphores pour synchroniser le dépôt et la récupération de messages.

1. Sémaphores :

semaphore SA=0, SB=0;

Processus A :

while (1) {
    lire(mess);
    depot(mess);
    V(SB);
    P(SA);
    recuperer(rep);
}

Processus B :

while (1) {
    P(SB);
    recuperer(mess);
    reponse(mess, rep);
    depot(mess);
    V(SA);
}

2. Extension avec un troisième processus C et un mutex pour protéger l'accès critique :

semaphore SA=0, SB=0, SC=0, mutex=1;

Les processus utilisent P(mutex) et V(mutex) pour protéger les sections critiques et les sémaphores SA, SB, SC pour la synchronisation.

Réponse : Cette solution permet une communication synchronisée entre plusieurs processus avec protection des sections critiques.

Solution 6

Synchronisation de plusieurs modules (mRC, mBO, mAS, mEM) avec différents sémaphores pour gérer l'ordre d'exécution.

Sémaphores :

Semaphore SRC=1, SBO=1, SAS1=0, SAS2=0, libre=N, occupe=0, mutex=1;

Chaque module attend et signale les sémaphores pour assurer l'ordre :

mRC() {
    while (1) {
        P(SRC);
        RC();
        V(SAS1);
    }
}

mBO() {
    while (1) {
        P(SBO);
        BO();
        V(SAS2);
    }
}

mAS() {
    while (1) {
        P(SAS1);
        P(SAS2);
        P(libre);
        AS();
        V(SRC);
        V(SBO);
        V(occupe);
    }
}

mEM() {
    while (1) {
        P(occupe);
        P(mutex);
        EM();
        V(mutex);
        V(libre);
    }
}

Réponse : La synchronisation complexe entre modules est assurée par une combinaison de sémaphores binaires et comptables pour garantir l'exclusion mutuelle et l'ordre d'exécution.

Solution 7

Gestion de robots traversant des segments avec sémaphores pour éviter les conflits et interblocages.

Sémaphores :

Semaphore SAB=1, SBC=1, SBD=1;

Processus RobotAC :

P(SAB);
TraverserSegAB();
P(SBC);
V(SAB);
TraverserSegBC();
V(SBC);
P(SBD);
TraverserSegBD();
P(SAB);
V(SBD);
TraverserSegAB();
V(SAB);

Processus RobotDA suit une logique similaire.

2. Analyse :

• Les demandes d'accès sont mémorisées dans des files FIFO, ce qui évite la famine si les durées de traversée sont finies.
• Pas d'interblocage car aucun robot ne détient un segment tout en attendant un autre détenu par un autre robot dans un cycle.

Réponse : La solution garantit l'absence d'interblocage et limite le risque de famine grâce à la gestion FIFO des sémaphores.

Solution 8

Synchronisation d'un feu de circulation avec deux sémaphores pour gérer les phases et éviter les blocages.

Sémaphores :

Semaphore SI1=1, SI2=1, SF1=1, SF2=0;

Processus Changement :

int Feu = 1;
while (1) {
    sleep(Duree_du_feu);
    if (Feu == 1) {
        P(SF1);
        V(SF2);
        Feu = 2;
    } else {
        P(SF2);
        V(SF1);
        Feu = 1;
    }
}

Processus Traversee1 et Traversee2 utilisent SI1, SI2, SF1, SF2 pour s'assurer que les voitures ne bloquent pas le changement de feu.

2. Moniteur Intersection :

Variables booléennes et compteurs pour gérer les attentes et les signaux entre les différentes phases du feu.

Réponse : L'utilisation combinée de sémaphores et de moniteurs permet une gestion efficace et sans blocage des feux de circulation.

Solution 9

Implémentation d'un compteur d'événements avec sémaphores et liste de sémaphores pour gérer des attentes conditionnelles.

Structure :

struct CompteurEvenement {
    int val;
    semaphore mutexE;
    struct listeSem { semaphore psem; int pval; } *Lsem;
};

Fonction Await :

void Await(CompteurEvenement *E, int Valeur) {
    P(E->mutexE);
    if (E->val < Valeur) {
        semaphore *new_sem;
        init(sem) = 0;
        ajouter(sem, Valeur) à E->Lsem;
        V(E->mutexE);
        P(sem);
    } else {
        V(E->mutexE);
    }
}

Fonction Advance :

void Advance(CompteurEvenement *E) {
    P(E->mutexE);
    E->val = E->val + 1;
    Pour chaque (sem, v) dans E->Lsem tel que E->val >= v {
        V(sem);
        supprimer cet élément;
    }
    V(E->mutexE);
}

Fonction Read :

int Read(CompteurEvenement *E) {
    int v;
    P(E->mutexE);
    v = E->val;
    V(E->mutexE);
    return v;
}

Réponse : Cette structure permet de gérer efficacement des attentes multiples sur un compteur d'événements avec protection mutuelle.

Solution 10

Gestion d'un passage à niveau avec plusieurs sémaphores pour coordonner trains et contrôleur.

Sémaphores :

Semaphore quitte=0, passage=0, present=0;

Fonction Contrôleur :

while (1) {
    P(present);
    FermerBarrieres();
    V(passage);
    P(quitte);
    while (PNB(present)) {
        V(passage);
        P(quitte);
    }
    OuvrirBarrieres();
}

Fonction Train :

V(present);
P(passage);
Traverser();
V(quitte);

Explications :

• present compte le nombre de trains présents.
• passage mémorise les trains en attente de passage.
• quitte bloque/débloque le contrôleur pendant la traversée.
• PNB est l'équivalent de sem_trywait.

Réponse : La synchronisation garantit que les barrières sont fermées pendant la traversée et ouvertes uniquement lorsque tous les trains ont passé.

Solution 11

Analyse critique d'une implémentation incorrecte d'une fonction d'échange de cours entre étudiants.

Problèmes identifiés :

• On désinscrit toujours l'utilisateur du premier cours même s'il n'a pas pu être inscrit au deuxième.
• Risque d'interblocage car on verrouille le deuxième cours alors que le premier est déjà verrouillé, ce qui peut causer un blocage circulaire si deux étudiants lancent la routine simultanément avec des cours inversés.
• Le deuxième cours n'est pas verrouillé avant de tester s'il est plein, ce qui peut provoquer des conditions de course.

Code problématique :

void EchangeCours(Putilisateurs utilisateur, PCours cours1, cours2) {
    cours2->verrouille();
    if (cours2->estPlein == false) {
        cours2->inscrit(utilisateur);
        cours2->deverrouille();
        cours1->verrouille();
        cours1->desinscrit(utilisateur);
        cours1->deverrouille();
        cours2->deverrouille();
    }
    else {
        // ...
    }
}

Réponse : Cette implémentation est incorrecte et peut causer interblocage et incohérences dans l'inscription.

Solution 12

Implémentation d'une barrière de synchronisation avec sémaphores.

Classe Barrier_t :

class Barrier_t {
    int nbproc;
    int cp;
    semaphore mutex, sem_barriere;
public:
    Barrier_t(int);
    void Barrier();
};

Barrier_t::Barrier_t(int v) {
    nbproc = v;
    cp = 0;
    mutex = 1;
    sem_barriere = 0;
}

void Barrier_t::Barrier() {
    P(mutex);
    cp++;
    if (cp == nbproc) {
        for (int i = 0; i < cp - 1; i++)
            V(sem_barriere);
        cp = 0;
        V(mutex);
    } else {
        V(mutex);
        P(sem_barriere);
    }
}

Utilisation dans différents modules :

mBO() {
    while (1) {
        BO();
        E1.Barriere();
        E2.Barriere();
    }
}

mRC() {
    while (1) {
        RC();
        E1.Barriere();
        E2.Barriere();
    }
}

mAS() {
    while (1) {
        E1.Barriere();
        GP();
        E2.Barriere();
        AS();
        E3.Barriere();
        E4.Barriere();
    }
}

mEM() {
    while (1) {
        E3.Barriere();
        GP();
        E4.Barriere();
        EM();
    }
}

3. Risque de blocage mutuel :

Si deux processus A et B appellent les barrières dans un ordre différent (A : E1 puis E2, B : E2 puis E1), ils peuvent se bloquer mutuellement.

Réponse : La barrière est correcte mais il faut éviter les appels croisés dans des ordres différents pour prévenir les blocages.

Solution 13

Analyse d'un problème de synchronisation avec deux sémaphores mutex1 et mutex2 et trois processus.

1. Non, la solution proposée est incorrecte car un processus en dehors de sa section critique peut bloquer un autre processus :

Processus P1:
P(mutex1);
n = n - 1;
V(mutex1);
P(mutex2);
out = out + 1;
V(mutex2);

Si P1 a exécuté P(mutex1) mais est bloqué avant de libérer, il empêche P3 d'entrer en section critique.

2. Proposition d'une solution avec un vecteur T de booléens pour contrôler le calcul des lignes :

fonction CalculLignes() {
    pour i = 0 à n-1 pas 1 {
        P(mutex);
        si (T[i] == 0) {
            T[i] = 1;
            V(mutex);
            pour j = 1 à n pas 1 {
                pour k = 1 à n pas 1 {
                    R[i,j] += A[i,k] * B[k,j];
                }
            }
        } else {
            V(mutex);
        }
    }
}

Réponse : Cette solution protège l'accès au vecteur T avec un mutex binaire et évite les conflits sur le calcul des lignes.

Solution 14

Modèle des lecteurs et rédacteurs appliqué à des trains circulant sur une voie.

Sémaphores :

autorisation = 1; partagé par tous les trains.

mutex = 1; partagé par les trains allant dans le même sens (deux mutex distincts pour chaque sens).

Gestion des trains AversB :

P(mutex);
if (NbAB == 0) P(autorisation);
NbAB++;
V(mutex);

Sortie de la voie par B:
P(mutex);
if (NbAB == 1) V(autorisation);
NbAB--;
V(mutex);

Gestion des trains BversA est similaire avec un compteur NbBA.

Réponse : Cette solution permet d'assurer l'exclusion mutuelle sur la voie en fonction du sens de circulation, évitant les conflits.

Solution 15

Implémentation classique du producteur-consommateur avec un tampon partagé et sémaphores.

a) Un producteur et un consommateur partagent un tampon :

Semaphore Mutex = 1, Vide = Max, Plein = 0;
Message tampon[Max];
int ip = 0; // index producteur
int ic = 0; // index consommateur

Producteur(int i) {
    Message m;
    Répéter {
        m = creermessage();
        P(Vide);
        P(Mutex);
        tampon[ip] = m;
        ip++;
        V(Mutex);
        V(Plein);
    } tant que vrai;
}

Consommateur(int i) {
    Message m;
    Répéter {
        P(Plein);
        P(Mutex);
        m = tampon[ic];
        ic++;
        V(Mutex);
        V(Vide);
    } tant que vrai;
}

b) Extension à plusieurs tampons :

Sémaphores :

Mutex[n] = {1, 1, ..., 1}, Vide[n] = {Max, Max, ..., Max}, Plein[n] = {0, 0, ..., 0};

Chaque tampon est indépendant :

Message tampon[n][Max];

Producteur() {
    int ip = 0;
    Message m;
    Répéter {
        m = creermessage();
        pour i = 0 à n-1 pas 1 {
            P(Vide[i]);
            P(Mutex[i]);
            tampon[i][ip] = m;
            V(Mutex[i]);
        }
        ip++;
        pour i = 0 à n-1 pas 1 {
            V(Plein[i]);
        }
    } tant que vrai;
}

Consommateur(int i) {
    int ic = 0;
    Message m;
    Répéter {
        P(Plein[i]);
        P(Mutex[i]);
        m = tampon[i][ic];
        V(Mutex[i]);
        ic++;
        V(Vide[i]);
    } tant que vrai;
}

Réponse : Cette solution permet de gérer plusieurs tampons indépendants avec protection mutuelle et synchronisation par sémaphores.

Méthode

Ce type d'examen récompense la compréhension claire des mécanismes de synchronisation par sémaphores, la capacité à identifier les sections critiques, et à concevoir des solutions évitant interblocage et famine. Il est essentiel de :

• Respecter les conventions et notations données dans l'énoncé.
• Montrer clairement les étapes de raisonnement et la justification des choix.
• Utiliser correctement les opérations P (wait) et V (signal) sur les sémaphores.
• Analyser les risques d'interblocage, de famine, et proposer des solutions pour les éviter.
• Ne pas inventer d'informations absentes du document source.
• Présenter les algorithmes et codes avec précision et clarté.

Les erreurs fréquentes sanctionnées sont les oublis de protection des sections critiques, le non-respect de l'ordre des sémaphores, et les risques d'interblocage non traités.