สแต็กที่ปราศจากการล็อกสามารถนำไปใช้เป็นรายการที่เชื่อมโยงโดยลำพังได้ ดูเหมือนง่ายจนเราต้องคิดว่าจะทำอย่างไรกับโหนดหลังจากที่ถูกเปิดแล้ว กลยุทธ์หนึ่งคือเพียงแค่ย้ายไปยังรายการอิสระ LIFO ต่อสแต็ก จนกระทั่งในที่สุดเธรดทั้งหมดจะเสร็จสิ้นด้วยสแต็ก ซึ่ง ณ จุดที่เธรดเดียวจะทำลายโหนดทั้งหมดในสแต็กและโหนดทั้งหมดในรายการอิสระ Boost.Lockfreeใช้กลยุทธ์นี้ การใช้งาน C11 ของ Chris Wellons ก็เช่นกัน ฉันจะอ้างถึงอย่างหลังเพราะอ่านง่ายกว่าและรายละเอียดก็เหมือนกันเนื่องจากอะตอม C11 นั้นคล้ายกับอะตอม C++11 มาก

ในการใช้งานของ Wellons ซึ่งสามารถพบได้ใน GitHub ที่นี่ออบเจ็กต์ทั้งหมดlstack_nodeไม่ใช่อะตอมมิก โดยเฉพาะอย่างยิ่ง นี่หมายความว่าการเข้าถึงnextสมาชิกของlstack_nodeอ็อบเจ็กต์ทั้งหมดไม่ใช่อะตอม สิ่งที่ฉันไม่เข้าใจคือ: เหตุใดการเข้าถึงดังกล่าวจึงไม่แข่งขันกันเอง

อ่าน สมาชิกได้nextที่lstack.c:30 มันเขียนไว้ที่lstack.c :39 หากสองบรรทัดนี้สามารถดำเนินการพร้อมกันบนlstack_nodeวัตถุเดียวกันได้ แสดงว่าโปรแกรมนั้นมีการแข่งขัน เป็นไปได้ไหม ดูเหมือนว่าเป็นไปได้สำหรับฉัน:

  • เธรดที่ 1 การโทรlstack_popซึ่งpopเรียก มันโหลดค่าของโหนดส่วนหัวลงในตัวแปรorigท้องถิ่น ตอนนี้orig.nodeเป็นตัวชี้ไปยังโหนดที่อยู่บนสุดของสแต็กในตอนนี้ (โปรดทราบว่าจนถึงจุดนี้ เฉพาะตัวแปรในเครื่องเท่านั้นที่ได้รับการแก้ไข ดังนั้นจึงเป็นไปไม่ได้ที่เธรดที่ 1 ได้ทำไปแล้วเพื่อทำให้ CAS ล้มเหลวในเธรดอื่น) ในขณะเดียวกัน...
  • กระทู้ที่ 2 โทรlstack_pop. popสำเร็จและส่งคืนnodeตัวชี้ไปยังโหนดที่เพิ่งถูกตัดออกจากสแต็ก นี่เป็นโหนดเดียวกับที่orig.nodeชี้ไปที่เธรด 1 จากนั้นจึงเริ่มเรียกpushเพื่อเพิ่มnodeในรายการอิสระ โหนดส่วนหัวอิสระถูกโหลดแบบอะตอม และnode->nextตั้งค่าให้ชี้ไปที่โหนดแรกในรายการอิสระ
  • อ๊ะ. แข่งกับการอ่านorig.node->nextในเธรดที่ 1

การใช้งานของ Wellons อาจผิดหรือเปล่า? ฉันสงสัยมัน. หากการใช้งานของเขาไม่ถูกต้อง Boost ก็เช่นกันเพราะวิธีเดียวที่จะแก้ไข (สิ่งที่ดูเหมือนว่าฉันจะเป็น) สภาพการแข่งขันคือการสร้างnextอะตอม แต่ฉันไม่คิดว่าการใช้งาน Boost อาจผิดในลักษณะพื้นฐานโดยที่ไม่มีใครสังเกตเห็นและแก้ไขในตอนนี้ ดังนั้นฉันต้องทำผิดในการให้เหตุผลของฉัน

ไม่พบคำตอบ