제이온

[Java] Szinkronizált gyűjtemény vs. egyidejű gyűjtemény

  • Írás nyelve: Koreai
  • Országkód: Minden országcountry-flag
  • Informatika

Létrehozva: 2024-04-25

Létrehozva: 2024-04-25 22:31

Szinkronizált gyűjtemény

A szinkronizált gyűjtemények leggyakoribb osztályai a következők:


  • Vector
  • Hashtable
  • Collections.synchronizedXXX


Mindezen osztályok a nyilvánosan deklarált metódusokban a synchronized kulcsszót használják, így biztosítják, hogy egyszerre csak egy szál férjen hozzá a belső értékekhez, ami biztosítja a szinkronitást.


Vector

```javascript public class Vector extends AbstractList implements List, RandomAccess, Cloneable, java.io.Serializable { ... public synchronized boolean add(E e) { modCount++; add(e, elementData, elementCount); return true; } ... }

A Vector osztály add() metódusában, amely elem hozzáadására szolgál, látható a synchronized kulcsszó. Ez azt jelenti, hogy a Vectoron belül az elem beszúrásának művelete szinkronizált.

Hashtable

```javascript public class Hashtable<K,V> extends Dictionary<K,V> implements Map<K,V>, Cloneable, java.io.Serializable { ... public synchronized boolean contains(Object value) { if (value == null) { throw new NullPointerException(); }

}


A Hashtable osztály contains() metódusa, amely ellenőrzi, hogy van-e azonos érték, ugyanúgy használja a synchronized kulcsszót, mint a Vector osztályban.


Collections.synchronizedXXX

Nézzük meg a SynchronizedList osztályt, amelyet a Collections.synchronizedList() metódussal hozunk létre.


```javascript static class SynchronizedList extends SynchronizedCollection implements List {

}


A SynchronizedList osztály metódusainak vizsgálata során azt láthatjuk, hogy mindegyikben a synchronized kulcsszó szerepel. A szinkronizálást azonban a mutex objektum segítségével egy synchronized blokkal valósítják meg. Minden metódus ugyanazt a mutex objektumot osztja meg, így ha egy szál belép a synchronized blokkba, akkor minden más metódus synchronized blokkja zárva lesz.


A szinkronizált gyűjtemények problémái

Bár multithreading környezetben szükség lehet a szinkronizált gyűjtemények használatára, más szinkronizálási módszerek használata ajánlott. Ennek két fő oka van.


Több művelet összevonása egyetlen műveletté

A szinkronizált gyűjtemények garantálják a szinkronitást multithreading környezetben. Ha azonban több műveletet kell összevonni egyetlen műveletté, akkor problémák merülhetnek fel. Előfordulhat, hogy a szinkronizált gyűjtemények használata ilyenkor nem biztosít helyes működést.


```javascript final List list = Collections.synchronizedList(new ArrayList()); final int nThreads = 2; ExecutorService es = Executors.newFixedThreadPool(nThreads);

for (int i = 0; i < nThreads; i++) { es.execute(new Runnable() {

}


Ha a fenti kódot futtatjuk, akkor ha a Thread A végrehajtja a remove(0) műveletet, és ugyanekkor a Thread B végrehajtja a clear() műveletet, akkor hiba lép fel. Ezért a műveleteket a következőképpen kell szinkronizálni:


```javascript synchronized (list) { list.clear(); list.add("888"); list.remove(0); }


Teljesítménycsökkenés

Ha minden olyan metódust, amely megosztott objektummal dolgozik, synchronized metódussá teszünk, vagy ha a metódusok belsejében azonos synchronized blokkot határozunk meg, akkor az a szál, amelyik megszerzi a zárat, blokkolja az összes többi szálat, amelyek ugyanazt a metódust akarják használni. Ez a jelenség többször megismétlődve teljesítménycsökkenéshez vezethet.


Egyidejű gyűjtemények

A java.util.concurrent csomag egyidejű gyűjteményeket biztosít. Ezek közül néhányat fogunk ebben a cikkben megvizsgálni.


  • CopyOnWriteArrayList
    • A List osztály alosztálya, amely a párhuzamos gyűjteményekben a listaelemek iterálása és lekérdezése közben a legjobb teljesítményt biztosítja.
  • ConcurrentMap
    • Párhuzamos gyűjtemény, amelynek interfésze tartalmaz olyan műveleteket, mint a put-if-absent, replace és conditional remove, amelyek csak akkor adnak hozzá új elemeket, ha az adott kulcs nem létezik.
  • ConcurrentHashMap
    • A ConcurrentMap alosztálya, amely párhuzamos gyűjteményként helyettesíti a HashMap-et.
  • ConcurrentLinkedQueue
    • FIFO típusú Queue, amely párhuzamos gyűjtemény. Ha nincs elem a sorban, akkor azonnal visszatér, és más feladatot végez.
  • LinkedBlockingQueue
    • Hasonló a ConcurrentLinkedQueue-hoz, de ha a sor üres, akkor a sorból való kivétel művelete addig vár, amíg új elem nem kerül hozzáadásra. Ha a sornak mérete van megadva, akkor a sor telítettségétől függően a sorhoz való hozzáadás művelete addig vár, amíg nem szabadul fel hely.
  • ConcurrentSkipListMap, ConcurrentSkipListSet
    • A SortedMap és SortedSet osztályok párhuzamos verziói, amelyek optimalizáltak a jobb teljesítmény érdekében.


A meglévő szinkronizált gyűjtemények párhuzamos gyűjteményekre cserélése jelentős teljesítménynövekedést eredményezhet anélkül, hogy további kockázatok merülnének fel.

Nézzük meg a párhuzamos gyűjteményeket részletesebben, összehasonlítva őket a szinkronizált gyűjteményekkel.


CopyOnWriteArrayList

A szinkronizált ArrayList létrehozásának két módja van:


  • Collections.synchronizedList()
  • CopyOnWriteArrayList


A Collections.synchronizedList() metódust a JDK 1.2 verzióban vezették be. Ez a gyűjtemény minden olvasási és írási műveletet szinkronizál, ami azt jelenti, hogy nincs rugalmassága. Ezt a problémát oldotta meg a CopyOnWriteArrayList.


Olvasási műveletek

A SynchronizedList minden olvasási és írási művelet során lezárja az objektumot. A CopyOnWriteArrayList azonban minden írási műveletkor elkészít egy új ideiglenes tömböt, amely tartalmazza az eredeti tömb elemeinek másolatát. Az írási műveletet ezen az ideiglenes tömbön hajtja végre, majd frissíti az eredeti tömböt. Ennek köszönhetően az olvasási műveletek nem záródnak le, így a SynchronizedList-hez képest jobb teljesítményt nyújtanak.


```javascript public class CopyOnWriteArrayList implements List, RandomAccess, Cloneable, java.io.Serializable {

}


A fenti get() metódus nem tartalmaz synchronized kulcsszót, tehát nem záródik le.


Írási műveletek

A CopyOnWriteArrayList írási műveletek során explicit zárat használ. Ennek eredményeként mindkét gyűjtemény típus esetében lezáródnak ezek a műveletek. A CopyOnWriteArrayList azonban relatíve költséges tömbmásolási műveletet végez, ami teljesítményproblémákat okozhat, ha sok írási műveletet hajtunk végre.


```javascript public class CopyOnWriteArrayList implements List, RandomAccess, Cloneable, java.io.Serializable {

}


A fenti add() metódus egy synchronized blokkal zárja le a tömbmásolási műveletet.


Iterator

A CopyOnWriteArrayList az iterátor kérésének pillanatában létező gyűjteményadatok alapján iterál. Az iterálás során a gyűjteményhez hozzáadott vagy törölt adatokat nem veszik figyelembe, hanem a másolt tömbre vonatkoznak, így nincs probléma a párhuzamos használattal.


CopyOnWriteArraySet

A szinkronizált Set létrehozásának két módja van:


  • Collections.synchronizedSet()
  • CopyOnWriteArraySet


A metódusnevek alapján egyértelmű, hogy a CopyOnWriteArraySet a CopyOnWriteArrayList-hez hasonlóan működik, kivéve az adatstruktúra sajátosságait.


Olvasási műveletek

```javascript public class CopyOnWriteArraySet extends AbstractSet implements java.io.Serializable {

}


A fenti contains() metódus azt mutatja, hogy a CopyOnWriteArraySet belsőleg egy CopyOnWriteArrayList objektumot hoz létre, és a CopyOnWriteArrayList metódusait használja.


```javascript public boolean contains(Object o) { return indexOf(o) >= 0; }

public int indexOf(Object o) { Object[] es = getArray(); return indexOfRange(o, es, 0, es.length); }

}


A CopyOnWriteArrayList contains() metódusának vizsgálata azt mutatja, hogy nem záródik le.


Írási műveletek

```javascript public class CopyOnWriteArraySet extends AbstractSet implements java.io.Serializable {

}


Az add() metódus szintén a CopyOnWriteArrayList metódusát használja.


```javascript public boolean addIfAbsent(E e) { Object[] snapshot = getArray(); return indexOfRange(e, snapshot, 0, snapshot.length) < 0 && addIfAbsent(e, snapshot); }

private boolean addIfAbsent(E e, Object[] snapshot) { synchronized (lock) { Object[] current = getArray(); int len = current.length; if (snapshot != current) { // Optimize for lost race to another addXXX operation int common = Math.min(snapshot.length, len); for (int i = 0; i < common; i++) if (current[i] != snapshot[i] && Objects.equals(e, current[i])) return false; if (indexOfRange(e, current, common, len) >= 0) return false; } Object[] newElements = Arrays.copyOf(current, len + 1); newElements[len] = e; setArray(newElements); return true; } }


Az addIfAbsent() metódus azt mutatja, hogy az írási műveletek során lezáródik a tömbmásolási művelet. Ennek megfelelően a CopyOnWriteArraySet esetében is kerülni kell a sok írási műveletet, akárcsak a CopyOnWriteArrayList esetében.


ConcurrentHashMap

A szinkronizált HashMap létrehozásának két módja van:


  • Collections.synchronizedMap(new HashMap<>())
  • ConcurrentHashMap


A ConcurrentHashMap ugyanúgy használja a Hash-alapú megközelítést, mint a HashMap. A synchronizedMap-hez képest hatékonyabb módszert biztosít a szinkronitás garantálására.


A Java 8 előtti verziókban a ReentrantLock-ot öröklő Segment-eket használták a szinkronitás biztosítására. A szinkronizálást területenként végezték el.


A Java 8 és a későbbi verziókban minden tábla-vödör függetlenül záródik le. Ha üres vödörbe kerül elem beszúrásra, akkor a zár helyett a CAS algoritmust használják. Ha más módosítás történik, akkor a vödör első elemére kerül zár (synchronized block), így minimalizálják a szálversengést, és biztosítják a szinkronitást.


Vizsgáljuk meg a ConcurrentHashMap-hez való elem hozzáadására szolgáló putVal() metódus kódját, hogy lássuk, hogyan biztosítják a szinkronitást. A következő kód a Java 11 verziójára vonatkozik.


A putVal() metódus két fő esetre osztható (a teljes elágazás négy részre):


  • Üres tábla-vödörbe való beszúrás
  • Már létező elemek a tábla-vödörben


```javascript final V putVal(K key, V value, boolean onlyIfAbsent) { if (key null || value null) throw new NullPointerException(); int hash = spread(key.hashCode()); int binCount = 0; for (Node<K,V>[] tab = table;;) { Node<K,V> f; int n, i, fh; K fk; V fv; if (tab null || (n = tab.length) 0) tab = initTable(); // (1) else if ((f = tabAt(tab, i = (n - 1) & hash)) null) { // (2) if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value))) break; } else if ((fh = f.hash) MOVED) tab = helpTransfer(tab, f); else if (onlyIfAbsent // check first node without acquiring lock && fh hash && ((fk = f.key) key || (fk != null && key.equals(fk))) && (fv = f.val) != null) return fv; // (3) else { V oldVal = null; synchronized (f) { if (tabAt(tab, i) f) { if (fh >= 0) { binCount = 1; for (Node<K,V> e = f;; ++binCount) { K ek; // (4) if (e.hash hash && ((ek = e.key) key || (ek != null && key.equals(ek)))) { oldVal = e.val; if (!onlyIfAbsent) e.val = value; break; } Node<K,V> pred = e; // (5) if ((e = e.next) null) { pred.next = new Node<K,V>(hash, key, value); break; } } } // (6) else if (f instanceof TreeBin) { Node<K,V> p; binCount = 2; if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key, value)) != null) { oldVal = p.val; if (!onlyIfAbsent) p.val = value; } } else if (f instanceof ReservationNode) throw new IllegalStateException("Recursive update"); } } ... } } ... }


Üres tábla-vödörbe való beszúrás

(1) Az új elem beszúrásához ellenőrzi, hogy a tábla-vödör üres-e (tabAt()).


```javascript static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) { return (Node<K,V>)U.getObjectAcquire(tab, ((long)i << ASHIFT) + ABASE); }


(2) A vödörben lévő volatile változóhoz fér hozzá, összehasonlítja a meglévő értéket (null) az új értékkel. Ha azonosak, akkor az új elemet menti. Ha nem azonosak, akkor a for ciklus újraindul. Ez a CAS (Compare And Swap) algoritmus.


```javascript static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i, Node<K,V> c, Node<K,V> v) { return U.compareAndSetObject(tab, ((long)i << ASHIFT) + ABASE, c, v); }


A CAS algoritmus biztosítja az atomikusságot és a láthatóságot, így a szinkronitás is garantált.


Már létező elemek a tábla-vödörben

(3) Ha már létezik elem a vödörben, akkor a synchronized blokk használatával csak egyetlen szálnak engedélyezik a hozzáférést. Mivel a nem üres Node<K, V> típusú vödörre kerül a zár, ezért a vödörhöz hozzáférni próbáló szálak blokkolva lesznek.

(4) Az új elemet a meglévővel cseréli.

(5) Ha ütközés történt, akkor a láncolathoz adja hozzá az új elemet.

(6) Ha ütközés történt, akkor a fához adja hozzá az új elemet.


Hivatkozások


Várható interjúkérdések és válaszok

Milyen problémák merülnek fel a Vector, HashTable és Collections.SynchronziedXXX osztályok használatakor?

A Vector, HashTable és SynchronziedXxx osztályok a synchronized metódust vagy blokkot használják, és ugyanazt a zárat osztják meg. Ez azt jelenti, hogy ha egy szál megszerzi a zárat a gyűjteményen, akkor az összes többi szál blokkolva lesz, és nem tudja használni a gyűjtemény metódusait. Ez teljesítménycsökkenéshez vezethet az alkalmazásban.


Mi a különbség a SynchronizedList és a CopyOnArrayList között?

A SynchronizedList minden olvasási és írási művelet során lezárja az objektumot. A CopyOnArrayList viszont írási művelet során lezárja a blokkot, majd másolatot készít az eredeti tömbről egy új ideiglenes tömbbe. Az írási műveletet ezen az ideiglenes tömbön hajtja végre, majd frissíti az eredeti tömböt. Így az olvasási műveletek nem záródnak le, ami a SynchronizedList-hez képest jobb olvasási teljesítményt eredményez. A CopyOnWriteArrayList írási műveletei viszont lassabbak, mivel tömbmásolási műveletet végeznek.

Összefoglalva, a CopyOnWriteArrayList hatékonyabb, ha több olvasási művelet van, mint írási művelet.


Mi a különbség a SynchronziedMap és a ConcurrentHashMap között?

A SynchronziedMap minden olvasási és írási művelet során lezárja az objektumot. A ConcurrentHashMap viszont minden tábla-vödörre külön zárat alkalmaz. Ha egy üres vödörbe kerül elem beszúrásra, akkor a zár helyett a CAS algoritmust használják. A többi módosítás során csak az érintett vödör záródik le, így minimalizálják a szálversengést, és biztosítják a szinkronitást.

Hozzászólások0