مخزن حلقي لمنتج واحد ومستهلك واحد

أبسط طابور بلا أقفال لا يحتاج إلى المقارنة والتبديل إطلاقًا. أعطِ كل موضع كاتبًا واحدًا: المنتج وحده يكتب الذيل والمستهلك وحده يكتب الرأس. قراءة قديمة لموضع الجانب الآخر آمنة دائمًا لذا يستطيع المخزن الحلقي تمرير تيكات بين خيطين دون قفل. يثبت المستكشف ذلك على 291 جدولًا ويُظهر انكساره في 458 من 1072 حين ينضم منتج ثانٍ.

يحتفظ المخزن الحلقي بعدّادين لا يزيدان إلا. يكتب المنتج الخانة tail % capacity ثم ينشر برفع tail؛ ويقرأ المستهلك الخانة head % capacity ثم يحررها برفع head. المخزن ممتلئ حين tail - head == capacity وفارغ حين head == tail. لماذا هو آمن بلا قفل؟ المنتج هو الكاتب الوحيد لـtail فيحتفظ بنسخة محلية منه. ويقرأ head ليبحث عن مكان وإن كانت القيمة قديمة فالرأس القديم أصغر من الحقيقي فيظن المنتج المخزن أملأ مما هو وأقصى ما يحدث أن يُسقط عنصرًا ولا يكتب فوق خانة لم تُقرأ أبدًا. وtail القديم عند المستهلك أصغر أيضًا فأقصى ما يحدث أن يرى المخزن فارغًا. هذا هو مبدأ الكاتب الواحد.

def initial_state():    return {"head": 0, "tail": 0, "pushed": (), "popped": ()}def ring_producer(items, capacity):    def thread(shared):        tail = 0        for item in items:            yield            head = shared.get("head", 0)            if tail - head < capacity:                yield                shared["slot%d" % (tail % capacity)] = item                yield                tail += 1                shared["tail"] = tail                shared["pushed"] = shared.get("pushed", ()) + (item,)    return threaddef ring_consumer(attempts, capacity):    def thread(shared):        head = 0        for _ in range(attempts):            yield            tail = shared.get("tail", 0)            if head != tail:                yield                item = shared.get("slot%d" % (head % capacity))                yield                head += 1                shared["head"] = head                shared["popped"] = shared.get("popped", ()) + (item,)    return threadtwo = lambda shared: [ring_producer((7, 8), 2)(shared), ring_consumer(2, 2)(shared)]for prefix in ([0, 0, 0], [0, 0, 0, 1, 1, 1], [0, 0, 0, 0, 0, 0, 1, 1, 1, 1]):    print(prefix, run_prefix(two, prefix, initial_state())[0])

[0, 0, 0] {'head': 0, 'tail': 1, 'pushed': (7,), 'popped': (), 'slot0': 7}
[0, 0, 0, 1, 1, 1] {'head': 1, 'tail': 1, 'pushed': (7,), 'popped': (7,), 'slot0': 7}
[0, 0, 0, 0, 0, 0, 1, 1, 1, 1] {'head': 1, 'tail': 2, 'pushed': (7, 8), 'popped': (7,), 'slot0': 7, 'slot1': 8}

ثلاثة أدوار للمنتج تدفع أول تيك: يقرأ الرأس ويخزّن العنصر في slot0 وينشر tail: 1. وبعد ثلاثة أدوار للمستهلك يصير head: 1 وpopped: (7,). وفي السطر الأخير دفع المنتج العنصرين (slot0: 7 وslot1: 8) وأخذ المستهلك الأول؛ والخيط 1 ما زال حيًّا لأن له محاولة أخرى.

ماذا يجب أن يعد الطابور؟ أمرين. العناصر المسحوبة هي العناصر المدفوعة بالترتيب نفسه ودون فجوات: popped بادئة من pushed (خاصية FIFO). ولا يُسحب ما لم يُدفع قط: len(popped) <= len(pushed). تسجّل الخيوط ما تدفعه وتسحبه في الدور نفسه الذي تنتهي فيه العملية فتستطيع violations فحص الأمرين على أي حالة نهائية. ثم تشغّل verify البرنامج كله تحت كل جدول بـexplore_all وتعدّ الجداول التي تكسر كل ثابت. قاموس broken فارغ عبر كل الجداول إثبات لهذا الحجم من البرنامج.

