مشكلة ABA والمؤشرات الموسومة

تسأل المقارنة والتبديل «هل القيمة ما زالت كما قرأتها؟» ولا تستطيع أن تسأل «هل تغيّرت ثم عادت؟». وفي مكدس بلا أقفال هذه البقعة العمياء هي مشكلة ABA: ينجح تبديل على تصوّر قديم للمكدس ويعيد قيمة مرتين. من 3021 جدولًا لسحب واحد أمام خيط يقلّب المكدس تُفسد 21 منها المكدس العادي ولا يُفسد أيٌّ منها المكدس الموسوم.

يحتفظ المكدس بلا أقفال بعقده في القاموس المشترك: للعقدة i قيمة val{i} ورابط next{i} إلى العقدة التي تحتها ويسمّي head القمة (-1 للفارغ). لدفع عقدة نقرأ الرأس ونوجّه رابط العقدة الجديدة إليه ونبدّل الرأس من القيمة المقروءة إلى العقدة الجديدة؛ وإن فشل التبديل فقد غيّر أحد الرأس فنبدأ من جديد. ولسحب عقدة نقرأ الرأس ونقرأ رابط عقدة القمة وقيمتها ونبدّل الرأس من العقدة المقروءة إلى رابطها. والسحب الفائز يسجّل قيمته في popped. كل عملية مكدس مولّد ويشغّلها الخيط بـyield from الذي يعيد أيضًا القيمة المرجعة.

def make_stack(values, tagged=False):    top = 0 if values else -1    shared = {"head": (top, 0) if tagged else top, "popped": ()}    for i, value in enumerate(values):        shared["val%d" % i] = value        shared["next%d" % i] = i + 1 if i + 1 < len(values) else -1    return shareddef push(shared, node, value, tagged=False):    shared["val%d" % node] = value    while True:        yield        old = shared["head"]        yield        shared["next%d" % node] = old[0] if tagged else old        yield        new = (node, old[1] + 1) if tagged else node        if compare_and_swap(shared, "head", old, new):            returndef pop(shared, tagged=False):    while True:        yield        old = shared["head"]        idx = old[0] if tagged else old        if idx == -1:            return None        yield        nxt = shared["next%d" % idx]        value = shared["val%d" % idx]        yield        new = (nxt, old[1] + 1) if tagged else nxt        if compare_and_swap(shared, "head", old, new):            shared["popped"] = shared["popped"] + (value,)            return valuedef alone(shared):    def thread():        for _ in range(3):            print("popped", (yield from pop(shared)))    return [thread()]final, alive = run_prefix(alone, [0] * 20, make_stack([10, 20]))print(final["head"], final["popped"])

popped 10
popped 20
popped None
-1 (10, 20)

وحدها تكون المكدس مكدسًا عاديًا: تعيد عمليات السحب 10 ثم 20 ثم None ويعود الرأس إلى -1. كل شيء يتوقف على ما يحدث حين يعمل خيط آخر بين قراءات السحب الثلاث وتبديله.

هذا هو الفخ. يبدأ خيط ضحية سحبًا: يقرأ head = 0 (العقدة A) والرابط next0 = 1 (العقدة B) ويتوقف قبل تبديله. ثم يسحب خيط مقلِّب A ويسحب B ويدفع العقدة 0 من جديد بقيمة جديدة 99 فيصير head يساوي 0 ثانية ولا شيء تحته. تستيقظ الضحية. لا تسأل المقارنة والتبديل عندها إلا هل ما زال head يساوي 0 وهو كذلك فينجح التبديل ويثبّت العقدة 1 رأسًا وهي عقدة لم تعد في المكدس. نتبع الجدول [0, 0] ثم تسعة أدوار للمقلّب ثم الضحية ونفحص النتيجة بـconserved: يجب أن تكون القيم المسحوبة مع القيم المتبقية في المكدس هي القيم التي وُضعت بالضبط.

