Sommaire

Définition succincte
Remarques générales
Réalisation de l'exclusion mutuelle
Problèmes posés par l'utilisation des sémaphores

Interblocage
Attente indéfinie en section critique
Privation (ou famine)

Processus

    Cette notion sera reprise en détail dans le chapitre du cours S.E. : "Vie et mort d'un processus".

Ressources

Sommaire

Echanges de données entre processus

    Un autre type d'interaction, cette fois voulue et forte, intervient lorsque deux processus coopèrent : chacun a une fonction définie dans le système et des échanges d'informations sont en général fréquemment nécessaires. Considérons par exemple un programme qui lit des données, les stocke dans une structure (liste, arbre, objet, fichier, etc...) et les traite.

    Une analyse classique du programme conduit à un corps du programme principal qui appelle successivement ou alternativement trois sortes de procédures correspondant aux trois sortes d'activités. On peut donc envisager le programme comme une boucle qui commence par une saisie, puis, en fonction de cette saisie, stocke la donnée, ou la traite avant de la stocker, ou la stocke sans la traiter, ou la retire de la structure de données, ou ..., puis retourne à la saisie. Il s'agit ici seulement d'appels à des procédures qui s'exécutent l'une après l'autre, donc séquentiellement. L'interaction entre les procédures est définie par l'intersection des antécédents et conséquents de ces procédures, soit, pour l'essentiel, la donnée en cours de traitement.

    Une autre approche, souvent beaucoup plus élégante, évolutive, et ayant de nombreux autres avantages, consiste à considérer l'application comme constitué de trois activités relativement indépendantes :

• les entrées/sorties sur un écran-clavier (menus déroulants, masque de saisie, etc...)
• le traitement proprement dit des données,
• la mémorisation et la restitution des données dans une structure de données (liste, arbre, etc...)

    Le problème qui se pose alors est celui de l'échange d'informations entre processus. Plusieurs solutions peuvent être envisagées selon les cas :

• un processus écrit dans un fichier, l'autre lit dedans (avec des conflits possibles si les opérations sont simultanées (ce type de situation sera repris en détail ultérieurement, lors de l'étude du problème des "Producteurs-consommateurs"). C'est de toutes façons une solution très lente, à n'utiliser que s'il n'y a pas mieux.
• un processus envoie les informations sur le réseau, l'autre les récupère à l'autre bout. Tous les problèmes sont gérés par la "couche de communication" et sont totalement transparents pour l'utilisateur. Cette solution ne correspond qu'au cas de processus tournant sur des machines distinctes et reliées par un réseau.
• lorsque les processus tournent sur la même machine, ils peuvent partager et utiliser la même mémoire centrale et le même processeur (et ses registres). Cette dernière solution est trop particulière pour être envisagée ici. Reste la mémoire : un processus peut recopier ses informations dans une zone mémoire d'emplacement convenu à l'avance, où l'autre processus ira les chercher. On parle alors de mémoire partagée. C'est la méthode la plus efficace et la plus rapide, qui peut encore être améliorée dans certains cas en évitant la recopie de l'espace propre d'un processus vers la mémoire partagée ou inversement. Il suffit pour cela que les différents processus travaillent directement avec les variables en mémoire partagée.

Exclusion mutuelle

    Soit X une variable en mémoire partagée. L'accès à cette variable doit être effectué en exclusion mutuelle. En effet considérons l'instruction ADA suivante :
 

X := X + 5;

    Cette opération n'est pas atomique : elle n'est pas effectuée "en une fois", (nous reviendrons plus tard dans le cours S.E. sur la notion d'atomicité). Elle est traduite dans un assembleur par plusieurs instructions élémentaires qui vont être exécutées successivement :
 

{1}  LOAD reg, x {2}  ADD  reg, 5 {3}  STO  reg, x

    Supposons que deux processus veuillent incrémenter simultanément X. La séquence d'instructions peut être la suivante : {1}, {2}, {1'}, {2'}, {3'} et {3}, le processus 1 ayant été interrompu après avoir commencé l'opération. Le résultat sera faux. Il faut donc que la variable X soit protégée pendant toute la durée de l'opération par une exclusion mutuelle.

    Le processeur étant une ressource critique, son utilisation doit être faite en exclusion mutuelle. C'est bien ce qui se passe dans la réalité, un seul processus étant exécuté à la fois. Le mécanisme qui réalise l'exclusion mutuelle est ici totalement matériel. L'accès à une ressource critique de plusieurs processus a pour effet de les sérialiser.

Sommaire

Sections critiques

    Quelques règles doivent être données pour une utilisation correcte des sections critiques :

