دانلود پروژه زمانبندی کارها روی سیستم های چند پردازنده ای بااستفاده از الگوریتم های ژنتیک

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

چکیده:

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

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

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

مقدمه:

امروزه یکی از مهم‌ترین زمینه‌های تحقیق و پژوهش، توسعۀ روش‌های جستجو بر مبنای اصول تکامل طبیعی می‌باشد. در محاسبات تکاملی به صورت انتزاعی از مفاهیم اساسی تکامل طبیعی در راستای جستجو برای یافتن راه حلّ بهینه برای مسائل مختلف الهام گرفته شده است.الگوریتمهای ژنتیک ابزاری می باشند که توسط آن ماشین می تواندمکانیزم انتخاب طبیعی را شبیه سازی نماید. این عمل با جستجو درفضای مسئله جهت یافتن جواب برتر و نه الزاما بهینه صورت می پذیرد. الگوریتم های ژنتیک با استفاده از نظریه داروین در مورد تکامل،جان گرفتند. سپس نظریه محاسبات تکاملی، توسط ریچنبرگ در سال ۱۹۶۰معرفی شدند و این نظریه توسط محققان دیگر توسعه یافت تا در سال ۱۹۷۵ منجربه اختراع الگوریتم های ژنتیک توسطHollandو دانشجویانش شد. مطالب که در این فصل مفاهیمی دربارۀ علم کامپیوتر و علم ژنتیک مانند الگوریتم و انواع آن، جستجو، تاریخچه الگوریتم ژنتیک و علم ژنتیک می باشد، و یا به بیانی خلاصه‌تر می‌توان گفت در این فصل به بیان مقدّمات خواهیم پرداخت.الگوریتم‌ژنتیک بر خلاف دیگر روش‌های جستجو، که توسط طراحان نگاشته می‌شوند، در حقیقت به دست دستگاه آفرینش پدید آمده، و پس از شناخت نسبی دانشمندان از این روش به صورت مسأله‌ای ریاضی فرموله شده و وارد دانش مهندسی کامپیوتر و دیگر علوم مرتبط گردیده است. در یکی دو دهه گذشته که این الگوریتم در علوم مهندسی بکار گرفته شده، ناباورانه چنان دست‌آوردهاو نتایج شگفت‌انگیزی داشته که نگاه بسیاری از دانش‌پژوهان علوم گوناگون فنی‌مهندسی را به خود جلب کرده است.

 فهرست

فصل اول: الگوریتم ژنتیک

1-1- مقدمه: 15

1-2- به دنبال تکامل. 15

1-3- الگوریتم ژنتیک... 17

1-3-1- ایده اصلی الگوریتم ژنتیک... 17

1-3-2- روش های انتخاب در الگوریتم ژنتیک... 18

1-3-3- شمای کلی از نحوه عملکرد الگوریتم ژنتیک... 20

شکل 1 – 1-( شمای کلی الگوریتم ژنتیک ) 20

1-3-4- اصطلاحات الگوریتم ژنتیک... 21

1-4- درباره علم ژنتیک... 21

1-5- تاریخچۀ علم ژنتیک... 22

1-6- رابطه تکامل طبیعی با روش‌های هوش مصنوعی.. 23

شکل 1-2-نقاط بهینۀ محلی و بهینۀ کلی.. 24

1-7-اجزاء اساسی الگوریتم ژنتیک و تشریح کلی از الگوریتم ژنتیک... 24

1-7-1 شبه کد. 26

1-7-2-آغاز الگوریتم ژنتیک... 26

1-7-3-شمای کلی شبه کد. 27

شکل 1 – 3 ( شمای شبه کد الگوریتم ژنیتک ) 27

1-8-کروموزوم (الگوریتم ژنتیک) 28

1-8-1-طراحی کروموزوم. 28

1-9-روند کار الگوریتم ژنتیک... 29

1-10-کاربردهای الگوریتم ژنتیک... 31

1-11-بهینه سازی به روش الگوریتم ژنتیک... 32

1-12-اصول اساسی الگوریتم ژنتیک... 33

1-13-الگوریتم جستجو. 34

1-13-1- الگوریتم‌های جستجوی ناآگاهانه. 35

1-13-1-1- جستجوی لیست.. 35

1-13-1-2-الگوریتم‌های جستجوی درختی.. 36

1-13-1-3- جستجوی گراف.. 36

1-13-2- الگوریتم‌های جستجوی آگاهانه. 36

1-13-2-1- جستجوی خصمانه. 37

1-14- مسائل NP-Hard. 37

فصل دوم: سیستم های چند   پردازنده ای Multi processing

2-2-سیستم های چند برنامه ای programming Multi 43

2-3-تقسیم بندی سیستم عاملهای چند پردازنده‌ای.. 44

2-4- مدیریت یک رایانه با چند سیستم عامل.. 45

2-5- چرا دو پردازنده بهتر از یک پردازنده است؟. 47

2-6-چند پردازنده ها 50

2-7- ساختارهای اتصالات متقابل. 51

2-8-گذرگاه مشترک با تسهیم زمانی.. 52

شکل2-1- زیر گذرگاه مشترک با تسهیم زمانی.. 52

2-9- حافظه چند پورتی.. 53

2-9-1- مزیت سازمان حافظه چند پورتی: 53

2-9-2- عیب این سازمان : 53

2-10-اتصال فوق مکعبی.. 53

شکل2-2- ساختار چندپردازنده فوق مکعبی یا چند پردازنده n بعدی.. 53

2-11-شبکه سوئیچینگ چند طبقه (امگا) 54

2-12-سوئیچینگ تقاطعی: 54

