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

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).

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);
}

Hey, j'avoue ne rien comprendre via un graph, je me ferais un plaisir de t'aider mais je veux bien que tu mettes l'algo (ou code) en spoiler

Yop Ricocotam, c'est fait, merci !

Je ne vais pas mentir, je ne comprends rien

Du coup je me demandais s'il était possible d'expliquer les grandes lignes de l'algo, ses objectifs⁽¹⁾ 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 ?

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 ?

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.

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

Heum mais ma question au début c'était quand même de comprendre cet algorithme x) Enfin de toute façon j'ai réussi mais merci^^

bonjour à tous; est qu’il y a qlq 1 parmi vous qui sais l’implémentation des sémaphores en langage C en utilisant shared memory (mémoire partagée)? i,e par la fonctin shmget(), shmat() et tous

svp de partager la solution merci à vous.