همگامسازی و عدم وجود رقابت دادهای
مکانیزمهای همگامسازی، رشتههای همزمان را هماهنگ میکنند تا دادههای مشترک به صورت ایمن دسترسی پیدا کنند، و عدم وجود رقابت دادهای ویژگیای است که برنامههای همزمان را قابل پیشبینی میکند.
Definition
همگامسازی، هماهنگی فعالیتهای همزمان برای اعمال ترتیب یا انحصار متقابل بر منابع مشترک است، و عدم وجود رقابت دادهای ویژگیای است که هیچ دو رشتهای به طور همزمان به یک مکان حافظه دسترسی پیدا نمیکنند، در حالی که حداقل یکی از آنها در حال نوشتن است و هیچ همگامسازی مداخلهگری وجود ندارد.
Scope
این موضوع مکانیزمها و ویژگیهایی را پوشش میدهد که دسترسی همزمان به وضعیت مشترک را صحیح میکنند: انحصار متقابل، قفلها، سمافورها و مانیتورها، متغیرهای شرطی، الگوریتمهای بدون قفل و بدون انتظار، حافظه تراکنشی، رابطه «قبل از وقوع» (happens-before)، و تشخیص رقابتهای دادهای. همچنین به بنبست، اتمیسیته، و نظم مورد نیاز برای حفظ برنامهها بدون رقابت دادهای میپردازد.
Core questions
- انحصار متقابل چگونه حاصل میشود و خطرات آن (بنبست، گرسنگی) چیست؟
- چه چیزی همگامسازی مبتنی بر قفل را از همگامسازی بدون قفل متمایز میکند؟
- رابطه «قبل از وقوع» چگونه رقابتهای دادهای را تعریف میکند؟
- رقابتهای دادهای چگونه میتوانند به صورت خودکار شناسایی شوند؟
Key theories
- انحصار متقابل
- راهحل دایکسترا برای مسئله کنترل همزمان، انحصار متقابل را به عنوان نیاز اساسی همگامسازی تثبیت کرد و تضمین میکند که بخشهای بحرانی به طور همزمان اجرا نمیشوند.
- حافظه تراکنشی
- هرلیهی و ماس حافظه تراکنشی را پیشنهاد کردند که در آن گروههایی از عملیات حافظه به صورت اتمی اجرا میشوند و جایگزینی قابل ترکیب برای قفلگذاری دقیق برای ساخت ساختارهای داده همزمان ارائه میدهند.
- «قبل از وقوع» و تشخیص رقابت پویا
- بر اساس رابطه «قبل از وقوع» لامپورت، ردیاب Eraser نشان داد که چگونه میتوان رقابتهای دادهای را به صورت پویا با بررسی یک نظم قفلگذاری پیدا کرد، که نمونهای از تشخیص خودکار رقابت است.
Clinical relevance
همگامسازی صحیح برای نرمافزارهای همزمان و موازی قابل اعتماد ضروری است؛ رقابتهای دادهای برخی از گریزانترین باگها را در عمل ایجاد میکنند. ردیابهای رقابت، حافظه تراکنشی، و الگوهای همگامسازی منظم ابزارهای اصلی برای ساخت سیستمهای چندرشتهای قابل اعتماد هستند.
History
راهحل انحصار متقابل دایکسترا در سال 1965 و سمافورهای بعدی او، بنیان همگامسازی را بنا نهادند، که پس از آن مانیتورهای هوار و برینچ هانسن معرفی شدند. رابطه «قبل از وقوع» لامپورت در سال 1978 زیربنای تعاریف مدرن رقابت است؛ هرلیهی و ماس حافظه تراکنشی را در سال 1993 معرفی کردند، و ردیابهای رقابت پویا مانند Eraser (1997) و ابزارهای بعدی «قبل از وقوع» برای اشکالزدایی همزمانی استاندارد شدند.
Debates
- قفلها در برابر رویکردهای بدون قفل و تراکنشی
- طراحان در مورد همگامسازی سنتی مبتنی بر قفل، که ساده است اما مستعد بنبست و ترکیبپذیری ضعیف است، در مقابل الگوریتمهای بدون قفل و حافظه تراکنشی، که ترکیبپذیری و تضمینهای پیشرفت را با هزینه پیچیدگی یا سربار بهبود میبخشند، بحث میکنند.
Key figures
- Edsger Dijkstra
- Leslie Lamport
- Maurice Herlihy
- C. A. R. Hoare
- Stefan Savage
Related topics
Seminal works
- dijkstra1965
- herlihy1993
- savage1997
- lamport1978
Frequently asked questions
- رقابت دادهای چیست؟
- رقابت دادهای زمانی رخ میدهد که دو رشته به طور همزمان به یک مکان حافظه دسترسی پیدا کنند، حداقل یکی از دسترسیها یک عملیات نوشتن باشد، و دسترسیها توسط همگامسازی مرتب نشده باشند، که در بیشتر مدلهای حافظه منجر به رفتار نامشخص یا غیرقابل پیشبینی میشود.
- تفاوت بین همگامسازی مبتنی بر قفل و بدون قفل چیست؟
- همگامسازی مبتنی بر قفل از انحصار متقابل استفاده میکند تا فقط یک رشته در یک زمان وارد یک بخش بحرانی شود، در حالی که همگامسازی بدون قفل از عملیات اتمی استفاده میکند تا تضمین کند که همیشه یک رشته بدون نگه داشتن قفل پیشرفت میکند و از بنبست جلوگیری میکند.