نموذج موارد خوارزمية تشاندي-ميسرا-هاس

تتحقق خوارزمية تشاندي -ميسرا-هاس لنموذج الموارد من حالات الجمود في النظام الموزع . وقد طُوّرت هذه الخوارزمية بواسطة ك. ماني تشاندي ، وجاياديف ميسرا، ولورا م. هاس .

لنفترض وجود n عملية P1 _، P2 ، P3 _، P4 ، _{P5 ،} ...، _Pn تُنفذ في نظام واحد (وحدة تحكم). تعتمد _P1 محليًا على Pn _إذا كانت P1 _تعتمد على P2 _، و P2 على P3 ، _وهكذا ، _و Pn _{- 1} على Pn . أي ، _إذا${\displaystyle P_{1}\rightarrow P_{2}\rightarrow P_{3}\rightarrow \ldots \rightarrow P_{n}}$، ثم${\displaystyle P_{1}}$يعتمد محليًا على${\displaystyle P_{n}}$إذا قيل أن P1 يعتمد محليًا على نفسه _، وكان يعتمد محليًا على Pn _، وكان Pn يعتمد على P1 _، أي _إذا${\displaystyle P_{1}\rightarrow P_{2}\rightarrow P_{3}\rightarrow \ldots \rightarrow P_{n}\rightarrow P_{1}}$، ثم${\displaystyle P_{1}}$يعتمد على نفسه محلياً.

تستخدم الخوارزمية رسالة تُسمى probe(i,j,k) لنقل رسالة من وحدة تحكم العملية _Pj إلى وحدة تحكم العملية Pk . تُحدد هذه الرسالة رسالةً بدأتها العملية Pi للتحقق مما إذا كان قد حدث تعطل أم لا. تحتفظ كل عملية Pj بمصفوفة منطقية تُسمى dependent _{، تحتوي على معلومات حول العمليات التي تعتمد عليها. في البداية ،} تكون جميع قيم كل مصفوفة "خطأ".

في الشفرة الزائفة ، تعمل الخوارزمية على النحو التالي: ^{[ 1 ]}

إذا كانت P j تعتمد محليًا على نفسها، فأعلن عن حالة تعطل ، وإلا فلكل P j و P k بحيث (i) P i يعتمد محليًا على P j ، (ii) ينتظر P j ' P k و (iii) P j و P k موجودان على وحدات تحكم مختلفة. أرسل إشارة التحقق (i, j, k) إلى الموقع الرئيسي لـ P k

إذا (1) كان P k خاملاً / محجوباً (ii) التابع k (i) = خطأ، و (iii) إذا لم يستجب P k لجميع طلبات P j، فابدأ بـ "التابعين" "k" (i) = صحيح؛ إذا كان k == i، فأعلن أن P i في حالة جمود، وإلا لكل P a و P b بحيث (i) يعتمد P k محليًا على P a ، (ii) ينتظر P a و P b (iii) P a و P b موجودان على وحدات تحكم مختلفة. أرسل المسبار (i, a, b) إلى الموقع الرئيسي لـ P b .

يبدأ P1 عملية اكتشاف حالة التعطل. _يرسل C1 إشارة تفيد بأن P2 يعتمد على P3 . بمجرد _استلام C2 للرسالة ، يتحقق مما إذا كان _P3 في وضع الخمول. يكون P3 _{في وضع} الخمول لأنه يعتمد محليًا على P4 _، ويُحدِّث _P3 (2) التابع إلى _{" صحيح "} .

كما سبق، يرسل C2 إشارة فحص إلى C3 _{، ويرسل} C3 إشارة فحص إلى C1 _. عند C1 ، يكون P1 _في وضع الخمول _، لذا يقوم بتحديث التابع _{1 (1 )} إلى صحيح. وبالتالي، يمكن إعلان حالة تعطل.

لنفترض أن هناك${\displaystyle n}$أجهزة التحكم و${\displaystyle m}$العمليات، على الأكثر${\displaystyle m(n-1)/2}$يجب تبادل الرسائل لاكتشاف حالة الجمود، مع تأخير قدره${\displaystyle O(n)}$الرسائل. ^{[ 2 ]}