บทความนี้ส่วนใหญ่ศึกษาเนื้อหาที่เกี่ยวข้องเกี่ยวกับปัญหา ABA และการหลีกเลี่ยงใน Java ดังนี้
ในบทที่ 15 ของหนังสือเล่มนี้ "การปฏิบัติในทางปฏิบัติพร้อมกันของ Java" มีสแต็คพร้อมกันที่ใช้โดยใช้ตัวแปรอะตอมและรหัสมีดังนี้:
โหนดคลาสสาธารณะ {รายการสตริงสุดท้ายสาธารณะ; โหนดสาธารณะถัดไป; โหนดสาธารณะ (รายการสตริง) {this.item = item;}} คลาสสาธารณะ ConcurrentStack {AtomicReference <Node> top = new AtomicReference <node> (); Public Void Push (รายการสตริง) {โหนด newtop = โหนดใหม่ (รายการ); โหนด oldtop; ทำ {oldtop = top.get (newtop.next = oldTop;} pop () {node newtop; node oldtop; ทำ {oldtop = top.get (); ถ้า (oldtop == null) {return null;} newtop = oldtop.next;} ในขณะที่ (!ตัวอย่างนี้จะไม่ทำให้เกิดปัญหา ABA เพราะเหตุใดจึงไม่ฉันจะอธิบายในภายหลัง มาพูดถึงปัญหา ABA ก่อน
ABA คืออะไร?
อ้างถึงหนังสือต้นฉบับ: หากโหนดในอัลกอริทึมสามารถใช้เป็นวงจรได้ปัญหานี้อาจเกิดขึ้นได้เมื่อใช้คำสั่ง "เปรียบเทียบและแลกเปลี่ยน" ในการดำเนินการ CAS จะได้รับการตัดสินว่า "คุณค่าของ V ยังคงเป็นหรือไม่" และถ้าเป็นเช่นนั้นการดำเนินการอัปเดตจะดำเนินต่อไป ในอัลกอริทึมบางอย่างหากค่าของ V เปลี่ยนจาก A เป็น B เป็นครั้งแรกจาก B จาก B เป็น A ดังนั้น CAS จะทำงานได้สำเร็จ
ตัวอย่างของ ABA
บางครั้งผลที่ตามมาจาก ABA นั้นร้ายแรงมาก มาแก้ไขตัวอย่างของสแต็คพร้อมกันเพื่อดูว่าปัญหาใดบ้างที่ ABA จะก่อให้เกิด:
โหนดคลาสสาธารณะ {รายการสตริงสุดท้ายสาธารณะ; โหนดสาธารณะถัดไป; โหนดสาธารณะ (รายการสตริง) {this.item = item;}} คลาสสาธารณะ ConcurrentStack {AtomicReference <Node> top = new AtomicReference <node> (); Public Void Push (โหนดโหนด) {Node oldtop; ทำ {oldtop = top.get (); node.next = oldTop;} oldtop; ทำ {oldtop = top.get (); ถ้า (oldtop == null) {return null;} newtop = oldtop.next; timeunit.seconds.sleep (เวลา);ให้ความสนใจกับการเปลี่ยนแปลงที่นี่โหนดไม่มีการเปลี่ยนแปลงโดยทั่วไป
มุ่งเน้นไปที่การเปลี่ยนแปลงในสแต็กพร้อมกัน
1. วิธีการพุช: ในขั้นต้นการใช้เนื้อหาเพื่อสร้างโหนด แต่ตอนนี้ส่งผ่านในโหนดโดยตรงซึ่งตรงตามข้อกำหนดของ "โหนดในอัลกอริทึมสามารถรีไซเคิลได้"
2. การนอนหลับของวิธีป๊อปซึ่งจำลองการดำเนินการของเธรดเพื่อสังเกตผลลัพธ์
ก่อนอื่นให้กดสองโหนดลงในสแต็ก:
สแต็คสแต็คพร้อมกัน = ใหม่พร้อมกัน (); stack.push (โหนดใหม่ ("a")); stack.push (โหนดใหม่ ("B"));จากนั้นสร้างสองเธรดเพื่อดำเนินการเข้าและออกจากสแต็ก
เธรดก่อนที่จะดำเนินการซ้อน: ปล่อยให้ Nodea ออกจากสแต็ก
stack.pop (3);
ด้วยเหตุผลบางอย่างเธรด A ถูกดำเนินการเป็นเวลานานและใช้เวลา 3 วินาที
Thread B ดำเนินการสแต็กแล้วเข้าสู่สแต็ก: อันดับแรก Nodea และ NodeB จะถูกปล่อยออกมาจากนั้นปล่อยให้ Nodec และ Nodea ป้อน (Nodea อยู่ที่ด้านบนของสแต็ก)
โหนด a = stack.pop (0); stack.pop (0); stack.push (โหนดใหม่ ("D")); stack.push (โหนดใหม่ ("C")); stack.push (a);หมายเหตุ: เธรด B ใช้การรีไซเคิลของโหนด ก่อนอื่นจะปล่อยเนื้อหาทั้งหมดในสแต็กแล้วนำไปใส่ลงในสแต็ก ในที่สุดเนื้อหาที่อยู่ด้านบนของสแต็กคือโหนดที่ปล่อยออกมาก่อน
หลังจากเธรด B ได้ดำเนินการเหล่านี้เธรด A จะดำเนินการ CAS ในเวลานี้ CAS สามารถดำเนินการได้สำเร็จ
ตามแนวคิดดั้งเดิมหลังจากที่เธรด A และ B ดำเนินการเนื้อหาของสแต็กควรเป็น: C และ D, C อยู่ที่ด้านบนของสแต็ก แต่ผลการดำเนินการที่นี่คือไม่มีอะไรในสแต็กซึ่งเป็นปัญหา ABA
วิธีหลีกเลี่ยงปัญหา ABA
AtomicstampedReference และ AtomicMarkableReference มีให้ใน Java เพื่อแก้ปัญหา ABA
AtomicStampedReference สามารถอัพเดทสองค่าอะตอม: การอ้างอิงและหมายเลขเวอร์ชันและแยกความแตกต่างการใช้วัฏจักรของโหนดตามหมายเลขเวอร์ชัน มาดูตัวอย่างของ AtomicstampedReference:
คลาสสาธารณะ ConcurrentStack {AtomicStampedReference <Node> TOP = ใหม่ AtomicStampedReference <Node> (null, 0); โมฆะสาธารณะกด (โหนดโหนด) {โหนด oldtop; int v; ทำ {v = top.getStamp (); โหนด, v, v+1)); //} ในขณะที่ (! top.compareanderdset (oldtop, โหนด, top.getstamp (), top.getstamp ()+1));} โหนดสาธารณะป๊อป (เวลา int) {node newtop; node oldtop; int v; null) {return null;} newtop = oldtop.next; ลอง {timeunit.seconds.sleep (เวลา);} catch (interruptedexception e) {e.printstacktrace ();}} ในขณะที่ (top.CompareAndSet newtop, top.getstamp (), top.getstamp ())); return oldtop;} โมฆะสาธารณะ get () {node node = top.getReference (); ในขณะที่ (node! = null) {system.out.println (node.getItem ()); node = node.getNode ();}}}}หมายเหตุ: คุณไม่สามารถใช้วิธีการแสดงความคิดเห็นไม่เช่นนั้นจะไม่แตกต่างจากการใช้ตัวแปรอะตอม
AtomicMarkableReference สามารถอัปเดตบิตตัวทำเครื่องหมายชนิดบูลีนและประเภทอ้างอิงได้ดูตัวอย่างต่อไปนี้:
AtomicMarkableReference <Node> top = new AtomicMarkableReference <node> (null, true); โมฆะสาธารณะกด (โหนดโหนด) {โหนด oldtop; บูลีน v; ทำ {v = top.ismarked (); oldTop = top.getReference (); node.next = oldtop; โหนด, v ,! v));}สรุป
ข้างต้นเป็นเนื้อหาทั้งหมดของบทความนี้เกี่ยวกับการอภิปรายสั้น ๆ เกี่ยวกับปัญหา ABA และการหลีกเลี่ยงใน Java ฉันหวังว่ามันจะเป็นประโยชน์กับทุกคน เพื่อนที่สนใจสามารถอ้างถึงหัวข้ออื่น ๆ ที่เกี่ยวข้องในเว็บไซต์นี้ต่อไป หากมีข้อบกพร่องใด ๆ โปรดฝากข้อความไว้เพื่อชี้ให้เห็น ขอบคุณเพื่อนที่ให้การสนับสนุนเว็บไซต์นี้!