حالات التسابق ولماذا توجد الأقفال

يضيف خيطان 1 إلى العدّاد نفسه فينتهي العدّاد خاطئًا دون خطأ أو انهيار. السطر x += 1 ليس خطوة واحدة بل ثلاث، وترتيب تداخل الخيطين لهذه الخطوات هو ما يحدد الجواب. على 1085 يوم صعود لـSPY تضيع 542 تحديثًا ويعيدها القفل كلها.

لا يستطيع المعالج أن يجمع إلى قيمة موجودة في الذاكرة. إنه يحمّل القيمة في مسجّل ويضيف إلى المسجّل ثم يخزّن المسجّل في الذاكرة. إذن x += 1 هي load x ثم add 1 ثم store x. الخيط الواحد ينفذ الثلاث متتابعة ولا شيء يسوء. ومع خيطين قد تنفذ الآلة خطوة من أحدهما ثم خطوة من الآخر بأي ترتيب. لنرى ذلك نكتب آلة صغيرة. الخيط قائمة خطوات لكل خيط مسجّله الخاص، وتتشارك الخيوط قاموسًا من القيم المسمّاة. تنفّذ الدالة execute خطوة واحدة من خيط. نلعب أدناه الخطوات الست لخيطين يدويًا، خطوة لكل خيط بالتناوب.

def execute(op, shared, regs, locks, tid):    kind = op[0]    if kind == "load":        regs[tid] = shared.get(op[1], 0)    elif kind == "add":        regs[tid] += op[1]    elif kind == "store":        shared[op[1]] = regs[tid]    elif kind == "lock":        if op[1] in locks:            return False        locks[op[1]] = tid    elif kind == "unlock":        del locks[op[1]]    return Trueshared, regs, locks = {"x": 0}, {0: 0, 1: 0}, {}turns = [(0, 0), (1, 0), (0, 1), (1, 1), (0, 2), (1, 2)]1for tid, step in turns:    execute(INCREMENT[step], shared, regs, locks, tid)    print("thread", tid, INCREMENT[step], "->", shared, regs)

thread 0 ('load', 'x') -> {'x': 0} {0: 0, 1: 0}
thread 1 ('load', 'x') -> {'x': 0} {0: 0, 1: 0}
thread 0 ('add', 1) -> {'x': 0} {0: 1, 1: 0}
thread 1 ('add', 1) -> {'x': 0} {0: 1, 1: 1}
thread 0 ('store', 'x') -> {'x': 1} {0: 1, 1: 1}
thread 1 ('store', 'x') -> {'x': 1} {0: 1, 1: 1}

1. 1يحمّل الخيطان قبل أن يخزّن أي منهما: يحمل كل مسجّل 0.

اقرأ المخرجات سطرًا سطرًا. يحمّل الخيط 0 القيمة 0 ويحمّل الخيط 1 القيمة 0 أيضًا (لم يخزّن الخيط 0 بعد) ويضيف كلاهما 1 إلى مسجّل فيه 0 ويخزّن كلاهما 1. نفّذ كل خيط x += 1 ومع ذلك قيمة x هي 1 لا 2. ضاع تحديث. لا خطأ في شيفرة أي من الخيطين؛ الخطأ موجود في هذا الترتيب للخطوات فقط.

في العالم الحقيقي يختار نظام التشغيل الجدول ويتغير من تشغيل إلى آخر، ولهذا يصعب تكرار حالة التسابق. وفي آلتنا نحن من يختاره. الجدول قائمة من أرقام الخيوط وrun تعطي الخيط الذي يسميه كل مدخل دورًا واحدًا. يهم جدولان بسيطان. في الجدول التسلسلي ينفذ الخيط 0 كل خطواته ثم الخيط 1: وهو ما نأمله. وفي جدول الدور الدائري يأخذ كل خيط خطوة بالتناوب: وهو أسوأ حالة لعدّادنا لأن خطوات الخيطين تتداخل في كل مكان. تقارن الدالة lost_updates ما كان على الزيادات أن تضيفه بما يعرضه العدّاد.

def run(programs, schedule, shared=None):    shared = dict(shared or {})    regs = {tid: 0 for tid in range(len(programs))}    pcs = [0] * len(programs)    locks = {}    for tid in schedule:        if pcs[tid] < len(programs[tid]) and execute(programs[tid][pcs[tid]], shared, regs, locks, tid):            pcs[tid] += 1    while any(pcs[t] < len(programs[t]) for t in range(len(programs))):        progress = False        for tid in range(len(programs)):            if pcs[tid] < len(programs[tid]) and execute(programs[tid][pcs[tid]], shared, regs, locks, tid):                pcs[tid] += 1                progress = True        if not progress:            raise RuntimeError("deadlock")    return shareddef serial_schedule(programs):    return [tid for tid, program in enumerate(programs) for _ in program]def round_robin_schedule(programs):    longest = max((len(program) for program in programs), default=0)    return [tid for step in range(longest) for tid, program in enumerate(programs) if step < len(program)]def lost_updates(programs, schedule, name="x"):    expected = sum(op[1] for program in programs for op in program if op[0] == "add")    return expected - run(programs, schedule).get(name, 0)two = [INCREMENT, INCREMENT]print(serial_schedule(two), run(two, serial_schedule(two)))print(round_robin_schedule(two), run(two, round_robin_schedule(two)))print("lost:", lost_updates(two, round_robin_schedule(two)))

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

