M4104C – Exercice1 / La piscine

Dans cet exercice nous allons vous demander de modéliser le fonctionnement d’une piscine. Les clients de la piscine sont des threads, nous vous demandons donc d’écrire le code de ces threads correspondant au comportement décrit dans la suite de l’énoncé.

Un baigneur doit :

  • Arriver à la piscine ;
  • Prendre un panier ;
  • Trouver cabine et entrer dedans afin de se déshabiller ;
  • Libérer la cabine ;
  • Aller nager
  • Prendre une cabine et s’habiller ;
  • Rendre son panier ;
  • Quitter la piscine ;

Ressources critiques : certaines phases de ces activités mettent en jeu des ressources critiques, pour lesquelles les threads rentrent en compétitions :

  • la piscine dispose d’un certain nombre NbPaniers de paniers dans lesquels les baigneurs laissent leurs habits pendant le temps de la baignade ;
  • chaque baigneur se déshabille et se rhabille dans une cabine individuelle. La piscine dispose d’un nombre NbCabines de cabines.

Les phases de déshabillage et de rhabillage ne peuvent commencer que si certaines conditions sont réalisées :

  • chaque baigneur doit disposer d’un panier et d’une cabine pour commencer à se déshabiller ;
  • chaque baigneur ne doit disposer que d’une cabine pour commencer à se rhabiller.

Ces deux conditions sont donc éventuellement bloquantes.

Les fins des phases de déshabillage et de rhabillage ne sont pas bloquantes mais correspondent à la libération de ressources critiques :

  • chaque baigneur rend sa cabine quand il a fini de se déshabiller ;
  • chaque baigneur rend sa cabine et son panier quand il a fini de se rhabiller.

Le code du baigneur peut être le suivant :

//arrivée
sleep (XXX) ;
// déshabillage
DebutDeshabiller();
sleep(XXX);
FinDeshabiller();
//baignade
sleep (XXX) ;
// rhabillage
DebutRhabiller() ;
sleep(XXX) ;
FinRhabiller() ;
//départ
sleep (XXX) ;

Ecrire le corps des fonctions : DebutDeshabiller (), FinDeshabiller (), DebutRhabiller () et FinRhabiller () selon les spécifications précédentes.

M4104C – EXERCICE2 / Lecteur / rédacteur

A. Utilisation d’un unique sémaphore en exclusion mutuelle (Mut)

Coté lecteur :

T Lire ()
    Mut.P();
        T info = RetirerInfo ();
    Mut.V ();
    return info;

Coté rédacteur :

void Ecrire (const T & info)
    Mut.P();
        PoserInfo (info);
    Mut.V();

Montrer que l’on peut obtenir un interblocage de processus.

B. Utilisation de plusieurs sémaphores

La solution ci-dessous est inspirée de celle vue en cours, malheureusement elle n’est pas fonctionnelle. Dites pourquoi et corrigez la.

Indication : on donnera toujours priorité aux lecteurs par rapport aux rédacteurs.

Init : MutRedPresent = 0 ;  MutRedEcr = 0 ; MutLect = 0; 

Coté lecteur :

MutRedPresent.P ();
MutLect.P();
    T info = RetirerInfo ();
MutLect.V ();
return info ;

Coté rédacteur :

MutRedEcr.P();
    PoserInfo (info) ;
MutRedEcr.V();
MutRedPresent.V ();

M4104C – EXERCICE3 / Le diner des philosophes

Problème :

La situation est la suivante :

  • cinq philosophes (initialement mais il peut y en avoir beaucoup plus) se trouvent autour d’une table ;
  • chacun des philosophes a devant lui un plat de spaghetti ;
  • à gauche de chaque plat de spaghetti se trouve une fourchette.

Un philosophe n’a que trois états possibles :

  • penser pendant un temps indéterminé ;
  • être affamé (pendant un temps déterminé et fini sinon il y a famine) ;
  • manger pendant un temps déterminé et fini.

Des contraintes extérieures s’imposent à cette situation :

  • quand un philosophe a faim, il va se mettre dans l’état « affamé » et attendre que les fourchettes soient libres ;
  • pour manger, un philosophe a besoin de deux fourchettes : celle qui se trouve à gauche de sa propre assiette, et celle qui se trouve à droite (c’est-à-dire les deux fourchettes qui entourent sa propre assiette) ;
  • si un philosophe n’arrive pas à s’emparer d’une fourchette, il reste affamé pendant un temps déterminé, en attendant de renouveler sa tentative.

