كيف يمكنني التحقق من الخوارزميات الخالية من القفل؟

Question

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

ملاحظة: إذا كنت تعرف طريقة لإثبات نقطة واحدة فقط (على سبيل المثال ، أثبت فقط أنها آمنة من مشكلة ABA) أو مشكلة لم أذكرها ، ثم نشر الحل على أي حال. في أسوأ سيناريو ، يمكن القيام بكل طريقة بدورها للتحقق منها بالكامل.

Answer 1

يجب عليك بالتأكيد تجربة تدور نموذج المدقق.

تكتب نموذجًا يشبه البرنامج بلغة بسيطة تشبه C تسمى Promela ، والتي تدور داخليًا إلى آلة الحالة. يمكن أن يحتوي النموذج على عمليات متوازية متعددة.

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

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

هذا لا يصدق البرنامج ، فاز في عام 2001 جائزة برنامج نظام ACM (تشمل الفائزون الآخرون Unix ، Postscript ، Apache ، Tex). لقد بدأت في استخدامه بسرعة كبيرة ، وفي غضون يومين ، تمكنت من تنفيذ نماذج وظائف MPI MPI_Isend() و MPI_Irecv() في باريسليلا. عثرت Spin على اثنين من مخادع ظروف السباق في شريحة واحدة من الكود المتوازي الذي قمت بتحويله عبر البرولة للاختبار.

Answer 2

الدوران ممتازة بالفعل ، ولكن أيضًا ضع في اعتبارك كاشف سباق الانتصاف بقلم ديمتري فاجوكوف. إنه مصمم خصيصًا للتحقق من الخوارزميات المتزامنة بما في ذلك خوارزميات عدم الحظر (WAIT-/LOCK FREE). إنه مفتوح المصدر ومرخص له بحرية.

يوفر RICASY POSIX و Windows Synchronization Primitives (Mutexes ، متغيرات الحالة ، الإشارات ، الحرج ، أحداث WIN32 ، متشابكة*، إلخ) ، لذلك يمكن تغذية تطبيق C ++ الفعلي بالتعلق للتحقق. لا حاجة لتطوير نموذج منفصل لخوارزميةك كما هو الحال مع البرولة والدوران.

يوفر التربية C ++ 0x std::atomic (طلب ذاكرة صريح للفوز!) حتى تتمكن من استخدام المعالج المسبق #defines للاختيار بين تنفيذ Ricaly والتنفيذ الذري المحدد للنظام الأساسي الخاص بك (TBB :: Atomic, Boost :: Atomic, ، إلخ).

يمكن السيطرة على الجدولة: العشوائية ، المرتبطة بالسياق ، والبحث الكامل (جميع عمليات التواصل المحتملة) المتاحة.

إليك مثال برنامج Liclacy. هناك عدد قليل من الأشياء ملاحظة:

• ال $ هو الماكرو للتعليم الذي يسجل معلومات التنفيذ.
• rl::var<T> الأعلام "العادية" (غير الذرية) المتغيرات التي تحتاج أيضًا إلى اعتبارها جزءًا من التحقق.

الرمز:

#include <relacy/relacy_std.hpp>

// template parameter '2' is number of threads
struct race_test : rl::test_suite<race_test, 2>
{
    std::atomic<int> a;
    rl::var<int> x;

    // executed in single thread before main thread function
    void before()
    {
        a($) = 0;
        x($) = 0;
    }

    // main thread function
    void thread(unsigned thread_index)
    {
        if (0 == thread_index)
        {
            x($) = 1;
            a($).store(1, rl::memory_order_relaxed);
        }
        else
        {
            if (1 == a($).load(rl::memory_order_relaxed))
                x($) = 2;
        }
    }

    // executed in single thread after main thread function
    void after()
    {
    }

    // executed in single thread after every 'visible' action in main threads
    // disallowed to modify any state
    void invariant()
    {
    }
};

int main()
{
    rl::simulate<race_test>();
}

