Deutsch
Menü

Was ist Warteschlange (Queue)?

FIFO-Datenstruktur (First In, First Out), bei der das zuerst hinzugefügte Element zuerst entnommen wird. Das Anfügen hinten heißt Enqueue, das Entnehmen vorn Dequeue. Warteschlangen dienen für anstehende Aufträge, für die Datenübergabe zwischen Tasks und für die Breitensuche.

Japanische Bezeichnung: キュー

„Warteschlange (Queue)“ kommt in 10 Übungsfragen aus 8 Themen vor, z. B. Datenstrukturen und Algorithmen, Multicore und Synchronisation, Embedded Systems und Firmware.

Fachgebiet: Datenstrukturen und Algorithmen

Jetzt üben: Fragen zu Warteschlange (Queue)

Warum wird beim Warten mit einer Bedingungsvariable auf „Warteschlange nicht mehr leer“ die Bedingung nach dem Aufwachen mit einer while-Schleife statt mit if erneut geprüft?

  1. AWeil while schneller als if ausgeführt wird
  2. BWeil if bei Bedingungsvariablen nicht verwendet werden darf
  3. CWeil die Bedingung auch nach dem Aufwecken nicht erfüllt sein kann, etwa weil ein anderer Thread zuvor zugegriffen hat oder das Aufwachen grundlos erfolgt ist
Antwort und Erläuterung anzeigen

Antwort: C. Weil die Bedingung auch nach dem Aufwecken nicht erfüllt sein kann, etwa weil ein anderer Thread zuvor zugegriffen hat oder das Aufwachen grundlos erfolgt ist

Beim Warten auf eine Bedingungsvariable wird die Sperre abgegeben und geschlafen, und nach der Benachrichtigung wird beim Aufwachen die Sperre wieder erworben und zurückgekehrt. In der Zeit bis zum Aufwachen kann jedoch ein anderer Thread die Sperre zuerst erwerben und das Element der Warteschlange entnehmen. Außerdem ist es aus Implementierungsgründen zulässig, auch ohne Benachrichtigung aufzuwachen (Spurious Wakeup). Daher wird die Bedingung nach dem Aufwachen geprüft und, falls nicht erfüllt, erneut gewartet, geschrieben als while-Schleife.

Welchen Vorteil hat es, bei einem RTOS Daten vom Sensor-Lese-Task über eine Queue (Message Queue) an den Anzeige-Task zu übergeben?

  1. ADaten, die durch die Queue laufen, werden automatisch verschlüsselt
  2. BDie empfangende Seite kann schlafend auf Daten warten, und Geschwindigkeitsunterschiede zwischen Sender und Empfänger werden in der Queue aufgefangen
  3. CMit einer Queue werden Task-Prioritäten überflüssig
Antwort und Erläuterung anzeigen

Antwort: B. Die empfangende Seite kann schlafend auf Daten warten, und Geschwindigkeitsunterschiede zwischen Sender und Empfänger werden in der Queue aufgefangen

Werden Daten über gemeinsame Variablen und Flags übergeben, sind Maßnahmen gegen Datenwettlauf nötig, und der Empfänger muss wiederholt abfragen. Mit einer RTOS-Queue legt der Sender nur Daten ein, und der Empfänger wartet im Wartezustand ohne CPU-Nutzung, bis Daten kommen. Da die Queue mehrere Daten aufnehmen kann, gehen auch bei vorübergehend schnellerem Sender keine Daten verloren.

„Warteschlange (Queue)“ in den Erläuterungen

Fragen mit „Warteschlange (Queue)“ (10)

  1. Warum wird beim Warten mit einer Bedingungsvariable auf „Warteschlange nicht mehr leer“ die Bedingung nach dem Aufwachen mit einer while-Schleife statt mit if erneut geprüft?
  2. Welchen Vorteil hat es, bei einem RTOS Daten vom Sensor-Lese-Task über eine Queue (Message Queue) an den Anzeige-Task zu übergeben?
  3. In eine leere Warteschlange (Queue) werden die Elemente A, B und C in dieser Reihenfolge eingefügt. Dann wird ein Element entnommen, D eingefügt und ein Element entnommen, E eingefügt und ein Element entnommen. In welcher Reihenfolge werden die Elemente entnommen?
  4. Eine Warteschlange verwendet das Zeichenketten-Array q mit 4 Elementen als Ring. head und tail beginnen bei 1. enq(v) führt q[tail] ← v und dann tail ← tail mod 4 + 1 aus; deq() gibt den Wert von q[head] zurück und führt dann head ← head mod 4 + 1 aus. In welchem Element von q wird „E“ gespeichert, wenn das folgende Programm ausgeführt wird?
  5. Welcher auf PCI Express basierende Schnittstellenstandard wird häufig zur Anbindung schneller SSDs an den Host verwendet?
  6. Was ist am wirksamsten, um ein Programm zu beschleunigen, das mit einem Gerät tausendfach einzelne kleine Daten austauscht?
  7. Welche Beschreibung des Grundgedankens der TCP-Überlastkontrolle ist richtig?
  8. In welcher Reihenfolge erscheinen die Zeichen in der Konsole, wenn das obige JavaScript im Browser ausgeführt wird?
  9. Auf einem leeren Stack werden nacheinander die Operationen push 1, push 2, pop, push 3, push 4, pop, pop ausgeführt. In welcher Reihenfolge werden die Werte durch pop entnommen?
  10. In einem Graphen mit ungewichteten Kanten soll die kleinste Zahl von Kanten vom Startknoten zu jedem anderen Knoten bestimmt werden. Welche Kombination aus Suchverfahren und Datenstruktur ist geeignet?

Verwandte Begriffe

Breitensuche (Breadth-First Search) Stack (Stapelspeicher) Bedingungsvariable (Condition Variable) RTOS (Echtzeitbetriebssystem) Data Race (Datenwettlauf) Array PCI Express NVMe Event Loop Tiefensuche (Depth-First Search)

Zur Glossarübersicht