Implémentation purement logiciel des sémaphores

Version imprimable

Voir 40 message(s) de cette discussion en une page

24/08/2007, 01h46
souviron34

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

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...
24/08/2007, 09h34
pseudocode

Citation:

Envoyé par Celelibi

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

Citation:

Envoyé par Celelibi

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... :mouarf:
24/08/2007, 11h48
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.
24/08/2007, 12h29
souviron34

Citation:

Envoyé par Celelibi

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

Désolé :P 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...
24/08/2007, 13h34
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:

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. :P
24/08/2007, 14h13
souviron34

Sans avoir suivi de cours (:P) 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...

Citation:

Envoyé par souviron34

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:

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.

Citation:

Envoyé par Celelibi

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:

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:

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

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:

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:

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 :

Citation:

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

Citation:

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

24/08/2007, 16h27
pseudocode

Citation:

Envoyé par souviron34

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.

Citation:

Envoyé par 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)
24/08/2007, 16h40
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).
24/08/2007, 16h49
pseudocode

Citation:

Envoyé par 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).

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.
24/08/2007, 17h29
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)).
24/08/2007, 17h54
pseudocode

Citation:

Envoyé par souviron34

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.

Citation:

Jusque-là, j'ai bon ?

oui

Citation:

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

non

Citation:

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.

Citation:

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. :king:

Citation:
Envoyé par pseudocode
Code:

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 ?

Citation:

Envoyé par pseudocode

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:

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

24/08/2007, 22h50
pseudocode

Citation:

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

Citation:

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

Citation:

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. ;)
25/08/2007, 09h41
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.

Citation:

Envoyé par 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.

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:

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:

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

25/08/2007, 20h36
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 ? :P

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.
26/08/2007, 13h38
pseudocode

Citation:

Envoyé par Celelibi

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 ? :P

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.

Citation:

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.

Citation:

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

Citation:

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 :mrgreen:.

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. :king:

Voir 40 message(s) de cette discussion en une page