Remerciez-le!

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

Université de Yaoundé 1 Faculté des Sciences Département d’Informatique INFO208

Université de Yaoundé 1 Faculté des Sciences Département d’Informatique INFO208 – Systèmes d’Exploitations : Processus : Problème Classique, IPC, Ordonnancement DOMGA KOMGUEM Rodrigue – cours.domga@gmail.com 2/21 Problèmes classiques : Les Philosophes (1/2) ●5 philosophes sont assis autour d'une table ronde ●Il n'y a qu'une fourchette entre deux assiettes consécutives. ●Soit un philosophe mange, soit il pense ●Quand un philosophe a faim, il tente de prendre les deux fourchettes encadrant son assiette ●Comment écrire un algorithme qui permette à chaque philosophe de ne jamais être bloqué: ✔Interblocage ✔Privation 3/21 Problèmes classiques : Les Philosophes (2/2) ●Une solution : Voir le support de cours ●Autres problèmes: ✔Le problème des lecteurs et des rédacteurs (en TD) ✔Le problème du coiffeur endormi (TPE) 4/21 Communication inter-processus ●Les processus du système ne s'exécutent pas tous de manière isolé ●Besoin de coopérer, et nécessitent donc des moyens de communications et de synchronisation ●D'autres se trouvent en compétition pour les ressources du système 5/21 IPC : Sérialisation des travaux d'impression (1/2) ●Les tâches à imprimer sont stockées dans un répertoire de spoule 6/21 IPC : Sérialisation des travaux d'impression (2/2) ●Les tâches à imprimer sont stockées dans un répertoire de spoule local_in = in placer_job(local_in) in = local_in + 1 ●En supposant que nous sommes dans un système à temps partagés, soulever le problème qui peut se poser. 7/21 IPC : Le modèle du producteur – consommateur (1/5) ●Un modèle de communication entre processus avec partage de zone commune (tampon) est le modèle producteur-consommateur ●Le producteur doit pouvoir ranger en zone commune des données qu'il produit en attendant que le consommateur soit prêt à les consommer ●Le consommateur ne doit pas essayer de consommer des données inexistantes ●Hypothèses : ✔les données sont de taille constante ✔les vitesses respectives des deux processus (producteur consommateur) sont quelconques. 8/21 IPC : Le modèle du producteur – consommateur (2/5) ●Règles ✔Règle 1 : Le producteur ne peut pas ranger un objet si le tampon est plein ✔Règle 2 : Le consommateur ne peut pas prendre un objet si le tampon est vide. ✔Règle 3 : Le consommateur ne peut prélever un objet que le producteur est en train de ranger ✔Règle 4 : Si le producteur (resp. consommateur) est en attente parce que le tampon est plein (resp. vide), il doit être averti dès que cette condition cesse d'être vraie. 9/21 IPC : Le modèle du producteur – consommateur (3/5) ●Le tampon peut être représenté par une liste circulaire ●NPLEIN : nombre d'objets dans le tampon (début : 0) ●NVIDE : nombre d'emplacements disponibles dans le tampon (N au début). ● 10/21 IPC : Le modèle du producteur – consommateur (4/5) 11/21 IPC : Le modèle du producteur – consommateur (5/5) 12/21 Solution avec les sémaphores ●Cas où le nombre de producteur (consommateur) est supérieur à 1 ✔Analyser et traiter en cours 13/21 Solution avec un compteur d'événements (1/2) ●Trois primitives permettent de manipuler une variable compteur d'événements E, ✔Read(E) donne la valeur de E ✔Advance(E) incrémente E de 1 de manière atomique ✔Await(E , v) attend que E ≥ v ●constante TAILLE /* nombre de places dans le tampon */ ●compteur_d_événements in = 0, /* nb d'objets mis dans le tampon */ out = 0 /* nb d'objets retirés du tampon */ 14/21 Solution avec un compteur d'événements (2/2) 15/21 Autres solutions ●Solution avec un moniteur ●Solution avec échanges de messages ● 16/21 ORDONNANCEMENT DES PROCESSUS (1/2) ●L'ordonnanceur définit l'ordre dans lequel les processus prêts utilisent l'UC et la durée d'utilisation, en utilisant un algorithme d'ordonnancement ●Un bon algorithme d'ordonnancement doit posséder les qualités suivantes : ✔équitabilité : chaque processus reçoit sa part du temps processeur ✔efficacité : le processeur doit travailler à 100 % du temps ✔temps de réponse : à minimiser en mode interactif ✔temps d'exécution : minimiser l'attente des travaux en traitement par lots (batch) ✔rendement : maximiser le nombre de travaux effectués par unité de temps 17/21 ORDONNANCEMENT DES PROCESSUS (2/2) ●On appelle temps de traitement moyen d'un système de tâches la moyenne des intervalles de temps séparant la soumission d'une tâche de sa fin d'exécution ●On appelle temps de traitement moyen d'un système de tâches la moyenne des intervalles de temps séparant la soumission d'une tâche de sa fin d'exécution. ●On appelle assignation la description de l'exécution des tâches sur le ou les processeurs. 18/21 Quelques algorithmes d’ordonnancement ●Ordonnancement circulaire ou tourniquet (round robin) ✔L'ordonnanceur gère une liste circulaire de processus. Chaque processus dispose d'un quantum de temps pendant lequel il est autorisé à s'exécuter ●Ordonnancement PCTER ✔à la fin de chaque quantum, on élit la tâche dont le temps d'exécution restant est minimal ●Ordonnancement avec priorité ✔L'ordonnanceur lance le processus prêt de priorité la plus élevée. ✔L'ordonnanceur abaisse à chaque interruption d'horloge la priorité du processus actif 19/21 Quelques algorithmes d’ordonnancement ●Ordonnancement avec files multiples ✔On associe une file d'attente et un algorithme d'ordonnancement à chaque niveau de priorité ●Ordonnancement dictée par une politique ✔Le SE mémorise combien chaque utilisateur a consommé de temps processeur et il calcule le rapport: temps processeur consommé/temps processeur auquel on a droit. ✔On élit le processus qui offre le rapport le plus faible jusqu'à ce que son rapport cesse d'être le plus faible 20/21 Quelques algorithmes d’ordonnancement ●Ordonnancement à deux niveaux ✔La taille de la mémoire centrale : certains processus contraints de résider sur disque ✔Un ordonnanceur de bas niveau (CPU scheduler) applique l'un des algorithmes précédents aux processus résidant en mémoire centrale ✔Un ordonnanceur de haut niveau (medium term scheduler) retire de la mémoire les processus qui y sont resté assez longtemps ✔Il peut exister un ordonnanceur à long terme (job scheduler) qui détermine si un processus utilisateur qui le demande peut effectivement entrer dans le système 21/21 Quelques algorithmes d’ordonnancement ●Ordonnancement à deux niveaux ✔L'ordonnanceur de haut niveau prend en compte les points suivants : ➔depuis combien de temps le processus séjourne-t-il en mémoire ou sur disque ? ➔combien de temps processeur le processus a-t-il eu récemment ? ➔quelle est la priorité du processus ? ➔quelle est la taille du processus ? (s'il est petit, on le logera sans problème) uploads/Philosophie/ info208-se-seance-4-5-problemeclassique-ipc-ordonancement-pdf.pdf