Synchronisieren einer Linked List

[Sophie]

Hallo Zusammen

Ich versuche gerade eine LinkedList zu synchronisieren und habe das Problem, dass ich "head" nicht locken kann, ich bekomme eine NullPointerException. Kann mir bitte jemand weiterhelfen, mein Programm so umzustellen, dass das funktioniert?

Das ist die Klasse Node:

public class Node<E> {

	public Object element;
	public Node<E> next;
	Lock lock = new ReentrantLock();


	public Node(Object e, Node<E> n) {
		element = e;
		next = n;

	}
}

Hier der Konstruktor der LinkedList Klasse

public class LinkedListSynchronizedElement<E> {

	int size;
	Node<E> prev; 
	private Node<E> head;

	public LinkedListSynchronizedElement() {

		size = 0;
		head = null;

	}

Und hier die Methode "add" die ich synchronisieren möchte

	public void insert(int index, Object elem) {

		// Create the new node
		Node<E> newNode = new Node<E>(elem, null);
		newNode.lock.lock();
		head.lock.lock();

		// Beginning of List
		if (index == 0) {
			newNode.next = head;
			head = newNode;
		} else {
			Node<E> prev = nodeAt(index - 1);
			newNode.next = prev.next;
			prev.next = newNode;
			newNode.lock.unlock();
		}
		size++;
	}

 

[Paddelpirat]

Hmm du setzt den head im Konstruktor ja auch auf null. Da wundert es mich nicht wenn du bei head.lock.lock() eine NullPointerException bekommst. Die bekommst du sogar schon vor dem eigentlichen lock(), bei head.lock.

 

[Sophie]

Ich überlege gerade ob es auch nicht einfach ausreicht, newNode und prev zu locken, was meint Ihr?
Head muss ich ja irgendwo initialisieren, oder?

 

[Paddelpirat]

Wenn ich das richtig sehe fehlen dir bei deiner insert Methode auch noch ein paar Fälle.

z.B.

1. Falls die Liste leer ist und du an der Stelle 0 ein Element hinzufügst, dann wird dieses Element der Head. und Head.next() zeigt wieder auf Head.

2. Falls es schon Elemente in der Liste gibt und du ein Element an der Stelle 0 hinzufügst, dann muss der Head neu gesetzt werden. Head.next() zeigt auf das nächste Element in der Liste und das letzte Element der Liste muss auf den neuen Head gesetzt werden.

3. Falls der Index kleiner 0 oder größer als die Länge der Liste ist, dann solltest du wohl eine Exception werfen.

usw.

Ich würde erst einmal die Grundlegenden Funktionen implementieren und anschließend schauen in welchem Fall du welche Elemente locken musst. Da siehst du ja dann eigentlich auch, wann du dein Head-Element initialisierst. Locken ohne Initialisierung macht halt nicht viel Sinn.

Musst du das eigentlich alles per Hand machen, oder würde nicht sowas besser Funktionieren:

List list = Collections.synchronizedList(new LinkedList(...));

 

[Sophie]

Hallo

Ne, wir müssen alles selber machen.

also ich habe das hier der Methode noch hinzugefügt

if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("index: " + index);
        }

aber den Fall, an index 0 einfügen habe ich ja schon, das wird ja alles zum head was ich dort einfüge, egal wie lange die liste ist, oder?

ich glaube ich habs jetzt auch geschafft 🙂

Vielen Dank für die Hilfe

 

[Paddelpirat]

Mein Fehler mit Index 0. Hatte noch in Erinnerung, dass das letzte Element der Liste wieder auf das erste Element zeigen muss, also praktisch ein Zirkel. Das brauchst du ja gar nicht, von daher ist dein Code da richtig.

Schön, dass es jetzt funktioniert 🙂

 

[Sophie]

Oh nein!
Zu früh gefreut
Das hier

	public void insert(int index, Object elem) {

		if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("index: " + index);
        }
		// Create the new node
		Node<E> newNode = new Node<E>(elem, null);
		// Beginning of List
		if (index == 0) {
			newNode.lock.lock();
			newNode.next = head;
			head = newNode;
			newNode.lock.unlock();
		} else {
			newNode.lock.lock();		
			Node<E> prev = nodeAt(index - 1);
			prev.lock.lock();
			newNode.next = prev.next;
			prev.next = newNode;
			newNode.lock.unlock();
			prev.lock.unlock();
		}
		size++;
	}

Ist immernoch langsamer als das hier:

public synchronized void insert(int index, Object elem) {

		// Create the new node
		Node<E> newNode = new Node<E>(elem, null);

		// Beginning of List
		if (index == 0) {
			newNode.next = head;
			head = newNode;
		} else {
			Node<E> prev = nodeAt(index - 1);
			newNode.next = prev.next;
			prev.next = newNode;
		}
		size++;
		notifyAll();
	}

Das sollte nicht so sein, oder?

 

[hdi]

Wie kommst du darauf dass die Version mit dem ReentrantLock schneller sein sollte als die mit synchronized? Wieviele Threads greifen denn auf die Daten zu?

 

