ما هو رقم الإجماع للوظائف؟

Question

(أعتقد أن إجماع رقم للحصول على mutex هو 2.

ما هو رقم الإجماع للمدرسات (مثل في pthread_sem_ *)؟

ما هو رقم توافق الآراء لمتغيرات الحالة (مثل في pthread_cond_ *)؟

Answer 1

سيكون رقم الإجماع ل Mutex 1. من الواضح بشكل تاسبي أن Mutex ستكون خالية من الانتظار لخيط واحد. من تعريفها، من الواضح أيضا أن Mutex لم تعد خالية من المواضيع. رقم توافق الآراء هو> = 1 و <2، لذلك يجب أن يكون 1.

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

Answer 2

تعتمد الإجابة على العمليات المدعومة على Mutex أو الإشارة. إذا تم دعم حظر الأقفال فقط، فإن رقم الإجماع هو 1. إذا كان بإمكان مؤشر الترابط أن يحاول قفل موبيككس دون انتظار، فإن رقم الإجماع هو 2. أي أنه إذا كان هناك خيطان، كلاهما يمكن أن يحاول قفل موباك، كلاهما موافق أي واحد حصل عليه، لذلك هناك إجماع. إذا كان MUTEX يمكن أن يحدد بالإضافة ما، لأي عدد من المواضيع، الذي قام مؤشر ترابط بإغلاقه، ثم رقم الإجماع غير محدود. أعتقد أن الوضع بالنسبة للدرسات مماثلة. تعادل MUTEXES الإشارات مع العداد 1. لا أعتقد أنه يمكن الوصول إلى توافق الآراء فقط مع عدادات أكبر، فلا يزال يتراجع إلى نفس العمليات. يدعم Pthreads أقفال غير حظر ولكن ليس الاستفسارات، لذلك هناك إجابة ستكون 2.

الإشارة إلى متغير الشرط لا يفعل شيئا إذا لم يكن أي خيوط ينتظره، لذلك لديهم إجماع رقم 1.

Answer 3

لانهائي، بالتأكيد؟ لكنهم لا ينتظرون مجانا.

ربما أنا سوء فهم. أنت تقول إن موبيوكس لديه إجماع رقم 2 - ما هو مصدرك لذلك؟ انها مصممة للسماح لأي عدد من الخيوط لمشاركة مورد، مع التجانس من الحظر.

الذري اختبر لديه عدد إجماع من 2، ولكن لا يحظر.

---

لتوضيح: السماوات، Mutexes، إلخ. هي بدائية يمكنك ببساطة التفاف حول مورد مشترك لجعلها آمنة (طالما كنت تفعل ذلك بشكل صحيح). قد يمنعون، لكنهم سيضمنون بياناتك آمنة.

الورقة التي تشير إليها هي عن البدائيات اللازمة لحماية البيانات دون حظر, ، الذي الصعب. وبعد قد تكون نفسية نفسها مفيدة للأقفال أيضا، لكن هذا مجرد إضافي.

Answer 4

من هذه المقالة وحدها، يمكنك استنتاج أن الإشارة يجب أن يكون لها رقم إجماع أقل من أو يساوي 2. فيما يلي:

في الصفحة الثالثة من المقالة التي تذكرها: "جلب وإضافة عملية مرنة للغاية: يمكن استخدامها في الساعات ...". نظرا لأننا نعلم أن جلب وإضافة لديه عدد إجماع يساوي 2، يمكن بعد ذلك استخدام نظرية 1 من تلك الورقة لإظهار أن الإشارة يجب أن يكون لها رقم إجماع أقل من أو يساوي 2. يذهب الدليل مثل هذا:

دليل

افترض أن تنفيذ خال من الانتظار للدراسات من خلال جلب وإضافة موجود. كذلك افتراض أن الإشارة له رقم إجماع أكبر من 2. نحن نعلم أن جلب وإضافة لديه إجماع رقم 2. من Theorem 1، يمكننا أن نستنتج أنه لا يوجد أي تنفيذ خال من الانتظار لمعرفة وإضافة نظام أكثر من 2 عملية وبعد هذا يتناقض مع افتراض أن التنفيذ عن طريق جلب وإضافة موجود. لذلك، يجب أن يكون الإشارة رقم إجماع أقل من أو يساوي 2.

كيد