چکیده:
یکی از مسائلی که برای افزایش راندمان کلی سیستم های چند پردازنده ای وجود دارد موضوع زمان بندی است دراین سیستم ها آنچه در اجرای فرایندها باید مورد توجه قرارگیرد زمان پایان کل کار است استفاده از روشهای قطعی زمان بندی در سیستمهای چند پردازنده ای برای بدست آوردن جواب بهینه دارای پیچیدگی زمانی بالایی است بنابراین راه موثر استفاده از روش های ابتکاری است دراین پروژه برای زمان بندی سیستمهای چند پردازنده ای از الگوریتم ژنتیک جدیدی استفاده شده است که براساس اولویت دهی گره های وظیفه و نگاشت همزمان به پردازنده ها می باشد بطوریکه محدودیت های موجود در اولویت دهی وظایف مورد نظر قرارگیرد نتایج عملی پیاده سازی شده نشان میدهد که الگوریتم پیشنهادی جدید می توان زمان بندی مناسب و قابل قبولی را نسبت به الگوریتم های مشابه به دست آ ورد.
الگوریتم ژنتیک نوع خاصی از الگوریتمهای تکامل است که از تکنیکهای زیست‌شناسی مانند وراثت و جهش استفاده می‌کند.
با استفاده از الگوریتم ژنتیک زمانبندی طراحی شده است تا در حد امکان زمان انجام کارها توسط پردازنده به حداقل رسانده شود و همچنین مراحل به انجام رساندن کارها بین چندین پردازنده تقسیم شود.
مقدمه:
امروزه یکی از مهمترین زمینه‌های تحقیق و پژوهش، توسعۀ روشهای جستجو بر مبنای اصول تکامل طبیعی می‌باشد. در محاسبات تکاملی به صورت انتزاعی از مفاهیم اساسی تکامل طبیعی در راستای جستجو برای یافتن راه حلّ بهینه برای مسائل مختلف الهام گرفته شده است.الگوریتمهای ژنتیک ابزاری می باشند که توسط آن ماشین می تواندمکانیزم انتخاب طبیعی را شبیه سازی نماید. این عمل با جستجو درفضای مسئله جهت یافتن جواب برتر و نه الزاما بهینه صورت می پذیرد. الگوریتم های ژنتیک با استفاده از نظریه داروین در مورد تکامل،جان گرفتند. سپس نظریه محاسبات تکاملی، توسط ریچنبرگ در سال ۱۹۶۰معرفی شدند و این نظریه توسط محققان دیگر توسعه یافت تا در سال ۱۹۷۵ منجربه اختراع الگوریتم های ژنتیک توسطHollandو دانشجویانش شد. مطالب که در این فصل مفاهیمی دربارۀ علم کامپیوتر و علم ژنتیک مانند الگوریتم و انواع آن، جستجو، تاریخچه الگوریتم ژنتیک و علم ژنتیک می باشد، و یا به بیانی خلاصه‌تر می‌توان گفت در این فصل به بیان مقدّمات خواهیم پرداخت.الگوریتم‌ژنتیک بر خلاف دیگر روشهای جستجو، که توسط طراحان نگاشته می‌شوند، در حقیقت به دست دستگاه آفرینش پدید آمده، و پس از شناخت نسبی دانشمندان از این روش به صورت مسأله‌ای ریاضی فرموله شده و وارد دانش مهندسی کامپیوتر و دیگر علوم مرتبط گردیده است. در یکی دو دهه گذشته که این الگوریتم در علوم مهندسی بکار گرفته شده، ناباورانه چنان دست‌آوردهاو نتایج شگفت‌انگیزی داشته که نگاه بسیاری از دانش‌پژوهان علوم گوناگون فنی‌مهندسی را به خود جلب کرده است.
فهرست
1-3-1- ایده اصلی الگوریتم ژنتیک... 17
1-3-2- روش های انتخاب در الگوریتم ژنتیک... 18
1-3-3- شمای کلی از نحوه عملکرد الگوریتم ژنتیک... 20
شکل 1 – 1-( شمای کلی الگوریتم ژنتیک ) 20
1-3-4- اصطلاحات الگوریتم ژنتیک... 21
1-6- رابطه تکامل طبیعی با روشهای هوش مصنوعی.. 23
شکل 1-2-نقاط بهینۀ محلی و بهینۀ کلی.. 24
1-7-اجزاء اساسی الگوریتم ژنتیک و تشریح کلی از الگوریتم ژنتیک... 24
1-7-2-آغاز الگوریتم ژنتیک... 26
شکل 1 – 3 ( شمای شبه کد الگوریتم ژنیتک ) 27
1-8-کروموزوم (الگوریتم ژنتیک) 28
1-9-روند کار الگوریتم ژنتیک... 29
1-10-کاربردهای الگوریتم ژنتیک... 31
1-11-بهینه سازی به روش الگوریتم ژنتیک... 32
1-12-اصول اساسی الگوریتم ژنتیک... 33
1-13-1- الگوریتمهای جستجوی ناآگاهانه. 35
1-13-1-2-الگوریتمهای جستجوی درختی.. 36
1-13-2- الگوریتمهای جستجوی آگاهانه. 36
فصل دوم: سیستم های چند پردازنده ای Multi processing
2-2-سیستم های چند برنامه ای programming Multi 43
2-3-تقسیم بندی سیستم عاملهای چند پردازنده‌ای.. 44
2-4- مدیریت یک رایانه با چند سیستم عامل.. 45
2-5- چرا دو پردازنده بهتر از یک پردازنده است؟. 47
2-7- ساختارهای اتصالات متقابل. 51
2-8-گذرگاه مشترک با تسهیم زمانی.. 52
شکل2-1- زیر گذرگاه مشترک با تسهیم زمانی.. 52
2-9-1- مزیت سازمان حافظه چند پورتی: 53
شکل2-2- ساختار چندپردازنده فوق مکعبی یا چند پردازنده n بعدی.. 53
2-11-شبکه سوئیچینگ چند طبقه (امگا) 54
2-13-سیستم های مالتی پروسسور بر اساس ساختار حافظه: 55
2-13-1-مالتی پروسسور با دسترسی یکنواخت به حافظه (UMA) 55
2-13-2-مالتی پروسسور با دسترسی غیر یکنواخت به حافظه (NUMA) 55
2-13-3- مالتی پروسسوربر اساس معماری فقط حافظه نهان (COMA) 56
2-14-طبقه بندی معماری سیستم های کامپیوتری (Flynn) 56
2-14-1-یک جریان داده و یک جریان دستور(SISD) : 56
2-14-2- چند جریان داده و یک جریان دستورSIMD. 57
2-14-3- یک جریان داده و چند جریان دستورMISD. 57
2-14-4- چند جریان داده و چند جریان دستورMIMD. 57
2-15-زمان بندی چند پردازنده ای.. 58
جدول 2-1-دانه بندی همگام سازی و فرآیندها 59
2-18-توازی دانه درشت و بسیار درشت.. 60
2-22-تخصیص فرآیندها به پردازنده 62
2-23-استفاده از چند برنامه ای روی هر پردازنده 63
2-24-توزیع وقت پردازنده به فرآیند. 64
شکل 2-4-(الف)(ب) مقایسه کارایی زمانبندی برای تک پردازنده و دو پردازنده ای 66
26-2-3-تخصیص پردازنده اختصاصی.. 68
2-28-تخصیص پردازنده اختصاصی.. 72
شکل2-5- مثالی از زمانبندی گروه ها 72
شکل2-6-افزایش سرعت برنامه کاربردی به صورت تابعی ازتعداد فرایندها 74
2-31-ویژگی های سیستم های عامل بی درنگ... 78
شکل 2-7-زمانبندی فرایند بی درنگ... 82
2-33-زمان بندی مهلت زمانی.. 85
جدول 2-2 سابقه اجرایی دو وظیفه متناوب.. 87
شکل 2-8-زمانبندی وظیفه های بی درنگ متناوب با مهلت زمانی کامل شدن. 88
شکل 2-9-زمانبندی وظیفه های بی درنگ نامتناوب با مهلت زمانی شروع. 89
جدول 2-3-سابقه اجرای پنج وظیفه نامتناوب.. 90
2-34-زمان بندی با نرخ یکنواخت.. 91
شکل 2-10-نمودار زمانبندی وظیفه متناوب.. 92
شکل2-11-مجموعه ای از وظیفه ها با زمانبندی نرخ یکنواخت.. 92
2-35-2-زمان بندی بی درنگ... 99
شکل2-13- مثالی از زمانبندی.. 100
2-35-3-زمان بندی غیر بی درنگ... 101
شکل 2-14-ساختمان داده های زمانبندی برای هر پردازنده 102
2-36-محاسبه اولویت ها و برهه های زمانی.. 103
2-36-1-ارتباط با وظیفه های بی درنگ... 103
2-36-2- زمان بندی یونیکس SVR4. 104
شکل 2-15-طبقه های اولویت.. 105
شکل 2-16-صف های توزیع وقت پردازنده 106
2-36-4- اولویت های نخ و فرآیند. 107
شکل 2-17-مثالی از رابطه اولویت ها 108
2-37-زمان بندی چند پردازنده ای.. 108
3-3-منابع کلیدی سیستم عامل. 112
3-3-7-حالت Suspend Blocked. 115
3-4-2- به اشتراک گذاشتن سخت افزار. 116
3-4-3- اجازه به اشتراک گذاشتن داده ها بین کاربران: 116
3-4-4- زمان بندی منابع برای تخصیص به کاربران: 117
3-4-5- تسهیل در ورودی و خروجی: 117
3-4-6- توانایی شناخت خطاها در سیستم عامل باید وجود داشته باشد: 117
3-6-7-سیستم عامل باید حسابدار باشد: 117
4-1-4-معیار های کمی زمانبندی.. 122
4-1-5-میزان بکارگیری پردازنده 122
4-1-6-معیارهای کیفی زمانبندی.. 123
4-1-6-1- Fairness (منصفانه) 123
4-1-6-2- قابلیت پیش بینی.. 124
4-2-الگوریتم های زمانبندی.. 124
جدول 4 – 1- پردازشهای مورد آزمایش... 124
4-2-1-First Come First Serviced. 125
4-2-3-Shortest Remaining Time Next 126
4-2-5-الگوریتم صفهای چندگانه Multi Queues 127
4-2-6-الگوریتم Multi Level Queue Schduling. 128
شکل 4-2-الگوریتم زمانبدی چند سطحی.. 129
4-4-مدیریت حافظه و فضای ذخیره سازی.. 134
4-4-1-مکانیزم ها یا شمای مدیریت حافظه ای.. 135
4-4-2-Partition Description Table 136
4-4-3-Internal Fragmentation. 136
4-4-4-سه مکانیزم تخصیص حافظه وجود دارد: 136
شکل 4-3- مکانیزم تخصیص حافظه. 137
4-4-5-Partition Static Model 137
4-4-6-به اشتراک گذاری در مدلStatic ) Sharing Static Model) 137
4-4-8-Partition Description Tabl 138
شکل 4-5-اشتراک در پارتیشن بندی پویا 140
4-5-ساختار PCB) : Process Control Block) 140
4-5-1-اطلاعاتی که در مورد پروسه ها باید داشته باشیم: 140
4-5-4-ملزومات انحصار متقابل: 145
4-5-5-2-بخش بحرانی یا Critical Selection. 146
4-7-سیستم‌عامل‌های چندوظیفه‌ای.. 147
4-7-1-چندوظیفه‌ای پیشگیرانه (قبضه کردنی یا غیر انحصاری) 147
4-7-2-چندوظیفه‌ای مشارکتی.. 147
4-8-الگوریتمهای زمانبندی پردازش... 148
4-8-1-زمانبندی اجرا به ترتیب ورود. 148
4-8-2-زمانبندی نخست کوتاهترین کار. 149
4-8-3-زمانبندی کوتاهترین زمان باقی‌مانده 149
4-8-4-بالاترین نسبت پاسخ.. 150
4-8-6-زمانبندی نوبت گردشی.. 151
4-8-6-1-صف چندگانه فیدبک... 151
جدول 4-2- خلاصه الگوریتم زمانبندی.. 152
4-9-زمانبندی درسیستم‌عامل‌های مختلف... 152
4-9-1- داس و ویندوزهای اولیه. 152
4-9-3-ویندوز سرور ۲۰۰۸ و ویندوز ویستا 153
4-10-تعریف زمانبندی در سیستم های چند پردازنده 155
4-11-زمانبندی برای سیستم های دارای پردازنده های ناهمگن.. 156
دانلود پروژه زمانبندی کارها روی سیستم های چند پردازنده ای بااستفاده از الگوریتم های ژنتیک
