13892

13892

طراحي، شبيه سازي و بهبود ماتريس زمان بندي جهت زمان بندي گروهي وظايف در سامانه هاي خوشه اي

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

برق - الكترونيك

شهريورماه 1393

شهريورماه 1393

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

دكتر كريم محمدي

چكيده الگوريتم¬هاي زمان¬بندي در بالاترين سطح به دو دسته اشتراك مكاني و اشتراك زماني تقسيم مي¬شوند. در بين تمامي الگوريتم¬هاي زمان¬بندي، زمان¬بندي گروهي به دليل كاهش ميزان اتلاف توان پردازنده¬ها از اهميت ويژه¬اي برخوردار است. نسخه پايه زمان¬بندي گروهي در چهار مرحله اصلي انجام مي¬شود. در بين مراحل چهارگانه زمان¬بندي گروهي مرحله چهارم آن پر كردن ماتريس نام دارد كه از اهميت بالايي برخوردار است. در اين مرحله زمان¬بند سعي مي¬كند شيارهاي بدون بار ماتريس زمان¬بندي را تا جاي ممكن با تكثير گروه¬هاي موجود در ماتريس زمان¬بندي پر نمايد. در نسخه پايه زمان¬بندي گروهي پر كردن ماتريس بر اساس اولويت زمان شروع گروه¬ها انجام مي¬شود. اين پايان¬نامه در مرحله اول روشي در جهت بهبود مرحله پر كردن ماتريس ارائه مي¬كند. در روش فوق عمليات تكثير گروه¬ها بر اساس اولويت بزرگي آن¬ها انجام مي¬شود. منظور از گروه بزرگ گروهي است كه داراي تعداد وظايف بيشتري باشد. در مرحله دوم روشي براي افزايش خدمت¬رساني به گروه¬هاي بزرگ بر مبناي زمان¬بندي گروهي و در جهت كاهش زمان پاسخ¬دهي ميانگين وزن¬دار (WRT) ارائه مي¬شود. روش فوق در هر دوره زمان¬بندي از روش پايه زمان¬بندي گروهي استفاده نموده و گروه¬هاي ورودي را به برش¬هاي زماني تخصيص مي¬دهد. سپس از ميان تمامي برش¬هاي زماني، برشي كه داراي بزرگ¬ترين گروه موجود در ماتريس زمان¬بندي است را انتخاب كرده و فرآيند اجراي گروه¬هاي موجود بر روي آن را اغاز مي-كند و يا ادامه مي¬دهد. روش پيشنهاد شده در مرحله پر كردن ماتريس توسط شبيه¬سازي با روش پايه مقايسه شده است. نتايج شبيه¬سازي نشان مي¬دهد كه ميزان كاهش زمان پاسخ¬دهي ميانگين (RT) در روش پيشنهادي نسبت به روش پايه به ازاي سياست¬هاي صف¬بندي FCFS، AFCFS و LGFS حداكثر 34، 13 و 11 درصد بوده است. همچنين مقايسه روش پيشنهادي در انتخاب گروه¬هاي بزرگ با روش پايه زمان¬بندي گروهي نشان مي¬دهد زمان پاسخ¬دهي ميانگين وزن¬دار (WRT) در روش پيشنهادي نسبت به روش پايه در بارهاي كاري سنگين (فاصله زماني كوتاه مابين ورود كارها به سامانه) و به ازاي سياست¬هاي صف¬بندي AFCFS و LGFS حداكثر 63 و 69 درصد و در بارهاي كاري سبك حداقل 22 درصد كاهش پيدا مي¬كند. واژه¬هاي كليدي: زمان¬بندي گروهي، پر كردن ماتريس، زمان پاسخ¬دهي ميانگين، زمان پاسخ-دهي ميانگين وزن¬دار، سياست¬هاي صف¬بندي