عنوان : ارایه‏ ی یک الگوریتم مقیاس‎پذیر آگاه از بارکاری جهت زمان‏بندی ماشین‏های مجازی
 
استاد راهنما:  دكتر محسن شریفی
استاد مشاور: مهندس هادی سلیمی
 
اسفندماه 1391
برای رعایت حریم خصوصی نام نگارنده پایان نامه درج نمی شود

(در فایل دانلودی نام نویسنده موجود است)

تکه هایی از متن پایان نامه به عنوان نمونه :

(ممکن است هنگام انتقال از فایل اصلی به داخل سایت بعضی متون به هم بریزد یا بعضی نمادها و اشکال درج نشود ولی در فایل دانلودی همه چیز مرتب و کامل است)

فهرست مطالب

فصل 1: مقدمه و كلیات تحقیق    1

1-1- مقدمه.. 2

1-2- اهداف.. 3

1-3- ساختار پایان‌نامه.. 3

فصل 2: مجازی‏سازی و پردازش ابری    5

2-1- مقدمه.. 6

2-2- تعریف مجازی‏سازی.. 6

2-3- تاریخچه‏ی مجازی‏سازی.. 7

2-4- ناظر ماشین مجازی.. 8

2-5- کاربردهای مجازی‏سازی.. 9

2-5-1- جعبه‏ی شنی … 9

2-5-2- محیط‏های اجرایی چندگانه… 9

2-5-3- سخت‏افزار مجازی… 9

2-5-4- سیستم‏عامل‏های چندگانه همزمان… 9

2-5-5- اشکال‏زدایی… 10

2-5-6- مهاجرت نرم‏افزار… 10

2-5-7- بسته‏ی پیش‏نصب مجازی… 10

2-5-8- تجمیع كارگزار… 10

2-6- سطوح مختلف مجازی‏سازی.. 14

2-6-1- معماری یک سیستم قابل مجازی سازی… 14

2-6-2- مجازی‏سازی در سطح معماری مجموعه دستور… 18

2-6-3- مجازی‏سازی در سطح انتزاع سخت‏افزار… 19

2-6-4- مجازی‏سازی در سطح سیستم‏عامل… 24

2-6-5- مجازی‏سازی در سطح برنامه‏ی کاربردی… 26

2-6-6- مجازی‏سازی در سطح کتابخانه… 29

2-7- پردازش ابری.. 30

2-7-1- تاریخچه… 30

2-7-2- مزایای اقتصادی ابر… 31

2-7-3- انواع ابر پردازشی… 32

فصل 3: تحقیقات مرتبط    33

3-1- مقدمه.. 34

3-2- رویكردهای متفاوت به زمان‏بندی ماشین‏های مجازی.. 34

3-2-1- مزایا و معایب رویکردهای زمان‏بندی ماشین‏های مجازی    36

فصل 4: الگوریتم DVMS   37

4-1- مقدمه.. 38

4-2- ملاحظات زمان‏بندی در یک محیط پردازش ابری.. 38

4-2-1- کارایی… 38

4-2-2- هزینه… 38

4-2-3- همجواری… 39

4-2-4- قابلیت اعتماد و دسترس‏پذیری مستمر… 39

4-3- چالش‏های زمان‏بندی.. 39

4-4- الگوریتم ارایه شده برای زمان‏بندی ماشین‏های مجازی   39

4-4-1- نگاشت مساله‏ی زمان‏بندی به مساله‏ی کوله پشتی… 40

4-4-2- مدل سیستم… 40

4-4-3- فرمول‏بندی مساله… 40

4-4-4- الگوریتم DVMS.. 42

4-4-5- قضیه… 45

4-4-6- بررسی پیچیدگی زمانی الگوریتم:… 47

4-4-7- پیچیدگی فضایی الگوریتم:… 48

فصل 5: ارزیابی الگوریتم ارایه شده    49

5-1- مقدمه.. 50

5-2- شرایط و محدودیت‏های ارزیابی.. 50

5-2-1- مشخصات سخت‏افزاری و نرم‏افزاری محیط ارزیابی… 51

5-3- فرض‏ها و تعریف‏ها.. 51

5-4- بررسی زمان اجرای الگوریتم.. 52

5-4-1- تعداد ماشین‏های فیزیکی ثابت، تعداد ماشین‏های مجازی متغیر    52

