Implémentation purement logiciel des sémaphores
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:
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:
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.