def violations(final):    pushed, popped = tuple(final.get("pushed", ())), tuple(final.get("popped", ()))    broken = []    if popped != pushed[: len(popped)]:        broken.append("order")    if len(popped) > len(pushed):        broken.append("count")    return sorted(broken)def verify(producers, attempts, capacity):    def make_threads(shared):        return [ring_producer(items, capacity)(shared) for items in producers] + [ring_consumer(attempts, capacity)(shared)]    outcomes = explore_all(make_threads, initial_state())    broken = {}    pushed = popped = 0    for key, count in outcomes.items():        final = dict(key)        pushed = max(pushed, len(final.get("pushed", ())))        popped = max(popped, len(final.get("popped", ())))        for name in violations(final):            broken[name] = broken.get(name, 0) + count    return {"schedules": sum(outcomes.values()), "broken": dict(sorted(broken.items())), "pushed": pushed, "popped": popped}print(violations({"pushed": (7, 8), "popped": (8,)}))print(verify([(7, 8)], 2, 2))print(verify([(7, 8)], 2, 1))

['order']
{'schedules': 101, 'broken': {}, 'pushed': 2, 'popped': 2}
{'schedules': 25, 'broken': {}, 'pushed': 2, 'popped': 2}

منتج بعنصرين في مخزن من خانتين يقرؤه مستهلك بمحاولتين له 101 جدول ولا يكسر أيٌّ منها ثابتًا. ومع مخزن من خانة واحدة يضطر المنتج إلى إسقاط عنصر حين يبطئ المستهلك لكنه يبقى صحيحًا: 25 جدولًا بلا أي انتهاك. أما القائمة المسحوبة (8,) بعد دفع (7, 8) فهي كما هو متوقع انتهاك للترتيب.

تستند حجة الأمان إلى حقيقة واحدة: tail له كاتب واحد. أضف منتجًا ثانيًا فيحتفظ كل من الخيطين بفكرته عن الذيل. يقرأ كلاهما head نفسه ويحسبان الخانة نفسها فتكتب الكتابة الثانية فوق الأولى. يجد المستكشف ذلك: 458 من 1072 جدولًا لمنتجين (تيك لكل منهما) تنتهي بـpopped ليس بادئة من pushed. والعلاج ليس رقعة لهذا المخزن بل بنية أخرى هي طابور متعدد المنتجين تبنيها المواضيع اللاحقة بالمقارنة والتبديل.

print(verify([(7,), (8,)], 2, 2))

{'schedules': 1072, 'broken': {'order': 458}, 'pushed': 2, 'popped': 1}

ticks = [int(round(float(c) * 100)) for c in load_bars()["close"].iloc[:4]]print(ticks)print("one producer: ", verify([ticks[:2]], 3, 2))print("two producers:", verify([ticks[:1], ticks[1:2]], 2, 2))

[9369, 9305, 9354, 9349]
one producer:  {'schedules': 291, 'broken': {}, 'pushed': 2, 'popped': 2}
two producers: {'schedules': 1072, 'broken': {'order': 458}, 'pushed': 2, 'popped': 1}

الدرس كله في رقمين: كاتب واحد لكل موضع يكفي للصحة على 291 جدولًا وكاتبان على الموضع نفسه يخطئان في 43% من 1072. لم يخمّن المستكشف بل شغّل كل التداخلات.

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

• الدالة · السؤالتعتمد على
• initial_state()كيف يبدو مخزن فارغ؟حساب بسيط
• ring_producer(items, capacity)كيف يدفع المنتج؟حساب بسيط
• ring_consumer(attempts, capacity)كيف يسحب المستهلك؟حساب بسيط
• violations(final)أي الثوابت يكسرها هذا الوضع؟حساب بسيط
• verify(producers, attempts, capacity)هل المخزن صحيح تحت كل الجداول؟explore_allviolations
• study(bars)ما الذي ينكسر مع منتج ثانٍ؟verify

الموضوع التالي: لحيلة الكاتب الواحد حدّ وللمقارنة والتبديل حدّ أيضًا. مشكلة ABA والمؤشرات الموسومة تبني مكدسًا بلا أقفال على المقارنة والتبديل وتُري جدولًا ينجح فيه التبديل رغم أن المكدس تغيّر من تحته وتصلحه بوسم إصدار.