Upload
cateline-rousset
View
108
Download
0
Embed Size (px)
Citation preview
GEF 435Principes des systèmes d’exploitation
Communication Interprocessus (CIP) II(Tanenbaum 2.3)
Revue
• Qu’est-ce que la concurrence critique (race
condition)?• Quel est le nom de la place dans un programme où
la concurrence critique peut arriver?• Quelles sont les quatre requis ou règles que les
algorithmes de sections critiques doivent rencontrer?
Synopsis
• Exclusion mutuelle sans attente active: sleep() and wakeup()
• Le problème du producteur/consommateur• Sémaphores• Résolution du problème du
producteur/consommateur avec les sémaphores• Mutex
sleep() et wakeup()Peterson
• Recall: Peterson’s Solution
sleep() et wakeup()
• La solution de Peterson (et aussi l’instruction TSL que nous avons vue) utilisent l’attente active ce qui gaspille beaucoup de cycles de CPU qui pourraient être utilisés à autres travails
• Autres effets qui sont imprédictibles : Inversion de priorité: Le processus L est dans sa
région critique. Processus H devient prêt à entrer dans sa région critique. Comme processus à plus haute priorité, H exécute une attente active et ne peut jamais entrer!
• L n’exécute jamais plus (Pensez à µC/OS)
sleep() et wakeup()
• Au lieu de faire de l’attente active, qu’arrive t’il si un processus peut être suspendu pendant qu’il attend d’entrer dans sa région critique?
• Crée deux appels de système: sleep() et wakeup()sleep() cause le processus à bloquer jusqu’à ce qu’il
soit éveillé par un autre processuswakeup(procID) éveille un autre processus avec un
identification spécifique
Le Problème Producteur/Consommateur• Quel problème existe ici?
Le Problème Producteur/Consommateur
• Une façon de réparer ce problème existe : ajouter une bit wakeupwaiting quant le processus qui est déjà éveillé se fait dire de s’éveillerUn processus qui essaie de dormir va décrémenter cette
bit au lieu de dormir si la bit est réglé (>0)Répare ce problème particulier. Que ce passe t’il si
nous avons 2 consommateurs, 10, 100…
Sémaphores
• Un nouveau type de variable un sémaphore, a été introduit en 1965 par Dijkstra pour entreposer les appels éveille pour utilisation futureLe sémaphore peut avoir la valeur 0, indiquant
qu’aucun éveil n’est sauvé, ou une valeur positive quelconque, indiquant les éveils accumulés
Utilise deux opérations down() et up() pour opérer les sémaphores
Sémaphores
• Opération des sémaphores:L’opération down() vérifie pour voir si le sémaphore
est plus grand que 0. Si oui, décrémente la valeur et continue
Si non, le processus qui a appelé down() s’endortLa vérification de la valeur, le changement et l’action
de s’endormir est un action atomique (indivisible)• Cette indivisibilité est essentiel pour résoudre la concurrence
mutuelle!
Sémaphores
• L’opération des sémaphores:L’opération up() essaie d’incrémenter le sémaphore. Si il y a
un processus qui dort sur le sémaphore, un est éveillé aléatoirement et permit de continuer
• Notez que la valeur du sémaphore va être encore 0, mais il va y avoir moins de processus qui dorment.
Si aucun processus ne dormais, alors la valeur est incrémenté; aucun processus ne bloque sur un up()
• Comment les sémaphores peuvent aider à résoudre le problème du producteur/consommateur?
Résolution du problème P/C
• Notez que nous avons utilisé les sémaphores pour deux différentes intentions:Le sémaphore mutex garantie l’exclusion mutuelle pour l’accès
d’une ressource partagée• Un sémaphore avec seulement deux états (0,1) s’appel sémaphore
binaire
Les sémaphores full/empty sont utilisés pour la synchronisation; ils garantissent l’occurrence ou la non occurrence de certaines séquences d’événements
• ie: Le producteur arrête de produire quand le tampon est plein et le consommateur arrête de consommer quand le tampon est vide
Résolution du problème P/C
• Pour que cela marche, les fonctions up() et down() doivent être implémentés comme actions atomiques... Tout le reste est basé sur ce faitTypiquement atteint en les implémentant comme appels
de système où les interruptions sont désactivées par le SE
• Ceci est bon parce que les opérations sont seulement quelques instructions
• Seulement le sémaphore est mis à jour et possiblement un processus éveillé
Mutex
• Si la capacité de contage du sémaphore n’est pas requise, une forme plus simple, mutex peut être utiliséeSeulement bon pour gérer l’exclusion mutuelle; ils ne
communiquent pas d’autre information
• Cette simplicité requiert seulement des commandes dans l’espace utilisateur si une commande TSL est disponible
• Un mutex a deux états: barré et débarré• Un thread qui veut entrer dans la région critique appel mutex_lock()
Mutex
• Comme le code l’indique, si le mutex n’est pas barré, le thread retourne et entre dans la région critique. Autrement le thread cède et permet à un autre thread d’accéder au CPU
Mutex
• Attendez, est-ce la même chose que enter_region()?
• Quels sont les deux avantages majeurs des mutex sur enter_region()?
Quiz Time!
Questions?