Le problème consiste à trouver un ordonnancement des philosophes tel qu’ils puissent tous manger, chacun à leur tour. Cet ordre est imposé par la solution que l’on considère comme celle de Dijkstra avec sémaphores ou Courtois avec des compteurs.

Le corps du processus philosophe peut être le suivant :

Philo(i)
{
    while(true)
    {
        pense( );
        prendre_fourchette( i );
        manger ( );
        poser_fourchette( i );
    }
}

Conséquence, il faut écrire les fonctions prendre_fouchette () et poser_fourchette ().

A. Première solution

On prend un sémaphore par fourchette (un mutex fait aussi l’affaire), chaque sémaphore est initialisé à 1.

sem fourch[ N ] = {1,........1}
prendre_fourchette (int i)
{
    fourch[i].P() ;
    fourch[(i+1)% N].P() ;
}

poser_fourchette (int i)
{
    fourch[i].V() ;
    fourch[(i+1)% N].V() ;
}

Monter que cette solution peut provoquer un interblocage de processus.

B. Deuxième solution

On modifie la solution 1 de sorte que les philosophes ne puissent pas prendre tous en même temps la fourchette de droite.

On introduit pour cela un sémaphore dont le compteur est égal à N-1

Implémenter cette solution.

C. Troisième solution

C’est la même chose que la première solution sauf qu’un philosophe est gaucher et ceci afin d’éviter l’interblocage.

Implémenter cette solution.

D. Quatrième solution 

On se centre ici sur les philosophes. Un sémaphore est attribué à chaque philosophe.

Etat = { PENSE , MANGE , A_FAIM}

Un philosophe qui veut prendre les fourchettes (donc manger) déclare qu’il a faim. Si l’un de ses deux voisins est en train de manger, il ne peut donc pas prendre les deux fourchettes pour l’instant et donc se met en attente. Si les deux philosophes à coté ne mangent pas alors il peut prendre les deux fourchettes et déclarer qu’il mange. Quand le philosophe a fini de manger, il déclare donc qu’il pense et regarde si ses deux voisins qui forcément ne pouvaient pas manger, en ont dès lors l’opportunité. Si c’est le cas il les réveille.

Implémenter cette solution.

M1103 TP6 (ULAM) – Exercice 1

Ecrire les fonctions ci-dessous :

bool estPremier (const unsigned & i);
vector <unsigned> nbPremiersAvantN (const unsigned & N);

La fonction estPremier () teste si l’entier passé en paramètre est un premier.

La fonction nbPremiersAvantN () renvoie dans un tableau, tous les nombres premiers plus petit que le paramètre.

M1103 TP6 (ULAM) – Exercice 2

Ecrire la fonction ci-dessous :

vector <unsigned> nbPremiersAvantN (const unsigned & N, vector<unsigned> & vLesPremiers, const unsigned & M);

