نموذج الذاكرة: الاكتساب والإطلاق

للمعالج حرية تنفيذ قراءتين وكتابتين مستقلتين بأي ترتيب وقد ترى نواة أخرى نتيجة ذلك الاختيار. انشر سعرًا لـSPY ثم ارفع علَمًا فقد يقرأ قارئ يرى العلم سعرًا يساوي 0. ومن الطرق الأربع لترتيب الكاتب والقارئ واحدة فقط آمنة: release عند الكاتب مقترنة بـacquire عند القارئ.

تسمح مخازن الكتابة والذاكرات المخبئية والمترجم كلها للنواة بإنهاء كتابة أو قراءة لاحقة قبل سابقة ما دام خيط واحد لا يستطيع ملاحظة ذلك. أما خيط آخر فيستطيع. تنمذج آلتنا ذلك مباشرة: الخيط قائمة عمليات ويستطيع تنفيذ أي عملية استوفت قيود ترتيبها بأي ترتيب. تحتفظ العمليات على العنوان نفسه دائمًا بترتيبها وإلا لما رأى الخيط كتاباته. تحميل acquire يحجب كل ما يليه؛ وتخزين release ينتظر كل ما قبله. دالتان تقولان كل شيء: must_wait تسرد ما تنتظره عملية وeligible تسرد ما يجوز تنفيذه تاليًا.

def must_wait(ops, j):    waits = []    for i in range(j):        same = ops[i][1] == ops[j][1]        after_acquire = ops[i][0] == "load" and ops[i][3] == "acquire"        release = ops[j][0] == "store" and ops[j][3] == "release"        if same or after_acquire or release:            waits.append(i)    return waitsdef eligible(ops, done):    return [j for j in range(len(ops)) if j not in done and all(i in done for i in must_wait(ops, j))]writer = [("store", "data", 1, "relaxed"), ("store", "flag", 1, "release")]reader = [("load", "flag", "r1", "acquire"), ("load", "data", "r2", "relaxed")]print(must_wait(writer, 1), eligible(writer, set()), eligible(writer, {0}))print(must_wait(reader, 1), eligible(reader, set()))print(eligible([("load", "flag", "r1", "relaxed"), ("load", "data", "r2", "relaxed")], set()))

[0] [0] [1]
[0] [0]
[0, 1]

يتنظر تخزين release للعلم الموضع 0 وهو تخزين البيانات فلا يستطيع الكاتب تنفيذ عملياته إلا بالترتيب. ويحجب تحميل acquire للعلم تحميل البيانات الذي يليه فيعمل القارئ بالترتيب أيضًا. وبتحميلات عادية يكون كلاهما مؤهلًا في آن واحد وقد يقرأ القارئ البيانات أولًا.

outcomes هو مستكشف المواضيع السابقة لهذه الآلة الجديدة. الحالة هي العمليات التي أنجزها كل خيط والذاكرة والمسجلات. ومن حالة يجرّب كل عملية مؤهلة لكل خيط وحين لا يبقى شيء للتنفيذ تكون المسجلات نتيجة. ولأن ترتيبات كثيرة تصل إلى الحالة نفسها فإنه يتذكر الحالات التي رآها. يُنشر في اختبار تمرير الرسالة بتخزينين البيانات ثم العلم ويُستهلك بتحميلين العلم ثم البيانات. ويخطئ المستهلك حين يرى r1 == 1 (العلم) وr2 == 0 (لا بيانات بعد) وهذا ما تفحصه reads_stale.

def outcomes(programs, memory=None):    found = set()    seen = set()    def visit(done, mem, regs):        state = (tuple(frozenset(d) for d in done), tuple(sorted(mem.items())), tuple(sorted(regs.items())))        if state in seen:            return        seen.add(state)        moved = False        for tid, ops in enumerate(programs):            for j in eligible(ops, done[tid]):                moved = True                kind, address, x, _ = ops[j]                mem2, regs2 = dict(mem), dict(regs)                if kind == "store":                    mem2[address] = x                else:                    regs2[x] = mem.get(address, 0)                done2 = [set(d) for d in done]                done2[tid].add(j)                visit(done2, mem2, regs2)        if not moved:            found.add(tuple(sorted(regs.items())))    visit([set() for _ in programs], dict(memory or {}), {})    return founddef mp_programs(write_order, read_order):    return [        [("store", "data", 1, "relaxed"), ("store", "flag", 1, write_order)],        [("load", "flag", "r1", read_order), ("load", "data", "r2", "relaxed")],    ]def reads_stale(results):    return any(dict(outcome).get("r1") == 1 and dict(outcome).get("r2") == 0 for outcome in results)for pair in (("relaxed", "relaxed"), ("release", "acquire")):    results = outcomes(mp_programs(*pair))    print(pair, sorted(results), "stale:", reads_stale(results))