[Sophie]

Ich habe es mit unterschiedlicher Anzahl von Threads und unterschiedlicher Anzahl von Elementen versucht.

Ich dachte das geht schneller, weil ich nur bestimmte Teile der Liste locke und wenn jetzt zum Beispiel vorne an der Liste eingefügt oder gelöscht wird, kann im anderen Teil, der nicht betroffen wird auch eingefügt oder gelöscht werden.

 

[hdi]

Ich dachte das geht schneller, weil ich nur bestimmte Teile der Liste locke und wenn jetzt zum Beispiel vorne an der Liste eingefügt oder gelöscht wird, kann im anderen Teil, der nicht betroffen wird auch eingefügt oder gelöscht werden.

Und zielt dein Testcase auch auf dieses Szenario ab?

Aber, ich glaub du hast das eh falsch gemacht. Die newNode musst du nicht locken, denn das ist eine lokale Variable. Darauf greift garantiert kein anderer Thread zu. Dafür machst du bei der Zuweisung zum head kein lock auf den head, und das müsstest du tun, denn auf head kann durchaus ein anderer Thread in dieser Zeit zugreifen. (Jeder, der bei index 0 oder 1 einfügen will)

Es müsste so aussehen:

 if (index == 0) {
            head.lock.lock();
            newNode.next = head;
            head = newNode;
            head.lock.unlock();
        } else {    
            Node<E> prev = nodeAt(index - 1);
            prev.lock.lock();
            newNode.next = prev.next;
            prev.next = newNode;
            prev.lock.unlock();
        }

 

[Sophie]

ja, ich wollte eigentlich auch den head locken. bekomme dann aber eine NullPointerException. Deshalb habe ich eigentlich das Thema gestartet. Weisst Du, wie ich das lösen kann?

 

[hdi]

Naja du musst den Spezialfall bedenken, wenn das allererste Element eingefügt wird. Du initialisiert deine Liste ja mit head = null. Ist klar, dass dann bei head.lock eine NPE fliegt. Also nimm noch ein if-Statement in deine insert Methode rein: Falls noch kein Head vorhanden, dann erstmal erstellen. Dies geht dann blöderweise nicht über dein ReentrantLock. Denn du hast ja noch nix, auf dessen lock du locken könntest 😉 D.h. in diesem Spezialfall kommst du doch nicht um ein einmaliges synchronized rum:

// insert-Methode
if( head == null ){
    synchronized(this){
        if(head == null){ // nochmalige Prüfung notwendig!
            head = newNode;
        }
    }
}

Alternativ initialisierst du head bei der Erzeugung der Liste mit irgendeinem Pseudo-Wert. Den musst du dann natürlich nach wie vor abfragen, aber dann kannst du auf's synchronized verzichten und kriegst beim Zugriff auf head.lock keine NPE.

Übrigens solltest du das, was du tust, etwas mehr hinterfragen. Einfach mal hirnlos* head.lock austauschen gegen newNode.lock, weil du eine NPE bekommst, die du scheinbar gar nicht verstehst, ist nicht so ne optimale Lösung 😉 Du weißt glaub ich auch gar nicht wie das Locking funktioniert. Denn die müsste klar sein, dass dein Code überhaupt teilweise gar nicht synchronisiert war.

* ist nicht so unfreundlich gemeint wie es sich liest 😉

 

[Sophie]

Du weißt glaub ich auch gar nicht wie das Locking funktioniert. Denn die müsste klar sein, dass dein Code überhaupt teilweise gar nicht synchronisiert war.

Was meinst Du damit? Weil ich head nicht gelockt habe, oder sind da noch mehr Fehler?

So ganz versteh ich das tatsächlich noch nicht. Deshalb auch die Übung 🙂

 

[hdi]

Ok Crashkurs Synchronisation:

Voraussetzung dafür, dass sich x Threads synchronisieren (was nötig ist, wenn sie (zumindest teilweise) auf die selben Daten zugreifen) ist, dass alle x Threads auf ein (und das selbe!) Lock synchronisieren.

synchronized(object){ code }

bedeutet: Wenn ein Thread an diesem Code ankommt, kann er den code-Block nur dann betreten, wenn grad kein anderer Thread innerhalb dieses Blocks steckt. Denn: Der Thread checkt, ob der Monitor (die Sperre, also das Lock) des Objekts vorhanden ist. Wenn ja,
1) nimmt er das Lock
2) fürht den code-Block aus
3) legt das Lock zurück
Wenn nein, wartet er, bis das Lock wieder da ist. Alles, was nicht in so einem synchronized-Block steckt, kann von mehreren Threads (pseudo-)parallel ausgeführt werden, und dann lauert die Gefahr von Race Conditions. In der Version, wo die gesamte insert-Methode synchronized ist, heißt das also, dass immer nur ein Thread in der Methode stecken kann. Ich glaube das ist dir noch klar.

