Algorithmes d’ordonnancement non préemptifs SJF (PDF)

page < Algorithmes d’ordonnancement non préemptifs « SJF » (1/4)  SJF (Shortest Job First) : Le plus court d’abord (VF)  Il lui alloue le processeur jusqu’à ce qu’il se termine ou qu’il se bloque (en attente d’un événement ex : E/S).  Il n’y a pas de réquisition.  Cet algorithme appart...

page < Algorithmes d’ordonnancement non préemptifs « SJF » (1/4)  SJF (Shortest Job First) : Le plus court d’abord (VF)  Il lui alloue le processeur jusqu’à ce qu’il se termine ou qu’il se bloque (en attente d’un événement ex : E/S).  Il n’y a pas de réquisition.  Cet algorithme appartient à la catégorie des ordonnancements par priorité, où la priorité, définie dynamiquement en fonction de la durée d’exécution /> 169 1 0 1 1 0 1 1 0 1 1 0 1 1 0 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 1 0 1 1 0 1 1 0 1 1 1 1 1 0 1 < Algorithmes d’ordonnancement non préemptifs « SJF » (2/4)  Règle principale : Une fois qu'un processus commence à s'exécuter, il ne peut pas être interrompu avant la fin de son exécution.  Fonctionnement :  Les processus sont triés par ordre croissant de leur temps d'exécution.  En cas d'égalité des durées d'exécution, on applique le First Come First Serve (FCFS) pour départager les processus arrivés simultanément. /> 170 1 0 1 1 0 1 1 0 1 1 0 1 1 0 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 1 0 1 1 0 1 1 0 1 1 1 1 1 0 1 1  page < Algorithmes d’ordonnancement non préemptifs « SJF » (3/4)  Principe : Le processus dont le temps d'exécution «burst time» est le plus court est ordonnancé en priorité.  Avantage : SJF réduit le temps d'attente des processus.  Inconvénients :  Nécessite de connaître les temps d'exécution à l'avance, ce qui est souvent difficile dans la pratique.  Famine pour les processus longs. /> 171 1 0 1 1 0 1 1 0 1 1 0 1 1 0 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 1 0 1 1 0 1 1 0 1 1 1 1 1 0 1 < Algorithmes d’ordonnancement non préemptifs « SJF » (4/4)  Exemple : (P1, P2, P3 et P4 arrivent dans cet ordre à t = 0) 1 0 1 1 0 1 1 0 1 1 0 1 1 0 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 1 0 1 1 0 />1 1172 1 1 0 1 1 1 0 1 2  page < Exercice : SJF non préemptif  Cette fois, appliquez l'algorithme SJF (non préemptif) Processus Temps d'arrivée Temps d'exécution P1 0 4 P2 1 3 P3 2 5 P4 3 2 1. Dessinez le diagramme de Gantt (correspondant à 3. Déduisez les temps l'algorithme SJF non préemptif) moyens pour chaque 2. Calculez pour chaque processus : métrique. a. Temps de rotation 4. Expliquez l'intérêt b. Temps d'attente de l'algorithme SJF par rapport à FIFO c. Le rendement pour chaque processus dans ce cas. 1 0 1 1 0 1 1 0 1 1 0 1 1 0 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 1 0 1 1 0 1 1 0 1 1 1 />1 1173 0 1 < Exercice : SJF non préemptif (Correction 1/4) 1. Diagramme de Gantt Processus P1 (4) P1 P2 (3) P2 P3 (5) P3 P4 (2) P4 0 4 6 9 14 Temps 1 0 1 1 0 1 1 0 1 1 0 1 1 0 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 1 0 1 1 0 1 1 0 1 1 1 />1 1174 0 1 3  page < Exercice : SJF non préemptif (Correction 2/4) 2. Calcul des Temps 𝐴𝑖 Fin 𝑇𝑅𝑖 𝑇𝐴𝑖 𝑅𝑖 Processus 𝑇𝑒𝑥𝑒𝑐 execution P1 0 4 4 4-0=4 4-4=0 4/4=1 P2 1 3 9 9-1=8 8-3=5 3/8≈0,38 P3 2 5 14 14-2=12 12-5=7 5/12≈0,42 P4 3 2 6 6-3=3 3-2=1 2/3 ≈ 0,667 1 0 1 1 0 1 1 0 1 1 0 1 1 0 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 1 0 1 1 0 1 1 0 1 1 1 />1 1175 0 1 < Exercice : SJF non préemptif (Correction 3/4) 3. Calcul des Moyennes a. Temps moyen de rotation : ( ) 𝑇𝑚𝑜𝑦𝑒𝑛_𝑟𝑜𝑡𝑎𝑡𝑖𝑜𝑛 = = 6,75 b. Temps moyen d’attente : ( ) 𝑇𝑚𝑜𝑦𝑒𝑛_𝑎𝑡𝑡𝑒𝑛𝑡𝑒 = = 3,25 c. Temps moyen de rendement : ( , , , ) 𝑇𝑚𝑜𝑦𝑒𝑛_𝑟𝑒𝑛𝑑𝑒𝑚𝑒𝑛𝑡 = ≈ 0,62 1 0 1 1 0 1 1 0 1 1 0 1 1 0 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 1 0 1 1 0 1 1 0 1 1 1 />1 1176 0 1 4  page < Exercice : SJF non préemptif (Correction 4/4) 4. Intérêt de SJF par rapport à FIFO  SJF réduit le TRM (6.75 vs 7.75).  Il diminue également le TAM (3.25 vs 4.25).  Le rendement moyen est plus élevé avec SJF (0.62 vs 0.55), ce qui indique une meilleure utilisation des ressources.  L'algorithme SJF réduit les délais moyens en priorisant les processus les plus courts, optimisant ainsi l'efficacité du système. 1 0 1 1 0 1 1 0 1 1 0 1 1 0 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 1 0 1 1 0 />1 1177 1 1 0 1 1 1 0 1 < Algorithmes d’ordonnancement préemptifs « SRTF » (1/4)  SJF Préemptif (VF)“Shortest Remaining Time First, SRTF” (VO)  Temps Restant le Plus Court d’Abord  Règle principale : Si un nouveau processus arrive et que son temps d'exécution restant est plus court que celui du processus en cours d'exécution, ce dernier est préempté. /> 178 1 0 1 1 0 1 1 0 1 1 0 1 1 0 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 1 0 1 1 0 1 1 0 1 1 1 1 1 0 1 5  page < Algorithmes d’ordonnancement préemptifs « SRTF » (2/4)  Fonctionnement :  Le processus avec le plus court temps restant est toujours priorisé.  Le contexte d'exécution est sauvegardé et repris ultérieurement si un processus est interrompu. /> 179 1 0 1 1 0 1 1 0 1 1 0 1 1 0 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 1 0 1 1 0 1 1 0 1 1 1 1 1 0 1 < Algorithmes d’ordonnancement préemptifs « SRTF » (3/4)  Avantage :  Minimise davantage le temps d'attente moyen par rapport à la version non-préemptive.  Inconvénients :  Entraîne une surcharge liée aux changements fréquents de contexte.  Toujours sujet à la famine pour les processus longs.  Difficile de prédire le futur /> 180 1 0 1 1 0 1 1 0 1 1 0 1 1 0 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 1 0 1 1 0 1 1 0 1 1 1 1 1 0 1 6  page < Algorithmes d’ordonnancement préemptifs « SRTF » (4/4)  Exemple :(P3 et P4 arrivent à t = 0; P2 à t = 20; P1 à t = 50) 1 0 1 1 0 1 1 0 1 1 0 1 1 0 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 1 0 1 1 0 /> 1 1181 1 1 0 1 1 1 0 1 7