Algorithme de planification FCFS : qu'est-ce que c'est, exemple de programme
Nathaniel Brooks
Qu'est-ce que la méthode du premier arrivé, premier servi ?
Premier arrivé, premier servi (FCFS) est un algorithme de planification du système d'exploitation qui exécute automatiquement les requêtes et les processus en file d'attente par ordre d'arrivée. Il s’agit de l’algorithme de planification CPU le plus simple et le plus simple. Dans ce type d'algorithme, les processus qui demandent le CPU en premier obtiennent en premier l'allocation de CPU. Ceci est géré avec une file d'attente FIFO. La forme complète du FCFS est le premier arrivé, premier servi.
Lorsque le processus entre dans la file d'attente prête, son PCB (Process Control Block) est lié à la queue de la file d'attente et, lorsque le CPU devient libre, il doit être affecté au processus au début de la file d'attente.
Caractéristiques de la méthode FCFS
- Il prend en charge l'algorithme de planification non préemptif et préemptif.
- Les travaux sont toujours exécutés selon le principe du premier arrivé, premier servi.
- Il est facile à mettre en œuvre et à utiliser.
- Cette méthode est peu performante et le temps d’attente général est assez élevé.
Exemple de planification FCFS
Un exemple concret de la méthode FCFS consiste à acheter un billet de cinéma au guichet. Dans cet algorithme de planification, une personne est servie selon le mode de file d'attente. La personne qui arrive en premier dans la file d'attente achète d'abord le billet, puis le suivant. Cela continuera jusqu'à ce que la dernière personne dans la file d'attente achète le billet. En utilisant cet algorithme, le processus CPU fonctionne de la même manière.
Comment fonctionne le FCFS ? Calcul du temps d'attente moyen
Voici un exemple de cinq processus arrivant à des moments différents. Chaque processus a un temps de rafale différent.
| Processus | Temps de rafale | Heure d'arrivée |
|---|---|---|
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
À l’aide de l’algorithme de planification FCFS, ces processus sont gérés comme suit.
Étape 1) Le processus commence par P4 qui a une heure d'arrivée 0
Étape 2) Au temps = 1, P3 arrive. P4 est toujours en cours d'exécution. Par conséquent, P3 est conservé dans une file d’attente.
| Processus | Temps de rafale | Heure d'arrivée |
|---|---|---|
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Étape 3) Au temps = 2, arrive P1 qui est conservé dans la file d'attente.
| Processus | Temps de rafale | Heure d'arrivée |
|---|---|---|
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Étape 4) Au temps = 3, le processus P4 termine son exécution.
Étape 5) Au temps = 4, P3, qui est le premier dans la file d'attente, démarre l'exécution.
| Processus | Temps de rafale | Heure d'arrivée |
|---|---|---|
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Étape 6) Au temps =5, P2 arrive, et il est maintenu dans une file d'attente.
| Processus | Temps de rafale | Heure d'arrivée |
|---|---|---|
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Étape 7) Au temps 11, P3 termine son exécution.
Étape 8) Au temps = 11, P1 démarre l'exécution. Il a un temps de rafale de 6. Il termine son exécution à l'intervalle de temps 17.
Étape 9) Au temps = 17, P5 démarre l'exécution. Il a un temps de rafale de 4. Il termine son exécution à temps = 21
Étape 10) Au temps = 21, P2 démarre l'exécution. Il a un temps de rafale de 2. Il termine son exécution à l'intervalle de temps 23.
Étape 11) Calculons le temps d'attente moyen pour l'exemple ci-dessus.
Waiting time = Start time - Arrival time
P4 = 0-0 = 0
P3 = 3-1 = 2
IP = 11-2 = 9
P5 = 17-4 = 13
P2= 21-5= 16
Temps d'attente moyen
= 40 / 5 = 8
Avantages du FCFS
Voici les avantages/avantages de l’utilisation de l’algorithme de planification FCFS :
- La forme la plus simple d'un Algorithme de planification du processeur
- Facile à programmer
- Premier arrivé premier servi
Inconvénients du FCFS
Voici les inconvénients/inconvénients de l’utilisation de l’algorithme de planification FCFS :
- Il s'agit d'un algorithme de planification de processeur non préemptif. Ainsi, une fois le processus alloué au processeur, il ne le libérera jamais tant qu'il n'aura pas terminé son exécution.
- Le temps d'attente moyen est élevé.
- Les processus courts qui se trouvent en fin de file d'attente doivent attendre la fin du processus long en début de file.
- Ce n’est pas une technique idéale pour les systèmes à temps partagé.
- En raison de sa simplicité, FCFS n'est pas très efficace.
Résumé
- Définition : FCFS est un algorithme de planification du système d'exploitation qui exécute automatiquement les requêtes et les processus en file d'attente par ordre d'arrivée.
- Il prend en charge la planification non préemptive et préemptive
- algorithme.
- FCFS signifie Premier arrivé, premier servi
- Un exemple concret de la méthode FCFS consiste à acheter un billet de cinéma au guichet.
- C'est la forme la plus simple d'un algorithme de planification de CPU
- Il s'agit d'un algorithme de planification de processeur non préemptif. Ainsi, une fois le processus alloué au processeur, il ne le libérera jamais tant qu'il n'aura pas terminé son exécution.
