Discussion :

[Celelibi]

Salut,

Après m'être replongé dans mes cours de système d'exploitation, je me suis rendu compte qu'il y avait certaines zones qui étaient restés assez floues, notamment concernant l'implémentation des sémaphores.

Par exemple pour l'opération P des sémaphores de Dijkstra

Code :

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

1
2
3
4
5
6
7
8
9
 procedure P (sem) {
    entrée_mutex;
    sem.compteur := sem.compteur - 1;
    if (sem.compteur < 0) {
        sem.liste.ajouter(processus_actuel);
        processus_actuel.endormir;
    }
    sortie_mutex;
}

J'ai mis un mutex pour garantir que l'opération P ne pourra pas être interrompue par une opération P ou V d'un autre processus.

Ce code peut sembler bien mais il ne fonctionne pas, car quand on endort le processus on a toujours le mutex. Relâcher le mutex juste avant d'endormir le processus ne marche pas non plus car il serait possible que le processus soit préempté après avoir relâché le mutex (et avant d'endormir le processus) et qu'un autre processus exécute une opération V sur le même sémaphore. Cette opération V va essayer de réveiller notre processus qui n'était pas endormis (donc sans effet), et quand notre processus continuera son exécution il va s'endormir alors que le compteur vient de passer positif.

Tenter de séparer "endormir" en un changement d'état suivit d'un réordonnancement (comme dans l'exemple sur wikipedia) ne marche pas non plus.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
 procedure P (sem) {
    entrée_mutex;
    sem.compteur := sem.compteur - 1;
    if (sem.compteur < 0) {
        sem.liste.ajouter(processus_actuel);
        processus_actuel.état := attente;
        sortie_mutex;
        ordonnancement;
    } else {
        sortie_mutex;
    }
}

Si notre processus est préempté juste après le changement d'état mais avant la sortie du mutex, notre processus ne pourra plus être exécuté à cause de son état qui n'est plus "prêt", et le mutex n'est pas relâché.
Il faudrait que le changement d'état et la sortie du mutex ne soit pas interrompu même par un processus qui n'a rien à voir avec nos sémaphores. Ceci ne me semble pas faisable de manière totalement logicielle.

Donc ma question est : est-il possible d'implémenter les sémaphores de manière purement logicielle ? C'est à dire sans faire appel à une instruction matérielle (comme le masquage des interruptions) ni à une fonction spécifique au système d'exploitation.



Et question subsidiaire : est-il possible de concevoir un algo d'exclusion mutuelle qui fasse de l'attente passive à partir d'un algo d'exclusion mutuelle qui fait de l'attente active ?
J'explique : j'ai un mutex qui utilise l'algo de peterson (par exemple) et je voudrait construire un mutex qui fait de l'attente passive.



Mes questions c'est pas parce que j'ai envie d'implémenter des sémaphore ou des mutex, c'est d'un point du vue purement théorique.

Merci d'avance.

[PRomu@ld]

Il me semble qu'on a eu droit au même cours de système d'exploitation (et c'est là que le bat blesse )

J'ai mis un mutex pour garantir que l'opération P ne pourra pas être interrompue par une opération P ou V d'un autre processus.

En fait, si tu veux réellement interdire l'exécution, il faut mettre en place l'exclusion mutuelle de façon matérielle (masquage des interruptions ), car un mutex est un sémaphore à un jeton et il faut que toutes les autres primitives testent ce mutex avant de commencer (un oubli et là c'est le drame).

Relâcher le mutex juste avant d'endormir le processus ne marche pas non plus car il serait possible que le processus soit préempté après avoir relâché le mutex (et avant d'endormir le processus) et qu'un autre processus exécute une opération V sur le même sémaphore.

En fait, ça ne pose pas de problème si tes primitives P et V partagent le même mutex, puisque admettons que ton processus soit préempté juste après l'endormissement, l'entrée dans la primitive V va s'arrêter sur le dépôt du mutex (qui est déjà pris par P) et donc la seule primitive qui va pouvoir finir son exécution c'est la primitive P, donc il ne devrait pas y avoir de soucis.

Donc ma question est : est-il possible d'implémenter les sémaphores de manière purement logicielle ? C'est à dire sans faire appel à une instruction matérielle (comme le masquage des interruptions) ni à une fonction spécifique au système d'exploitation.

En fait non, puisque si tu es en pur logiciel, aucun moyen d'assurer une lecture propre (ton processus peut-être pré-empté n'importe quand sans que tu le saches)

est-il possible de concevoir un algo d'exclusion mutuelle qui fasse de l'attente passive à partir d'un algo d'exclusion mutuelle qui fait de l'attente active ?

Intuitivement je dirai non, mais je n'ai pas encore creusé la question pour un début de justification. (mais de toute manière si c'est possible par un artifice, tu auras toujours de l'attente active de part la construction du sous système)

[Celelibi]

En fait, ça ne pose pas de problème si tes primitives P et V partagent le même mutex, puisque admettons que ton processus soit préempté juste après l'endormissement, l'entrée dans la primitive V va s'arrêter sur le dépôt du mutex (qui est déjà pris par P) et donc la seule primitive qui va pouvoir finir son exécution c'est la primitive P, donc il ne devrait pas y avoir de soucis.

Comment un processus qui s'est endormi va-t-il pouvoir poursuivre son exécution ?
Le seul moyen de le réveiller est d'effectuer une opération V, ce qui n'est pas possible puisque le mutex n'est pas libre.

Code :

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

Intuitivement je dirai non, mais je n'ai pas encore creusé la question pour un début de justification.

Dire "non" à cette question ça revient à dire qu'il est impossible d'avoir une implémentation purement logicielle des sémaphores.


PS : En effet, on a très certainement eut droit aux même cours. Je pense qu'Annie Geniet refait les mêmes cours depuis 10 ans, ce qui expliquerait la légère impression de "vieux cours".

[PRomu@ld]

Comment un processus qui s'est endormi va-t-il pouvoir poursuivre son exécution ?

Oups désolé, j'avais vu ça un peu trop vite ce matin. En fait, ce qu'il faut faire, c'est rendre l'opération endormir atomique avec deux opérations : endormissement et libération du mutex.

Dans ce cas, la procédure P devient :

Code :

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

1
2
3
4
5
6
7
8
9
10
procedure P (sem) {
    entrée_mutex;
    sem.compteur := sem.compteur - 1;
    if (sem.compteur < 0) {
        sem.liste.ajouter(processus_actuel);
        processus_actuel.endormir;
        return;
    }
    sortie_mutex;
}

[pseudocode]

J'ai mis un mutex pour garantir que l'opération P ne pourra pas être interrompue par une opération P ou V d'un autre processus.

Mouais... vu qu'un mutex n'est qu'un semaphore binaire (count=1), ca ne fait que repousser le probleme

Ce code peut sembler bien mais il ne fonctionne pas, car quand on endort le processus on a toujours le mutex.

Exact.

Relâcher le mutex juste avant d'endormir le processus ne marche pas non plus car il serait possible que le processus soit préempté après avoir relâché le mutex (et avant d'endormir le processus) et qu'un autre processus exécute une opération V sur le même sémaphore. Cette opération V va essayer de réveiller notre processus qui n'était pas endormis (donc sans effet), et quand notre processus continuera son exécution il va s'endormir alors que le compteur vient de passer positif.

