Ez egy AI által fordított bejegyzés.
[Java] Szinkronizált gyűjtemény vs. egyidejű gyűjtemény
- Írás nyelve: Koreai
- •
-
Referencia ország: Minden ország
- •
- Informatika
0000-00-00 00:00:00
Válasszon nyelvet
A durumis AI által összefoglalt szöveg
- A szinkronizált gyűjtemények biztonságosak többszálas környezetben, de nem célszerű használni őket, ha több műveletet egyetlen műveletként kell végrehajtani, vagy ha a teljesítmény csökken. Ezért a párhuzamos gyűjtemények használata ajánlott.
- A párhuzamos gyűjtemények hatékonyabban biztosítják az egyidejűséget, mint a szinkronizált gyűjtemények, és több fajtája is létezik, például a CopyOnWriteArrayList és a ConcurrentHashMap.
- A CopyOnWriteArrayList különösen akkor előnyös, ha az olvasási műveletek során nincs szükség zárra, így gyorsabb, mint a SynchronizedList, de a írási műveletek során tömbmásolást végez, ami teljesítménycsökkenéshez vezethet.
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
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
public class Hashtable extends Dictionary
implements Map, Cloneable, java.io.Serializable {
...
public synchronized boolean contains(Object value) {
if (value == null) {
throw new NullPointerException();
}
Entry tab[] = table;
for (int i = tab.length ; i-- > 0 ;) {
for (Entry e = tab[i] ; e != null ; e = e.next) {
if (e.value.equals(value)) {
return true;
}
}
}
return false;
}
... 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.
static class SynchronizedList extends SynchronizedCollection
implements List {
final Object mutex;
...
public E get(int index) {
synchronized (mutex) {return list.get(index);}
}
public E set(int index, E element) {
synchronized (mutex) {return list.set(index, element);}
}
public void add(int index, E element) {
synchronized (mutex) {list.add(index, element);}
}
public E remove(int index) {
synchronized (mutex) {return list.remove(index);}
}
... 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.
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() {
public void run() {
while(true) {
try {
list.clear();
list.add("888");
list.remove(0);
} catch(IndexOutOfBoundsException e) {
e.printStackTrace();
}
}
}
}); 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:
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.
public class CopyOnWriteArrayList implements List, RandomAccess, Cloneable, java.io.Serializable {
final transient Object lock = new Object();
private transient volatile Object[] array;
...
public E get(int index) {
return elementAt(getArray(), index);
}
... 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.
public class CopyOnWriteArrayList implements List, RandomAccess, Cloneable, java.io.Serializable {
final transient Object lock = new Object();
private transient volatile Object[] array;
public void add(int index, E element) {
synchronized (lock) {
...
int numMoved = len - index;
if (numMoved == 0)
newElements = Arrays.copyOf(es, len + 1);
else {
newElements = new Object[len + 1];
System.arraycopy(es, 0, newElements, 0, index);
System.arraycopy(es, index, newElements, index + 1,
numMoved);
}
...
}
} 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
public class CopyOnWriteArraySet extends AbstractSet implements java.io.Serializable {
private final CopyOnWriteArrayList al;
public boolean contains(Object o) {
return al.contains(o);
} 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.
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
public int indexOf(Object o) {
Object[] es = getArray();
return indexOfRange(o, es, 0, es.length);
}
private static int indexOfRange(Object o, Object[] es, int from, int to) {
if (o == null) {
for (int i = from; i < to; i++)
if (es[i] == null)
return i;
} else {
for (int i = from; i < to; i++)
if (o.equals(es[i]))
return i;
}
return -1;A CopyOnWriteArrayList contains() metódusának vizsgálata azt mutatja, hogy nem záródik le.
Írási műveletek
public class CopyOnWriteArraySet extends AbstractSet implements java.io.Serializable {
private final CopyOnWriteArrayList al;
public boolean add(E e) {
return al.addIfAbsent(e);
} Az add() metódus szintén a CopyOnWriteArrayList metódusát használja.
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
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[] tab = table;;) {
Node 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(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 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 pred = e;
// (5)
if ((e = e.next) == null) {
pred.next = new Node(hash, key, value);
break;
}
}
}
// (6)
else if (f instanceof TreeBin) {
Node p;
binCount = 2;
if ((p = ((TreeBin)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()).
static final Node tabAt(Node[] tab, int i) {
return (Node)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.
static final boolean casTabAt(Node[] tab, int i, Node c, Node 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
(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.
