الفرق بين إجماع رقم N ورقم توافق في الآراء

Question

في كتاب البرمجة المتزامنة: الخوارزميات والمبادئ والمؤسسات من ميشيل رانال، في القسم 16.5.1، يقول نظرية 75

مقارنة وكائنات تبديل لها رقم إجماع لا حصر له.

وفي القسم 16.5.2، يقول Lemma 40

يحتوي نوع كائن Memon-Swap على رقم إجماع N في نظام العمليات N.

بعد ذلك، في القسم 16.1، يضع المؤلف في الجدول كلاهما مقارنة ومبادلة و MEN-TO-SWAT ككائنات ذات رقم إجماع لانهائي.

لذلك، ما هو الفرق بين الكائنات مع رقم الإجماع N والأشياء مع إجماع رقم غير محدود؟

Answer 1

عدد الإجماع من الكائن هو الحد الأقصى لعدد العمليات المتزامنة التي يمكنك مزامنتها مع أحد هذه الأشياء بطريقة خالية من الانتظار (لن أذهب إلى ما يعنيه ما انتظار الخالية هنا). على سبيل المثال، لا يساعد التسجيل في عمليات القراءة والكتابة فقط في المزامنة الخالية من الانتظار على الإطلاق، لذلك يحتوي على إجماع رقم 1. يمكن استخدام سجل مع عملية اختبار وحدد لمزامنة العمليات في انتظار طريقة خاصة، ولكن ليس ثلاثة أو أكثر، لذلك عدد الإجماع من الاختبار والحدد هو 2.

$ N $ -anment، حيث يمكن أن تكتب عملية الكتابة بشكل ساحر إلى سجلات متعددة، حتى $ 2n- 2 $ عمليات لمزامنة الانتظار مجانا إذا كان هناك $ n $ السجلات. المزيد من العمليات تتطلب المزيد من السجلات. لذلك عدد الإجماع من OBJET يتكون من $ N $ السجلات التي يمكن تعيينها بشكل جذري هو $ 2N-2 $ .

سجل واحد مع عملية مقارنة وبرنامج مبادلة يكفي لمزامنة أي عدد من العمليات خالية من الانتظار. لذلك عدد إجماع المقارنة والتبادل غير المحدود.

lemma 40 ينص على أن كائن mem-and swap يسمح بمزامنة الانتظار الخالية من جميع العمليات في نظام $ n $ العمليات المتزامنة، لأي رقم $ n $ . هذا يعني أنه بالنسبة لأي رقم $ n $ ، فإن عدد الإجماع من MEM-and-swap هو على الأقل $ n $ < / span>. (توضيح أن رقم الإجماع هو $ n $ في نظام $ n $ العمليات هي القليل من nechnomer لأن تعريف رقم الإجماع لا يعتمد فعليا على إجمالي عدد العمليات.) نظرا لأن عدد الإجماع من MEM-and-swap هو على الأقل $ n $ لأي $ n $ ، إنه لانهائي.

إذا كنت تفضل مصدر آخر من كتاب Raynal، فيمكنك قراءة ورقة من موريس هرليو .