On pourrait s'en sortir en faisaint un double-check sur la valeur du compteur du semaphore, juste avant d'endormir le processus. Mais c'est assez sale.

Generalement dans les OS "traditionnels", l'utilisation d'un semaphore se termine tot ou tard par un appel systeme, et on se retrouve donc du coté "kernel". Dans ce cas, on n'a plus de probleme de préemption car les appels systemes liés aux semaphores sont non-interruptibles.

[Celelibi]

Mouais... vu qu'un mutex n'est qu'un semaphore binaire (count=1), ca ne fait que repousser le probleme

Un mutex n'est pas nécessairement un sémaphore initialisé à 1, les algorithmes d'exclusion mutuelle tels que celui de Peterson ou de Dekker ne sont pas basés sur des sémaphores.

On pourrait s'en sortir en faisaint un double-check sur la valeur du compteur du semaphore, juste avant d'endormir le processus. Mais c'est assez sale.

Tu parles d'un comme comme ça ?

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
procedure P (sem) {
    entrée_mutex;
    sem.compteur := sem.compteur - 1;
    if (sem.compteur < 0) {
        sem.liste.ajouter(processus_actuel);
        sortie_mutex;
        if (sem.compteur < 0) {
            processus_actuel.endormir;
        }
    }
    sortie_mutex;
}

