นี่คือโพสต์ที่แปลด้วย AI
[Java] Synchronized Collection vs Concurrent Collection
- ภาษาที่เขียน: ภาษาเกาหลี
- •
-
ประเทศอ้างอิง: ทุกประเทศ
- •
- เทคโนโลยีสารสนเทศ
0000-00-00 00:00:00
เลือกภาษา
สรุปโดย AI ของ durumis
- คอลเลกชันแบบซิงโครไนซ์ เช่น Vector, Hashtable, Collections.synchronizedXXX ฯลฯ ใช้คีย์เวิร์ด synchronized ภายใน เพื่อรับประกันความพร้อมเพรียง แต่การรวมการดำเนินการหลายอย่างหรือปัญหาประสิทธิภาพอาจเกิดขึ้นได้
- คอลเลกชันแบบขนานที่ให้บริการโดยแพ็คเกจ java.util.concurrent นำเสนอคลาสต่างๆ เช่น CopyOnWriteArrayList, ConcurrentMap, ConcurrentHashMap ฯลฯ และมีประสิทธิภาพสูงกว่าคอลเลกชันแบบซิงโครไนซ์
- คอลเลกชันแบบขนาน เช่น CopyOnWriteArrayList, ConcurrentHashMap ฯลฯ มีประสิทธิภาพการอ่านที่สูงกว่าคอลเลกชันแบบซิงโครไนซ์และ การใช้งานสำหรับการเขียนงานที่มีน้อยจะได้ผลดี
คอลเลกชันแบบซิงโครไนซ์
คอลเลกชันแบบซิงโครไนซ์มีคลาสหลัก ๆ ดังต่อไปนี้
- เวกเตอร์
- แฮชเทเบิล
- Collections.synchronizedXXX
คลาสทั้งหมดนี้ใช้คำหลัก synchronized สำหรับเมธอดที่ประกาศเป็น public เพื่อควบคุมให้มีเพียงเธรดเดียวเท่านั้นที่สามารถใช้ค่าภายในได้ ทำให้มั่นใจได้ถึงความพร้อมกัน
เวกเตอร์
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;
}
... ลองดูเมธอด add() ที่ใช้สำหรับเพิ่มองค์ประกอบในคลาส Vector จะเห็นคำหลัก synchronized ซึ่งหมายความว่าภายใน Vector จะมีการรับรองความพร้อมกันในขณะที่ดำเนินการแทรกองค์ประกอบ
แฮชเทเบิล
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;
}
... ถ้าลองดูเมธอด contains() ของคลาส Hashtable ซึ่งใช้เพื่อตรวจสอบว่ามีค่าเดียวกันอยู่หรือไม่ จะเห็นว่ามีการใช้คำหลัก synchronized เช่นเดียวกับคลาส Vector
Collections.synchronizedXXX
ลองดูคลาส SynchronizedList ที่สร้างขึ้นโดยใช้เมธอด Collections.synchronizedList()
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);}
}
... ถ้าลองดูเมธอดของคลาส SynchronizedList จะเห็นว่ามีการใช้คำหลัก synchronized ทั้งหมด แต่ใช้บล็อก synchronized เพื่อรับรองความพร้อมกันผ่านมิวเท็กซ์ เมธอดทั้งหมดจะใช้ร่วมกันวัตถุมิวเท็กซ์ ดังนั้นเมื่อเธรดหนึ่งเข้าไปในบล็อก synchronized บล็อก synchronized ของเมธอดอื่น ๆ จะถูกบล็อกทั้งหมด
ปัญหาของคอลเลกชันแบบซิงโครไนซ์
แม้ว่าในสภาพแวดล้อมแบบมัลติเธรด จะต้องใช้คอลเลกชันแบบซิงโครไนซ์ แต่โดยทั่วไปแล้ว ควรใช้วิธีการซิงโครไนซ์อื่น ๆ แทน เหตุผลหลักมีสองประการ
การรวมหลายการดำเนินการเพื่อใช้เป็นการดำเนินการเดียว
คลาสคอลเลกชันแบบซิงโครไนซ์จะรับรองความพร้อมกันในสภาพแวดล้อมแบบมัลติเธรด แต่ถ้าต้องรวมหลายการดำเนินการเพื่อใช้เป็นการดำเนินการเดียว อาจเกิดปัญหาขึ้น แม้จะใช้คอลเลกชันแบบซิงโครไนซ์นี้ก็อาจทำงานไม่ถูกต้อง
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();
}
}
}
}); ถ้าเรียกใช้โค้ดนี้ เมื่อ Thread A ทำ remove(0) และ Thread B ทำ clear() ในเวลาเดียวกัน จะเกิดข้อผิดพลาด ดังนั้นจึงต้อง รวมไว้ในบล็อก synchronized ดังนี้
synchronized (list) {
list.clear();
list.add("888");
list.remove(0);ประสิทธิภาพลดลง
หากแปลงเมธอดทั้งหมดที่ต้องการใช้วัตถุที่แชร์ให้เป็นเมธอด synchronized หรือกำหนดบล็อก synchronized เดียวกันภายในเมธอด เมื่อเธรดหนึ่งได้รับ lock เธรดอื่น ๆ จะไม่สามารถใช้เมธอด synchronized ทั้งหมดได้และจะอยู่ในสถานะที่ถูกบล็อก เหตุการณ์ที่เกิดขึ้นซ้ำ ๆ แบบนี้จะนำไปสู่ประสิทธิภาพที่ลดลง
คอลเลกชันแบบพร้อมกัน
java.util.concurrent แพคเกจนี้มีคอลเลกชันแบบขนานหลายประเภท ซึ่งในบทความนี้จะกล่าวถึงเพียงบางส่วนเท่านั้น
- CopyOnWriteArrayList
- เป็นคลาสย่อยของคลาส List ซึ่งเป็นคอลเลกชันแบบขนานที่ให้ความสำคัญกับประสิทธิภาพของการดำเนินการค้นหา โดยการวนซ้ำผ่านรายการวัตถุ
- ConcurrentMap
- เป็นคอลเลกชันแบบขนาน โดยการดูที่อินเตอร์เฟส จะพบว่ามีการกำหนดการดำเนินการ put-if-absent, replace, conditional remove ซึ่งจะเพิ่มเฉพาะในกรณีที่ไม่มีรายการอยู่แล้วเท่านั้น
- ConcurrentHashMap
- เป็นคลาสย่อยของ ConcurrentMap ซึ่งเป็นคอลเลกชันแบบขนานที่แทนที่ HashMap และมีการรับรองความพร้อมกัน
- ConcurrentLinkedQueue
- เป็นคิวแบบ FIFO ซึ่งเป็นคอลเลกชันแบบขนานที่รับรองความพร้อมกัน หากไม่มีองค์ประกอบในคิว จะคืนค่าทันที และไปดำเนินการอื่น
- LinkedBlockingQueue
- คล้ายกับ ConcurrentLinkedQueue แต่ถ้าคิวว่าง การดำเนินการดึงองค์ประกอบออกจากคิวจะต้องรอจนกว่าจะมีองค์ประกอบใหม่เพิ่มเข้ามา ในทางกลับกัน หากคิวมีขนาดที่กำหนดไว้ และคิวเต็มจนถึงขนาดที่กำหนดไว้ การดำเนินการเพิ่มองค์ประกอบใหม่ลงในคิวจะต้องรอจนกว่าจะมี ช่องว่างในคิว
- ConcurrentSkipListMap, ConcurrentSkipListSet
- เป็นรูปแบบที่พัฒนาขึ้นเพื่อเพิ่มความพร้อมกันของ SortedMap และ SortedSet ตามลำดับ
เพียงแค่เปลี่ยนคลาสคอลเลกชันแบบซิงโครไนซ์ที่เคยใช้ไปเป็นคอลเลกชันแบบขนาน ก็สามารถเพิ่มประสิทธิภาพโดยรวมได้อย่างมากโดยไม่ต้องเสี่ยง ใด ๆ
ลองดูรายละเอียดของคอลเลกชันแบบขนานโดยเปรียบเทียบกับคอลเลกชันแบบซิงโครไนซ์
CopyOnWriteArrayList
มีสองวิธีในการสร้าง ArrayList แบบซิงโครไนซ์ ดังนี้
- Collections.synchronizedList()
- CopyOnWriteArrayList
Collections.synchronizedList() เพิ่มใน JDK เวอร์ชัน 1.2 คอลเลกชันนี้จะซิงโครไนซ์สำหรับการดำเนินการอ่านและเขียนทั้งหมด ดังนั้นจึงอาจกล่าวได้ว่าเป็นการออกแบบที่ไม่ยืดหยุ่น ดังนั้นจึงมีการนำ CopyOnWriteArrayList มาใช้เพื่อแก้ไขปัญหานี้
การดำเนินการอ่าน
SynchronizedList จะล็อกอินสแตนซ์ในขณะที่ดำเนินการอ่านและเขียน แต่ CopyOnWriteArrayList จะสร้างอาร์เรย์ชั่วคราวใหม่ โดยการคัดลอกองค์ประกอบที่มีอยู่ในอาร์เรย์ต้นฉบับทุกครั้งที่มีการดำเนินการเขียน จากนั้นจึงดำเนินการเขียนไปยังอาร์เรย์ชั่วคราวนี้ และอัปเดตอาร์เรย์ต้นฉบับ ด้วยเหตุนี้ การดำเนินการอ่านจึงไม่ถูกบล็อก ทำให้ CopyOnWriteArrayList มีประสิทธิภาพดีกว่า SynchronizedList
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);
}
... ด้านบนคือเมธอด get() ซึ่งไม่มี synchronized ดังนั้นจึงไม่ถูกบล็อก
การดำเนินการเขียน
CopyOnWriteArrayList ใช้ล็อกแบบชัดเจนในขณะที่ดำเนินการเขียน ในท้ายที่สุดทั้งสองประเภทของคอลเลกชันจะถูกบล็อก ในขณะที่ดำเนินการนี้ ในกรณีนี้ CopyOnWriteArrayList จะใช้การคัดลอกอาร์เรย์ ซึ่งเป็นการดำเนินการที่มีค่าใช้จ่ายสูง ดังนั้นอาจเกิดปัญหาประสิทธิภาพหากมีการดำเนินการเขียนจำนวนมาก
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);
}
...
}
} ด้านบนคือเมธอด add() ซึ่งใช้บล็อก synchronized เพื่อบล็อกและดำเนินการคัดลอกอาร์เรย์
ตัววนซ้ำ
ใน CopyOnWriteArrayList ขณะที่ดึงตัววนซ้ำออก จะใช้ข้อมูลคอลเลกชันในขณะนั้นเป็นเกณฑ์ในการวนซ้ำ และเนื่องจากข้อมูลที่เพิ่มหรือ ลบออกจากคอลเลกชันในขณะที่วนซ้ำ จะถูกนำไปใช้กับสำเนาที่ไม่ได้เกี่ยวข้องกับลูป ดังนั้นจึงไม่มีปัญหาในการใช้งานพร้อมกัน
CopyOnWriteArraySet
มีสองวิธีในการสร้างเซ็ตแบบซิงโครไนซ์ ดังนี้
- Collections.synchronizedSet()
- CopyOnWriteArraySet
จากชื่อเมธอด จะเห็นได้ว่าวิธีการทำงานนั้นเกือบจะเหมือนกับ CopyOnWriteArrayList ยกเว้นลักษณะเฉพาะของโครงสร้างข้อมูล
การดำเนินการอ่าน
public class CopyOnWriteArraySet extends AbstractSet implements java.io.Serializable {
private final CopyOnWriteArrayList al;
public boolean contains(Object o) {
return al.contains(o);
} ด้านบนคือเมธอด contains() ซึ่งจะเห็นได้ว่า CopyOnWriteArraySet จะกำหนด CopyOnWriteArrayList ภายใน และใช้เมธอดของ CopyOnWriteArrayList
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;ถ้าลองดูเมธอด contains() ของ CopyOnWriteArrayList จะเห็นว่าไม่มีการล็อก
การดำเนินการเขียน
public class CopyOnWriteArraySet extends AbstractSet implements java.io.Serializable {
private final CopyOnWriteArrayList al;
public boolean add(E e) {
return al.addIfAbsent(e);
} เมธอด add() ก็ใช้เมธอดของ CopyOnWriteArrayList เช่นกัน
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;
}ถ้าลองดูเมธอด addIfAbsent() จะเห็นว่ามีการบล็อกและดำเนินการคัดลอกอาร์เรย์ในขณะที่ดำเนินการเขียน ดังนั้น CopyOnWriteArraySet จึงควรหลีกเลี่ยงการดำเนินการเขียนมาก ๆ เหมือนกับ CopyOnWriteArrayList
ConcurrentHashMap
มีสองวิธีในการสร้าง HashMap แบบซิงโครไนซ์ ดังนี้
- Collections.synchronizedMap(new HashMap<>())
- ConcurrentHashMap
ConcurrentHashMap เป็น Map ที่ใช้แฮชเป็นพื้นฐานเช่นเดียวกับ HashMap ConcurrentHashMap มีประสิทธิภาพมากกว่า synchronizedMap ในการรับรองความพร้อมกัน
ก่อน Java 8 จะใช้ Segment ซึ่งสืบทอดมาจาก ReentrantLock เพื่อแบ่งพื้นที่ และล็อกแต่ละพื้นที่
ตั้งแต่ Java 8 เป็นต้นมา จะใช้การล็อกแต่ละถังของตารางแบบอิสระ หากจะแทรกโหนดในถังว่าง จะใช้แอลกอริทึม CAS แทนการล็อก ส่วนการเปลี่ยนแปลงอื่น ๆ จะได้รับ lock เฉพาะส่วน (synchronized block) โดยใช้โหนดแรกของแต่ละถังเป็นเกณฑ์ เพื่อลดการแย่งชิงเธรดและรับรองความพร้อมกัน
ลองดูโค้ดของเมธอด putVal() ที่ใช้สำหรับแทรกโหนดใหม่ลงใน ConcurrentHashMap เพื่อดูว่ารับรองความพร้อมกันอย่างไร หมายเหตุ โค้ดตัวอย่างนี้ใช้ Java 11 เป็นเกณฑ์
เมธอด putVal() สามารถแบ่งออกเป็นสองกรณี (การแยกแขนง 4 ส่วน) ดังนี้
- กรณีแทรกโหนดลงในถังแฮชที่ว่าง
- กรณีที่มีโหนดอยู่แล้วในถังแฮช
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");
}
}
...
}
}
... กรณีแทรกโหนดลงในถังแฮชที่ว่าง
(1) เพื่อแทรกโหนดใหม่ จะตรวจสอบว่าค่าของถังนั้น (tabAt()) ว่างหรือไม่
static final Node tabAt(Node[] tab, int i) {
return (Node)U.getObjectAcquire(tab, ((long)i << ASHIFT) + ABASE); (2) เข้าถึงตัวแปร volatile ที่เก็บอยู่ในโหนด และเปรียบเทียบกับค่าเดิม (null) ถ้าเหมือนกัน จะบันทึกโหนดใหม่ ถ้าไม่เหมือนกัน จะวนกลับไปที่ for loop วิธีนี้คือแอลกอริทึม CAS
static final boolean casTabAt(Node[] tab, int i, Node c, Node v) {
return U.compareAndSetObject(tab, ((long)i << ASHIFT) + ABASE, c, v); การใช้แอลกอริทึม CAS จะช่วยแก้ปัญหาการเป็นอะตอมและการมองเห็นได้ เพื่อรับรองความพร้อมกัน
กรณีที่มีโหนดอยู่แล้วในถังแฮช
(3) หากมีโหนดอยู่แล้ว จะใช้ synchronized block เพื่อควบคุมให้มีเพียงเธรดเดียวเท่านั้นที่สามารถเข้าถึงได้ ในกรณีนี้ จะล็อกถังแฮชที่ไม่ว่างซึ่งมี Node
(4) แทนที่ด้วยโหนดใหม่
(5) หากเกิดการชนกันของแฮช จะเพิ่มไปยัง Separate Chaing
(6) หากเกิดการชนกันของแฮช จะเพิ่มไปยังต้นไม้
อ้างอิง
คำถามที่คาดหวังในสัมภาษณ์และคำตอบ
ปัญหาของ Vector, HashTable, Collections.SynchronziedXXX คืออะไร
คลาส Vector, HashTable, SynchronziedXxx จะใช้เมธอดหรือบล็อก synchronized และใช้วัตถุล็อกเดียวกัน ดังนั้นเมื่อเธรดหนึ่งได้รับ lock เธรดอื่น ๆ จะไม่สามารถใช้เมธอดทั้งหมดได้ และจะอยู่ในสถานะที่ถูกบล็อก ซึ่งอาจ เป็นสาเหตุของประสิทธิภาพของแอปพลิเคชันที่ลดลง
ความแตกต่างระหว่าง SynchronizedList กับ CopyOnArrayList คืออะไร
SynchronizedList จะล็อกอินสแตนซ์ในขณะที่ดำเนินการอ่านและเขียน แต่ CopyOnArrayList จะล็อกบล็อกนั้น และสร้างอาร์เรย์ชั่วคราวใหม่โดยการคัดลอกองค์ประกอบที่มีอยู่ในอาร์เรย์ต้นฉบับ จากนั้นจึงดำเนินการเขียนไปยังอาร์เรย์ชั่วคราวนี้ และอัปเดตอาร์เรย์ต้นฉบับ ด้วยเหตุนี้ การดำเนินการอ่านจึงไม่ถูกบล็อก ทำให้ CopyOnArrayList มีประสิทธิภาพในการอ่าน ดีกว่า SynchronizedList แต่การดำเนินการเขียนจะใช้การคัดลอกอาร์เรย์ ซึ่งเป็นการดำเนินการที่มีค่าใช้จ่ายสูง ดังนั้นประสิทธิภาพในการเขียนของ CopyOnArrayList จึงต่ำกว่า SynchronizedList
ดังนั้น หากมีการอ่านมากกว่าการแก้ไข CopyOnArrayList จะมีประสิทธิภาพมากกว่า
ความแตกต่างระหว่าง SynchronizedMap กับ ConcurrentHashMap คืออะไร
SynchronziedMap จะล็อกอินสแตนซ์ในขณะที่ดำเนินการอ่านและเขียน แต่ ConcurrentHashMap จะใช้การล็อกแต่ละถัง ของตารางแบบอิสระ หากจะแทรกโหนดในถังว่าง จะใช้แอลกอริทึม CAS แทนการล็อก ส่วนการเปลี่ยนแปลงอื่น ๆ จะได้รับ lock เฉพาะส่วน (synchronized block) โดยใช้โหนดแรกของแต่ละถังเป็นเกณฑ์ เพื่อลดการแย่งชิงเธรด และรับรองความพร้อมกัน
