نموذج الممثل وحسابات العمليات

يمكن تمثيل قناة متزامنة بواسطة ممثل يستقبل البيانات putويرسلها get. فيما يلي سلوك الممثل في قناة متزامنة بسيطة:

• تحتوي كل putعملية اتصال على رسالة وعنوان يتم إرسال إشعار استلام إليه عند استلام الرسالة.
• لكل get عملية اتصال عنوان يتم إرسال الرسالة المستلمة إليه.
• عند استلام getرسالة، يختار الفاعل putرسالة بترتيب FIFO ، ويرسل الرسالة والإقرار إلى العناوين المحددة.

مع ذلك، لا تكفي قنوات الاتصال المتزامنة البسيطة لحسابات العمليات مثل عمليات الاتصال التسلسلي (CSP) [Hoare 1978 و1985]، وذلك بسبب استخدام أمر الاختيار المحمي (المُسمى بالأمر البديل في CSP). في أمر الاختيار المحمي، يمكن تقديم عروض متعددة (تُسمى حراسًا) بشكل متزامن عبر قنوات ورسائل متعددة put؛ getولكن لا يمكن اختيار أكثر من حارس واحد لكل تنفيذ لأمر الاختيار المحمي. ولأنه لا يمكن اختيار سوى حارس واحد، فإن أمر الاختيار المحمي يتطلب عمومًا بروتوكول التزام ثنائي المراحل ، أو ربما بروتوكول التزام ثلاثي المراحل إذا سُمح بانتهاء المهلة الزمنية في الحراس (كما في Occam 3 [1992]).

ضع في اعتبارك البرنامج التالي المكتوب بلغة CSP [Hoare 1978]:

[X :: Z!stop() || Y :: guard: boolean; guard := true; *[guard  →  Z!go(); Z?guard] || Z :: n: عدد صحيح؛ n:= 0؛ *[X?stop()  →  Y!false; print!n; [] Y?go()  →  n := n+1; Y!true] ]

بحسب كلينجر [1981]، يُجسّد هذا البرنامج عدم الحتمية الشاملة، إذ تنشأ هذه اللا حتمية من عدم اكتمال تحديد توقيت الإشارات بين العمليات الثلاث . Xيحتوي الأمر المحمي المتكرر في تعريف على بديلين: YZZ

1. stopيتم قبول الرسالة من ، Xوفي هذه الحالة Yيتم إرسال القيمة خطأ إلى ، printويتم إرسال القيمة إلىn
2. goيتم قبول رسالة من ، Yوفي هذه الحالة nيتم زيادة قيمة ويتم Yإرسال القيمة true إليها .

إذا Zقبلت stopالعملية الرسالة من X، فإنها Xتُنهي عملها. يؤدي قبول الرسالة stopإلى Yإرسال قيمة خاطئة ، والتي عند إدخالها كقيمة لحارسها، ستؤدي Yإلى إنهاء عملها. عندما تُنهي كلتا العمليتين Xو ، تُنهي العملية ، لأنها لم تعد تتلقى مدخلات من عمليات نشطة.YZ

في البرنامج أعلاه، توجد قنوات متزامنة من Xإلى Z، Yإلى Z، Zوإلى Y.

بحسب كنابي [1992]، وصف تشاندي وميسرا [1988] هذا بأنه مشابه لمشكلة تنسيق اللجنة:

يُعيّن أساتذة الجامعة في لجانٍ مختلفة. وقد يقرر أحد الأساتذة أحيانًا حضور اجتماعٍ لإحدى لجانه، فينتظر حتى يتسنى له ذلك. ولا تبدأ الاجتماعات إلا باكتمال الحضور. والهدف هو ضمان حضور عضوٍ واحدٍ على الأقل من أعضاء اللجنة في حال انتظارهم.

يكمن جوهر هذه المشكلة في أن لجنتين أو أكثر قد تشتركان في أستاذ واحد. فعندما يصبح هذا الأستاذ متاحاً، لا يمكنها اختيار سوى اجتماع واحد، بينما تستمر اللجان الأخرى في الانتظار.

يقدم هذا القسم بروتوكولاً موزّعاً بسيطاً للقنوات في حسابات العمليات المتزامنة. ويعاني هذا البروتوكول من بعض المشاكل التي سيتم تناولها في الأقسام التالية.

يكون سلوك أمر الاختيار المحمي كما يلي:

• يرسل الأمر رسالة إلى كل حارس من حراسه إلى prepare.
• عندما تتلقى أول رد من أحد حراسها يفيد بأنها مستعدة، فإنها ترسل رسالة إلى ذلك الحارس prepare to commitوترسل رسائل إلى جميع الحراس الآخرين abort.
  • عندما يتلقى النظام رسالة من الحارس تفيد بأنه جاهز prepared to commit، فإنه يرسل commitرسالة إلى الحارس. أما إذا أطلق الحارس استثناءً يفيد بأنه لا يستطيع prepare to commit، فإن أمر الاختيار المحمي يبدأ العملية برمتها من جديد.
