Remerciez-le!

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

Master-Genie industriel et Logistique-ENSAK Ordonnancement des Processus et Ate

Master-Genie industriel et Logistique-ENSAK Ordonnancement des Processus et Atelier Flexible Pr. M. AZHARI A.U. 2021-2022 1/61 Mourad AZHARI Cours de l’ordonnancement des processus et AF Master-Genie industriel et Logistique-ENSAK Introduction Concepts clefs sur l’odonnancement des processus un processus (process) en informatique : un programme en cours d’ex´ ecution par un ordinateur. Il permet d’ex´ ecuter un ensemble d’instructions un processeur (CPU Central Processing Unit): a pour mission de r´ ealiser les diff´ erents calculs inh´ erents au bon fonctionnement de l’ordinateur. Il Sert ` a traiter toutes les informations permettant ` a l’ordinateur d’effectuer les tˆ aches demand´ ees par l’utilisateur. Le syst` eme d’exploitation est charg´ e d’allouer les ressources (m´ emoires, temps processeur, entr´ ees/sorties) n´ ecessaires aux processus et d’assurer que le fonctionnement d’un processus n’interf` ere pas avec celui des autres. 2/61 Mourad AZHARI Cours de l’ordonnancement des processus et AF Master-Genie industriel et Logistique-ENSAK Ordonnancement d’un processus qu’est ce qu ’un ordonnancement? permet ` a un syst` eme d’exploitation de g´ erer l’allocation du processeur aux diff´ erents processus ` a ex´ ecuter. un ordonnanceur: est un module du noyau du syst` eme d’exploitation qui choisit les processus qui vont ˆ etre ex´ ecut´ es par les processeurs d’un ordinateur. Crit` eres d’ordonnancement: ordre d’arriv´ ee, Dur´ ee d’ex´ ecution et priorit´ e. Diagramme de Gantt (compl´ ement souvent de diagramme de PERT) permet de r´ ealiser une repr´ esentation sch´ ematique de l’´ evolution des processus dans le temps et de visualiser les diverses tˆ aches composant un projet(des processus ) 3/61 Mourad AZHARI Cours de l’ordonnancement des processus et AF Master-Genie industriel et Logistique-ENSAK ordonnancement d’un processus Algorithmes de l’ordonnancement Un ordonnanceur fait face ` a deux probl` emes principaux : le choix du processus ` a ex´ ecuter; le temps d’allocation du processeur au processus choisi. Les algorithmes non-pr´ eemptifs (sans r´ equisition): un processus en ex´ ecution continue jusqu’` a ce qu’il se termine ou se bloque (non ad´ equat pour les syst` emes temps r´ eel et temps partag´ e) 4/61 Mourad AZHARI Cours de l’ordonnancement des processus et AF Master-Genie industriel et Logistique-ENSAK Algorithmes de l’ordonnancement algorithmes non-pr´ eemptifs Les algorithmes pr´ eemptifs ( avec r´ equisition): un processus en ex´ ecution peut ˆ etre interrompu par diverses causes (un nouveau processus arrive, un processus existant est r´ eveill´ e, un temps q s’est ´ ecoul´ e, la priorit´ e d’un processus prˆ et est devenue plus grande que celle du processus actif, ...) 5/61 Mourad AZHARI Cours de l’ordonnancement des processus et AF Master-Genie industriel et Logistique-ENSAK Algorithmes de l’ordonnancement Algorithme non-pr´ eemptif: FIFO L ’organisation de la ﬁle d’attente des processus prˆ ets est donc tout simplement du ”First In First Out” ; FIFO traite les processus dans l’ordre de leur soumission (date d’arriv´ ee) sans aucune consid´ eration de leur temps d’ex´ ecution ; L ’algorithme FIFO consiste ` a choisir ` a un instant donn´ e, le processus qui est depuis le plus longtemps dans la ﬁle d’attente, ce qui revient ` a choisir celui disposant du temps d’arriv´ ee minimal et l’ex´ ecuter pendant un temps d’ex´ ecution bien d´ eﬁnit, Ce proc´ ed´ e est r´ ep´ et´ e jusqu’` a ´ epuisement des processus dans la ﬁle d’attente. 6/61 Mourad AZHARI Cours de l’ordonnancement des processus et AF Master-Genie industriel et Logistique-ENSAK Algorithmes de l’ordonnancement Algorithme non-pr´ eemptif: FIFO 7/61 Mourad AZHARI Cours de l’ordonnancement des processus et AF Master-Genie industriel et Logistique-ENSAK Algorithmes de l’ordonnancement Exercice 1: Algorithme non-pr´ eemptif: FIFO Au temps 0, seulement le processus A est dans le syst` eme et il s’ex´ ecute. Au temps 1 le processus B arrive mais il doit attendre que A termine car il a encore 2 unit´ es de temps. Ensuite B s’ex´ ecute pendant 4 unit´ es de temps. Au temps 4, 6, et 7 les processus C, D et E arrivent mais B a encore 2 unit´ es de temps. Une fois que B a termin´ e, C, D et E entrent au syst` eme dans l’ordre 8/61 Mourad AZHARI Cours de l’ordonnancement des processus et AF Master-Genie industriel et Logistique-ENSAK Algorithmes de l’ordonnancement Exercice 1: Algorithme non-pr´ eemptif: FIFO Le temps de s´ ejour pour chaque processus est obtenu soustrayant le temps d’entr´ ee du processus du temps de terminaison: 9/61 Mourad AZHARI Cours de l’ordonnancement des processus et AF Master-Genie industriel et Logistique-ENSAK Algorithmes de l’ordonnancement Exercice 1: Algorithme non-pr´ eemptif: FIFO 10/61 Mourad AZHARI Cours de l’ordonnancement des processus et AF Master-Genie industriel et Logistique-ENSAK Algorithmes de l’ordonnancement Exercice 2: Algorithme non-pr´ eemptif: FIFO TAF: 1-calculer le temps moyen de s´ ejour. 2-calculerle temps temps moyen d’attente. 3-nombre d’unit´ es de temps par processus 4-Repr´ esenter l’´ evolution des processus par le diagramme de Gantt. 11/61 Mourad AZHARI Cours de l’ordonnancement des processus et AF Master-Genie industriel et Logistique-ENSAK Algorithmes de l’ordonnancement EXERCICE2 QUESTION4: diagramme de Gantt 12/61 Mourad AZHARI Cours de l’ordonnancement des processus et AF Master-Genie industriel et Logistique-ENSAK Algorithmes de l’ordonnancement Algorithme non-pr´ eemptif SJF: Shortest Job First. SJF choisit de fac ¸on prioritaire les processus ayant le plus court temps d’ex´ ecution sans r´ eellement tenir compte de leur date d’arriv´ ee. Ce proc´ ed´ e est r´ ep´ et´ e jusqu’` a ´ epuisement des processus dans la ﬁle d’attente Chaque processus se comporte comme suit : il attend une commande, l’ex´ ecute, attend la commande suivante, et ainsi de suite. Alors parmi les processus prˆ ets, le processus ´ elu est celui dont la commande ` a ex´ ecuter est la plus courte en temps. Le temps d’ex´ ecution de la prochaine commande de chaque processus est estim´ e en se basant sur le comportement pass´ e du processus. 13/61 Mourad AZHARI Cours de l’ordonnancement des processus et AF Master-Genie industriel et Logistique-ENSAK Algorithmes de l’ordonnancement Algorithme non-pr´ eemptif SJF: Shortest Job First. 14/61 Mourad AZHARI Cours de l’ordonnancement des processus et AF Master-Genie industriel et Logistique-ENSAK Algorithmes de l’ordonnancement Algorithme non-pr´ eemptif SJF: Shortest Job First. 15/61 Mourad AZHARI Cours de l’ordonnancement des processus et AF Master-Genie industriel et Logistique-ENSAK Algorithmes de l’ordonnancement Algorithme non-pr´ eemptif SJF: Shortest Job First. 16/61 Mourad AZHARI Cours de l’ordonnancement des processus et AF Master-Genie industriel et Logistique-ENSAK Algorithmes de l’ordonnancement Algorithme non-pr´ eemptif SJF: Shortest Job First. 17/61 Mourad AZHARI Cours de l’ordonnancement des processus et AF Master-Genie industriel et Logistique-ENSAK Algorithmes de l’ordonnancement Algorithme non-pr´ eemptif SJF: Shortest Job First. 18/61 Mourad AZHARI Cours de l’ordonnancement des processus et AF Master-Genie industriel et Logistique-ENSAK Algorithmes de l’ordonnancement Algorithme non-pr´ eemptif SJF: Shortest Job First. 19/61 Mourad AZHARI Cours de l’ordonnancement des processus et AF Master-Genie industriel et Logistique-ENSAK Algorithmes de l’ordonnancement Algorithme non-pr´ eemptif SJF: Shortest Job First. 20/61 Mourad AZHARI Cours de l’ordonnancement des processus et AF Master-Genie industriel et Logistique-ENSAK Algorithmes de l’ordonnancement Algorithme non-pr´ eemptif SJF: Shortest Job First. 21/61 Mourad AZHARI Cours de l’ordonnancement des processus et AF Master-Genie industriel et Logistique-ENSAK Algorithmes de l’ordonnancement Algorithme non-pr´ eemptif SJF: Shortest Job First. 22/61 Mourad AZHARI Cours de l’ordonnancement des processus et AF Master-Genie industriel et Logistique-ENSAK Algorithmes de l’ordonnancement exercice 3 sur SJF avec digramme de Gantt 23/61 Mourad AZHARI Cours de l’ordonnancement des processus et AF Master-Genie industriel et Logistique-ENSAK Algorithmes de l’ordonnancement EXERCICE 4 SUR SJF TAF: 1-calculer le temps moyen de s´ ejour. 2-calculerle temps moyen d’attente. 3-nombre d’unit´ es de temps par processus. 4-Repr´ esenter l’´ evolution des processus par le diagramme de Gantt. 24/61 Mourad AZHARI Cours de l’ordonnancement des processus et AF Master-Genie industriel et Logistique-ENSAK Algorithmes pr´ eemptifs La priorit´ e sans prise en consid´ eration d’une mani` ere g´ en´ erale des donn´ ees dur´ ee d’ex´ ecution et date d’arriv´ ee des processus. associer ` a chaque processus une priorit´ e (la plus grande priorit´ e) Ce proc´ ed´ e est r´ ep´ et´ e jusqu’` a ´ epuisement des processus se trouvant dans la ﬁle d’attente. 25/61 Mourad AZHARI Cours de l’ordonnancement des processus et AF Master-Genie industriel et Logistique-ENSAK Algorithmes pr´ eemptifs La priorit´ e 26/61 Mourad AZHARI Cours de l’ordonnancement des processus et AF Master-Genie industriel et Logistique-ENSAK Algorithmes pr´ eemptifs Deux concepts des Algorithmes pr´ eemptifs contexte de communication/changement de processus: A chaque interruption d’horloge, le syst` eme d’exploitation reprend la main et d´ ecide si le processus courant doit poursuivre son ex´ ecution ou s’il doit ˆ etre suspendu pour laisser place ` a un autre. S’il d´ ecide de suspendre son ex´ ecution au proﬁt d’un autre, il doit d’abord sauvegarder l’´ etat des registres du processeur avant de charger dans les registres les donn´ ees du processus ` a lancer (suspendre ou sauvegarder) quantum:Le temps d’allocation du processeur au processus. la commutation entre les processus exiger un temps nettement inf´ erieur au quantum. 27/61 Mourad AZHARI Cours de l’ordonnancement des processus et AF Master-Genie industriel et Logistique-ENSAK Algorithmes pr´ eemptifs problmes Choix de la valeur du quantum Choix du prochain processus uploads/Industriel/ ordonncement-processus-2.pdf