Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
File (structure de données)
Résumé
En informatique, une file dite aussi file d'attente (en anglais queue) est un type abstrait basé sur le principe « premier entré, premier sorti » ou PEPS, désigné en anglais par l'acronyme FIFO () : les premiers éléments ajoutés à la file seront les premiers à en être retirés.
vignette|First In First Out - Premier Entré Premier Sorti.
Le type décrit le fonctionnement d'une : les premiers arrivés sont les premiers à sortir (PEPS, FIFO en anglais pour First in, first out). Quand le dernier entré est le premier à sortir (DEPS, LIFO pour Last in, first out en anglais), c'est une pile (stack).
Les algorithmes utilisés pour suivre les stocks doivent être cohérents avec la méthode utilisée en gestion des stocks.
Une liste chaînée dont on n'utilise que les opérations ajouterQueue et retirerTête constitue une queue. Si la queue se base sur un tableau, la structure enregistre deux indices, l'un correspondant au dernier arrivé, l'autre au prochain à sortir.
Les queues servent à organiser le traitement séquentiel des blocs de données d'origines diverses.
La , élaborée pour le dimensionnement des réseaux téléphoniques, relie le nombre d'usagers, le nombre de canaux disponibles, le temps d'occupation moyen du canal, et les temps d'attente à prévoir.
Dans un logiciel informatique, l'avantage de cet 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 être sûr d'effectuer les opérations dans un ordre logique.
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.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.