ارایه‏ی یک الگوریتم مقیاس‎پذیر آگاه از بارکاری جهت زمان‏بندی ماشین‏های مجازی- قسمت …

Section2

Phase 1

Phase 2

Find lowest interference for each PM and assign selected VM to the specific PM.

شبه‏کد الگوریتم DVMS
الگوریتم ارایه‏شده از که این پس DVMS[85] نامیده می‏شود، از دو بخش کلی تشکیل شده است که هر بخش شامل فازهای مختلفی می‏باشد.شبه‏کد این الگوریتم در شکل شماره‏ی (۴-۱) نشان داده شده است. برای توضیح این الگوریتم فرض می‏کنیم که n ماشین مجازی داریم که قرار است بر روی m ماشین فیزیکی زمان‏بندی شوند. به مجموعه ماشین‏ها مجازی که بر روی ماشین فیزیکی زمان‏بندی شده باشند، مجموعه ماشین‏های مجازی زمان‏بندی شده و به بقیه ماشین‏های مجازی زمان‏بندی نشده می گوییم
بخش اول
هدف این بخش یافتن ماشین‏هایی با بیشترین تداخل است به این منظور که این ماشین‏های مجازی بر روی ماشین‏های فیزیکی جداگانه‏ای اجرا شوند.
فاز اول : در این فاز نخست میزان تابع تداخل به ازای هر دو ماشین مجازی محاسبه می‏شود و نتیجه در یک ماتریس ذخیره می‏شود. به این ماتریس، ماتریس تداخل می گوییم.
فاز دوم: از میان درایه‏های ماتریس تداخل تعداد  درایه‏ی بیشینه را انتخاب می نماییم. ماشین‏هایی که متعلق به این درایه‏ها می‏باشند را یافته و آن‏ها را به ماشین‏های فیزیکی منتسب می‏نماییم. در پایان این فاز m ماشین مجازی به m ماشین فیزیکی به صورت یک به یک منتسب شده‏اند. شکل (۴-۲) این فرایند را نمایش می‏دهد. ممکن است در بین m درایه با بیشینه تداخل، ماشین‏های مشترکی نیز وجود داشته باشند. مثلا ماشین‏های i,j و ماشین‏های i,k در گروه ماشین‏های با تداخل بیشتر باشند. در این حالت ماشین i و j به دو ماشین فیزیکی جداگانه منتسب می‏شوند و در مرحله‏ی بعد ماشین k به یک ماشین فیزیکی متنسب می‏شود، ماشین i هم که قبلا منتسب شده است. بنابراین باید تعداد بیشتری از درایه‏های نشان‏دهنده‏ی تداخل بیشتر در ماتریس تداخل را انتخاب نمود. فرآیند انتخاب درایه‏ها مادامی که تعداد ماشین‏های مجازی مجزا به عدد m برسد ادامه پیدا می‏کند.
فاز دوم از بخش اول الگوریتم
فاز سوم: در این مرحله از روی ماتریس تداخل، و از مجموعه ماشین‏های زمان‏بندی نشده، m ماشین انتخاب می نماییم که با m ماشین زمان‏بندی شده از مرحله‏ی قبل کمترین تداخل را داشته باشند. این ماشین‏های مجازی را به ماشین‏های فیزیکی متناظر منتسب می‏کنیم. در این مرحله تعداد ۲×m ماشین مجازی زمان‏بندی شدند. اگر تعداد ماشین‏های مجازی یعنی n کمتر از ۲×m باشند، پس از پایان این مرحله مجموعه‏ی ماشین‏های زمان‏بندی نشده تهی خواهد بود و ماشینی برای زمان‏بندی وجود نخواهد داشت در نتیجه الگوریتم به پایان می‏رسد. در غیر این صورت وارد بخش دوم الگوریتم می‏شویم
بخش دوم:
در این بخش در فاز نخست ماتریس تداخل را بین m مجموعه ماشین‏های مجازی زمان‏بندی شده بر روی ماشین‏های سخت‏افزاری و مجموعه ماشین‏های مجازی زمان‏بندی نشده محاسبه می‏نماییم. در فازدوم کمترین میزان تداخل بین ماشین‏های مجازی زمان‏بندی نشده و مجموعه ماشین‏های زمان‏بندی شده بر روی هر ماشین سخت‏افزاری را یافته و ماشین مجازی متناظر را مجموعه‏ی ماشین‏های مجازی زمان‏بندی شده بر روی ماشین سخت‏افزاری متناظر اضافه می‏نماییم. این بخش را تا زمانی که مجموعه‏ی ماشین‏های مجازی زمان‏بندی نشده غیر تهی باشد تکرار می‏‏‏نماییم. شکل(۴-۳) این فرایند را نمایش می‏دهد.
بخش دوم الگوریتم DVMS
از آن‏جا که در این بخش ماشین‏های زمان‏بندی نشده یکی یکی به مجموعه‎ی ماشین‏های زمان‏بندی شده افزوده می‏شوند جهت بالاتر بردن سرعت الگوریتم و با توجه به قضیه‏ای که در ادامه اثبات می‏گردد. راه‏کاری اتخاذ می‏گردد که در هر مرحله m ماشین مجازی زمان‏بندی نشده، زمان‏بندی شوند.
قضیه
فرض می‏کنیم میزان تداخل k ماشین مجازی بر روی یک ماشین سخت‏افزاری Iباشد. ثابت می‏کنیم که اگر یک ماشین مجازی دیگر به این مجموعه ماشین مجازی اضافه شود، میزان تداخل ماشین‏های مجازی که با عدد Ik+1 نمایش می‏دهیم افزایش می‏یابد به عبارت دیگر ثابت می‏کنیم که Ik<Ik+1
دو تابع  و  را به صورت زیر تعریف می‏کنیم:

(۴-۱۰)
منبع فایل کامل این پایان نامه این سایت pipaf.ir است