Ça ne marche pas non plus car on risque de se faire préempter après le deuxième test avant de s'endormir. Et c'est le même problème, si il y a une opération V qui est exécutée durant ce temps.


Donc si je comprend bien, il est impossible d'avoir une implémentation purement logicielle des sémaphores. À moins de tricher en disant soit :
- Lorsque le processus s'endort, il sort de l'opération P et par conséquent libère le mutex
- Il y a une instruction qui relâche le mutex et endort le processus de façon atomique
- On réalise de façon atomique le relâchement du mutex et le changement d'état du processus

[pseudocode]

Un mutex n'est pas nécessairement un sémaphore initialisé à 1, les algorithmes d'exclusion mutuelle tels que celui de Peterson ou de Dekker ne sont pas basés sur des sémaphores.

Oui, c'est vrai qu'un mutex n'est pas nécessairement "implémenté" comme un sémaphore. Mais son fonctionnement est analogue, donc on a le meme probleme d' "entrée" et de "sortie" des sections critiques.

Tu parles d'un comme comme ça ? (...)

oui, presque... on doit changer l'état du processus pendant qu'on possede encore dans le mutex (processus_actuel.status=wait_pending) et tester cette valeur dans V() et dans le double-check pour savoir s'il y a eu preemption ou maj du semaphore... Et idem dans V (processus_actuel.status=wakeup_pending).

C'est le principe utilisé dans linux (qui utilise des listes de processus en attente de wait/wakeup)

http://lxr.linux.no/source/lib/semaphore-sleepers.c

42 * Logic:
43 * - only on a boundary condition do we need to care. When we go
44 * from a negative count to a non-negative, we wake people up.
45 * - when we go from a non-negative count to a negative do we
46 * (a) synchronize with the "sleeper" count and (b) make sure
47 * that we're on the wakeup list before we synchronize so that
48 * we cannot lose wakeup events.

Donc si je comprend bien, il est impossible d'avoir une implémentation purement logicielle des sémaphores. À moins de tricher en disant soit :
(...)

Ce n'est pas "tricher". L'implementation d'un semaphore se termine generalement par un bloc de code "non interruptible/préemptable" géré par l'OS (ou la VM).

[Celelibi]

J'ai dit "tricher" car mon but est quand même de trouver une solution 100% logicielle, et les trois assertions proposés font appel au système ou au matériel.

[Jedai]

J'ai dit "tricher" car mon but est quand même de trouver une solution 100% logicielle, et les trois assertions proposés font appel au système ou au matériel.

C'est impossible.

--
Jedaï

[Celelibi]

Serait-il possible que tu explique pourquoi c'est impossible ?

[Graffito]

Bonjour,

En fait, si tu veux réellement interdire l'exécution, il faut mettre en place l'exclusion mutuelle de façon matérielle (masquage des interruptions )

L'autre methode est l'utilisation des instructions (inintéruptibles) de SWAP consistant à échanger le contenu d'un mot mémoire avec celui d'un registre.

