File (structure de données)

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Pour les articles homonymes, voir File.
Page d’aide sur l’homonymie Pour les articles ayant des titres homophones, voir Fil et Phil.
First In First Out - Premier Entré Premier Sorti

En informatique, une file, file d'attente ou queue[1] (« queue » est aussi le terme anglais), est une structure de données basée sur le principe du Premier entré, premier sorti, en anglais FIFO (« First in, first out »), en français PEPS (premier arrivé premier sorti) ce qui veut dire que les premiers éléments ajoutés à la file seront les premiers à être récupérés. Le fonctionnement ressemble à une file d'attente : les premières personnes arrivées sont les premières personnes à sortir de la file.

Les queues servent à organiser le traitement séquenciel des blocs de données d'origines diverses.

Limites de la méthode[modifier | modifier le code]

Dans un logiciel informatique, l'avantage de cette politique d'ordonnancement réside dans sa relative simplicité, cependant elle pénalise les processus à temps bref d'exécution. En effet, si on lance, à la suite d'un processus qui demande beaucoup de temps de calcul, une petite tâche (par exemple, dans un serveur qui ne gère qu'une imprimante, imprimer une page) la petite tâche devra attendre la fin de la tache qui demande beaucoup plus de temps (imprimer cent pages) avant de s'exécuter. À l'époque des machines à un seul processeur, c’était la technique la plus fiable pour effectuer les opérations dans un ordre logique[réf. nécessaire].

Cet algorithme est également utilisé comme politique de remplacement des lignes de cache en raison de sa simplicité d'implémentation et de son faible coût. Néanmoins, il présente dans cet usage une anomalie connue sous le nom d'anomalie de Belady : augmenter le nombre d'étages de la pile peut avoir un effet négatif sur la performance[réf. nécessaire].

Applications[modifier | modifier le code]

Cette technique est utilisée principalement dans les systèmes temps réel.

Cette structure est utilisée par exemple :

  • En général, pour mémoriser temporairement des transactions qui doivent attendre pour être traitées.
  • Les serveurs d'impression, qui traitent ainsi les requêtes dans l'ordre dans lequel elles arrivent, et les insèrent dans une file d'attente (dite aussi queue ou spool).
  • Certains moteurs multitâches, dans un système d'exploitation, qui doivent accorder du temps-machine à chaque tâche, sans en privilégier aucune.
  • Un algorithme de parcours en largeur utilise une file pour mémoriser les nœuds visités.
  • Pour créer toutes sortes de mémoires tampons (en anglais « buffers »).

Primitives[modifier | modifier le code]

Voici les primitives communément utilisées pour manipuler des files. Il n'existe pas de normalisation pour les primitives de manipulation de file. Leurs noms sont donc indiqués de manière informelle[réf. nécessaire].

  • « Enfiler » : ajoute un élément dans la file. Terme anglais correspondant : « Enqueue ».
  • « Défiler » : renvoie le prochain élément de la file, et le retire de la file. Terme anglais correspondant : « dequeue ».
  • « La file est-elle vide ? » : renvoie « vrai » si la file est vide, « faux » sinon.
  • « Nombre d'éléments dans la file » : renvoie le nombre d'éléments dans la file.

Exemple en C#[modifier | modifier le code]

Voir aussi[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Liens externes[modifier | modifier le code]

  • Bruno Bachelet, « File d'attente », dans Structures de données,‎ 2011 (lire en ligne)

Notes et références[modifier | modifier le code]