Wachtrij
Uit Wikipedia, de vrije encyclopedie
Een wachtrij is een rij waar elementen aan kunnen worden toegevoegd en elementen uit kunnen worden weggenomen, zodanig dat wegnemen van een element altijd aan de andere kant gebeurt dan toevoegen. Met andere woorden: wie het langst in de rij staat wordt het eerst geholpen (FIFO-principe).
Wachtrijen worden bestudeerd in de wachtrijtheorie, een onderdeel van de stochastiek.
Daarnaast zijn wachtrijen belangrijk als datastructuur en abstract datatype in de informatica, die ze echter meestal met hun Engelse naam aanduidt: queue.
Inhoud |
[bewerken] Wachtrijen in de wachtrijtheorie
De wachtrijtheorie bestudeert wiskundige modellen van systemen waarin het werk wordt gedaan door een of meer verwerkingseenheden die maar een element tegelijk kunnen verwerken, zodat elementen voor verwerking in een wachtrij kunnen komen. Daarbij wordt aangenomen dat grootheden zoals de verwerkingstijd van elementen zich volgens gegeven stochastische functies gedragen. Het doel van de theorie is om hieruit andere informatie over het systeem af te kunnen leiden, bijvoorbeeld de totale gemiddelde wachttijd voor een element, of de gemiddelde rijlengte voor elke verwerkingseenheid. Zo kunnen bottlenecks en optimalisaties worden bepaald. Voorbeeld: hoeveel loketten moeten er opengaan om klanten te bedienen zonder dat de rijlengte groeit bij een gegeven frequentie waarmee de klanten binnenkomen.
[bewerken] De queue als abstract datatype
In de informatica is een wachtrij een soort datastructuur, meestal queue genoemd of FIFO (First In First Out). De tegenhanger van de queue is de stack, die volgens het LIFO-principe werkt (Last In First Out).
De mogelijke bewerkingen op een queue zijn:
- Een element in de queue plaatsen.
- Een element uit de queue ophalen.
Het ophalen gebeurt aan de andere kant dan het plaatsen.
Daarbij kunnen de volgende fouten optreden:
- underflow: een poging om een element uit een lege queue te halen.
- overflow: een poging om een element aan een volle queue toe te voegen. Dit kan alleen als de queue een begrensde grootte heeft.
[bewerken] Implementatie van een queue-datastructuur
Een queue kan worden geïmplementeerd als gelinkte lijst, of, bij begrensde grootte, als een array. Om onbeperkt door het geheugen wandelen van de queue-data te vermijden wordt zo'n array meestal gebruikt als ringbuffer: het voorste element van de queue staat dan niet altijd vooraan de array, maar wordt aangegeven door een extra pointer, die steeds verschoven wordt, en als het einde van de buffer is bereikt, gaat men verder aan het begin.
Bij het verzenden en ontvangen van seriële data wordt meestal van een queue gebruikgemaakt - het programma zet een aantal te verwerken bytes klaar voor verzending die dan één voor één worden verzonden. Wordt een bepaalde mate van vulling van de queue bereikt, dan wordt een 'hoog water'-signaal van kracht dat aangeeft dat er even niets meer bij kan; is de bufferinhoud onder een bepaald minimum gedaald dan wordt dit signaal weer verwijderd en/of een 'laag water'-signaal gezet.
