Musterlösungen

Laboraufgabe “SynchronizedCollection-Wrapper”

Durch Hinzufügen von implements List<T> kann man in Eclipse leicht die zu überschreibenden Methodenrümpfe generieren lassen.

Lösungsalternative mit gegenseitigem Ausschluss über `synchronized`

Jede generierte Methode muss synchronized gekennzeichnet werden. Dadurch wird der Zugriff auf jede dieser Methoden für sich threadsicher (durch gegenseitigen Ausschluss über den Monitor this). Denkbar wäre decorated als Monitor zu verwenden, doch so arbeitet java.util.synchonizedList etc. nicht, u.a. damit es nicht zu Verklemmungen wegen anderweitiger Nutzung von decorated als Monitor kommt.

Die Implementierung jeder zu überschreibenden Methode erfolgt dann durch die Anwendung derselben (unsynchronisierten) Methode an der dekorierten Collection-Instanz:

package pp;

import java.util.Collection;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;

public class SynchWrapper<T> implements List<T> {
    private final List<T> decorated;

    public static <T> List<T> synchronizedList(List<T> list) {
        return new SynchWrapper<>(list);
    }

    private SynchWrapper(List<T> list) {
        this.decorated = list;
    }

    @Override
    public synchronized int size() {
        return this.decorated.size();
    }

    @Override
    public synchronized boolean isEmpty() {
        return this.decorated.isEmpty();
    }

    @Override
    public synchronized boolean contains(Object o) {
        return this.decorated.contains(o);
    }

    @Override
    public synchronized Iterator<T> iterator() {
        return this.decorated.iterator();
    }

    @Override
    public synchronized Object[] toArray() {
        return this.decorated.toArray();
    }

    @Override
    public synchronized <T> T[] toArray(T[] a) {
        return this.decorated.toArray(a);
    }

    @Override
    public synchronized boolean add(T e) {
        return this.decorated.add(e);
    }

    @Override
    public synchronized boolean remove(Object o) {
        return this.decorated.remove(o);
    }

    @Override
    public synchronized boolean containsAll(Collection<?> c) {
        return this.decorated.containsAll(c);
    }

    @Override
    public synchronized boolean addAll(Collection<? extends T> c) {
        return this.decorated.addAll(c);
    }

    @Override
    public synchronized boolean addAll(int index, Collection<? extends T> c) {
        return this.decorated.addAll(index, c);
    }

    @Override
    public synchronized boolean removeAll(Collection<?> c) {
        return this.decorated.removeAll(c);
    }

    @Override
    public synchronized boolean retainAll(Collection<?> c) {
        return this.decorated.retainAll(c);
    }

    @Override
    public synchronized void clear() {
        this.decorated.clear();
    }

    @Override
    public synchronized T get(int index) {
        return this.decorated.get(index);
    }

    @Override
    public synchronized T set(int index, T element) {
        return this.decorated.set(index, element);
    }

    @Override
    public synchronized void add(int index, T element) {
        this.decorated.add(index, element);
    }

    @Override
    public synchronized T remove(int index) {
        return this.decorated.remove(index);
    }

    @Override
    public synchronized int indexOf(Object o) {
        return this.decorated.indexOf(o);
    }

    @Override
    public synchronized int lastIndexOf(Object o) {
        return this.decorated.lastIndexOf(o);
    }

    @Override
    public synchronized ListIterator<T> listIterator() {
        return this.decorated.listIterator();
    }

    @Override
    public synchronized ListIterator<T> listIterator(int index) {
        return this.decorated.listIterator(index);
    }

    @Override
    public synchronized List<T> subList(int fromIndex, int toIndex) {
        return this.decorated.subList(fromIndex, toIndex);
    }

}

Lösungsalternative mit Anwendung eines `ReadWriteLock`

Für jede Methode muss analysiert werden, ob sie die Liste ändert oder ob der Zugriff nur lesend ist. Für die lesenden reicht der Read-Lock, für die ändernden muss es der Write-Lock eines gemeinsamen ReentrantReadWriteLock-Objekts sein, das als private Instanzvariable des Wrappers erzeugt wird und damit exklusiv für die zu wrappende Liste verwendet wird.

package pp;

import java.util.Collection;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReadWriteLock;
import java.util.concurrent.locks.ReentrantReadWriteLock;

