Chapitre 2 -- gestion des processus PDF

Licence info, FST de Fès Pr. M. Talibi Alaoui LST Info, FSTF 2018-2019 1  Introduction  Processus  Appels système  Ordonnancement des processus  Communication et synchronisation des processus  Gestion des processus sous Unix  Les s...

Licence info, FST de Fès Pr. M. Talibi Alaoui LST Info, FSTF 2018-2019 1  Introduction  Processus  Appels système  Ordonnancement des processus  Communication et synchronisation des processus  Gestion des processus sous Unix  Les signaux LST Info, FSTF 2018-2019 2  Lesordinateurs mono processeur actuels sont capables d’exécuter plusieurs programmes « simultanément ».  Multiprogrammation, multi-tâches ou encore pseudo- parallélisme.  En réalité ce n’est pas vrai, une machine mono processeur ne peut exécuter qu’une seule tâche à un instant donné.  Le processeur est affecté, périodiquement, à chaque programme en cours d’exécution pour une durée infiniment petite  donne l’impression d’exécuter tous les programmes en même temps. LST Info, FSTF 2018-2019 3  Un processus est un programme en exécution qui a son propre environnement  Espace d’adressage  Code (instructions du programme)  Pile  Compteur ordinal  Registres  Variables  …  Un programme peut être exécuté par plusieurs processus. LST Info, FSTF 2018-2019 4 Les systèmes d’exploitation ont besoin de savoir que tous les processus nécessaires existent bel et bien : - Pour les systèmes les plus simples, - ou ceux conçus pour exécuter une seule application (par exemple le contrôleur d’un four à micro-ondes), Il est envisageable que tous les processus susceptibles d’intervenir soient actifs pendant le fonctionnement du système LST Info, FSTF 2018-2019 5 Le microprocesseur et le microcontrôleur :  Sont les puces électroniques programmables typiques qui sont utilisées à des fins différentes. La différence significative entre eux est :  qu'un microprocesseur est un moteur Informatique programmable composé d'ALU, CU et de registres, couramment utilisé comme unité de traitement qui peut effectuer des calculs et prendre des décisions.  Comme le CPU dans les ordinateurs Le microprocesseur et le microcontrôleur : En revanche, un microcontrôleur est :  unmicroprocesseur spécialisé considéré comme un "ordinateur sur puce" car il intègre des composants tels que microprocesseur, mémoire et E / S numériques parallèles. En général, les systèmes généralistes ont besoin de disposer d’une méthode pour créer et arrêter les processus, selon le cas, au cours de leur activité. LST Info, FSTF 2018-2019 8  Création des processus  Quatre événements sont à l’origine de la création d’un processus.  Initialisation du système.  Exécution d’un appel système de création de processus par un processus en cours d’exécution.  Requête utilisateur sollicitant la création d’un nouveau processus.  Initiation d’un travail en traitement par lot. LST Info, FSTF 2018-2019 9  Lors de l’amorçage (déclenchement) du système d’exploitation, plusieurs processus sont crées, à savoir :  Certains sont des processus de premier plan : des processus qui interagissent avec l’utilisateur et accomplissent des taches pour eux.  D’autres sont des processus d’arrière plan, non associé à une utilisation particulière de l’ordinateur. LST Info, FSTF 2018-2019 10  Ces processus ont des fonctions spécifiques.  On peut trouver par exemple un processus d’arrière plan conçu pour accepter les courriers électroniques entrants; celui-ci sera inactif la plupart du temps, mais se réactivera lors de l’arrivée d’un message.  Les processus qui restent à l’arrière plan pour gérer des activités qui concernent les courriers électroniques, les pages web, les news, les impressions, etc. s’appellent des démons (daemons). LST Info, FSTF 2018-2019 11  Sur les gros systèmes, on en trouve généralement des dizaines des processus.  Sous UNIX, la commande ps sert à afficher la liste des processus en cours d’exécution.  Sous windows 95/98/Me, le fait de taper Ctrl+Alt+Del une seule fois permet de voir les processus en cours.  Sous Windows 2000/XP, c’est le gestionnaire des taches qui intervient. LST Info, FSTF 2018-2019 12  Au-delà des processus crées lors de l’amorçage, de nouveaux processus peuvent être crées.  Il arrive souvent qu’un processus en cours d’exécution émettent des appels système pour créer un ou plusieurs nouveaux processus qui l’aideront dans son activité.  Il est particulièrement utile de créer de nouveaux processus lorsque la tache à accomplir peut être divisée en plusieurs processus, qui interagissent entre eux tout en étant indépendants. LST Info, FSTF 2018-2019 13  Par exemple, si l’on récupère d’importantes quantités de données sur un réseau afin de les traiter ultérieurement, il peut être pratique :  de créer un processus pour récupérer les données et les placer dans un tampon partagé,  tandis qu’un autre processus ôtera (enlever) les éléments de données et les traitera. LST Info, FSTF 2018-2019 14  Sur un ordinateur multiprocesseur, le fait que chaque processus puisse s’exécuter sur un processeur différent peut également en accélérer l’exécution.  Sur les systèmes interactifs, les utilisateurs peuvent démarrer un programme en saisissant une commande ou en cliquant sur une icône.  L’une ou l’autre de ces actions lance un nouveau processus qui exécute le programme concerné. LST Info, FSTF 2018-2019 15  Le dernier cas de figure impliquant la création de processus : ne s’applique qu’aux systèmes de traitement par lots que l’on trouve sur les gros mainframes.  En informatique, un traitement par lots (batch processing en anglais) est un enchaînement automatique d'une suite de commandes (processus) sur un ordinateur sans intervention d'un opérateur. LST Info, FSTF 2018-2019 16  Un Mainframe est un ordinateur :  Il renferme énormément de mémoire RAM (20 Go est très courant *),  une puissance (64 processeurs à plusieurs centaines de mégahertz ) de traitement très importante.  Pour le stockage de masse (les disques durs) :  Le mainframe fait le plus souvent appel à d’autres machines physiques (souvent conçues spécialement pour ce même mainframe) qui gère les disques.  La capacité de ceux ci peut avoisiner plusieurs dizaines de Tera Octets de données.  Typiquement, les données sont transmises sur un réseau FDDI (fibre optique) entre le Mainframe et le stockage.  Dans ce cas, lorsque le système d’exploitation constate qu’il dispose des ressources nécessaires à l’exécution d’un job supplémentaire, il crée un nouveau processus et exécute le job suivant la file d’attente. LST Info, FSTF 2018-2019 19 Création des processus :  La création d’un processus se traduit toujours par un appel système déclenché à partir de :  Processus utilisateur OU  Processus système, OU  Processus gestionnaire de traitements par lots. Cet appel demande au système d’exploitation de créer un nouveau processus et indique, directement ou indirectement, quel programme y exécuter.  Sous Unix : fork() crée un clone du processus appelant  Sous Win32 : Create_Process. LST Info, FSTF 2018-2019 20  Dans les deux cas, une fois qu’un processus a été crée, le parent et le fils disposent désormais de leur propre espace d’adressage.  S’il arrive que l’un des processus modifie un mot dans son espace d’adressage, le changement n’est pas visible par l’autre processus. LST Info, FSTF 2018-2019 21  Fin d’un processus :  Une fois qu’un processus a été créé, il commence à s’exécuter, quelle que soit sa tache.  Mais tôt ou tard, le nouveau processus s’arrete pour diverses raisons : LST Info, FSTF 2018-2019 22  Fin d’un processus  Arrêt normal (volontaire)  Exécution de toutes les instructions du programme correspondant.  Arrêt à cause d’une erreur fatale  Erreur imprévisible (division par 0)  Par exemple, saisir la commande gcc foo.c Pour compiler le programme foo.c et que le fichier correspondant n’existe pas, le compilateur s’arrete. En général, les processus interactifs prenant en charge des Interfaces visuelles ne s’interrompent pas si on leur fournit de mauvais paramètres. LST Info, FSTF 2018-2019 23  Un autre motif d’arret d’un processus : Intervient lorsqu’il exécute un appel système indiquant au SE d’arreter un ou plusieurs autres processus. Sous UNIX, cet appel est kill. LST Info, FSTF 2018-2019 24  Hiérarchie des processus  Chaque processus a un et un seul processus parent  Sous Unix le processus « init » est le seul qui n’a pas de parent  C’est le processus qui initialise le système  Un processus peut avoir des processus fils 0,1,2 ou plus.  Sous Unix, il est possible d’envoyer des signaux à toute une arborescence de processus  Demande d’arrêt par exemple  Le principe de l’hiérarchie n’existe pas sous Windows  Tous les processus sont égaux LST Info, FSTF 2018-2019 25  Etats des processus  Un processus peut être dans l’un des trois états  Elu : En cours d’exécution  C’est lui qui détient la CPU  Prêt  A toutes les ressources nécessaires et attend son tour pour la CPU.  Bloqué  Attend une ressource ou un événement  Ne peut pas être candidat pour obtenir la CPU avant qu’il soit débloqué LST Info, FSTF 2018-2019 26  La transition 1 : rend le processus bloqué en attente d’une ressource ou d’un événement.  La transition 2 : reprend la CPU au processus et la donne à un autre processus. Elu 1: réquisition Notre processus doit attendre son tour. d’une ressource 2: réquisition de la CPU 3: attribution  La transition 3 : donne (redonne) la CPU de la CPU à notre processus. Bloqué  La transition 4 : débloque le processus Prêt ce qui le rend candidat pour obtenir la 4: acquisition de toutes les ressources CPU.  Un processus prêt ne peut pas devenir bloqué sans passer par l’état « élu ».  Un processus bloqué ne peut pas prendre la CPU sans passer par l’état « prêt ». LST Info, FSTF 2018-2019 27  Appels systèmes :  Définissent l’interface entre le SE et les programmes utilisateurs  Sorte de bibliothèque de fonctions.  Environ 100 appels systèmes dans la norme UNIX.  Analogie avec l’appel de fonctions en langage C.  Les tâches correspondant aux appels systèmes sont exécutées en mode noyau.  Services offerts à travers les appels systèmes  Gestion des processus  Gestion de la mémoire  Gestions des fichiers  Gestion des E/S LST Info, FSTF 2018-2019 28  Principaux appels système de gestion des processus de la norme UNIX : Appel système description pid = fork() Crée un processus enfant identique au parent pid = waitpid(pid, &stat, Attend la terminaison d'un fils options) exit (statut) Termine l'exécution du processus et renvoie le statut LST Info, FSTF 2018-2019 29  Appels système de gestion des processus  fork  Crée une copie conforme du processus appelant  Même code  Mêmes descripteurs de fichiers  …  Sauf la valeur retournée par fork  Nulle dans le nouveau processus (fils)  PID du fils dans le processus père  Les deux processus évolueront, en général, différemment.  Le seul moyen de créer les processus LST Info, FSTF 2018-2019 30  Unappel système signifie que tu vas faire appel à des fonctions du noyau du système d'exploitation.  Parexemple la fonction Sleep sous windows qui endort le processus appelant c'est un appel système.  donc ton programme va passer en mode kernel et exécuter la fonction (en général ca priorité sera augmenté).  Principaux appels système de gestion des fichiers de la norme UNIX : Appel système description df = open(fich, mode,_) Ouvre un fichier en lecture et/ou en écriture s = close(df) Ferme un fichier ouvert n = read(df,tampon, nbOctets) Lit des données d'un fichier dans un tampon n = write(df,tampon, Ecrit les données d'un tampon dans un nbOctets) fichier pos = lseek(df, offset, orig) Déplace le pointeur de fichier s = stat (nom, &buf) Récupère l'information sur un fichier LST Info, FSTF 2018-2019 32  Principaux appels système de gestion des répertoires de la norme UNIX : Appel système description s = mkdir(nom, mode) Crée un nouveau répertoire s = rmdir(nom) Supprime un répertoire vide s = link(nom1, nom2) Crée une nouvelle entrée (nom2) pointant sur nom1 s = unlink(nom) Supprime l'entrée de répertoire correspondante s = mount(spec,nom, flags) Monte un système de fichiers (partitionner) s = umount (spec) Démonte un système de fichiers LST Info, FSTF 2018-2019 33  Autres appels système de la norme UNIX : Appel système description s = chdir(nomRep) Change le répertoire de travail s = chmod(nom, mode) Change les droits d'accès d'un fichier Envoie un signal à un processus s = kill(pid, signal) LST Info, FSTF 2018-2019 34 Quelques appels système sous Windows : UNIX Win32 Description fork CreateProcess Crée un nouveau processus waitpid WaitForSingleObject Attend la fin d'un processus execve (rien) CreateProcess = fork + execve exit ExitProcess Termine l'exécution du processus Crée un nouveau fichier (ou en ouvre un open CreateFile existant) close CloseHandle Ferme un fichier read ReadFile Lit des données depuis un fichier write WriteFile Écrit des données dans un fichier lseek SetFilePointer Déplace le pointeur de fichier stat GetFileAttributesEx Trouve l'information sur un fichier mkdir CreateDirectory Crée un nouveau répertoire rmdir RemoveDirectory Supprime un répertoire vide link (rien) Win32 ne supporte pas les liens LST Info, FSTF 2018-2019 35 LST Info, FSTF 2018-2019 36 Lorsqu’un ordinateur est multiprogrammé, il possède fréquemment plusieurs processus en concurrence pour l’obtention de temps processeur. Cette situation se produit chaque fois que deux processus ou plus sont en état prêt en même temps. S’il y’a un seul processeur, un choix doit être fait quand au prochain processus. LST Info, FSTF 2018-2019 37  La partie du système d’exploitation qui effectue ce choix se nomme l’ordonnanceur (sheduler).  L’algorithme qu’il emploie s’appelle algorithme d’ordonnancement (sheduling algorithm). LST Info, FSTF 2018-2019 38  L’ordonnanceur peut jouer un rôle prépondérant pour améliorer les performances du système d’exploitation  Exemple :  Etant donnés deux processus P1 et P2  P1 : processus de rafraichissement de l’écran  P2 : processus d’envoi de courrier électronique  Retarder P1 (i.e. ralentir le rafraichissement de l’écran)  l’utilisateur perçoit ce petit retard comme une dégradation du service.  Par contre un petit retard de l’envoi du courrier électronique ne sera pas senti par l’utilisateur.  L’ordonnanceur doit, normalement favoriser le processus P1. LST Info, FSTF 2018-2019 39  Quand ordonnancer ? Un large éventail de situations nécessitent de l’ordonnancement. - lorsqu’un nouveau processus est créé, il faut décider s’il faut exécuter d’abord le processus parent ou le processus fils. Etant donné que les deux sont en état prêt. - lorsqu’un processus se termine, un autre processus doit être choisi dans le jeu des processus prêts. LST Info, FSTF 2018-2019 40 - lorsqu’un processus bloque sur des E/S un autre processus, un autre processus doit être sélectionné pour être exécuté. - lorsqu'une interruption d’E/S se produit, il faut également prendre une décision d’ordonnancement. Si l’horloge matérielle fournit des interruptions périodiques à une fréquence de 50 ou 60 Hz, par exemple, une décision d’ordonnancement peut être prise à chaque kéme interruption. LST Info, FSTF 2018-2019 41 On peut classer les algorithmes d’ordonnancement en deux catégories selon leur manière de réagir aux interruptions de l’horloge : - Un algorithme non préemptif : sélectionne un processus, puis le laisse s’exécuter jusqu’à ce qu’il bloque ou qu’il libère volontairement le processeur. Même s’il s’exécute pendant des heures. - Par contre un algorithme préemptif, sélectionne un processus et le laisse s’exécuter pendant un délai déterminé. Si le processus est toujours en cours à l’issue de ce délai : il est suspendu. LST Info, FSTF 2018-2019 42  Efficacité de l’utilisation du processeur  Le basculement du processeur d’un processus à un autre est relativement coûteux  Basculement en mode noyau  Sauvegarder l’état du processus en cours  Charger l’environnement du processus suivant  Démarrer le processus   éviter les basculements très nombreux LST Info, FSTF 2018-2019 43  Plusieurs algorithmes d’ordonnancement :  Ordonnancement de type tourniquet (round robin)  Ordonnancement par priorités  Ordonnancement garanti  Ordonnancement par tirage au sort  Ordonnancement équitable  … LST Info, FSTF 2018-2019 44 1.Ordonnancement de type tourniquet (round robin)  Le plus ancien et le plus utilisé  Tous les processus à ordonnancer sont au même pied d’égalité.  Le processeur est attribué, à tour de rôle, à chacun des processus en lice pour une durée donnée (quantum)  Un processus, qui n’a pas terminé son exécution au bout de son quantum, se met de nouveau dans la file d’attente. LST Info, FSTF 2018-2019 45  Le choix du quantum est très déterminant pour les performances du système.  Un quantum très petit provoquerait des basculements très fréquents  dégradation des performances  Un quantum très grand  temps d’attente est important pour les processus prêts  atteinte à l’interactivité LST Info, FSTF 2018-2019 46 En revanche, le fait de donner d’importants quanta à tous les processus ralentit le temps de réponse. La solution a donc était de créer des catégories de priorités. 2.Ordonnancement par priorités  En réalité, les processus ne sont pas de même niveau d’importance  Les processus système sont le pivot du système et par la suite doivent être les plus prioritaires.  Un processus d’envoi de courrier n’est pas sensible à un petit retard.  Un processus de traitement de texte peut être sensible au retard d’affichage des caractères saisis au clavier.   il est important de définir des priorités entre les processus LST Info, FSTF 2018-2019 48  Ordonnancement par priorités  Principe :  Attribution d’une priorité à chaque processus  Parmi les processus prêts, l’ordonnanceur choisit celui qui a la plus grande priorité  La priorité peut être :  Statique : ne change pas le long de l’exécution  un processus de priorité supérieure est toujours prioritaire par rapport à un autre de prioritaire moindre. LST Info, FSTF 2018-2019 49  Dynamique  Le niveau de priorité du processus qui détient la CPU baisse dans le temps jusqu’à ce qu’un autre processus devient plus prioritaire et lui prend la CPU.  De même le processus prêt se voit augmenter le niveau de priorité au fil du temps ce qui lui donne la chance d’avoir la CPU. LST Info, FSTF 2018-2019 50  Ordonnancement par priorités  Catégories de priorités  Le système définit plusieurs catégories de priorités  Regrouper les processus par catégorie  Les processus de la même catégorie ont le même niveau de priorité.  L’ordonnancement adopté entre ces processus est celui de type Tourniquet.  Les processus de la catégorie de priorité supérieure sont toujours prioritaires par rapport aux autres processus des autres catégories. LST Info, FSTF 2018-2019 51  Ordonnancement par priorités  Files d’attente par catégories  Définition de plusieurs catégories de priorités  Le quantum du processeur n’est pas le même pour toutes les catégories. La catégorie de niveau de priorité inférieure a un quantum relativement grand que celui de la catégorie de priorité supérieure.  Récompenser le retard des processus de priorité inférieure par une durée de détention de la CPU supérieure.  Le processus qui termine sa durée et lâche le processeur passe à la catégorie inférieure.  les processus interactifs commencent dans la catégorie supérieure.  Une interaction (clique, retour chariot) remet le processus dans la catégorie supérieure. LST Info, FSTF 2018-2019 52  Ordonnancement par priorités  Exécuter le processus le plus court :  Permet de favoriser les processus interactifs  Le temps moyen de réponse devient plus court  L’estimation de la durée d’exécution des processus peut être basée sur l’historique des exécutions précédentes :  Moyenne arithmétique  Moyenne pondérée  Favoriser les plus récentes LST Info, FSTF 2018-2019 53 3. Ordonnancement garanti  Le principe de cet ordonnancement est que les processus doivent avoir, globalement, le même cumul des durées de détention du processeur.  Le système maintient, pour chaque processus, un taux correspondant à la durée effective d’utilisation de la CPU par rapport à son quota. Le processus qui a le taux le plus petit (qui a moins utilisé la CPU) sera le plus prioritaire.  Exemple Un processus de taux ½ (a utilisé la moitié de son quota) est prioritaire par rapport au processus de taux 1,2 (a dépassé son quota de 20%). LST Info, FSTF 2018-2019 54 4. Ordonnancement par tirage au sort :  L’idée de base consiste à donner aux processus des « billets de loterie » pour différentes ressources du système et notamment pour le temps processeur.  L’ordonnanceur effectue, à chaque fois, un tirage au sort et le processus possédant le billet tiré aura le CPU.  Possibilité d’instaurer une discrimination positive :  Pour favoriser certains processus, il suffit de leur attribuer plus de billets que les autres  Le processus qui a plus de billets a beaucoup de chance qu’un de ses billets soit tiré. LST Info, FSTF 2018-2019 55  Des processus coopératifs peuvent s’échanger leurs billets  Un processus bloqué, en attente d’un autre processus, préférerait donner ses billets à ce dernier.   le processus bloquant aura, donc, plus de chance d’être sélectionné.  Notre processus pourra récupérer ses billets et éventuellement ceux de l’autre processus. LST Info, FSTF 2018-2019 56 5. Ordonnancement équitable  les ordonnancements précédents, ne tiennent pas compte des autres processus du même utilisateur  Exemple  Etant donnés deux utilisateurs A et B de même niveau de priorité  L’utilisateur A a lancé deux processus et l’utilisateur B a lancé 10 processus  Un processus de l’utilisateur A aura la même priorité qu’un processus de l’utilisateur B   ces types d’ordonnancement « favorisent » les utilisateurs qui surchargent le système  Le principe de l’ordonnancement équitable est de répartir le temps CPU à parts égales entre les utilisateurs plutôt qu’entre les processus  Un processus d’un utilisateur qui a beaucoup de processus, aura moins de temps CPU que ceux d’un utilisateur qui a peu de processus LST Info, FSTF 2018-2019 57  Comment un processus passe des informations à un autre processus ?  Comment éviter des conflits entre des processus concurrents qui s’engagent dans des activités critiques ?  Comment synchroniser les processus dépendants ? LST Info, FSTF 2018-2019 58  Les conditions de concurrence  La section critique  L’exclusion mutuelle avec attente active  Le sommeil et l’activation  Les sémaphores  Les moniteurs  L’échange de message  Les barrières LST Info, FSTF 2018-2019 59  Exemple : spooler d’impression  Principe  Un processus qui veut imprimer un fichier, entre son nom dans un répertoire spécial : répertoire du spooler  Le démon d’impression (spooler) inspecte périodiquement son répertoire, s’il y a un fichier il l’imprime et le supprime du répertoire.  Le répertoire du spooler possède un grand nombre d’entrées numérotées : 0, 1 ,2 … chacune pouvant accueillir un nom de fichier.  Le spooler utilise deux variables partagées : out et in  Out : pointe vers le prochain fichier à imprimer  In : pointe vers la prochaine entrée libre du répertoire  Les variables out et in peuvent être stockées dans un fichier de deux mots, disponible pour tous les processus. LST Info, FSTF 2018-2019 60  Problème : deux processus A et B tentent d’imprimer en même temps  Le processus A lit la valeur de in, et en stocke out in la valeur 7, dans une variable locale appelée 4 7 next_free_slot.  A ce moment là, une interruption se 4 Linux.pdf Processus A produit. La CPU jugeant que le processus 5 Prog.c A a bénéficié de suffisamment du temps 6 Script.sh d’exécution, bascule vers le processus B. Processus 7 B  Celui-çi lit la valeur de in et récupère également un 7. Il stocke cette valeur dans sa variable locale appelée aussi next_free_slot.  A ce point, les 2 processus pensent que la prochaine entrée disponible est la 7. LST Info, FSTF 2018-2019 61 Le processus B continue de s’exécuter. Il stocke son nom de fichier dans l’entrée 7 et actualise in qui prend la valeur 8. Finalement, le processus A s’exécute à nouveau, reprenant les choses où il les avait laissées. Il examine next_free_lost, y trouve un 7, et écrit son nom de fichier dans le connecteur 7, écrasant le nom que le processus B venait juste d’y placer. Ensuite, il calcule next_free_lost+1, ce qui donne 8, et positionne in à 8. LST Info, FSTF 2018-2019 62  Problème : deux processus A et B tentent d’imprimer en même temps.  Le processus B ne recevra jamais de sortie. L’utilisateur B va attendre longtemps une impression qui ne viendra jamais.  De telles situations, ou deux processus ou plus lisent ou écrivent des données partagées et ou le résultat final dépend de quel élément s’exécute à un instant donné : sont nommées conditions de concurrence. LST Info, FSTF 2018-2019 63  Appelée aussi région critique, c’est l’ensemble d’instructions d’un processus (par exemple : accès à la mémoire ou fichiers partagés) susceptibles de provoquer les conditions de concurrence avec d’autres processus.  Pour éviter les conditions de concurrence il faut éviter que les processus concernés ne se trouvent en même temps dans la section critique.  L’Exclusion mutuelle (éviter que 2 processus se trouvent dans la même section critique) LST Info, FSTF 2018-2019 64  L’exclusion mutuelle est une méthode qui permet de s’assurer que si un processus utilise une variable ou un fichier partagés, les autres processus seront exclus de la même activité. La partie du programme à partir de laquelle on accède à la mémoire partagée se nomme région critique, ou section critique. Si l’on pouvait empêcher que deux processus se trouvent simultanément dans leurs sections critiques, on éviterait les conditions de concurrence. LST Info, FSTF 2018-2019 65  Quatre conditions sont nécessaires pour éviter les conditions de concurrence tout en assurant la coopération et l’utilisation adéquate des ressources partagées :  Deux processus ne doivent pas se trouver simultanément dans leurs sections critiques (exclusion mutuelle)  Il ne faut pas faire de suppositions quant à la vitesse ou le nombre de processeur mis en œuvre.  Aucun processus s’exécutant à l’extérieur de la section critique ne doit bloquer d’autres processus.  Aucun processus ne doit attendre indéfiniment pour pouvoir entrer dans sa section critique. Le comportement que nous voulons mettre en œuvre est celui illustré à la figure suivante. LST Info, FSTF 2018-2019 66  A entre dans sa A quitte sa section critique section critique Processus A B tente B entre dans B quitte sa d’entrer dans sa section section sa section critique critique critique Processus B B est T T2 bloqué T3 T4 1 temps LST Info, FSTF 2018-2019 67  Plusieurs manières d’assurer l’exclusion mutuelle  L’exclusion mutuelle avec attente active  Le sommeil et l’activation  Les sémaphores  … LST Info, FSTF 2018-2019 68  Leprincipe est que lorsqu’un processus se trouve dans sa section critique, les autres processus ne peuvent pas y entrer, mais restent actifs et attendent que le processus en cours termine la région critique.  Plusieurs techniques sont utilisées  Désactivation des interruptions  Variables de verrou  Alternance stricte  Solution de Peterson  Instruction TSL LST Info, FSTF 2018-2019 69  Désactivation des interruptions  Le processus qui entre dans sa section critique, désactive les interruptions   Dans ce cas, l’horloge aussi ne pourrait pas envoyer les interruptions, ce qui implique que le processeur ne pourrait pas basculer vers un autre processus.  Le processus en cours est sûr maintenant qu’aucun processus concurrent (ou autre) ne pourra entrer dans la section critique.  Les autres processus n’ont même pas la possibilité d’avoir le processeur tant que les interruptions sont désactivées.  Le processus en cours doit réactiver les interruptions à la fin de la section critique.  Attention!!  Donner aux processus utilisateurs de bloquer les interruptions n’est pas une bonne idée  Un processus (utilisateur) qui termine sa section critique et oublie de réactiver les interruptions.  Un processus (utilisateur) qui, volontairement, ne réactive pas les interruptions pour s’emparer (l’utiliser tout seul) exclusivement du processeur.  La désactivation des interruptions peut être intéressante pour les processus en mode noyau  En général, les processus en mode noyau sont très courts.  Certains processus noyau (comme l’ordonnanceur) ne doivent pas être préempté. LST Info, FSTF 2018-2019 70  Variables verrou : Solution logicielle  Le processus qui veut exécuter sa section critique, teste une variable verrou ( ou lock) partagée dont la valeur initiale est 0.  Si cette variable est à 0, alors il la remet à 1 et entre dans la section critique  Si le verrou est déjà à 1, ce qui signifie qu’un autre processus se trouve dans la section critique  le processus doit attendre que le verrou passe à 0  Le processus remet le verrou à 0 quand il termine la section critique  Problème :  La variable verrou est partagée  pour y accéder, les conditions de concurrence peuvent se produire  Un processus qui a testé le verrou et le trouve à 0, perd le processeur avant de remettre le verrou à 1 (un autre processus s’exécute et le fait à sa place).  Un deuxième processus teste aussi le verrou (toujours à 0) et le remet à 1 ensuite, il entre dans sa section critique.  Lorsque le premier processus reprend son exécution, il remet le verrou à 1(il est déjà à 1) et commence sa section critique. Résultat : les deux processus se trouvent en même temps dans la section critique!! LST Info, FSTF 2018-2019 71  Alternance stricte  Deux processus alternent strictement leur entrées dans la section critique  Entre deux exécutions de la section critique par l’un des processus, il est impératif que l’autre processus exécute aussi la section critique.  Pratique pour représenter le modèle basique de producteur / consommateur.  Principe  Les deux processus inspectent une variable « turn »  Le processus 1 entre dans sa section critique si turn est à 0. Sinon, il entre dans une phase d’attente active  A l’inverse du processus 1, le processus 2 entre dans sa section critique si turn est à 1. Sinon il entre dans une phase d’attente  Chacun des deux processus alterne la variable turn à la fin de sa section critique.  Le processus 1 : 01  Le processus 2 : 10 LST Info, FSTF 2018-2019 72  Alternance stricte  Code d’entrée dans la section critique des deux processus Processus 1 Processus 2 LST Info, FSTF 2018-2019 73  Quatre conditions sont nécessaires pour éviter les conditions de concurrence tout en assurant la coopération et l’utilisation adéquate des ressources partagées : 1. Deux processus ne doivent pas se trouver simultanément dans leurs sections critiques (exclusion mutuelle). 2. Pas de suppositions sur la vitesse ou le nombre de processeur mis en œuvre. 3. Aucun processus s’exécutant à l’extérieur de la section critique ne doit bloquer d’autres processus 4. Aucun processus ne doit attendre indéfiniment pour pouvoir entrer dans sa section critique. LST Info, FSTF 2018-2019 74  Alternance stricte  Problème :  La démarche proposée entre en conflit avec la troisième condition : Le processus 1 peut être bloqué par un processus, hors de sa section critique. Par exemple, le processus 1 ne serait pas autorisé à imprimer un autre fichier, car le processus 2 serait occupé à une autre tache. LST Info, FSTF 2018-2019 75  Solution de Peterson  Combine l’alternance stricte et la variable verrou  Un processus peut enchaîner deux (ou plusieurs) exécutions de la section critique, alors que l’autre processus n’en a pas exécuté une.  L’algorithme de Peterson, est composé de deux procédures développées en C ANSI. LST Info, FSTF 2018-2019 76  Code de la solution de Peterson : #define FALSE 0 #define TRUE 1 #define n 2 int turn; int interested[n]; void enter_region (int process) { int other; other = 1 – process; interested[process] = TRUE; turn = process; while(turn == process && interested[other] == TRUE); } void leave_region(int process) { inerested[process] = FALSE; } LST Info, FSTF 2018-2019 77  Avantd’utiliser les variables partagées, chaque processus appelle enter_region avec son propre numéro de processus, 0 ou 1.  Cet appel le met en attente, jusqu’à ce qu’il entre  Unefois qu’il a fini avec les variables partagées, le processus appelle leave_region pour autoriser un autre processus à entrer. LST Info, FSTF 2018-2019 78  Voyons comment fonctionne cette solution :  1er cas :  Aucun des processus ne se trouve dans sa section critique.  Le processus 0 appelle enter_region.  Il montre son intérêt en positionnant turn à 0.  Si le processus 1 est désintéressé, enter_region retourne immédiatement.  Si le processus 1 appelle maintenant enter_region, il attend jusqu’à ce que interested passe à FALSE.  Ceci ne se produit que si le processus 0 appelle leave_region. LST Info, FSTF 2018-2019 79  2éme cas :  Les 2 processus appellent enter_region simultanément.  Ils vont stocker tous les 2 leur numero de processus dans turn.  Supposons que le processus 1 soit stocké en dernier : turn est à 1.  Lorsque les 2 processus arrivent, le processus 0 entre en section critique.  Le processus 1 n’entre pas en section critique tant que le processus 0 n’a pas quitté la sienne. LST Info, FSTF 2018-2019 80  InstructionTSL :(Test and Set Lock : Tester et définir le verrou) Etudions maintenant une proposition qui sollicite un peu d’aide de la part du matériel. De nombreux ordinateurs, et notamment ceux qui ont été conçus pour accueillir plusieurs processeurs, prennent en charge l’instruction : TSL RX, LOCK LST Info, FSTF 2018-2019 81  Elle fonctionne de la manière suivante : Elle lit le contenu du mot mémoire lock dans le registre RX, puis stocke une valeur différente de 0 à l’adresse mémoire lock. Les opérations qui consistent à lire le mot et à y stocker une valeur sont absolument indivisibles : aucun autre processeur ne peut accéder à la mémoire tant que l’instruction n’est pas terminée. Le processeur exécutant l’instruction TSL verrouille le bus mémoire pour interdire aux autres processeurs d’accéder à la mémoire tant qu’il n’a pas terminé. LST Info, FSTF 2018-2019 82 Lorsque lock est à 0, n’importe quel processus peut la positionner à 1 via l’instruction TSL, puis lire ou écrire dans la mémoire partagée. Cela fait, le processus repositionne lock à 0 à l’aide d’une structure move ordinaire pour sortir de la Mémoire. Mais comment utiliser cette instruction pour empêcher deux processus d’entrer simultanément dans leurs sections critiques ? LST Info, FSTF 2018-2019 83 La solution est illustré dans les sous-programmes suivants : Enter_region : TSL REGISTER, LOCK |copie lock dans le registre et |la positionne à 1 CMP REGISTER, #0 ;look était-elle à 0 ? JNE enter_region RET ; Retourne à l’appelant leave_region : MOV LOCK, #0 ; stocke un 0 dans look RET ; Retourne à l’appelant LST Info, FSTF 2018-2019 84  Instruction TSL  Cette technique utilise une variable verrou.  La spécificité est que le test et le positionnement du verrou sont deux opérations indivisibles.  Si le verrou est à 1 le processus doit attendre qu’il passe à 0  Si le verrou est à 0 le processus le positionne à 1 et entre dans sa section critique.  Entre le test et le positionnement aucun autre processus ne pourra accéder au verrou.  Le processus doit remettre le verrou à 0 à la fin de sa section critique. LST Info, FSTF 2018-2019 85  Limitations  Toutes les solutions de cette catégorie obligent le processus en attente d’entrer dans sa section critique à rester actif.  Le processus s’installe dans une petite boucle en attendant l’ouverture.   Cette approche est très consommatrice du temps processeur.  Le processus consomme, inutilement, sa part du processeur. LST Info, FSTF 2018-2019 86  Limitations  Exemple  Etant donnés deux processus P1 et P2 dans le cas d’un ordonnancement par priorité statique.  P1 s’exécute dans sa section critique.  P2 vient d’être lancé.  P2 a une priorité supérieure à celle de P1.  P2 est en attente active pour entrer dans la section critique, alors que P1 ne l’a pas encore quitté.  P1 ne pourra pas s’exécuter parce que l’ordonnanceur donne la priorité à P2.  P2 entre dans une boucle infinie. LST Info, FSTF 2018-2019 87  Principe :  Le processus, en attente d’entrer dans sa section critique, ne doit pas rester actif.  N’a pas besoin d’avoir la CPU   Le processus en attente doit se bloquer (s’endormir) en attendant que le processus en cours le débloque (le réveille).  Deux primitives sont utilisées : sleep et wakeup  Un processus qui n’est pas autorisé à entrer dans la section critique se bloque (est suspendu de la liste de l’ordonnanceur ) en appelant la primitive sleep.  A la fin de la section critique, le processus vérifie si un processus est bloqué, si c’est le cas il le réveille avec la primitive wakeup. LST Info, FSTF 2018-2019 88  Producteur/consommateur  Deux processus se partagent un tampon (buffer) de taille fixe. Le premier (producteur) écrit des informations dans le tampon et le deuxième (consommateur) y récupère les informations.  Le producteur se bloque quand le tampon devient plein.  Le consommateur se bloque quand le tampon se vide.  Principe :  N étant la taille fixe du tampon  Les deux processus se partagent une variable « count » correspondant au nombre d’éléments dans le tampon  Consommateur  Si count = 0  le consommateur entre en sommeil  Si count = N-1  le consommateur réveille le producteur (si le consommateur arrive à N-1 de la consommation, il doit reveillé le producteur)  Producteur  Si count = N  le producteur entre en sommeil  Si count = 1  le producteur réveille le consommateur LST Info, FSTF 2018-2019 89  Telleétait la situation, en 1965, lorsque E. W. Dijkstra suggéra d’utiliser un nouveau type de variable entière qui devait permettre de décompter le nombre de wakeup enregistrés pour un usage ultérieur.  Danssa proposition, il appelait ce nouveau type de variable un sémaphore. LST Info, FSTF 2018-2019 90  Unsémaphore est une variable entière spéciale sur laquelle on peut exécuter deux opérations : down et up  L’opération down teste si le sémaphore est supérieur à 0. Dans ce cas, elle le décrémente et le processus peut entrer dans la section critique. Si le sémaphore est nul alors, le processus entre en sommeil.  L’opération up incrémente le sémaphore.  Si un processus se trouve en sommeil sur ce sémaphore, alors il sera réveillé.  Les opérations de test, de modification du sémaphore et de mise en sommeil sont indivisibles  ceci permet d’éviter les conditions de concurrence. LST Info, FSTF 2018-2019 91  Résolution du problème du producteur / consommateur avec les sémaphores :  Deux processus se partageant un tampon de taille fixe. Le premier écrit dans le tampon et l’autre y consomme.  Trois sémaphores sont utilisés dans la solution  Full : pour compter le nombre d’emplacements pleins dans tampon  Empty : le nombre d’emplacements vides  Mutex : pour assurer l’exclusion mutuelle lors de l’accès au tampon (afin de s’assurer que le producteur et le consommateur n’accèdent pas simultanément au tampon). LST Info, FSTF 2018-2019 92  Dans la figure suivante, le sémaphore mutex est employé pour l’exclusion mutuelle. Il est conçu afin de garantir qu’un seul processus à la fois accédera en lecture et en écriture au tampon et aux variables associées.  Cetteexclusion mutuelle est indispensable pour éviter tout désordre. LST Info, FSTF 2018-2019 93   Solution du Producteur/consommateur #define n 100 Typedef int semaphore ; semaphore mutex = 1; semaphore empty = n; semaphore full = 0; void producer() { int item; while (TRUE) { item = produce_item(); down(&empty); down(&mutex); insert_item(item); up(&mutex); up(&full); } } LST Info, FSTF 2018-2019 94 void consumer() { int item; while (TRUE) { down(&full); down(&mutex); item = remove_item(); up(&mutex); up(&empty); consomme_item(item); } } LST Info, FSTF 2018-2019 95  les sémaphores servent également à faire de la synchronisation. Les sémaphores full et empty sont nécessaires pour garantir que certaines séquences d’événements se produisent ou ne se produisent pas.  Dans ce cas de figure, ils font en sorte que le producteur cesse de s’exécuter lorsque le tampon est plein, et que le consommateur cesse de s’exécuter quand il est vide.  Il s’agit d’un usage différent de celui de l’exclusion mutuelle. LST Info, FSTF 2018-2019 96  Version simplifiée des sémaphores  Prend en charge particulièrement l’exclusion mutuelle  Un mutex peut prendre deux valeurs  1 : déverrouillé  0 : verrouillé  Deux fonctions pour la gestion des mutex  Mutex_lock : invoquée pour pouvoir entrer en section critique  Si le mutex est à 1 alors, il passe à 0 et le processus pourrait entrer en section critique.  Si le mutex est à 0 alors le processus se bloquerait jusqu’à ce que le mutex sera débloqué par un autre processus (celui qui exécute sa section critique)  Mutex_unlock : remet le mutex à 1 à la fin de la section critique, et réveille éventuellement un processus bloqué. LST Info, FSTF 2018-2019 97  L’usage des sémaphores est relativement complexe et la moindre erreur peut avoir des conséquences fatales sur le fonctionnement global des processus.  Exemple : producteur/consommateur  Que se passe-t-il si, par erreur, l’ordre des deux instructions down dans le producteur a été inversé? void producer() void consumer() { { int item; int item; while (TRUE) while (TRUE) { { item = produce_item(); down(&full); down(&mutex); down(&mutex); down(&empty); item = remove_item(); insert_item(item); up(&mutex); up(&mutex); up(&empty); up(&full); consomme_item(item); } } } } LST Info, FSTF 2018-2019 98  Exemple : producteur/consommateur (down(&mutex); down(&empty)))  Si mutex = 1 et empty = 0  le producteur va pouvoir réaliser l’opération down(mutex) ce qui signifie que le mutex passe à 0. Par contre il se bloquera après l’opération down(empty).  Le consommateur sera bloqué sur down(mutex) parce que le producteur n’a pas encore fait l’opération up(mutex).  interblocage   interblocage   utilisation des primitives de synchronisation de haut niveau fournies par un langage de programmation : Moniteurs LST Info, FSTF 2018-2019 100  Mettre à la disposition des utilisateurs un moyen de définir et de spécifier une partie du code nécessitant l’exclusion mutuelle sans se soucier de la gestion «complexe » de sémaphores.  Minimiser le risque d’erreur lors de la gestion des sémaphores.  utilisation des primitives de synchronisation de haut niveau fournies par un langage de programmation : Moniteurs. LST Info, FSTF 2018-2019 101  Un moniteur est un module spécial regroupant des fonctions, des variables et des structures de données.  Les processus peuvent appeler les fonctions du moniteur, mais ils ne peuvent pas accéder directement à ses structures internes.  A un instant donné, un seul processus peut être actif dans le moniteur.  Le programmeur n’a pas à se soucier de la manière d’assurer l’exclusion mutuelle :  Normalement c’est le compilateur qui s’en charge LST Info, FSTF 2018-2019 102  Comment synchroniser deux processus qui s’exécutent sur deux ordinateurs distincts reliés par internet ?  Pas de mémoire partagée pour conserver un sémaphore.  Les moniteurs eux aussi se basent sur les sémaphores.  Les autres techniques vues précédemment nécessitent une zone mémoire partagée.  L’échange de message LST Info, FSTF 2018-2019 103  Lesprocessus distants peuvent se synchroniser en échangeant des messages avec deux primitives send et receive (en général présentes sous forme d’appel système).  send(destination, &message)  Envoie un message vers une destination  receive(source, &message)  Reçoit un message d’une source donnée.  En l’absence du message, le récepteur peut se bloquer jusqu’à ce que celui-ci arrive. LST Info, FSTF 2018-2019 104  Problème de perte de messages  Utiliser la technique d’acquittement et de duplication de messages.  Pour chaque message reçu, on doit envoyer un accusé de réception.  Si l’émetteur ne reçoit pas l’accusé de réception, il déduit que son message est perdu  il réémette le message  Que se passe-t-il si le message est arrivé mais son accusé de réception est perdu?  Le message sera réémis et risque d’être pris en compte deux fois.   numéroter les messages  Si un message arrive deux fois, le récepteur peut se rendre compte qu’il s’agit d’un doublon et l’ignorer. LST Info, FSTF 2018-2019 105  Moyen de synchroniser un groupe de processus au début de chaque « phase »  Tous les processus doivent arriver à un seuil (barrière) avant que chacun d’eux ne puisse poursuivre son exécution  Point de rencontre  Attendre le dernier LST Info, FSTF 2018-2019 106  A A A B B B barrière barrière barrière C C C D D D temps Les processus A, B, C et D doivent tous atteindre la barrière avant que le groupe puisse poursuivre la suite de l’exécution LST Info, FSTF 2018-2019 107  108 LST Info, FSTF 2018-2019  Le système Unix/Linux est multi-tâche : Plusieurs programmes peuvent être en cours d’exécution en même temps sur une même machine.  Maisà chaque instant, le processeur ne traite qu’un un seul programme lancé (un seul processus).  Lagestion des processus est effectuée par le système d’exploitation. LST Info, FSTF 2018-2019  Lesprocessus correspondent à l’exécution des tâches.  L’environnement d’un processus est doté d’un espace d’adressage (ensemble d’adresses) dans lesquelles le processus peut lire et écrire. LST Info, FSTF 2018-2019  Unprocessus est un programme qui s'exécute et possède :  Un compteur ordinal,  Un ensemble de registres  une mémoire(données, code et pile ). LST Info, FSTF 2018-2019  Le code correspond aux instructions, en langage machine, du programme à exécuter.  Lazone de données contient les variables globales ou statiques du programme ainsi que les allocations dynamiques de mémoire.  Enfin,les appels de fonctions, avec leurs paramètres et leurs variables locales, viennent s'empiler sur la pile. LST Info, FSTF 2018-2019 Relation entre les processus :  Les processus des utilisateurs sont lancés par un interprète de commande (shell).  Ils peuvent eux-même lancer ensuite d'autres processus.  On appelle le processus créateur, le père, et les processus créés, les fils.  Les processus peuvent donc se structurer sous la forme d'une arborescence.  Au lancement du système, il n'existe qu'un seul processus, appelé processus « init ». Le processus "init" crée 2 sortes de processus :  Desdémons, des processus qui ne sont rattachés à aucun terminal, qui sont endormis la plupart du temps, mais qui se réveillent de temps en temps pour effectuer une tâche précise.  Desprocessus interactifs, vous permettant de vous connecter.  init daemons getty login shell Création d’un processus :  Un processus est crée au moyen d’un appel système, c’est-à-dire par un autre processus ayant réalisé cet appel,  Un processus et identifié par un numéro (PID) ( Process IDentifier ) :  La primitive getpid() renvoie le numéro (PID) du processus qui l’exécute.  Chaque processus a un père, celui qui l’a lancé. La primitive getppid() renvoie le numéro du père. Le PID du processus init est 1. $ cmd1 & cmd2 & $ cmd1 & cmd1 & printf("je suis le père, mon PID est %d\n", getpid()); } else { printf("je suis le fils, mon PID est %d et le PID de mon père est %d\n", getpid(), getppid()); }  Pendant l'exécution du fork() le système :  alloue une entrée dans la table des processus au nouveau processus,  alloue un pid unique au nouveau processus,  duplique le contexte du processus père (code, données, compteur ordinal, pile, etc...),  retourne au père le pid du fils créé et 0 au fils.  Le fils hérite de tous les attributs du père sauf :  l'identifiant du père : le pid et le ppid Quelques données concernant les processus :  Attention : Le PID est lié au processus. Pa exemple, si on lance 10 fois le même programme, on aura 10 processus, et par conséquent 10 PID différents.  PPID (PrentProcess ID): un processus (processus père) peut lancer lui aussi d’autres processus, appelés processus fils. Le processus fils peut identifier son processus père par un numéro désigné par PPID. Tous les processus ont un PPID sauf le processus init représente le processus de démarrage du système.  UID (User IDentifier) et le GID (Group IDentifier) :  UID: l'identificateur de l'utilisateur propriétaire du processus.  GID : le groupe auquel appartient cet utilisateur. A chaque processus, on associe l'UID et le GID de l'utilisateur qui a lancé le processus. Terminer un processus avec la primitive exit : void exit(int status) :  Termine brutalement un processus  La valeur status est envoyée au processus parent.  Librairies à utiliser : stdlib.h Faire attendre un processus avec la primitive Sleep :  int sleep(int seconds)  le processus qui appelle sleep est bloqué pendant le nombre de secondes spécifié.  Les entrées/sorties : Lors de l’exécution d’une commande, un processus est créé. Celui-ci va alors ouvrir trois canaux de communication: – l’entrée standard, – la sortie standard, – la sortie d’erreurs standard.  Le fichier « stdin» : le processus lit les données en entrée à partir du fichier « stdin». Il est ouvert avec le numéro logique 0. Par défaut, il est associé au clavier.  Lefichier « stdout» : le processus écrit les sorties qu’il produit dans le fichier «stdout». Il est ouvert avec le numéro logique 1. Par défaut, il est associé à l’écran.  Lefichier « stderr» : le processus écrit les messages d’erreur dans le fichier «stderr». Il est ouvert avec le numéro logique 2. Par défaut, il est associé à l’écran.  Enrésumé, à chacun des trois canaux est affecté un nom de fichier et un numéro : Canal de Communication Fichier Descripteur Entrée Standard stdin 0 Sortie Standard stdout 1 Sortie d’erreurs standard stderr 2  Un processus peut être créé :  Directement en lançant une commande  À partir d'un autre processus  Lors du démarrage  init : le processus qui initialise le système  Processus système (deamons)  Shell : le processus qui permet de lancer les commandes ... LST Info, FSTF 2018-2019 130  Directement par une commande Processus LST Info, FSTF 2018-2019 131  Directement par une commande Shell Processus ls fils Le processus fils hérite l'environnement du père sauf le PID et le PPID père LST Info, FSTF 2018-2019 132  À partir d'un autre processus Code du processus 1 Processus Instruction 1 père... commande... Processus Le processus fils hérite fils l'environnement du père sauf le PID et le PPID LST Info, FSTF 2018-2019 133  Exemple de création d’un processus #include #include main() { int r; printf(" Avant la création du nouveau processus \n"); r=fork(); if (r==0) { printf(" Je suis le fils mon PID est %d et mon PPID est %d\n",getpid(),getppid()); sleep(3); printf(" Fin du processus fils\n"); } else { printf(" Je suis le père mon PID est %d et mon PPID est %d\n",getpid(),getppid()); sleep(5); printf(" Fin du processus père \n"); } } LST Info, FSTF 2018-2019 134  PID = 27 PID = 56 PPID = 1 PPID = 27 UID = 512 UID = 512 Répertoire courant Répertoire courant GID = 10 GID = 10 /home/ali /home/ali Fichiers Fichiers ouverts ouverts Processus 0 Processus 0 père 1 fils 1 2 2 Umask = 027 Umask = 027 Priorité = 20 Priorité = 20 ulimit = 2048 ulimit = 2048 tty de contrôle temps = 5.7 tty de contrôle temps = 0.5 /dev/tty03 /dev/tty03 LST Info, FSTF 2018-2019 135  1 Nouveau Prêt Zombi 2 9 8 Actif 3 Appel 6 Noyau Systéme 4 Elu 7 5 Bloqué 7 Suspendu Endormi LST Info, FSTF 2018-2019 136  Transitions entre les états du processus 1. Le processus a acquis les ressources nécessaires à son 1 exécution Nouveau Prêt 2. Le processus vient d’être élu par l’ordonnanceur Zombi 3. Le processus revient d’un appel système 2 9 4. Le processus a réalisé un appel 8 système ou une interruption est 6 survenue Actif 3 Appel 5. Le processus se met en attente Noyau Systéme d’un événement 4 7 6. L’événement attendu par le 5 système est survenu 7. Demande de suspension du 7 processus Suspendu Endormi 8. Reprise du processus 9. Le processus se termine LST Info, FSTF 2018-2019 137  Etat zombi  Le processus a terminé son exécution, mais il n’a pas encore libéré son entrée dans la table des processus.  Toutes ses autres ressources sont libérées.  Il attend que le processus père récupère sa valeur de retour. LST Info, FSTF 2018-2019 138 Ou bien :  Quand un processus se termine, il délivre un code de retour (paramètre de la primitive exit()). Par exemple exit(0) donne un code de retour de 0.  Tout processus qui se termine passe dans l’état zombi tant que son père n’a pas pris connaissance de sa terminaison. exit() état Zombi fils endormi père fork Sleep bash - Le temps pendant lequel le processus fils est en état zombi, il n’a plus son code ni ses données en mémoire; Seules les informations utiles pour le père sont conservées. - Il faut éviter de garder des processus en état zombi.  Exemple #include #include main() { int r; printf(" Avant la création du nouveau processus \n"); r=fork(); if (r==0) { printf(" Je suis le fils mon PID est %d et mon PPID est %d\n",getpid(),getppid()); sleep(3); printf(" Fin du processus fils, je suis maintenant à l‘état zombie en attendant la fin du père \n"); } else { printf(" Je suis le père mon PID est %d et mon PPID est %d\n",getpid(),getppid()); sleep(50); printf(" Fin du processus père\n"); } } LST Info, FSTF 2018-2019 141  Plusieurs processus peuvent être lancés en même temps selon trois manières :  En série  En parallèle  Par tube (pipe) LST Info, FSTF 2018-2019 142  Les processus s’exécutent dans l’ordre  Le deuxième processus ne peut démarrer qu’après la fin du premier. Et ainsi de suite pour les autres.  En ligne de commande les programmes correspondants sont séparés par le caractère « ; »  Exemple  prop1 ; prog2 ; prog3 ;  Comportement par défaut dans le Shell LST Info, FSTF 2018-2019 143  Les processus s’exécutent de manière indépendante  Tous les processus commencent l’exécution en même temps  En ligne de commande les programmes correspondants sont séparés par le caractère « & »  Exemple :  prop1 & prog2 & prog3 &  Dans le Shell, rajouter le caractère & à la fin d’une commande permet de la lancer en arrière plan :  Le moyen d’exécuter le père (Shell) et le fils (commande) en parallèle. LST Info, FSTF 2018-2019 144  Considéré principalement comme un moyen de communication entre processus  En ligne de commande : les programmes correspondants sont séparés par le caractère « | ».  La sortie standard du premier processus est utilisée comme entrée standard du deuxième processus.  Le tube est considéré comme un fichier spécial ouvert en écriture au premier processus et en lecture au deuxième processus.  Les deux processus s’exécutent en même temps  Le premier processus se bloque sur une écriture si le tube est plein.  Le deuxième processus se bloque sur une lecture si le tube est vide. LST Info, FSTF 2018-2019 145  Identificateurs réels :  UID : identificateur de l'utilisateur réel qui a lancé le processus.  GID : identificateur du groupe de l'utilisateur qui a lancé le processus. LST Info, FSTF 146  Identificateurs effectifs :  EUID : identificateur de l'utilisateur propriétaire de la commande lancée.  EGID : identificateur du groupe de l'utilisateur propriétaire de la commande lancée.  Souvent les identificateurs réels et effectifs sont confondus.  Seul le root a le droit de créer des programmes pouvant changer les EUID et EGID. LST Info, FSTF 2018-2019 147 LST Info, FSTF 2018-2019 148  Dans un système multiprogrammé, plusieurs processus peuvent être présents en mémoire centrale.  Le système d’exploitation décide de l’ordre et du moment de l’admission des programmes en attente (ordonnanceur de haut niveau).  Il gère également l’allocation du processeur aux différents processus à exécuter (ordonnanceur de bas niveau).  L’exécution d’un processus est une séquence alternée de calculs CPU et d’attentes d’événements (E/S, attente d’un sémaphore..).  Lorsque le processus en cours se bloque, le processeur est alloué à un autre => L’ordonnanceur de bas niveau se charge des changements de contexte. LST Info, FSTF 2018-2019 149  L’ordonnanceur de haut niveau décide du degré de la multiprogrammation (nombre maximal de processus dans le système).  L’ordonnanceur de niveau intermédiaire gère le déplacement des processus d’une file d’attente à une autre.  Dans la majorité des systèmes actuels, les niveaux intermédiaire et haut sont combinés -> haut niveau.  L’ordonnanceur de bas niveau (dispatcher ou répartiteur) est sollicité plusieurs fois par seconde et doit constamment résider en mémoire.  L’ordonnancement doit se faire selon une politique bien réfléchie visant à répondre à des objectifs de performance. 1. Maximiser le nombre de processus exécutés par unité de temps. 2. Minimiser le temps d’attente d’exécution de chaque processus. 3. Maximiser les temps d’utilisation des processeurs et autres ressources. 4. Respecter les échéanciers (terminer l’exécution avant leurs deadlines). 5. Éviter le problème de famine (attente infinie). 6. Favoriser les processus les plus prioritaires. Prioriser les objectifs.  Temps de séjour d’un processus : temps entre l’admission du processus et sa sortie.  Temps d'attente d’un processus : somme des périodes que le processus passe à l'état prêt.  Temps de réponse: temps qui s'écoule entre l'entrée d'un processus et le moment où il commence à être traité.  Capacité de traitement : nombre de processus traités par unité de temps.  Taux d’utilisation d’un processeur.  Choix du processus à exécuter ? – Premier arrivé, premier servi. – Plus prioritaire (priorités statiques ou dynamiques). – Plus court temps ….  Le temps d’allocation du processeur au processus choisi : – Allocation jusqu’à terminaison ou libération volontaire (ordonnanceur non préemptifs). – Temps d’allocation limité fixe ou variable (ordonnanceur préemptifs).  Quand appeler l’ordonnanceur ? – Le processus en cours se termine, se bloque ou cède le processeur, – Le temps alloué a expiré. – L’arrivée d’un processus plus prioritaire… Cas d’UNIX (traditionnel)  C’est un ordonnanceur à deux niveaux. L’ordonnanceur de bas niveau se charge d’élire un processus parmi ceux qui résident en mémoire.  L’ordonnanceur de haut niveau se charge des transferts de processus de la mémoire centrale,  L’ordonnanceur de bas niveau utilise plusieurs files, une priorité est associée à chaque file (plusieurs niveaux de priorité).  Les priorités des processus s’exécutant en mode utilisateur sont positives ou nulles, alors que celles des processus s’exécutant en mode noyau sont négatives.  Les priorités négatives sont les plus élevées.  Principe :  Utiliser plusieurs files d’attente où chacune d’elles est associée à un ensemble de valeurs de priorités.  Les priorités utilisées par UNIX sont des valeurs entières entre -20 et 20.  Les valeurs de priorités positives correspondent aux processus s’exécutant en mode utilisateur.  Les valeurs de priorités négatives correspondent aux processus s’exécutant en mode superviseur (noyau). LST Info, FSTF 2018-2019 155 Priorité maximale Processus -4 Attente d’E/S disque en mode superviseur -3 Attente du buffer disque -2 Attente de saisie au clavier -1 Attente d’affichage à 0 Prioritél’écran utilisateur 0 1 Priorité utilisateur 1 Processus 2 Priorité utilisateur 2 en mode 3 Priorité utilisateur 3 utilisateur Priorité minimale LST Info, FSTF 2018-2019 156  L’ordonnanceur cherche une file non vide en commençant par la file de plus grande priorité (-20)  La CPU est attribuée pour un quantum au premier processus de cette file.  Après, le processus s’il n’a pas terminé, il est replacé à la fin de file.  Les processus de la même classe de priorité subissent un ordonnancement de type tourniquet.  Si un processus débloqué ou un nouveau processus rejoint une file de priorité supérieure à celle de la file du processus en cours d’exécution, alors, l’ordonnanceur passera à la file de priorité supérieure.  Si la file courante se vide (terminaison ou blocage du dernier processus) l’ordonnanceur passera à la première file non vide en-dessous. LST Info, FSTF 2018-2019 157  Enprésence de processus de priorité importante, les processus de priorité moindre n’auront jamais la possibilité de s’exécuter !!  Lapriorité n’est pas figée(rigide), elle est mise à jour à chaque seconde par la formule :  Priority = CPU_usage + nice + base  Le processus sera donc attaché à la file correspondant à sa nouvelle priorité. LST Info, FSTF 2018-2019 158  base : ne change pas et elle est liée à la nature des instructions exécutées.  CPU_usage : le nombre moyen de cycle d’horloges/seconde attribués au processus dans les dernières secondes :  A force d’utiliser la CPU, ce paramètre s’incrémente ce qui augmente la valeur de priorité du processus et par conséquent le processus peut passer à une file de priorité moins importante.  De l’autre côté, le processus qui utilise moins la CPU, sa valeur de priorité va diminuer ce qui lui donnera plus de chance pour avoir la CPU  nice : permet à un processus de choisir un comportement de « sympathie » favorisant ainsi les autres processus :  Sa valeur est comprise entre -20 et 20  Par défaut elle vaut 0  Un processus utilisateur peut la positionner entre 0 et 20  Augmenter la valeur de sa priorité  favoriser les autres processus  L’administrateur peut choisir une valeur entre -20 et -1 LST Info, FSTF 2018-2019 159  L’ordonnancement des systèmes Linux diffère de celui des systèmes UNIX :  L’ordonnancement de Linux est fondé sur les threads et non sur les processus.  Linuxdistingue trois classes de threads pour l’ordonnancement : 1. Les FIFO temps réel 2. Les tourniquets temps réel 3. Les threads en temps partagé LST Info, FSTF 2018-2019 160 1. Les FIFO temps réel :  Les threads de cette catégorie sont prioritaires  Ne sont pas préemptibles 2. Les tourniquets temps réel :  Sont prioritaires par rapport à la catégorie 3  Sont interruptibles par l’horloge  En présence de plusieurs threads de cette catégorie, l’algorithme de tourniquet est utilisé pour partager la CPU.  Les deux catégories dites temps réel ne reflètent pas réellement cette caractéristique :  Aucune garantie par rapport aux délais.  Temps réel c’est tout simplement prioritaires/catégorie 3. LST Info, FSTF 2018-2019 161  Chaque thread a une priorité entre 1 et 40  Par défaut elle vaut 20  L’appel système nice(val) permet de modifier cette valeur.  val est entre -20 et 19  La nouvelle priorité est 20-val   la priorité est toujours entre 1 et 40  Par opposition à UNIX, la grande valeur de priorité correspond à la plus forte priorité :  Le thread de priorité 24 est prioritaire à celui qui a la priorité 20. LST Info, FSTF 2018-2019 162  L’ordonnancement est basé sur un paramètre appelé «goodness » calculé en fonction de la priorité, le quantum et la classe des threads selon les formules :  if (class==real-time) goodness = 1000+priority  if(class==timesharing && quantum>0) goodness=quantum+priority  if(class==timesharing && quantum ==0) goodness=0  Le processus qui a la plus grande goodness est sélectionné pour un quantum comprenant un nombre de cycles d’horloges égal à sa priorité. LST Info, FSTF 2018-2019 163  La première formule permet de garantir que les threads des deux premières catégories obtiennent une goodness nettement supérieure à celle de tous les autres threads de la catégorie 3(temps partagé).  Les deux dernières formules permettent de favoriser le thread qui n’a pas encore terminé son quantum :  Il y a beaucoup de chance que son code et ses données soient encore présents en mémoire. LST Info, FSTF 2018-2019 164  Le principe de l’ordonnancement est :  Attribuer la CPU au thread qui a la plus grande goodness.  A chaque top de l’horloge, son quantum est décrémenté de 1.  La CPU peut être retirée au thread dans les cas suivants:  Son quantum atteint 0  Le thread se bloque  E/S, section critique, … LST Info, FSTF 2018-2019 165  Un thread bloqué qui n’a pas encore fini son quantum sera récompensé en augmentant son quantum par la formule :  quantum = quantum/2 + priority  Quand un thread termine son quantum, une remise à jour générale lui donnera une nouvelle valeur égale à sa priorité :  quantum = priority LST Info, FSTF 2018-2019 166