Qu'est-ce que la planification de la première tâche la plus courte?
Shortest Job First (SJF) est un algorithme dans lequel le processus ayant le plus petit temps d'exécution est choisi pour la prochaine exécution. Cette méthode de planification peut être préventive ou non préventive. Cela réduit considérablement le temps d'attente moyen pour les autres processus en attente d'exécution. La forme complète de SJF est le travail le plus court d'abord.
Il existe essentiellement deux types de méthodes SJF:
- SJF non préventif
- SJF préventif
Dans ce didacticiel sur le système d'exploitation, vous apprendrez:
- Qu'est-ce que la planification de la première tâche la plus courte?
- Caractéristiques de la planification SJF
- SJF non préventif
- SJF préventif
- Avantages de SJF
- Inconvénients / inconvénients de SJF
Caractéristiques de la planification SJF
- Il est associé à chaque tâche comme une unité de temps à terminer.
- Cette méthode d'algorithme est utile pour le traitement par lots, où l'attente de la fin des travaux n'est pas critique.
- Il peut améliorer le débit du processus en veillant à ce que les travaux plus courts soient exécutés en premier, et donc éventuellement dans un délai d'exécution court.
- Il améliore la sortie des travaux en offrant des travaux plus courts, qui doivent être exécutés en premier, qui ont généralement un délai d'exécution plus court.
SJF non préventif
Dans la planification non préemptive, une fois que le cycle CPU est 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 ayant chacun leur propre heure de rafale et 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 commence 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 terminer. Il continuera l'exécution.
Étape 2) Au temps = 2, le processus P1 arrive et est ajouté à la file d'attente. P4 continuera l'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 à P3.
Étape 4) Au temps = 4, le processus P5 arrive et est ajouté à la file d'attente. P1 continuera l'exécution.
Étape 5) Au temps = 5, le processus P2 arrive et est ajouté à la file d'attente. P1 continuera 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 bas.
É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 timeP4= 0-0=0P1= 3-2=1P2= 9-5=4P5= 11-4=7P3= 15-1=14
Average Waiting Time= 0+1+4+7+14/5 = 26/5 = 5.2
SJF préventif
Dans la planification SJF préemptive, les travaux sont placés dans la file d'attente prête au fur et à mesure qu'ils arrivent. Un processus avec le temps de rafale le plus court commence l'exécution. Si un processus avec un temps de rafale encore plus court arrive, le processus en cours est supprimé ou préempté de l'exécution, et le travail le plus court est alloué au 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 commence 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. Il continuera l'exécution.
É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 continuera l'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 bas. Le processus P1 est préempté.
| File d'attente de processus | Temps de rafale | Heure d'arrivée |
| P1 | Il 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 petit. Le processus P5 est préempté.
| File d'attente de processus | Temps de rafale | Heure d'arrivée |
| P1 | Il reste 5 sur 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | Il 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 reste 5 sur 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | Il 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 sa durée de rafale est inférieure.
Étape 9) Au temps = 15, P1 termine son exécution. P3 est le seul processus qui reste. Il commencera l'exécution.
Étape 10) Au temps = 23, P3 termine son exécution.
Étape 11) Calculons le temps d'attente moyen pour l'exemple ci-dessus.
Wait timeP4= 0-0=0P1= (3-2) + 6 =7P2= 5-5 = 0P5= 4-4+2 =2P3= 15-1 = 14
Average Waiting Time = 0+7+0+2+14/5 = 23/5 =4.6
Avantages de 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 sur 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 travaux exécutés par lots, pour lesquels 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 temps d'achèvement des travaux doit être connu plus tôt, mais il est difficile à 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 la planification du processeur à court terme. C'est parce qu'il n'y a pas de méthode spécifique pour prédire la longueur de la prochaine rafale CPU.
- Cet algorithme peut entraîner des délais d'exécution très longs ou une famine.
- Nécessite la connaissance de la durée d'exécution d'un processus ou d'une tâche.
- Cela conduit à la famine qui ne réduit pas le temps de traitement moyen.
- Il est difficile de connaître la longueur 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 plus petit temps d'exécution est choisi pour la prochaine exécution.
- La planification SJF est associée à chaque travail comme une unité de temps à terminer.
- Cette méthode d'algorithme est utile pour le traitement par lots, où l'attente de la fin des travaux 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 que le cycle CPU est alloué au processus, le processus le maintient jusqu'à ce qu'il atteigne un état d'attente ou se termine.
- Dans la planification SJF préemptive, les travaux sont placés dans la file d'attente prête au fur et à mesure qu'ils arrivent.
- Bien qu'un processus avec un temps de rafale court commence, le processus en cours est supprimé ou préempté de l'exécution, et le travail qui est 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 sur l'algorithme FIFO (First in First Out).
- Dans la planification SJF, l'heure de fin de la tâche doit être connue plus tôt, mais elle est difficile à prévoir.
- SJF ne peut pas être implémenté pour la planification du processeur à court terme. C'est parce qu'il n'y a pas de méthode spécifique pour prédire la longueur de la prochaine rafale CPU.