بخشی از مقاله
نظریه بازی ها و کاربرد آن در توازن بار در محیط رایانش ابری
چکیده
اینترنت از ابتدای آغاز کار خود تاکنون دستخوش تحولات فراوانی شده است که بعضی از آنها موجب تغییر شیوه زندگی بشر در چند دهه اخیر گشته است. یکی از جدیدترین تغییرات در نحوه کارکرد اینترنت، با معرفی رایانش ابری صورت پذیرفته است. در این فناوری جدید، همه نوع امکانات به کاربران، به عنوان یک سرویس ارائه شده است. طبیعتاً هر تغییر و مفهوم جدیدی در دنیای فناوری، مشکلات و پیچیدگیهای خاص خود را دارد. بهرهگیری از رایانش ابری نیز از این قاعده مستثنی نبوده و چالشهای فراوانی را پیش روی صاحب نظران این حوزه قرار داده است که از آن جمله میتوان به مواردی نظیر: توازنبار، امنیت، قابلیت اطمینان و پشتیبانگیری از دادهها اشاره کرد. مسئله توازنبار جزء مسائل غیر چندجملهای کامل است و به همین دلیل مورد توجه بسیاری از پژوهشگران قرار گرفته است تا بتوانند راهحلهای بهینهای برای آن بیابند. راهحلهای متنوعی نیز برای حل این مسئله ارائه شده است که هریک از این روشها دارای ویژگیهای خاصی هستند و ممکن است از توابع سود مختلفی برای حل مسئله توازنبار استفاده کنند. یکی از روشهای مدلسازیریاضی که در سالهای اخیر بسیار مورد توجه محققین حوزههای مختلف علوم مهندسی نیز قرار گرفته است نظریهبازیها میباشد. در این پژوهش، امکان بکارگیری نظریه بازیها برای حل مسئله توازنبار در محیط رایانش ابری مورد بررسی قرار گرفته است. مسئله توازنبار از جهات بسیاری شبیه مدلهای بازی موجود در نظریه بازیها است و همین نکته میتواند از دلایل اصلی برای گرایش محققان به سمت نظریه بازیها برای حل این مسئله باشد. همچنین در الگوریتمهای توازنبار، تصمیماتی که هر یک از اجزای موجود در سیستم اتخاذ میکنند وابسته به تصمیمات سایر اجزا است. با وجود شباهتهای زیادی که بین مسئله توازنبار و مدل نظریه بازیها وجود دارد اما پژوهشهای زیادی برای حل این مسئله با استفاده از نظریه بازیها صورت نگرفته است. هدف از این پژوهش معرفی و ارائه قوانین و راهکارهای
مبتنی بر نظریه بازیها برای توازنبار در محیط رایانش ابر میباشد.
واژههای کلیدی: رایانش ابری، توازنبار، نظریه بازیها، سیستمهای کامپیوتری توزیع شده.
.1 مقدمه
پیشرفتهای موجود در تکنولوژیهای سختافزاری و نرمافزاری، باعث افزایش تمایل بشر به سمت سیستمهای موازی با مقیاس بزرگ و سیستمهای توزیع شده، برای کاربردهای بلادرنگ، نظامی، محاسباتی و کاربردهای تجاری مقیاس بزرگ، شده است. سیستم عامل و مدیریت پردازشهای ورودی، بخشهای اصلی سیستمهای توزیعشده و موازی را تشکیل میدهند. یکی از مهمترین مباحث مطرح در طراحی اینگونه سیستمها، استفاده از روشهای مناسب برای توزیع فرآیندهای یک برنامه موازی در چندین پردازنده است. این مسئله عبارت است از چگونگی توزیع فرآیندها در بین عناصر پردازشی، برای دستیابی به هدف یا اهداف کارایی؛ مانند کاهش مدت زمان اجرای وظایف، کاهش تاخیرهای ارتباطی و یا افزایش بهرهوری منابع. از دید سیستمی، انتخاب روش توزیع فرآیندها، از مسائل مربوط به مدیریت منابع است و باید به عنوان یک عامل تاثیرگذار در طول فازهای طراحی سیستمهای چند پردازندهای در نظر گرفته شود .[1]
یک سیستم رایانش ابری اغلب از مجموعهای از منابع محاسباتی و ارتباطی ناهمگن تشکیل شده است. با توجه به تفاوتهای ممکن در ظرفیتهای محاسباتی و ورود کارها با الگوهای غیرقابل پیشبینی، حجم بار در کامپیوترهای مختلف میتواند به میزان قابل توجهی تفاوت داشته باشد. بهبود کارایی این نوع از سیستمها با توزیع مناسب حجمبار میان کامپیوترها به توازنبار معروف است. چنانچه بخواهیم یک فرمول کلی برای مسئله توازن بار داشته باشیم میتوان گفت که با فرض داشتن تعداد زیادی کار، هدف از توازنبار، یافتن تخصیصی از کارها در بین منابع کامپیوتری است به گونهای که یک تابع هدف بهینه شود .[2]
طوربه کلی تعاریف مختلفی برای مفهوم توازن بار ارائه شده است. زٌمایا و تِه در [3]، معتقدند که توازنبار در واقع با چگونگی تقسیمبندی یک برنامه به وظایف کوچکتری که میتوانند بهصورت همزمان اجرا شوند و نگاشت هر یک از این وظایف به یک منبع محاسباتی سروکار دارد،. پِنماتسادر[4] و کُرنُپُولُس بیان کردند که توازن بار با استفاده از انتقال بعضی از کارها از منابع محاسباتی که بار سنگینی2 دارند، به منابع بیکار و یا با بار سبک3، حاصل میشود.
.2 انواع روشهای توازنبار
روشهای توازنبار در سیستمهای کامپیوتری بر اساس چگونگی بدست آوردن پارامترهای مورد نیاز برای حل این مسئله، قابل تقسیمبندی به دو دسته کلی روشهای ایستا4 و پویا5 هستند. روشهای توازن بار ایستا از اطلاعات سیستم به عنوان پارامترهای ورودی خود استفاده نمیکنند و یا تنها از رفتار تقریبی سیستم استفاده میکنند .[5] در واقع روشهای توازنبار ایستا، از یک دانش اولیه از برنامهها و اطلاعات ایستا راجعبه سیستم استفاده مینمایند.
روشهای توازنبار پویا بر طبق تصمیمات انجام شده در همان لحظه از سیستم، عمل میکنند. به عبارت دیگر، روشهای توازنبار پویا، با در نظر گرفتن حالت سیستم در هر لحظه، از اطلاعات آن لحظه (به صورت زمان اجرا(6 در محاسبات مربوط به تخصیصکار استفاده میکنند .[5]
با توجه به اینکه روشهای توازن بار پویا از اطلاعات حالت سیستم به صورت لحظهای استفاده میکنند، از دقت بالاتری برخوردار خواهند بود. اما دستیابی به اطلاعات لحظهای از حالت سیستم، سربار زیادی را به سیستم وارد میکند که باعث افزایش هزینه مربوط به الگوریتم توازن بار خواهد شد. با افزایش هزینههای مربوط به سربار تعویض اطلاعات حالت سیستم در روشهای توازنبار پویا، روشهای توازنبار ایستا میتوانند در مقایسه با روشهای پویا عملکردی برابر و یا حتی بهتر داشته باشند.
.3 معیارهای ارزیابی الگوریتمهای توازنبار
معیارهایی برای ارزیابی کارایی یک الگوریتم توازنبار و همچنین مقایسه آن با سایر الگوریتمهای موجود برای حل این مسئله در نظر گرفته شده است. در این راستا معیارهای متعددی ارائه شدهاند که هر یک از آنها با در نظر گرفتن جنبههایی از عملکرد سیستم، سعی در تعیین کارایی سیستم با بهکارگیری یک روش توازنبار دارند. به عنوان مثال اهداف مورد انتظار از یک راهحل توازنبار میتواند شامل موارد زیر باشد 1]، 3، 6، 7، .[8
- کاهش بیشترین مقدار حجمبار کامپیوترها:7 هدف یک الگوریتم توازنبار، توزیع عادلانه کارها در بین منابع موجود در سیستم است. به همین دلیل پارامتر کاهش بیشترین مقدار حجمبار کامپیوترها که به توزیع یکنواخت کارها در سیستم کمک میکند، مهمترین هدف یک الگوریتم توازنبار است 5]، 8، .[9
-کاهش مدت زمان پاسخ مورد انتظار:8 مدت زمان پاسخ مورد انتظار یک کاربر، بر اساس فاصله زمانی پیشبینی شده در الگوریتم توازنبار، بین ورود کار به سیستم و دریافت پاسخ خروجی سیستم از این کار، محاسبه میشود 5]، .[6
- برقراری عدالت9 در سیستم: براساس این معیار، الگوریتم توازنبار تضمین میکند که همه کارها به میزان تقریبا یکسان و برابری از منابع موجود در سیستم استفاده میکنند .[10] زمانی که سیستم کامپیوتری چند کاربره باشد (مانند سیستمهای رایانش ابری)، در نظر گرفتن این پارامتر در سیستم، به توزیع عادلانه کارهای همه کاربران کمک زیادی میکند.
- افزایش بازدهی سیستم:10 بازدهی سیستم کامپیوتری نشان دهنده میزان استفاده بهینه از منابع محاسباتی موجود در سیستم است که براساس نسبت مدت زمان پردازش منابع محاسباتی، به مدت زمان بیکار بودن آنها در سیستم محاسبه میشود .[6]
ممکن است بعضی از این اهداف در تناقض با یکدیگر باشند. در اغلب روشهای توازنبار، یک یا چند معیار برای ارزیابی کارایی روش توازنبار مورد ارزیابی قرار میگیرد.
.4 نظریه بازیها
همه ما انسانها در طول روز با شرایط و مسائلی روبرو میشویم که حاصل اعمال افراد مختلف هستند. همچنین اعمال ما در موارد مختلف میتواند در نتیجه اعمال افراد دیگر تاثیر بگذارد و سبب تعیین و یا تغییر اعمال صورت گرفته توسط آنها شود، که بازی11 مینامیم. یک بازی با یک تصمیمگیری فردی متفاوت است. در تصمیمگیری فردی، عملی که عامل انجام میدهد بدون در نظر گرفتن تصمیمات و اعمال سایر عاملها و منظور کردن آنها در تصمیمات خود است، زیرا پیامدی که فرد از نتیجه تصمیم خود میگیرد، وابسته به تصمیمات سایر افراد نیست. اما در یک بازی، عملی که هر عامل انجام میدهد روی اعمال سایر عاملهای موجود در محیط بازی تاثیر متقابل دارد و میتواند سایر عاملها را تحریک کند تا بر اساس آن، عمل و تصمیم خود را عوض کنند و حتی نسبت به تصمیم عامل متقابل خود واکنش نشان دهند.
در توصیف مفهوم نظریهبازیها، تعاریفمختلفی ارائه شده است. آاُمن [11]، نظریهبازیها را در مطالعه مدلهای ریاضی تقابل12 و تعامل13 بین تصمیم گیرندههای عاقل و هوشمند معرفی میکند. بنابر تعریف آزیورن [12]، نظریهبازیها مجموعهای از ابزارهای تحلیلی است که برای کمک به درک پدیدهای که در آن تعدادی تصمیمگیرنده باهم در تقابل هستند، طراحی شده است. همچنین راسمسُن [13]، در کتاب خود بیان میکند که نظریهبازیها بر روی اعمال تصمیم گیرندههای هوشیاری تمرکز دارد که به این
واقعیت واقف هستند که اعمال آنها بر روی سایر تصمیمگیرندهها تاثیر میگذارد.
نظریهبازیها علمی است که به مطالعه تصمیمگیری افراد در شرایط تعامل با یکدیگر میپردازد .[14] هدف اصلی نظریه بازیها، ایجاد نگرش و دیدگاه است که براساس آن بازیکنان بایستی عاقلانه رفتار کنند. منظور از عاقلانه رفتار کردن این است که عامل قبل از اینکه دست به انجام عملی بزند، بهطور عمیق درباره آن فکر کند و هدف، ترجیحات و قیود خود را در نظر بگیرد، سپس عمل را مبتنی بر قاعدهای انتخاب کند که در راستای منافع او باشد. هدف از نظریهبازی آموزش اسرار محرمانهای نیست که سبب شود در تعامل با دیگران هرگز دچار ضرر نشویم، زیرا مطمئناً حریف نیز میتواند نظریهبازیها را مطالعه کند. ادعای نظریهبازیها این است که میتواند اصول عمومی را به فرد آموزش دهد تا با توجه به عوامل تاثیرگذار در یک بازی، براساس آن اصول تصمیم مناسبی را اتخاذ نماید .[14]
.5 توصیف بازی
عناصر اصلی یک بازی شامل بازیکنان14، عملها15، سود 16 و اطلاعات 17 هستند، مجموعه این عناصر به عنوان قوانین بازی18 شناخته میشوند. در مدلسازی با استفاده از نظریهبازیها، هدف طراحی شرایطی براساس قوانین بازی است تا بیان شود که در این شرایط چه اتفاقاتی رخ خواهد داد. بازیکنان با تلاش برای افزایش مقدار سود خود در بازی، تصمیماتی را اتخاذ میکنند که به آنها استراتژی19 گفته میشود. هر بازیکن براساس استراتژی خود اعمالی را طبق اطلاعاتی که در آن لحظه در فضای مسئله بهدست آورده است، انجام میدهد. به مجموعه استراتژیهای اتخاذ شده توسط بازیکن در بازی، نمایه استراتژی20 گفته میشود و مجموعه نمایه استراتژیهای تمام بازیکنان بازی، نمایه استراتژی بازی نامیده میشود. در نظریهبازی فرض میشود که بازیکنان دارای عقلانیت هستند، به این معنا که هر بازیکن سعی میکند براساس اطلاعاتی که از شرایط محیط و اعمال سایر بازیکنان به دست آورده است، استراتژیی را انتخاب کند که به بیشترین مقدار سود ممکن دست یابد. برای رفتار عقلانی دو شرط لازم است 12]، .[13
-1 بازیکن نسبت به پیامد بازی آگاهی و دانش کامل داشته باشد.
-2 بازیکن از استراتژی انتخابی که در راستای منافع او خواهد بود، محاسبه دقیق و بی عیبی داشته باشد.
ترکیبی از استراتژیهای انتخاب شده توسط هر یک از بازیکنان، توازن21 نامیده میشود. بنابراین در توازن، هر بازیکن استراتژیی را به کار میبرد که بهترین پاسخ به استراتژیهای انتخابی توسط سایر بازیکنان باشد. در توازن لزوماً همه شرایط برای بازیکنان در بهترین حالت نیست؛ به عبارت دیگر، در توازن لزوماً همه بازیکنان به بیشترین سود دست پیدا نمیکنند. حتی ممکن است تعامل استراتژیک میان بازیکنان منجربه نتیجهای شود که برای تمام آنها بدتر باشد. همچنین زمانی که تعداد بازیکنان و یا تعداد استراتژیهای آنها افزایش یابد، یافتن توازن پیچیدهتر میشود. طراح بازی با داشتن توازن، میتواند مشاهده کند که چه اعمالی از اتصال تصمیمات اتخاذ شده توسط همه بازیکنان بهدست آمده است و در نتیجه خروجی بازی را بررسی نماید 13]، .[14
.6 انواع بازیها
مدل یک بازی نشان دهنده انتزاعی از وضعیت محیط واقعی است. بنابر حالات و شرایط مختلفی که ممکن است در محیط واقعی رخ دهد، بازیها را میتوان از جنبههای گوناگون مانند اطلاعات بازیکنان نسبت بهیکدیگر، ترتیب حرکت بازیکنان و همچنین
همکاری یا عدم همکاری بین بازیکنان بازی دستهبندی کرد. در ادامه به انواع بازیها بر اساس دستهبندیهای متفاوت اشاره خواهد شد.
.1-6 بازیهای با اطلاعات کامل22 و اطلاعات ناقص23
اگر هریک از بازیکنان بازی اطلاعات کافی نسبت به حرکت سایر بازیکنان و پیامدهای آنها داشته باشند، در اینصورت آن بازی از نوع بازی با اطلاعات کامل خواهد بود. اما در بازیهای با اطلاعات ناقص ممکن است بازیکنان بازی بهصورت ناقص از حرکت سایر بازیکنان مطلع شوند 12]، .[14
.2-6 بازیهای فرم استراتژیک24 و بسط یافته25
چنانچه در یک بازی، ترتیب حرکت بازیکنان اهمیت نداشته باشد و به عبارتی بتوان فرض کرد که بازیکنان میتوانند همزمان باهم حرکت کنند، بازی از نوع استراتژیک نامیده میشود. بنابراین در بازیهای فرم استراتژیک زمانی که تصمیمی برای انجام حرکت توسط یک بازیکن گرفته میشود، هیچ یک از بازیکنان بازی از آن تصمیم مطلع نخواهند شد. در مقابل اگر ترتیب حرکت بازیکنان در بازی اهمیت داشته باشد، بازی فرم بسط یافته خواهد بود .[12]
.3-6 بازیهای همکارانه26 و غیرهمکارانه27
در همه مدلهای مبتنی بر نظریه بازی، موجودیت اصلی "بازیکن" است. یک بازیکن میتواند بهصورت یک فرد یا گروهی از افراد که یک تصمیم واحد میگیرند، در نظر گرفته شود. با تعریف مجموعه بازیکنان بازی، ممکن است دو مدل زیر از هم متمایز شوند؛ مدلهایی که مجموعه عملهای ممکن بازیکنان انفرادی28، به عنوان عناصر اصلی شناخته میشوند و مدلهایی که مجموعه حرکتهای مشترک گروهی از بازیکنان عناصر اصلی بازی را تشکیل میدهند. در بعضی موارد مدلهای نوع اول به عنوان مدلهای بازی "غیرهمکارانه" و مدلهای نوع دوم به عنوان بازی "همکارانه" شناخته میشوند .[12]
همچنین باید بیان داشت که چنانچه مجموعه استراتژیهای بازیکنان بازی متناهی باشد، آن بازی از نوع متناهی29 و در غیراینصورت نامتناهی30، خواهد بود.
.7 حل بازی
یک بازی استراتژیک مدلی از تصمیمگیری تعاملی است که در آن هر بازیکن تنها یک بار تصمیم برای حرکت میگیرد و این تصمیمات بهصورت همزمان انجام میشود. بهطور کلی یک بازی استراتژیک متشکل از سه جزء اصلی زیر است:
-1 بازیکنها: مجموعه بازیکنها با N نشان داده میشود.
-2 مجموعهای از عملها: برای هر بازیکن i∈N، یک مجموعه غیرتهی از اعمال بهصورت Ai وجود دارد.
-3 ترجیحات:31 هر بازیکن بر روی خروجیهای ممکن بازی، ترجیحات متفاوتی دارد. بهعبارت دیگر، اگر Xj∈NAj نشان دهنده حاصلضرب دکارتی مجموعه استراتژیهای همه بازیکنان بازی، یا هر ترکیبی از استراتژیهای بازیکنان نسبت به استراتژیهای انتخابی سایرین باشد؛ در آن صورت یک رابطه ترجیحی32 با استفاده از نماد ≥ i روی این حاصلضرب دکارتی نشان داده میشود.
جهت بیان بهتر مطلب، در ادامه از یک بازی مشهور در نظریه بازیها به نام معمای زندانیها33، استفاده خواهد شد. سناریوی بازی به این شرح است. دو مجرم را در نظر بگیرید که به دلیل انجام جرم کوچکی دستگیر شدهاند، اما پلیس مظنون به انجام جرم بزرگتری توسط آنها است ولی شواهد کافی برای اثبات اتهام را ندارد. به همین دلیل پلیس میخواهد از روشی استفاده کند تا یکی از مجرمها به دیگری خیانت کند و بتواند از این طریق از آنها اعتراف بگیرد. راهکار پلیس، قرار دادن مجرمها در دو اتاق بازجویی متفاوت و پیشنهاد چند گزینه به آنها است. اگر هیچیک از مجرمها به جرم اصلی اعتراف نکنند، به خاطر انجام جرم کوچک اول، به یک سال زندان محکوم میشوند. اگر یکی از مجرمها اعتراف کند، پلیس از مجرمی که اعتراف کرده گذشت کرده، وی را آزاد میکند و مجرمی که سکوت کرده را به بیست سال زندان محکوم میکند. اگر هر دو مجرم اعتراف کنند، پلیس هر دوی آنها را به پنج سال زندان محکوم میکند.
بازیکنان این بازی مجرمها هستند، به دلیل اینکه هر یک از بازیکنان در اتاقهای مجزا بازجوئی میشوند، از انجام عمل توسط بازیکن مقابل مطلع نیستند و یا میتوان گفت بازیکنان همزمان باهم عمل میکنند. به همین دلیل این بازی از نوع بازی استراتژیک است. همچنین در این بازی هر بازیکن از مجموعهای از اقدامات ممکن توسط سایر بازیکنان بازی و پیامدهای حاصل از انجام هر یک از آنها آگاه است، بنابراین بازی از نوع با اطلاعات کامل میباشد. علاوه بر این، مجموعه اعمال ممکن توسط هر یک از بازیکنان، یک مجموعه محدود را تشکیل میدهد که نشان دهنده متناهی بودن بازی است. بازیهای استراتژیک با اطلاعات کامل را میتوان براساس اطلاعات موجود در بازی بهصورت ماتریس نشان داد. شکل 1-2 ماتریس بازی معمای زندانیها را که شرح داده شد نشان میدهد.
