Le travail le plus court en premier (SJF) : exemple préemptif et non préemptif

Par : Nathaniel Brooks Nathaniel Brooks
Hours Le kit de préparation mis à jour

⚡ Résumé intelligent

L'algorithme Shortest Job First (SJF) est un algorithme d'ordonnancement du processeur qui sélectionne le processus ayant le temps d'exécution le plus court pour le lancer ensuite. Il peut être préemptif ou non préemptif et réduit considérablement le temps d'attente moyen des processus.

  • ️ Définition: Le processus présentant la durée d'exécution la plus courte est sélectionné pour la prochaine exécution.
  • 🔀 Deux types: Le SJF peut être non préemptif ou préemptif (temps restant le plus court en premier).
  • (I.e. Avantage clé : Elle indique le temps d'attente moyen le plus court pour un ensemble de processus donné.
  • (I.e. Utilisation optimale : Idéal pour les systèmes de traitement par lots où la durée d'exécution des tâches est connue à l'avance.
  • ❓ Principale limitation : La durée de l'impulsion doit être connue à l'avance, ce qui est difficile à prévoir.
  • ⚠️ Risque: Les processus longs risquent de s'enliser si les tâches courtes continuent d'affluer.
En savoir plus

Planification selon la méthode du travail le plus court (SJF)

Qu'est-ce que la planification du travail le plus court en premier ?

Travail le plus court d'abord (SJF) est un algorithme dans lequel le processus ayant le temps d'exécution le plus petit est choisi pour la prochaine exécution. Cette méthode de planification peut être préemptive ou non préemptive. Cela réduit considérablement le temps d’attente moyen des autres processus en attente d’exécution. La forme complète de SJF est le travail le plus court en premier.

Il existe essentiellement deux types de méthodes SJF :

  • SJF non préemptif
  • SJF préemptif

Caractéristiques de la planification SJF

  • Il est associé à chaque tâche comme unité de temps à accomplir.
  • Cette méthode d'algorithme est utile pour le traitement par lots, où l'attente de la fin des tâches n'est pas critique.
  • Cela peut améliorer le débit des processus en veillant à ce que les tâches les plus courtes soient exécutées en premier, ce qui permet potentiellement de réduire le temps d'exécution.
  • Cela améliore la productivité en proposant des tâches plus courtes, qui doivent être exécutées en premier et qui ont généralement un délai d'exécution plus court.

SJF non préemptif

Dans la planification non préemptive, une fois que le cycle CPU est alloué à un processus, celui-ci le conserve jusqu'à ce qu'il atteigne un état d'attente ou qu'il soit terminé.

Considérons les cinq processus suivants, chacun ayant son propre temps d'explosion et son propre temps d'arrivée.

File d'attente de processus Temps de rafale Heure d'arrivée
P1 6 2
P2 2 5
P3 8 1
P4 3 0
P5 4 4

Étape 0) À l'instant t = 0, P4 arrive et commence son exécution.

SJF non préemptif

Étape 1) À l'instant t = 1, le processus P3 arrive. Mais P4 a encore besoin de 2 unités d'exécution pour se terminer. Il va donc poursuivre son exécution.

SJF non préemptif

Étape 2) Au temps = 2, le processus P1 arrive et est ajouté à la file d'attente. P4 poursuivra l'exécution.

SJF non préemptif

Étape 3) Au temps = 3, le processus P4 terminera son exécution. Le temps de rafale de P3 et P1 est comparé. Le processus P1 est exécuté car son temps de rafale est inférieur à celui de P3.

SJF non préemptif

Étape 4) Au temps = 4, le processus P5 arrive et est ajouté à la file d'attente. P1 poursuivra l'exécution.

SJF non préemptif

Étape 5) Au temps = 5, le processus P2 arrive et est ajouté à la file d'attente. P1 poursuivra l'exécution.

SJF non préemptif

Étape 6) Au temps = 9, le processus P1 terminera son exécution. Le temps de rafale de P3, P5 et P2 est comparé. Le processus P2 est exécuté car son temps de rafale est le plus faible.

