Verwenden von Threads mit Sammlungen, Teil 1

Threads sind ein wesentlicher Bestandteil der Java-Sprache. Mithilfe von Threads sind viele Algorithmen, z. B. Warteschlangenverwaltungssysteme, leichter zugänglich als Abfrage- und Schleifentechniken. Als ich kürzlich eine Java-Klasse schrieb, stellte ich fest, dass ich beim Aufzählen von Listen Threads verwenden musste, und dies deckte einige interessante Probleme auf, die mit threadbewussten Sammlungen verbunden waren.

Dieses Java In Depth Spalte beschreibt die Probleme , die ich in meinem Versuch , entdeckt eine Thread-sichere Sammlung zu entwickeln. Eine Sammlung wird als "thread-sicher" bezeichnet, wenn sie von mehreren Clients (Threads) gleichzeitig sicher verwendet werden kann. "Also, was ist das Problem?" du fragst. Das Problem ist, dass ein Programm im typischen Sprachgebrauch eine Sammlung ( Mutation genannt ) sowohl ändert als auch liest ( Enumerating genannt ).

Einige Leute registrieren einfach nicht die Aussage "Die Java-Plattform ist Multithread-fähig." Sicher, sie hören es und nicken mit den Köpfen. Sie verstehen jedoch nicht, dass Threads in Java im Gegensatz zu C oder C ++, bei denen das Threading von der Seite durch das Betriebssystem angeschraubt wurde, grundlegende Sprachkonstrukte sind. Dieses Missverständnis oder schlechte Verständnis der inhärenten Thread-Natur von Java führt unweigerlich zu zwei häufigen Fehlern im Java-Code von Programmierern: Entweder deklarieren sie eine Methode nicht als synchronisiert, die sein sollte (weil sich das Objekt während des Java in einem inkonsistenten Zustand befindet) Ausführung der Methode) oder sie deklarieren eine Methode als synchronisiert, um sie zu schützen, was dazu führt, dass der Rest des Systems ineffizient arbeitet.

Ich bin auf dieses Problem gestoßen, als ich eine Sammlung haben wollte, die mehrere Threads verwenden können, ohne die Ausführung der anderen Threads unnötig zu blockieren. Keine der Sammlungsklassen in der Version 1.1 des JDK ist threadsicher. Insbesondere können Sie in keiner der Auflistungsklassen mit einem Thread auflisten, während Sie mit einem anderen mutieren.

Nicht threadsichere Sammlungen

Mein Grundproblem war wie folgt: Angenommen, Sie haben eine geordnete Sammlung von Objekten, entwerfen Sie eine Java-Klasse so, dass ein Thread die gesamte oder einen Teil der Sammlung auflisten kann, ohne sich Sorgen machen zu müssen, dass die Aufzählung aufgrund anderer Threads, die die Sammlung ändern, ungültig wird. Betrachten Sie als Beispiel für das Problem die Java- VectorKlasse. Diese Klasse ist nicht threadsicher und verursacht neue Probleme für neue Java-Programmierer, wenn sie sie mit einem Multithread-Programm kombinieren.

Die VectorKlasse bietet eine sehr nützliche Funktion für Java-Programmierer: ein dynamisch großes Array von Objekten. In der Praxis können Sie diese Funktion verwenden, um Ergebnisse zu speichern, bei denen die endgültige Anzahl der Objekte, mit denen Sie sich befassen, erst bekannt wird, wenn Sie mit allen fertig sind. Ich habe das folgende Beispiel erstellt, um dieses Konzept zu demonstrieren.

01 import java.util.Vector; 02 import java.util.Enumeration; 03 public class Demo {04 public static void main (String args []) {05 Vektorgrafiken = neuer Vektor (); 06 int result = 0; 07 08 if (args.length == 0) {09 System.out.println ("Verwendung ist Java-Demo 12345"); 10 System.exit (1); 11} 12 13 für (int i = 0; i = '0') && (c <= '9')) 16 digits.addElement (neue Ganzzahl (c - '0')); 17 sonst 18 Pause; 19} 20 System.out.println ("Es gibt" + digits.size () + "digits."); 21 für (Aufzählung e = digits.elements (); e.hasMoreElements ();) {22 result = result * 10 + ((Integer) e.nextElement ()). IntValue (); 23} 24 System.out.println (args [0] + "=" + result); 25 System.exit (0); 26} 27}

