Reentrent Lock

[Sophie]

Hallo!

Ich versuche gerade eine LinkedList mit Hilfe von Reentrent Lock zu synchronisieren. Aber es funktioniert nicht richtig.

public void insert(int index, Object elem) {

		if (!isInRemovedNodesList(index) && inRemove == false) {
			
			 if (index < 0 || index > size) {
			 throw new IndexOutOfBoundsException();

			 }
			if (index == 0 && size == 0) {
				synchronized (this) {
					if (head == null) {
						Node<E> newNode = new Node<E>(elem, null);
						newNode.next = head;
						head = newNode;
						size++;
					}
				}
			} else {
				head.lock.lock();
				Node<E> n = head;
					for (int i = 0; i < index; i++) {
						n = n.next;
					}
					
				head.lock.unlock();
				if (n == null) {
					head.lock.lock();
					Node<E> nn = head;
						for (int i = 0; i < index - 1; i++) {
							nn = nn.next;
					}
					head.lock.unlock();
					Node<E> pred = nn;
					pred.lock.lock();
					Node<E> newNode = new Node<E>(elem, null);
					newNode.next = pred.next;
					pred.next = newNode;
					pred.lock.unlock();
					size++;
				}
			}
		}
	}

Das Problem ist, dass Elemente doppelt eingesetzt werden.

7 8 9 10 11 12 12 13 13 14 15 16

Weiss jemand woran das liegt?

 

[Kr0e]

Hab grad keine Zeit , das zu durchdenken, aber ein kleiner Tipp am Rande:

Locks IMMMER mit try{} finally{} benutzen. Falls eine exeption dazwischen geschieht, werden locks evt sonst nicht mehr frei gegeben...

 

[Sophie]

Hallo

ja, habe ich auch gerade nachgelesen und ausprobiert

	public void insert(int index, Object elem) {

		if (!isInRemovedNodesList(index) && inRemove == false) {
			
			 if (index < 0 || index > size) {
			 throw new IndexOutOfBoundsException();

			 }
			if (index == 0 && size == 0) {
				synchronized (this) {
					if (head == null) {
						Node<E> newNode = new Node<E>(elem, null);
						newNode.next = head;
						head = newNode;
						size++;
					}
				}
			} else {
				head.lock.lock();
				try {
				Node<E> n = head;
					for (int i = 0; i < index; i++) {
						n = n.next;
					}

				if (n == null) {

					Node<E> nn = head;
						for (int i = 0; i < index - 1; i++) {
							nn = nn.next;
					}

					Node<E> pred = nn;
					pred.lock.lock();
					try {
					Node<E> newNode = new Node<E>(elem, null);
					newNode.next = pred.next;
					pred.next = newNode;
					System.out.println(Thread.currentThread().getName());
					
					size++;
					} finally {
						pred.lock.unlock();
					}
				}
				}finally {
					head.lock.unlock();
				}
			}
		}
	}

Jetzt geht aber nur noch ein Thread rein, die anderen machen gar nichts. Sollte auch nicht so sein, oder?

 

[Kr0e]

Das hat aber dann nichts mit deiner Impl. zu tun. Wenn mehrere Threads auf die locked-Abschnitte zugreifen, und die Locks keinen Deadlock verursachen, dann müsste alle threads, die drum kämpfen eigentlcih mal an die Reihe kommen.

Als kleine Anregung: Locks und synchronisierte Abschnitte sollte man vermeiden, wo immer es geht. Jedes der beiden Verfahren verursacht einen Contextwechsel im Thread-scheduling. Intern ist sowas sehr viel teurer als keinen lock zu verwenden. Na klar, hin und wieder kann man das nciht verhindern, Locks zu benutzen aber es gibt da eine Reihe von Sekundärtechniken, z.B. Lockfree-Programming oder viel mit Immutable-Types arbeiten / volatile / Atomic etc.

Ich persönlcih würde mir 5 mal überlegen, im Zeitalter von Multicore Prozessoren Locks zu benutzen.
Falls hier Interesse deinerseits besteht, empfehle ich um jeden Preis diese Präsentation:

JAX TV: Java-Programmierung im Multicore-Zeitalter

Dort werden typische Probleme aufgezeigt und behandelt.

Deine Impl. sieht so aus, als ob du eine Liste oder ähnliches versuchst zu implementieren. Es gibt von Java hier ausgesprochen effiziente Klassen (Concurrent*Queue etc.).

Gruß,

Chris