2-12-1- مزیت: 54

2-12-2- عیب : 54

شکل 2-3- سوئیچینگ تقاطعی.. 55

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-16-دانه بندی.. 58

2-17-توازی مستقل. 59

جدول 2-1-دانه بندی همگام سازی و فرآیندها 59

2-18-توازی دانه درشت و بسیار درشت.. 60

2-19-توازی دانه متوسط.. 61

2-20-توازی دانه ریز. 61

2-21-موضوعات طراحی.. 61

2-22-تخصیص فرآیندها به پردازنده 62

2-23-استفاده از چند برنامه ای روی هر پردازنده 63

2-24-توزیع وقت پردازنده به فرآیند. 64

2-25-زمان بندی فرآیند. 65

2-26-زمان بندی نخ ها 66

شکل 2-4-(الف)(ب) مقایسه کارایی زمانبندی برای تک پردازنده و دو پردازنده ای   66

2-26-1-اشتراک بار. 67

2-26-2-زمان بندی گروهی.. 67

26-2-3-تخصیص پردازنده اختصاصی.. 68

2-26-4-زمان بندی پویا 68

2-26-5-اشتراک باز. 68

2-27-زمان بندی گروهی.. 70

2-28-تخصیص پردازنده اختصاصی.. 72

شکل2-5- مثالی از زمانبندی گروه ها 72

شکل2-6-افزایش سرعت برنامه کاربردی به صورت تابعی ازتعداد فرایندها 74

2-29-زمان بندی پویا 75

2-30-زمان بندی بی درنگ... 77

2-31-ویژگی های سیستم های عامل بی درنگ... 78

شکل 2-7-زمانبندی فرایند بی درنگ... 82

2-32- زمان بندی بی درنگ... 83

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-اولویت معکوس... 94

شکل 2-12-اولویت معکوس... 96

2-35-1-زمان بندی لینوکس... 98

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-3-زمان بندی ویندوز. 106

2-36-4- اولویت های نخ و فرآیند. 107

شکل 2-17-مثالی از رابطه اولویت ها 108

2-37-زمان بندی چند پردازنده ای.. 108

فصل سوم

3-1-مدیریت منابع. 111

3-2-ویژگی ها 111

3-3-منابع کلیدی سیستم عامل. 112

شکل 3-1 (حالتهای پردازش) 113

3-3-1حالت Running. 113

3-3-2-حالت Ready. 114

3-3-3-حالت Despatch. 114

3-3-4-Time Out Run. 114

3-3-5-حالت Blocked. 114

3-3-6-حالت Suspend Ready. 115

3-3-7-حالت Suspend Blocked. 115

3-4- وظایف سیستم عامل. 116

3-4-1- رابط کاربر. 116

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-زمانبندی.. 119

4-1-1-زمانبند بلند مدت.. 120

4-1-2-زمانبند میان مدت.. 120

4-1-3-زمانبند کوتاه مدت.. 121

4-1-3-1- Suspend Queue : 121

4-1-4-معیار های کمی زمانبندی.. 122

4-1-5-میزان بکارگیری پردازنده 122

4-1-5-1- Trough put 122

4-1-5-2- Turn Over Time 123

4-1-5-3- Waiting Time 123

4-1-5-4- Response Time 123

4-1-6-معیارهای کیفی زمانبندی.. 123

4-1-6-1- Fairness (منصفانه) 123

4-1-6-2- قابلیت پیش بینی.. 124

4-1-6-3- قابلیت تکرار. 124

4-2-الگوریتم های زمانبندی.. 124

جدول 4 – 1- پردازشهای مورد آزمایش... 124

4-2-1-First Come First Serviced. 125

4-2-2-الگوریتم Priority 125

4-2-3-Shortest Remaining Time Next 126

4-2-4-Shortest Job First 127

4-2-5-الگوریتم صفهای چندگانه Multi Queues 127

شکل 4-1-( صفهای پردازش) 128

4-2-6-الگوریتم Multi Level Queue Schduling. 128

شکل 4-2-الگوریتم زمانبدی چند سطحی.. 129

4-3-مدیریت پردازنده 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-7-پارتیشن بندی پویا 138

4-4-8-Partition Description Tabl 138

شکل 4–4-پارتیشن بندی پویا 139

4-4-9-Sharing در مدل پویا 140

شکل 4-5-اشتراک در پارتیشن بندی پویا 140

4-5-ساختار PCB) : Process Control Block) 140

4-5-1-اطلاعاتی که در مورد پروسه ها باید داشته باشیم: 140

4-5-2-گفتگوی پروسه ها 142

4-5-3-رقابت پروسه ها 143

4-5-4-ملزومات انحصار متقابل: 145

4-5-5-1-مذاکره 146

4-5-5-2-بخش بحرانی یا Critical Selection. 146

4-5-5-3-اعلام. 146

4-6- اعزام کننده 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-5-زمان‌بندی اولویت.. 150

4-8-6-زمان‌بندی نوبت گردشی.. 151

4-8-6-1-صف چندگانه فیدبک... 151

جدول 4-2- خلاصه الگوریتم زمانبندی.. 152

4-9-زمان‌بندی درسیستم‌عامل‌های مختلف... 152

4-9-1- داس و ویندوزهای اولیه. 152

4-9-2- ویندوز ان‌تی.. 153

4-9-3-ویندوز سرور ۲۰۰۸ و ویندوز ویستا 153

4-10-تعریف زمانبندی در سیستم های چند پردازنده 155

4-11-زمانبندی برای سیستم های دارای پردازنده های ناهمگن.. 156

4-12-چند الگوریتم زیر بهین