Die obige einfache Klasse verwendet ein VectorObjekt, um Ziffernzeichen aus einer Zeichenfolge zu sammeln. Die Auflistung wird dann aufgelistet, um den ganzzahligen Wert der Zeichenfolge zu berechnen. An dieser Klasse ist nichts auszusetzen, außer dass sie nicht threadsicher ist. Wenn ein anderer Thread zufällig einen Verweis auf den Ziffernvektor enthält und dieser Thread ein neues Zeichen in den Vektor einfügt, sind die Ergebnisse der Schleife in den Zeilen 21 bis 23 oben nicht vorhersehbar. Wenn das Einsetzen stattgefunden , bevor das Aufzählungsobjekt des Einfügepunkt vergangen war, der Thread Rechener würde das neue Zeichen verarbeiten. Wenn die Einfügung erfolgte, nachdem die Aufzählung die Einfügemarke überschritten hatte, würde die Schleife das Zeichen nicht verarbeiten. Das schlimmste Szenario ist, dass die Schleife möglicherweise a auslöstNoSuchElementException wenn die interne Liste kompromittiert wurde.

Dieses Beispiel ist genau das - ein erfundenes Beispiel. Es zeigt das Problem, aber wie groß ist die Wahrscheinlichkeit, dass ein anderer Thread während einer kurzen fünf- oder sechsstelligen Aufzählung ausgeführt wird? In diesem Beispiel ist das Risiko gering. Die Zeit, die vergeht, wenn ein Thread eine gefährdete Operation startet, in diesem Beispiel die Aufzählung, und die Aufgabe dann beendet, wird als Schwachstellenfenster oder Fenster des Threads bezeichnet . Dieses spezielle Fenster wird als Rennbedingung bezeichnetweil ein Thread "rast", um seine Aufgabe zu beenden, bevor ein anderer Thread die kritische Ressource (die Liste der Ziffern) verwendet. Wenn Sie jedoch Sammlungen verwenden, um eine Gruppe von mehreren tausend Elementen darzustellen, z. B. bei einer Datenbank, vergrößert sich das Fenster der Sicherheitsanfälligkeit, da die Thread-Aufzählung viel mehr Zeit in der Aufzählungsschleife verbringt und dadurch möglicherweise ein anderer Thread ausgeführt wird viel höher. Sie möchten sicher nicht, dass ein anderer Thread die Liste unter Ihnen ändert! Was Sie wollen, ist die Zusicherung, dass das EnumerationObjekt , das Sie halten, gültig ist.

Eine Möglichkeit, dieses Problem zu betrachten, besteht darin, zu beachten, dass das EnumerationObjekt vom VectorObjekt getrennt ist. Da sie getrennt sind, können sie nach ihrer Erstellung nicht mehr die Kontrolle über einander behalten. Diese lose Bindung legte mir nahe, dass ein nützlicher Weg zum Erkunden eine Aufzählung war, die enger an die Sammlung gebunden war, aus der sie hervorging.

Sammlungen erstellen

Um meine thread-sichere Sammlung zu erstellen, brauchte ich zuerst eine Sammlung. In meinem Fall wurde eine sortierte Sammlung benötigt, aber ich habe mich nicht darum gekümmert, die vollständige binäre Baumroute zu gehen. Stattdessen habe ich eine Sammlung erstellt, die ich als SynchroList bezeichnet habe . In diesem Monat werde ich mir die Kernelemente der SynchroList-Sammlung ansehen und deren Verwendung beschreiben. Nächsten Monat werde ich in Teil 2 die Sammlung von einer einfachen, leicht verständlichen Java-Klasse zu einer komplexen Multithread-Java-Klasse umwandeln. Mein Ziel ist es, das Design und die Implementierung einer Sammlung in Bezug auf die Techniken, mit denen sie threadsicher gemacht wird, eindeutig und verständlich zu halten.

Ich habe meine Klasse benannt SynchroList. Der Name "SynchroList" stammt natürlich aus der Verkettung von "Synchronisation" und "Liste". Die Sammlung ist einfach eine doppelt verknüpfte Liste, wie Sie sie in jedem Lehrbuch zum Thema Programmierung finden können, obwohl durch die Verwendung einer inneren Klasse mit dem Namen Linkeine gewisse Eleganz erreicht werden kann. Die innere Klasse Linkist wie folgt definiert:

Klasse Link {private Objektdaten; privater Link nxt, prv; Link (Objekt o, Link p, Link n) {nxt = n; prv = p; Daten = o; if (n! = null) n.prv = this; if (p! = null) p.nxt = this; } Objekt getData () {Daten zurückgeben; } Link next () {return nxt; } Link next (Link newNext) {Link r = nxt; nxt = newNext; return r;} Link prev () {return prv; } Link prev (Link newPrev) {Link r = prv; prv = newPrev; return r;} public String toString () {return "Link (" + data + ")"; }}

