بخشی از مقاله
نقش حافظه های تراکنشی در برنامه نویسی موازی
خلاصه
با رواج ریزپردازنده های چند هسته ای با حافظه مشترک و توسعه پردازش های چندنخی1، همزمان سازی و ایجاد سنکرونی بین نخ2 های موازی در دسترسی به حافظه مشترک، مستلزم به کارگیری مکانیزم هایی برای کنترل نخ های موازی و همروند است. این مکانیزم ها عبارتند از: قفل ها3، حافظه تراکنشی.4 هدف اصلی این مکانیزم ها، تضمین اجرای موازی به طور صحیح و عدم برخورد در دسترسی به حافظه مشترک می باشد. استفاده از قفل ها دارای بسیاری نقایص شناخته شده می باشد مانند بن بست5، اولویت معکوس6 و ...... می باشد. حافظه تراکنشی جایگزینی است که در طی دو دهه اخیر برای قفل ها پیشنهاد شده است و توجه محققان را به خود جلب نموده است. در این مقاله، مفهوم حافظه تراکنشی را توضیح داده و مزایا و محدودیت های آن را شرح داده همچنین کار بر روی نرم افزار، سخت افزار و روشهای ترکیبی در مورد حافظه تراکنشی نیز ارائه شده است.
کلمات کلیدی: حافظه تراکنشی، قفل ها، برنامه نویسی موازی، حافظه مشترک
.1 مقدمه
در طی دو دهه اخیر محققان بر این واقعیت که رایانه های آنها به افزایش سرعت ادامه خواهند داد تکیه کردند. سرعت پردازش به طور مداوم در طول سالها مطابق با قانون مور افزایش یافته و بدین ترتیب سیستم هایی با پیچیدگی های روزافزون را بدون نیاز به نوآوری های انقلابی در زمینه نرم افزاری ایجاد کردیم. متاسفانه به نظر می رسد که این روند رو به اتمام است به گفته سیمون [1]، ما دیگر نمی توانیم فرض کنیم که برنامه های ما تنها با خرید جدیدترین نسل پردازنده های سریعتر اجرا خواهد شد در حالی که بهبود پردازنده های انفرادی ممکن است در حال کاهش باشد، در نتیجه تلاش ها به برنامه نویسی موازی معطوف شده است.
پردازنده های چند هسته ای در حال گسترش می باشند و این وظیفه توسعه دهندگان سیستم عامل و نرم افزار است که راه حلی برای استفاده از آنها با حداکثر ظرفیتشان بیابند. لاروس و راجوار [2]، درکتاب خود اشاره می کنند که
سیستمهای پایگاه داده در طی دهه ها به طور موفقیت آمیزی با استفاده از تراکنش ها همزمانی7 را ممکن ساخته اند. این امر منجر به تلاش های بسیار برای استفاده از مدل برنامه نویسی در پایگاه داده ها به عنوان روش برنامه نویسی موازی فراگیرتر شده است. برنامه نویسی موازی برای استفاده هر چه بهتر از منابع سیستم و افزایش سرعت و کارایی برنامه روی پردازندهها به وجود آمد.
در این نوع برنامه نویسی، قسمتهایی از برنامه اصلی که قابلیت اجرای همزمان را دارند به چند زیر برنامه تقسیم شده و به صورت همزمان روی چند پردازنده یا چند نخ اجرا میشوند. قسمتی از برنامه هم که قابلیت اجرای موازی را ندارد به صورت سریال روی یک پردازنده اجرا میشود. در واقع تفاوت اصلی برنامه نویسی ترتیبی8 و موازی همین امر میباشد، اما در پی آن مفاهیم متعددی مطرح میشود که اغلب در برنامه نویسی ترتیبی مطرح نبوده و یا ماهیت آنها با مفهوم متناظر آن در برنامه نویسی ترتیبیکاملاً متفاوت است.
محاسبات موازی تحولی در محاسبات ترتیبی است که تلاش می کند رویدادهای بسیار پیچیده و وابسته به یکدیگر با وجود تبعیت از یک توالی همگی در یک زمان رخ دهند. از دلایل اولیه استفاده از پردازش موازی صرفه جویی در زمان، توانایی حل مسائل بزرگتر در یک بازه زمانی ثابت و انجام چند کار به طور همزمان می باشد از دیگر مزایای استفاده از پردازش موازی بهره وری از منابع غیر محلی می باشد به عنوان مثال استفاده از کامپیوترهای یک شبکه یا حتی اینترنت وقتی که منابع محلی به اندازه کافی در اختیار نمی باشد، از نگاهی دیگر با استفاده از منابع محاسباتی ارزان تر و موجود به صورت موازی می توان در پرداخت هزینه برای خرید ابرکامپیوتر صرفه جویی کرد. وقتی از یک کامپیوتر به صورت منفرد استفاده می شود محدودیتی در حداکثر مقدار حافظه آن وجود دارد که برای حل مسائل بزرگ استفاده از حافظه چندین کامپیوتر می تواند راهی برای غلبه بر این محدودیت باشد.
نوشتن برنامه های موازی که به طور صحیح کار کند کاری دشوار است و مهمترین مسئله در نوشتن برنامه های موازی، بحث همگام سازی می باشد. چند پردازنده ممکن است نیاز به دسترسی به مکانهای یکسان در حافظه مشترک داشته باشند همان طورکه شکل .1 نشان می دهد به عنوان مثال در صورتی که دو پردازنده سعی کنند که متغیری را در یک زمان یکسان تغییر دهند، این امر می تواند منجر به خرابی داده ها گردد که از قفل ها به عنوان راه حل این مشکل استفاده می کنند.
شکل-1 دسترسی همزمان به حافظه مشترک
متداولترین راه برای استفاده از برنامه نویسی موازی استفاده از قفل ها می باشد. قفل امتیاز دستیابی منابع مشترک
به یک واحد داده است که توسط زیر سیستم قفل گذاری به یک تراکنش داده می شود و یا از او پس گرفته می شود.
برنامه نویسان به طور سنتی از قفل ها برای ناحیه بحرانی استفاده می کنند. ناحیه بحرانی بلوکی از کد می باشد و دارای
متغیرهایی که قابل دسترسی توسط چند پردازنده است، که قفل ها اجازه دسترسی به ناحیه بحرانی را به یک پردازنده می
دهند.
زمانی که یک پردازنده تلاش می کند به ناحیه بحرانی دسترسی پیدا کند باید اول قفل آن قسمت را باز کند در
صورتی که پردازنده ای در آن لحظه قفل را در اختیار داشته باشد، پردازنده دیگری نمی تواند تا زمانی که پردازنده قبلی
قفل را رها نکرده به آن قسمت دسترسی یابد. در حالی که قفل ها مشکل دسترسی به داده یکسان را در یک زمان حل می
کنند، دارای نقایصی در زمینه عملکرد و سادگی به کارگیری می باشند. مدیریت قفل ها مشکل است، استفاده نادرست از قفل ها می تواند نتیجه ای ناسازگار با چیزی که ما می خواهیم
تولید کند به عنوان مثال بن بست زمانی اتفاق می افتد که پروسه1 در حال انتظار برای دریافت قفلی می باشد که در
اختیار پروسه2 است، و پروسه2 هم نیاز به دریافت قفلی دارد که در اختیار پروسه1 هست و اولویت معکوس، زمانی روی
می دهد که یک پروسه با اولویت پایین در گرفتن قفل پیشدستی کند در حال که قفل مورد نیاز پروسه ای با اولویت بالاتر
است.
مشکل دیگر در مورد قفل ها این است که برای افزایش همزمانی، قفل گذاری با اندازه بندی مناسب مورد نیاز می
باشد این امر ممکن است منجر به پیچیدگی کد به سبب به دست آوردن و رها نمودن قفل های متعدد در موقعیت های
بسیار باشد مثلا استفاده نادرست از قفل های درشت دانه منجر به کاهش موازی سازی می شود و یا به منظور افزایش
کارایی به قفل های ریزدانه نیاز داریم که به کار بردن هر چه بیشتر قفل های ریزدانه باعث ایجاد سربار و همراه با خطا
هست که اشکال زدایی آن نیز مشکل است. بنابراین استفاده از قفل ها مشکلات زیادی را به همراه دارند و نیاز به یک مدل
همزمانی بهتر برای نرم افزارهای چند هسته ای داریم. حافظه تراکنشی در حال توسعه برای تبدیل شدن به مهمترین ابزار
هماهنگ سازی در برنامه نویسی همزمان است و می تواند جایگزین همزمان سازی مبتنی بر قفل ها باشد.
حافظه تراکنشی در رابطه با برنامه نویسی برنامه های موازی است و برای برنامه نویسی همزمان تلاش می کند. در صورت استفاده از حافظه تراکنشی سطح موازی سازی افزایش می یابد، برنامه های موازی را با استخراج گروهی از دستورات برای تراکنش های اتمیک9 ساده می کند بنابراین کارایی هم افزایش می یابد. با قفل های محدود کننده دسترسی به سیستم، تنها یک نخ می تواند در یک زمان یک قفل را نگه دارد در حالی که در بیشتر پیاده سازی های حافظه تراکنشی بیشتر از یک نخ می تواند به منابع دسترسی داشته باشد.
مفاهیم
هرلی و موس [3]، حافظه تراکنشی سخت افزاری را به عنوان راهکاری برای همگام سازی داده ها بدون نیاز به قفل ها پیشنهاد دادند و از آن زمان حافظه تراکنشی به عنوان موضوعی قابل توجه در بین محققان مطرح بوده است. حافظه تراکنشی دارای ریشه هایی در مدیریت تراکنش در سیستم های پایگاه داده همزمان است. تراکنش یک زنجیره ای از دستورالعمل هاست که شامل خواندن و نوشتن از حافظه است و دارای خواص اتمیک، سازگاری10، ایزوله بودن11، ماندگاری12 هست. سه مفهوم تکمیل نهایی13، لغو14، اعتبار15، در ارتباط با تراکنش است. . به عنوان نمونه این تراکنش را در نظر بگیرید.
Typical Transaction (1)
/* keep trying */ While ( true ) { /* read variables */
Y1 /7 ( 91 ); …; YQ /7 ( 9Q );
/* check consistency */ if ( > VALIDATE ( ) ) continue; /* compute new values */ FRPSXWH ( Y1' … ' YQ);
/* write tentative values */
67 (Y1' 91); … 67(YQ' 9Q);
/* try to commit */ if ( COMMIT ( ) ) return result; else backoff;
اتمیک ، به معنای این است هنگامی که یک تراکنش با موفقیت انجام می شود یا به اصطلاح تکمیل نهایی شود، در این حالت تمام نوشته هاش قابل رویت می شود و تراکنش های دیگر می توانند از آن استفاده کنند و هنگامی که یک تراکنش ناموفق می ماند، سیستم همه نوشته های مربوط به آن را از رده خارج کرده و به حالت قبل برگشت داده می شود.
در ناحیه بحرانی، آن قسمت از کد که می خواهیم توسط یک تراکنش، به صورت اتمیک اجرا شود، باید توسط نشانه های شروع 16 و پایان17 احاطه شده باشد. زمانی که داخل یک تراکنش هستیم، هر تلاشی برای خواندن یا نوشتن در حافظه اجرا نمی شود، بلکه در یک نوع لیست ذخیره می شود و زمانی که تراکنشی به پایان می رسد، سیستم بررسی می کند تا ببیند مکان هایی از حافظه که در تراکنش مورد دسترسی قرار گرفته اند آیا توسط پردازنده دیگری در زمانی که تراکنش در حال اجرا بوده، مورد تغییر قرار گرفته اند یا خیر؟ در صورتی که تعارضی (تعارض به معنای نقض ترتیب زمانی می باشد و زمانی اتفاق می افتد که دو یا چند تراکنش می خواهند با هم بر روی بخش های یکسانی از حافظه مشترک عملیاتی انجام دهند) مشاهده نشود، تراکنش آزاد است که تمام اصلاحات حافظه خود را از لیست انجام داده و آن گاه خارج شود.
در صورت مشاهده تعارض، تراکنش لیست را خالی کرده و به اول تراکنش باز می گردد و این بازگشت باعت می شود که به نظر برسد ناحیه بحرانی هیچ گاه اجرا نشده است. به کار گیری حافظه تراکنشی بدین گونه، اجرای بهینه نام دارد. این روش بهینه تلقی می گردد چون در صورتی که به یک نشانه شروع تراکنش برسیم، سیستم وارد تراکنش شده تا بتواند تمام تغییرات را در پایان انجام دهد و تکمیل نهایی شود. بنابراین این نکته حائز اهمیت است که تراکنش به دسترسی به هر گونه قفلی نیاز ندارد به سادگی و با سرعت اجرا شده و هر گونه خواندن یا نوشتن در حافظه را به لیست منتقل می نماید. مرحله تاییدی انجام شده در پایان، صحت لیست را قبل از این که تغییرات تکمیل نهایی شود بررسی می کند. برای بررسی نمودن صحت لیست، سیستم باید هر متغیری که خوانده یا نوشته شده را بررسی کند تا از هماهنگی مقادیر آنها با زمانی که تراکنش آغاز شده است اطمینان حاصل کند.
این وظیفه قسمت اجرایی است که از انجام شدن مرحله تایید تراکنش به صورت اتمیک اطمینان حاصل نماید. به طور کلی، این راه حلی مشخص برای برنامه نویسی موازی می باشد، چون همزمانی فقط با احاطه کردن تمام نواحی بحرانی با نشانه های شروع و پایان تراکنش انجام می شود. متاسفانه، حافظه تراکنشی دارای محدودیت های بزرگی است که باعث شده هنوز قفل ها به طور کامل جایگزین نشوند. یکی از این محدودیت ها، کارایی می باشد. زمانی که یک تراکنش بازگشت می یابد، تمام کاری که انجام داده از بین می رود.
کاسکاوال و همکارانش [4]، اظهار می کنند که سیستم های حافظه تراکنشی باید نتایجی هماهنگ بر جای گذارند و بدون ایجاد خطاهای غیر قابل پذیرش باشد که منجر به کندی سیستم ها نشود که این حاکی از توانایی آنها در کار کردن است.
به طورکلی از حافظه تراکنشی چه انتظاری داریم ؟
یک سیستم حافظه مشترک با : مدل برنامه نویسی ساده، پیاده سازی سخت افزاری با پیچیدگی کم، کارایی خوب
.3 انواع پیاده سازی حافظه تراکنشی
یک موضوع مهم در حافظه تراکنشی این است که آیا باید تراکنش را در سخت افزار انجام داد یا در نرم افزار؟ این
قسمت به بررسی به کارگیری آن در هر دو روش می پردازد و مزایا و معایب هر روش را بررسی می کند. کارهای انجام
شده روی اجرای ترکیبی نیز مورد بحث قرار گرفته است.
.3.1 حافظه تراکنشی سخت افزاری18
در سال 1993، هرلی و موس [3]، راهی بسیار هوشمندانه برای به کارگیری حافظه تراکنشی در سخت افزار
پیشنهاد دادند. آنها این کار را با ویرایش پروتکل های همبستگی کش چند پردازنده ای با هدف کارایی برای حافظه
تراکنشی انجام دادند. پروتکل های همبستگی کش چند پردازنده ای از این که پردازنده های متفاوت نتوانند مقادیر
ناهماهنگ مربوط به مکانی یکسان در حافظه را در کش خود نگهداری نمایند، اطمینان حاصل می نمایند. هرلی و موس
پیشنهاد دادند هر پروتکلی که قادر به شناسایی تعارض ها در دسترسی ها باشد پس تعارض های تراکنشی را هم می تواند
شناسایی کند.
شیوه اجرای شرح داده شده در [3]، شامل دستورالعمل های دسترسی به حافظه است :
تراکنش بار19، تراکنش باری انحصاری20، تراکنش ذخیره21 تراکنش بار، مقدار یک مکان حافظه مشترک را خوانده و در یک ثبات اختصاصی ذخیره می کند، تراکنش باری
انحصاری نیز همین کار را انجام می دهد با این تفاوت که مکان بروز رسانی خواهد گشت و تراکنش ذخیره هم از ثبات اختصاصی به داخل حافظه می نویسد، ولی تغییرات را برای دیگر پردازنده ها آشکار نمی کند تا زمانی که تراکنش تکمیل نهایی شود.
در پروتکل های همبستگی کش چند پردازنده ای، دسترسی ها ممکن است غیرانحصاری (اجازه خواندن اطلاعات) یا انحصاری (اجازه نوشتن) باشد. در هر لحظه، یک مکان از حافظه بلافاصله توسط هر پردازشگری در دسترس نمی باشد یا به صورت غیرانحصاری توسط یک یا چند پردازنده و یا به صورت انحصاری توسط یک پردازنده در دسترس می باشد به عنوان مثال در صورتی که پردازنده 1 دارای دسترسی غیر انحصاری با مکانی در حافظه باشد و پردازنده 2 بخواهد که داده ها را در آن مکان ذخیره کند در این صورت پردازنده 2 باید دسترسی انحصاری را به دست آورد و این کار را با لغو نمودن دسترسی پردازنده 1 انجام می دهد. اجرای حافظه تراکنشی سخت افزاری توسط هرلی و موس هر گونه تراکنشی را که سعی به لغو نمودن دسترسی یک ورودی تراکنشی از تراکنش فعالی دیگر داشته باشد را متوقف می نماید.
با گسترش پروتکل اسنوپی گودمن برای یک باس اشتراکی [5]، هرلی و موس هر پردازنده را وادار به حفظ یک
کش منظم و تراکنشی می نمایند. کش تراکنشی تمام نوشتن های موقتی را نگاه داشته و تنها در موردی که تراکنش
تکمیل نهایی شود، تغییرات را به دیگر پردازنده ها یا حافظه مشترک انتقال می دهد. آنها هر خط کش تراکنشی را با یکی
از حالتهای تراکنشی، خالی22 (داده ای نیست)، عادی23 (شامل داده تکمیل نهایی)، پایه تکمیل نهایی24 (توقف بر روی داده
تکمیل نهایی)، پایه لغو25 (توقف بر روی تغییرات لغو شده) مجهز می نمایند.
عملیات تراکنشی آنگاه دو ورودی را در کش قرار داده است که یکی با نشانه پایه تکمیل نهایی و دیگری با نشانه پایه
لغو آغاز می گردد. تمام تغییرات با ورود به پایه لغو انجام شده و به محض این که تکمیل نهایی شد، ورودی های مشخص
شده با پایه تکمیل نهایی روی حالت خالی و ورودی های مشخص شده با پایه لغو روی حالت عادی قرار می گیرند. در
صورت درخواست لغو تراکنش، ورودی های مشخص شده در پایه لغو برابر با خالی و ورودی های مشخص شده در پایه
تکمیل نهایی روی حالت عادی تنظیم می گردند. در یک چرخه باس، کش مانند یک کش عادی عمل می کند، با این
تفاوت ورودی هایی که عادی نباشند را اجرا نمی کند و از انتقال تمام تغییرات به حافظه مشترک در صورت انجام تراکنش
اطمینان حاصل می کند.
البته این روش دارای مکانیزمی برای لغو تغییرات در صورت ایجاد تراکنش متعارض می باشد که این کار با وادار ساختن هر پردازنده به داشتن دو نشان انجام می گیرد : نشان تراکنش فعال26 (آیا تراکنش فعال می باشد؟)، و نشان تراکنش لغو شده27 (آیا تراکنش فعال لغو شده است؟). تراکنش فعال، در هر زمانی که یک تراکنش اولین عملیات تراکنشی خود را انجام دهد روی حالت درست28 تنظیم می گردد. در زمان اعمال تراکنش بار، کش تراکنشی برای یافتن یک ورودی پایه لغو، مورد جستجو قرار می گیرد (این ورودی ویرایش شده ولی هنوز اعمال نشده است) در صورتی که ورودی پایه لغو برای مکان حافظه پیدا نشود ولی یک مورد عادی وجود داشته باشد، آنها حالت را از عادی به پایه لغو تغییر می دهند و یک ورودی دوم با داده های مشابه ایجاد کرده و وضعیت پایه تکمیل نهایی را به آن الحاق می نمایند.
در صورتی که ورودی عادی نیز موجود نباشد، داده از حافظه خوانده شده و ورودی های پایه تکمیل نهایی و پایه لغو به صورت ذکر شده در خواهند آمد. در صورتی که این خواندن حافظه به علت ایجاد یک تعارض با شکست مواجه گردد، تراکنش لغو شده برابر با نادرست29 تنظیم می گردد، تمام ورودی های پایه لغو رها شده و تمام ورودی های پایه تکمیل نهایی برابر با عادی می شوند. دستورات تراکنش باری انحصاری و تراکنش ذخیره هم به شیوه بسیار مشابهی عمل می نمایند. در صورتی که اعتبار سنجی اجرا گردد، اگر تراکنشی که لغو شده برابر با نادرست باشد، تراکنش فعال برابر با نادرست قرار داده شده و تراکنش لغو شده برابر با حالت درست قرار می گیرد (این کار تراکنش را لغو می کند). زمانی که تراکنش لغو گردد، ورودی های کش تراکنشی نیز لغو می شوند و تراکنش فعال برابر با نادرست تنظیم شده و تراکنش لغو شده برابر با درست قرار می گیرد. ولی در صورتی که تکمیل نهایی اجرا گردد، تراکنش لغو شده برابر با درست و تراکنش فعال برابر با نادرست قرار میگیرد، و تمام ورودی های پایه لغو روی حالت عادی تنظیم می شوند (تا بتوان آنها را در چرخه باس بعدی خواند).
این ایده استفاده از پروتکل های همبستگی کش برای به کارگیری حافظه تراکنشی سخت افزاری بسیاری تحقیقات را در این زمینه آغازگر شد. متاسفانه نقایصی در مورد حافظه تراکنشی سخت افزاری وجود دارد که هنوز مشکلاتی اساسی تلقی می گردد.
.3.1.1 راههای دیگر برای به کارگیری حافظه تراکنشی سخت افزاری ویکی پدیا [6]، در مورد حافظه تراکنشی می گوید که عملیات لینک بار30 و ذخیره شرطی31 را می توان به عنوان
اصلی ترین پشتیبان از حافظه تراکنشی در سخت افزار نام برد. لینک بار مقدار یک مکان حافظه را مشخص می کند و ذخیره شرطی، مقداری جدید را در صورت عدم انجام هر گونه بروز رسانی در آن مکان از زمان اجرای آخرین لینک بار، ذخیره می نماید این نمونه ای از یک عملیات بروز رسانی و اجرای ساده می باشد البته این عملیات روی داده های به اندازه
