Discussion :

[souviron34]

ben si t'exposais un peu plus clairement ton problème, on pourrait comprendre...

Avec ton dernier message on commence à entrevoir le problème.. Et il ne correspond pas vraiment à ton exposé du premier et 2ième post

Mais tu ne nous l'a pas encore explicité sous forme algo ..

Raisonne en termes algos et non implémentation (pas de mutex ou autres), du texte clair...

A partir de là, une éventuelle solution sera beaucoup plus claire...

[pseudocode]

Quand une ressource va se libérer le processus arrivé il y a 3 heures ne sera pas sûr de pouvoir prendre celle-là.

Si, car lorsque le processus entre dans le spin-lock, il s'enregistre a la fin de la queue d'attente du semaphore.

Lorsque la procedure V() est appelée, seul le "premier" processus de la queue est reveillé. Donc le plus "ancien".

mais bon, le spinlock ça reste de l'attente active même si on met un micro-sommeil au millieu, donc une méthode "pas géniale" à mon sens qui relève un peu du bricolage.

Je ferai suivre cette reflexion aux developpeurs du kernel linux, ca leur fera plaisir...

[Celelibi]

souviron34, en texte claire c'est : sémaphore avec attente passive. Comment qu'on fait ?
Et ce bien entendu totalement en userland et indépendamment de tout langage, système et matériel.
Et si possible sans "tricher".

pseudocode, je ne vois pas comment introduire une gestion de file avec du spinlock. (Du moins pas avec la manière dont je l'ai exprimé.)


Et puis hein, moi je suis dans une optique totalement userland, quand on code un OS (en particulier le noyau) on peut se permettre certaines choses.

[souviron34]

souviron34, en texte claire c'est : sémaphore avec attente passive. Comment qu'on fait ?

Désolé pas plus clair....

Quel est le problème initial ? là tu donnes une solution (ésotérique) à un problème non défini.

Est-ce que tu veux avoir une série de processus qui attendent un feu vert donné par quelqu'un d'autre ? est-ce que tu veux faire un scheduler ? est-ce que la série de processus est liée dans le temps ? est-ce que chacun connait l'autre ? est-ce une série de processus indépendants ?

Bref, expose clairement ton problème, pas ta solution...

[Celelibi]

1) Le problème de la programmation concurrente
Plusieurs processus s'exécutent "en même temps", il est possible que plusieurs processus aient envie de travailler avec une même ressource. Ça peut être un segment de mémoire partagée par exemple ou un périphérique quelconque ou n'importe quoi dont l'accès ne peut se faire que par un nombre limité de processus à la fois.
Pour mettre un peu d'ordre dans tout ça, on a découpé les processus en sections (purement virtuelle, ce n'est qu'une vue de l'esprit).
La section critique c'est la section de code qui manipule la ressource en question.
Le bout de code avant la section critique chargé de garantir qu'il n'y aurai jamais trop de processus en même temps en section critique c' est la section d'entrée.
Et le bout de code juste après c'est la section de sortie.
Tout le reste du code c'est la section restante.
Un programme ressemble donc à :

Code :

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

1
2
3
4
5
<SR>
<SE>
<SC>
<SS>
<SR>

Le problème de la section critique consiste donc à trouver des bouts de code pour la SE et la SS
Les différentes solutions au problème de la section critique doivent respecter les règles suivantes :
- Ne pas dépasser le nombre maximal de processus concurrents en section critique
- Pas d'interblocage : il doit être strictement impossible que deux processus s'attendent mutuellement pour une durée infini. (Il ne s'agit pas d'éviter les mauvaises utilisation d'une bonne solution.)
- Pas de famine : chaque processus quand il arrive en section d'entrée doit être assuré de pouvoir entrer en section critique au bout d'un temps fini.

2) La solution des sémaphores
Edsger Dijkstra à été le premier à formaliser la notion de sémaphore. Il les a défini comme des objets possédant les trois opérations suivantes :
Init : Initialise un sémaphore à une certaine valeur
P : Teste si il reste une ressource disponible et dès que c'est possible en prend une.
V : Redonne la ressource précédemment prise avec une opération P.

Chacune de ces opérations ne doit pas pouvoir être interrompu (sauf l'opération P lorsqu'elle est en attente).

On a donc la section d'entrée qui se résume à P(sem) et la section de sortie à V(sem).

Tout ceci était sous-entendu quand je parlais des sémaphores de Dijkstra. Oui ça fait beaucoup de sous-entendus mais en même temps tout ceci est extrêmement lié, quand on connaît les sémaphores, on est censé connaître tout ça.


