náhled|Znázornění fronty
Fronta je v programování abstraktní datový typ typu FIFO (z anglického First In, First Out, česky První dovnitř, první ven). Fronta používaná v operačních systémech pro meziprocesovou komunikaci je také nazývána roura (angl. pipe). Opakem fronty FIFO je zásobník (LIFO).
Minimální implementace fronty inicializace fronty (create) vlož položku na konec fronty (enqueue) vyber položku ze začátku fronty s čekáním, pokud je fronta prázdná (dequeue) vyber položku ze začátku fronty bez čekání – doplňková funkce získání položky ze začátku bez jejího odebrání z fronty (peek) nebo (front) – doplňková funkce dotaz na prázdnost fronty (is_empty)
Synchronizace Fronta zpráv je synchronizační primitivum. Skládá se z fronty, do které se ukládají zprávy, funkce pro odeslání zprávy (která může blokovat při zaplnění fronty) a funkce pro přijetí zprávy, která blokuje proces, pokud zpráva není přítomna. Fronta může být pojmenovaná nebo může patřit konkrétnímu programu (a nikdo jiný z ní nesmí zprávy číst).
V praxi existuje obvykle i funkce zjišťující, zda je přítomna zpráva (bez čekání), ale pro funkci synchronizačního primitiva není potřebná.
Složitost v závislosti na implementaci Frontu lze implementovat (nejen) pomocí paměťového pole, kruhového pole a jednosměrného spojového seznamu. V těchto implementacích je pro všechny operace asymptotická složitost operací konstantní – mimo výběru položky v paměťovém poli. V tomto případě je asymptotická složitost O(n). Je totiž nutné všechny předchozí prvky posunout o jednu pozici doleva.
Související články Zásobník (datová struktura) Synchronizační primitivum Deadlock Prioritní fronta implementovaná haldou
Externí odkazy
Kategorie:Synchronizace Kategorie:Datové struktury