การประสานงานและการปลอดจากการแข่งขันข้อมูล

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

Definition

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

Scope

หัวข้อนี้ครอบคลุมกลไกและคุณสมบัติที่ทำให้การเข้าถึงสถานะที่ใช้ร่วมกันพร้อมกันเป็นไปอย่างถูกต้อง: การกีดกันร่วมกัน, ล็อก, เซมาฟอร์และมอนิเตอร์, ตัวแปรเงื่อนไข, อัลกอริทึมแบบไร้ล็อกและไร้การรอ, หน่วยความจำธุรกรรม, ความสัมพันธ์แบบ happens-before และการตรวจจับการแข่งขันข้อมูล นอกจากนี้ยังกล่าวถึงภาวะติดตาย (deadlock), อะตอมมิซิตี (atomicity) และระเบียบวินัยที่จำเป็นในการรักษาโปรแกรมให้ปลอดจากการแข่งขันข้อมูล

Core questions

• การกีดกันร่วมกันทำได้อย่างไรและมีอันตรายอะไรบ้าง (ภาวะติดตาย, การอดอยาก)?
• อะไรคือความแตกต่างระหว่างการประสานงานแบบใช้ล็อกกับการประสานงานแบบไร้ล็อก?
• ความสัมพันธ์แบบ happens-before กำหนดการแข่งขันข้อมูลได้อย่างไร?
• จะตรวจจับการแข่งขันข้อมูลโดยอัตโนมัติได้อย่างไร?

Key theories

การกีดกันร่วมกัน

โซลูชันของ Dijkstra สำหรับปัญหาการควบคุมพร้อมกันได้กำหนดให้การกีดกันร่วมกันเป็นข้อกำหนดพื้นฐานของการประสานงาน ซึ่งรับประกันว่าส่วนวิกฤตจะไม่ถูกดำเนินการพร้อมกัน

หน่วยความจำธุรกรรม

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

Happens-before และการตรวจจับการแข่งขันแบบไดนามิก

จากการสร้างบนความสัมพันธ์แบบ happens-before ของ Lamport ตัวตรวจจับ Eraser ได้แสดงให้เห็นถึงวิธีการค้นหาการแข่งขันข้อมูลแบบไดนามิกโดยการตรวจสอบระเบียบวินัยการล็อก ซึ่งเป็นตัวอย่างของการตรวจจับการแข่งขันข้อมูลแบบอัตโนมัติ

Clinical relevance

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

History

โซลูชันการกีดกันร่วมกันของ Dijkstra ในปี 1965 และเซมาฟอร์ของเขาในเวลาต่อมาได้วางรากฐานของการประสานงาน ตามมาด้วยมอนิเตอร์ของ Hoare และ Brinch Hansen ความสัมพันธ์แบบ happens-before ของ Lamport ในปี 1978 เป็นพื้นฐานของคำจำกัดความของการแข่งขันข้อมูลสมัยใหม่ Herlihy และ Moss ได้นำเสนอหน่วยความจำธุรกรรมในปี 1993 และตัวตรวจจับการแข่งขันข้อมูลแบบไดนามิก เช่น Eraser (1997) และเครื่องมือ happens-before ในเวลาต่อมาได้กลายเป็นมาตรฐานสำหรับการดีบักการทำงานพร้อมกัน

Debates

การใช้ล็อกเทียบกับแนวทางแบบไร้ล็อกและแบบธุรกรรม

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

Key figures

• Edsger Dijkstra
• Leslie Lamport
• Maurice Herlihy
• C. A. R. Hoare
• Stefan Savage

Seminal works

• dijkstra1965
• herlihy1993
• savage1997
• lamport1978

Frequently asked questions

การแข่งขันข้อมูลคืออะไร?

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

ความแตกต่างระหว่างการประสานงานแบบใช้ล็อกกับการประสานงานแบบไร้ล็อกคืออะไร?

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