Et donc ma question c'est : algorithmiquement, comment "implémenter" ces trois opérations et en particulier l'opération P. Et ce, avec de l'attente passive. Étant donne que cela constitue l'étape inférieur dans les outils de synchronisation, on peut éventuellement considérer que l'on dispose d'un mutex.


Si c'est toujours pas clair, je vois pas ce que je peux faire.

[souviron34]

Sans avoir suivi de cours () c'est bien ce que j'avais compris...

Sauf que tu n'avais pas mentionné (ni même sous-entendu) le nombre maximal. Moi je pensais 1 (1 seul processus à la fois dans la section critique).

La solution donnée plus haut marche toujours :

Nmax+1 sémaphores + 1 entier

1 sem pour dire section bloquée/non bloquée
Nmax sem correspondants à chacun des processus
1 entier correspondant au nombre de processus

Chaque processus met son sem à 1 lorsqu'il veut accèder. Les numéros de sémaphores sont assignés en fonction du nombre déjà mis (d'où la file). Quand l'entier est à Nmax la section est bloquée. Chaque processus ayant fini met son sem à 0 et décrémente l'entier et débloque la section. Chaque nouveau processus incrémente l'entier et se voit assigner un sémaphore. Puis en fonction du nombre bloque ou pas la section..

Je ne vois pas en quoi tout ceci ne peut pas être fait en 100% logiciel...

[Celelibi]

Sauf que tu n'avais pas mentionné (ni même sous-entendu) le nombre maximal. Moi je pensais 1 (1 seul processus à la fois dans la section critique).

C'est justement sous-entendu quand on parle de sémaphores. Les sémaphores de Dijkstra permettent une initialisation à N (N pouvant être positif ou nul.) et comme c'est lui le premier à avoir formalisé les sémaphores, tous les sémaphores peuvent avoir une valeur initiale différente de 1.
Quand il est initialisé à 1 il se comporte comme un mutex, mais ça tu l'avais deviné.



Maintenant, voyons si j'ai compris la solution que tu propose :
Chaque processus a un bit dans le sémaphore qui lui est réservé et qui sert à indiquer si il veut entrer en section critique ou non.
Le compteur du sémaphore, toi tu veux l'initialiser à 0 et l'incrémenter quand un processus entre en section critique et le décrémenter quand il sort. (Généralement on fait le contraire, mais qu'importe.)

Note : qu'on s'entende bien sur le langage employé, un sémaphore est un "objet" (pas au sens POO hein ?) qui peut contenir tout plein de données, mais c'est pas grave puisqu'on est censé y accéder que par les trois opérations Init, P et V. Le sémaphore est censé être unique pour une certaine ressource. Donc je suppose que quand tu as dit "sémaphore" c'était parfois pour parler abusivement d'un bit dont la valeur est partagée entre tous les processus.

Et donc selon toi l'algo de l'opération P serait (on va passer en pseudo-code français tiens) :

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
procédure P (sémaphore : sem) est
début
    sem.veux[sem.liste_prcessus.taille] := 1;
    si (sem.bloqué) alors
        sem.liste_processus.ajouter(processus_actuel);
 
        // Pas sûr que ça soit ce à quoi tu penses
        tant que (sem.bloqué) boucler
            ne rien faire;
        fin tant que;
 
    fin si;
    sem.compteur := sem.compteur + 1;
 
    si (sem.compteur = sem.Nmax) alors
        sem.bloqué := 1;
    fin si;
fin P;

J'ai plusieurs questions à propos de cet algo (sûrement dû au fait que je t'ai mal compris) :
- Comment rendre l'exécution de la procédure P non interruptible par une opération P ou V ?
- est-ce que la boucle "tant que" qui attend que la section critique soit débloquée est ce à quoi tu pensais ? Parce que dans ce cas là je vois pas comment l'opération V va faire pour choisir le processus qui pourra entrer en section critique.
De plus cette méthode suppose d'avoir un bit pour chaque processus qui attend ce qui suppose soit de connaître le nombre maximal de processus concurrents, soit de faire de l'allocation dynamique de mémoire, soit de fixer une limite supérieur.

[pseudocode]

