اگر به پست‌های قبلی که راجع به مباحث مربوط به پیاده‌سازیِ ساختمان‌داده‌های lock-free نوشتم دقت کنیم، می‌بینیم که مقدار خوبی پیچیدگی در طراحی و پیاده‌سازیِ این نوع از ساختمان‌داده‌ها وجود داره و همیشه وقتی یه چیزی خیلی پیچیده‌ست، خوبه که چکیدهٔ مفاهیم و نکات رو به صورت خلاصه داشته باشیم تا بعدا بتونیم بهشون رجوع کنیم و حکم یک یادآوری رو برامون داشته باشه. با ما همراه باشید(اجباری).

استفاده از memory_order_seq_cst برای طراحی و پیاده‌سازیِ یک پروتوتایپ

پیاده‌سازیِ یک ساختمان‌دادهٔ lock-free به اندازهٔ کافی پیچیده هست. فکر کردن راجع به race conditionها، مدیریت حافظه و کلی چیز دیگه هست که باید بهشون فکر کنیم و توی پیاده‌سازی/طراحی بهش توجه داشته باشیم. پس بهتره که کار خودمون رو از اینی که هست سخت‌تر نکرده و قصهٔ پر غصهٔ memory orderها رو وارد ماجرا نکنیم. بنابراین زمانی که داریم پیاده‌سازیِ اولیه از ساختمان‌داده‌مون رو ارائه می‌دیم، همهٔ عملیات‌ها رو با استفاده از std::memory_order_seq_cst برچسب‌گذاری می‌کنیم تا تمرکزمون رو روی functionality برنامه بذاریم. به‌صورت کلی و جدای از سخت‌تر کردن توسعه، داستان memory orderها یکجور بهینه‌سازی محسوب میشه و درنظر گرفتن memory orderها در زمان توسعه، یک premature optimization درنظر گرفته میشه که باید ازش دوری کرد. از طرف دیگه، معمولا ما تنها زمانی می‌تونیم این چنین بهینه‌سازی‌ای رو انجام بدیم که ساختار کلیِ کدمون مشخص شده باشه پس درنظر گرفتن memory order زمانی که ساختار کد مشخص نیست ممکنه باعث این بشه که حتی کد درستی ننویسیم.

استفاده از الگوهای lock-free مدیریت حافظه

به‌نظر من بزرگترین چالش توی طراحی و پیاده‌سازیِ یک ساختمان دادهٔ lock-free بحث مدیریت حافظه هست. اینکه چطور در محیط چند تردی بتونیم بفهمیم آیا باید حافظهٔ یک شئ رو آزاد کنیم یا نه و چطور اینکار رو با سرعت خوبی انجام بدیم که باعث نشه اشیاء زیادی توی حافظه باقی بمونن که استفاده هم نمیشن. ۳تا روش مرسوم که می‌تونم ازشون نام ببرم این‌ها هستند که ۲تاشون رو در پست‌های قبلی دیدیم:

• ایجاد یک لیست انتظار از اشیاء قابل حذف شدن و حذف کردن اون‌ها در لحظه‌ای که هیچ تردی به ساختمان دادهٔ ما دسترسی نداره: قسمت اول پیاده‌سازی stack
• استفاده از Hazard Pointersها یا اسم موردعلاقه‌ٔ من: اشاره‌گرهای خطری
• استفاده از شمارش ارجاع یا Reference counting بنابراین میتونیم در حین آزاد کردن حافظه بفهمیم آیا تردی هست که به شئ موردنظر دسترسی داشته باشه یا نه.

پیاده‌سازی یک پشتهٔ Lock-Free - قسمت اول

در این پست(و احتمالا پست بعدی) راجع به پیاده‌سازی کردن یک Stack به شکل lock-free صحبت می‌کنیم.

وبلاگ سیْدپولرسیدپولر

پیاده‌سازی یک پشتهٔ Lock-Free - قسمت دوم: اشاره‌گرهای خطری

