อัลกอริทึมของเรย์มอนด์
อัลกอริทึมของเรย์มอนด์เป็นอัลกอริทึมแบบใช้ล็อกสำหรับการกีดกันร่วมกันในระบบกระจายอำนาจโดยกำหนดโครงสร้างเชิงตรรกะ ( ต้นไม้ K-ary ) ให้กับทรัพยากรแบบกระจายอำนาจ ตามที่กำหนดไว้ โหนดแต่ละโหนดจะมีโหนดแม่เพียงโหนดเดียว ซึ่งคำขอทั้งหมดในการขอรับโทเค็นจะถูกส่งไปยังโหนดแม่นั้น
อัลกอริทึม
คุณสมบัติของโหนด
- แต่ละโหนดจะมีโหนดแม่เพียงโหนดเดียว ซึ่งคำขอที่ได้รับจะถูกส่งต่อไปยังโหนดนั้น
- แต่ละโหนดจะรักษาคิวคำขอแบบ FIFO ไว้ทุกครั้งที่ได้รับโทเค็น
- หากโหนดใดกำลังส่งต่อสิทธิ์ไปยังโหนดอื่นและมีคิวที่ไม่ว่างเปล่า โหนดนั้นจะส่งต่อข้อความร้องขอไปด้วย
อัลกอริทึม
- หากโหนดi (ที่ไม่ได้ถือโทเค็น) ต้องการรับโทเค็นเพื่อเข้าสู่ส่วนวิกฤต ของตน โหนด i จะส่งคำขอไปยังโหนดแม่คือโหนดj
- ถ้า FIFO ของโหนดjว่างเปล่า โหนดjจะย้ายiเข้าไปในคิว FIFO ของตน จากนั้น jจะส่งคำขอไปยังโหนดแม่kเพื่อขอโทเค็น
- ถ้าคิว FIFO ของโหนด j ไม่ว่าง ระบบจะเลื่อนโหนดiเข้าไปในคิว โดยตรง
- เมื่อโหนดkมีโทเค็นและได้รับคำขอจากโหนด jโหนด k จะส่งโทเค็นไปยังโหนด jและกำหนดให้โหนดjเป็นโหนดแม่
- เมื่อโหนดjได้รับโทเค็นจากkแล้ว มันจะส่งต่อโทเค็นไปยังiและiจะถูกลบออกจากคิวของj
- หากคิวของjยังไม่ว่างหลังจากส่งโทเค็นไปยังiแล้วjจะต้องส่งคำขอไปยังiเพื่อขอรับโทเค็นคืน
หมายเหตุ : หากโหนดjต้องการขอโทเค็น และคิวของโหนด j ไม่ว่างเปล่า โหนด j จะเพิ่มตัวเองเข้าไปในคิวของตนเอง โหนดjจะใช้โทเค็นนั้นเพื่อเข้าสู่ส่วนวิกฤต (critical section) หากโหนด j อยู่ที่หัวคิวเมื่อได้รับโทเค็น
ความซับซ้อน
อัลกอริทึมของเรย์มอนด์รับประกันว่าจะมีประสิทธิภาพO(log n)ต่อรายการในส่วนวิกฤต หากโปรเซสเซอร์ถูกจัดเรียงเป็น ต้นไม้ K-aryนอกจากนี้ โปรเซสเซอร์แต่ละตัวจำเป็นต้องจัดเก็บบิตอย่างมากที่สุดO(log n)เนื่องจากต้องติดตามเพื่อนบ้านO(1) [ 1 ]