Cette fonction ajoute au vecteur vLesPremiers tous les nombres premiers compris entre [N,M[.

M1103 TP6 (ULAM) – Exercice 3

Ecrire les fonctions ci-dessous :

void stockerVectPremiersDansFichier (const vector <unsigned> & vect, const unsigned & N, const string & nomFichier);

void lireVectPremiersDepuisFichier (vector <unsigned> & vect,unsigned & N, const string & nomFichier);

L’objectif est de lire / d’écrire dans un fichier texte le vecteur contenant tous les premiers plus petit que N.
Sur la première ligne, on trouve N, puis tous les autres premiers à raison d’un élément par ligne.

En conséquence le fichier (pour N fixé à 10) sera le suivant :

10
2
3
5
7

M1103 TP6 (ULAM) – Exercice 4

On définit le type CMatrice comme suit :

typedef vector <vector< unsigned>> CMatrice;

Ecrire les fonctions ci-dessous :

void afficherMatrice (const CMatrice & Mat);
void construireMatriceAleatoire (CMatrice & Mat, const unsigned & N);

Dans cette deuxième fonction, N est la taille de la matrice (carrée) et tous les nombres sont générés aléatoirement dans l'intervalle [2, N2+1[.

Ecrire la fonction :

void afficherMatriceUlam (const CMatrice & Mat, const vector <unsigned> & vLesPremiers);

Cette fonction est une modification de la fonction afficherMatrice (). Vous devez afficher le caractère 'X' si le nombre courant est un premier, sinon vous affichez la caractère ' '.

Ecrire la fonction :

void construireMatriceEscargot (CMatrice & Mat, const unsigned & N);

Cette fonction construit la matrice sous-jacente à la spirale d’ULAM.

M1103 TP6 (ULAM) – Corrigé Exo1 -> 4

#include <iostream>
#include <vector>
#include <fstream>
#include <iomanip>
using namespace std;

bool estPremier (const unsigned & i){
    for (unsigned j (2) ; j < i; ++j)
        if (i %j ==0) return false;
    return true;
} 

vector <unsigned> nbPremiersAvantN (const unsigned & N) {
    vector<unsigned> vLesPremiers;
    //vérifier si tous tous les nombres de 1 à N sont premiers
    for (unsigned i (2); i < N ; ++i){
        if (estPremier (i)){
            vLesPremiers.push_back(i);
        }
    }
    return vLesPremiers;
}

bool estPremier (const unsigned & i, const vector<unsigned> & vect){
    for (const auto & val : vect)
        if (i % val == 0) return false;
    return true;
    //    for (unsigned j (2) ; j < i; ++j)
    //        if (i %j ==0) return false;
    //    return true;
} 
/**
 * @brief ajoute au vecteur vLesPremiers tous les nombres premiers compris entre [N,M[
 * @param N
 * @param vLesPremiers
 * @param M
 * @return
 */
vector <unsigned> nbPremiersAvantN (const unsigned & N, vector<unsigned> & vLesPremiers, 
                                    const unsigned & M) {
    //vérifier si tous tous les nombres de 1 à N sont premiers
    for (unsigned i (M); i < N ; ++i){
        if (estPremier (i, vLesPremiers)){
            vLesPremiers.push_back(i);
        }
    }
    return vLesPremiers;
}

template <typename T>
void affchichVect(const vector<T> & vect){
    for (const auto & val : vect)
        cout << val << ';';
    cout << endl;
}
/**
 * @brief lire un vecteur d'entiers depuis un fichier.
1ere ligne : nombre max du premier
autre ligne : tous les entiers du vecteur
 * @param[in out] vect
 * @param[in out] N
 * @param [in] nomFichier
 */
void lireVectPremiersDepuisFichier (vector <unsigned> & vect,
                                    unsigned & N, const string & nomFichier){
    vect.resize(0);
    N = 0;
    //1 ouvrir un flux vers nomFichier
    ifstream ifs (nomFichier);
    //2 s'assurrer que le flux existe et est valide
    if (!ifs.is_open())
    {
        cout <<"il y a eu un soucis";
        return;
    }

    //3 lecture du nombre max
    unsigned Entier;
    vect.push_back(N);

    //4 lire les elements du vecteur à raison de 1 par ligne
    while (ifs >> Entier)
        vect.push_back(Entier);

}
/**
 * @brief stocker un vecteur d'entiers dans un fichier.
1ere ligne : nombre max du premier
autre lignes : tous les premiers plus petit (strict que max)
 * @param[in] vect
 * @param[in] N
 * @param[in] nomFichier
 */
void stockerVectPremiersDansFichier (const vector <unsigned> & vect,
                                     const unsigned & N, const string & nomFichier){
    //1 ouvrir un flux vers nomFichier
    ofstream ofs (nomFichier);
    //2 s'assurrer que le flux existe et est valide
    //    if (ofs.is_open() == true)
    //    {
    //     // faire action //3 & 4
    //    }
    //    else
    //    {
    //    cout << "Erreur" << endl;
    //    }
    if (! ofs.is_open()){
        cout << "Erreur" << endl;
        return;
    }

    //3 ecrire N
    ofs << N << endl;
    //4 ecrire les elements du vecteur à raison de 1 par ligne
    //    for (const auto & val : vect)
    //        cout << val << endl;
    for (unsigned i = 0; i < vect.size() ; ++i)
        ofs << vect[i] << endl;
}

typedef vector <vector< unsigned>> CMatrice;

void afficherMatrice (const CMatrice & Mat){
    for (unsigned i = 0; i < Mat.size(); ++i)
    {
        for (unsigned j = 0; j < Mat[i].size(); ++j)
        {
            cout << setw (3) << Mat[i][j];
        }
        cout << endl;
    }
}

void construireMatriceAleatoire (CMatrice & Mat, const unsigned & N){
    //dimensionner la matrice à la taille NxN
    Mat.resize(N);

    for (unsigned i = 0; i<Mat.size() ; ++i)
    {
        Mat[i].resize(N);
    }

    //remplir la matrice avec des éléments aléatoires entre 2 et NxN
    for (unsigned i = 0; i<Mat.size() ; ++i)
    {
        for (unsigned j = 0; j<Mat[i].size() ; ++j)
        {
            Mat[i][j] = rand () % (N*N) + 1;
        }
    }

}

void afficherMatriceUlam (const CMatrice & Mat, const vector <unsigned> & vLesPremiers)
{
    for (unsigned i = 0; i<Mat.size() ; ++i)
    {
        for (unsigned j = 0; j<Mat[i].size(); ++j)
        {
            if (estPremier(Mat[i][j]))
                cout <<setw (3) <<  'X' ;
            else
                cout << setw (3) << ' ';
        }
        cout << endl;
    }
}

//void afficherMatriceUlam (const cMatrice & Mat, const vector <unsigned> & vLesPremiers){
//    //on a afficher 'X' si mat[i][j] est premier sinon afficher ' '
//    for (unsigned i = 0; i<Mat.size() ; ++i)
//     {
//         for (unsigned j = 0; j<Mat[i].size() ; ++j)
//         {
//             if (estPremier(Mat[i][j], vLesPremiers)){
//                 cout << 'X';}
//             else{
//                 cout << ' ';
//             }
//         }
//         cout << endl;
//     }
//}

void construireMatriceEscargot (CMatrice & Mat, const unsigned & N){
    if (N % 2 == 0) {
        cout << "pas possible c'est pair" << endl;
        return;
    }

    //dimensionner la matrice à la taille NxN
    Mat.resize(N);

    for (unsigned i = 0; i<Mat.size() ; ++i)
    {
        Mat[i].resize(N);
    }
    //construction de la matrice
    unsigned posX (N/2), posY(N/2), val (1);
    Mat [posX][posY] = val++;
    for (unsigned nbMouvement (2); val <= N * N; nbMouvement += 2){
        //deplacement bas droite
        ++posX; ++posY;
        //deplacement haut
        for (unsigned i (0); i < nbMouvement; ++i)
            Mat[--posX][posY] = val++;
        //deplacement gauche
        for (unsigned i (0); i < nbMouvement; ++i)
            Mat[posX][--posY] = val++;
        //deplacement bas
        for (unsigned i (0); i < nbMouvement; ++i)
            Mat[++posX][posY] = val++;
        //deplacement droite
        for (unsigned i (0); i < nbMouvement; ++i)
            Mat[posX][++posY] = val++;
    }
}


int main() {
    ////    srand(time(NULL));
    //    unsigned N = 5;
    //    vector <unsigned> vUlam = nbPremiersAvantN(N*N+1);
    ////    vUlam = nbPremiersAvantN (N*N+1, vUlam, 2);
    //    affchichVect (vUlam);
    ////    stockerVectPremiersDansFichier(vUlam, N, "tmp.txt");
    ////    lireVectPremiersDepuisFichier(vUlam, N, "tmp.txt");
    // //   affchichVect (vUlam);
    //    cMatrice uneMatrice;
    //    construireMatriceAleatoire (uneMatrice, N);
    //    afficherMatrice (uneMatrice);
    //    afficherMatriceUlam (uneMatrice, vUlam);
    //    return 0;
    srand(time(NULL));

    unsigned N = 5;
    unsigned M = 0;
    vector <unsigned> vUlam = nbPremiersAvantN(N*N+1);
    vector <unsigned> vBis;


    //nbPremiersAvantN(1001, vUlam, N);
    affchichVect (vUlam);

    //stockerVecteurPremiersDansFichier(vUlam, N, "Test.txt");

    //lireVectPremiersDepuisFichier("Test.txt", M, vBis);
    //afficheVect(vBis);

    CMatrice Mat;
    //construireMatriceAleatoire(Mat, N);
    construireMatriceEscargot(Mat,N);
    afficherMatrice(Mat);
    afficherMatriceUlam(Mat, vUlam);


    return 0;
}