طراحي الگوريتم و شبيه‎سازي زمان‎بندي گروهي پوياي كارها در سامانه‎هاي پردازشي توزيع‎شده

درجه كارشناسي ارشد

مهندسي برق گرايش الكترونيك

اسفند ماه 1390

اسفند ماه 1390

دكتر هادي‎شهريار شاه‎حسيني

چكيده در سامانه‎هاي توزيع‎شده، به اشتراك‎گذاري مكاني و زمان‎بندي گروهي به عنوان اصلي‎ترين ديدگاه‎هاي زمان‎بندي شناخته شده‎اند كه از ميان آن‎ها‎ زمان‎بندي گروهي به دليل كاهش ميزان اتلاف توان پردازنده‎ها بيشتر مورد توجه قرار گرفته است. نسخه پايه زمان‎بندي گروهي داراي چهار مرحله اصلي است كه از ميان آن‎ها مرحله ادغام ماتريس، به دليل يكپارچه نمودن فضاهاي خالي در سطرهاي مختلف ماتريس زمان‎بندي، تاثير قابل توجهي بر عملكرد زمان‎بندي گروهي دارد. اين پايان‎نامه در مرحله اول روشي جهت بهبود مرحله ادغام ماتريس در زمان‎بندي گروهي پيشنهاد نموده است. اين روش با بهره‎گيري از دو ايده جديد سعي در برآوردن هر چه بهتر اهداف مرحله ادغام دارد. در مرحله بعد روشي جهت افزايش به‌كارگيري پردازنده‌ها و بهبود زمان پاسخ‌دهي ميانگين با نام زمان‌بندي گروهي حريصانه (GGS) ارائه گرديده است. روش GGS در هر دوره زمان‌بندي از روش پايه زمان‎بندي گروهي استفاده نموده و گروه‌هاي ورودي را به برش‌هاي زماني تخصيص مي‌دهد. آن‌گاه از ميان تمامي برش‌هاي زماني، برشي كه در آن بيشترين تعداد پردازنده‌ها اشغال گرديده به عنوان برش پيروز انتخاب و فرآيند اجراي گروه‌هاي موجود در آن آغاز شده يا ادامه مي‌يابد. اثر هر يك از ايده‎هاي روش پيشنهادي بهبود ادغام ماتريس، به طور جداگانه وهمچنين به صورت همزمان با استفاده از شبيه‎سازي نسبت به روش پايه ادغام ماتريس مقايسه شده است. آزمايش‎ها نشان مي‎دهد، ميزان كاهش زمان پاسخ‎دهي ميانگين (RT) در روش پيشنهادي ادغام ماتريس در مقايسه با روش پايه با در نظر گرفتن سربارهاي مهاجرتي معادل 5، 10 و 15 درصد طول هر يك از برش‎هاي زماني، به ترتيب 2 تا 20، 0 تا 10 و 5- تا 5 درصد بوده است. همچنين مقايسه GGS نسبت به GS نشان مي‌دهد روش پيشنهادي، زمان پاسخ‌دهي ميانگين را در هر يك از سياست‌هاي صف‌بندي تا حدود 75% كاهش مي‌دهد. واژه‌هاي كليدي: ادغام ماتريس، الگوريتم حريصانه، زمان پاسخ دهي، صف‎بندي، مهاجرت.