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 ماشین مجازی بر روی یک ماشین سختافزاری Ik باشد. ثابت میکنیم که اگر یک ماشین مجازی دیگر به این مجموعه ماشین مجازی اضافه شود، میزان تداخل ماشینهای مجازی که با عدد Ik+1 نمایش میدهیم افزایش مییابد به عبارت دیگر ثابت میکنیم که Ik<Ik+1
دو تابع و را به صورت زیر تعریف میکنیم:
(۴-۱۰) |
|
منبع فایل کامل این پایان نامه این سایت pipaf.ir است |