Wie Sie im obigen Code sehen können, Linkkapselt ein Objekt das Verknüpfungsverhalten, das die Liste zum Organisieren seiner Objekte verwendet. Um das doppelt verknüpfte Listenverhalten zu implementieren, enthält das Objekt Verweise auf sein Datenobjekt, einen Verweis auf das nächste Glied in der Kette und einen Verweis auf das vorherige Glied in der Kette. Ferner sind die Methoden nextund prevüberladen, um ein Mittel zum Aktualisieren des Zeigers des Objekts bereitzustellen. Dies ist erforderlich, da die übergeordnete Klasse Links in die Liste einfügen und löschen muss. Der Link-Konstruktor dient zum gleichzeitigen Erstellen und Einfügen eines Links. Dies speichert einen Methodenaufruf bei der Implementierung der Liste.

Another inner class is used in the list -- in this case, an enumerator class named ListEnumerator. This class implements the java.util.Enumeration interface: the standard mechanism that Java uses to iterate over a collection of objects. By having our enumerator implement this interface, our collection will be compatible with any other Java classes that use this interface to enumerate the contents of a collection. The implementation of this class is shown in the code below.

 class LinkEnumerator implements Enumeration { private Link current, previous; LinkEnumerator( ) { current = head; } public boolean hasMoreElements() { return (current != null); } public Object nextElement() { Object result = null; Link tmp; if (current != null) { result = current.getData(); current = current.next(); } return result; } } 

In its present incarnation, the LinkEnumerator class is pretty straightforward; it will become more complicated as we modify it. In this incarnation, it simply walks through the list for the calling object until it comes to the last link in the internal linked list. The two methods required to implement the java.util.Enumeration interface are hasMoreElements and nextElement.

Of course, one of the reasons we aren't using the java.util.Vector class is because I needed to sort the values in the collection. We had a choice: to build this collection to be specific to a particular type of object, thus using that intimate knowledge of the object type in order to sort it, or to create a more generic solution based on interfaces. I chose the latter method and defined an interface named Comparator to encapsulate the methods necessary to sort objects. That interface is shown below.

 public interface Comparator { public boolean lessThan(Object a, Object b); public boolean greaterThan(Object a, Object b); public boolean equalTo(Object a, Object b); void typeCheck(Object a); } 

As you can see in the above code, the Comparator interface is pretty simple. The interface requires one method for each of the three basic comparison operations. Using this interface, the list can compare the objects that are being added or removed with objects that are already on the list. The final method, typeCheck, is used to ensure type safety of the collection. When the Comparator object is used, the Comparator can be used to insure that objects in the collection are all of the same type. The value of this type checking is that it saves you from seeing object casting exceptions if the object in the list was not of the type you expected. I've got an example later on that uses a Comparator, but before we get to the example, let's look at the SynchroList class directly.

 public class SynchroList { class Link { ... this was shown above ... } class LinkEnumerator implements Enumeration { ... the enumerator class ... } /* An object for comparing our elements */ Comparator cmp; Link head, tail; public SynchroList() { } public SynchroList(Comparator c) { cmp = c; } private void before(Object o, Link p) { new Link(o, p.prev(), p); } private void after(Object o, Link p) { new Link(o, p, p.next()); } private void remove(Link p) { if (p.prev() == null) { head = p.next(); (p.next()).prev(null); } else if (p.next() == null) { tail = p.prev(); (p.prev()).next(null); } else { p.prev().next(p.next()); p.next().prev(p.prev()); } } public void add(Object o) { // if cmp is null, always add to the tail of the list. if (cmp == null) { if (head == null) { head = new Link(o, null, null); tail = head; } else { tail = new Link(o, tail, null); } return; } cmp.typeCheck(o); if (head == null) { head = new Link(o, null, null); tail = head; } else if (cmp.lessThan(o, head.getData())) { head = new Link(o, null, head); } else { Link l; for (l = head; l.next() != null; l = l.next()) { if (cmp.lessThan(o, l.getData())) { before(o, l); return; } } tail = new Link(o, tail, null); } return; } public boolean delete(Object o) { if (cmp == null) return false; cmp.typeCheck(o); for (Link l = head; l != null; l = l.next()) { if (cmp.equalTo(o, l.getData())) { remove(l); return true; } if (cmp.lessThan(o, l.getData())) break; } return false; } public synchronized Enumeration elements() { return new LinkEnumerator(); } public int size() { int result = 0; for (Link l = head; l != null; l = l.next()) result++; return result; } }