การกีดกันร่วมแบบกระจายและการเลือกหัวหน้า

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

Definition

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

Scope

หัวข้อนี้ครอบคลุมอัลกอริทึมการกีดกันร่วมแบบใช้การอนุญาต (อัลกอริทึมการประทับเวลาของ Lamport, Ricart-Agrawala, แนวทางโควรัมของ Maekawa) และอัลกอริทึมแบบใช้โทเค็น พร้อมด้วยความซับซ้อนของข้อความและคุณสมบัติความเป็นธรรม และอัลกอริทึมการเลือกหัวหน้าสำหรับวงแหวน (Chang-Roberts) และเครือข่ายทั่วไป (อัลกอริทึม bully) รวมถึงข้อสมมติเกี่ยวกับตัวระบุและการซิงโครไนซ์ หลักการพื้นฐานเหล่านี้ปรากฏซ้ำๆ ในบริการประสานงานและระบบจำลองแบบ

Core questions

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

Key theories

การกีดกันร่วมแบบใช้การอนุญาต

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

การกีดกันร่วมแบบใช้โทเค็น

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

การเลือกหัวหน้า

อัลกอริทึมการเลือกเช่น Chang-Roberts สำหรับวงแหวนและอัลกอริทึม bully สำหรับเครือข่ายทั่วไปใช้ตัวระบุกระบวนการเพื่อรวมกันเป็นผู้ประสานงานที่มีลำดับความสำคัญสูงสุดเพียงคนเดียวที่กระบวนการที่ถูกต้องทั้งหมดรับรู้

Clinical relevance

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

History

บทความเกี่ยวกับนาฬิกาเชิงตรรกะของ Lamport ในปี 1978 ได้นำเสนออัลกอริทึมการกีดกันร่วมแบบใช้การประทับเวลา Ricart และ Agrawala ได้ปรับปรุงให้เหมาะสมในปี 1981 Maekawa ได้นำเสนอโควรัมหลังจากนั้นไม่นาน และอัลกอริทึม bully ของ Garcia-Molina ในปี 1982 ได้กำหนดรูปแบบการเลือกหัวหน้าอย่างเป็นทางการ ซึ่งทำให้อัลกอริทึมการประสานงานที่เป็นแบบฉบับของสาขาวิชานี้

Key figures

• Leslie Lamport
• Glenn Ricart
• Ashok Agrawala
• Hector Garcia-Molina

Seminal works

• ricart1981
• garcia-molina1982
• lynch1996

Frequently asked questions

การกีดกันร่วมแบบกระจายแตกต่างจากการล็อกบนเครื่องเดียวอย่างไร?

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