اتمی atomic
شمارنده و پرچمی که چند نخ بدون قفل گرفتن دستی میتوانند با خیال راحت تغییرشان دهند.
واردسازی اتمی
نام آرگومانها شناسهی خود کد است و معادل فارسی ندارد؛ گونهها، کلیدواژهها و نام بستهها با معادل فارسی نوشته میشوند.
برای یک شمارندهی ساده که چند نخ زیادش میکنند، لازم نیست خودتان قفل بسازید: صحیح۶۴ در این بسته هر کار را یکجا و بدون تداخل انجام میدهد. مقایسه سپس تعویض پایهی بیشتر الگوریتمهای بدون قفل است: مقدار را فقط اگر هنوز همانی باشد که انتظار دارید عوض میکند.
با gcc و clang و پشتیبان LLVM هر کار یکی از دستورهای اتمی خود پردازنده است. در tcc که این دستورها را ندارد، هر خانه بهجای آن با یک قفل کوچک محافظت میشود؛ نتیجه همان است، فقط کندتر.
دو گونه در کار است: صحیح۶۴، یک عدد صحیح ۶۴ بیتی مشترک، و پرچم، یک درست یا نادرست مشترک. هر دو دستههای کوچکی به یک خانه در حافظهی پویا هستند، پس فرستادن آنها به تابع یا نخ بهصورت مقدار همان خانه را به اشتراک میگذارد. برای چیزی بزرگتر از یک مقدار، همگام سازی را به کار ببرید؛ برای فرستادن مقدار میان نخها، کانال را.
اشتباههای رایج:
- به کار بردن خانهای که هرگز ساخته نشده.
اتمی.صحیح۶۴ {}خانهای ندارد و با نخستینافزودنبرنامه را از کار میاندازد؛ آن را باصحیح۶۴ جدیدیاپرچم جدیدبسازید، و برای متغیر سراسری در آغازریشه. - ترکیب دو عمل.
اگر بارگذاری(ع) < ۱۰: افزودن(ع، ۱) پایاندو گام است و نخ دیگری میتواند میانشان کاری بکند؛مقایسه سپس تعویضدر یک حلقه برای همین است. - نابود کردن زودهنگام.
نابودسازی صحیح۶۴خانه را برای همهی رونوشتهای دسته آزاد میکند؛ آن را یک بار و پس از پیوستن همهی نخهایی که از آن استفاده میکنند صدا بزنید.
تفریق جداگانهای نیست: افزودن(ع، ۰ - ۱) به عقب میشمارد.
دادن شمارههای یکتا
افزودن مقدار پس از جمع را برمیگرداند و هیچ دو فراخوانیای یک عدد نمیگیرند. پس یک منبع آماده برای شناسههای یکتا، شمارهی نوبت یا شمارهی خانه است که هر تعداد نخ میتوانند بی هیچ قفلی از آن استفاده کنند.
واردسازی اتمی
ناپایا شناسهی بعدی := اتمی.صحیح۶۴ {}
ناپایا دفعات := وکتور {} برگردان وکتور<صحیح۶۴>
تابع پخش شناسه():
تکرار ۱۰۰:
شناسه := اتمی.افزودن(شناسهی بعدی، ۱)
دفعات.بنشان(شناسه برگردان صحیح - ۱، دفعات.بگیر(شناسه برگردان صحیح - ۱) + ۱)
پایان
پایان
تابع ریشه:
شناسهی بعدی = اتمی.صحیح۶۴ جدید(۰)
تکرار ۴۰۰:
دفعات.بیفزا(۰)
پایان
الف := نخساز(پخش شناسه)
ب := نخساز(پخش شناسه)
پ := نخساز(پخش شناسه)
ت := نخساز(پخش شناسه)
نخپیوند(الف)
نخپیوند(ب)
نخپیوند(پ)
نخپیوند(ت)
ناپایا تکراری := ۰
هر ع در دفعات:
اگر ع != ۱:
تکراری++
پایان
پایان
سرچاپ "آخرین شناسه:"، اتمی.بارگذاری(شناسهی بعدی)
سرچاپ "شناسههایی که بیش از یک بار داده شدند:"، تکراری
دفعات.آزادکن()
اتمی.نابودسازی صحیح۶۴(شناسهی بعدی)
پایانچهار نخ هر کدام ۱۰۰ شناسه گرفتند و هر شناسه از ۱ تا ۴۰۰ دقیقاً یک بار داده شد. هر نخ هم فقط در خانهای مینویسد که شناسهی خودش نشان میدهد، برای همین وکتور هم قفل نمیخواهد.
بهروزرسانی با مقایسه سپس تعویض
بعضی بهروزرسانیها یک جمع ساده نیستند: «بزرگترین مقدار دیدهشده را نگه دار» باید مقدار را بخواند، تصمیم بگیرد و بنویسد. اگر این کار در دو قدم انجام شود، نخ دیگری میتواند وسط آن برسد. راه حل یک حلقه است: مقدار را بخوانید، مقدار تازه را حساب کنید و از مقایسه سپس تعویض بخواهید آن را فقط وقتی ذخیره کند که مقدار در این فاصله عوض نشده باشد. اگر عوض شده بود، دوباره بخوانید و تکرار کنید.
واردسازی اتمی
ناپایا بیشترین := اتمی.صحیح۶۴ {}
تابع ثبت(مقدار: صحیح۶۴):
ناپایا دیدهشده := اتمی.بارگذاری(بیشترین)
تا مقدار > دیدهشده:
اگر اتمی.مقایسه سپس تعویض(بیشترین، دیدهشده، مقدار):
برگشت
پایان
دیدهشده = اتمی.بارگذاری(بیشترین)
پایان
پایان
تابع خوانشهای پایین():
تکرار ۵۰۰ در ای:
ثبت((ای * ۷ % ۹۰۰) برگردان صحیح۶۴)
پایان
پایان
تابع خوانشهای بالا():
تکرار ۵۰۰ در ای:
ثبت((ای * ۱۳ % ۱۰۰۰) برگردان صحیح۶۴)
پایان
پایان
تابع ریشه:
بیشترین = اتمی.صحیح۶۴ جدید(۰)
الف := نخساز(خوانشهای پایین)
ب := نخساز(خوانشهای بالا)
نخپیوند(الف)
نخپیوند(ب)
سرچاپ "بیشترین خوانش:"، اتمی.بارگذاری(بیشترین)
اتمی.نابودسازی صحیح۶۴(بیشترین)
پایانحلقه همچنین به محض اینکه مقدار ذخیرهشده دستکم به همین اندازه بزرگ باشد میایستد، پس بیشتر فراخوانیها اصلاً چیزی نمینویسند.
علامت ایست برای یک کارگر
پرچم سادهترین راه برای گفتن به یک نخ طولانی است که کارش را تمام کند: کارگر در هر دور آن را نگاه میکند و نخ اصلی وقتش که رسید آن را روشن میکند. یک متغیر سراسری منطقی ساده کافی نیست، چون هیچ تضمینی نیست که کارگر هرگز تغییر را ببیند.
واردسازی اتمی
واردسازی همگام سازی
ناپایا ایست := اتمی.پرچم {}
ناپایا دورها := اتمی.صحیح۶۴ {}
تابع کارگر():
تا وارونه اتمی.گرفتن(ایست):
اتمی.افزودن(دورها، ۱)
همگام سازی.خواب میلی ثانیه(۱)
پایان
پایان
تابع ریشه:
ایست = اتمی.پرچم جدید(نادرست)
دورها = اتمی.صحیح۶۴ جدید(۰)
ن := نخساز(کارگر)
تا اتمی.بارگذاری(دورها) < ۲۰:
همگام سازی.خواب میلی ثانیه(۱)
پایان
اتمی.تنظیم(ایست، درست)
نخپیوند(ن)
سرچاپ "کارگر دستکم ۲۰ دور کار کرد:"، اتمی.بارگذاری(دورها) >= ۲۰
سرچاپ "پرچم ایست:"، اتمی.گرفتن(ایست)
اتمی.نابودسازی پرچم(ایست)
اتمی.نابودسازی صحیح۶۴(دورها)
پایانفقط اولی برنده است
آزمون سپس تنظیم پرچم را روشن میکند و میگوید آیا شما بودید که روشنش کردید. وقتی چند نخ برای یک کار با هم مسابقه میدهند، مثل فرستادن یک هشدار یا یک پاکسازی یکباره، دقیقاً یکی از آنها درست میگیرد.
واردسازی اتمی
ناپایا گرفتهشده := اتمی.پرچم {}
ناپایا برندهها := اتمی.صحیح۶۴ {}
ناپایا بازندهها := اتمی.صحیح۶۴ {}
تابع کوشش برای گرفتن():
اگر اتمی.آزمون سپس تنظیم(گرفتهشده):
اتمی.افزودن(برندهها، ۱)
وگرنه:
اتمی.افزودن(بازندهها، ۱)
پایان
پایان
تابع ریشه:
گرفتهشده = اتمی.پرچم جدید(نادرست)
برندهها = اتمی.صحیح۶۴ جدید(۰)
بازندهها = اتمی.صحیح۶۴ جدید(۰)
ناپایا نخها := وکتور {} برگردان وکتور<صحیح۶۴>
دیرکن نخها.آزادکن()
تکرار ۸:
نخها.بیفزا(نخساز(کوشش برای گرفتن))
پایان
هر ن در نخها:
نخپیوند(ن)
پایان
سرچاپ "برندهها:"، اتمی.بارگذاری(برندهها)، "بازندهها:"، اتمی.بارگذاری(بازندهها)
اتمی.نابودسازی پرچم(گرفتهشده)
اتمی.نابودسازی صحیح۶۴(برندهها)
اتمی.نابودسازی صحیح۶۴(بازندهها)
پایاناتمی یا قفل؟
مقدار اتمی وقتی مناسب است که وضعیت مشترک یک عدد یا یک پرچم باشد. همین که دو مقدار باید با هم عوض شوند، مثل موجودی و تاریخچه، از همگام سازی.قفل استفاده کنید: دو کار اتمی پشت سر هم با هم اتمی نیستند. برای آمادهسازیای که باید یک بار اجرا شود، همگام سازی.یک بار روشنتر از یک پرچم دستساز است.
| کار | تابع |
|---|---|
| شمردن رویدادها از چند نخ | افزودن(الف، ۱) |
| گرفتن شمارهی آزاد بعدی | افزودن و استفاده از نتیجهاش |
| خواندن آخرین مقدار برای گزارش | بارگذاری |
| صفر کردن و گرفتن جمع قبلی | تعویض(الف، ۰) |
| هر بهروزرسانی از نوع خواندن، حساب، نوشتن | مقایسه سپس تعویض در یک حلقه |
| گفتن به یک نخ که بایستد | پرچم با تنظیم و گرفتن |
| اینکه دقیقاً یک نخ کاری بکند | آزمون سپس تنظیم |
گونهها
صحیح۶۴ I64
ساختار صحیح۶۴| نام | انگلیسی | گونه | توضیح |
|---|---|---|---|
| سلول | cell | صحیح۶۴* | نشانی مقدار. |
| قفل | mu | همگام سازی.قفل | قفل درونی. |
واردسازی اتمی
ناپایا شمارنده := اتمی.صحیح۶۴ {}
تابع کارگر():
تکرار ۱۰۰۰:
اتمی.افزودن(شمارنده، ۱)
پایان
پایان
تابع ریشه:
شمارنده = اتمی.صحیح۶۴ جدید(۰)
الف := نخساز(کارگر)
ب := نخساز(کارگر)
نخپیوند(الف)
نخپیوند(ب)
سرچاپ اتمی.بارگذاری(شمارنده)
اتمی.ذخیره(شمارنده، ۱۰)
سرچاپ اتمی.تعویض(شمارنده، ۲۰)، اتمی.بارگذاری(شمارنده)
سرچاپ اتمی.مقایسه سپس تعویض(شمارنده، ۲۰، ۳۰)، اتمی.مقایسه سپس تعویض(شمارنده، ۲۰، ۴۰)، اتمی.بارگذاری(شمارنده)
اتمی.نابودسازی صحیح۶۴(شمارنده)
پ := اتمی.پرچم جدید(نادرست)
سرچاپ اتمی.آزمون سپس تنظیم(پ)، اتمی.آزمون سپس تنظیم(پ)، اتمی.گرفتن(پ)
اتمی.تنظیم(پ، نادرست)
سرچاپ اتمی.گرفتن(پ)
اتمی.نابودسازی پرچم(پ)
پایانپرچم 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