کتابخانه‌ی استاندارد · زمان و همروندی

اتمی atomic

شمارنده و پرچمی که چند نخ بدون قفل گرفتن دستی می‌توانند با خیال راحت تغییرشان دهند.

واردسازی اتمی

نام آرگومان‌ها شناسه‌ی خود کد است و معادل فارسی ندارد؛ گونه‌ها، کلیدواژه‌ها و نام بسته‌ها با معادل فارسی نوشته می‌شوند.

برای یک شمارنده‌ی ساده که چند نخ زیادش می‌کنند، لازم نیست خودتان قفل بسازید: صحیح۶۴ در این بسته هر کار را یک‌جا و بدون تداخل انجام می‌دهد. مقایسه سپس تعویض پایه‌ی بیشتر الگوریتم‌های بدون قفل است: مقدار را فقط اگر هنوز همانی باشد که انتظار دارید عوض می‌کند.

با gcc و clang و پشتیبان LLVM هر کار یکی از دستورهای اتمی خود پردازنده است. در tcc که این دستورها را ندارد، هر خانه به‌جای آن با یک قفل کوچک محافظت می‌شود؛ نتیجه همان است، فقط کندتر.

دو گونه در کار است: صحیح۶۴، یک عدد صحیح ۶۴ بیتی مشترک، و پرچم، یک درست یا نادرست مشترک. هر دو دسته‌های کوچکی به یک خانه در حافظه‌ی پویا هستند، پس فرستادن آن‌ها به تابع یا نخ به‌صورت مقدار همان خانه را به اشتراک می‌گذارد. برای چیزی بزرگ‌تر از یک مقدار، همگام سازی را به کار ببرید؛ برای فرستادن مقدار میان نخ‌ها، کانال را.

اشتباه‌های رایج:

  • به کار بردن خانه‌ای که هرگز ساخته نشده. اتمی.صحیح۶۴ {} خانه‌ای ندارد و با نخستین افزودن برنامه را از کار می‌اندازد؛ آن را با صحیح۶۴ جدید یا پرچم جدید بسازید، و برای متغیر سراسری در آغاز ریشه.
  • ترکیب دو عمل. اگر بارگذاری(ع) < ۱۰: افزودن(ع، ۱) پایان دو گام است و نخ دیگری می‌تواند میانشان کاری بکند؛ مقایسه سپس تعویض در یک حلقه برای همین است.
  • نابود کردن زودهنگام. نابودسازی صحیح۶۴ خانه را برای همه‌ی رونوشت‌های دسته آزاد می‌کند؛ آن را یک بار و پس از پیوستن همه‌ی نخ‌هایی که از آن استفاده می‌کنند صدا بزنید.

تفریق جداگانه‌ای نیست: افزودن(ع، ۰ - ۱) به عقب می‌شمارد.

دادن شماره‌های یکتا

افزودن مقدار پس از جمع را برمی‌گرداند و هیچ دو فراخوانی‌ای یک عدد نمی‌گیرند. پس یک منبع آماده برای شناسه‌های یکتا، شماره‌ی نوبت یا شماره‌ی خانه است که هر تعداد نخ می‌توانند بی هیچ قفلی از آن استفاده کنند.

atomic-guide-ids.salam
واردسازی اتمی

ناپایا شناسه‌ی بعدی := اتمی.صحیح۶۴ {}
ناپایا دفعات := وکتور {} برگردان وکتور<صحیح۶۴>

تابع پخش شناسه():
    تکرار ۱۰۰:
        شناسه := اتمی.افزودن(شناسه‌ی بعدی، ۱)
        دفعات.بنشان(شناسه برگردان صحیح - ۱، دفعات.بگیر(شناسه برگردان صحیح - ۱) + ۱)
    پایان
پایان

تابع ریشه:
    شناسه‌ی بعدی = اتمی.صحیح۶۴ جدید(۰)
    تکرار ۴۰۰:
        دفعات.بیفزا(۰)
    پایان
    الف := نخ‌ساز(پخش شناسه)
    ب := نخ‌ساز(پخش شناسه)
    پ := نخ‌ساز(پخش شناسه)
    ت := نخ‌ساز(پخش شناسه)
    نخ‌پیوند(الف)
    نخ‌پیوند(ب)
    نخ‌پیوند(پ)
    نخ‌پیوند(ت)
    ناپایا تکراری := ۰
    هر ع در دفعات:
        اگر ع != ۱:
            تکراری++
        پایان
    پایان
    سرچاپ "آخرین شناسه:"، اتمی.بارگذاری(شناسه‌ی بعدی)
    سرچاپ "شناسه‌هایی که بیش از یک بار داده شدند:"، تکراری
    دفعات.آزادکن()
    اتمی.نابودسازی صحیح۶۴(شناسه‌ی بعدی)