On peut ainsi bloquer temporairement l'accès à une fonction.
On met le registre à la valeur "Bloquage activé", on fait le swap avec la variable d'état associé à la fonction et on teste la valeur précédement d'état lue en mémoire:
- si "bloquage activé", on boucle sur le swap,
- sinon, on exécute la fonction.
A la fin de la fonction, on remet la mémoire à la valeur "Bloquage désactivé".

[pseudocode]

Serait-il possible que tu explique pourquoi c'est impossible ?

parceque tu es obligé:
1. d'avoir un mutex sur le semaphore (lecture & ecriture)
2. de relacher le mutex du semaphore avant d'endormir le processus...

Et donc il peut y avoir la perte d'un evenement "reveil".

[Jedai]

Bonjour,


L'autre methode est l'utilisation des instructions (inintéruptibles) de SWAP consistant à échanger le contenu d'un mot mémoire avec celui d'un registre.

On peut ainsi bloquer temporairement l'accès à une fonction.
On met le registre à la valeur "Bloquage activé", on fait le swap avec la variable d'état associé à la fonction et on teste la valeur précédement d'état lue en mémoire:
- si "bloquage activé", on boucle sur le swap,
- sinon, on exécute la fonction.
A la fin de la fonction, on remet la mémoire à la valeur "Bloquage désactivé".

Oui mais là, si tu travailles avec de l'assembleur, tu sais qu'il y a un certain nombre d'opérations ininterruptibles, tu ne respectes donc pas le cahier des charges de Celelibi.

--
Jedaï

[souviron34]

J'ai dit "tricher" car mon but est quand même de trouver une solution 100% logicielle, et les trois assertions proposés font appel au système ou au matériel.

il me semble me souvenir (je n'ai suivi aucun cours d'info, à plus forte raison là dessus), mais j'ai pratiqué une année entière à temps plein les "VMS internals"...

Et ce qu'ils faisaient sur VMS était la chose suivante :

à l'époque il y avait 128 sémaphores locaux et 128 sémaphores réseaux (dans la partie physique du disque réservée aux COMMON et autres PSECT...) : 256 bits, dont chacun portait un nom logique.

Comme l'écriture d'une ligne d'un fichier, l'instruction "$FLAG1 = 1" permettait la modification du bit 1 et donc du sémaphore 1. En ce sens c'est du 100% logiciel.

Il suffisait donc dans les programmes de faire des while($FLAG1 = 1) par exemple, etc etc.. vous comprenez le principe..

Mais peut-être est-ce moi qui n'ai pas vraiment compris le problème ??

[Celelibi]

parceque tu es obligé:
1. d'avoir un mutex sur le semaphore (lecture & ecriture)
2. de relacher le mutex du semaphore avant d'endormir le processus...

Et donc il peut y avoir la perte d'un evenement "reveil".

Je me disait qu'il y avait peut-être une méthode totalement différente à laquelle je n'ai pas pensée.


souviron34 malheureusement il faut dans ton cas faire l'hypothèse que l'affectation d'un bit est atomique, ce n'est pas toujours le cas. D'ailleurs tester un bit n'est souvent pas une opération atomique non plus.
Quoi qu'il en soit ça revient à faire une hypothèse sur le matériel.


Au cas où ma question n'était pas clair jusque là, je cherche un algo purement logiciel pour les sémaphores, tout comme il en existe pour les mutex (comme l'algo de Peterson pour ne citer que lui).


Petit hors-sujet juste pour le fun : des gens on créés un programme qui trouve des algorithmes d'exclusion mutuelle http://bardavid.com/mead/ c'est ouf.


EDIT : j'ai l'impression que je vais avoir un problème similaire en tentant d'implémenter les moniteurs à partir des sémaphores, mais je vais d'abord étudier la question.

[pseudocode]

