Nederlands
Menu

Wat is Wachtrij (queue)?

First-in-first-out-datastructuur (FIFO) waarin het eerst toegevoegde element als eerste wordt verwijderd. Achteraan toevoegen heet enqueue en vooraan verwijderen dequeue. Wachtrijen worden gebruikt voor werk dat op verwerking wacht, voor het doorgeven van gegevens tussen taken en voor breedte-eerst zoeken.

Japanse benaming: キュー

“Wachtrij (queue)” komt voor in 13 oefenvragen uit 9 onderwerpen, bijv. Datastructuren en algoritmen, Embedded systemen en firmware, Multicore en synchronisatie.

Vakgebied: Datastructuren en algoritmen

Nu oefenen: vragen over Wachtrij (queue)

Waarom wordt bij een conditievariabele, wanneer wordt gewacht tot de wachtrij niet meer leeg is, na het ontwaken de voorwaarde opnieuw gecontroleerd met een while-lus in plaats van een if-opdracht?

  1. AOmdat een while-lus sneller wordt uitgevoerd dan een if-opdracht
  2. BOmdat een conditievariabele volgens de regels niet met een if-opdracht kan worden gebruikt
  3. COmdat de thread ook na het wekken kan merken dat de voorwaarde niet vervuld is, doordat een andere thread eerder iets heeft weggehaald of de thread zonder reden is ontwaakt
Antwoord en toelichting tonen

Antwoord: C. Omdat de thread ook na het wekken kan merken dat de voorwaarde niet vervuld is, doordat een andere thread eerder iets heeft weggehaald of de thread zonder reden is ontwaakt

Wachten op een conditievariabele laat de lock los, slaapt en neemt na wakker worden door een melding de lock opnieuw voordat hij terugkeert. In de tussentijd kan een andere thread eerder de lock nemen en het element uit de wachtrij halen. Bovendien is toegestaan dat vanwege de implementatie zonder melding wordt ontwaakt (spurious wakeup). Daarom wordt na het ontwaken de voorwaarde gecontroleerd en wordt met een while-lus opnieuw gewacht als die niet is vervuld.

Wat is het voordeel van een wachtrij (berichtenwachtrij) bij het doorgeven van gegevens van een taak die een sensor leest aan een taak die weergeeft in een RTOS?

  1. AGegevens worden automatisch versleuteld wanneer ze door de wachtrij gaan
  2. BDe ontvanger kan slapend wachten tot er gegevens komen en het snelheidsverschil tussen zender en ontvanger wordt in de wachtrij opgevangen
  3. CMet een wachtrij zijn taakprioriteiten niet meer nodig
Antwoord en toelichting tonen

Antwoord: B. De ontvanger kan slapend wachten tot er gegevens komen en het snelheidsverschil tussen zender en ontvanger wordt in de wachtrij opgevangen

Bij het doorgeven van gegevens met gedeelde variabelen en vlaggen zijn maatregelen tegen dataraces nodig en moet de ontvanger herhaaldelijk gaan kijken. Met een RTOS-wachtrij hoeft de zender alleen de gegevens erin te plaatsen en kan de ontvanger in een wachttoestand zonder CPU-gebruik wachten tot er gegevens zijn. In de wachtrij kunnen meerdere gegevens worden opgeslagen, zodat geen gegevens verloren gaan als de zender tijdelijk sneller is.

“Wachtrij (queue)” in de toelichting

Vragen met “Wachtrij (queue)” (13)

  1. Waarom wordt bij een conditievariabele, wanneer wordt gewacht tot de wachtrij niet meer leeg is, na het ontwaken de voorwaarde opnieuw gecontroleerd met een while-lus in plaats van een if-opdracht?
  2. Wat is het voordeel van een wachtrij (berichtenwachtrij) bij het doorgeven van gegevens van een taak die een sensor leest aan een taak die weergeeft in een RTOS?
  3. In een lege wachtrij worden de elementen A, B en C in deze volgorde geplaatst. Daarna wordt er één element uitgehaald, wordt D toegevoegd en weer één uitgehaald, en wordt E toegevoegd en nog één uitgehaald. In welke volgorde worden de elementen uitgehaald?
  4. Een wachtrij gebruikt de array q (4 elementen van het type string) als ring. head en tail beginnen bij 1. enq(v) voert q[tail] ← v uit en daarna tail ← tail mod 4 + 1; deq() geeft de waarde van q[head] terug en voert daarna head ← head mod 4 + 1 uit. In welk element van q wordt „E” opgeslagen als het volgende programma wordt uitgevoerd?
  5. Welke interfacestandaard op basis van PCI Express wordt veel gebruikt voor de verbinding tussen snelle SSD’s en de host?
  6. Welke uitleg over paravirtualisatie is juist?
  7. Wat is het belangrijkste doel van het gebruik van een RTOS (real-time besturingssysteem) in embedded apparatuur?
  8. Wat is de meest effectieve methode om een programma te versnellen dat duizenden keren kleine gegevens één voor één met een apparaat uitwisselt?
  9. Welke beschrijving van het basisidee van congestiebeheersing bij TCP is juist?
  10. Op een lege stack worden achtereenvolgens push 1, push 2, pop, push 3, push 4, pop, pop uitgevoerd. In welke volgorde komen de waarden die pop verwijdert eruit?
  11. Een max-heap, waarin de waarde van elke ouder minstens zo groot is als die van zijn kinderen, wordt opgeslagen in een array met de wortel in a[0]. Aan de heap 50, 30, 40, 10, 20, 35 wordt 45 toegevoegd door de waarde achteraan te plaatsen en haar met haar ouder te verwisselen zolang ze groter is dan die ouder. Hoe ziet de array er daarna uit?
  12. In een graaf waarvan de kanten geen gewicht hebben, wil je vanaf een startknoop het kleinste aantal kanten naar elke andere knoop bepalen. Welke combinatie van zoekmethode en datastructuur is geschikt?
  13. Wat gebeurt er met de wachttijd van verzoeken wanneer de bezettingsgraad van een server (het aandeel van de tijd dat deze bezig is) 100 % nadert?

Verwante termen

Stack (stapelgeheugen) RTOS (real-time besturingssysteem) Breedte-eerst zoeken (breadth-first search) Array Conditievariabele Variabele Modulo-operatie PCI Express NVMe Hypervisor

Naar de woordenlijst