پایان
خروجیآخرین شناسه: 400 شناسه‌هایی که بیش از یک بار داده شدند: 0

چهار نخ هر کدام ۱۰۰ شناسه گرفتند و هر شناسه از ۱ تا ۴۰۰ دقیقاً یک بار داده شد. هر نخ هم فقط در خانه‌ای می‌نویسد که شناسه‌ی خودش نشان می‌دهد، برای همین وکتور هم قفل نمی‌خواهد.

به‌روزرسانی با مقایسه سپس تعویض

بعضی به‌روزرسانی‌ها یک جمع ساده نیستند: «بزرگ‌ترین مقدار دیده‌شده را نگه دار» باید مقدار را بخواند، تصمیم بگیرد و بنویسد. اگر این کار در دو قدم انجام شود، نخ دیگری می‌تواند وسط آن برسد. راه حل یک حلقه است: مقدار را بخوانید، مقدار تازه را حساب کنید و از مقایسه سپس تعویض بخواهید آن را فقط وقتی ذخیره کند که مقدار در این فاصله عوض نشده باشد. اگر عوض شده بود، دوباره بخوانید و تکرار کنید.

atomic-guide-max.salam
واردسازی اتمی

ناپایا بیشترین := اتمی.صحیح۶۴ {}

تابع ثبت(مقدار: صحیح۶۴):
    ناپایا دیده‌شده := اتمی.بارگذاری(بیشترین)
    تا مقدار > دیده‌شده:
        اگر اتمی.مقایسه سپس تعویض(بیشترین، دیده‌شده، مقدار):
            برگشت
        پایان
        دیده‌شده = اتمی.بارگذاری(بیشترین)
    پایان
پایان

تابع خوانش‌های پایین():
    تکرار ۵۰۰ در ای:
        ثبت((ای * ۷ % ۹۰۰) برگردان صحیح۶۴)
    پایان
پایان

تابع خوانش‌های بالا():
    تکرار ۵۰۰ در ای:
        ثبت((ای * ۱۳ % ۱۰۰۰) برگردان صحیح۶۴)
    پایان
پایان

تابع ریشه:
    بیشترین = اتمی.صحیح۶۴ جدید(۰)
    الف := نخ‌ساز(خوانش‌های پایین)
    ب := نخ‌ساز(خوانش‌های بالا)
    نخ‌پیوند(الف)
    نخ‌پیوند(ب)
    سرچاپ "بیشترین خوانش:"، اتمی.بارگذاری(بیشترین)
    اتمی.نابودسازی صحیح۶۴(بیشترین)
پایان
خروجیبیشترین خوانش: 993

حلقه همچنین به محض این‌که مقدار ذخیره‌شده دست‌کم به همین اندازه بزرگ باشد می‌ایستد، پس بیشتر فراخوانی‌ها اصلاً چیزی نمی‌نویسند.

علامت ایست برای یک کارگر

پرچم ساده‌ترین راه برای گفتن به یک نخ طولانی است که کارش را تمام کند: کارگر در هر دور آن را نگاه می‌کند و نخ اصلی وقتش که رسید آن را روشن می‌کند. یک متغیر سراسری منطقی ساده کافی نیست، چون هیچ تضمینی نیست که کارگر هرگز تغییر را ببیند.

atomic-guide-stop.salam
واردسازی اتمی
واردسازی همگام سازی

ناپایا ایست := اتمی.پرچم {}
ناپایا دورها := اتمی.صحیح۶۴ {}

تابع کارگر():
    تا وارونه اتمی.گرفتن(ایست):
        اتمی.افزودن(دورها، ۱)
        همگام سازی.خواب میلی ثانیه(۱)
    پایان
پایان

تابع ریشه:
    ایست = اتمی.پرچم جدید(نادرست)
    دورها = اتمی.صحیح۶۴ جدید(۰)
    ن := نخ‌ساز(کارگر)
    تا اتمی.بارگذاری(دورها) < ۲۰:
        همگام سازی.خواب میلی ثانیه(۱)
    پایان
    اتمی.تنظیم(ایست، درست)
    نخ‌پیوند(ن)
    سرچاپ "کارگر دست‌کم ۲۰ دور کار کرد:"، اتمی.بارگذاری(دورها) >= ۲۰
    سرچاپ "پرچم ایست:"، اتمی.گرفتن(ایست)
    اتمی.نابودسازی پرچم(ایست)
    اتمی.نابودسازی صحیح۶۴(دورها)