public class SynchWrapperRW<T> implements List<T> {
    private final List<T> decorated;
    private final ReadWriteLock lock;
    private final Lock rLock;
    private final Lock wLock;

    public static <T> List<T> synchronizedList(List<T> list) {
        return new SynchWrapperRW<>(list);
    }

    private SynchWrapperRW(List<T> list) {
        this.decorated = list;
        this.lock = new ReentrantReadWriteLock();
        this.rLock = this.lock.readLock();
        this.wLock = this.lock.writeLock();
    }

    @Override
    public int size() {
        this.rLock.lock();
        try {
            return this.decorated.size();
        } finally {
            this.rLock.unlock();
        }
    }

    @Override
    public boolean isEmpty() {
        this.rLock.lock();
        try {
            return this.decorated.isEmpty();
        } finally {
            this.rLock.unlock();
        }
    }

    @Override
    public boolean contains(Object o) {
        this.rLock.lock();
        try {
            return this.decorated.contains(o);
        } finally {
            this.rLock.unlock();
        }
    }

    @Override
    public Iterator<T> iterator() {
        this.rLock.lock();
        try {
            return this.decorated.iterator();
        } finally {
            this.rLock.unlock();
        }
    }

    @Override
    public Object[] toArray() {
        this.rLock.lock();
        try {
            return this.decorated.toArray();
        } finally {
            this.rLock.unlock();
        }
    }

    @Override
    public <T> T[] toArray(T[] a) {
        this.rLock.lock();
        try {
            return this.decorated.toArray(a);
        } finally {
            this.rLock.unlock();
        }
    }

    @Override
    public boolean add(T e) {
        this.wLock.lock();
        try {
            return this.decorated.add(e);
        } finally {
            this.wLock.unlock();
        }
    }

    @Override
    public boolean remove(Object o) {
        this.wLock.lock();
        try {
            return this.decorated.remove(o);
        } finally {
            this.wLock.unlock();
        }
    }

    @Override
    public boolean containsAll(Collection<?> c) {
        this.rLock.lock();
        try {
            return this.decorated.containsAll(c);
        } finally {
            this.rLock.unlock();
        }
    }

    @Override
    public boolean addAll(Collection<? extends T> c) {
        this.wLock.lock();
        try {
            return this.decorated.addAll(c);
        } finally {
            this.wLock.unlock();
        }
    }

    @Override
    public boolean removeAll(Collection<?> c) {
        this.wLock.lock();
        try {
            return this.decorated.removeAll(c);
        } finally {
            this.wLock.unlock();
        }
    }

    @Override
    public boolean retainAll(Collection<?> c) {
        this.wLock.lock();
        try {
            return this.decorated.retainAll(c);
        } finally {
            this.wLock.unlock();
        }
    }

    @Override
    public void clear() {
        this.wLock.lock();
        try {
            this.decorated.clear();
        } finally {
            this.wLock.unlock();
        }
    }

    @Override
    public T get(int index) {
        this.rLock.lock();
        try {
            return this.decorated.get(index);
        } finally {
            this.rLock.unlock();
        }
    }

    @Override
    public T set(int index, T element) {
        this.wLock.lock();
        try {
            return this.decorated.set(index, element);
        } finally {
            this.wLock.unlock();
        }
    }

    @Override
    public void add(int index, T element) {
        this.wLock.lock();
        try {
            this.decorated.add(index, element);
        } finally {
            this.wLock.unlock();
        }
    }

    @Override
    public T remove(int index) {
        this.wLock.lock();
        try {
            return this.decorated.remove(index);
        } finally {
            this.wLock.unlock();
        }
    }

    @Override
    public int indexOf(Object o) {
        this.rLock.lock();
        try {
            return this.decorated.indexOf(o);
        } finally {
            this.rLock.unlock();
        }
    }

    @Override
    public int lastIndexOf(Object o) {
        this.rLock.lock();
        try {
            return this.decorated.lastIndexOf(o);
        } finally {
            this.rLock.unlock();
        }
    }

    @Override
    public ListIterator<T> listIterator() {
        this.rLock.lock();
        try {
            return this.decorated.listIterator();
        } finally {
            this.rLock.unlock();
        }
    }

