Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Cours « système d’exploitation » 2ème année IUT de Caen, Département d’Informat

Cours « système d’exploitation » 2ème année IUT de Caen, Département d’Informatique (François Bourdon) Cours Système d’Exploitation − IUT de Caen François Bourdon Chapitre 3 Synchronisation de Processus (partie−2) Cours Système d’Exploitation − IUT de Caen François Bourdon Plan 1.Système de Gestion des Fichiers : Concepts avancés 2.Création et ordonnancement de Processus 3.Synchronisation de Processus 3.1 Expression de la notion de processus 3.2 Modèles de représentation des processus Processus séquentiels Systèmes de tâches et graphes de précédence Automates finis Réseaux de Pétri Exemples de mise en oeuvre sur UNIX 3.3 Interactions de processus Déterminisme d’un système de tâches Blocage dans un système de tâches 3.4 Synchronisation de processus Section critique Désarmement des interruptions Instruction Test−and−Set Les sémaphores Les moniteurs de Hoare 3.5 Problèmes classiques de synchronisation Producteurs/consommateurs Lecteurs/rédacteurs Le problème des philosophes [Dikkstra 65] 4.Communication entre Processus : les Signaux 5.Echange de données entre Processus 6.Communication entre Processus : les IPC Cours Système d’Exploitation − IUT de Caen François Bourdon 3.3 Interactions de processus Des processus qui agissent en parallèle peuvent coopérer (partage d’information ou accélération d’un calcul), ou être en compétition les uns par rapport aux autres pour acquérir des ressources, quand elles sont en quantité insuffisante. La base de l’interaction est la communication. Dans les systèmes centralisés, les processus communiquent par l’intermédiaire de variables et d’objets partagés. Dans les systèmes répartis, où il n’existe pas de mémoire commune, les communications se font par messages et peuvent ne pas être instantanées. Des interactions mal contrôlées peuvent être la cause d’un mauvais fonctionnement du système et d’une utilisation impropre des ressources. Pour cela on peut regarder deux problèmes : Déterminisme et blocage. Cours Système d’Exploitation − IUT de Caen François Bourdon Déterminisme d’un système de tâches Définition : C’est l’étude de la possibilité de décider si un système de tâches donné, fournit pour chacun de ses composants, la même suite de résultats. Soit, par exemple, deux processus qui accèdent sans contrôle à une même cellule mémoire M, contenant la valeur 10, le premier pour y ajouter 5, le deuxième pour doubler la valeur contenue dans M. Suivant l’ordre d’accès à M des deux processus, on obtient comme valeur finale soit : (10 + 5) * 2 = 30, soit : (10 * 2) + 5 = 25. Cours Système d’Exploitation − IUT de Caen François Bourdon Ce problème est inhérent aux systèmes multi− programmés, puisque les processus peuvent être mis en attente à des instants quelconques, pour des durées qui dépendent de paramètres extérieurs. Lorsque l’on sait résoudre ce problème (notion d’interférence), on peut envisager de transformer un processus séquentiel (une chaîne de tâches) en un système équivalent, où certaines tâches sont exécutées en parallèle (parallélisme maximal). Cours Système d’Exploitation − IUT de Caen François Bourdon Blocage dans un système de tâches Définition : Un blocage se produit lorsqu’un ensemble de processus est tel que chacun d’eux tient au moins une ressource et est en attente, pour poursuivre sa progression, d’une ressource tenue par l’un des autres processus. Pour traiter ce problème on a le choix entre trois types de techniques : prévention, détection, évitement. Cours Système d’Exploitation − IUT de Caen François Bourdon Les techniques de prévention : Garantir que les situations de blocage ne puissent pas se produire, en utilisant des contraintes très fortes. Les techniques de détection : Laisser le blocage se produire, puis après l’avoir détecté, reprendre les ressources de certains processus pour les redistribuer à d’autres, qui peuvent ainsi poursuivre leur exécution. Les techniques d’évitement : En contrôlant pas à pas la progression des processus, faire en sorte qu’à chaque étape d’attribution de ressources, il reste une possibilité au système d’échapper à un blocage. Cours Système d’Exploitation − IUT de Caen François Bourdon 3.4 Synchronisation de processus Nous avons vu qu’en définissant une relation de précédence sur un ensemble de tâches, on obtient un système de tâches satisfaisant les contraintes imposées en terme de production/consommation de ressources, mais aussi en terme de parallélisation maximale des tâches. Problème : Dans certains cas cette approche est insuffisante. Il se peut que plusieurs comportements (mots du langage) soient valides par rapport au graphe de précédence produit pour une situation donnée, alors que certains d’entre eux ne donnent pas le même résultat. Exemple : La réservation de place de spectacle. Cours Système d’Exploitation − IUT de Caen François Bourdon #define MAX 20 int res = 0; /* nb de places réservées */ void reserver (int dem) { if ( res + dem <= MAX) res += dem ; else ... /* erreur */ ; } si l’on a 2 processus P1 P2 res 11 res 11 7 OK! if (res + dem) <= MAX si l’ordonnanceur donne la 5 main à P2 if (res + dem) <= MAX OK! res += dem res += dem bug ! Cours Système d’Exploitation − IUT de Caen François Bourdon 16 = 11 + 5 23 = 16 + 7 On s’aperçoit qu’éliminer les cas divergeant revient à rendre indivisible (atomique) la séquence de plusieurs tâches dans le graphe de précédence. Les solutions mises en oeuvre ont en commun le fait qu’elles ajoutent toujours de nouvelles tâches au graphe de précédence initial. La section critique Définition : La section critique d’un programme donné, est une suite d’instructions de ce programme dont l’exécution est gérée en exclusion mutuelle. Un processus parmi ceux qui s’exécutent en parallèle ne peut entrer en section critique si l’un des autres s’y trouve déjà. Cours Système d’Exploitation − IUT de Caen François Bourdon Intuitivement, un processus attend dans la section d’entrée qu’une certaine condition soit satisfaite pour entrer en section critique et signale sa sortie dans la section de sortie. répeter <section restante> <section d’entrée> <section critique> <section de sortie> jusqu’à faux; Si dans certains systèmes il existe des dispositifs implantés au niveau matériel, qui assurent l’indivisibilité des instructions élémentaires, ce n’est pas le cas partout et surtout pas dans les systèmes répartis. Cours Système d’Exploitation − IUT de Caen François Bourdon Il existe des solutions logicielles (utilisation de variables partagées) pour pallier à ces manques matériel, par exemple : Soit deux processus P1 et P2 qui partagent une variable commune nommée Tour, qui peut prendre les valeurs 1 ou 2. La section d’entrée consiste à consulter la valeur de Tour. L’exécution de la section critique de Pi n’est autorisée que si Tour a la valeur i. Lorsque la section critique est terminée, le processus exécute sa section de sortie en affectant à Tour le numéro de l’autre processus, permettant à celui−ci d’entrer dans sa propre section critique. P1 P2 section−entrée ret := Tour ; ret := Tour ; si (ret == 1) { si (ret == 2) { section−critique ............... ; .............. ; ............... ; .............. ; ............... ; .............. ; section−sortie Tour = 2 ; Tour = 1 ; } } Cours Système d’Exploitation − IUT de Caen François Bourdon Tour Cette solution a des inconvénients en particulier si l’un des processus s’arrête définitivement, alors que la variable Tour n’a pas été changée. Pour cela on impose une condition supplémentaire, appelée condition de progression : Définition : un processus bloqué en section restante ne peut pas empêcher un autre processus d’entrer en section critique. D’autres algorithmes mettent en évidence que le problème de la section critique n’est pas simple à résoudre, surtout quand des conditions supplémentaires s’y greffent, comme la progression et l’absence de blocage. Cours Système d’Exploitation − IUT de Caen François Bourdon Une dernière condition, appelée attente bornée, permet d’assurer une certaine équité entre les processus : Définition : Lorsqu’un processus est en attente de sa section critique, il existe une borne supérieure au nombre de fois où d’autres processus exécutent leur section critique. Cette condition interdit à certains processus d’exécuter itérativement leur section critique, en laissant un processus attendre, pendant une durée arbitrairement longue, l’entrée dans sa propre section critique. Cours Système d’Exploitation − IUT de Caen François Bourdon Certains algorithmes comme celui de Peterson respectent ces quatres conditions : exclusion mutuelle, absence de blocage, progression, attente bornée. Il existe des solutions qui utilisent des dispositifs matériels particuliers pour résoudre le problème de la section critique. Ces solutions sont utilisées dans la pratique sur systèmes monoprocesseurs centralisés. Cours Système d’Exploitation − IUT de Caen François Bourdon Désarmement des interruptions On désarme les interruptions pendant toute la durée de la section critique et on les réarme en sortie de la section critique. L’unité centrale reste allouée à ce processus jusqu’à la fin de sa section critique, ce qui garantit l’exclusion mutuelle. Le problème c’est qu’il peut bloquer un processus prioritaire, d’où la difficulté de mettre cette possibilité dans les mains des utilisateurs. Cours Système d’Exploitation − IUT de Caen François Bourdon Instruction Test−and−Set De nombreux ordinateurs disposent d’une instruction élémentaire (Test−and−Set, TS ou TAS) exécutée par le matériel, qui permet de lire et d’écrire le contenu d’un mot de la mémoire de manière indivisible. procédure TS ( var a, b: entier) ; début a := b ; b := 1 ; fin; Cette instruction a uploads/Industriel/ synchronisation-de-processus-partie-2.pdf