مشروع ختامي: توزيع بيانات سوق بلا أقفال مع إثبات ثوابته

المشروع الختامي هو توزيع: منتج واحد ينشر نقرات SPY وعدة مستهلكين يقرأ كل منهم جميعها بلا أي قفل. كل ما بنيته يلتقي هنا. ذيل لا يحرّكه إلا المنتج ومؤشر خاص لكل مستهلك فلا يتنازع أحد وترتيب كتابة يقرر ما يستطيع القارئ رؤيته ومستكشف يحوّل «يبدو أنه يعمل» إلى عبارة عن كل جدول.

الخلاصة سجل لا ينمو إلا. الموضع p يحمل tick<p> ويقول tail كم موضعًا نُشر. لا يكتب النقرات والذيل إلا المنتج فلا شيء يُتنازع عليه من جهته. ولكل مستهلك مؤشر هو الموضع التالي الذي سيقرؤه ولا يكتبه أحد غيره. هذه كل حيلة التوزيع: لا يكتب المستهلكون شيئًا يقرؤه الآخرون فإضافة مستهلك لا تكلّف غيره شيئًا. الحقيقة المشتركة الوحيدة هي الذيل والسؤال الوحيد هو بأي ترتيب يكتب المنتج النقرة ويحرّك الذيل. إن حرّكه بعد البيانات وجد القارئ الذي يرى الذيل الجديد البيانات. وإن حرّكه قبلها قد يرى القارئ موضعًا لم يُكتب بعد.

def publish(shared, tick, safe=True):    if safe:        yield        pos = shared["tail"]        shared["tick%d" % pos] = tick        shared["put%d" % pos] = tick        yield        shared["tail"] = pos + 1    else:        yield        pos = shared["tail"]        shared["tail"] = pos + 1        yield        shared["tick%d" % pos] = tick        shared["put%d" % pos] = tickfor safe in (True, False):    shared, _ = run_prefix(lambda sh: [publish(sh, 9369, safe)], [0], make_feed(1))    print("safe  " if safe else "unsafe", "after one turn:", {k: v for k, v in shared.items() if k in ("tail", "tick0")})

safe   after one turn: {'tail': 0, 'tick0': 9369}
unsafe after one turn: {'tail': 1}

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

def poll(shared, c):    yield    tail = shared["tail"]    yield    pos = shared["cur%d" % c]    if pos >= tail:        return None    value = shared.get("tick%d" % pos)    shared["cur%d" % c] = pos + 1    shared["got%d_%d" % (c, pos)] = value    return valueready = dict(make_feed(1), tail=1)shared, alive = run_prefix(lambda sh: [poll(sh, 0)], [0, 0], ready)print("tail is 1 but tick0 was never written:", {k: v for k, v in shared.items() if k.startswith(("cur", "got"))})

tail is 1 but tick0 was never written: {'cur0': 1, 'got0_0': None}

ماذا يعني «صحيح» للتدفق؟ ثلاث عبارات عن الحالة النهائية. ممزق: كل نقرة استلمها مستهلك تساوي النقرة الموضوعة في ذلك الموضع (نقرة غائبة استُلمت None ممزقة). فجوة: استلم كل مستهلك المواضع 0 و1 و2 ... بلا ثقب. تجاوز: لا مؤشر يتجاوز الذيل. يستكشف verify كل جدول لمنتج ومستهلكين ويعدّ الجداول التي تكسر كلًّا منها. المستكشف هو الدليل: لا يستطيع أخذ عينة من التشغيل المحظوظ الواحد بل يزورها كلها.

def violations(final):    puts = {int(key[3:]): value for key, value in final.items() if key.startswith("put")}    gots = {}    for key, value in final.items():        if key.startswith("got"):            c, p = key[3:].split("_")            gots[(int(c), int(p))] = value    broken = []    if any(value != puts.get(p) for (c, p), value in gots.items()):        broken.append("torn")    for c in {c for c, _ in gots}:        if sorted(p for cc, p in gots if cc == c) != list(range(sum(1 for cc, _ in gots if cc == c))):            broken.append("gap")            break    if any(key.startswith("cur") and value > final["tail"] for key, value in final.items()):        broken.append("overrun")    return sorted(broken)def verify(ticks, polls, safe=True):    outcomes = explore_all(feed_threads(ticks, polls, safe), make_feed(len(polls)))    broken = {}    delivered = 0    for key, count in outcomes.items():        final = dict(key)        delivered = max(delivered, sum(1 for k in final if k.startswith("got")))        for name in violations(final):            broken[name] = broken.get(name, 0) + count    return {"schedules": sum(outcomes.values()), "broken": dict(sorted(broken.items())), "delivered": delivered}ticks = [9369, 9305]print("safe  ", verify(ticks, (2, 1), True))print("unsafe", verify(ticks, (2, 1), False))

safe   {'schedules': 3150, 'broken': {}, 'delivered': 3}
unsafe {'schedules': 3150, 'broken': {'torn': 869}, 'delivered': 3}

البرنامج نفسه و3150 جدولًا وتبديل ترتيب سطرين فقط يحوّل «لا شيء مكسور» إلى 869 مكسورًا. معظمها جداول لن تصادفها بضعة آلاف من تشغيلات الاختبار تقريبًا. هذه حجة الاستكشاف بدل الاختبار وهي المهارة كلها في جدول واحد: نموذج صغير بما يكفي للتعداد ومدقق للثوابت وحكم على كل جدول.

يتبع المختبر الدرس: التدفق الفارغ والمنتج بترتيبيه واستطلاع المستهلك ومدقق الثوابت الثلاثة والمدقق الذي يستكشف كل الجداول وإعادة تشغيل هادئ يستلم فيه كل مستهلك النقرات بالترتيب والدراسة على إغلاقات SPY.

• الدالة · السؤالتعتمد على
• make_feed(consumers)ما المشترك؟حساب بسيط
• publish(shared, tick, safe)البيانات أولًا أو الذيل أولًاحساب بسيط
• poll(shared, c)النقرة التالية للمستهلك cحساب بسيط
• violations(final)أي الثوابت انكسرت؟حساب بسيط
• verify(ticks, polls, safe)هل التدفق صحيح تحت كل الجداول؟explore_allviolations
• drain(ticks, polls)ماذا يستلم كل مستهلك؟run_prefix
• study(bars)آمن وغير آمن وهادئ على SPYverifydrain

بهذا تكتمل مهارة البرمجة بلا أقفال. صرت تستطيع بناء القطع (الذرّيات وcompare-and-swap والمكدسات والطوابير) وتسمية الأخطار (التسابقات وABA والاسترجاع) وقبل كل شيء فحص تصميم على كل جدول بدل الوثوق بتشغيل نجح مصادفة. والخطوة التالية هي الانضباط نفسه على عتاد حقيقي في مواضيع ذرّيات C++.