كيفية إظهار أن نمط القفل المزدوج مع TrygetValue من Dictionary ليس مؤشر الترابط

Question

لقد رأيت مؤخرًا بعض مشاريع C# التي تستخدم نمط قفل مزدوج على أ Dictionary. شيء من هذا القبيل:

private static readonly object _lock = new object();
private static volatile IDictionary<string, object> _cache = 
    new Dictionary<string, object>();

public static object Create(string key)
{
    object val;
    if (!_cache.TryGetValue(key, out val))
    {
        lock (_lock)
        {
            if (!_cache.TryGetValue(key, out val))
            {
                val = new object(); // factory construction based on key here.
                _cache.Add(key, val);
            }
        }
    }
    return val;
}

هذا الرمز غير صحيح ، لأن Dictionary يمكن أن تكون "تنمو" المجموعة في _cache.Add() في حين _cache.TryGetValue (خارج القفل) هو التكرار على المجموعة. قد يكون من غير المرجح للغاية في العديد من المواقف ، لكنه لا يزال خطأ.

هل هناك برنامج بسيط لإثبات أن هذا الرمز يفشل؟

هل من المنطقي دمج هذا في اختبار الوحدة؟ وإذا كان الأمر كذلك ، كيف؟

Answer 1

في هذا المثال ، يتم إلقاء الاستثناء رقم 1 على الفور تقريبًا على جهازي:

var dict = new Dictionary<int, string>() { { 1234, "OK" } };

new Thread(() =>
{
    for (; ; )
    {
        string s;
        if (!dict.TryGetValue(1234, out s))
        {
            throw new Exception();  // #1
        }
        else if (s != "OK")
        {
            throw new Exception();  // #2
        }
    }
}).Start();

Thread.Sleep(1000);
Random r = new Random();
for (; ; )
{
    int k;
    do { k = r.Next(); } while (k == 1234);
    Debug.Assert(k != 1234);
    dict[k] = "FAIL";
}

ومع ذلك ، فإن السلوك الدقيق للكود غير المصمم ليكون آمن لا يمكن التنبؤ به.
أنت لا يمكن الاعتماد عليها. وبالتالي فإن رمز الفحص المزدوج مكسور بالفعل.

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

Answer 2

من الواضح أن الكود ليس مؤشر ترابط. ما لدينا هنا هو حالة واضحة لمخاطر التحسين المبكر.

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

من الواضح أننا لسنا في الحالة الثانية. أنت تستخدم قاموسًا من أجل السماء. حتى بدون القفل ، فإنه سيقوم بإجراء عمليات بحث ومقارنات ستكون مئات أو آلاف المرات أكثر تكلفة من وفورات تجنب قفل بلا جدال.

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

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

Answer 3

لا أعتقد حقًا أنك بحاجة إلى لإثبات ذلك ، تحتاج فقط إلى إحالة الأشخاص إلى وثائق ل Dictionary<TKey, TValue>:

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

إنها في الواقع حقيقة معروفة (أو ينبغي أن تكون) لا يمكنك القراءة من القاموس بينما يكتب مؤشر ترابط آخر إليه. لقد رأيت بعض أنواع الأسئلة "الغريبة متعددة الخيوط" من الأسئلة هنا ، حيث اتضح أن المؤلف لم يدرك أن هذا لم يكن آمنًا.

لا ترتبط المشكلة على وجه التحديد بالقفل الذي تم فحصه مزدوجًا ، فهو مجرد أن القاموس ليس فئة آمنة من مؤشرات الترابط ، ولا حتى بالنسبة لسيناريو كاتب واحد/قارئ واحد.

---

سأذهب خطوة واحدة إلى الأمام وأريكم لماذا ، في عاكس ، هذا ليس آمنًا للموضوع:

private int FindEntry(TKey key)
{
    // Snip a bunch of code
    for (int i = this.buckets[num % this.buckets.Length]; i >= 0;
        i = this.entries[i].next)
    // Snip a bunch more code
}

private void Resize()
{
    int prime = HashHelpers.GetPrime(this.count * 2);
    int[] numArray = new int[prime];
    // Snip a whole lot of code
    this.buckets = numArray;
}

انظر إلى ما يمكن أن يحدث إذا Resize يحدث أن يتم تشغيل الطريقة بينما حتى مكالمات القارئ FindEntry:

1. الموضوع أ: يضيف عنصرًا ، مما يؤدي إلى تغيير حجم ديناميكي ؛
2. الموضوع ب: يحسب إزاحة دلو (رمز التجزئة ٪ عدد دلو) ؛
3. الموضوع أ: يغير الدلاء للحصول على حجم مختلف (رئيسي) ؛
4. الموضوع ب: يختار فهرس العناصر من الجديد صفيف دلو في قديم فهرس دلو
5. مؤشر الموضوع B لم يعد صالحًا.

وهذا هو بالضبط ما فشل في مثال DTB. الخيط A يبحث عن مفتاح معروف مقدما أن تكون في القاموس ، ومع ذلك لم يتم العثور عليها. لماذا ا؟ بسبب ال FindValue اختارت الطريقة ما اعتقدت أنه الدلو الصحيح ، ولكن قبل أن تتاح لها فرصة للنظر في الداخل ، قام الخيط B بتغيير الجرافات ، والآن يبحث الموضوع A في بعض الدلو العشوائي تمامًا الذي لا يحتوي أو حتى يؤدي إلى الإدخال الصحيح.

المغزى من القصة: TryGetValue ليست عملية ذرية ، و Dictionary<TKey, TValue> ليست فئة آمنة مؤشرات الترابط. إنها ليست مجرد كتابة متزامنة أنك بحاجة إلى القلق ؛ لا يمكن أن يكون لديك متزامن القراءة والكتابة أيضا.

