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-2Prionty .....................14
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

فهرست اشکال :

شکل 1 – 1 ( حالتهای پردازش) ............7

شکل 1 – 2 ( صفهای پردازش ) .........16

شکل 1 – 3 (الگوریتم زمانبندی چند سطحی ) .................17

شکل 1 – 4 ( مکانیزم تخصیص حافظه ) ........................23

شکل 1 – 5 ( پارتیشن بندی پویا ) .....25

شکل 1 – 6 ( اشتراک در پارتیشن بندی پویا ) .............26

شکل 2 – 1 ( توضیح تصویری الگوریتم رقابتی ) .............38

شکل 3 – 1 ( شمای کلی الگوریتم ژنتیک )......................44

شکل 3 – 2 ( شمای شبه کد الگوریتم ژنتیک ) ............48

شکل 4 – 1 ( نمودار طول زمانبند در هر نسل ) ................64

فهرست جداول :

جدول 1 – 1 ( پردازشهای مورد آزمایش) ...............13

جدول 4 – 1 ( لیست task های تولید شده) ..........63

چکیده :

کارایی سیستمهای کامپیوتری وابستگی زیادی به منابع موجود و تخصیص بهینه آنها دارد. یک الگوریتم تخصیص منابع بهینه نقش بسزایی در افزایش کارایی یک سیستم دارد. مطالعات زیادی در این زمینه انجام گرفته و الگوریتمهای مختلفی ارائه شده است. تخصصی تر شدن علوم کامپیوتر و افزایش پیچیدگی ها و مسائلی موجود در آن منجر به پیچیدگی بیشتر بهینه سازی گردیده و لزوم الگوریتمهای بهینه سازی کارا و سریع افزایش یافته شده است. مطالعات فراوانی کارایی روشهای مبتنی بر علم ژنتیک موسوم به الگوریتم ژنتیک را در مسائل بهینه سازی نشان داده است. الگوریتم ژنتیک نوع خاصی از الگوریتمهای تکامل است که از تکنیکهای زیست‌شناسی مانند وراثت و جهش استفاده می‌کند.

در این پروژه استفاده از الگوریتم ژنتیک در تخصیص منبع cpu به پروسسهای مختلف ارائه شده است. با استفاده از الگوریتم ژنتیک زمانبندی طراحی شده است تا در حد امکان زمان انجام پروسس ها توسط پردازنده به حداقل رسانده شود و همچنین مراحل به انجام رساندن پروسس ها بین چندین پردازنده تقسیم شود .این پروژه از زمان ورود و زمان اجرای هر پروسس استفاده کرده و طی مراحلی بهترین زمان تخصیص یافته برای هر پروسس با پردازنده مورد نظر محاسبه شده است.

کلمات کلیدی : تخصیص منابع ، الگوریتم ژنتیک ، وراثت ، جهش ، بهینه سازی

پیش گفتار

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

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

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

در این راستا ، این پژوهش پاسخگوی این پرسشها بود که

علم ژنتیک در چه زمانی شناخته شد و شروع به کار کرد
اساس کار و عملکرد علم ژنتیک چیست.
بهینه سازی مسائل چگونه انجام میشود.
چگونه از علم ژنتیک در زمانبندی منابع بالاخص CPU استفاده میشود.

و در آخر

آیا استفاده از الگوریتم ژنتیک در تخصیص منابع باعث بهینه شدن آن میشود.

پاسخ دادن به این پرسشها هریک به نوبه ی خود به عنوان یکی از اهداف اصلی این پژوهش مطرح شد و زمینه ساز آغاز مطالعات در این زمینه گردید.

برای رسیدن به این هدف لازم بود ابتدا به مطالعه منابع علم ژنتیک پرداخته شود که شامل تاریخچه آن ، عملکرد آن و آشنایی با کدهای الگوریتم ژنتیک میباشد و مطالعه در زمینه تخصیص منابع که منابع شامل موارد گوناگون از جمله CPU ، RAM ، دستگاهها و ... میباشد .

سپس این تحقیقات و CPU (به عنوان منبع مورد آزمایش) به عنوان منابع پایه مورد بررسی قرار گیرد.

که چنین نیز شد.

کتابها و مقالاتی که از طریق کتابخانه ها و اینترنت – به عنوان به روزترین منابع – بطور مستقیم به بررسی این علم می­پرداخت ، همچنین منابع جانبی ای مانند مصاحبه با افراد متخصص که امکان داشت به طور غیر مستقیم در انجام این پژوهش موثر واقع شود ، مورد مطالعه و یادداشت برداری قرار گرفت. با انجام این مراحل پیشینه ی تحقیقی موضوع مورد نظر ما بیش از پیش آشکار شد و مشخص گردید که تاکنون در این زمینه بخصوص در این دانشگاه و حومه ی آن کمتر کار شده. منابع موجود نیز بیشتر به معرفی آن پرداخته بودند و در آنها هیچگونه بررسی با درون مایه ی مورد نظر ما به چشم نمی خورد.

مجموع این مسائل اگر چه برای پژوهش نوعی تنگنا محسوب می شد اما موجب آن شد که نگارنده با انگیزه مضاعفی به انجام این تحقیق بپردازد و آنچه پیش رو دارید حاصل این انگیزه و تلاش ناشی از آن است.

عنوان پژوهش با توجه به اهداف کار «زمانبندی پروسسها با الگوریتم ژنتیک در سیستمهای چند پردازنده­ای» انتخاب شد و فصلها نیز با توجه به همین اهداف و یادداشت برداری های انجام شده مرتب گردید.

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

فصل دوم به بررسی مفهوم بهینه سازی مسائل پرداخته است. توابع آن و اهداف بهینه کردن در این فصل مشخص گردیده و روشهای موجود بهینه سازی معرفی شده است که یکی از این روشها الگوریتم ژنتیک می باشد.

که فصل سوم به این الگوریتم پرداخته است. تاریخچه ، شرح کامل اصطلاحات، عملکرد، کاربردهای آن و بهینه سازی به روش الگوریتم ژنتیک بیان شده است.

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

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

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

و در انتها مایه ی غرور و مباهات خود می دانیم که بگوییم در مراحل گوناگون این پژوهش از راهنمایی های فاضلانه مهندس ایمان کامکار به عنوان استاد راهنما و همچنین حمایتهای بی دریغ دکتر مجید بقایی نژاد و راهنمایی های ارزشمند مهندس هادی صباغ زاده که در آشنایی با کد الگوریتم ژنتیک بهره های فراوانی برده ایم که بدین وسیله از این بزرگواران سپاسگذاری می نماییم و تمام دوستایی که به نوعی در به انجام رسیدن این پژوهش با ما همکاری داشته اند تشکر می­کنیم و از خداوند متعال برای تمامی این عزیزان آرزوی موفقیت و سربلندی و برای خودمان توفیق جبران زحمات این بزرگواران را مسئلت می نماییم.

و...