Aller au contenu

TNSI : OS - Communication Inter-Processus (IPC)⚓︎

Problématique⚓︎

Plusieurs processus indépendants doivent pouvoir s’exécuter sans interférence :

  • partage des ressources (arbitrage)
  • isolation des processus (abstraction, autorisation)

À l’inverse, Les processus, qu'ils soient lourds ou légers (threads), doivent pouvoir communiquer entre eux doivent pouvoir communiquer si leur programme le demande : on parle dans ce cas de Communication Inter-Processus 🇫🇷 / IPC - Inter-Process Communication 🇬🇧.

La communication IPC se fait dans des machines :

  • Monoprocesseur : un seul processeur doit partager plusieurs processus préemptibles (pseudo-parallélisme)
  • Multiprocesseur avec mémoire partagée : plusieurs processeurs se partagent plusieurs processus en parallèle.

Dans tous les cas, plusieurs processus (thread) sont en exécution concurrente :

  • l’ordre des accès à des mémoires partagées peut influencer le résultat final, d'où la nécessité de coopération et de synchronisation
  • Il y a donc besoin d'accès exclusif à une ressource partagée pour maintenir la cohérence des données

Il existe \(3\) sortes de mécanismes permettant à des processus concurrents de communiquer entre eux :

  • les mécanismes de coopération qui permettent l'Échange de Données entre les processus :
    • Fichiers,
    • Espaces Mémoires - RAM,
    • Tubes/Pipes,
    • Sockets (Unix ou Réseau),
    • etc..
  • les mécanismes permettant la Synchronisation entre les processus (notamment pour gérer les conflits grâce au principe :
    • des Signaux d'interruption logicielles par l'OS
    • des verrous 🇫🇷 / Locks 🇬🇧, qui utilisent le principe des mutex - EXclusion MUTuelle pour les sections critiques
    • des Sémaphores, sorte de verrou généralisé (non binaire), qui utilisent aussi des sections critiques.
  • les mécanismes permettant l'échange de données ET la synchronisation entre les processus.

Danger

La programmation concurrente est un problème difficile. Elle fait partie des domaines frontières de l'informatique

IPC par Échange de Données⚓︎

Les échanges de données entre processus concurrents peuvent se faire par différentes approches :

  • des Fichiers
  • des Espaces Mémoires (RAM)
  • des Tubes / Pipes (anonymes vs nommés)
  • des Sockets (Réseau vs Unix)
  • etc..

Dans les deux premiers cas, les échanges sont réalisés en plaçant les données en mémoire dans des variables partagées par les processus.

via des Fichiers⚓︎

  • Les fichiers peuvent être utilisés pour échanger des données entre plusieurs processus concurrents.
  • Les processus voulant envoyer des données écrivent dans un ou plusieurs fichiers à certaines positions
  • les processus souhaitant recevoir ces données se positionnent à ces positions dans le (ou les) fichier(s) et les lisent.

Ce type d'échange est possible entre des :

  • processus concurrents locaux (en utilisant le système de fichiers local), ou
  • des processus concurrents distants (en utilisant un système de fichiers distribué, tel que NFS).

via la mémoire RAM⚓︎

La mémoire principale (RAM) d'un ordinateur peut aussi être utilisée pour échanger des données entre plusieurs processus concurrents. Suivant le type de processus, les mécanismes utilisés ne sont pas les mêmes :

Col

Schéma de Principe de la Mémoire Virtuelle. Wikipedia

  • dans le cas de processus lourds, les espaces mémoires des processus ne sont pas partagés. On peut tout de même utiliser un mécanisme de partage de mémoire (tel que les segments de mémoire partagée dans Unix), appelé mémoire virtuelle1, dont le principe fondamental est une traduction à la volée des adresses -virtuelles- vues pas le logiciel, en adresses physiques de mémoire vive - RAM.
    • Principe de la mémoire virtuelle :
      • Les adresses mémoires émises par le processeur sont des adresses virtuelles, indiquant la position d'un mot dans la mémoire virtuelle.
      • La mémoire virtuelle est découpée en des pages2 de même taille.
      • Une Adresse Virtuelle est donc un couple (numéro de page, déplacement dans la page). La taille des pages est une puissance entière de deux, de façon à déterminer sans calcul le déplacement (10 bits de poids faible de l'adresse virtuelle pour des pages de 1 024 mots), et le numéro de page (les autres bits).
      • La mémoire vive (contenant les Adresses Physiques) est également composée de zones de même taille, appelées frames 🇬🇧 / cadres 🇫🇷, dans lesquelles prennent place les pages (un cadre contient une page : taille d'un cadre = taille d'une page). La taille de l'ensemble des cadres en mémoire vive utilisés par un processus est appelé Resident set size.
      • Un mécanisme de traduction (translation, ou génération d'adresse) assure la conversion des adresses virtuelles en adresses physiques, en consultant une table des pages 3 🇫🇷 / page table 🇬🇧 pour connaître le numéro du frame / cadre qui contient la page recherchée.
      • L'adresse physique obtenue est le couple (numéro de cadre, déplacement).
      • chaque processus contient sa propre table de page, qui contient les pages mémoires, mais ne les voit pas nécessairement à la même adresse
    • Avantages de la Mémoire Virtuelle : Elle permet de :
      • Utiliser la mémoire de massse comme extension de la mémoire vive
      • Augmenter le taux de multiprogrammation (nombre de processus présents dans la mémoire à un instant donné). Cf par ex. la commande vmstat sur Unix/Linux
      • Mettre en place des mécanismes de protection de la mémoire (verrous)
      • Partager la mémoire entre processus

Mémoire Virtuelle, Traduction Adresses Traduction à la volée des adresses virtuelles en adresses physiques, et certaines informations peuvent être temporairement placées sur un support de stockage. wikipedia

  • dans le cas de processus légers / thread, l'espace mémoire des processus est partagé, la mémoire peut donc être utilisée directement. Des problèmes de synchronisation peuvent alors apparaître (interblocage, etc..)

via des Tubes / Pipes⚓︎

Les Tubes 🇫🇷 / Pipes 🇬🇧 🇫🇷 peuvent être de deux sortes :

Tubes anonymes / anonymous Pipes⚓︎

Un tube anonyme 🇫🇷 / anonymous pipe 🇬🇧, ou canal de communication, est un mécanisme (inventé par Unix) de gestion de flux de données, dont l'utilisation principale est la communication inter-processus. Un tube/pipe anonyme est un flux de données unidirectionnel (Half Duplex) FIFO d'un processus vers un autre. Le tube/pipe anonyme est détruit lorsque le processus qui l'a créé disparaît, contrairement aux tubes nommés qui sont liés à l'OS, et qui doivent être explicitement détruits. Des communications inter-processus bi-directionnelles (Full Duplex) peuvent être créées grâce à deux pipes dans des sens opposés.

Exp

Les tubes Unix sont des implémentations des tubes anonymes: ils utilisant le symbole | (barre verticale ou pipe)
Les tubes Unix chaînent les processus de sorte que la sortie d'un processus (standout) alimente directement l'entrée (standin) du suivant. Chaque connexion est implantée par un tube anonyme.

Tubes nommés / names Pipes⚓︎

Le terme tube nommé 🇫🇷 / named pipe 🇬🇧 est une extension des tubes Unix et une des méthodes de communications inter-processus (IPC). Comme les tubes anonymes, les tubes/pipes nommés sont des zones de données organisées en FIFO, mais contrairement à ceux-ci, qui sont détruits lorsque le processus qui les a créés disparait, les tubes nommés sont liés au système d'exploitation et ils doivent être explicitement détruits (après destruction du processus qui les a créés). Ce type de mécanisme se retrouve bien sûr dans tous les systèmes d'exploitation de type Unix mais aussi dans les systèmes d'exploitation de Microsoft cependant leur sémantique est sensiblement différente.

via des Sockets⚓︎

Sockets Réseau⚓︎

Des données envoyées vers une interface réseau, vers un processus distinct sur le même ordinateur, ou vers un autre ordinateur du même réseau. Les données sont envoyées en suivant les protocoles TCP ou quelquefois UDP (etc..)

Sockets Unix⚓︎

Les Sockets (de domaine) Unix, ou Sockets Unix, sont semblables aux Sockets Réseau, à ceci près que toutes les communications ont lieu dans le noyeau/kernel. Les Sockets Unix utilisent le système de fichier comme leur Espace d'adressage. Les processus référencent une socket Unix comme une inode 🇬🇧 🇫🇷 / noeud d'index 🇫🇷 (structures de données sur les fichiers/répertoires Unix), et plusieurs processus peuvent communiquer avec une même socket.

IPC par Synchronisation⚓︎

La cohérence des données ou des ressources partagées entre les processus (lourds ou légers/threads) est maintenue par des mécanismes de synchronisation. Il en existe plusieurs :

  • Les Signaux
  • Les Verrous
  • Les Sémaphores

Les Signaux⚓︎

Définition⚓︎

Signal

Un Signal est un événement logiciel, produit par le (noyau du) Système d'Exploitation à destination d’un processus :

  • soit à la demande d’un autre processus (appel système kill)
  • soit en réponse à un événement interne au système (interruption matérielle, erreur logicielle, etc…)

Utilisation⚓︎

  • Il existe différents types de signaux (correspondant à des numéros).
  • Un programme peut associer une procédure/action à un signal (appels systèmes signal ou sigaction)
  • L’action associée par défaut à la majorité des signaux est l'arrêt du processus : par exemple (sur Linux) le signal SIGSEGV tue un processus qui effectue un accès à une zone de mémoire qu'il n'a pas allouée.
  • mais les actions peuvent autres : ignoré, bloque ou débloque le processus :
    • Le blocage d'un processus peut se faire en demandant l'attente de l'arrivée d'un signal
    • le déblocage consiste à envoyer un message au processus.
  • Les signaux peuvent également être utilisés pour communiquer entre plusieurs processus de manière asynchrone
    • SIGUSR1 et SIGUSR2 réservés aux applications (i.e. pas de sémantique préfédinie, jamais envoyés par le système lui même)
  • Ils peuvent notamment servir à la synchronisation
    • un processus attend (appel système sleep) qu’un autre processus lui envoie un signal pour poursuivre son exécution

Conflits & Sections Critiques⚓︎

  • Si les processus en accès simultanés sont tous en mode lecture/consultation, il n'y a pas de problème de synchronisation puisque la ressource partagée n'est pas modifiée.

  • Par contre, il peut y avoir un Problème de Synchronisation (Conflit), si un des processus impliqués dans l’accès en parallèle à la ressource partagée est en mode écriture/modification du contenu.

Conflits Possibles⚓︎

Quelle que soit la méthode utilisée pour échanger les données (fichiers ou mémoire principale), les accès de processus concurrents à des ressources partagées peuvent (usuellement, mais pas obligatoirement) mener aux comportements inattendus ou erronés suivants :

  • les données ne sont plus cohérentes
  • un ou plusieurs des processus concernés plantent
  • un ou plusieurs des processus est interrompu : il(s) doit(/doivent) attendre que la donnée commune soit libérée

En utilisant des fichiers, on tombe généralement sur le deuxième ou le troisième cas. Si on le prévoit, le processus peut attendre (10 millisecondes, 1 seconde, etc.) et reprendre plus tard l'accès aux données. Cela dit, cette solution n'est pas toujours possible en réseau, car les fichiers ne sont pas toujours libérés correctement.

En utilisant la mémoire principale, on tombe plutôt sur le premier cas. Si on le prévoit, le processus peut effectuer des synchronisations par lectures/écritures exclusives. Dans tous les cas, le partage de données en mémoire n'est possible que sur un seul et même ordinateur.

Concurrence SANS problème⚓︎

Concurrence AVEC problème⚓︎

Ressource Critique⚓︎

Ressource Critique

Une Ressource Critique 🇫🇷 ou Critic Ressource 🇬🇧 est une ressource partagée dont l'utilisation simultanée ne doit être faite que par UN SEUL PROCESSUS (/thread) à la fois, car sinon, des accès concurrents de plusieurs tâches (processus/threads) à cette ressource peuvent résulter en un état incohérent (même si chaque tâche, prise individuellement, se comporte correctement).

Section Critique⚓︎

En pratique, cela veut dire que certaines parties du code doivent être protégées contre les accès concurrents (càd qu'un seul processus doit pouvoir y accéder simultanément) : On appelle ces parties du code des Sections Critiques ou (quelquefois) Régions Critiques.

Section Critique

Une Section Critique 🇫🇷 / Critic Section 🇬🇧 est une portion de code manipulant une ressource critique.
Autrement dit, une Section Critique est une partie de code dont l'accès simultané ne doit être fait que par UN SEUL PROCESSUS (/thread) à la fois, car sinon, des accès concurrents de plusieurs tâches (processus/threads) à cette section de code (donc à ses ressources) peuvent résulter en un état incohérent (même si chaque tâche, prise individuellement, se comporte correctement).

Il est nécessaire d'utiliser des sections critiques lorsqu'il y a accès à des ressources partagées par plusieurs processus/threads. En pratique, on crée une section critique pour chaque ressource critique.

Opérations Atomiques & Sections Critiques⚓︎

Pte

Une section de code/opération/instruction est une atomique (comprendre indivisible) est une section/opération/instruction qui ne peut pas être interrompue :

  • soit elle commence, auquel cas elle est entièrement exécutée
  • soit elle n'est pas du tout exécutée

Intuitivement, une opération est atomique si son exécution peut être vue comme instantanée/prenant un temps nul.

Les Sections Critiques sont Atomiques

L'exécution d'une section critique ne peut/doit pas être interrompue au milieu par un autre processus : Les sections critiques sont atomiques.

Intuitivement, cela nous donne un indice pour déterminer les sections critiques:

  • si une partie du code n'était pas protégée (en section critique), son interruption au milieu de cette partie du code pourrait entraîner des incohérences.

Les instructions d'Assembleur sont atomiques

Les instructions de base en assembleur d'un processeur peuvent généralement être considérés comme des opérations atomiques

Instructions Atomiques en Assembleur

Les instructions Assembleur load, store, test sont considérées atomiques.
Si deux de ces instructions sont exécutées "simultanément", le résultat est équivalent à leur exécution séquentielle selon un ordre quelconque. Donc, si un load et un store sont exécutés simultanément, l'instruction load prendra soit l'ancienne valeur soit la nouvelle valeur, mais jamais une combinaison quelconque des deux

Danger

Par contre, des opérations qui peuvent sembler simples en termes de langages de haut niveau, comme par exemple x = x + 1, ou x = x -1 ne le sont pas. Comme le prouve l'exemple du compte bancaire précédent.

Exclusion Mutuelle / mutex⚓︎

Le problème des sections critiques nous montre qu'il faut être très prudent lorsque deux programmes utilisent le même espace mémoire (les mêmes variables). La section critique est précédée d'un code/protocole d'entrée, que nous noterons entrée_SC(), et suivi d'un code/protocole de sortie, noté sortie_SC(), qui ont pour but d'assurer la protection de la section critique. Ce code implante un algorithme ou une manière de gérer l'accès à la section critique. Ce code utilisera généralement quelques variables partagées par les divers processus et qui pourraient agir comme des verrous (passage autorisé/déverrouilé, ou passage défendu/verrouillé). Ces variables étant partagées, le code qui les utilise (code d'entrée et de sortie) devra être écrit avec beaucoup de soins, avec synchronisation, pour garantir en tout temps la consistance/cohérence de leurs valeurs.

Définition⚓︎

EXclusion MUTuelle

L'EXclusion MUTuelle 🇫🇷 / mutex 🇫🇷 🇬🇧 est un mécanisme (une primitive) de synchronisation qui garantit un unique accès simultané à des ressources partagées (en pratique une section critique, qui est atomique).

Il en existe plusieurs :

  • un verrou 🇫🇷 / lock 🇬🇧 est mutex 🇫🇷 🇬🇧 / un mécanisme \(=\) EXclusion MUTuelle, avec attente active : c'est une structure de données incluant une variable de verrouillage partagée binaire (verrouillé/non verrouillé)
  • un sémaphore, qui est une généralisation des verrous. Un sémaphore est aussi un mutex / un mécanisme d'EXclusion MUTuelle , mais avec attente passive.
  • etc.., d'autres primitives de programmation concurrente existent

Critères à Vérifier⚓︎

L'EXclusion MUTuelle doit, idéalement, vérifier les propriétés suivantes :

  • Exclusion (ou Pas d'interblocage) Deux tâches (processus/threads) ne doivent pas se trouver en même temps en Section Critique
  • Progression Une tâche doit pouvoir entrer en Section Critique si aucune autre ne s’y trouve
  • Équité Une tâche ne devrait pas attendre indéfiniment pour entrer en Section Critique.
    Autrement dit : Attente Bornée / Pas de Famine : il doit y avoir une borne (valeur limite) sur le nombre de fois que les autres processus sont autorisés à entrer dans leurs sections critiques avant qu'il n'obtienne finalement l'autorisation.
  • Tolérance aux Pannes Si la tâche en Section Critique est détruite ou se termine anormalement, il ne faut pas qu’il bloque tout le système
  • Symétrie Les protocoles d’Entrée et de Sortie en Section Critique doivent être identiques pour tous les processus et indépendants de leur nombre
  • L’exclusion mutuelle doit fonctionner dans un contexte multi-coeurs. On notera que les implémentations pratiques des mutex peuvent différer entre:
    • des architectures monoprocesseur
    • des architectures multiprocesseur

mutex par attente active vs passive⚓︎

Lorsqu'un processus/thread souhaite acquérir une ressource par Exclusion Mutuelle / mutex :

  • soit il arrive à l'acquérir,
  • soit il doit attendre pour pouvoir y arriver. Dans ce cas, le processus/thread doit attendre, et il peut patienter de deux manières différentes :
    • par attente active / verrou tournant 🇫🇷 /spinlock 🇬🇧 : Le processus exécute du code pendant qu'il patiente pour accéder à la section critique : le processus consomme du temps processeur pendant qu'il patiente.
    • par attente passive : Le processus n'exécute pas de code pendant qu'il patiente pour accéder à la section critique : le processus ne consomme pas du temps processeur pendant qu'il patiente

par attente active⚓︎

C'est le cas des Verrous :

  • Les processus se détectent en conflit d’exclusion mutuelle en utilisant des mécanismes matériels, en cas d’attente ils exécutent une boucle
  • Le processus consomme du temps processeur pendant qu'il patiente pour accéder à la section critique

par attente passive (blocage)⚓︎

C'est le cas des Sémaphores (et des moniteurs, etc..).

  • Libération du processeur en cas d’attente
  • Le processus ne consomme pas du temps processeur pendant qu'il patiente pour accéder à la section critique

Attente Active vs Attente Passive

Conclusion⚓︎

Les algorithmes par attente active:

  • présentent l'avantage d'être plus compréhensibles,
  • le désavantage de consommer du temps CPU : c'est pourquoi on s'en passe dès que possible.

Pour les algorithmes à attente passive :

  • Ils font gagner du temps d'exécution, car ils ne consomment pas de temps CPU.

En général, on préfère l'attente passive. Mais dans certains cas très particuliers, l'attente active peut être plus avantageuse, par exemple : * lorsque le changement de contexte est plus long que le temps d'attente moyen (contrainte temps réel souple) ou maximum (contrainte temps réel dur). Ce n'est en général le cas que dans les systèmes à multiprocesseurs.

Principe d'Entrée et Sortie d'une Section Critique⚓︎

Principe Général⚓︎

TANT QUE VRAI:
    Entrée_SC()          // Contrôle de l'Accès du Processus P
    Section_Critique()   // Utilisation de la Section Critique
    Sortie_SC()          // Libération de l'accès à la Section Critique

    En_dehors_de_SC()    // cette partie n'est pas protégée

Un Exemple⚓︎

variable globale compte                /* commun */
PROCÉDURE entrée_SC_compte():
    // à détailler
PROCÉDURE sortie_SC_compte():
    // à détailler

AFFICHER("ajout de 1000€")            /* tâche 1 */
entrée_SC_compte();
compte += 1000;
sortie_SC_compte();
AFFICHER("ajout effectué\n");

AFFICHER("retrait de 500€\n");        /* tâche 2 */
entrée_SC_compte();
compte -= 500;
sortie_SC_compte();
AFFICHER("retrait effectué\n");

ATTENTION : seule la lecture ou l’écriture d’une variable est atomique, entre deux instructions machines le processeur peut être alloué à un autre processus... Dans le code précédent, compte += 1000 à deux opérations atomiques (et nous avons vu qu'interrompre l'exécution entre ces deux lignes pouvait mener des données incohérentes):

  • lire variable compte : provisoire = compte
  • écrire dans compte la valeur compte + 1000: compte = provisoire + 1000

Implémentations entrée_SC()/sortie_SC() = Réalisation Logicielle de l'Exclusion Mutuelle⚓︎

Réaliser logiciellement l'Exclusion Mutuelle sans erreurs, càd implémenter logiciellement sans erreurs les procédures entrée_SC() et sortie_SC(), permet de garantir la gestion correcte des Entrées et Sorties de la Section Critique : C'est un problème sensible et important, contre-intuitif quelquefois. Ce n'est pas un problème trivial. Plusieurs solutions fausses ont été publiées.

Tout ce qui précède est donc basé sur la possiblité d'implémenter deux procédures :

  • entrée_SC() : Le protocole d'entrée dans la Section Critique (SC) est un ensemble d ’instructions qui permet de vérifier que la ressource est disponible et empêche une progression éventuelle. Autrement dit, ce protocole garantit qu'un seul processus puisse entrer dans la section critique.
  • sortie_SC() : Le protocole de sortie de la Section Critique est un ensemble d’instructions qui permet à un processus ayant terminé sa Section Critique d ’avertir d ’autres processus en attente que la voie est libre

Voici quelques idées, ⚠ dont certaines sont mauvaises ⚠, pour implémenter l'EXclusion MUTuelle grâce aux procédures entrée_SC() et sortie_SC()

Idée N°1 : Masquage d'Interruption⚓︎

Le Principe (Brutal)

  • Avant d'entrer dans une section critique, le processus masque les interruptions
  • Il les restaure à la fin de la section critique
  • Il ne peut être alors suspendu durant l'exécution de la section critique
Conclusion? Le Masquage des Interruptions : Bonne Idée ? ou Mauvaise idée?
  • SOLUTION DANGEREUSE, car le processus courant peut, pour diverses raisons, ne pas réactiver les interruptions
  • Conclusion : ⚠ cet algorithme n'assure PAS l'exclusion mutuelle ⚠

Idée N°2 : Verrouillage naïf avec un verrou⚓︎

Col

var v:Verrou
PROCÉDURE entrée_SC():
    Tant Que v ≠ 0:
        pass    # Attente Active
    v = 1

PROCÉDURE sortie_SC():
    v = 0

# Processus P0
entrée_SC()
section_critique()
sortie_SC()

En_Dehors_de_SC()

# Idem pour Processus P1

Algorithme de Verrouillage naïf avec un verrou

Le Principe

  • La variable de verrouillage partagée, le verrou v, est initialisée à 0
  • Pour entrer en section critique, un processus doit tester la valeur du verrou v. Si v est égal à 0, le processus modifie la valeur du verrou v à 1 et exécute sa section critique.
  • A la fin de la section critique, il remet le verrou v à 0. Sinon, il attend par une attente active que le verrou devienne égal à 0 : càd Tant Que v != 0
Conclusion? L'Algorithme de Verrouillage naïf : Bonne Idée ? ou Mauvaise idée?
  • Entre le moment où le processus lit le verrou v et le moment où il écrit dans le verrou (lecture et écriture étant deux opérations distinctes successives), un autre processus peut intervenir !
  • Conclusion : ⚠ cet algorithme n'assure PAS l'exclusion mutuelle ⚠

Idée N°3 : Alternance Stricte⚓︎

Col

Entier tour = 0

# Processus P0
Tant Que VRAI:
    # entrée_SC()
    Tant Que tour ≠ 0: # Attente Active
        pass    # ne fait rien

    section_critique()

    # sortie_SC()
    tour = 1

    En_dehors_de_SC()

Col

# Processus P1
Tant Que VRAI:
    # entrée_SC()
    Tant Que tour ≠ 1: # Attente Active
        pass    # ne fait rien

    section_critique()

    # sortie_SC()
    tour = 0

    En_dehors_de_SC()

Algorithme de l'Alternance Stricte

Le Principe

  • Chacun des deux processus ne peut entrer dans sa section critique que si la valeur de tour est égale à son numéro (0 ou 1)
  • Supposons que le processus P0 lise tour et constate que sa valeur est 0 ; il entre dans sa section critique
  • Si le processus P1 lit à son tour (valeur 0), il doit attendre dans une boucle le passage de tour à 1 (attente active)
  • Quand le processus P0 sort de sa section critique, il met tour à 1. Le processus P1 peut alors entrer dans sa section critique
  • quand il en sortira, il mettra tour à 0.
Conclusion ? L'Alternance Stricte : Bonne Idée ? ou Mauvaise idée?
  • Imaginons que le processus P0 s'arrête. Le processus P1 pourra entrer encore une fois dans sa section critique, mais il sera ensuite bloqué (violation de la condition 3).
  • Plus encore, on peut imaginer que le processus P1 boucle indéfiniment dans sa section non critique, le processus P0 finira également par être bloqué (violation de la règle 3)
  • Conclusion : ⚠ Cet algorithme n'assure PAS l'exécution mutuelle ⚠

Algorithme de Peterson, 1981⚓︎

Col

# Processus P0
# entrée_SC() :
veut_entrer0 = VRAI     # souvent noté flag0
tour = 1
Tant Que veut_entrer1 EST VRAI ET tour == 1:
    pass    # # Attente Active

section_critique()

# sortie_SC() :
veut_entrer0 = FAUX

Col

# Processus P1
# entrée_SC() :
veut_entrer1 = VRAI     # souvent noté flag1
tour = 0
Tant Que veut_entrer0 EST VRAI ET tour == 0:
    pass    # Attente Active

section_critique()

# sortie_SC() :
veut_entrer1 = FAUX

Algorithme de Peterson6, \(1981\)

Le Principe

  • Pour entrer dans sa section critique, le processus P0 (resp. P1) met d'abord flag0 (resp. flag1) à VRAI, et alors suppose que c'est au tour de l'autre processus d'entrer dans sa section critique en mettant tour à 1 (resp. 0).
  • Si les deux processus essaient d'entrer en même temps, les deux valeurs 0 et 1 seront assignées à tour presque en même temps.
  • L'opération d'assignation (de copie) d'une valeur à une variable (position mémoire) peut cependant être considérée comme une opération atomique. Donc, des deux valeurs assignées à tour, une seule va durer. La première valeur sera rapidement remplacée par la seconde. La dernière valeur de tour déterminera lequel des deux processus peut entrer dans sa section critique. Cependant, peu importe si la première ou la seconde valeur est 0 ou 1, l'algorithme assurera toujours l'exclusion mutuelle

Conclusion :

  • L'Algorithme de (Gary) Peterson (1981) EST un algorithme d'Exclusion MUTuelle
  • L'Algorithme de Peterson prévient les Interblocages : en effet, le seul endroit où un processus peut être bloqué est dans la boucle Tant Que. Il ne peut donc pas y avoir d'interblocage (c'est-à-dire que les deux processus se bloquent mutuellement) car les deux ne peuvent être bloqués simultanément dans la boucle Tant Que. En effet, selon la valeur de tour, un processus sera forcément libéré.
  • L'Algorithme de Peterson prévient les Famines : Chaque Processus a la garantie d'entrer en Section Crtitique en un temps fini (au plus un tour)

Réalisation Matérielle de l'EXclusion MUTuelle⚓︎

La fonction test_and_set du Langage machine⚓︎

Pour réaliser une exclusion mutuelle, on peut aussi utiliser l'instruction test_and_set du langage machine, considérée comme une solution matérielle : cette fonction consulte et modifie une variable de manière atomique :

  • Si la variable vaut 1, alors elle renvoie 1
  • Si la variable vaut 0, alors elle la met à 1 et renvoie 0

Autrement dit, cette fonction équivaut à :

var v: Verrou
FONCTION test_and_set(v: Verrou)
    var ancienne_valeur = v.libre
    v.libre = VRAI
    RENVOYER ancienne_valeur

Implémentation Matérielle de l'Exclusion Mutuelle avec un Verrou⚓︎

var v: Verrou
PROCÉDURE entrée_SC(v: Verrou)
    Tant Que test_and_set(v: Verrou) EST VRAI
        pass                # Attente Active

PROCÉDURE sortie_SC(v: Verrou)
    v.libre = FAUX

entrée_SC()
section_critique()
sortie_SC()

Problèmes en cas de Mauvaise Gestion de l'Exclusion Mutuelle / Sections Critiques⚓︎

Les problèmes en cas de mauvaise gestion des sections critiques :

  • Si l'exclusion mutuelle n'est pas respectée, alors Situation de Compétition 🇫🇷 / Race condition 🇬🇧 :
    Deux processus/threads sont dans une section critique en même temps : non déterminisme (bug, plantage, exploitation...)
  • Si la progression n'est pas respectée, alors Interblocage 🇫🇷 / Deadlock :
    Le processus est bloqué.
  • Si l'attente bornée n'est pas respectée, alors Famine 🇫🇷 / Starvation 🇬🇧 :
    Un processus/thread ne voit jamais sa demande aboutir

Remarques⚓︎

  • Certaines opérations sur la ressource critique ne nécessitent pas forcément d’exclusion mutuelle.
    • exemple : lecture de la valeur du compte (si on accepte que la valeur lue devienne rapidement invalide…)
  • Le mécanisme d’exclusion mutuelle n’est pas une protection, mais une convention entre les processus souhaitant utiliser la ressource sans la corrompre.
    • il est toujours possible de manipuler la ressource sans « prendre le jeton »

Les sections critiques sont un mal nécessaire:

  • un mal, parce qu’elles empêchent le parallélisme qu’on a tant de mal à mettre en place… elles réduisent donc les performances.
  • nécessaire, parce qu’elles garantissent l’intégrité des ressources critiques

Conséquence : les éviter lorsqu’on le peut (e.g. en concevant des structures de données toujours cohérentes)

Les Verrous⚓︎

Définition⚓︎

Un verrou 🇫🇷 est un mutex 🇫🇷 🇬🇧 / un mécanisme d’EXclusion MUTuelle, par attente active, qui permet de bloquer tout ou une partie d'un programme (la section critique). Plus précisément :

Verrou

Un Verrou 🇫🇷 / Lock 🇬🇧 est une structure de données partagée du Système d'Expoitation composée de :

  • une variable libre, de type booléen, qui représente son état :
    • verrouillé (v.libre = FAUX) ou
    • non verrouillé (v.libre = VRAI)
  • d'une File d'attente v.file_attente: la liste de tâches usuellement gérée en FIFO - First In First Out

Les blocages peuvent être réalisés soit pour les opérations de lecture, soit d'écriture, soit pour les deux.

Réalisation d'un Verrou⚓︎

En supposant que l'on sache programmer un mutex, càd garantir l'accès simultané unique d'un processus à une ressource, voici comment on peut réaliser un verrou en pratique. Un verrou est associé à deux opérations (principalement) :

  • verrouiller / lock pour verrouiller le verrou
  • déverrouiller / unlock pour le déverrouiller et
  • quelquefois, trylock équivalent à lock , mais qui en cas d’échec ne bloque pas le processus.

Pour un verrou donné, les deux procédures suivantes doivent s'exécuter en exclusion mutuelle (par ex. en masquant les interruptions).

Une tentative naïve⚓︎

Col

var v: Verrou
PROCÉDURE Verrouiller(v:Verrou): # Prendre la ressource
    SI v.libre = FAUX ALORS
        Soit P le processus appelant
        Ajouter P dans (la queue de) v.file_attente
        Suspendre le processus P
    SINON
        v.libre = FAUX
    FINSI

Col

var v: Verrou
PROCÉDURE Déverrouiller(v:Verrou): # Libérer la ressource
    SI v.file_attente EST VIDE ALORS
        v.libre = VRAI
    SINON
        v.libre = FAUX
        Sortir un Processus Q de (la tête de) v.file_attente
        réveiller le processus Q
    FIN_SI

Cette définition peut poser des problèmes :

  • Verrouiller() est elle-même une section critique
  • Déverrouiller() doit être ininterruptible :
    • sinon incohérence si elle est interrompue entre le SI et le SINON
    • cette incohérence est passagère, car le système redevient cohérent dès qu'un nouveau processus verrouille

La même idée, avec des Sections Critiques⚓︎

Col

var v: Verrou
PROCÉDURE Verrouiller(v:Verrou): # Prendre la ressource
    # entrée_SC() # par ex. masquer les interruptions
    SI v.libre = FAUX ALORS
        Soit P le processus appelant
        Ajouter P dans (la queue de) v.file_attente
        Suspendre le processus P
    SINON
        v.libre = FAUX
    FINSI
    # sortie_SC()

Col

var v: Verrou
PROCÉDURE Déverrouiller(v:Verrou): # Libérer la ressource
    # entrée_SC() # par ex. masquer les interruptions
    SI v.file_attente EST VIDE ALORS
        v.libre = VRAI
    SINON
        v.libre = FAUX
        Sortir un Processus Q de (la tête de) v.file_attente
        réveiller le processus Q
    FIN_SI
    # sortie_SC()

Utilisation de l'EXclusion Mutuelle avec les Verrous⚓︎

Ensuite, il suffira d'utiliser le verrou comme ceci classiquement : 

# Exclusion Mutuelle avec des Verrous
var v: Verrou
init(v)         # Une seule fois
verrouiller(v:Verrou)
section_critique()
déverrouiller(v:Verrou)

Problèmes Possibles avec des Verrous⚓︎

Verrous & Sections Critiques⚓︎

Un verrou est lui-même une Section Critique.. ce qui pose des problèems de définition circulaire.. : on ne peut pas utiliser de verrou pour implémenter un verrou (càd pour implémenter les procédures verrouiller et déverrouiller() ..) Une solution serait d'utiliser des appels systèmes pour masquer les interruptions.

Interblocage⚓︎

Les Verrous peuvent mener à l'interblocage !! Par exemple :

Col

var v0: Verrou
var v1: Verrou
init(v0: Verrou)
init(v1: Verrou)

PROCÉDURE P0(v0, v1)
(1)   verrouiller(v0)
(2)   verrouiller(v1)
(3)   section_critique()
(4)   déverrouiller(v1)
(5)   déverrouiller(v0)

Col

PROCÉDURE P1(v0, v1)
(A)   verrouiller(v1)
(B)   verrouiller(v0)
(C)   section_critique()
(D)   déverrouiller(v0)
(E)   déverrouiller(v1)

Il y a interblocage pour la séquence (1) \(\rightarrow\) (A) \(\rightarrow\) (2) \(\rightarrow\) (B)

Les Sémaphores⚓︎

Les solutions au problème de la section critique présentées jusqu'ici sont difficiles à généraliser pour des problèmes plus complexes. Nous présentons maintenant un mécanisme de synchronisation plus intéressant: les sémaphores.

Définition⚓︎

Un Sémaphore 🇫🇷 est un mutex 🇫🇷 🇬🇧 / un mécanisme d’EXclusion MUTuelle, par attente passive, qui permet de bloquer tout ou une partie d'un programme (la section critique). Plutôt que des solutions avec attente active (ce qui reste possible), on implémente usuellement les sémaphores avec attente passive, en utilisant des appels systèmes pour demander au noyau de :

  • mettre en sommeil un processus (SLEEP(processus)) (jusqu'à son réveil par un autre processus)
  • réveiller le processus ( WAKEUP(processus) )

Le système désactive toutes les interruptions pendant un très court laps de temps durant lequel il teste le sémaphore, l’actualise et place si nécessaire le processus en sommeil.

Plus précisément :

Def

Un Sémaphore (défini par Edsger Dijkstra en 1965) est un mécanisme plus général. C'est une structure de données composée de :

  • Un compteur d'accès (qu'on notera s.n, POO), donc une variable entière, qui tient les comptes du nombre de places ENCORE DISPONIBLES pour l'accès simultané de processus souhaitant accéder à la ressource. Cette variable est initialisée au nombre maximal d'accès possible pour la ressource. Cette variable n'est accédée que par les deux fonctions P et V suivantes.
  • Une fonction P(s) Proberen 🇳🇱 (hollandais), quelquefois appelée acquire() (en Python ) / wait() ou down() ce qui signifie Puis-je? / Essayer de / Tenter de 🇫🇷 (d'acquérir d'où le acquire), qui demande une ressource/processus, càd qui teste/essaye la positivité du compteur s.n (s'il reste des places), et le décrémente en une seule opération atomique. Si le compteur s.n est nul (ou <=0)) le processus est bloqué (il attend : d'où le nom wait). 
    var s: Sémaphore
PROCÉDURE P(s) / wait(s)
    Tant Que s.n≤0:        # Attente Active
        pass                # ne fait rien
    s.n = s.n - 1
    Cette procédure sera donc la candidate idéale pour entrée_SC()
  • Une fonction V(s) Verhogen 🇳🇱 (hollandais), quelquefois appelée release() (en Python ) / signal() ou up() ou post() ou Vas-y! 🇫🇷, qui incrémente le compteur s.n et débloque/relâche (d'où le release) l'une des resssources ou processus bloqués en file d'attente s.file_attente (il signale que ce processus est débloqué). 
    PROCÉDURE V(s) / signal(s) / post(s)
    s.n = s.n + 1
    Cette procédure sera donc la candidate idéale pour sortie_SC()
  • une File d'attente (qu'on notera s.file_attente) des processus bloqués (qui souhaitent accéder à la ressource), usuellement gérée en mode FIFO - First In First Out

Hein, quoi ? par attente active ? Mais on n'a pas dit que.. \(\rightarrow\) Si .. Si.. nous avons dit que c'était "possible" (bien que ce ne soit pas l'implémentation préférée)
Cette implémentation par attente active est seulement donnée pour la définition, en raison de sa simplicité de compréhension, mais usuellement, on préfère implémenter les sémaphores par attente passive :

Un sémaphore n'est pas associé à un type particulier de ressource.
Un sémaphore permet de limiter l'accès concurrent à une section critique à un certain nombre de processus.

un Verrou est un cas particulier de Sémaphore

Un verrou/mutex peut être vu comme un sémaphore binaire (sémaphore ne pouvant qu'avoir la valeur \(0\) ou \(1\), càd un sémaphore initialisé à \(1\)).

Réalisation d'un Sémaphore⚓︎

Une tentative naïve⚓︎

Implémentation Simple, par attente passive

var s: Sémaphore
PROCÉDURE P(s) / wait(s)
    SI s.n = 0 ALORS
        bloquer_processus_courant_en_queue(s.file_attente)
    SINON
        s.n = s.n -1
    FINSI

PROCÉDURE V(s) / signal(s) / post(s)
    s.n = s.n + 1
    SI s.file_attente EST NON VIDE ALORS
        Débloquer_le_processus_en_tête(s.file_attente)
        s.n = s.n - 1
    FINSI

Il existe le même risque de définition circulaire que pour les verrous : Le problème (encore une fois) ici, c'est que les primitives P(s) / wait() et V(s) / signal() sont elles-mêmes des sections critiques pour le Sémaphore lui-même... Pour résoudre cela, il faut donc protéger les accès à certaines parties des codes de wait() et signal() :

La même idée, avec des Sections Critiques⚓︎

var s: Sémaphore
PROCÉDURE P(s) / wait(s)
    entrée_SC()
    SI s.n = 0 ALORS
        sortie_SC()
        bloquer_processus_courant_en_queue(s.file_attente)
    SINON
        s.n = s.n -1
        sortie_SC()
    FINSI

PROCÉDURE V(s) / signal(s) / post(s)
    entrée_SC()
    s.n = s.n + 1
    SI s.file_attente EST NON VIDE ALORS
        Débloquer_le_processus_en_tête(s.file_attente)
        s.n = s.n - 1
    FINSI
    sortie_SC()

Utilisation de l'EXclusion MUTuelle avec les Sémaphores⚓︎

On suppose dans ce paragraphe que :

  • Le type Sémaphore existe déjà
  • les fonctions P(s) / acquire() / wait() / entrée_SC() et V(s) / release() / post() / sortie_SC() sont déjà implémentées.

La question est ici de savoir: Comment utiliser/implémenter l'Exclusion Mutuelle, avec des sémaphores, pour programmer deux processus concurrents ?

Ensuite, il suffira d'utiliser le verrou comme ceci classiquement : 

# Exclusion Mutuelle avec des Verrous
var s: Sémaphore
init(s, x)                  # Initialise le compteur du sémaphore à x : une seule fois
entrée_SC(s:Sémaphore)      # P(s) / wait(s) : acquérir le sémaphore
section_critique()
sortie_SC(s:Sémaphore)      # V(s)  / post(s) : relâcher le sémaphore

Exp

# La variable s est passée par référence
Entier: compte                       /* commun */
var s: Sémaphore
état = init(s, 1);                   # initialisé à un seul accès simultané

AFFICHER("ajout de 1000€");           /* tâche 1 */
état = wait(s);
compte += 1000;
état = post(s);
AFFICHER("ajout effectué");

AFFICHER("retrait de 500€");          /* tâche 2 */
état = wait(s);
compte -= 500;
état = post(s);
AFFICHER("retrait effectué");

Problèmes Possibles avec des Sémaphores⚓︎

Interblocages⚓︎

Les Sémaphores peuvent mener à l'interblocage!! par exemple :

Col

var s0: Sémaphore
var s1: Sémaphore

init(s1,1)
init(s2,1)

PROCÉDURE P0(s0,s1)
    entrée_SC(s0)
    entrée_SC(s1)
    section_critique()
    sortie_SC(s1)
    sortie_SC(s0)

Col

PROCÉDURE P1(s0,s1)
    entrée_SC(s1)
    entrée_SC(s0)
    section_critique()
    sortie_SC(s0)
    sortie_SC(s1)

Références & Notes⚓︎

  1. Virtual Memory, Wikipedia, Mémoire Virtuelle, Wikipedia ↩

  2. Memory Paging, Wikipedia, Pagination mémoire Virtuelle, wikipedia ↩

  3. Table des Pages, Wikipedia 🇬🇧, Table des pages, Wikipedia 🇫🇷 ↩

  4. Sémaphores et Variables de Condition, Michael RAO, ENS Lyon ↩

  5. Parallélisme, Introduction aux conditions variables  ↩

  6. La Programmation Concurrente, Gabriel Girard, Univ Sherbrook, 🇨🇦, p14 ↩

  7. Processus Concurrents et Parallélisme, Communication Inter Processus, Univ Usherbrook, CA 🇨🇦 ↩

  8. Systèmes d'Exploitation, Amine DHRAIEF, ESEN, Univ Manouba,  ↩

  9. Cours Synchronisation des Processus, N. Hameurlain, Univ Pau, 🇫🇷 ↩

  10. Communication Interprocessus, Pierre antoine Champin, LIRIS, CNRS, 🇫🇷 ↩

  11. Cours Synchronisation, Pierre antoine Champin, LIRIS, CNRS, 🇫🇷 ↩

  12. Cours Contrôle de Concurrence en mémoire commune. Mécanismes primitifs d'Exclusion mutuelle ↩

  13. Systèmes d'Exploitation : Processus, Interruptions, Ordonnancement. Benjamin MONMÈGE, Univ Aix-Marseille ↩

  14. Systèmes d'Exploitation, Benjamin MONMÈGE, Univ Aix-Marseille ↩

  15. Synchronisation des Processus Concurrents: mutex, Michael RAO, ENS Lyon ↩

  16. DU ISN, Systèmes, Vania Marangozova-Martin, Maîtresse de Conférence Univ Grenbole Alpes ↩

  17. Notes de cours sur Théorie et pratique de la Concurrence, François Laroussinie, LIAFA,Univ Jussieu Paris 7 ↩