Unterscheidung zwischen Warteschlange voll und Warteschlange leer

Question

Ich verwende ein Array mit einem Schreibindex und einem Lese-Index, um eine einfache FIFO-Warteschlange zu implementieren. Ich mache die übliche MOD ArraySize, wenn ich den Schreib- und Lese-Index inkrementiere. Gibt es eine Möglichkeit, zwischen Warteschlange voll und Warteschlange leere Bedingung (wrIndex == rdIndex) zu unterscheiden, ohne eine zusätzliche Warteschlange zu verwenden und auch ohne Array-Eintrag, d. Warteschlange ist voll if (WrIndex + 1) MOD ArraySize == ReadIndex

Answer 1

Ich würde mit einem Array-Eintrag "verschwenden", um die Warteschlange voll Zustand zu erkennen, vor allem, wenn Sie mit verschiedenen Threads/Aufgaben als Hersteller und Verbraucher beschäftigt sind. Mit einer anderen Flagge, die diese Situation verfolgt, erhöht sich die Sperrung, die notwendig ist, um die Dinge konsistent zu halten, und erhöht die Wahrscheinlichkeit eines Fehlers, der eine Wettlaufsituation einführt. Dies gilt umso mehr, wenn Sie einen kritischen Abschnitt (wie Sie in einem Kommentar angeben) nicht verwenden können, um sicherzustellen, dass die Dinge synchron sind.

Sie müssen mindestens ein bisschen irgendwo, um diese Bedingung zu verfolgen, und das bedeutet wahrscheinlich mindestens ein Byte. Unter der Annahme, dass Ihre Warteschlange ints enthält, sparen Sie nur 3 Byte RAM und Sie werden mehrere Bytes des Programmabbilds (was möglicherweise nicht so wertvoll ist, so dass es egal sein könnte). Wenn Sie ein Flag-Bit in einem Byte behalten, das zum Speichern anderer Flag-Bits verwendet wird, müssen Sie zusätzlich mit dem Einstellen/Testen/Löschen dieses Flag-Bits in Thread-sicherer Weise umgehen, um sicherzustellen, dass die anderen Bits nicht beschädigt werden.

Wenn Sie Bytes in die Warteschlange stellen, speichern Sie wahrscheinlich nichts - Sie können das Sentinel-Element als Flag betrachten, das Sie woanders hinlegen müssten. Aber jetzt müssen Sie haben keine zusätzlichen Code, um mit der Flagge umzugehen.

überlegen Sie sorgfältig, wenn Sie brauchen, dass zusätzliches Warteschlangenelement wirklich, und denken Sie daran, dass, wenn Sie Bytes sind Warteschlangen, dann ist das zusätzliche Warteschlangenelement wahrscheinlich nicht wirklich mehr Platz ist

Answer 2

Was ist falsch an einer Warteschlangenanzahl? Es hört sich so an, als würden Sie nach maximaler Effizienz und minimaler Logik streben, und obwohl ich das gleiche tun würde, würde ich immer noch eine Variable für die Warteschlangenzählung verwenden. Andernfalls wäre eine andere mögliche Lösung die Verwendung einer verketteten Liste. Eine geringe Speicherauslastung und das Entfernen des ersten Elements wäre einfach. Stellen Sie nur sicher, dass Sie Zeiger auf den Anfang und das Ende der Liste haben.

Answer 3

Im Grunde brauchen Sie nur ein einzelnes zusätzliches Bit irgendwo, um zu signalisieren, dass die Warteschlange momentan leer ist. Sie können das wahrscheinlich irgendwo verstecken, z. B. in dem höchstwertigen Bit eines Ihrer Indizes (und dann die unteren Bits kreativ AND an den Stellen, an denen Sie nur mit dem tatsächlichen Index in Ihrem Array arbeiten müssen).

Aber ehrlich gesagt, würde ich mit einer Warteschlangenzahl zuerst gehen und nur schneiden, wenn ich wirklich diesen Raum brauche, anstatt mit ein wenig herumspielen zu dulden.

Answer 4

Statt ein Lese- und Schreibindex , könnten Sie einen Lese-Index und eine Warteschlangenanzahl verwenden. Aus der Anzahl der Warteschlangen können Sie leicht erkennen, ob die Warteschlange leer ist. Und der Write-Index kann berechnet werden als (read index + queue count) mod array_size.