En image : l'algorithme du lecteur-rédacteur, priorité du rédact

L'auteur de ce sujet a trouvé une solution à son problème.
Auteur du sujet

Salut à tous,

J'essaie de prendre de l'avance sur l'année qui vient, notamment en Java et plus précisément sur les threads ; j'ai déjà sollicité plusieurs fois votre aide pour corriger ou valider des sources que j'ai écrites dans le cadre d'un TP, cette fois-ci (et ce sera mon dernier topic au sujet des threads d'ailleurs) je souhaiterais vous demander de l'aide pour comprendre un algorithme.

Il s'agit de l'algorithme du système lecteurs-rédacteurs, avec priorité des rédacteurs sur les lecteurs.

Le prof a écrit cet algorithme, mais sans donner d'explication ; aussi je le trouve long et plutôt "mystérieux". J'ai mis sous forme graphique cet algorithme (je trouve que c'est bien plus clair, et je procède ainsi systématiquement depuis quelques jours, dès que je me trouve face à des threads).

Algo LR avec priorité des R sur les L

Dans le TP, je n'ai qu'un seul rédacteur et un seul lecteur qui travaillent sur une même donnée, et qui peuvent s'exécuter en même temps. Cependant je pense que l'algo que je viens de vous fournir marche avec plusieurs Rédacteurs et plusieurs Lecteurs, donc il est généralisant.

Voilà, autant j'ai bien compris le fonctionnement des algos "producteur-consommateur" et même "lecteur-rédacteur avec priorité du lecteur", autant celui-ci me paraît beaucoup plus long et complexe… Je suis perdu entre tous ces "DL, DR", ces conditions, tout ça…

Si quelqu'un est dispo pour m'aider, ce serait sympa !

Merci et bonne journée !

EDIT : Algorithme version rédigée.

 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
64
65
66
67
68
69
70
71
72
73
static int lecteur,demandeLecteur; // nombre de lecteurs
static int redacteur,demandeRedacteur;

semaphore mutex; // protection des variables
semaphore semLec;
semaphore semRed;

void initialisation() {
   Init(& mutex,1);
   Init(& semLec,0);
   Init(& semRed,0);
   lecteur=0;
   demandeLecteur=0;
   redacteur=0;
   demandeRedacteur =0;
}

void lecteur(void) {
   P(&mutex); // accès aux variables protégées

   if (redacteur || demandeRedacteur)
   // teste s'il y a un rédacteur ou
   // une demande d'un rédacteur
      demandeLecteur++;
      V(&mutex)
      P(&semLec);
      P(&mutex)
      demandeLecteur--;
   lecteur++;
   V(&mutex);

   ACCES A L'INFORMATION

   P(&mutex);
   lecteur--;

   if (lecteur == 0 && demandeRedacteur)
   // seul lecteur
      V(&semRed);// libère le rédacteur
   V(&mutex);
}

void redacteur(void) {
   P(&mutex); // demande aux variables

   if (lecteur||redacteur || demandeRedacteur){
      demandeRedacteur++
      V(&mutex)
      P(&semRed);
      P(&mutex)
      DemandeRedacteur --;
   }

   redacteur ++;
   V(&mutex)

   PRODUIRE L'INFO

   P(&mutex)
   redacteur --;

   if (demandeRedacteur)
      V(&semRed)
   else {
      if (demandeLecteur) {
         int nb;
         for (nb=0;nb < demandeLecteur, nb++)
            V(&semLec);
      }
   }

   V(&mutex);
}

Édité par The-Aloha-Protocol

Université de Bretagne-Sud <3

+0 -0
Auteur du sujet

Je ne vais pas mentir, je ne comprends rien :euh:

Du coup je me demandais s'il était possible d'expliquer les grandes lignes de l'algo, ses objectifs(1) et puis d'aller plus loin en précision (expliquer en détails l'algo) ?

^1 : normalement il y a 2 objectifs. Le premier est d'empêcher les lecteurs et les rédacteurs d'accéder en même temps à la ressource. Le second, de permettre aux rédacteurs d'écrire dès qu'ils le peuvent et donc de faire patienter tous les lecteurs, même s'il ya déjà un lecteur en train de lire. Non ?

Université de Bretagne-Sud <3

+0 -0

Cette réponse a aidé l'auteur du sujet

Je ne t'expliquerais pas exactement ce que ça fait parce que c'est toi l'étudiant :p

Mais je peux quand même te guider et valider/invalider tes "réponses" ou éclairer quelques points

Je pense que tu l'as fait mais je te le dis quand même, prend toi plusieurs exemples et déroule ton algorithme en maintenant à jour tes sémaphores et tes autres variables (souvent un tableau est pas mal). Ca te permettra de mieux saisir comment ça fonctionne. Une fois que tu as compris, essaie de reproduire le code à partir de tes dessins (ceux que tu as fais pour comprendre, pas ta transcription de l'algorithme). Je pense que si tu arrives à faire ça tu seras au point.

Le code tel que tu l'as donné ne permet pas de faire tourner en boucle donc en vrai il ne fait pas du tout ce que tu racontes. Imaginons que ça tourne en boucle, je te laisse faire ce que j'ai dit avant pour essayer de vraiment bien comprendre.

Je te déconseille de lire la suite si tu n'as pas essayé, ça te gâcherait ton apprentissage.

Sûr hein ?

De ce que je vois en lisant le code, le rédacteur ne peut accéder à la ressource que quand il n'y a plus de lecteur, et les lecteurs ne peuvent accéder à la ressource que s'il n'y a aucun rédacteur en attente.

+1 -0
Auteur du sujet

Coucou ! Excuse-moi du retard et merci de ta réponse !

Alors, dis-moi si je me trompe :

Concernant les threads-rédacteurs (TR) :

semRed permet de mettre les TR en attente d'un release effectué par le seul et unique thread qui n'est pas en attente. A un instant t, il n'y a en effet qu'un seul TR qui puisse mettre à jour la donnée partagée, puis effectuer ce release.

Le dernier TR à s'exécuter (donc DR ne sera plus supérieure à 0 puisqu'aucun nouveau TR n'est créé) autorisera tous les threads-lecteurs à s'exécuter avec un release sur semLec. Seul ce "dernier TR" peut le faire, aucun autre.

Prenons un exemple.

On admet qu'aucun TL n'ait été créé (pour simplifier l'exemple), et qu'on va créer 3 TR.

T0 verrouille m. Aucun TR en attente, on passe donc directement à R++ et on déverrouille m puis fait sa màj de valeur.

Admettons que T1 se lance : il verrouille m, DR++, déverrouille m et va se mettre en attente sur semRed (car ce dernier est init à 0).

Admettons que T0 reprenne la main (T2 pourrait aussi se lancer, et ferait pareil que T1 bref).

T0 s'étant réveillé, il verrouille m, fait R-- et comme il constate qu'il y a un TR en attente (DR = 1), il le réveille puis va mourir (déverrouille m et meurt).

T1 reprend : il verrouille m, fait DR-- (qui vaut maintenant 0), R++, déverrouille m. Il màj.

Là T2 se lance : il verrouille m et T1 est donc mis en attente. Comme R = 1, T2 est mis en attente sur semRed et DR = 1 (et il a déverrouillé m).

Alors T1 reprend, fait R-- et réveille T2. Pis va déverrouiller m et mourir.

T2 reprend, constate que DR = 0 et va donc dans le SINON. S'il y avait un ou des TL, ces derniers seraient réveillés.

Donc les TL doivent attendre que le dernier TR ait fini son travail.

Un cas me chiffonne par contre : imaginons que T0 et T1 se soient exécutés, mais que T2, pour une raison quelconque, n'ait pas réussi à se lancer durant T0 ou durant T1 (dès qu'un m est déverrouillé). Ainsi le dernier thread est T1 et non T2. Du coup : soit T2 prend enfin la main, soit c'est un TL qui prend la main !

C'est pas grave ça ?

Édité par The-Aloha-Protocol

Université de Bretagne-Sud <3

+0 -0

Cette réponse a aidé l'auteur du sujet

J'avoue m'être un peu perdu dans tes explications ^^

Je vais te donner un exemple complet (enfin je crois) et tu vas le dérouler, ce sera probablement plus simple :)

Il y a 2 demandes de redactions et 1 demande de lecture à l'initialisation. Ce n'est pas dans le programme mais on considère que la rédaction passe en premier au début. Chaque rédaction met 10ms et toute les 15ms un nouveau rédacteur arrive. La lecture met 5ms et un lecteur arrive toute les 10ms (tu peux t'arrêter au bout de 5/6 lecteurs-redacteurs)

+1 -0
Auteur du sujet

Je ne comprends pas :

Il y a 2 demandes de redactions et 1 demande de lecture à l'initialisation.

Ce n'est pas au dév de choisir arbitrairement ces valeurs, ça j'en suis bien sûr ?

Mais de toute façon ce que j'ai dit en "citation", dans mon précédent message, est un exemple tout ce qu'il y a de plus concret ^^ J'ai juste tout bien détaillé (à part sur la fin où je me suis permis de ne pas tout raconter). Et sinon ce que j'ai écrit juste avant le bloc de citation, c'est ce que j'ai compris globalement.

Donc dans un premier temps j'avais expliqué comment l'algo fonctionne, et dans un deuxième temps, j'ai donné un exemple concret.

Édité par The-Aloha-Protocol

Université de Bretagne-Sud <3

+0 -0

Cette réponse a aidé l'auteur du sujet

Je ne comprends pas :

Il y a 2 demandes de redactions et 1 demande de lecture à l'initialisation.

Tes variables DR et DL peuvent être initialisées en avance (imagine l'ouverture d'une librairie où deux rédacteurs et un lecteur sont présents avant l'ouverture)

Le problème dans ton exemple c'est que c'est un exemple dépendant du code que je ne connais pas bien donc pour le comprendre je suis obligé de faire des allers-retours.

L'avantage d'écrire les exemples comme le mien c'est que tu peux comprendre indépendamment de l'implémentation :).

+1 -0
Auteur du sujet

Tes variables DR et DL peuvent être initialisées en avance (imagine l'ouverture d'une librairie où deux rédacteurs et un lecteur sont présents avant l'ouverture)

Franchement je ne pense pas que ce soit "permis" dans cet algorithme, ces variables doivent être initialisées à 0 au début, et s'incrémentent petit à petit puis se décrémentent lors de l'exécution.

Le problème dans ton exemple c'est que c'est un exemple dépendant du code que je ne connais pas bien donc pour le comprendre je suis obligé de faire des allers-retours.

Je ne comprends pas vraiment, ton exemple est également dépendant du code… Enfin de toute façon il faut bien réfléchir sur le code, pas en l'air ?

M'enfin honnêtement je pense avoir compris :)

Université de Bretagne-Sud <3

+0 -0

Cette réponse a aidé l'auteur du sujet

Je ne comprends pas vraiment, ton exemple est également dépendant du code… Enfin de toute façon il faut bien réfléchir sur le code, pas en l'air ?

Alors là c'est une grosse erreur à ne pas faire. Si quand tu as un sujet à traiter et que tu veux le comprendre pleinement et identifier les problèmes potentiels, tu le fais en réfléchissant grâce au code, tu auras toujours des problèmes de plus grandes ampleurs. Quand tu abordes un problème tu dois d'abord essayer de comprendre ce qu'il fait en français et avec des schémas qui n'ont rien à voir avec une implémentation ou un algorithme et ensuite traduire tes réflexions en code, sinon tu vas te retrouver avec des bugs de mauvais enchaînement, ou alors tu vas avoir des données modifiées sans comprendre pourquoi etc

+1 -0
Vous devez être connecté pour pouvoir poster un message.
Connexion

Pas encore inscrit ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte