제이온

[Java] คอลเล็กชันที่ซิงโครไนซ์ เทียบกับ คอลเล็กชันแบบพร้อมใช้งาน

สร้าง: 2024-04-25

สร้าง: 2024-04-25 22:31

คอลเลกชันแบบซิงโครไนซ์

คอลเลกชันแบบซิงโครไนซ์มีคลาสหลัก ๆ ดังต่อไปนี้


  • เวกเตอร์
  • แฮชเทเบิล
  • Collections.synchronizedXXX


คลาสทั้งหมดนี้ใช้คำหลัก synchronized สำหรับเมธอดที่ประกาศเป็น public เพื่อควบคุมให้มีเพียงเธรดเดียวเท่านั้นที่สามารถใช้ค่าภายในได้ ทำให้มั่นใจได้ถึงความพร้อมกัน


เวกเตอร์

```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; } ... }

ลองดูเมธอด add() ที่ใช้สำหรับเพิ่มองค์ประกอบในคลาส Vector จะเห็นคำหลัก synchronized ซึ่งหมายความว่าภายใน Vector จะมีการรับรองความพร้อมกันในขณะที่ดำเนินการแทรกองค์ประกอบ

แฮชเทเบิล

```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(); }

}


ถ้าลองดูเมธอด contains() ของคลาส Hashtable ซึ่งใช้เพื่อตรวจสอบว่ามีค่าเดียวกันอยู่หรือไม่ จะเห็นว่ามีการใช้คำหลัก synchronized เช่นเดียวกับคลาส Vector


Collections.synchronizedXXX

ลองดูคลาส SynchronizedList ที่สร้างขึ้นโดยใช้เมธอด Collections.synchronizedList()


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

}


ถ้าลองดูเมธอดของคลาส SynchronizedList จะเห็นว่ามีการใช้คำหลัก synchronized ทั้งหมด แต่ใช้บล็อก synchronized เพื่อรับรองความพร้อมกันผ่านมิวเท็กซ์ เมธอดทั้งหมดจะใช้ร่วมกันวัตถุมิวเท็กซ์ ดังนั้นเมื่อเธรดหนึ่งเข้าไปในบล็อก synchronized บล็อก synchronized ของเมธอดอื่น ๆ จะถูกบล็อกทั้งหมด


ปัญหาของคอลเลกชันแบบซิงโครไนซ์

แม้ว่าในสภาพแวดล้อมแบบมัลติเธรด จะต้องใช้คอลเลกชันแบบซิงโครไนซ์ แต่โดยทั่วไปแล้ว ควรใช้วิธีการซิงโครไนซ์อื่น ๆ แทน เหตุผลหลักมีสองประการ


การรวมหลายการดำเนินการเพื่อใช้เป็นการดำเนินการเดียว

คลาสคอลเลกชันแบบซิงโครไนซ์จะรับรองความพร้อมกันในสภาพแวดล้อมแบบมัลติเธรด แต่ถ้าต้องรวมหลายการดำเนินการเพื่อใช้เป็นการดำเนินการเดียว อาจเกิดปัญหาขึ้น แม้จะใช้คอลเลกชันแบบซิงโครไนซ์นี้ก็อาจทำงานไม่ถูกต้อง


```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() {

}


ถ้าเรียกใช้โค้ดนี้ เมื่อ Thread A ทำ remove(0) และ Thread B ทำ clear() ในเวลาเดียวกัน จะเกิดข้อผิดพลาด ดังนั้นจึงต้อง รวมไว้ในบล็อก synchronized ดังนี้


```javascript 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


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

}


ด้านบนคือเมธอด get() ซึ่งไม่มี synchronized ดังนั้นจึงไม่ถูกบล็อก


การดำเนินการเขียน