في الواقع ، فإن المشكلة تعمل في الواقع بشكل أعمق بكثير من هذا ، بسبب تعليمات إعادة ترتيبها بواسطة الارتعاش ووحدة المعالجة المركزية ، وذاكرة التخزين المؤقت التي لا معنى لها ، وما إلى ذلك - لا توجد حواجز للذاكرة على الإطلاق هنا - ولكن هذا يجب أن يثبت يدع مجالا للشك أن هناك حالة سباق واضحة إذا كان لديك Add الاحتجاج في نفس الوقت مثل أ TryGetValue استدعاء.

Answer 4

السبب في أنني أعتقد أن هذا السؤال يأتي مرارًا وتكرارًا:

قبل 2.0 ، قبل الأدوية (BG) ، Hashtable كانت الحاوية الترابطية الأساسية في .NET ، والتي توفر بالفعل بعض ضمانات الخيوط. من MSDN:
"Hashtable هو مؤشر ترابط آمن للاستخدام من قِبل مؤشرات ترابط القارئ المتعددة وخيط كتابة واحد. إنه مؤشر ترابط آمن للاستخدام متعدد الخيوط عندما يكون أحد عمليات مؤشرات الترابط (تحديث) فقط ، مما يسمح بقراءات خالية من القفل بشرط يتم تسلسلها إلى علامة التصنيف ".

قبل أن يحصل أي شخص الى ابعد حد متحمس ، هناك بعض القيود.
انظر على سبيل المثال هذا المنشور من براد أبرامز, ، من يملك Hashtable.
بعض الخلفية التاريخية أكثر على Hashtable يمكن ايجاده هنا (... بالقرب من النهاية: "بعد هذا التحويل الطويل - ماذا عن الهاشت؟").

لماذا Dictionary<TKey, TValue> يفشل في الحالة أعلاه:

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

this.buckets = newBuckets;
//One of the problems here.
this.entries = newEntries;

ال buckets الصفيف يحمل فهارس في entries مجموعة مصفوفة. دعنا نقول أن لدينا 10 إدخالات حتى الآن والآن نضيف جديدًا.
دعونا نتظاهر كذلك من أجل البساطة أننا لم نلاحق ولن نحصل على تصادمات.
في القديم buckets, ، كان لدينا فهارس تعمل من 0 إلى 9 - إذا لم يكن لدينا تصادمات.
الآن الفهارس في الجديد buckets صفيف يدير من 0 إلى 10 (!).
نحن الآن نغير القطاع الخاص buckets حقل للإشارة إلى الدلاء الجديدة.
إذا كان هناك قارئ يفعل TryGetValue() في هذه اللحظة ، يستخدم الجديد دلاء للحصول على الفهرس ، ولكن بعد ذلك يستخدم الجديد فهرس للقراءة في قديم صفيف الإدخالات ، منذ entries لا يزال الحقل يشير إلى الإدخالات القديمة.
أحد الأشياء التي يمكن للمرء الحصول عليها - إلى جانب القراءات الخاطئة - ودية IndexOutOfRangeException.
طريقة أخرى "رائعة" للحصول على هذا @هارونوت تفسير. (... وكلاهما يمكن أن يحدث ، على سبيل المثال كما في DTB مثال).

هذا هو في الحقيقة مجرد مثال واحد ، لم يتم تصميم المقدمة ولم يكن من المفترض أن يكون آمنًا للخيط. ومع ذلك ، فقد تم تصميمه ليكون سريعًا - وهذا يعني أن القفل لن يتم عقده لفترة طويلة.

Answer 5

بما في ذلك الرمز في السؤال ، يمكنك اختباره باستخدام الكود التالي.

//using System.Collections.Generic;
//using System.Threading;

private static volatile int numRunning = 2;
private static volatile int spinLock = 0;

static void Main(string[] args)
{
    new Thread(TryWrite).Start();
    new Thread(TryWrite).Start();
}

static void TryWrite()
{
    while(true) 
    {
        for (int i = 0; i < 1000000; i++ )
        {
            Create(i.ToString());
        }

        Interlocked.Decrement(ref numRunning);
        while (numRunning > 0) { } // make sure every thread has passed the previous line before proceeding (call this barrier 1)

        while (Interlocked.CompareExchange(ref spinLock, 1, 0) != 0){Thread.Sleep(0);} // Aquire lock (spin lock)
        // only one thread can be here at a time...

        if (numRunning == 0) // only the first thread to get here executes this...
        {
            numRunning = 2; // resets barrier 1
            // since the other thread is beyond the barrier, but is waiting on the spin lock,
            //  nobody is accessing the cache, so we can clear it...
            _cache = new Dictionary<string, object>(); // clear the cache... 
        }

        spinLock = 0; // release lock...
    }

}

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

System.Collections.Generic.Dictionary`2.FindEntry(TKey key)

يعد إضافة هذا الاختبار أمرًا صعبًا لأنه اختبار احتمالي ، ولا تعرف المدة التي سيستغرقها الفشل (إن وجدت). أعتقد أنه يمكنك اختيار قيمة مثل 10 ثوانٍ وتركها تعمل لفترة طويلة. إذا لم يفشل ذلك في هذا الوقت من الوقت ، فإن الاختبار يمر. ليس الأفضل ، ولكن شيء ما. يجب عليك أيضًا التحقق من ذلك Environment.ProcessorCount > 1 قبل إجراء الاختبار ، وإلا فإن احتمال فشله هو ضئيل.