SJF non préemptif

Étape 7) À l'instant t = 10, P2 est en cours d'exécution et P3 et P5 sont dans la file d'attente.

SJF non préemptif

Étape 8) Au temps = 11, le processus P2 terminera son exécution. Le temps de rafale de P3 et P5 est comparé. Le processus P5 est exécuté car son temps de rafale est inférieur.

SJF non préemptif

Étape 9) Au temps = 15, le processus P5 terminera son exécution.

SJF non préemptif

Étape 10) Au temps = 23, le processus P3 terminera son exécution.

SJF non préemptif

Étape 11) Calculons le temps d'attente moyen pour l'exemple ci-dessus.

Wait time
P4 = 0 - 0 = 0
P1 = 3 - 2 = 1
P2 = 9 - 5 = 4
P5 = 11 - 4 = 7
P3 = 15 - 1 = 14
Average Waiting Time = (0 + 1 + 4 + 7 + 14)/5 = 26/5 = 5.2

ARTICLES LIÉS

SJF préemptif

Dans l'ordonnancement SJF préemptif, les tâches sont placées dans la file d'attente des tâches prêtes dès leur arrivée. Le processus ayant la durée d'exécution la plus courte démarre. Si un processus avec une durée d'exécution encore plus courte arrive, le processus en cours est retiré ou préempté, et un cycle CPU est alloué à la tâche la plus rapide.

Considérons les cinq processus suivants :

File d'attente de processus Temps de rafale Heure d'arrivée
P1 6 2
P2 2 5
P3 8 1
P4 3 0
P5 4 4

Étape 0) À l'instant t = 0, P4 arrive et commence son exécution.

File d'attente de processus Temps de rafale Heure d'arrivée
P1 6 2
P2 2 5
P3 8 1
P4 3 0
P5 4 4

SJF préemptif

Étape 1) À l'instant t = 1, le processus P3 arrive. Mais P4 a une durée d'exécution plus courte. Il poursuivra donc son exécution.

SJF préemptif

Étape 2) Au temps = 2, le processus P1 arrive avec un temps de rafale = 6. Le temps de rafale est supérieur à celui de P4. Par conséquent, P4 poursuivra son exécution.

SJF préemptif

Étape 3) Au temps = 3, le processus P4 terminera son exécution. Le temps de rafale de P3 et P1 est comparé. Le processus P1 est exécuté car son temps de rafale est inférieur.

SJF préemptif

Étape 4) Au temps = 4, le processus P5 arrivera. Le temps de rafale de P3, P5 et P1 est comparé. Le processus P5 est exécuté car son temps de rafale est le plus faible. Le processus P1 est préempté.

File d'attente de processus Temps de rafale Heure d'arrivée
P1 Il en reste 5 sur 6 2
P2 2 5
P3 8 1
P4 3 0
P5 4 4

SJF préemptif

Étape 5) À l'instant t = 5, le processus P2 arrive. Les durées d'exécution des processus P1, P2, P3 et P5 sont comparées. Le processus P2 est exécuté car sa durée d'exécution est la plus courte. Le processus P5 est préempté.

File d'attente de processus Temps de rafale Heure d'arrivée
P1 Il en reste 5 sur 6 2
P2 2 5
P3 8 1
P4 3 0
P5 Il en reste 3 sur 4 4

SJF préemptif

Étape 6) À l'instant = 6, P2 est en cours d'exécution.

SJF préemptif

Étape 7) À l'instant t = 7, P2 termine son exécution. Les durées d'exécution de P1, P3 et P5 sont comparées. Le processus P5 est exécuté car sa durée d'exécution est plus courte.

File d'attente de processus Temps de rafale Heure d'arrivée
P1 Il en reste 5 sur 6 2
P2 2 5
P3 8 1
P4 3 0
P5 Il en reste 3 sur 4 4

SJF préemptif

Étape 8) À l'instant t = 10, P5 aura terminé son exécution. Les durées d'exécution de P1 et P3 sont comparées. Le processus P1 est exécuté car sa durée d'exécution est plus courte.

