الذرّيات والقراءة والتعديل والكتابة

يحدث التحديث الضائع لأن القراءة والكتابة دوران بينهما فجوة. العملية الذرّية تسد الفجوة: القراءة والتعديل والكتابة في خطوة واحدة غير قابلة للتجزئة. وبها يصح العدّاد تحت كل الجداول: 4 جداول بدل 28 ولا خطأ في أيٍّ منها.

في آلتنا يمتد الدور من yield إلى التالي فلا يمكن تداخل أي شيء مكتوب بين yield واحد وآخر. لذا تتصرف الدالة التي لا تحوي yield كـعملية ذرّية. وأشهرها fetch-and-add: تقرأ القيمة القديمة وتكتب old + n وتعيد old كل ذلك في دور واحد. فيخطو خيط العدّ الذي يستدعيها yield واحدًا للزيادة كلها بدل اثنين فلا يستطيع الخيطان بعد الآن قراءة القيمة القديمة نفسها.

def fetch_add(shared, name, n):    old = shared.get(name, 0)    shared[name] = old + n    return olddef atomic_increments(k):    def thread(shared):        for _ in range(k):            yield            fetch_add(shared, "x", 1)    return threadtwo = lambda shared: [atomic_increments(1)(shared), atomic_increments(1)(shared)]for prefix in ([0, 1], [1, 0]):    print(prefix, run_prefix(two, prefix))

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

ينتهي الترتيبان عند {'x': 2} ولا يبقى خيط حيّ. مع دور واحد لكل زيادة لا يملك البرنامج إلا الجدولين [0, 1] و[1, 0] (4 في الدراسة لزيادة واحدة وثلاث زيادات) ولا يستطيع أي منهما تضييع تحديث.

يقتصر fetch-and-add على الجمع. ولما عداه تحتاج الأداة العامة المقارنة والتبديل (CAS). النمط حلقة: اقرأ القيمة القديمة واحسب الجديدة منها واطلب من CAS تثبيتها فقط إن لم يغيّر أحد القيمة في هذه الأثناء. فإن فشل CAS فقد سبقك أحد فتقرأ من جديد وتعيد المحاولة. أدناه عدّادان بـCAS: حين يقرأ الخيط 1 قبل أن يكتب الخيط 0 يفشل CAS عنده مرة ويعدّ محاولة معادة وتنجح المحاولة الثانية. لا يضيع التحديث أبدًا لأن الكتابة القديمة تُرفض.

def compare_and_swap(shared, name, expected, new):    if shared.get(name, 0) != expected:        return False    shared[name] = new    return Truedef cas_increments(k):    def thread(shared):        for _ in range(k):            while True:                yield                old = shared.get("x", 0)                yield                if compare_and_swap(shared, "x", old, old + 1):                    break                fetch_add(shared, "retries", 1)    return threadcas = lambda shared: [cas_increments(1)(shared), cas_increments(1)(shared)]print(run_prefix(cas, [0, 1, 0, 1]))print(run_prefix(cas, [0, 1, 0, 1, 1, 1]))

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

بعد [0, 1, 0, 1] يكون القاموس المشترك {'x': 1, 'retries': 1} والخيط 1 ما زال حيًّا: قرأ 0 لكن الخيط 0 كان قد خزّن 1 فرُفضت مقارنته وتبديله. وبإعطاء الخيط 1 دوريه التاليين (قراءة جديدة وتبديل جديد) ينتهي عند x = 2. لاحظ الثمن: الخاسر أنجز العمل مرتين. لا يعيد fetch-and-add المحاولة أبدًا؛ أما CAS فيعيدها بقدر تصادم الخيوط.

افترض مستكشف الموضوع السابق أن لكل خيط عددًا ثابتًا من الأدوار هو lengths. وتكسر حلقة إعادة المحاولة ذلك: الخيط الذي يخسر سباقًا يأخذ أدوارًا إضافية وعددها يتوقف على الجدول. الحل أن نبحث في الجداول كشجرة. من بادئة من الأدوار تعيد run_prefix تشغيل البرنامج وتخبر أي الخيوط ما زالت حية؛ فإن لم يبق أحد فالجدول كامل وتُحتسب حالته النهائية وإلا تفرّعنا على كل منها. يزور هذا البحث بالعمق أولًا كل جدول كامل مرة واحدة بالضبط. ثم تقرأ values_of اسمًا مشتركًا واحدًا من كل النتائج.

def explore_all(make_threads, shared=None):    outcomes = {}    def visit(prefix):        final, alive = run_prefix(make_threads, prefix, shared)        if not alive:            key = tuple(sorted(final.items()))            outcomes[key] = outcomes.get(key, 0) + 1            return        for tid in alive:            visit(prefix + [tid])    visit([])    return outcomesdef values_of(outcomes, name):    return sorted({dict(key).get(name, 0) for key in outcomes})print(explore_all(cas))racy = lambda shared: [increments(1)(shared), increments(1)(shared)]print(values_of(explore_all(racy), "x"), values_of(explore_all(cas), "x"))

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

returns = [float(r) for r in load_bars()["close"].pct_change().dropna()][:6]ups = [sum(1 for r in returns[start::2] if r > 0) for start in (0, 1)]for name, factory in (("racy", increments), ("atomic", atomic_increments), ("cas", cas_increments)):    outcomes = explore_all(lambda shared, f=factory: [f(k)(shared) for k in ups])    print(name, sum(outcomes.values()), "schedules, x in", values_of(outcomes, "x"))

racy 28 schedules, x in [1, 2, 3, 4]
atomic 4 schedules, x in [4]
cas 144 schedules, x in [4]

الإصلاحان صحيحان تحت كل الجداول ويختلفان في الكلفة. يؤدي fetch-and-add العمل بدور واحد لكل زيادة: 4 جداول. وللعدّاد بـCAS 144 جدولًا لأن التصادم يضيف أدوارًا وفي أسوئها يعيد خيط المحاولة 3 مرات. هذه مقايضة الشيفرة بلا أقفال: لا ينتظر أحد قفلًا لكن الفائز في كل سباق يجبر الخاسر على إعادة عمله.

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

• الدالة · السؤالتعتمد على
• fetch_add(shared, name, n)أضف n وما كان قبلًا؟حساب بسيط
• compare_and_swap(shared, name, expected, new)هل بقيت القيمة كما قرأتها؟حساب بسيط
• atomic_increments(k)عدّاد بلا فجوة؟fetch_add
• cas_increments(k)عدّاد يعيد المحاولة بدل أن يخسر؟compare_and_swapfetch_add
• explore_all(make_threads, shared)كل النتائج مهما كان عدد الأدوار؟run_prefix
• values_of(outcomes, name)ما القيم التي يتخذها هذا الاسم؟حساب بسيط
• study(bars)كيف تقارن العدّادات الثلاثة على SPY؟explore_allvalues_of

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