CopyOnWriteArrayList ใช้ล็อกแบบชัดเจนในขณะที่ดำเนินการเขียน ในท้ายที่สุดทั้งสองประเภทของคอลเลกชันจะถูกบล็อก ในขณะที่ดำเนินการนี้ ในกรณีนี้ CopyOnWriteArrayList จะใช้การคัดลอกอาร์เรย์ ซึ่งเป็นการดำเนินการที่มีค่าใช้จ่ายสูง ดังนั้นอาจเกิดปัญหาประสิทธิภาพหากมีการดำเนินการเขียนจำนวนมาก


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

}


ด้านบนคือเมธอด add() ซึ่งใช้บล็อก synchronized เพื่อบล็อกและดำเนินการคัดลอกอาร์เรย์


ตัววนซ้ำ

ใน CopyOnWriteArrayList ขณะที่ดึงตัววนซ้ำออก จะใช้ข้อมูลคอลเลกชันในขณะนั้นเป็นเกณฑ์ในการวนซ้ำ และเนื่องจากข้อมูลที่เพิ่มหรือ ลบออกจากคอลเลกชันในขณะที่วนซ้ำ จะถูกนำไปใช้กับสำเนาที่ไม่ได้เกี่ยวข้องกับลูป ดังนั้นจึงไม่มีปัญหาในการใช้งานพร้อมกัน


CopyOnWriteArraySet

มีสองวิธีในการสร้างเซ็ตแบบซิงโครไนซ์ ดังนี้


  • Collections.synchronizedSet()
  • CopyOnWriteArraySet


จากชื่อเมธอด จะเห็นได้ว่าวิธีการทำงานนั้นเกือบจะเหมือนกับ CopyOnWriteArrayList ยกเว้นลักษณะเฉพาะของโครงสร้างข้อมูล


การดำเนินการอ่าน

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

}


ด้านบนคือเมธอด contains() ซึ่งจะเห็นได้ว่า CopyOnWriteArraySet จะกำหนด CopyOnWriteArrayList ภายใน และใช้เมธอดของ CopyOnWriteArrayList


```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); }

}


ถ้าลองดูเมธอด contains() ของ CopyOnWriteArrayList จะเห็นว่าไม่มีการล็อก


การดำเนินการเขียน

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

}


เมธอด add() ก็ใช้เมธอดของ CopyOnWriteArrayList เช่นกัน


```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; } }


ถ้าลองดูเมธอด 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 ส่วน) ดังนี้


  • กรณีแทรกโหนดลงในถังแฮชที่ว่าง
  • กรณีที่มีโหนดอยู่แล้วในถังแฮช


```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"); } } ... } } ... }


กรณีแทรกโหนดลงในถังแฮชที่ว่าง

(1) เพื่อแทรกโหนดใหม่ จะตรวจสอบว่าค่าของถังนั้น (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) เข้าถึงตัวแปร volatile ที่เก็บอยู่ในโหนด และเปรียบเทียบกับค่าเดิม (null) ถ้าเหมือนกัน จะบันทึกโหนดใหม่ ถ้าไม่เหมือนกัน จะวนกลับไปที่ for loop วิธีนี้คือแอลกอริทึม CAS


```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); }


การใช้แอลกอริทึม CAS จะช่วยแก้ปัญหาการเป็นอะตอมและการมองเห็นได้ เพื่อรับรองความพร้อมกัน


กรณีที่มีโหนดอยู่แล้วในถังแฮช

(3) หากมีโหนดอยู่แล้ว จะใช้ synchronized block เพื่อควบคุมให้มีเพียงเธรดเดียวเท่านั้นที่สามารถเข้าถึงได้ ในกรณีนี้ จะล็อกถังแฮชที่ไม่ว่างซึ่งมี Node<K, V> ดังนั้นเธรดที่เข้าถึงถังเดียวกันจะอยู่ในสถานะที่ถูกบล็อก

(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) โดยใช้โหนดแรกของแต่ละถังเป็นเกณฑ์ เพื่อลดการแย่งชิงเธรด และรับรองความพร้อมกัน

ความคิดเห็น0