SJF préemptif

Étape 9) À l'instant t = 15, P1 termine son exécution. Seul P3 reste en cours d'exécution.

SJF préemptif

Étape 10) À l'instant = 23, P3 termine son exécution.

SJF préemptif

Étape 11) Calculons le temps d'attente moyen pour l'exemple ci-dessus.

Wait time
P4 = 0 - 0 = 0
P1 = (3 - 2) + 6 = 7
P2 = 5 - 5 = 0
P5 = 4 - 4 + 2 = 2
P3 = 15 - 1 = 14
Average Waiting Time = (0 + 7 + 0 + 2 + 14)/5 = 23/5 = 4.6

Avantages du SJF

Voici les avantages de la méthode SJF :

  • SJF est fréquemment utilisé pour la planification à long terme.
  • Il réduit le temps d'attente moyen par rapport à l'algorithme FIFO (Premier entré, premier sorti).
  • La méthode SJF offre le temps d'attente moyen le plus court pour un ensemble spécifique de processus.
  • Il convient aux tâches exécutées par lots, pour lesquelles les temps d'exécution sont connus à l'avance.
  • Pour le système par lots de planification à long terme, une estimation du temps de rafale peut être obtenue à partir de la description de poste.
  • Pour la planification à court terme, nous devons prédire la valeur de la prochaine heure de rafale.
  • C'est probablement optimal en ce qui concerne le délai d'exécution moyen.

Inconvénients/Inconvénients de SJF

Voici quelques inconvénients de l'algorithme SJF :

  • Le délai d’achèvement des travaux doit être connu plus tôt, mais il est difficile de le prévoir.
  • Il est souvent utilisé dans un système par lots pour la planification à long terme.
  • SJF ne peut pas être mis en œuvre pour Ordonnancement du processeur pour le court terme. En effet, il n’existe aucune méthode spécifique pour prédire la durée de la prochaine rafale du processeur.
  • Cet algorithme peut entraîner des délais d’exécution très longs, voire la famine.
  • Nécessite de connaître la durée d'exécution d'un processus ou d'un travail.
  • Cela engendre une pénurie de main-d'œuvre qui ne réduit pas le délai de traitement moyen.
  • Il est difficile de connaître la durée de la prochaine requête CPU.
  • Il convient d'enregistrer le temps écoulé, ce qui engendre une charge supplémentaire pour le processeur.

FAQ

SRTF (Shortest Remaining Time First) est simplement la version préemptive de SJF. Dans SJF, une tâche en cours se termine avant que la suivante ne soit sélectionnée. Dans SRTF, une tâche nouvellement arrivée avec un temps restant plus court peut prendre la place de la tâche en cours.

SJF privilégie toujours la tâche la plus courte. Si des processus courts arrivent continuellement, un processus long risque de ne jamais obtenir le CPU et d'attendre indéfiniment. C'est ce qu'on appelle la famine. Le vieillissement, qui augmente progressivement la priorité d'une tâche en attente, permet d'éviter ce problème.

Oui. Il est prouvé que SJF est optimal car il minimise le temps d'attente moyen pour un ensemble de processus donné. Cependant, cela n'est vrai que si les durées des rafales sont connues à l'avance, ce qui est rarement possible en pratique.

L'IA et l'apprentissage automatique peuvent analyser l'historique d'un processus, les caractéristiques de son code et ses exécutions précédentes afin d'estimer son temps d'exécution CPU maximal. Des prédictions plus précises rendent SJF plus performant, réduisant ainsi le temps d'attente par rapport aux estimations traditionnelles basées sur la moyenne exponentielle.

C'est possible. SJF peine à gérer la planification à court terme car la durée des pics d'activité est inconnue. Une IA capable de prédire ces pics en temps réel pourrait rendre SJF utilisable, mais la surcharge liée à la prédiction et les erreurs doivent rester suffisamment faibles pour que la décision de planification demeure pertinente.

Résumez cet article avec :