در این پست، سعی کردیم مدیریت حافظهٔ ساختمان‌داده‌ای که نوشتیم رو با استفاده از Hazard Pointer ها انجام بدیم.

وبلاگ سیْدپولرسیدپولر

ایدهٔ کلیِ همهٔ اون ۳تا روش این هست که راهی پیدا کنیم تا ببینیم آیا شئ موردنظر تحت دسترسی تردی هست یا نه. اگر هیچ تردی به شئ‌مون دسترسی نداشت، یعنی میتونیم با خیال راحت حافظه‌ش رو آزاد کنیم.

این بحث مدیریت حافظه دردی هست که سی++کارها باید باهاش دست و پنجه نرم کنن چون Garbage Collectorای در این زبان وجود نداره. اگر در زبانی(یا کامپایلری) که شما باهاش کار می‌کنید این قابلیت وجود داره، خوش‌به‌حالتون!

یک راه‌حل دیگه که من خودم طرفدارش هستم(چون ادای کسانی رو درمیارم که خیلی پرفورمنس براشون مهمه)، بازیافت کردن nodeهاست. یعنی حافظه‌ای رو آزاد نکنیم یا اختصاص ندیم بلکه ساختمان داده‌مون تعداد ثابتی گره داشته باشه و همیشه از همون‌ها استفاده کنیم. اینجوری هم سربار تخصیص/آزاد کردن حافظه رو نداریم و هم احتمال داشتن UB خیلی کمتر میشه. اما این روش میتونه یک مشکل دیگه‌ای رو بوجود بیاره که بهش میگن ABA Problem

حواسمون به ABA Problem باشه!

مسئلهٔ ABA مشکلی هست که در الگوریتم‌هایی بوجود میاد که بر اساس compare- exchange هستند. این مسئله اینطور به‌وجود میاد:

1. ترد ۱، یک متغییر اتمیک(مثلا x) رو می‌خونه و می‌بینه مقدارش برابر با A هست.
2. ترد ۱، یک‌سری عملیات رو بر اساس این مقدار انجام می‌ده(هر چیزی، مثلا dereference میکنه).
3. ترد ۱ توسط سیستم‌عامل stall/suspend میشه.
4. یک ترد دیگه(مثلا ترد ۲)، یک‌سری عملیات روی x انجام می‌ده و مقدار x رو به B تغییر میده.
5. ترد ۲، مقدار x که توی مرحلهٔ قبل باهاش کار انجام داده بود رو invalid می‌کنه(مثلا حافظهٔ‌ش رو آزاد میکنه).
6. ترد۲، دوباره مقدار x رو عوض میکنه و دوباره مقدار A رو داخلش قرار میده. (ممکنه A، آدرس یک شئ جدید باشه که تازه allocate شده ولی آدرسش دقیقا برابر با همون شئ‌ای باشه که توی مرحلهٔ قبل آزادش کرده).
7. ترد ۱ از حالت stall درمیاد و ادامهٔ کارش رو انجام میده و برای اینکه مطمئن بشه هنوز مقدار x عوض نشده، یک عملیات compare-exchange انجام میده تا ببینه آیا هنوز مقداری که خونده(مثلا اشاره‌گر) برابر با A هست یا نه. و می‌بینه که بله هنوز برابر با A هست. اما این مقدار جدیدِ A، همون شئ‌ای نیست که توی مرحلهٔ ۲ خونده و عوض شده و ترد ۱ هیچ راهی برای فهمیدن این موضوع نداره! پس به‌فنا رفتیم!

مرسوم‌ترین راه جلوگیری از این مشکل اینه که یک ABA counter در کنار متغییر x داشته باشیم(مثلا در یک struct) و هربار که عملیات compare-exchange رو انجام میدیم، مقدار شمارنده رو یکی اضافه می‌کنیم. اینطوری دیگه حتی اگه مقدار x برابر باشه، اون شمارنده عوض شده و عملیات compare-exchange با موفقیت انجام نمیشه چون این عملیات رو روی کلِ اون struct انجام میدیم.

