Le travail le plus court en premier (SJF) : exemple préemptif et non préemptif
Nathaniel Brooks
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 du processus en garantissant que les tâches les plus courtes sont exécutées en premier, et donc éventuellement dans un délai d'exécution court.
- Il améliore le rendement des travaux en proposant des travaux plus courts, qui doivent être exécutés 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 le cycle CPU alloué au processus, le processus le maintient jusqu'à ce qu'il atteigne un état d'attente ou se termine.
Considérez les cinq processus suivants, chacun ayant sa propre heure de rafale et son heure 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) Au temps = 0, P4 arrive et démarre l'exécution.
Étape 1) Au temps = 1, le processus P3 arrive. Mais P4 a encore besoin de 2 unités d’exécution pour être complété. L'exécution se poursuivra.
Étape 2) Au temps =2, le processus P1 arrive et est ajouté à la file d'attente. P4 poursuivra son exécution.
É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.
Étape 4) Au temps = 4, le processus P5 arrive et est ajouté à la file d'attente. P1 poursuivra l'exécution.
Étape 5) Au temps = 5, le processus P2 arrive et est ajouté à la file d'attente. P1 poursuivra l'exécution.
É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.
Étape 7) Au temps = 10, P2 est en cours d'exécution et P3 et P5 sont dans la file d'attente.
É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.
Étape 9) Au temps = 15, le processus P5 terminera son exécution.
Étape 10) Au temps = 23, le processus P3 terminera son exécution.
É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
SJF préemptif
Dans la planification préemptive SJF, les tâches sont placées dans la file d'attente au fur et à mesure de leur arrivée. Un processus avec le temps de rafale le plus court commence son exécution. Si un processus avec un temps de rafale encore plus court arrive, le processus en cours est supprimé ou exclu de l'exécution, et le travail le plus court se voit attribuer un cycle CPU.
Considérez 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) Au temps = 0, P4 arrive et démarre l'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 |
Étape 1) Au temps = 1, le processus P3 arrive. Mais P4 a un temps de rafale plus court. L'exécution se poursuivra.
É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.
É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.
É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 |
Étape 5) Au temps = 5, le processus P2 arrivera. Le temps de rafale de P1, P2, P3 et P5 est comparé. Le processus P2 est exécuté car son temps de rafale est le plus court. 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 |
Étape 6) Au temps =6, P2 est en cours d'exécution.
Étape 7) Au temps =7, P2 termine son exécution. Le temps de rafale de P1, P3 et P5 est comparé. Le processus P5 est exécuté car son temps de rafale est moindre.
| 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 |
Étape 8) Au temps =10, P5 terminera son exécution. Le temps de rafale de P1 et P3 est comparé. Le processus P1 est exécuté car son temps de rafale est inférieur.
Étape 9) Au temps =15, P1 termine son exécution. P3 est le seul processus restant. L'exécution commencera.
Étape 10) Au temps =23, P3 termine son exécution.
É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/avantages de l’utilisation de la méthode SJF :
- SJF est fréquemment utilisé pour la planification à long terme.
- Il réduit le temps d'attente moyen grâce à l'algorithme FIFO (First in First Out).
- La méthode SJF donne le temps d'attente moyen le plus bas 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.
- Probablement optimal en ce qui concerne le délai d’exécution moyen.
Inconvénients/Inconvénients de SJF
Voici quelques inconvénients/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 implémenté 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 conduit à une famine qui ne réduit pas le délai d’exécution moyen.
- Il est difficile de connaître la durée de la prochaine requête CPU.
- Le temps écoulé doit être enregistré, ce qui entraîne une surcharge du processeur.
Résumé
- SJF est un algorithme dans lequel le processus ayant le temps d'exécution le plus court est choisi pour la prochaine exécution.
- SJF Scheduling est associé à chaque tâche en tant qu’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.
- Il existe essentiellement deux types de méthodes SJF 1) SJF non préemptif et 2) SJF préemptif.
- Dans la planification non préemptive, une fois le cycle CPU alloué au processus, le processus le maintient jusqu'à ce qu'il atteigne un état d'attente ou se termine.
- Dans la planification préemptive SJF, les tâches sont placées dans la file d'attente au fur et à mesure de leur arrivée.
- Bien qu'un processus avec un temps de rafale court démarre, le processus en cours est supprimé ou empêché d'être exécuté, et le travail le plus court est exécuté en premier.
- SJF est fréquemment utilisé pour la planification à long terme.
- Il réduit le temps d'attente moyen grâce à l'algorithme FIFO (First in First Out).
- Dans la planification SJF, l’heure d’achèvement du travail doit être connue plus tôt, mais elle est difficile à prédire.
- SJF ne peut pas être implémenté pour la planification du processeur à court terme. En effet, il n’existe aucune méthode spécifique pour prédire la durée de la prochaine rafale du processeur.