pseudocode, je ne vois pas comment introduire une gestion de file avec du spinlock. (Du moins pas avec la manière dont je l'ai exprimé.)

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
 
procedure P(sem) {
    entrée_mutex;
    sem.compteur := sem.compteur - 1;
    if (sem.compteur < 0) {
    	currentprocess.status := WAIT;
    	sem.waiters.add(currentprocess);
        sortie_mutex;
        while (currentprocess.status == WAIT) {
            yield();
        }
    } else {
    	sortie_mutex;
    }
}

Code :

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

1
2
3
4
5
6
7
8
9
10
 
procedure V(sem) {
    entrée_mutex;
    sem.compteur := sem.compteur + 1;
    if (sem.compteur <= 0) {
    	process := sem.waiters.getAndRemoveFirst();
    	process.status := RUN;
    }
    sortie_mutex;
}

[souviron34]

je ne sais pas ce qu'est un mutex ;-)

Bon, plus sérieusement, en gros c'est ça..

Pour moi un sémaphore est un sémaphore : un flag 1 ou 0. Si cela correspond à la libération de l'accès à une zone partagée, pas de problème. Mais un sémaphore, comme son nom l'indique, c'est de la SIGNALISATION.


Je crois qu'il y a encore un problème de compréhension. Tu parles de "section V qui choisirait un processus", mais c'est le contraire (sauf si tu fais un scheduler).

Chaque processus a sa section d'entrée et sa section de sortie (c'est le même code pour tous, mais chacun a le sien).

En gros, l'algo serait :

section d'entrée :

Code :

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

1
2
3
4
5
6
7
8
Si section bloquée
       attends (soit while, soit sleep)
Sinon
       Appelle la routine qui ajoute 1 au nombre de processus 
         (la routine qui ferait ça vérifie si on est au nombre max, 
          et si oui bloque la section, et de plus met le sémaphore à 1, 
          et renvoie le sémaphore)
Fin si

Si on est ici, c'est qu'on exécute la section critique.

Puis, pour la section de sortie :

Code :

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

1
2
3
Appelle la routine qui décrémente le nombre de processus
(la routine qui ferait ça vérifie si on était au nombre max, si oui 
débloque la section, et met le sémaphore à 0)

Note : et je rajouterais que tu te contredis, mais je pense que c'est à cause de l'imprécision entre le fait de savoir si tu fais un scheduler ou le mécanisme :

Chacune de ces opérations ne doit pas pouvoir être interrompu (sauf l'opération P lorsqu'elle est en attente).

- Comment rendre l'exécution de la procédure P non interruptible par une opération P ou V ?

[pseudocode]

Pour moi un sémaphore est un sémaphore : un flag 1 ou 0. Si cela correspond à la libération de l'accès à une zone partagée, pas de problème. Mais un sémaphore, comme son nom l'indique, c'est de la SIGNALISATION.

Ca c'est le semaphore au sens litteral, genre feu rouge. Celelibi parle du semaphore de Dijkstra.

Semaphore [Dijkstra - 1965]

D'un point de vue informatique, un sémaphore est un objet à valeur entière qui supporte deux opérations atomiques: P (wait) et V (signal)

L'opération P(...) décrémente la valeur du sémaphore et bloque le processus si la nouvelle valeur est strictement plus petite que 0

L'opération V(...) incrémente la valeur du sémaphore et, si la nouvelle valeur est plus petite ou égale à 0, réveille un processus dormant (s'il en existe au moins un)

[souviron34]

ok donc à ce compte-là c'est pour un scheduler...

Mais dans le principe, c'est la même chose vu de l'autre côté..

Donc , en appliquant le même principe, ça marche aussi (en fait c'est la bibliothèque des 2 routines entrèe et sortie), et non le programme appellant.

Mais le programme appelant a néanmoins besoin d'avoir une instruction équivalente, non ? (comme dans MMI).

[pseudocode]

ok donc à ce compte-là c'est pour un scheduler...

Mais dans le principe, c'est la même chose vu de l'autre côté..

Donc , en appliquant le même principe, ça marche aussi (en fait c'est la bibliothèque des 2 routines entrèe et sortie), et non le programme appellant.

Mais le programme appelant a néanmoins besoin d'avoir une instruction équivalente, non ? (comme dans MMI).

En fait, le "programme appelant" n'a pas besoin d'instruction de synchronisation. On peut faire la synchronisation directement dans le semaphore (la bibliothèque des 2 routines ).

Cette synchronisation supplémentaire est de type "mutex", qu'on peut implementer simplement avec un spin-lock. Il faut juste que les operations de read/write d'un octet soient atomiques.

[souviron34]

je ne comprend toujours pas le pourquoi du atomique.....

Bon, si je reprend, admettons que l'on ait :

• une bibliothèque contenant 1 routine dite "critique"
  
• un nombre max de processus l'appelant simultanément
  
• des processus l'appelant

Dans cette routine critique, on a :

• une section d'entrée
  
• le calcul proprement dit
  
• une section de sortie

Jusque-là, j'ai bon ?

ou alors la section d'entrée/sortie est dans le processus ?

ou ce n'est pas une biblothèque mais un processus ? un serveur ?


Que ce soit une bibliothèque ou un processus, il suffit de passer en paramètre d'appel le pid (getpid() en C), et le stocker (tableau dimensionné au nombre max possible). Ensuite le réveil se fera via l'envoi d'un signal (et alors l'attente sera un sleep(99999999)).

[pseudocode]

je ne comprend toujours pas le pourquoi du atomique.....

C'est juste une remarque en passant sur l'implementation du mutex... rien de bien important.

Jusque-là, j'ai bon ?

oui

ou alors la section d'entrée/sortie est dans le processus ?

non

ou ce n'est pas une biblothèque mais un processus ? un serveur ?

hum... dans le cas qui nous interesse (userland): non.

dans le cas d'un semaphore geré par l'os (kernel): oui. L'OS joue le role de "serveur": il gere le compteur du semaphore, les acces concurents (mutex) et endort/reveille les processus.

Que ce soit une bibliothèque ou un processus, il suffit de passer en paramètre d'appel le pid (getpid() en C), et le stocker (tableau dimensionné au nombre max possible). Ensuite le réveil se fera via l'envoi d'un signal (et alors l'attente sera un sleep(99999999)).