[สำหรับผู้ไม่ใช่ผู้เชี่ยวชาญ ด้านการพัฒนาซอฟต์แวร์ เพื่อความอยู่รอด] 14. สรุปเนื้อหาสัมภาษณ์ทางเทคนิคที่ผู้พัฒนาซอฟต์แวร์มือใหม่ถามบ่อยสรุปคำถามทางเทคนิคที่มักถามในการสัมภาษณ์งานผู้พัฒนาซอฟต์แวร์มือใหม่ (พื้นที่หน่วยความจำ โครงสร้างข้อมูล ฐานข้อมูล ฯลฯ) หวังว่าจะเป็นประโยชน์ในการเตรียมตัวสัมภาษณ์งานด้านการพัฒนา
투잡뛰는 개발 노동자
투잡뛰는 개발 노동자
투잡뛰는 개발 노동자
투잡뛰는 개발 노동자

April 3, 2024

การสร้างแบบจำลองข้อมูลเชิงกายภาพการสร้างแบบจำลองข้อมูลเชิงกายภาพคือการนำแบบจำลองเชิงตรรกะมาใช้จริงในรูปแบบของตาราง โดยคำนึงถึงประสิทธิภาพการใช้พื้นที่จัดเก็บและการปรับแต่งประสิทธิภาพ สามารถปรับปรุงประสิทธิภาพโดยใช้ slow query, index และ cache
제이의 블로그
제이의 블로그
제이의 블로그
제이의 블로그

April 9, 2024

สัญญาบนพื้นฐานบล็อกเชนเนื้อหาครอบคลุมเกี่ยวกับแนวคิด สาระสำคัญ กระบวนการใช้งาน ความปลอดภัย และประเด็นทางกฎหมาย ตลอดจนอนาคตของสัญญาอัจฉริยะบนพื้นฐานบล็อกเชน พร้อมยกตัวอย่างการใช้งานในหลากหลายสาขา เช่น การเงิน อสังหาริมทรัพย์ และอื่นๆ รวมถึงการนำเสนอข้อจำกัดทางเทคนิคและแนวทางแ
Cherry Bee
Cherry Bee
Cherry Bee
Cherry Bee

March 23, 2025

ไกด์ครบเครื่อง เกมไพ่ The Witcher: Gwentบทความสรุปคำศัพท์และประเภทของไพ่ในเกมไพ่ The Witcher: Gwent รวมถึงความสามารถและสถานะต่างๆ ช่วยให้เข้าใจคำศัพท์ในเกม เช่น สนามรบ มือ ไพ่สำรับ รวมถึงประเภทของไพ่ หน่วยรบ คาถา กับดัก เป็นต้น
길리
길리
길리
길리

April 7, 2024

การสร้างแบบจำลองข้อมูลเชิงตรรกะบทความนี้จะอธิบายกระบวนการสร้างแบบจำลองข้อมูลเชิงตรรกะ ซึ่งเป็นการแปลงแบบจำลองข้อมูลเชิงแนวคิดให้เป็นแบบจำลองฐานข้อมูลเชิงสัมพันธ์ ครอบคลุมการจัดการความสัมพันธ์แบบ 1:1, 1:N, N:M และการทำให้เป็นปกติ (1NF, 2NF, 3NF)
제이의 블로그
제이의 블로그
제이의 블로그
제이의 블로그

April 9, 2024

2024-11-18 สิ่งที่สนใจอย่างหลากหลายในชีวิต : ฉันใช้เวลาว่างทำอะไรบ้าง?บทความบล็อกที่เขียนเมื่อวันที่ 18 พฤศจิกายน 2024 บทความนี้กล่าวถึงงานอดิเรก การลงทุน การเรียนรู้ และกิจวัตรประจำวันต่างๆ ของผู้เขียน รวมถึงความกังวลเกี่ยวกับการเพิ่มประสิทธิภาพการทำงานผ่านระบบอัตโนมัติ
Charles Lee
Charles Lee
Charles Lee
Charles Lee

November 19, 2024