5-4-2- تعداد ماشین‏های مجازی ثابت، تعداد ماشین‏های فیزیکی متغیر    55

5-5- مقایسه الگوریتم DVMS با دو الگوریتم پایه.. 56

5-5-1- الگوریتم تصادفی… 57

5-5-2- الگوریتم توازن بار… 57

5-5-3- روش مقایسه الگوریتم DVMS با الگوریتم تصادفی و چرخشی    57

فصل 6: نتیجه‏گیری و كارهای آینده    61

6-1- نتیجه‏گیری.. 62

6-2- کارهای آینده.. 62

منابع    64

 

فهرست شكل‏ها

شکل (1-1) ساختار پایان‌نامه.. 4

شکل (2-1) ناظر ماشین مجازی و ماشین‏های مجازی.. 8

شکل (2-2) تجمیع كارگزارها.. 11

شکل (2-3) مشكل مقیاس‏پذیری تجمیع كارگزارها.. 13

شکل (2-4) سطوح انتزاعی مجازی‏سازی.. 16

شکل (2-5) ساختار ماشین مجازی مستقل.. 21

شکل (2-6) ساختار ماشین مجازی میزبانی.. 22

شکل (2-7) معماری VMware Workstation. 23

شکل (2-8) معماری VMware ESX.. 24

شکل (2-9) یك ماشین با دو jail 26

شکل (4-1) شبه‏كد الگوریتم DVMS. 42

 

شکل (4-2) فاز دوم از بخش اول الگوریتم.. 44

شکل (4-3) بخش دوم الگوریتم DVMS. 45

شکل (4-4) شبه كد محاسبه‏ی تداخل دو به دوی ماشین‏های مجازی   47

شکل (4-5) شبه‏كد تداخل بین ماشین‏های زمان‏بندی شده و ماشین‏های زمان‏بندی نشده.. 48

شکل (5-1) نتیجه‏ی آزمایش شماره 1.. 53

شکل (5-2) نتیجه‏ی آزمایش شماره 2.. 53

شکل (5-3) نمودار تلفیقی دو آزمایش 1و2.. 54

شکل (5-4) نتیجه‏ی آزمایش شماره 3 و4.. 55

شکل (5-5) نتیجه‏ی زمان‏بندی 100 ماشین مجازی.. 56

شکل (5-6) مقایسه‏ی زمان اجرای ماشین‏های مجازی در سه الگوریتم مورد آزمایش.. 58

شکل (5-7) مقایسه‏ی زمان اجرای سه الگوریتم مورد آزمایش.. 59

شکل (5-8) مقایسه‏ی زمان اجرای ماشین‏های مجازی در سه الگوریتم مورد آزمایش بدون زمان اجرای الگوریتم.. 59

شکل (5-9) مقایسه‏ی میزان تداخل ماشین‏های مجازی در سه الگوریتم مورد آزمایش.. 60

شکل (5-10) مقایسه‏ی نسبت تجمیع سه الگوریتم مورد آزمایش با توجه به تعداد ماشین‏های مجازی.. 60

 

 

فهرست جدول‏ها

جدول (2-1) بهره‏و‏ری كارگزارها.. 11

جدول (5-1) مشخصات بستر سخت‌افزاری مورد استفاده در آزمایش‏ها   51

 

 

مقدمه و كلیات تحقیق
 