yes. 100% correct. 20/20.

[Celelibi]

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
 
procedure P(sem) {
    entrée_mutex;
    sem.compteur := sem.compteur - 1;
    if (sem.compteur < 0) {
    	currentprocess.status := WAIT;
    	sem.waiters.add(currentprocess);
        sortie_mutex;
        while (currentprocess.status == WAIT) {
            yield();
        }
    } else {
    	sortie_mutex;
    }
}

L'état WAIT est bien censé indiquer à l'ordonnanceur de ne plus exécuter le processus non ? Si c'est le cas, ton processus risque de se faire préempter immédiatement après avoir changé l'état du processus. Dans ce cas là il détient toujours le mutex, il n'est pas dans la liste des processus, et n'est plus exécutable.
Si c'est pas ça, j'ai besoin d'explication.
Pour rappel : la préemption c'est quand le système décide que le processus s'est assez exécuté pour le moment et interrompt son exécution pour exécuter un autre processus.
Et la fonction yield elle fait quoi ?

Ca c'est le semaphore au sens litteral, genre feu rouge. Celelibi parle du semaphore de Dijkstra.

Je connaissais les sémaphores en navigation et en informatique, mais pas au sens "feu rouge".
Mais bon, en informatique il existe d'autres sémaphores qui reprennent en quelques sortes les principes des sémaphores de Dijkstra (les sémaphores system V et POSIX pour ne citer qu'eux).


souviron34, dans le sens où c'est l'opération V qui va choisir à quel processus il va donner sa ressource, oui c'est un peu un ordonnanceur (ou scheduler).

Histoire de compléter pseudocode et d'illustrer un peu l'utilisation des sémaphores de Dijkstra, on suppose le sémaphore place_parking initialisé à 20 (autre chose si ça vous fait plaisir).
Et le processus "voiture" défini comme suit :

Code :

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

1
2
3
4
5
6
7
aller_au_parking();
P(place_parking);
se_garer();
//faire_ses_courses;
sortir_du_parking();
V(place_parking);
rentrer_chez_soi();

Tu peux lancer 50000 processus voiture il n'y en aura jamais plus de 20 en même temps dans le parking.