يعطي الجدول التسلسلي [0, 0, 0, 1, 1, 1] القيمة 2؛ ويعطي جدول الدور الدائري [0, 1, 0, 1, 0, 1] القيمة 1 ويضيّع تحديثًا. لاحظ ما تفعله run حين ينتهي الجدول مبكرًا: تواصل الخيوط غير المنتهية أخذ الأدوار خطوة لكل خيط بترتيب الخيوط، فيكتمل كل برنامج دائمًا. ولاحظ أن الخيط المنتهي يتجاهل أدواره، فأي قائمة من أرقام الخيوط جدول صالح.

يعالج القفل حالة التسابق بمنع التداخل. يأخذ الخيط القفل قبل load ويحرّره بعد store. والخيط الثاني الذي يطلب القفل في هذه الأثناء لا يحصل عليه: دوره لا يفعل شيئًا ويبقى عند الخطوة نفسها حتى يتحرر القفل. فتعمل الخطوات بين lock وunlock ككتلة واحدة ولا يستطيع خيط آخر التسلل بينها. تبني الدالة counter_program برنامج خيط يزيد عدّادًا بالقفل أو بدونه. وتجلب الأقفال خطرًا جديدًا يظهر في آخر الشيفرة: خيطان يأخذان قفلين بترتيبين متعاكسين قد يمسك كل منهما القفل الذي يحتاجه الآخر ولا يستطيع أحدهما التقدم أبدًا. هذا هو الجمود، وتكشفه run حين لا يحقق مرور كامل أي تقدم.

def counter_program(increments, locked=False):    program = []    for _ in range(increments):        program += ([("lock", "m")] if locked else []) + INCREMENT + ([("unlock", "m")] if locked else [])    return programsafe = [counter_program(1, locked=True), counter_program(1, locked=True)]print(counter_program(1, locked=True))print(run(safe, round_robin_schedule(safe)))ab = [[("lock", "a"), ("lock", "b"), ("unlock", "b"), ("unlock", "a")],      [("lock", "b"), ("lock", "a"), ("unlock", "a"), ("unlock", "b")]]try:    run(ab, [0, 1])except RuntimeError as error:    print("error:", error)

[('lock', 'm'), ('load', 'x'), ('add', 1), ('store', 'x'), ('unlock', 'm')]
{'x': 2}
error: deadlock

def study(bars):    returns = [float(r) for r in bars["close"].pct_change().dropna()][:2000]    ups = [sum(1 for r in returns[start::2] if r > 0) for start in (0, 1)]    free = [counter_program(k) for k in ups]    locked = [counter_program(k, locked=True) for k in ups]    return {"up": sum(ups),            "serial": run(free, serial_schedule(free))["x"],            "racy": run(free, round_robin_schedule(free))["x"],            "locked": run(locked, round_robin_schedule(locked))["x"]}print(study(load_bars()))

{'up': 1085, 'serial': 1085, 'racy': 543, 'locked': 1085}

بلا قفل يُبقي جدول الدور الدائري الخيطين على بُعد خطوة واحدة فيحمّلان القيمة نفسها دائمًا ويُحتسب كل زوج من الزيادات مرة واحدة: يضيع نحو نصف أيام الصعود الـ1085. ويعيد القفل المجموع الدقيق بثمن إجبار خيط على الانتظار.

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

• الدالة · السؤالتعتمد على
• execute(op, shared, regs, locks, tid)ماذا تفعل خطوة واحدة وهل يجب أن ينتظر الخيط؟حساب بسيط
• run(programs, schedule, shared)ماذا تتركه الخيوط تحت هذا الجدول؟execute
• serial_schedule(programs)خيط بعد آخر؟حساب بسيط
• round_robin_schedule(programs)خطوة لكل خيط بالتناوب؟حساب بسيط
• lost_updates(programs, schedule)كم زيادة تختفي؟run
• counter_program(increments, locked)ماذا يفعل خيط العدّ؟حساب بسيط
• study(bars)كم تحديثًا تكلّف حالة التسابق على SPY؟counter_programrunlost_updates

الموضوع التالي: وجدت التحديث الضائع باختيار جدول يدويًا. لبرنامج حقيقي جداول أكثر من أن تُجرَّب يدويًا. في مستكشف التداخلات تعدّد كل جداول برنامج صغير وتعدّ التي تكسره وتحتفظ بالمستكشف أداةً لبقية المهارة.