مقدمه
فناوری مجازی‏سازی به عنوان یک رکن اساسی در سیستم‏های مبتنی بر پردازش ابری[1] و مراکز داده [2]مورد توجه ویژه می‏باشد. مفهوم مجازی‏سازی دارای قدمتی طولانی در دنیای رایانه است و سرآغاز آن به دهه 60 میلادی، برای استفاده‏ی بهینه از توان رایانه‏های بزرگ[3] می‏رسد. با ظهور رایانه‏های شخصی ارزان قیمت این فناوری به فراموشی سپرده شد، ولی در آغاز قرن جاری به مدد پیشرفت‏های قابل توجه در ساخت رایانه‏های توانمند، شبکه‏های با پهنای باند بالا و ابزارهای ذخیره‏سازی مدرن این فناوری امکان ظهور مجدد یافته ‏است. استفاده‏ی بهینه از منابع کارگزارها[4] با تجمیع[5] سرویس‏ها بر تعداد ماشین سخت‏افزاری کمتر، کاهش هزینه‏های زیرساخت مانند مصرف برق و خنک‏کنندگی، مدیریت بهتر و آسان‏تر كارگزارها، امکان مهاجرت[6] ماشین‏های مجازی در حال اجرا به میزبان‏های فیزیکی دیگر، ایجاد محیط‏های سازگار با نرم‏افزارهای قدیمی، ایجاد محیط‏های اجرایی[7] مجزا جهت نرم‏افزارهای نامطمئن[8] و یا تست و عیب‏یابی نرم‏افزارهای جدید از علت‏های مورد توجه قرار گرفتن این فناوری می‏باشند. هسته اصلی محیط مجازی، یک میزبان نرم‏افزاری به نام ناظر ماشین مجازی[9] است. وظیفه‏ی اصلی ناظر ماشین مجازی ایجاد و مدیریت منابع محیط‏های اجرایی است. از آن‏جا که منابع موجود، محدود و مشترک می‏باشند، رقابت بر سر استفاده از آن‏ها باعث ایجاد پدیده‏ای به نام تداخل بار کاری[10] می‏شود که تاثیر قابل توجهی بر کاهش کارایی ماشین‏های مجازی می‏گذارد. در این میان نقش کلیدی ناظر ماشین‏‏‏ مجازی این است که منابع موجود را به گونه‏ای تسهیم[11] و زمان‏بندی نماید که کارایی ماشین‏های مجازی تحت تاثیر قرار نگیرد.

معمولا زمان اجرای یک برنامه بر روی یک ماشین مجازی طولانی‎تر از زمان اجرای آن بر روی یک ماشین فیزیكی می‏باشد که علت اصلی آن سربار ناشی از مجازی‏سازی و تداخل بارهای کاری است. از این رو ارایه‏ی الگوریتم‏هایی با رویکرد کاهش تداخل بار کاری می‏تواند نقش بارزی در کاهش زمان اجرای برنامه‏های اجرایی در محیط‏های مجازی شود. از سویی دیگر با توجه به تنوع و تعدد میزبان‏های سخت‏افزاری در محیط پردازش ابری، مقیاس‏پذیری به عنوان یک مشخصه‏ی کلیدی در الگوریتم‏های ارایه شده می‏بایست مورد توجه ویژه قرار گیرد.

اهداف
در این پایان‏نامه سعی بر آن است كه با توجه به اثر منفی پدیده‏ی تداخل بار کاری بر زمان اجرای ماشین‏های مجازی یک الگوریتم زمان‏بندی با رویکرد کاهش تداخل بار کاری ارایه شود که علاوه بر کاهش زمان اجرا، مقیاس‏پذیر نیز بوده و قابل اجرا بر روی ابرهای معمول امروزی باشد. بنابراین با بررسی فناوری مجازی‌سازی و اثر تداخل بار کاری، سعی در ارایه الگوریتمی جهت زمان‏بندی ماشین‏های مجازی با رویکرد کاهش تداخل بار کاری خواهیم نمود.

ساختار پایان‌نامه
مطالب مندرج در این پایان‌نامه، همان طور که در شكل (1-1) نشان داده شده است، به صورت زیر سازمان‌دهی شده‌اند: فصل دوم به بررسی پیشینه‏‏ی مجازی‏سازی و سیستم‏های پردازش ابری می‏پردازد. این فصل در ادامه گذری بر مفهوم زمان‏بندی و پدیده‏ی تداخل بار کاری دارد. فصل سوم تحقیقات مرتبط در زمینه‏ی زمان‏بندی ماشین‏های مجازی مورد بررسی قرار خواهد داد. در فصل چهارم ضمن فرموله کردن مساله‏ی زمان‏بندی ماشین‏های مجازی با رویکرد تداخل بار کاری، الگوریتمی با همین رویکرد ارایه می‏شود. در فصل پنجم راهکار ارایه شده ارزیابی گردیده، کارایی، بهبودها و یا مشکلات آن را بیان خواهد شد. در نهایت در فصل ششم به نتیجه‌گیری از کل بحث در خصوص رویکرد کاهش تداخل بار کاری در زمان‏بندی ماشین‏های مجازی و نیز کارهای آینده قابل انجام در ادامه‌ی این پایان‌نامه پرداخته خواهد شد.

 

ساختار پایان‌نامه