خوارزمية ريموند

خوارزمية ريموند هي خوارزمية تعتمد على القفل لتحقيق الاستبعاد المتبادل في نظام موزع . تفرض هذه الخوارزمية بنية منطقية ( شجرة من الرتبة K ) على الموارد الموزعة. وكما هو مُعرّف، لكل عقدة أصل واحد فقط، تُوجّه إليه جميع طلبات الحصول على الرمز المميز.

الخوارزمية

خصائص العقدة

  1. لكل عقدة أصل واحد فقط يتم توجيه الطلبات الواردة إليه
  2. تحتفظ كل عقدة بقائمة انتظار FIFO للطلبات في كل مرة ترى فيها الرمز المميز؛
  3. إذا كانت أي عقدة تقوم بإعادة توجيه الامتيازات إلى عقدة أخرى ولديها قائمة انتظار غير فارغة، فإنها تعيد توجيه رسالة الطلب.

الخوارزمية

  1. إذا رغبت عقدة i (التي لا تحمل الرمز المميز) في الحصول على الرمز المميز من أجل الدخول إلى قسمها الحرج ، فإنها ترسل طلبًا إلى عقدتها الأصلية، العقدة j .
    • إذا كانت قائمة انتظار FIFO للعقدة j فارغة، فإن العقدة j تُدخل العنصر i في قائمة انتظار FIFO الخاصة بها؛ ثم تُصدر j طلبًا إلى العقدة الأب k تُفيد فيه برغبتها في الحصول على الرمز المميز.
    • إذا لم تكن قائمة انتظار FIFO للعقدة j فارغة، فإنها ببساطة تنقل العنصر i إلى قائمة الانتظار.
  2. عندما تمتلك العقدة k رمزًا مميزًا وتتلقى الطلب من فإنها ترسل الرمز المميز إلى j وتجعل j بمثابة العقدة الأب لها.
  3. عندما يستلم العقد j الرمز المميز من k ، فإنه يعيد توجيه الرمز المميز إلى i ويتم إزالة i من قائمة انتظار j
    • إذا لم تكن قائمة انتظار j فارغة بعد إعادة توجيه الرمز المميز إلى i ، فيجب على j إصدار طلب إلى i لاستعادة الرمز المميز.

ملاحظة : إذا رغب العقد j في طلب رمز مميز، ولم تكن قائمة انتظاره فارغة، فإنه يضع نفسه في قائمته الخاصة. سيستخدم العقد j الرمز المميز للدخول إلى قسمه الحرج إذا كان في مقدمة قائمة الانتظار عند استلام الرمز.

تعقيد

يضمن خوارزمية ريموند أن يكون زمن تنفيذها O(log n) لكل مدخل من مداخل القسم الحرج إذا تم تنظيم المعالجات في شجرة من الرتبة K. بالإضافة إلى ذلك، يحتاج كل معالج إلى تخزين O(log n) بت على الأكثر لأنه يجب عليه تتبع O(1) من الجيران. [ 1 ]

مراجع

  1. آر. تشاو، تي. جونسون؛ أنظمة التشغيل الموزعة والخوارزميات ؛ أديسون-ويسلي، 1997.

انظر أيضاً