مستكشف التداخلات: العثور على الأخطاء بتعداد الجداول

تجربة الجداول يدويًا لا تجد الخطأ إلا إن خمّنت الجدول الصحيح. يشغّل المستكشف البرنامج تحت كل الجداول ويسرد كل النتائج ويعطيك الجدول الذي كسره. وفي حالة خيطين يعدّان أيام صعود عشرة عوائد من SPY هناك 210 جدولًا لا يعطي العدّ الصحيح منها إلا 10.

الجدول ترتيب للأدوار والخيط t يأخذ منها lengths[t] بالضبط. لعدّ الترتيبات نضع كل الأدوار في صف (مجموع أطوالها) ويمكن ترتيبه بعدد من الطرق يساوي مضروب ذلك العدد؛ ثم نقسم على مضروب أدوار كل خيط لأن تبديل دورين من الخيط نفسه لا يعطي جدولًا جديدًا. هذا هو المعامل متعدد الحدود. ينمو بسرعة: لخيطين من دورين 6 جداول فقط ولثلاثة خيوط من ثلاثة أدوار 1680 ولخيطين من عشرة أدوار 184756. ولهذا لا يستطيع أحد فحص برنامج متزامن بتجربة جداول عشوائية والأمل.

def count_schedules(lengths):    total = factorial(sum(lengths))    for n in lengths:        total //= factorial(n)    return totalprint(count_schedules([2, 2]))print(count_schedules([3, 3, 3]))print(count_schedules([10, 10]))

6
1680
184756

في المختبر السابق كان الخيط قائمة خطوات. والشيفرة الحقيقية أفضل كتابتها بـPython عادية، لذا يصبح الخيط من الآن مولّدًا يأخذ القاموس المشترك وينفّذ yield قبل كل وصول إلى البيانات المشتركة. فاستدعاء واحد لـnext() يقدّم الخيط حتى وصوله التالي لا أبعد، وهكذا يكون الدور الواحد خطوة واحدة بالضبط يمكن لخيط آخر أن يتداخل معها. تهيّئ run_threads كل مولّد (تشغّله حتى أول yield) وتعطي دورًا للخيط الذي يسميه كل مدخل في الجدول وحين ينتهي الجدول تترك الخيوط غير المنتهية تكمل بترتيب الخيوط. وتسرد all_schedules كل ترتيبات الأدوار باختيار الخيط الذي يبدأ ثم التكرار على الباقي. أدناه الجداول الستة لخيطين يزيد كل منهما مرة واحدة.

def all_schedules(lengths):    if sum(lengths) == 0:        return [[]]    out = []    for tid, n in enumerate(lengths):        if n:            rest = list(lengths)            rest[tid] -= 1            out += [[tid] + tail for tail in all_schedules(rest)]    return outdef run_threads(make_threads, schedule, shared=None):    shared = dict(shared or {})    threads = make_threads(shared)    alive = [True] * len(threads)    def turn(tid):        try:            next(threads[tid])        except StopIteration:            alive[tid] = False    for tid in range(len(threads)):        turn(tid)    for tid in schedule:        if alive[tid]:            turn(tid)    while any(alive):        for tid in range(len(threads)):            if alive[tid]:                turn(tid)    return sharedtwo = lambda shared: [increments(1)(shared), increments(1)(shared)]for schedule in all_schedules([2, 2]):    print(schedule, run_threads(two, schedule))

[0, 0, 1, 1] {'x': 2}
[0, 1, 0, 1] {'x': 1}
[0, 1, 1, 0] {'x': 1}
[1, 0, 0, 1] {'x': 1}
[1, 0, 1, 0] {'x': 1}
[1, 1, 0, 0] {'x': 2}

تنتهي اثنتان من الجداول الستة عند 2 والأربعة الأخرى عند 1. الجيدان هما ما ينفّذ فيه خيط خطوتيه قبل أن يبدأ الآخر. وفي الأربعة الأخرى يقرأ الخيطان قبل أن يكتب أيٌّ منهما وهذا بالضبط التحديث الضائع من المختبر السابق وقد وُجد الآن دون تخمين.

تشغّل explore البرنامج تحت كل الجداول وتعدّ كم جدولًا يعطي كل حالة نهائية. المفتاح هو صف مرتّب من أزواج (الاسم، القيمة) لتكون الحالات المتساوية المفتاح نفسه. وتطرح find_schedule سؤال تقرير الخطأ: أي جدول يكسر ثابتي؟ تعيد الأول وبما أن run_threads حتمية يمكنك إعادة تشغيله أو طباعته أو لصقه في اختبار. وإن أعادت None فالثابت صحيح تحت كل الجداول وهذا إثبات لهذا البرنامج الصغير لا أمل.

def explore(make_threads, lengths, shared=None):    outcomes = {}    for schedule in all_schedules(lengths):        key = tuple(sorted(run_threads(make_threads, schedule, shared).items()))        outcomes[key] = outcomes.get(key, 0) + 1    return outcomesdef find_schedule(make_threads, lengths, check, shared=None):    for schedule in all_schedules(lengths):        if not check(run_threads(make_threads, schedule, shared)):            return schedule    return Noneprint(explore(two, [2, 2]))print(find_schedule(two, [2, 2], lambda shared: shared["x"] == 2))

{(('x', 2),): 2, (('x', 1),): 4}
[0, 1, 0, 1]

returns = [float(r) for r in load_bars()["close"].pct_change().dropna()][:10]ups = [sum(1 for r in returns[start::2] if r > 0) for start in (0, 1)]lengths = [2 * k for k in ups]many = lambda shared: [increments(k)(shared) for k in ups]print(ups, count_schedules(lengths))print({dict(key)["x"]: n for key, n in explore(many, lengths).items()})

[2, 3] 210
{5: 10, 4: 70, 3: 104, 2: 26}

الجواب الصحيح x = 5 يظهر في 10 جداول فقط من 210 أي نحو 5%. اختبار يشغّل البرنامج مرة أو مئة مرة على جهاز حقيقي لا يتداخل فيه الخيطان هكذا إلا نادرًا سيمرّ تقريبًا في كل مرة ومع ذلك يُسلَّم بخطأ. والمستكشف لا يفوّته وfind_schedule تعطيك أول مذنب: [0, 0, 0, 1, 0, 1, 1, 1, 1, 1].

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

• الدالة · السؤالتعتمد على
• count_schedules(lengths)كم جدولًا للبرنامج؟حساب بسيط
• all_schedules(lengths)ما هي بالترتيب؟حساب بسيط
• run_threads(make_threads, schedule, shared)ماذا يترك جدول واحد؟حساب بسيط
• explore(make_threads, lengths, shared)ما النتائج الموجودة وكم مرة؟all_schedulesrun_threads
• find_schedule(make_threads, lengths, check)أي جدول يكسر الثابت أولًا؟all_schedulesrun_threads
• study(bars)كم جدولًا من عدّ SPY يفشل؟count_schedulesexplorefind_schedule

الموضوع التالي: يُظهر المستكشف أن الخطأ حقيقي؛ والآن نصلحه. يضيف الذرّيات والقراءة والتعديل والكتابة العمليات التي يستطيع المعالج تنفيذها في خطوة واحدة غير قابلة للتجزئة مثل fetch-and-add وcompare-and-swap وتتحقق بالمستكشف أن العدّاد صحيح تحت كل الجداول.