Soubor (datová struktura)
Ve výpočetní technice je soubor, který se také nazývá fronta (anglický tail ), datová struktura založená na principu „ first in, first out “ nebo FIFO, na který se v angličtině odkazuje zkratka FIFO ( „ first in, first out » ): The first prvky přidané do fronty budou odstraněny jako první.
Popis
Struktura funguje jako fronta : první, kdo dorazí, jsou první, kdo odejdou ( PEPS , FIFO v angličtině pro First in, first out ). Když je poslední vstup první ven (LIFO, LIFO Last in, první ven v angličtině), je to stack ( stack ).
Algoritmy používané ke sledování akcií musí být v souladu s metodou používanou při správě akcií .
Spojový seznam , který pouze addQueue a removeHead operace se používají představuje fronty. Pokud je fronta založena na poli , struktura zaznamenává dva indexy, jeden odpovídá poslednímu, který dorazí, druhý další, aby opustil.
Fronty slouží k organizaci sekvenčního zpracování datových bloků různého původu.
Teorie front , který byl vypracován pro dimenzování telefonních sítí, spojuje počet uživatelů, počet dostupných kanálů, průměrná doba obsazení kanálu, a čekací doby se dalo čekat.
Omezení metody
V počítačovém softwaru spočívá výhoda tohoto plánování v relativní jednoduchosti; penalizuje však procesy s krátkou dobou provedení: skutečně, pokud se spustí proces, který vyžaduje hodně výpočetního času, malý úkol (například na serveru, který spravuje pouze jednu tiskárnu, vytiskne stránku), malý Úkol bude muset počkat na konec úkolu, který vyžaduje mnohem více času (tisk sto stránek) před provedením. Ve dnech jednoprocesorových strojů to byla nejspolehlivější technika zajišťující, že operace byly prováděny v logickém pořadí.
Tento algoritmus se také používá jako politika nahrazení řádku mezipaměti kvůli jeho jednoduchosti implementace a nízké ceně. V tomto použití však představuje anomálii známou jako anomálie Belady : zvýšení počtu pater ve frontě může mít negativní vliv na výkon.
Aplikace
Tato struktura se používá například:
- obecně dočasně ukládat transakce, které musí počkat na zpracování;
- tiskové servery, které tak zpracovávají požadavky v pořadí, v jakém přicházejí, a vkládají je do fronty (nazývané také fronta nebo zařazovací služba );
- některé multitaskingové motory v operačním systému , který musí každému úkolu přidělit strojový čas , aniž by jakýkoli privilegoval;
- šířka traversal algoritmus používá frontu k ukládání na uzly;
- vytvářet všechny druhy vyrovnávacích pamětí (v angličtině „ buffers “ );
- Ve správě zásob musí algoritmy respektovat správu fyzických zásob, aby byla zajištěna fyzická konzistence / ocenění.
Primitiv
Zde jsou primitiva běžně používaná k manipulaci s frontami. U primitiv pro manipulaci s frontami neexistuje žádná standardizace. Jejich jména jsou proto uvedena neformálně.
- "Thread": přidá prvek do fronty. Odpovídající anglický výraz je enqueue .
- "Posun": vrátí další prvek ve frontě a odebere jej z fronty. Odpovídající anglický výraz je dequeue .
- „Je řádek prázdný?“ „: Vrátí„ true “, pokud je fronta prázdná, jinak„ false “.
- „Počet položek ve frontě“: Vrátí počet položek ve frontě.
Příklad v C #
Příklad v C #
using System;
namespace ExempleFile
{
public class File
{
private object[] _File;
private int _PointeurDeTete;
private int _PointeurDeQueue;
private int _Taille;
private int _NbreElements;
#region Constructeur
public File(int Taille)
{
this._Taille = Taille;
this._File = new object[Taille];
this._PointeurDeTete = 0;
this._PointeurDeQueue = 0;
this._NbreElements = 0;
}
#endregion
#region Fonctions
public virtual void Enfiler(object item)
{
lock (this)
{
if (this.EstPleine())
{
throw new Exception("La file est pleine !");
}
else
{
this._File[this._PointeurDeQueue] = item;
this._NbreElements++;
// Pointer sur le prochain elément libre,
// revenir à zéro si on est au bout de la file
this._PointeurDeQueue = this._PointeurDeQueue + 1;
if (this._PointeurDeQueue >= this._File.Length)
{
this._PointeurDeQueue = 0;
}
}
}
}
public virtual object Defiler()
{
lock (this)
{
object item = null;
if (this.EstVide())
{
throw new Exception("La file est vide !");
}
else
{
item = this._File[this._PointeurDeTete];
this._NbreElements--;
// Faire pointer le pointeur de queue sur le prochain élément valide,
// revenir à zéro si on est au bout de la file
this._PointeurDeTete = this._PointeurDeTete + 1;
if (this._PointeurDeTete >= this._File.Length)
{
this._PointeurDeTete = 0;
}
}
return item;
}
}
public virtual bool EstVide()
{
return (this._NbreElements == 0);
}
public virtual bool EstPleine()
{
return (this._NbreElements == this._Taille);
}
public int NbreElements
{
get { return this._NbreElements; }
}
#endregion
}
}
Poznámky a odkazy
-
Fronta je anglický výraz vypůjčený z francouzštiny, zatímco soubor označuje soubor v tomto jazyce .
-
Srov. Alfred Aho , John Hopcroft a Jeffrey Ullman ( překlad J.-M. Moreau), Datové struktury a algoritmy , Paříž, InterÉditions,1995, 450 s. ( ISBN 978-2-7296-0194-2 ) , „Elementární abstraktní datové typy“, s. 58-62
-
Bachelet 2011 .
-
Michel Fleutry , encyklopedický slovník elektroniky: anglicko-francouzský , Paříž, dům slovníku,1991, 1054 s. ( ISBN 2-85608-043-X ) , str. 699 ; (en) RL Brewster , Telekomunikační technologie , Chichester, Velká Británie, Ellis Horwood,1986, str. 45.
-
Srov. „ Fronty “ na Université P. et M. Curie Paris - Počítačové operační systémy
Podívejte se také
Bibliografie
Související články
externí odkazy
- Bruno Bachelet , „Queue“ , v Datové struktury ,2011( číst online )