    @Override
    public ListIterator<T> listIterator(int index) {
        this.rLock.lock();
        try {
            return this.decorated.listIterator(index);
        } finally {
            this.rLock.unlock();
        }
    }
    @Override
    public List<T> subList(int fromIndex, int toIndex) {
        this.rLock.lock();
        try {
            return this.decorated.subList(fromIndex, toIndex);
        } finally {
            this.rLock.unlock();
        }
    }

}

Unit-Tests

package pp;

import org.junit.jupiter.api.Test;

import static org.junit.jupiter.api.Assertions.*;

import java.util.ArrayList;
import java.util.List;

class Tests {
  private final static int SIZE = 10000;

  static void testAdd(List<Integer> l) {
    var t1 = new Thread(() -> {
      for (var i = 0; i < SIZE; i++) {
        l.add(Integer.valueOf(i));
      }
    });
    var t2 = new Thread(() -> {
      for (var i = 0; i < SIZE; i++) {
        l.add(Integer.valueOf(i));
      }
    });
    t1.start();
    t2.start();
    try {
      t1.join();
      t2.join();
      assertEquals(l.size(), SIZE * 2);
    } catch (InterruptedException e) {
      fail("Interrupt");
    }
  }

  @Test
  void testWrappedListSynchronizedAdd() {
    testAdd(SynchWrapper.synchronizedList(new ArrayList<Integer>()));
  }

  @Test
  void testWrappedListReadWriteLockAdd() {
    testAdd(SynchWrapperRW.synchronizedList(new ArrayList<Integer>()));
  }

  @Test
  void testWrappedListLombokLockAdd() {
    testAdd(SynchWrapperLombok.synchronizedList(new ArrayList<Integer>()));
  }

  @Test
  void testWrappedListReadWriteiLombokLockAdd() {
    testAdd(SynchWrapperRWLombok.synchronizedList(new ArrayList<Integer>()));
  }

}

Laboraufgabe “Experimenteller Vergleich von Container-Varianten”

Implementierung der Versuchsbedingungen (“Varianten”)

Die unabhängigen Variablen sind Größe der Aufgabe und Listenimplementierung. Die Größe der Aufgabe wird durch die Länge der Liste variiert, die bei der Methode work in ExperimentVector vom int-Parameter size abhängig ist.

Als abhängige Variable soll die Laufzeit gemessen werden. Die Aufgabe muss daher (abgesehen von der UV “Größe der Aufgabe”) in jeder Versuchsbedingung identisch sein.

Da die Implementierung von Vector bereits threadsicher ist, kann sie als Vorlage verwendet werden.

Die eine unabhängige Variable “Listenimplementierung” wird darüber realisiert, dass die work-Methode wie in ExperimentVector in entsprechenden Klassen dupliziert wird. In jeder dieser Klassen wird eine andere Implementierung von List verwendet:

ExperimentVector: new Vector<>()
ExperimentArrayList: new ArrayList<>()
ExperimentLinkedList: new LinkedList<>()
ExperimentSynchedArrayList: Collections.synchronizedList(new ArrayList<>())
ExperimentSynchedLinkedList: Collections.synchronizedList(new LinkedList<>())
ExperimentSynchedLinkedListRO: synchronized List für ändernden Zugriff, unmodifiable List für lesenden Zugriff

Als Listenimplementierung werden hier also die folgenden Container-Datenstrukturen verwendet:

ArrayList
LinkedList

Diese beiden Implementierungen sind nicht threadsicher. Damit sie in einer Multi-Threadumgebung eingesetzt werden können, muss man für die Koordination des nebenläufigen Zugriffs sorgen. Dafür werden hier die folgenden Mechanismen verwendet:

synchronized (Monitor ist die Liste)
Collections.synchronizedList()
Analog zum DesignPattern ReadWriteLock: Collections.synchronizedList() kombiniert mit Collections.unmodifiableList()

Die Zugriffe sind hier nicht in nicht-unterbrechbare “Transaktionen” eingebettet, sondern jeder Zugriff steht für sich. Also muss nur jeder einzelner Zugriff durch einen Koordinationsmechanismus geschützt werden.

Bei den synchronized-Varianten wird das durch die folgenden Konstrukte umgesetzt:

synchronized (this.list) {
    this.list.add(1);
}

bzw.

synchronized (this.list) {
    this.countA += this.list.get(i);
}