• إذا أجاب جميع حراسها بأنهم لا يستطيعون prepare، فإن الأمر المحروس لا يفعل شيئًا.

يكون سلوك الحارس كما يلي:

• عند استلام رسالة prepare، يرسل الحارس prepareرسالة إلى كل قناة من القنوات التي يعرض التواصل معها. إذا كانت لدى الحارس قيم منطقية تشير إلى عدم قدرته على التواصل، prepareأو إذا ردت أي من القنوات بعدم قدرتها على ذلك prepare، فإنه يرسل abortرسائل إلى القنوات الأخرى ثم يرد بعدم قدرتها على التواصل prepare.
  • عند استلام رسالة prepare to commit، يقوم الحارس بإرسال prepare to commitرسالة إلى كل قناة من القنوات. إذا ردت أي من القنوات بأنها لا تستطيع prepare to commit، فإنه يرسل abortرسائل إلى القنوات الأخرى ثم يطرح استثناءً يفيد بعدم قدرته على ذلك prepare to commit.
  • عندما يتم استلام رسالة commit، يقوم الحارس بإرسال commitرسالة إلى كل قناة من القنوات.
  • عندما يتم استلام رسالة abort، يقوم الحارس بإرسال abortرسالة إلى كل قناة من القنوات.

يكون سلوك القناة كما يلي:

• عند prepare to putاستلام رسالة، قم بالرد بأنها جاهزة إذا كانت هناك prepare to getرسالة معلقة، إلا إذا terminateتم استلام رسالة بالفعل، وفي هذه الحالة قم برمي استثناء يفيد بأنه لا يمكن ذلك prepare to put.
• عند prepare to getاستلام رسالة، قم بالرد بأنها جاهزة إذا كانت هناك prepare to putرسالة معلقة، إلا إذا terminateتم استلام رسالة بالفعل، وفي هذه الحالة قم برمي استثناء يفيد بأنه لا يمكن ذلك prepare to get.
  • عند prepare to commit to putاستلام رسالة، قم بالرد بأنها جاهزة إذا كانت هناك prepare to commit to getرسالة معلقة، إلا إذا terminateتم استلام رسالة بالفعل، وفي هذه الحالة قم برمي استثناء يفيد بأنه لا يمكن ذلك prepare to commit to put.
  • عند prepare to commit to getاستلام رسالة، قم بالرد بأنها جاهزة إذا كانت هناك prepare to commit to putرسالة معلقة، إلا إذا terminateتم استلام رسالة بالفعل، وفي هذه الحالة قم برمي استثناء يفيد بأنه لا يمكن ذلك prepare to commit to get.
    • عند commit putاستلام رسالة، يعتمد ذلك على أي مما يلي تم استلامه:
      • عند commit getاستلام أي اتصال، قم بتنفيذ الإجراءات اللازمة وتنظيف التجهيزات إن لم تكن قد تم ذلك putبالفعل get.
      • عند abort getتلقي أي اتصال، قم بإلغاء الاستعدادات
    • عند commit getاستلام رسالة، يعتمد ذلك على أي مما يلي تم استلامه:
      • عند commit putاستلام أي اتصال، قم بتنفيذ الإجراءات اللازمة وتنظيف التجهيزات إن لم تكن قد تم ذلك getبالفعل put.
      • عند abort putتلقي أي اتصال، قم بإلغاء الاستعدادات.
    • عند abort putتلقي أي اتصال، قم بإلغاء الاستعدادات.
    • عند abort getتلقي أي اتصال، قم بإلغاء الاستعدادات.

لنأخذ مرة أخرى البرنامج المكتوب بلغة CSP (الذي تمت مناقشته في قسم القنوات المتزامنة في حسابات العمليات أعلاه):

[X :: Z!stop() || Y :: guard: boolean; guard := true; *[guard  →  Z!go(); Z?guard] || Z :: n: عدد صحيح؛ n:= 0؛ *[X?stop()  →  Y!false; print!n; [] Y?go()  →  n := n+1; Y!true] ]

كما أشير في كنابي [1992]، فإن إحدى مشاكل البروتوكول المذكور أعلاه ( بروتوكول توزيع بسيط ) هي أن العملية Zقد لا تقبل stopالرسالة من X(ظاهرة تسمى الحرمان ) وبالتالي قد لا يطبع البرنامج المذكور أعلاه أي شيء.

على النقيض من ذلك، لنفترض نظام ممثلين بسيطًا يتكون من الممثلين X و Y و Z ، ونطبع حيث

• يتم إنشاء الممثل X بالسلوك التالي:
  • إذا تم استلام الرسالة "start"، فأرسل الرسالة إلى Z"stop"
