Dans ce didacticiel, nous allons apprendre un concept important dans les algorithmes de planification des processus CPU. Le nom important du concept est Premier arrivé, premier servi. Il s'agit de l'algorithme de base que chaque étudiant doit apprendre pour comprendre toutes les bases des algorithmes de planification des processus CPU.
Le premier arrivé, premier servi ouvre la voie à la compréhension d’autres algorithmes. Cet algorithme peut présenter de nombreux inconvénients. Mais ces inconvénients ont donné naissance à des algorithmes très nouveaux et efficaces. Il est donc de notre responsabilité de nous renseigner sur les algorithmes de planification des processus CPU, premier arrivé, premier servi.
Abréviations importantes
- CPU - - - > Unité centrale de traitement
- FCFS - - -> > Premier arrivé, premier servi
- AT - - -> Heure d'arrivée
- BT - - -> > Temps de rafale
- WT - - -> Temps d'attente
- TAT - - - > Délai d'exécution
- CT - - - > Temps d'achèvement
- FIFO - - - > Premier entré, premier sorti
Premier arrivé premier servi
L'algorithme de planification du processeur premier arrivé, premier servi, brièvement connu sous le nom de FCFS, est le premier algorithme d'algorithme de planification des processus CPU. Dans l’algorithme premier arrivé, premier servi, nous permettons au processus de s’exécuter de manière linéaire.
Cela signifie que quel que soit le processus qui entre en premier dans la file d'attente prête, il est exécuté en premier. Cela montre que l'algorithme du premier arrivé, premier servi suit le principe du premier entré, premier sorti (FIFO).
L'algorithme premier arrivé, premier servi peut être exécuté de manière préventive et non préventive. Avant de passer aux exemples, comprenons ce qu'est l'approche préventive et non préventive dans la planification des processus CPU.
Approche préventive
Dans cette instance de planification préventive des processus, le système d'exploitation alloue les ressources à un processus pour une période de temps prédéterminée. Le processus passe de l'état d'exécution à l'état prêt ou de l'état d'attente à l'état prêt pendant l'allocation des ressources. Cette commutation se produit parce que le processeur peut attribuer la priorité à d’autres processus et remplacer le processus actuellement actif par le processus de priorité plus élevée.
Approche non préventive
Dans ce cas de planification de processus non préemptive, la ressource ne peut pas être retirée d'un processus avant la fin de son exécution. Lorsqu'un processus en cours se termine et passe à l'état d'attente, les ressources sont commutées.
Effet de convoi dans le premier arrivé, premier servi (FCFS)
L'effet de convoi est un phénomène qui se produit dans l'algorithme de planification nommé premier arrivé, premier servi (FCFS). L'algorithme de planification premier arrivé, premier servi se produit de manière non préventive.
La méthode non préemptive signifie que si un processus ou un travail démarre, le système d'exploitation doit terminer son processus ou son travail. Jusqu'à ce que le processus ou le travail soit nul, le nouveau ou le prochain processus ou travail ne démarre pas son exécution. La définition de la planification non préemptive en termes de système d'exploitation signifie que l'unité centrale de traitement (CPU) sera entièrement dédiée jusqu'à la fin du processus ou du travail démarré en premier et que le nouveau processus ou travail n'est exécuté qu'après la fin de l'ancien processus ou emploi.
Il peut y avoir quelques cas qui peuvent amener l'unité centrale de traitement (CPU) à allouer trop de temps. En effet, dans l'approche non préemptive de l'algorithme de planification premier arrivé, premier servi, les processus ou les tâches sont choisis dans un ordre sériel. En raison de ces tâches ou processus plus courts, l'exécution des processus ou tâches plus importants prend trop de temps. Pour cette raison, le temps d’attente, le temps d’exécution et le temps d’achèvement sont très élevés.
Ainsi, ici, lorsque le premier processus est volumineux ou que le temps d'achèvement est trop long, cet effet de convoi dans l'algorithme premier arrivé, premier servi se produit.
Supposons que Longer Job prenne un temps infini. Ensuite, les processus restants doivent attendre pendant le même temps infini. En raison de cet effet de convoi créé par le travail plus long, la famine des processus d'attente augmente très rapidement. C’est le plus gros inconvénient de la planification des processus CPU FCFS.
Caractéristiques de la planification des processus CPU FCFS
Les caractéristiques de la planification des processus CPU FCFS sont :
- La mise en œuvre est simple.
- Ne provoque aucune causalité lors de l'utilisation
- Il adopte une stratégie non préventive et préventive.
- Il exécute chaque procédure dans l'ordre dans lequel elles sont reçues.
- L’heure d’arrivée est utilisée comme critère de sélection des procédures.
Avantages de la planification des processus CPU FCFS
Les avantages de la planification des processus CPU FCFS sont :
- Afin d'attribuer les processus, il utilise la file d'attente Premier entré, premier sorti.
- Le processus de planification du processeur FCFS est simple et facile à mettre en œuvre.
- Dans la planification préventive de la situation FCFS, il n'y a aucune chance que le processus soit affamé.
- Comme il n’y a aucune considération de priorité du processus, il s’agit d’un algorithme équitable.
Inconvénients de la planification des processus CPU FCFS
Les inconvénients de la planification des processus CPU FCFS sont :
- L'algorithme de planification du processeur FCFS a un long temps d'attente
- La planification du processeur FCFS favorise le processeur par rapport aux opérations d'entrée ou de sortie.
- Dans FCFS, il y a une chance d’apparition d’un effet de convoi
- Parce que FCFS est si simple, il n’est souvent pas très efficace. Cela va de pair avec des délais d’attente prolongés. Toutes les autres commandes restent inactives si le processeur est occupé à traiter une commande chronophage.
Problèmes dans l'algorithme de planification du processeur premier arrivé, premier servi
python __dict__
Exemple
S. No Process ID Process Name Arrival Time Burst Time _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 1 P 1 A 0 9 2 P 2 B 1 3 3 P 3 C 1 2 4 P 4 D 1 4 5 P 5 E 2 3 6 P 6 F 3 2
Approche non préventive
Maintenant, résolvons ce problème à l'aide de l'algorithme de planification nommé premier arrivé, premier servi dans une approche non préemptive.
Le diagramme de Gantt pour l'exemple 1 ci-dessus est :
Temps d'exécution = Heure d'achèvement - Heure d'arrivée
Temps d'attente = Temps d'exécution - Temps de rafale
Solution à la question ci-dessus, exemple 1
| Oui Non | ID de processus | Heure d'arrivée | Temps de rafale | Le temps d'achèvement | Temps de retournement | Temps d'attente | |
|---|---|---|---|---|---|---|---|
| 1 | P1 | UN | 0 | 9 | 9 | 9 | 0 |
| 2 | P2 | B | 1 | 3 | 12 | onze | 8 |
| 3 | P3 | C | 1 | 2 | 14 | 13 | onze |
| 4 | P4 | D | 1 | 4 | 18 | 17 | 13 |
| 5 | P5 | ET | 2 | 3 | vingt-et-un | 19 | 16 |
| 6 | P6 | F | 3 | 2 | 23 | vingt | 18 |
Le délai moyen de réalisation est de :
CT moyen = ( 9 + 12 + 14 + 18 + 21 + 23 ) / 6
CT moyen = 97/6
CT moyen = 16,16667
Le temps d'attente moyen est de :
WT moyen = ( 0 + 8 + 11 + 13 + 16 + 18 ) /6
WT moyen = 66/6
WT moyen = 11
Le délai d’exécution moyen est de :
TAT moyen = ( 9 + 11 + 13 + 17 + 19 +20 ) / 6
chaîne trouver c++
TAT moyen = 89/6
TAT moyen = 14,83334
C'est ainsi que le FCFS est résolu dans l'approche non préventive.
Voyons maintenant comment ils peuvent être résolus avec une approche préventive.
Approche préventive
Maintenant, résolvons ce problème à l'aide de l'algorithme de planification nommé premier arrivé, premier servi dans une approche préventive.
Dans l'approche préventive, nous recherchons le meilleur processus disponible
Le diagramme de Gantt pour l'exemple 1 ci-dessus est :
| Oui Non | ID de processus | Heure d'arrivée | Temps de rafale | Le temps d'achèvement | Temps de retournement | Temps d'attente | |
|---|---|---|---|---|---|---|---|
| 1 | P1 | UN | 0 | 9 | 23 | 23 | 14 |
| 2 | P2 | B | 1 | 3 | 8 | 7 | 4 |
| 3 | P3 | C | 1 | 2 | 3 | 2 | 0 |
| 4 | P4 | D | 1 | 4 | quinze | 14 | dix |
| 5 | P5 | ET | 2 | 3 | onze | 9 | 7 |
| 6 | P6 | F | 3 | 2 | 5 | 2 | 0 |
| suivant → ← précédent Pour résoudre le problème du gaspillage des signaux de réveil, Dijkstra a proposé une approche qui consiste à stocker tous les appels de réveil. Dijkstra déclare qu'au lieu de donner le signal d'alarme directement au consommateur, le producteur peut stocker le signal d'alarme dans une variable. N'importe quel consommateur peut le lire quand il en a besoin. Le sémaphore est la variable qui stocke l'intégralité des appels de réveil transférés du producteur au consommateur. C'est une variable sur laquelle la lecture, la modification et la mise à jour s'effectuent automatiquement en mode noyau. Le sémaphore ne peut pas être implémenté en mode utilisateur car une situation de concurrence critique peut toujours survenir lorsque deux processus ou plus tentent d'accéder simultanément à la variable. Il a toujours besoin du support du système d’exploitation pour être mis en œuvre. Selon les besoins de la situation, le Sémaphore peut être divisé en deux catégories.
Nous discuterons de chacun en détail. |