التجميع مع المترجم العادي الخاص بك (الارتباط هو الرأس فقط) وقم بتشغيل القابل للتنفيذ:

struct race_test
DATA RACE
iteration: 8

execution history:
[0] 0:  atomic store, value=0, (prev value=0), order=seq_cst, in race_test::before, test.cpp(14)
[1] 0:  store, value=0, in race_test::before, test.cpp(15)
[2] 0:  store, value=1, in race_test::thread, test.cpp(23)
[3] 0:  atomic store, value=1, (prev value=0), order=relaxed, in race_test::thread, test.cpp(24)
[4] 1:  atomic load, value=1, order=relaxed, in race_test::thread, test.cpp(28)
[5] 1:  store, value=0, in race_test::thread, test.cpp(29)
[6] 1: data race detected, in race_test::thread, test.cpp(29)

thread 0:
[0] 0:  atomic store, value=0, (prev value=0), order=seq_cst, in race_test::before, test.cpp(14)
[1] 0:  store, value=0, in race_test::before, test.cpp(15)
[2] 0:  store, value=1, in race_test::thread, test.cpp(23)
[3] 0:  atomic store, value=1, (prev value=0), order=relaxed, in race_test::thread, test.cpp(24)

thread 1:
[4] 1:  atomic load, value=1, order=relaxed, in race_test::thread, test.cpp(28)
[5] 1:  store, value=0, in race_test::thread, test.cpp(29)
[6] 1: data race detected, in race_test::thread, test.cpp(29)

توفر الإصدارات الحديثة من Ricaly أيضًا نماذج ذاكرة Java و CLI إذا كنت في هذا النوع من الأشياء.

Answer 3

اكتشاف سباق البيانات هو مشكلة صعبة NP [Netzer & Miller 1990

سمعت عن قفل الأدوات ، و djit+ (هم تدريسه في دورة CDP). حاول قراءة الشرائح ، و googling ما يشيرون إليه. أنه يحتوي على بعض المعلومات المثيرة للاهتمام.

Answer 4

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

لم أستخدمها كمية كبيرة ، عقل.

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

في الماضي ، قمت أيضًا ببناء إصدارات خاصة من الكود المعني (من خلال كتل #if وما إلى ذلك) التي تضيف معلومات تتبع الحالة الإضافية ؛ التهم والإصدارات وما إلى ذلك يمكنني بعد ذلك الانخفاض في اختبار الوحدة.

المشكلة في ذلك هي أن الأمر يتطلب الكثير من الوقت لكتابة الكود الخاص بك ، ولا يمكنك دائمًا إضافة هذا النوع من الأشياء دون تغيير الهيكل الأساسي للرمز الموجود بالفعل.

Answer 5

إذا كنت ترغب حقًا في التحقق من الكود الخالي من القفل (على عكس اختبار مثيل صغير بشكل شامل) ، يمكنك استخدام VCC (http://vcc.codeplex.com) ، التحقق الاستنتاجي لرمز C المتزامن والذي تم استخدامه للتحقق من بعض الخوارزميات المثيرة للاهتمام الخالية من القفل (مثل القوائم الخالية من القفل والعلامات التجزئة التي يمكن إصلاحها باستخدام مؤشرات المخاطر ، ومعالجة المعاملات المتعددة المتفائلة ، والمحاكاة الافتراضية MMU ، ومختلف التزامن ، وما إلى ذلك). يقوم بالتحقق المعياري ، وقد تم استخدامه للتحقق من قطع غير تافهة للرمز الصناعي (تصل إلى حوالي 20 كيلوكة).

لاحظ ، مع ذلك ، أن VCC هو expier ، وليس أداة صيد الأخطاء ؛ سيتعين عليك القيام بتوضيح كبير على الشفرة الخاصة بك للحصول عليه للتحقق ، ويمكن أن يكون منحنى التعلم حادًا بعض الشيء. لاحظ أيضًا أنه يفترض الاتساق المتسلسل (كما يفعل معظم الأدوات).

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