this.list wird hier entweder mit einer Instanz von ArrayList oder LinkedList initialisiert.

Bei den Varianten mit Wrapper wird this.list hingegen durch die Verwendung der Factory-Methode synchronizedList von Collections initialisiert. Jeder einzelne Zugriff ist damit dann schon synchronized und muss daher nicht noch extra geschützt werden:

this.list.add(1);

bzw.

this.countA += this.list.get(i);

Bei der Variante ExperimentSynchedLinkedListRO werden zwei Wrapper erzeugt.

Achtung:

Die zwei unterschiedlichen Wrapper für dasselbe Objekt sind im Gegensatz zum Read-Write Lock-Entwurfsmuster nicht gegeneinander verschränkt, sondern stellen unabhängig voneinander jeweils einen (semantisch unterschiedlichen) Zugriffsmechanismus auf die originale Liste (im Beispiel von ExperimentSynchedLinkedListRO eine Instanz von LinkedList) dar. Die Kombination von unmodifiable List und synchronized List ist daher im Gegensatz zum Read-Write Lock-Entwurfsmuster nicht universell einsetzbar!

this.list = new LinkedList<>();
this.listSynch = Collections.synchronizedList(this.list);
this.listRO = Collections.unmodifiableList(this.list);

Die ändernden Zugriffe erfolgen dann am synchronized List-Wrapper:

this.listSynch.add(1);

Die lesenden Zugriffe hingegen am unmodifiable List-Wrapper:

this.countA += this.listRO.get(i);

`Main`

In der Main-Klasse werden die work-Methoden der unterschiedlichen Implementierungen aufgerufen. Aus der umgebenen Schleife wird ein Parameter mit der unabhängigen Variable “Aufgabengröße” (i) in Zehnerpotenzen hochgezählt.

Visualisierung

Die unabhängigen Variablen werden als Spalte und Zeile in einer Tabelle verwendet. Die gemessene Ausprägung der abhängigen Variablen in den jeweiligen Zellen eintragen.

In einem beispielhaften Durchlauf auf einem Macbook Pro Retina 2015 (4 Cores, availableProcessors() \(=\) 8) ergaben sich folgende Messungen (AL = ArrayList, LL = LinkedList):

Messungen (beispielhaft)

UV’s	Vector	ArrayList	LinkedList	SynchedAL	SynchedLL	SynchedLLRO
100	12 ms	17 ms	17 ms	19 ms	19 ms	15 ms
1000	15 ms	20 ms	28 ms	21 ms	15 ms	25 ms
10000	54 ms	19 ms	398 ms	8 ms	360 ms	222 ms
100000	97 ms	132 ms	54089 ms	58 ms	47633 ms	20578 ms

Visualisierung

Es zeigt sich, dass die Varianten LinkedList/ArrayList (gegenseitiger Ausschluss mit synchronized(this.list)) und SynchedLinkedList/SynchedArrayList (gegenseitiger Ausschluss über synched List-Wrapper) jeweils einen vergleichbaren Aufwand haben, wobei die Variante mit dem Wrapper etwas effizienter ist.

Die LinkedList-Variante mit doppeltem Wrapper (getrennt nach lesend und ändernd) ist ebenso vergleichbar aber wegen des größeren Potenzials für Parallelverarbeitung wiederum effizienter als die anderen beiden LinkedList-Varianten.

Da bei den lesenden Zugriffen bei LinkedList der Aufwand O(N) ist und bei ArrayList O(1) und zudem auch die ändernden Zugriffe bei ArrayList im Mittel effizienter als bei LinkedList erfüllt die Messung der insgesamt geringeren Aufwände für die ArrayList- verglichen mit den LinkedList-Varianten die Erwartungen.

Laboraufgabe “SynchronizedCollection-Wrapper”

Lösungsalternative mit gegenseitigem Ausschluss über synchronized

Lösungsalternative mit Anwendung eines ReadWriteLock

Unit-Tests

Verwandte Arbeiten

Laboraufgabe “Experimenteller Vergleich von Container-Varianten”

Implementierung der Versuchsbedingungen (“Varianten”)

Achtung:

Main

Visualisierung

Messungen (beispielhaft)

Visualisierung

Lösungsalternative mit gegenseitigem Ausschluss über `synchronized`

Lösungsalternative mit Anwendung eines `ReadWriteLock`

`Main`