def walk(shared, tagged=False):    values = []    idx = shared["head"][0] if tagged else shared["head"]    while idx != -1 and len(values) < 10:        values.append(shared["val%d" % idx])        idx = shared["next%d" % idx]    return valuesdef conserved(shared, expected, tagged=False):    return sorted(list(shared["popped"]) + walk(shared, tagged)) == sorted(expected)def aba_program(tagged=False):    def make_threads(shared):        def victim():            yield from pop(shared, tagged)        def churner():            yield from pop(shared, tagged)            yield from pop(shared, tagged)            yield from push(shared, 0, 99, tagged)        return [victim(), churner()]    return make_threadsprefix = [0, 0] + [1] * 9 + [0]final, alive = run_prefix(aba_program(), prefix, make_stack([10, 20]))print(final)print("still on the stack:", walk(final), "| conserved:", conserved(final, [10, 20, 99]))

{'head': 1, 'popped': (10, 20, 10), 'val0': 99, 'next0': -1, 'val1': 20, 'next1': -1}
still on the stack: [20] | conserved: False

أعادت الضحية 10 الذي كان المقلّب قد سحبه (popped: (10, 20, 10)) والرأس هو العقدة 1 مع أن القيمة 20 سُحبت أيضًا فهي في المكدس وفي popped معًا وتضيع القيمة الجديدة 99. تقول conserved إنها False. تحديث ضائع وقيمة مكررة وعقدة ما كان ينبغي أن توجد: كل ذلك من تبديل «صحيح» بالنسبة للقيمة التي قارنها.

الإصلاح هو أن يحمل الرأس تاريخه. في نسخة المؤشر الموسوم يكون head زوجًا (العقدة، الوسم) ويبدّله كل دفع أو سحب ناجح بـ(العقدة الجديدة، الوسم + 1). تقارن المقارنة والتبديل الآن الحقلين معًا فالرأس (0, 3) الذي تركه المقلّب ليس (0, 0) الذي قرأته الضحية. يفشل تبديل الضحية فتعدّ محاولة معادة وتقرأ المكدس الحقيقي وتسحب 99. الجدول نفسه مع الوسم ينتهي صحيحًا.

final, alive = run_prefix(aba_program(True), prefix, make_stack([10, 20], True))print(final["head"], "victim alive:", alive == [0])final, alive = run_prefix(aba_program(True), prefix + [0] * 6, make_stack([10, 20], True))print(final["popped"], walk(final, True), "| conserved:", conserved(final, [10, 20, 99], True))

(0, 3) victim alive: True
(10, 20, 99) [] | conserved: True

values = [int(round(float(c) * 100)) for c in load_bars()["close"].iloc[:2]]for tagged in (False, True):    outcomes = explore_all(aba_program(tagged), make_stack(values, tagged))    corrupt = sum(n for key, n in outcomes.items() if not conserved(dict(key), values + [99], tagged))    print("tagged" if tagged else "plain ", sum(outcomes.values()), "schedules,", corrupt, "corrupt")

plain  3021 schedules, 21 corrupt
tagged 3021 schedules, 0 corrupt

واحد وعشرون جدولًا من 3021 أقل من 1%. قد يعمل اختبار إجهاد على جهاز حقيقي أيامًا دون أن يصطدم بأيٍّ منها ثم يفشل مرة في الإنتاج. يسردها المستكشف كلها ويزيلها الوسم كلها.

يتبع المختبر الدرس: المكدس في القاموس المشترك وpush وpop بحلقة مقارنة وتبديل (عادي وموسوم) وعبور للمكدس وفحص الحفظ وبرنامج ABA لضحية ومقلّب ودراسة المكدسين على كل الجداول بإغلاقين لـSPY.

• الدالة · السؤالتعتمد على
• make_stack(values, tagged)كيف يبدو المكدس المشترك؟حساب بسيط
• push(shared, node, value, tagged)كيف تُدفع عقدة؟حساب بسيط
• pop(shared, tagged)كيف تُسحب قيمة؟حساب بسيط
• walk(shared, tagged)ماذا في المكدس؟حساب بسيط
• conserved(shared, expected, tagged)هل ضاع شيء أو تكرر؟walk
• aba_program(tagged)كيف يبدو فخ ABA؟poppush
• study(bars)كم جدولًا ينقذه الوسم؟make_stackaba_programconserved

الموضوع التالي: للمكدس رأس واحد. أما الطابور فله طرفان وخيوط كثيرة عند كل منهما. طوابير متعددة المنتجين والمستهلكين تبني طابورًا محدودًا يحجز فيه المنتجون والمستهلكون تذكرة بـfetch-and-add وتحمل كل خانة رقم تسلسل ويتحقق المستكشف منه على كل الجداول.