Im vorherigen Kapitel haben wir die blockierende Warteschlangenblockierung vorgestellt. Im Folgenden stellen wir seine häufig verwendeten Implementierungsklassen -ArrayBlocking -Verlockungsqueue ein.
1. Verwenden Sie Arrays, um Warteschlangen zu implementieren
Aufgrund der besonderen Anforderungen der Datenstruktur der Warteschlange ist es natürlich geeignet, in Form einer verknüpften Liste implementiert zu werden. Zwei Variablen werden verwendet, um den Header bzw. das Ende der verknüpften Liste aufzuzeichnen. Ändern Sie beim Löschen oder Einfügen der Warteschlange einfach den Header oder das Ende der verknüpften Liste. Darüber hinaus ist die verknüpfte Liste in Bezug auf eine Referenzverletzung verknüpft, sodass ihre Kapazität nahezu unbegrenzt ist.
So verwenden Sie Arrays, um Warteschlangen zu implementieren. Wir benötigen vier Variablen: Objekt [] Array, um Elemente in der Warteschlange, HeadIndex und TailIndex zu speichern, zeichnen Sie die Warteschlangenkopf und den Schwanz auf und zählen Sie die Anzahl der Warteschlangen.
Hier wird ein sehr cleverer Weg verwendet. Wir wissen, dass ein Element, wenn es in die Warteschlange eingefügt wird, eine Position im Array einnimmt. Wenn ein Element gelöscht wird, ist die Position des Arrays tatsächlich frei, was darauf hinweist, dass ein neues Element in diese Position eingefügt werden kann.
Bevor wir ein neues Element einfügen, müssen wir überprüfen, ob die Warteschlange voll ist, und bevor wir das Element löschen, müssen wir überprüfen, ob die Warteschlange leer ist.
2. Wichtige Mitgliedsvariablen in ArrayBlockingQueue
/ ** Speichern Sie die Elemente in der Warteschlange*/ endgültiges Objekt [] Elemente; / ** Die Position des Warteschlangenkopfes*/ int takeIndex; / ** Die Position des Warteschlangenschwanzes*/ int putIndex; / ** Die Anzahl der Elemente in der aktuellen Warteschlange*/ int Count; / ** verwendet, um die Sicherheit von gemeinsam genutzten Variablen mit mehreren Threads zu gewährleisten*/ Final Reentrantlock Lock; / ** Wenn die Warteschlange leer ist, wird die Wartezeit von Notizty aufgerufen, um den aktuellen Thread zu warten. / ** Wenn die Warteschlange voll ist, wird die Warteverfahrensmethode von Notfull aufgerufen, wodurch der aktuelle Thread wartet*/ private endgültige Bedingung Notvoller;
Es gibt mehr Sperr-, Notiz- und Nichtfrequenzvariablen, um die Sicherheit und die Wartezeit von Multi-Thread-Threads zu implementieren. Wie arbeiten sie?
2.1 Die Rolle der Sperre
Da ArrayBlockingQueue unter mehreren Threads arbeitet, müssen bei der Änderung von Mitgliedsvariablen wie Elementen, PutIndex und Count-Sicherheit Sicherheitsfragen in Betracht gezogen werden. Daher wird hier die EXCLUSIVE LOCKS -Sperre verwendet, um die Sicherheit gleichzeitiger Vorgänge zu gewährleisten.
2.2 Die Rolle von Notizty und Nonfotly
Da die Blockierung von Warteschlangen implementiert werden muss, muss die Warteschlange oder Einfügungsoperation warten, wenn die Warteschlange leer ist oder die Warteschlange voll ist. Deshalb dachten wir an das Bedingungsobjekt im Rahmen des Rahmens für die Genauigkeit und verwenden es, um es zu kontrollieren.
In AQs stellen wir die Rolle dieser Klasse vor:
3. Elementmethode hinzufügen
3.1 Fügen Sie (e e) und bieten (e) Methoden an:
// Rufen Sie die Methode in der Abstractqueue -Elternklasse auf. public boolean add (e e) {// implementieren if (Angebot (e)) return true; sonst werfen Sie neue IllegalStateException ("Warteschlange voll"); } // Fügen Sie dem Ende der Warteschlange neues Element hinzu. Return true bedeutet, dass die Zugabe erfolgreich ist, falsche Mittelwerte Die Zugabe hat fehlgeschlagen, und keine Ausnahme wird das öffentliche boolesche Angebot (e e) {achhnotnull (e) geworfen; endgültiger Reentrantlock Lock = this.lock; // Lock verwenden, um sicherzustellen, dass die multi-thread-Änderung der Mitgliedsattribute lock.lock (); Versuchen Sie {// Die Warteschlange ist voll, und die Hinzufügung von Elementen fehlschlägt falsch. if (count == items.length) return false; sonst rufen Sie die Enqueue -Methode auf, um das Element in die Warteschlange Enqueue (e) einzufügen; zurückkehren; }} endlich {lock.unlock (); }}Die Add -Methode wird implementiert, indem die Angebotsmethode aufgerufen wird. In der Angebotsmethode muss zunächst festgestellt werden, ob die Warteschlange voll ist. Wenn es voll ist, gibt es direkt falsch zurück, ohne den aktuellen Thread zu blockieren. Wenn Sie nicht zufrieden sind, rufen Sie die Enqueue -Methode auf, um das Element in die Warteschlange einzufügen.
HINWEIS: Verwenden von lock.lock () stellt hier sicher, dass nur ein Thread -Modifys -Mitgliedsvariablen gleichzeitig zur Verhinderung von gleichzeitigen Betriebsproblemen. Obwohl es auch den aktuellen Thread blockiert, handelt es sich nicht um ein bedingendes Warten, sondern nur, weil das Schloss von anderen Fäden gehalten wird und die Methodenbetriebszeit in ArrayBlockingQueue nicht lang ist, was dem Nichtsperrung des Fadens entspricht.
3.2 Methode setzen
// Fügen Sie dem Ende der Warteschlange ein neues Element hinzu. Wenn die Warteschlange voll ist, wartet der aktuelle Thread. Antwort auf die Interrupt -Ausnahme Public void put (e e) löscht InterruptedException {ChecknotNull (e); endgültiger Reentrantlock Lock = this.lock; // Lock verwenden, um sicherzustellen, dass Multi-Threads die Sicherheit von Mitgliedern von Attributen lock.lockinterrupticled () ändern; Versuchen Sie {// Wenn die Warteschlange voll ist, rufen Sie die Methode Notfull.await () auf, um den aktuellen Thread warten zu lassen, bis die Warteschlange nicht voll ist, während (count == items.length) notledle.await (); // Rufen Sie die Enqueue -Methode auf, um das Element in die Warteschlange Enqueue (e) einzulegen. } endlich {lock.unlock (); }}Der allgemeine Prozess der Angebotsmethode entspricht der Angebotsmethode. Wenn die Warteschlange jedoch voll ist, wird die Methode Notful.await () aufgerufen, um den aktuellen Threadblock zu erstellen und zu warten, bis die Warteschlange von anderen Threads entfernt wird. Wenn die Warteschlange nicht zufrieden ist, wird der wartende Thread geweckt.
3.3 Angebot (e e, langfristige, Zeiteinheit) Methode
/*** Fügen Sie dem Ende der Warteschlange ein neues Element hinzu. Wenn in der Warteschlange kein Platz verfügbar ist, wartet der aktuelle Thread. * Wenn die Wartezeit die Zeitüberschreitung überschreitet, wird FALSE zurückgegeben, was darauf hinweist, dass die Hinzufügung fehlgeschlagen ist // Berechnen Sie den Zeitwert des maximalen Warten -Gesamt -Nanos -langen Nanos = Einheit.Tonanos (Timeout); endgültiger Reentrantlock Lock = this.lock; // Lock verwenden, um sicherzustellen, dass die Multi-Thread-Änderung der Mitgliedsattribute lock.lockInterruptisle (); Versuchen Sie {// Die Warteschlange ist voll, während (count == items.length) {// nanos <= 0 bedeutet, dass die maximale Wartezeit eingetreten ist, sodass Sie nicht mehr warten müssen. Rückgabe falsch und zeigt an, dass die Zugabe fehlgeschlagen ist. if (nanos <= 0) return false; // Rufen Sie die NOTFUL.AWAITNANOS (NANOS) -Methode an. Die Zeitüberschreitungszeit wird automatisch geweckt. // Wenn es im Voraus aufgeweckt wird, wird die verbleibende Zeit zurückgegeben. } // Rufen Sie die Enqueue -Methode auf, um das Element in die Warteschlange Enqueue (e) einzufügen. zurückkehren; } endlich {lock.unlock (); }}Der allgemeine Put -Methodefluss entspricht der Put -Methode. Sie werden nur die NOTFALL.AWAITNANOS (NANOS) -Methode aufgerufen, um den aktuellen Thread zu warten und die Wartezeit einzustellen.
4. Elementmethode löschen
4.1 REMET () und POLL () Methoden:
// Rufen Sie die Methode in der Abstractqueue -Elternklasse auf. public e remove () {// Implementierung durch Aufrufen von POLL E x = POLL (); if (x! = null) return x; sonst werfen Sie neue NoSuchelementException (); } // Löschen Sie das erste Element der Warteschlange (d. H. Der Warteschlangenheader) und geben Sie es zurück. Wenn die Warteschlange leer ist, bringt sie keine Ausnahme, sondern kehrt Null zurück. public e poll () {Final Reentrantlock Lock = this.lock; // Lock verwenden, um sicherzustellen, dass die multi-thread-Änderung der Mitgliedsattribute lock.lock (); Versuchen Sie {// if count == 0 und die Liste ist leer, null zurück. Rufen Sie ansonsten die DEQUEUE -Methode auf, um das Listen -Header -Element zurückzugeben (count == 0)? null: dequeue (); } endlich {lock.unlock (); }}Die Entfernungsmethode wird durch Aufrufen der Poll () -Methode implementiert. In der Methode der Umfrage (), wenn die Liste leer ist, gibt sie NULL zurück, andernfalls wird die DEQUEUE -Methode aufgerufen, um das Listen -Header -Element zurückzugeben.
4.2 Take () Methode
/*** Kehren Sie zurück und entfernen Sie das erste Element der Warteschlange. Wenn die Warteschlange leer ist, wartet der vordere Faden. Antwort Interrupt Exception*/ public e take () löscht InterruptedException {Final Reentrantlock lock = this.lock; // Lock verwenden, um sicherzustellen, dass Multi-Threads die Sicherheit von Mitgliedern von Attributen lock.lockinterrupticled () ändern; Versuchen Sie es mit {// Wenn die Warteschlange leer ist, rufen Sie die Methode Notimpty.await () an, um den aktuellen Thread warten zu lassen. // Bis ein anderer Faden Elemente in die Warteschlange einfügt, wird der Faden erweckt. while (count == 0) notieren.await (); // rufen Sie die DEQUEUE -Methode an, um das List -Header -Element zurückzugeben. Retqueue (); } endlich {lock.unlock (); }}Wenn die Methode take () leer ist, muss der aktuelle Thread warten, bis ein anderer Thread ein neues Element in die Warteschlange einfügt und der Faden erweckt wird.
4.3 Umfrage (lange Zeit, Zeiteinheit) Methode
/*** Kehren Sie zurück und entfernen Sie das erste Element der Warteschlange. Wenn die Warteschlange leer ist, wartet der vordere Faden. * Wenn die Wartezeit die Zeitüberschreitung überschreitet, wird Falsch zurückgegeben, um anzuzeigen, dass das Element fehlgeschlagen ist endgültiger Reentrantlock Lock = this.lock; // Lock verwenden, um sicherzustellen, dass die multi-thread-Änderung der Mitgliedsattribute lock.lockinterruptisle (); Versuchen Sie {// Die Warteschlange ist leer, während (count == 0) {// nanos <= 0 bedeutet, dass die maximale Wartezeit eingetroffen ist, sodass es nicht mehr warten muss, null zurückzukehren. if (nanos <= 0) return null; // rufen Sie die motiNtempy.awaitnanos (NANOS) -Methode an, um den Zeitplan -Thread zu warten und die Zeitüberschreitungszeit festzulegen. Nanos = Notizty.Awaitnanos (Nanos); } // Rufen Sie die DeQueue -Methode auf, um das List -Header -Element zurückzugeben. Retqueue (); } endlich {lock.unlock (); }}Genau wie beim Take () -Methodeprozess wird es nur als Awaitnanos (NANOS) -Methode bezeichnet, damit der aktuelle Thread warten und die Wartezeit festlegen.
5. Methoden zum Anzeigen von Elementen
5.1 Element () und Peek () Methoden
// Rufen Sie die Methode in der Abstractqueue -Elternklasse auf. public e element () {e x = peek (); if (x! = null) return x; sonst werfen Sie neue NoSuchelementException (); } // Queue -Header -Elemente public e peek () {Final Reentrantlock lock = this.lock; // Lock verwenden, um sicherzustellen, dass die multi-thread-Änderung der Mitgliedsattribute lock.lock (); Versuchen Sie es mit {// das Element des aktuellen Warteschlangen -Header -Return -Itemat (takeIndex) zurück; // null Wenn die Warteschlange leer ist} endlich {lock.unlock (); }}Vi. Andere wichtige Methoden
6.1 Enqueue- und Dequeue -Methoden
// Element X in den Schwanz der Warteschlange einfügen private void Enqueue (e x) {// Assert Lock.GetHholdCount () == 1; // Elemente gründen [putIndex] == null; // Das aktuelle PutIndex -Positionselement muss null endgültig sein. [] Items = this.items; Elemente [putIndex] = x; // Wenn PutIndex gleich den Elementen ist. // Fügen Sie der Anzahl der Warteschlangen einen Zähl ++ hinzu; // Da ein Element eingefügt wird, ist die aktuelle Warteschlange definitiv nicht leer. Wachen Sie dann einen Thread auf, auf den unter Notizty -Bedingung notieren Sie sich. Signal (); } // Löschen Sie das Element des Warteschlangenheaders und geben Sie es privat e dequeue () {// Assert Lock.GetHholdCount () == 1; // Elemente geltend machen [takeIdex]! = null; endgültiges Objekt [] items = this.items; // Erhalten Sie das Element des aktuellen Warteschlangenheaders @SuppressWarnings ("Deaktiviert") e x = (e) Elemente [takeIdex]; // Setzen Sie die aktuelle Warteschlange -Header -Position auf Nullelemente [takeIdex] = null; if (++ takeIndex == items.Length) takeIndex = 0; // abzüglich der Anzahl der Warteschlangen von einer Zählung-; if (itrs! = null) itrs.elementdequed (); // Da ein Element gelöscht wird, ist die Warteschlange definitiv nicht zufrieden. Wachen Sie also einen Thread auf, der unter dem nicht feiner Zustand wartet. Signal (); Rückkehr x; }Diese beiden Methoden repräsentieren, die Elemente in Elemente aus der Warteschlange einfügen und entfernen. Und sie wollen den wartenden Thread aufwachen. Nach dem Einsetzen eines Elements darf die Warteschlange nicht leer sein, so Nach dem Löschen des Elements muss die Warteschlange unzufrieden sein, so
6.2 Methode (Objekt O) entfernen
// Löschen Sie das Objekt o -Element in der Warteschlange und löschen Sie höchstens einen öffentlichen booleschen (Objekt o) {if (o == null) reta falsch; endgültiges Objekt [] items = this.items; // Lock verwenden, um die Sicherheit der Multi-Thread-Änderung der Mitgliedsattribute endgültig zu sorgen. Lock = this.lock; lock.lock (); Versuchen Sie es nur, wenn in der Warteschlange ein Wert vorhanden ist. if (count> 0) {// Die nächste Position am Ende der Warteschlange Final int putIndex = this.putIndex; // die Position des Warteschlangenheaders int i = takeIdex; do {// Das aktuelle Positionselement entspricht dem gelöschten Element, wenn (O.Equals (Elemente [i])) {// das i -Positionelement Removat (i) löschen; // Return true Return True; } if (++ i == items.length) i = 0; // Wenn i == putIndex bedeutet, dass alle Elemente durchquert wurden} während (i! = PutIndex); } return false; } endlich {lock.unlock (); }} Löschen Sie das angegebene Objekt O aus der Warteschlange, dann müssen Sie die Warteschlange durchqueue und das erste Element löschen, das das gleiche wie Objekt O ist. Wenn in der Warteschlange kein Objekt o -Element vorhanden ist, geben Sie Falsch zurück, um fehlgeschlagen zu werden.
Hier sind zwei Punkte zu beachten:
Wie man eine Warteschlange durchqueu macht, muss vom Kopf der Warteschlange bis zum Ende der Warteschlange führen. Es hängt von den beiden Variablen ab, die Indedex und PutIndex nehmen.
Warum ist Objekt [] items = this.items; Dieser Code wird nicht in den Synchronen -Sperr -Lock -Code -Code -Block platziert. Elemente sind Mitgliedsvariablen. Wenn es so viele Themen gibt, geben es dann keine Probleme mit der Parallelität?
Dies liegt daran, dass Elemente Referenzvariablen sind, keine grundlegenden Datentypen, und unsere Einfügungs- und Löschvorgänge in Warteschlangen sind alle für dieses Element -Array, und der Verweis auf das Array wird nicht geändert. Daher erhalten im Sperrcode Elemente die neuesten Änderungen durch andere Threads. Aber wenn der int putindex = this.putIndex; Methode sperrt den Codeblock nach außen, ein Problem tritt auf.
Entfernung (endgültige int removeIndex) Methode
// das Element in der Warteschlange löschen remeIndex Position void removeat (endgültig int removeIndex) {// Assert Lock.getHholdCount () == 1; // Elemente gründen [removedIndex]! = null; // Assert RemoveIndex> = 0 && removeIndex <items.length; endgültiges Objekt [] items = this.items; // Dies bedeutet, dass es viel einfacher ist, das Element als Listenheader zu löschen, was dem DEQUEUE -Methodenprozess ähnlich ist, wenn (removeIndex == takeIndex) {// das Element in den Positionselementen removeIndex [takeIdex] = null entfernen; // Wenn das Ende des Arrays, müssen Sie zur Position des Array -Headers gehen, wenn (++ takeIndex == items.length) takeIndex = 0; // abzüglich der Anzahl der Warteschlangen von einer Zählung-; if (itrs! = null) itrs.elementdequed (); } else {// ein "Innenraum" endgültig int putIndex = this.putIndex; für (int i = removeIndex ;;) {int next = i + 1; if (next == items.length) next = 0; // Das Ende der Warteschlange hat das Ende der Warteschlange noch nicht erreicht, dann wird das Element in der nächsten Position durch das Element in der vorherigen Position überschrieben, wenn (nächstes! I = Weiter; } else {// Setzen Sie das Schwanzelement der Warteschlangennullelemente [i] = null; // den Wert von PutIndex this.putIndex = i zurücksetzen; brechen; }} // Verringern Sie die Anzahl der Warteschlangen durch Zählung-; if (itrs! } // Da ein Element gelöscht wird, ist die Warteschlange definitiv nicht zufrieden. Wachen Sie also einen Thread auf, der unter dem nicht fehlerhaften Zustand wartet. Signal (); }Löschen Sie Elemente in der angegebenen Position in der Warteschlange. Es ist zu beachten, dass das Array nach dem Löschen die Warteschlangenform, die in zwei Situationen unterteilt ist, noch beibehalten kann:
Das obige ist der gesamte Inhalt dieses Artikels. Ich hoffe, es wird für das Lernen aller hilfreich sein und ich hoffe, jeder wird Wulin.com mehr unterstützen.