پایان
خروجیکارگر دست‌کم ۲۰ دور کار کرد: true پرچم ایست: true

فقط اولی برنده است

آزمون سپس تنظیم پرچم را روشن می‌کند و می‌گوید آیا شما بودید که روشنش کردید. وقتی چند نخ برای یک کار با هم مسابقه می‌دهند، مثل فرستادن یک هشدار یا یک پاک‌سازی یک‌باره، دقیقاً یکی از آن‌ها درست می‌گیرد.

atomic-guide-first.salam
واردسازی اتمی

ناپایا گرفته‌شده := اتمی.پرچم {}
ناپایا برنده‌ها := اتمی.صحیح۶۴ {}
ناپایا بازنده‌ها := اتمی.صحیح۶۴ {}

تابع کوشش برای گرفتن():
    اگر اتمی.آزمون سپس تنظیم(گرفته‌شده):
        اتمی.افزودن(برنده‌ها، ۱)
    وگرنه:
        اتمی.افزودن(بازنده‌ها، ۱)
    پایان
پایان

تابع ریشه:
    گرفته‌شده = اتمی.پرچم جدید(نادرست)
    برنده‌ها = اتمی.صحیح۶۴ جدید(۰)
    بازنده‌ها = اتمی.صحیح۶۴ جدید(۰)
    ناپایا نخ‌ها := وکتور {} برگردان وکتور<صحیح۶۴>
    دیرکن نخ‌ها.آزادکن()
    تکرار ۸:
        نخ‌ها.بیفزا(نخ‌ساز(کوشش برای گرفتن))
    پایان
    هر ن در نخ‌ها:
        نخ‌پیوند(ن)
    پایان
    سرچاپ "برنده‌ها:"، اتمی.بارگذاری(برنده‌ها)، "بازنده‌ها:"، اتمی.بارگذاری(بازنده‌ها)
    اتمی.نابودسازی پرچم(گرفته‌شده)
    اتمی.نابودسازی صحیح۶۴(برنده‌ها)
    اتمی.نابودسازی صحیح۶۴(بازنده‌ها)
پایان
خروجیبرنده‌ها: 1 بازنده‌ها: 7

اتمی یا قفل؟

مقدار اتمی وقتی مناسب است که وضعیت مشترک یک عدد یا یک پرچم باشد. همین که دو مقدار باید با هم عوض شوند، مثل موجودی و تاریخچه، از همگام سازی.قفل استفاده کنید: دو کار اتمی پشت سر هم با هم اتمی نیستند. برای آماده‌سازی‌ای که باید یک بار اجرا شود، همگام سازی.یک بار روشن‌تر از یک پرچم دست‌ساز است.

کارتابع
شمردن رویدادها از چند نخافزودن(الف، ۱)
گرفتن شماره‌ی آزاد بعدیافزودن و استفاده از نتیجه‌اش
خواندن آخرین مقدار برای گزارشبارگذاری
صفر کردن و گرفتن جمع قبلیتعویض(الف، ۰)
هر به‌روزرسانی از نوع خواندن، حساب، نوشتنمقایسه سپس تعویض در یک حلقه
گفتن به یک نخ که بایستدپرچم با تنظیم و گرفتن
این‌که دقیقاً یک نخ کاری بکندآزمون سپس تنظیم

گونه‌ها

صحیح۶۴ I64

ساختار صحیح۶۴
یک عدد صحیح ۶۴ بیتی مشترک بین نخ‌ها.
نامانگلیسیگونهتوضیح
سلولcellصحیح۶۴*نشانی مقدار.
قفلmuهمگام سازی.قفلقفل درونی.
atomic-I64.salam
واردسازی اتمی

ناپایا شمارنده := اتمی.صحیح۶۴ {}

تابع کارگر():
    تکرار ۱۰۰۰:
        اتمی.افزودن(شمارنده، ۱)
    پایان
پایان

