در سده ی اخیر با پیشرفتهایی که در زمینه های گوناگون علمی نصیب انسان شده است و با تخصصی تر شدن هرچی بیشتر علوم، شاخه های جدیدی از دانش از بطن دانش قدیم بشر سر برآورده و رشد و بالیدن گرفته اند. یکی از این علوم نسبتا جدید الگوریتم ژنتیک است که موجودیت و حیاتش ریشه در علومی دارد که به گونه ای از انسان ناشی میشود.
این علم در سالهای اخیر بسیار مورد توجه همگان بوده است در نتیجه مراحل تکامل طبیعی موجودات زنده تبدیل به یکی از علوم جذاب و مطلوب پژوهشگران شده و بستر تحقیقات و مطالعات فراوانی گردیده است. این علم شاخه ها و عرصه های مختلفی را شامل میشود که هریک به تنهایی میتواند در حد یک علم مستقل مطرح شود.
نکته اصلی در این کار تلاش برای جستجو و یافتن پیوندهای پیدا و نهانی است که علم ژنتیک با علوم کامپیوتر دارد. اهمیت این عرصه از آن جهت است که انجام مطالعاتی با این درون مایه و سمت و سو جدا از آنکه سبب یافتن ریشه های علم ژنتیک در سایر علوم میشود، میتواند راهنما و پاسخگوی بسیاری از پرسش ها و ابهاماتی باشد که گاه در مطالعه ی علوم کامپیوتری برای افراد به وجود می آید و جز استفاده از ژنتیک شیوه مناسب دیگری برای پاسخگویی به آنها وجود ندارد. بنابراین ضرورت انجام چنین تحقیقاتی کاملا احساس میشود نگارنده با احساس کردن همین ضرورت در این پژوهش بر آن شد تا قدم به این عرصه بگذارد و ریشه های ژنتیک را در علوم کامپیوتری بالاخص تخصیص منابع جستجو کند.
در این راستا ، این پژوهش پاسخگوی این پرسشها بود که
• علم ژنتیک در چه زمانی شناخته شد و شروع به کار کرد
• اساس کار و عملکرد علم ژنتیک چیست.
• بهینه سازی مسائل چگونه انجام میشود.
• چگونه از علم ژنتیک در زمانبندی منابع بالاخص CPU استفاده میشود.
و در آخر
• آیا استفاده از الگوریتم ژنتیک در تخصیص منابع باعث بهینه شدن آن میشود.
پاسخ دادن به این پرسشها هریک به نوبه ی خود به عنوان یکی از اهداف اصلی این پژوهش مطرح شد و زمینه ساز آغاز مطالعات در این زمینه گردید.
برای رسیدن به این هدف لازم بود ابتدا به مطالعه منابع علم ژنتیک پرداخته شود که شامل تاریخچه آن ، عملکرد آن و آشنایی با کدهای الگوریتم ژنتیک میباشد و مطالعه در زمینه تخصیص منابع که منابع شامل موارد گوناگون از جمله CPU ، RAM ، دستگاهها و ... میباشد .
سپس این تحقیقات و CPU (به عنوان منبع مورد آزمایش) به عنوان منابع پایه مورد بررسی قرار گیرد.
که چنین نیز شد.
کتابها و مقالاتی که از طریق کتابخانه ها و اینترنت – به عنوان به روزترین منابع – بطور مستقیم به بررسی این علم می-پرداخت ، همچنین منابع جانبی ای مانند مصاحبه با افراد متخصص که امکان داشت به طور غیر مستقیم در انجام این پژوهش موثر واقع شود ، مورد مطالعه و یادداشت برداری قرار گرفت. با انجام این مراحل پیشینه ی تحقیقی موضوع مورد نظر ما بیش از پیش آشکار شد و مشخص گردید که تاکنون در این زمینه بخصوص در این دانشگاه و حومه ی آن کمتر کار شده. منابع موجود نیز بیشتر به معرفی آن پرداخته بودند و در آنها هیچگونه بررسی با درون مایه ی مورد نظر ما به چشم نمی خورد.
مجموع این مسائل اگر چه برای پژوهش نوعی تنگنا محسوب می شد اما موجب آن شد که نگارنده با انگیزه مضاعفی به انجام این تحقیق بپردازد و آنچه پیش رو دارید حاصل این انگیزه و تلاش ناشی از آن است.
عنوان پژوهش با توجه به اهداف کار «زمانبندی پروسسها با الگوریتم ژنتیک در سیستمهای چند پردازنده-ای» انتخاب شد و فصلها نیز با توجه به همین اهداف و یادداشت برداری های انجام شده مرتب گردید.
فصل اول بطور کامل به معرفی تخصیص منابع اختصاص یافت و با نظر به آنکه استفاده کنندگان از این پژوهش دانشجویان مهندسی کامپیوتر خواهند بود سعی اصلی در این فصل بر آن قرار گرفت تا یک تصویر کلی اما جامع از تخصیص منابع ، معرفی منابع و زمانبندها شکل گیرد تا برقرار کردن ارتباط با فصلهای بعدی آسانتر صورت گیرد.
فصل دوم به بررسی مفهوم بهینه سازی مسائل پرداخته است. توابع آن و اهداف بهینه کردن در این فصل مشخص گردیده و روشهای موجود بهینه سازی معرفی شده است که یکی از این روشها الگوریتم ژنتیک می باشد.
که فصل سوم به این الگوریتم پرداخته است. تاریخچه ، شرح کامل اصطلاحات، عملکرد، کاربردهای آن و بهینه سازی به روش الگوریتم ژنتیک بیان شده است.
پیش گفتار 1
فصل اول : مدیریت منابع 4
1-1 مدیریت منابع 5
1-2 ویژگی ها 5
1-3 منابع کلیدی سیستم عامل 6
1-3-1 حالت Running 7
1-3-2 حالت Ready 7
1-3-3 حالتDespatch7
1-3-4 Time Out Run 7
1-3-5 حالت Blocked 8
1-3-6 حالت Suspend Ready 8
1-3-7 Suspend Blocked 8
1-4 وظایف سیستم عامل 9
1-5 زمانبندی 10
1-5-1 زمانبند بلند مدت 10
1-5-2 زمانبند میان مدت 10
1-5-3 زمانبند کوتاه مدت 10
1-5-4 معیار های کمی زمانبندی11
1-5-5 معیارهای کیفی زمانبندی 12
1-6 الگوریتم زمانبندی 13
1-6-1 First Come First Service 13
1-6-2Prionty14
1-6-3 SRTN 14
1-6-4 SJF 15
1-6-5 MQ 16
1-6-6 MLQ 16
1-7 مدیریت پردازنده 17
1-8 مدیریت حافظه و فضای ذخیره سازی 21
1-8-1 شمای مدیریت حافظه 21
1-8-2 جدول پارتیشن بندی 22
1-8-3 پارتیشن بندی داخلی 22
1-8-4 مکانیزم تخصیص حافظه 23
1-8-5 مدل پارتیشن ایستا23
1-8-6 اشتراک گذاری در پارتیشن ایستا 24
1-8-7 پارتیشن بندی پویا 24
1-8-8 جدول پارتیشن بندی پویا 25
1-8-9 اشتراک گذاری در مدل پویا 26
1-9 ساختار PCB 26
1-9-1 اطلاعاتی درباره پروسه 26
1-9-2 گفتگوی پروسه ها 27
1-9-3 رقابت پروسه ها 28
1-9-4 ملزومات انحصار متقابل 30
1-9-5 پروتکلها 30
فصل دوم : بهینه سازی 32
2-1 بهینه سازی 33
2-2 مراحل حل مسئله بهینه سازی 33
2-3 هدف 34
2-4 متغیرهای بهینه سازی 34
2-5 ارتباط میان هدف و متغیرها بصورت ریاضی 35
2-6 پس از تعریف ارتباط ریاضی تابع هزینه و متغیرهای بهینه سازی چه باید کرد 36
2-7 آیا تابع هزینه مسئله بصورت یک برنامه است 37
2-8 پارامترها 37
2-9 الگوریتم رقابت استعماری 37
2-10 بهینه سازی و روشهای موجود 39
فصل سوم : الگوریتم ژنتیک 41
3-1 الگوریتم ژنتیک 42
3-1-1 ایده اصلی الگوریتم ژنتیک 42
3-1-2 روشهای انتخاب در الگوریتم ژنتیک 43
3-1-3 شمای کلی از نحوه عملکرد الگوریتم ژنتیک 44
3-1-4 اصطلاحات الگوریتم ژنتیک 45
3-2 اجزای اساسی الگوریتم و تشریح کلی آن 45
3-2-1 شبه کد 46
3-2-2 آغاز الگوریتم ژنتیک 47
3-2-3 شمای کلی شبه کد 48
3-3 کروموزوم 48
3-3-1 طراحی کروموزوم 48
3-4 روند کار الگوریتم ژنتیک 49
3-5 شرایط خاتمه الگوریتم 50
3-6 کاربردهای الگوریتم ژنتیک 51
3-7 بهینه سازی به روش الگوریتم ژنتیک 51
3-8 اصول اساسی الگوریتم ژنتیک 52
فصل چهارم : پیاده سازی 54
توابع برنامه 55
4 – 1 تابع Final 55
4 – 1 – 1 تابع Task_Generate 56
4 – 1 – 2 تابعSort 56
4 – 1 – 3 تابع Generate_Initial_Population 57
4 – 1 – 4 تابع Size_Chromosome 57
4 – 1 – 5 تابع Fitness_Of_Chromosome 58
4 – 1 – 6 تابع Rank 58
4 – 1 – 7 تابع Select_Best 59
4 – 1 – 8 تابع Crossover 59
4 – 1 - 9 تابع Mutation 61
4 – 2 خروجی برنامه 62
4 – 3 نمودار طول زمانبند در هر نسل 64
نتیجه گیری 65
واژه نامه انگلیسی به فارسی 66
واژه نامه فارسی به انگلیسی 67
منابع 68
شامل 75 صفحه فایل word
دانلود پایان نامه زمانبندی پروسس ها با الگوریتم ژنتیک در سیستم های چند پردازنده ای