Il suffisait donc dans les programmes de faire des while($FLAG1 = 1) par exemple, etc etc.. vous comprenez le principe..
Mais peut-être est-ce moi qui n'ai pas vraiment compris le problème ??

Oui, c'est la methode dite du "spin lock" (ou busy-wait).

Dans ce cas, le processus en attente n'est pas endormi mais teste en permanance la dispo du verrou. C'est le principe expliqué sur wikipedia.

[souviron34]

...souviron34 malheureusement il faut dans ton cas faire l'hypothèse que l'affectation d'un bit est atomique, ce n'est pas toujours le cas. D'ailleurs tester un bit n'est souvent pas une opération atomique non plus.
Quoi qu'il en soit ça revient à faire une hypothèse sur le matériel.
...

Que ce soit un bit ou un octet ou un entier..

Je ne vois pas en quoi lire un fichier (ce qui revient strictement au même) serait faire une hypothèse sur le matériel ????

[Celelibi]

Ah, j'avais compris qu'il s'agissait de modifier des bits en mémoire et non pas dans un fichier, mais le problème est le même, on ne peut pas garantir que la lecture ou l'écriture sera atomique.


À propos des moniteurs : même en supposant qu'on dispose de sémaphores il semble impossible d'implémenter les moniteurs de façon purement logicielle pour des raisons similaires. Lors de l'opération wait des variables condition, il faut relâcher le mutex du moniteur avant d'endormir le processus (par une opération P sur un sémaphore).

C'est marrant parcequ'on trouve sur le net plusieurs implémentation des moniteurs avec des sémaphores, mais toutes sont victimes de ce problème.

[souviron34]

Ah, j'avais compris qu'il s'agissait de modifier des bits en mémoire et non pas dans un fichier, mais le problème est le même, on ne peut pas garantir que la lecture ou l'écriture sera atomique.

Encore une fois je ne comprend pas....

Si tu utilises par exemple une fonction comme fwrite(en C), tu peux très bien écrire un entier ou un char... je ne vois pas en quoi ton prog dépendra du matériel...

Et si par dessus, au lieu de faire comme j'avais dit un while, tu fais un usleep ou un timer avec un ordre de grandeur de la résolution minimale (microseconde (CLOCKS_PER_SEC)), quand tu es endormi, tu peux très bien vraisemblablement obtenir une synchro quasi-exacte (je dis bien quasi), et le tout 100% en logiciel..

Ou alors je ne comprend pas ton problème...

[Celelibi]

Je crois que j'avais mal compris ce que tu proposais souviron34.
Tu me propose de faire de l'attente active dans le sémaphore, quelque chose du genre :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
procedure P (sem) {
    entrée_mutex;
    sem.compteur := sem.compteur - 1;
    if (sem.compteur < 0) {
        while (sem.dispo = 0) {
            sortie_mutex;
            mirco_sommeil; // Juste histoire de relancer l'ordonnanceur
            entrée_mutex;
        }
        sem.dispo := sem.dispo - 1;
    }
    sortie_mutex;
}

J'ai rajouté sem.dispo, il est utilisé uniquement quand le compteur est négatif. L'opération V ne fait qu'incrémenter sem.dispo pour signaler aux processus qui attendent qu'une ressource est disponible.

C'est pas trop mal mais malheureusement il n'y a plus de gestion de file d'attente, l'opération V ne contrôle plus quel est le processus qui va se réveiller (car le "réveille" se fait via sem.dispo qui va devenir > 0).
Et le gros problème de cet algo, c'est le risque de famine lié à cette absence de gestion de file de processus. En effet, imaginons qu'il y ait 10 processus qui sont en attente d'une ressource dans ces 10 processus il y en a 1 qui est arrivé il y a 3 heures, et tous les autres sont arrivés il y a 0.42 secondes. 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à.
De plus il est possible pour les processus de se coaliser pour arriver de telle façon que le "vieux processus" n'obtiendra jamais la ressource.

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.