Discussion :

[Giovanny Temgoua]

Bonjour!

Voilà, je suis entrain de lire le livre d'Andrew Tanenbaum (pour ceux qui connaissent) intitulé "Système d'exploitation" et il est question de trouver une solution au problème des boulangers posé de cette façon :

Dans une boulangerie, on a n boulangers. Les clients arrivent et doivent prendre un numéro. Un seul boulanger peut lire à un moment donné un numéro et servir le client correspondant; de même un client à la fois peut prendre un numéro. Le nombre de numéro est également limité et vaut N. On suppose qu'une fois le client appelé, l'action du boulanger se résume à la fonction ServirClient(). Ecrire en utilisant les sémaphores, des procédures pour les clients et des procédures pour les vendeurs

Dans le livre, pour ne pas être spécifique à un langage, on utilise les primitives Down et Up qui représentent les fonctions de manipulation des sémaphores (WaitForSingleObject et Release respectivement).

J'ai déjà cherché des algorithmes pour ce problème mais aucun ne me propose une solution vraiment efficace; de plus ce que j'ai écris ne semble pas marcher

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
Semaphore mu=1; //une ressource disponible. mutex pour rendre l'action atomique
Semaphore Vendeur=n; //on a n vendeurs
Semaphore Client=1; //un client à la fois.
NombreNumero = 0; //nombre de numero déjà pris par les clients
 
void Client()
{
 while(1)
 {
  down(client);
  down(mutex); //pour s'assurer qu'un seul client pourra exécuter cette action
    PrendreNumero(); //action de prendre un numéro
    NombreNumero--; //le nombre de numéro dispo diminue
    si(NombreNumero==0) Up(Vendeur); //le nombre de numéro dispo vaut 0 donc on a tout pris alors on demande à un vendeur de lire
  up(mutex);
 }
}
 
void Vendeur
{
 while(1)
 {
  down(Vendeur);
  down(mutex); // j'utilise le même mutex pour être sûr qu'on ne pourra pas lire un numero pendant qu'un client en prend. 
    LireNumero(); //le vendeur lit un numero
    NombreNumero++;
    si(NombreNumero==N) //le nombre de numéro dispo = nombre de numéro total
        Up(Client); //on "reveille" le client
  up(mutex);
 }
}

Une boucle infinie parce qu'on suppose qu'on travaille à plein temps (personne ne dort ici )

Voilà, j'espère que vous pouvez un peu m'éclairer sur ce problème (des liens vers des cours, n'importe quoi).

Merci.

[Trap D]

Salut
+ "algorithme du boulanger"

[Giovanny Temgoua]

Salut
+ "algorithme du boulanger"

Google te fournit 6 réponses!
Solution 1 : Pas terrible (déjà vu!
Solution 3 : RAS

Pas le temps d’en parler…

Solution 5 pas d'exemple!
Solution 2 et 6 pareil alors

J'ai déjà cherché des algorithmes pour ce problème mais aucun ne me propose une solution vraiment efficace;

[Trap D]

Excuses moi d'insister mais "baker's algorithm" donne 229 réponses !
là il y a l'implémentation en C++; maintenant, je ne m'y connais pas assez pour dire si elle est efficace.

[Giovanny Temgoua]

Excuses moi d'insister mais "baker's algorithm" donne 229 réponses !

Tu fais bien d'insister parce que je ne connaissais pas que cet algorithme s'appelait comme cela

Merci

Sinon avec l'aide de bulbo (Merci au passage), j'ai réussit à avoir ceci :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
semaphore NbrNumero = N; //nombre de numéro
Semaphore mutex_boulanger = 1; //mutex sur les boulangers
Semaphore mutex_Client = 1; //mutex sur les clients
 
void Client()
{
 while(1)
 {
  Down(mutex_Client)
  Down(NbrNumero)
  PrendreNumero()
  Up(mutex_Client)
 } 
}
 
void Boulanger()
{
 while(1)
 {
  Down(mutex_Boulanger)
  ServirClient()
  Up(NbrNumero)
  Up(mutex_Boulanger)
 }
}

que j'ai ensuite modifié comme ceci :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
 
Semaphore Mutex_Client = 0;
Semaphore Mutex_Vendeur = 0;
Semaphore Mutex = 1;
 
void Vendeur()
{
 while(1)
{
   down(Mutex_Client);
   down(Mutex);
   AppelerNumero();
   Up(Mutex_Vendeur);
   Up(Mutex);
   Servir();
}
}
 
void Client()
{
 while(1)
 {
    down(Mutex);
    PrendreNumero();
    Up(Client);
    Up(Mutex);
    Down(Mutex_Vendeur);
 }
}

Je vais tester et voir si tout cà marche correctement

[gangsoleil]

A priori, ce code semble correcte (pas d'inter blocage)

[Giovanny Temgoua]

A priori, ce code semble correcte (pas d'inter blocage)

Merci d'avoir vérifié

J'ai vérifié également et il n'y a pas d'inter-blocage