('relaxed', 'relaxed') [(('r1', 0), ('r2', 0)), (('r1', 0), ('r2', 1)), (('r1', 1), ('r2', 0)), (('r1', 1), ('r2', 1))] stale: True
('release', 'acquire') [(('r1', 0), ('r2', 0)), (('r1', 0), ('r2', 1)), (('r1', 1), ('r2', 1))] stale: False

بترتيبات relaxed قد ينتهي المستهلك بالأزواج الأربعة (r1, r2) ومنها (1, 0) وهو القديم. وبـrelease على تخزين العلم وacquire على تحميله لا يبقى إلا ثلاثة: القارئ الذي يرى العلم يرى البيانات أيضًا لأن أيًّا من الجانبين لا يمكن إعادة ترتيبه عبر العلم.

هل يكفي جانب واحد؟ جرّب الأزواج الأربعة. يفشل release عند الكاتب وحده: فقد يحمّل القارئ البيانات قبل العلم. ويفشل acquire عند القارئ وحده: فقد يخزّن الكاتب العلم قبل البيانات. لا ينجح إلا الزوج وهذا ما يبينه الجدول أدناه. هذا هو عقد release-acquire في std::atomic بلغة C++ وفي Rust وسبب نشر الطابور بلا أقفال لخانة بتخزين release لفهرس وقراءتها بتحميل acquire.

PAIRS = [("relaxed", "relaxed"), ("release", "relaxed"), ("relaxed", "acquire"), ("release", "acquire")]def ordering_table():    return {pair: reads_stale(outcomes(mp_programs(*pair))) for pair in PAIRS}for pair, stale in ordering_table().items():    print("write", pair[0], "| read", pair[1], "->", "can read stale data" if stale else "safe")

write relaxed | read relaxed -> can read stale data
write release | read relaxed -> can read stale data
write relaxed | read acquire -> can read stale data
write release | read acquire -> safe

price = int(round(float(load_bars()["close"].iloc[0]) * 100))programs = mp_programs("release", "acquire")programs[0][0] = ("store", "data", price, "relaxed")print(price, sorted(outcomes(programs)))

9369 [(('r1', 0), ('r2', 0)), (('r1', 0), ('r2', 9369)), (('r1', 1), ('r2', 9369))]

مع أول إغلاق لـSPY وهو 9369 سنتًا يستطيع القارئ أن يرى العلم وسعرًا يساوي 0 في ثلاث من الإعدادات الأربعة. يجتاز خطأ من هذا النوع كل الاختبارات على جهاز يحافظ على الترتيب ثم يظهر على آخر. ولهذا يجب إثبات الزوج الآمن على كل الترتيبات المسموحة كما يفعل المستكشف.

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

• الدالة · السؤالتعتمد على
• must_wait(ops, j)ماذا يجب أن تنتظر هذه العملية؟حساب بسيط
• eligible(ops, done)أي العمليات تُنفَّذ تاليًا؟حساب بسيط
• outcomes(programs, memory)بماذا يمكن أن تنتهي الخيوط؟eligible
• mp_programs(write_order, read_order)كيف يبدو تمرير الرسالة؟حساب بسيط
• reads_stale(results)هل يستطيع القارئ رؤية العلم بلا البيانات؟حساب بسيط
• ordering_table()أي أزواج الترتيبات آمنة؟outcomesmp_programs
• study(bars)أي الأزواج تحمي سعرًا حقيقيًا لـSPY؟outcomesmp_programs

الموضوع التالي: لديك الآن الأدوات لبناء بنية بلا أقفال ومفردات لوصف ما تضمنه. ضمانات التقدم تسمّي المستويات الثلاثة وهي بلا عرقلة وبلا أقفال وبلا انتظار وتختبر كل عدّاد كتبته أمام خيط يُوقَف إلى الأبد في أسوأ لحظة.