• une section critique doit être la plus courte possible. Elle perturbe en effet le quasi-parallélisme et pourrait priver les autres processus de la ressource processeur.
• un processus ne peut rester indéfiniment dans une section critique. Cela implique que, si un programme boucle dans une section critique, le système puisse non seulement l'interrompre au bout d'un temps raisonnable, mais encore débloquer les autre processus en attente de la même ressource.
• il ne faut faire aucune hypothèse sur les vitesses d'exécution relative des différentes instructions,
• un processus hors de sa section critique ne doit pas pouvoir empêcher un autre d'accéder à la ressource critique associée à cette section.

Sémaphores - Première approche

    Les sémaphores sont parmi les outils les plus élémentaires permettant de réaliser l'exclusion mutuelle. Ils sont à la fois faciles à implanter et suffisamment puissants pour permettre d'exprimer élégamment les solutions aux problèmes d'exclusion mutuelle et de synchronisation. Ils ont été imaginés par DIJSKTRA en 1965.

Définition succincte

    L'appel par un programme de la primitive P(s), où s est la variable "sémaphore", provoque l'exécution de la séquence suivante :
 

si (valeur du compteur de s > 0) alors     décrémenter le compteur de 1 sinon     <suspendre l'exécution du processus en cours> finsi

    L'appel par un programme de la primitive V(s), où s est la variable "sémaphore", provoque l'exécution de la séquence suivante :
 

si (au moins un processus a été précédemment suspend           sur s par une opération P(s)) alors  <réveiller un de ces processus> sinon  incrémenter le compteur de 1 finsi

Sommaire

Remarques générales

    Les primitives P et V s'excluent mutuellement (par définition), donc si deux d'entre elles se produisent simultanément, elles sont exécutées séquentiellement dans un ordre arbitraire.

    La primitive V n'est jamais bloquante. La primitive P peut l'être.

    Un sémaphore qui ne prend que les valeurs 0 et 1 est appelé sémaphore binaire. Sinon, il est appelé sémaphore général ou sémaphore n-aire.

    Il est impossible d'accéder au contenu d'un sémaphore autrement que par les deux primitives. En particulier, il est impossible de tester ou de modifier la valeur du compteur. De plus, les processus en attente sur un sémaphore sont stockés dans une structure cachée (une donnée-membre du sémaphore), elle aussi inaccessible à l'utilisateur qui ne peut ni savoir comment elle est gérée, ni en modifier gestion. C'est souvent une structure FIFO (file d'attente First In First Out) qui est adoptée.

    Quelle que soit l'implémentation (mécanisme offert par le S.E., par un langage de programmation, ou simulation de sémaphore par un autre mécanisme), nous supposons ici qu'un sémaphore est un objet de type T_Semaphore. Suivant l'implémentation, les primitives P(s) et V(s) existent ou doivent être implémentées. De plus l'utilisateur dispose de, ou doit mettre en place, deux primitives permettant de créer et de détruire un sémaphore: Creer_Sem(s, v) et Detruire_Sem(s), où s est de type T_Semaphore et v est la valeur entière à laquelle le compteur associé au sémaphore est initialisé à la création. On peut montrer que v correspond au nombre d'accès simultanés maximal à la ressource critique.

Sommaire

Réalisation de l'exclusion mutuelle

    Le fonctionnement est le suivant: l'un des deux processus se présente devant le sémaphore (exécute la primitive ininterruptible P(s)). Le compteur est décrémenté et vaut donc 0 et le processus entre dans sa section critique. Si le deuxième processus exécute à son tour P(s), le compteur ne peut être décrémenté, donc le processus est mis en file d'attente. Il ne sera réveillé que lorsque l'autre aura fini d'exécuter V(s).

    Ce mécanisme peut être étendu à un nombre quelconque de processus: le premier arrivé entrera dans sa section critique, tous les autres iront en file d'attente, l'un d'eux sera réveillé par la sortie du premier, entrera lui-même dans sa section critique, et ainsi de suite.

Sommaire

Problèmes posés par l'utilisation des sémaphores

Interblocage

     A l'évidence, si les deux processus se présentent à peu près simultanément devant leurs section critique, la séquence suivante est possible et conduit à l'interblocage:
 

{1}, {1'}, {2}, {2'}

    Aucun des deux processus ne peut aller plus loin! On démontre que seules les sections imbriquées dans le même ordre protègent de l'interblocage.

    Il est d'ailleurs encore plus facile d'obtenir un simple blocage d'un processus par lui-même :
 

P (s); P (s);  !!!   c'est fini.

    Il est donc risqué de confier à l'utilisateur la responsabilité de s'assurer de la validité de l'implémentation.

Sommaire

Attente indéfinie en section critique

Privation (ou famine)

© D. Mathieu     mathieu@romarin.univ-aix.fr
I.U.T.d'Aix en Provence - Département Informatique