• يتم إنشاء الممثل Y بالسلوك التالي:
  • إذا تم استلام الرسالة "start"، فأرسل الرسالة إلى Z"go"
  • إذا تم استلام الرسالة "صحيح" ، فأرسل الرسالة إلى Z"go"
  • إذا تم استلام رسالة خاطئة ، فلا تفعل شيئًا.
• يتم إنشاء الممثل Z بالسلوك التالي الذي يكون عدده nفي البداية 0 :
  • إذا تم استلام الرسالة "start"، فلا تفعل شيئاً.
  • إذا تم استلام الرسالة "stop"، فأرسل Y الرسالة خطأ وأرسل طباعة الرسالة العدد n.
  • إذا تم استلام الرسالة "go"، فأرسل Y الرسالة صحيحة وقم بمعالجة الرسالة التالية المستلمة مع كون العدد nهو n+1.

بحسب قوانين دلالات الممثل، سيتوقف نظام الممثل المذكور أعلاه دائمًا عندما يتم إرسال رسالة إلى كل من الممثلين X و Y و Z"start" مما يؤدي إلى إرسال طباعة رقم يمكن أن يكون كبيرًا بلا حدود.

يكمن الفرق بين برنامج CSP ونظام الممثل في أن الممثل Z لا يستقبل الرسائل باستخدام أمر اختيار محمي من قنوات متعددة. بدلاً من ذلك، يعالج الرسائل حسب ترتيب وصولها، وبموجب قوانين أنظمة الممثل، stopيُضمن وصول الرسالة.

ضع في اعتبارك البرنامج التالي المكتوب بلغة CSP [Hoare 1978]:

[Bidder1 :: b: bid; *[Bids1?b  →  process1!b; [] Bids2?b  →  process1!b;] || مقدم العرض 2 :: ب: عرض؛ *[Bids1?b  →  process2!b; [] Bids2?b  →  process2!b;] ]

كما أشار كنابي [1992]، تكمن إحدى مشكلات البروتوكول المذكور أعلاه ( بروتوكول توزيع بسيط ) في أن العملية Bidder2قد لا تقبل عرضًا من Bid1أو Bid2(ظاهرة تُعرف باسم "التعطل ")، وبالتالي process2قد لا تتلقى أي شيء. في كل محاولة لقبول رسالة، Bidder2تُحبط العملية لأن العرض المقدم من Bids1أو Bids2يُنتزع من قبل، Bidder1إذ يتضح أن Bidder1الوصول إلى العملية أسرع بكثير من الوصول Bidder2إلى Bids1و Bids2. ونتيجة لذلك، Bidder1يمكن للعملية قبول عرض، ومعالجته، ثم قبول عرض آخر قبل أن Bidder2تتمكن من الالتزام بقبول عرض.

كما أشار كنابي [1992]، فإن إحدى مشكلات البروتوكول المذكور أعلاه ( بروتوكول توزيع بسيط ) هي العدد الكبير من الاتصالات اللازمة لإجراء المصافحة وإرسال رسالة عبر قناة متزامنة. في الواقع، وكما هو موضح في القسم السابق ( التعطل )، قد يكون عدد الاتصالات غير محدود.

أوضحت الأقسام الفرعية أعلاه القضايا الثلاث التالية المتعلقة باستخدام القنوات المتزامنة لحسابات العمليات:

1. التجويع. يمكن أن يتسبب استخدام القنوات المتزامنة في حدوث تجويع عندما تحاول عملية ما الحصول على رسائل من قنوات متعددة في أمر اختيار محمي.
2. التعطل. يمكن أن يؤدي استخدام القنوات المتزامنة إلى تعطل العملية عندما تحاول الحصول على رسائل من قنوات متعددة في أمر اختيار محمي.
3. الكفاءة. قد يتطلب استخدام القنوات المتزامنة عددًا كبيرًا من الاتصالات من أجل الحصول على رسائل من قنوات متعددة في أمر اختيار محمي.

ومن الجدير بالذكر أنه في كل ما سبق، تنشأ المشكلات من استخدام أمر اختيار محمي للحصول على رسائل من قنوات متعددة.

يمكن تمثيل قناة غير متزامنة بواسطة ممثل يستقبل البيانات putويرسلها get. فيما يلي سلوك الممثل في قناة غير متزامنة بسيطة:

• تحتوي كل putعملية اتصال على رسالة وعنوان يتم إرسال إشعار استلام إليه على الفور (دون انتظار وصول الرسالة عن طريق getالاتصال).
• لكل get عملية اتصال عنوان يتم إرسال الرسالة المستلمة إليه.

لغة برمجة Join-calculus (التي نُشرت عام 1996) تُنفذ عمليات حسابية متزامنة محلية وموزعة. وقد تضمنت قنوات غير متزامنة، بالإضافة إلى نوع من القنوات المتزامنة المستخدمة لاستدعاء الإجراءات. يعتمد حساب Aπ Actor الخاص بآغا ( آغا وثاتي، 2004 ) على نسخة مُصنفة من حساب π-calculus غير المتزامن .