لينكس 3.0:خطأ في حالة توقف تام لقفل Futex؟

Question

// SubFetch(x,y) = atomically x-=y and return x (__sync_sub_and_fetch)
// AddFetch(x,y) = atomically x+=y and return x (__sync_add_and_fetch)
// CompareWait(x, y) = futex(&x, FUTEX_WAIT, y) wait on x if x == y
// Wake(x, y) = futex(&x, FUTEX_WAKE, y) wake up y waiters

struct Lock
{
Lock() : x(1) {}

void lock()
{
    while (true)
    {
        if (SubFetch(x, 1) == 0)
            return;

        x = -1;

        CompareWait(x, -1);
    }
}

void unlock()
{
    if (AddFetch(x, 1) == 1)
        return;

    x = 1;

    Wake(x, 1);
}

private:
    int x;
};

يوفر Linux 3.0 مكالمة نظام تسمى com.futex, ، والتي تعتمد عليها العديد من أدوات التزامن المساعدة بما في ذلك تطبيقات pthread_mutex الحديثة.عندما تكتب تعليمات برمجية، يجب عليك دائمًا التفكير فيما إذا كان استخدام تطبيق موجود أو كتابته بنفسك هو الخيار الأفضل لمشروعك.

أعلاه هو تطبيق القفل (mutex، 1 تصريح عد الإشارة) بناءً على futex والوصف الدلالي في مان فيوتكس(7)

يبدو أنه يحتوي على خطأ في حالة توقف تام حيث بعد أن تحاول سلاسل رسائل متعددة قفله وفتحه بضعة آلاف من المرات، يمكن أن تصل سلاسل الرسائل إلى حالة حيث x == -1 وجميع سلاسل الرسائل عالقة في CompareWait، ولكن لا أحد يمسك بالمفتاح قفل.

يمكن لأي شخص أن يرى أين هو الخلل؟

تحديث: أنا مندهش قليلاً من أن futex(7)/الدلالات معطلة جدًا.لقد قمت بإعادة كتابة القفل بالكامل على النحو التالي ...هل هذا صحيح الآن؟

// CompareAssign(x,y,z) atomically: if (x == y) {x = z; ret true; } else ret false;

struct Lock
{
Lock() : x(0) {}

void lock()
{
    while (!CompareAssign(x, 0, 1))
        if (x == 2 || CompareAssign(x, 1, 2))
            CompareWait(x, 2);
}

void unlock()
{
    if (SubFetch(x, 1) == 0)
        return;

    x = 0;

    Wake(x, 1);
}

private:
int x;
};

الفكرة هنا هي أن x لها الحالات الثلاث التالية:

0: unlocked
1: locked & no waiters
2: locked & waiters

Answer 1

المشكلة هي أنك قمت بتعيين -1 بشكل صريح لـ x إذا SubFetch فشل في الحصول على القفل.هذا يتسابق مع الفتح.

1. الموضوع 1 يكتسب القفل. x==0.
2. يحاول الخيط 2 الحصول على القفل.ال SubFetch مجموعات x إلى -1، ثم يتم تعليق الخيط 2.
3. الموضوع 1 يطلق القفل.ال AddFetch مجموعات x إلى 0، لذلك يتم تعيين الكود بشكل صريح x إلى 1 والمكالمات Wake.
4. يستيقظ الخيط 2 ويضبط x إلى -1، ثم يستدعي CompareWait.

الموضوع 2 عالق الآن في الانتظار، مع x تم ضبطه على -1، ولكن لا يوجد أحد لإيقاظه، حيث أن الخيط 1 قد قام بالفعل بتحرير القفل.

Answer 2

التنفيذ السليم لموصف Mutex القائم على Futex في ورق Ulrich Drepper "Futexes صعبة"

http://people.redhat.com/drepper/futex.pdf

لا يتضمن الكود فقط ولكن أيضا شرح مفصل للغاية لماذا هو الصحيح.الرمز من الورق: giveacodicetagpre.

مقارنة التعليمات البرمجية في الورق مع التعليمات البرمجية الخاصة بك، وأنا اكتشف فرقا

لديك

إذا كان (x== 2 || مقارنة (x، 1، 2))

باستخدام قيمة Futex مباشرة، حيث يستخدم Driepper قيمة الإرجاع من المقارنة السابق ().هذا الفرق سيؤثر على الأداء فقط.

رمز إلغاء القفل الخاص بك هو مختلف، ولكن يبدو أنه معادل دلاجة.

على أي حال، أود أن أنصحك بشدة بمتابعة رمز Drepper بالرسالة.وقفت تلك الورقة اختبار الزمن واستلم الكثير من مراجعة النظراء.لا تكسب شيئا من المتداول بنفسك.

Answer 3

ماذا عن هذا السيناريو الذي يحتوي على ثلاثة خيوط، A وB وC.

الحالة الأولية لهذا السيناريو هي:

• الخيط أ يحمل القفل
• الخيط B لا يتنافس على القفل حتى الآن
• الخيط C في CompareWait()
• x == -1 منذ أن فشل C في الحصول على القفل

        A                  B                C
    ==============   ================  ===============
     AddFetch()
     (so x == 0)
                       SubFetch()
                       (so x == -1)

     x = 1

                       x = -1

     Wake()

في هذه المرحلة، سواء تم إلغاء حظر B أو C، فلن يحصلوا على نتيجة 0 عندما هم SubFetch().