Bei ReentrentLock ist es nun genauso, nur dass das Nehmen und Zurücklegen des Locks nicht automatisch geschieht, sondern über .lock() und .unlock() gehandelt wird.

Denkfehler #1 in deiner Version war:
Du lockst auf eine lokale Variable. Lokale Variablen existieren immer nur für den entsprechenden Thread, der die Deklaration durchläuft. Es ist kein Objekt, welches global für alle Threads vorhanden ist. Also ist Synchronisation nicht nötig (siehe erster Absatz in diesem Post), und dieses lock/unlock auf newNode bringt dir rein gar nix.

Denkfehler #2:
head ist keine lokale Variable, sondern eine Instanz-Variable deiner Liste. Und all deine Threads arbeiten auf der selben Liste. Also ist Synchronisation nötig (siehe wieder erster Absatz). Aber du synchronisierst den Zugriff auf head nicht. Deswegen muss es eben head.lock/unlock heißen, damit du das synchronisierst.

oder sind da noch mehr Fehler?

Wie gesagt die Sache, dass head ja bei der Erzeugung der Liste null ist. Weißt du, was eine NPE ist? Das bedeutet, du hast einen Zugriff (geschieht über den Punkt : head.) auf eine Variable die gar nix referenziert. Du kannst alos nicht head.irgendwas schreiben, solange head == null ist. Du musst also dieses head erstmal initialisieren, um darauf synchronisieren zu können.

Aber damit nicht zwei Threads gleichzeitig versuchen, den ersten Eintrag zu setzen, musst du das wiederum synchronisieren. Und das ist der Code, den ich dir vorhin gegeben habe.

...Kann sein, dass ich dich noch mehr verwirrt habe. Synchronisation ist ein sehr schwieriges Thema.

Mein Tipp: Solange du das noch übst, verzichte auf ReentrentLocks, und belasse es beim normalen synchronized. Das musst du erstmal richtig verstehen... Ich würde sagen wenn dir klar ist, dass die erste Version (synchronized void insert) funktioniert, und warum/wie sie funktioniert, dann reicht das erstmal.

edit: Solltest du lesen:
AngelikaLanger.com - Articles by Angelika Langer & Klaus Kreft - Angelika Langer Training/Consulting

Die ersten paar Artikel zum Thema "concurrent programming" sollte erstmal reichen.

 

[Sophie]

Vielen Dank für den Link!

 

[Sophie]

Hallo

ich bin immernoch am ausprobieren und habe mal eine Frage zur Matrixmultiplikation.

Ich verwende diesen Algorithmus hier:

matrixC = new int[size][size];
			
		for (int i = 0; i < matrixA.length; i++) {
			for (int j = 0; j < size; j++) {
				for (int k = 0; k < size; k++) {
					matrixC[i][j] += matrixA[i][k] * matrixB[k][j];				
				}
			}
		}

Ich weiss, es gibt noch schnellere vor allem bei grossen Matrizen. Aber warum dauert denn das Programm länger wenn ich Threads verwende?
Oder mach ich irgendwas mit dem start() falsch? (Ich habs mit ner Größe von 999 getestet, also 10 Threads)

Thread[] ts;
		
		if (ro_co <= 100) {
			ts = new Thread[2];
			ro_co = 2;
		} else if (ro_co <= 1000) {
			ts = new Thread[10];
			ro_co = 10;
		} else {
			ts = new Thread[15];
			ro_co = 15;
		}
		

		for (int k = 0; k < ro_co; k++) {
			ts[k] = new Thread(new MatrixMultiplication(arrA, arrB));
			ts[k].setName(Integer.toString(k));
			ts[k].start();
		}
		
		for (int j = 0; j < ro_co; j++) {
			try {
				ts[j].join();
			} catch (InterruptedException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
		}

 

[Sophie]

Hallo, und wieder zurück bei der Linked List

Ich hab mal eine eher allgemeine Frage, da ich nicht weiss, wie ich die Testklasse schreiben soll.

Also Aufgabe ist es eine Linked List so zu synchronisieren, dass die Methoden einfügen(int index, Object element) und löschen(int index) parallel laufen können.
Im ersten Teil dieser Aufgabe sollen wir ersteinmal versuchen, dass immer nur ein Thread gleichzeitig auf die Liste zugreifen kann.
Ich glaube, dass ist jetzt nicht das Problem, aber jetzt möchte ich das ganze testen.

Wenn ich jetzt eine run()-Methode habe, und dann die Liste mit 60 elementen mit insert() auffülle und in dieser run()-Methode auch remove() habe, mit der Bedingung, erst anfangen zu löschen, wenn die Liste 30 Elemente hat.
Wenn ich das so teste, sehe ich zwar, dass insert() und remove() gleichzeitig ausgeführt werden können, nur ist es so, dass wenn ein Thread schon in remove() löscht und noch ein anderer in insert() ist wird die Liste wieder aufgefüllt, was ja nicht passieren soll.

Könnt ihr mir weiterhelfen, wie ich hierfür einen Testcase schreibe?