Pourquoi ne pas avoir simplement 20 mutex ?
Parce que toutes les places sont identiques et qu'il n'y a aucune raison qu'une voiture choisisse une place plutôt qu'une autre.
En effet, si le parking est plein on aurait la 21eme voiture qui attendrait devant une des places prises, et si c'est une autre qui se libère, bah celle-là elle attend toujours sa place.
(Et puis c'est juste pour illustrer les sémaphores.)

[pseudocode]

Pour rappel : la préemption c'est quand le système décide que le processus s'est assez exécuté pour le moment et interrompt son exécution pour exécuter un autre processus.

cool... un petit rappel ne fait jamais de mal...

L'état WAIT est bien censé indiquer à l'ordonnanceur de ne plus exécuter le processus non ?

Non. Il n'y a pas d'ordonnanceur dans un modele "100% userland".

Ici, on fait juste une attente active (busy-wait). La variable "status" est une variable banale, spécifique au processus. On la change de valeur comme n'importe quelle autre variable.

yield() est un microsommeil equivalent a sleep(0)... (c'est un peu plus fort que ca, mais on va dire que ca ira).

Si c'est le cas, ton processus risque de se faire préempter immédiatement après avoir changé l'état du processus. Dans ce cas là il détient toujours le mutex, il n'est pas dans la liste des processus, et n'est plus exécutable.
Si c'est pas ça, j'ai besoin d'explication.

Le processus peut etre préempté n'importe quand. Dans un modele "100% userland", on ne doit pas présupposer de l'ordonnancement.

Tant que le processus detient le mutex dans P(), personne d'autre ne peut s'executer, donc il reprendra la main tot ou tard dans P().

L'endroit interessant, c'est apres le "sortie_mutex" dans le "if" de P().

Si le processus est préempté a ce moment la + c'est le seul processus dans la file d'attente "waiters" + V() est appelé, alors le code de V() repasse immédiatement le processus dans l'etat "RUN'...

... et a la fin de la préemption, le processus continue a executer le code dans P(), et ne rentre meme pas dans le "while" => sortie de P().

Ce qui est le fonctionnement attendu.

[Celelibi]

En effet, c'est une bonne solution avec attente active, je la garde dans un coin.

Est-il possible d'avoir une solution similaire avec attente passive ?
J'ai beau torturer le problème dans tous les sens j'ai toujours une action à effectuer de manière indivisible avec la mise en sommeil du processus.

[pseudocode]

En effet, c'est une bonne solution avec attente active, je la garde dans un coin.

Est-il possible d'avoir une solution similaire avec attente passive ?
J'ai beau torturer le problème dans tous les sens j'ai toujours une action à effectuer de manière indivisible avec la mise en sommeil du processus.

Oui, il y en a... mais il faut connaitre le fonctionnement "interne" des fonctions de synchronisation (wait, wakeup, signal, ...)

Une methode "sale" consiste a:
1. endormir le processus dans P() (remplacer yield() par wait())
2. bombarder le processus de wakeup() dans V() jusqu'a son reveil

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
 
procedure P(sem) {
    entrée_mutex;
    sem.compteur := sem.compteur - 1;
    if (sem.compteur < 0) {
    	currentprocess.status := WAIT;
    	sem.waiters.add(currentprocess);
        sortie_mutex;
        while (currentprocess.status == WAIT) {
            currentprocess.wait();
        }
        currentprocess.status == RUN;
    } else {
    	sortie_mutex;
    }
}

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
procedure V(sem) {
    entrée_mutex;
    sem.compteur := sem.compteur + 1;
    if (sem.compteur <= 0) {
    	process := sem.waiters.getAndRemoveFirst();
	process.status := WAKEUP;
	while (process.status != RUN) {
                process.wakeup();
                yield();
        }
    }
    sortie_mutex;
}

[Celelibi]

Hum, joli, j'y aurais vraiment pas pensé.

Mais pourquoi il y a un while dans P ? C'est pour le cas où il recevrait un signal wakeup sans qu'on veuille le réveiller ?

Et pour la ligne qui suit ce while je suppose que c'était un ":=" et pas un "==".

Cela dit je remarque que ça revient à faire de l'attente active dans l'opération V. Il faut attendre que le processus qu'on réveil ait changé son état.


Bien que la solution ne soit pas des plus jolies, elle me convient quand même. Bien joué pseudocode.

[pseudocode]

Mais pourquoi il y a un while dans P ? C'est pour le cas où il recevrait un signal wakeup sans qu'on veuille le réveiller ?

Heu... oui. C'est vrai que dans ton cas, on peut s'en passer. En pratique, il vaut mieux le laisser car on ne sait jamais "pourquoi" l'ordonnanceur reveille un processus. Ca peut etre parceque on a explicitement appelé V(), mais ca peut venir de tout un tas d'autres raisons.

Et pour la ligne qui suit ce while je suppose que c'était un ":=" et pas un "==".

arf. oui. un copier/coller un peu hatif.

Cela dit je remarque que ça revient à faire de l'attente active dans l'opération V. Il faut attendre que le processus qu'on réveil ait changé son état.

bien vu. C'est pour ca que je dis que c'est plutot "sale". On deplace le busy-wait dans V(), ce qui en theorie coute moins cher en CPU que de le laisser dans P(). En probabilité, un processus passe plus de temps a "attendre" un ressource qu'a la liberer...

Bien que la solution ne soit pas des plus jolies, elle me convient quand même. Bien joué pseudocode.

Le principal c'est que ca te convienne .

Poru reprendre ce que je disais plus tot, si tu commences a jouer avec wait/wakeup, tu n'es plus dans une approche "100% userland. Tu accède a des fonctions "internes" de l'OS. Et dans ce cas, tu as certainement accès a une implémentation optimisée des sémaphores, signaux, ... inutile de s'en priver.