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ï

[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 ??