این مشکل مخصوصا در ساختمان‌داده‌ها/الگوریتم‌هایی که از free listها استفاده می‌کنن یا به هر نوعی گره‌ها رو بجای برگردوندنشون به allocator، بازیافت می‌کنن بوجود میاد و اگر از این تکنیک‌ها و ابزارها استفاده می‌کنیم باید حواسمون به این مسئله هم باشه.

پیدا کردن حلقه‌های busy-wait و کمک کردن تردها به همدیگه

اگه حواسمون جمع نباشه، ساختمان‌دادهٔ lock-freeای که با بدبختی پیاده‌سازیش کردیم میتونه هیچ فرقی با یک ساختمان‌دادهٔ lock-based نداشته باشه. چطور؟ با busy-wait. ممکنه انقدر تردها توی حلقه‌های compare-exchange یا هرنوع busy-waitدیگه‌ای بمونن که عملا فقط یک ترد بتونه در یک نقطهٔ زمانی عملیات خودش رو انجام بده و این عملا فرقی با استفاده از lock نداره و چه بسا بهتر باشه که از mutex و امثالهم استفاده کنیم چون اون‌ها حداقل سیکل پردازنده رو هدر نمیدن(چون باعث suspend شدن ترد میشن). اگر می‌بینیم که در ساختمان‌داده‌مون جایی وجود داره که ممکنه busy-wait پیش بیاد و تردهای دیگه عملا بلاک بشن، میتونیم کاری کنیم که تردها بجای صبر کردن الکی بیان و به ترد فعلی که داره پردازش می‌کنه کمک کنن تا کارش زودتر تموم بشه(یعنی برخی از عملیات‌های تردهای دیگه رو توی این زمانی که دارن صبر میکنن انجام بدن) و اینطوری نه تنها دیگه blocking نیستند بلکه با کمک به تردی که جلوی کارشون رو گرفته باعث میشن خودشون یا بقیه زودتر از busy-wait دربیان. میدونم که این موضوع ممکنه یکم گیج‌کننده باشه مخصوصا که مثالی ازش نمیارم ولی خب reproduce کردن این موضوع راحت نیست پس اگر دوست دارید بیشتر راجع بهش بیشتر بدونید، زحمت جستجو کردنش گردن خودتونه.

جمع بندی

همونطور که قبلا بارها این مورد رو دیدیم و به‌صورت شهودی بهش رسیدیم، طراحی ساختمان داده‌های lock-free کار راحتی نیست. چیزهای بسیار زیادی هست که باید بهش توجه کنیم و همین باعث میشه که راحت یک چیزی از زیر دستمون دربره و به‌صورت کلی اشتباه کنیم. مهمه که بدونیم همیشه نباید از این نوع ساختمان‌داده‌ها استفاده کرد چرا که لزوما استفاده از ساختمان‌داده‌های lock-free دلیل نمیشه پرفورمنس بهتری داشته باشیم. در شرایط خیلی نادرتر، حتی اصلا نیاز نباشه که کلا از اول یک ساختمان داده رو برای کار concurrent خودمون طراحی/استفاده کنیم چون به صورت کلی دلیلی که ما از این ابزار استفاده می‌کنیم این هست که وظیفهٔ sync کردن داده‌ها رو تا جای ممکن encapsulate کنیم در ساختمان داده تا کد اصلیمون که می‌خواد پردازش اصلی رو روی داده‌های موجود در ساختمان داده انجام بده رو با فراغت خیال بیشتری طراحی و پیاده‌سازی کنیم.

در پست‌های بعدی بیشتر راجع به همین مسئله صحبت می‌کنم: اینکه حالا چطور واقعا از این ساختمان‌داده‌های concurrent استفاده کنیم!

عزت زیاد.