تابع ریشه:
    شمارنده = اتمی.صحیح۶۴ جدید(۰)
    الف := نخ‌ساز(کارگر)
    ب := نخ‌ساز(کارگر)
    نخ‌پیوند(الف)
    نخ‌پیوند(ب)
    سرچاپ اتمی.بارگذاری(شمارنده)
    اتمی.ذخیره(شمارنده، ۱۰)
    سرچاپ اتمی.تعویض(شمارنده، ۲۰)، اتمی.بارگذاری(شمارنده)
    سرچاپ اتمی.مقایسه سپس تعویض(شمارنده، ۲۰، ۳۰)، اتمی.مقایسه سپس تعویض(شمارنده، ۲۰، ۴۰)، اتمی.بارگذاری(شمارنده)
    اتمی.نابودسازی صحیح۶۴(شمارنده)
    پ := اتمی.پرچم جدید(نادرست)
    سرچاپ اتمی.آزمون سپس تنظیم(پ)، اتمی.آزمون سپس تنظیم(پ)، اتمی.گرفتن(پ)
    اتمی.تنظیم(پ، نادرست)
    سرچاپ اتمی.گرفتن(پ)
    اتمی.نابودسازی پرچم(پ)
پایان
خروجی2000 10 20 true false 30 true false true false

پرچم Flag

ساختار پرچم
یک پرچم درست یا نادرست مشترک بین نخ‌ها.
نامانگلیسیگونهتوضیح
سلولcellصحیح۶۴*نشانی مقدار.
قفلmuهمگام سازی.قفلقفل درونی.

نمونه‌ی این مورد همراه با موارد بالاتر آمده است: atomic-I64.salam

تابع‌ها

صحیح۶۴ جدید NewI64

تابع صحیح۶۴ جدید(v: صحیح۶۴): صحیح۶۴
خانه‌ی تازه با مقدار اولیه.

نمونه‌ی این مورد همراه با موارد بالاتر آمده است: atomic-I64.salam

بارگذاری Load

تابع بارگذاری(a: صحیح۶۴): صحیح۶۴
مقدار فعلی را می‌خواند.

نمونه‌ی این مورد همراه با موارد بالاتر آمده است: atomic-I64.salam

ذخیره Store

تابع ذخیره(a: صحیح۶۴، v: صحیح۶۴)
مقدار تازه را می‌نویسد.

نمونه‌ی این مورد همراه با موارد بالاتر آمده است: atomic-I64.salam

افزودن Add

تابع افزودن(a: صحیح۶۴، delta: صحیح۶۴): صحیح۶۴
delta را اضافه می‌کند و مقدار تازه را برمی‌گرداند.

نمونه‌ی این مورد همراه با موارد بالاتر آمده است: atomic-I64.salam

تعویض Swap

تابع تعویض(a: صحیح۶۴، v: صحیح۶۴): صحیح۶۴
مقدار تازه را می‌نویسد و مقدار قبلی را برمی‌گرداند.

نمونه‌ی این مورد همراه با موارد بالاتر آمده است: atomic-I64.salam

مقایسه سپس تعویض CompareAndSwap

تابع مقایسه سپس تعویض(a: صحیح۶۴، expected: صحیح۶۴، next: صحیح۶۴): منطقی
اگر مقدار فعلی برابر expected باشد، آن را next می‌کند و درست برمی‌گرداند؛ وگرنه دست نمی‌زند.

نمونه‌ی این مورد همراه با موارد بالاتر آمده است: atomic-I64.salam

نابودسازی صحیح۶۴ DestroyI64

تابع نابودسازی صحیح۶۴(a: صحیح۶۴)
خانه را آزاد می‌کند.

نمونه‌ی این مورد همراه با موارد بالاتر آمده است: atomic-I64.salam

پرچم جدید NewFlag

تابع پرچم جدید(v: منطقی): پرچم
پرچم تازه با مقدار اولیه.

نمونه‌ی این مورد همراه با موارد بالاتر آمده است: atomic-I64.salam

گرفتن Get

تابع گرفتن(f: پرچم): منطقی
مقدار پرچم.

نمونه‌ی این مورد همراه با موارد بالاتر آمده است: atomic-I64.salam

تنظیم Set

تابع تنظیم(f: پرچم، v: منطقی)
مقدار پرچم را تعیین می‌کند.

نمونه‌ی این مورد همراه با موارد بالاتر آمده است: atomic-I64.salam

آزمون سپس تنظیم TestAndSet

تابع آزمون سپس تنظیم(f: پرچم): منطقی
اگر پرچم خاموش باشد، روشنش می‌کند و درست برمی‌گرداند؛ اگر از قبل روشن بوده، نادرست. فقط یک نخ برنده می‌شود.

نمونه‌ی این مورد همراه با موارد بالاتر آمده است: atomic-I64.salam

نابودسازی پرچم DestroyFlag

تابع نابودسازی پرچم(f: پرچم)
پرچم را آزاد می‌کند.

نمونه‌ی این مورد همراه با موارد بالاتر آمده است: atomic-I64.salam