بخشی از مقاله
چکیده
رشد روز افزون در زمینه کامپیوتر و ارتباطات آن باعث به وجود آمدن سیستم های توزیع شده گردیده است تا تبادل اطلاعات و انجام محاسبات با سرعت بیشتری فراهم گردد.زمانبندی و توازن بار از مسائل مهم در سیستم های توزیع شده می باشد. هدف ما در این مقاله این است که به بررسی برخی از الگوریتم های زمانبندی در سیستم های توزیع شده بپردازیم و مقایسه ی بین آنها انجام دهیم . و ارائه راه حل عملی مبتنی بر واقعیات موجود در سیستم های توزیع شده می باشد.
واژه های کلیدی : الگوریتم های زمانبندی،سیستم توزیع،توازن بار
-1 مقدمه
سیستم های توزیع شده از مجموعه ای از کامپیوترهای مستقل از هم که به واسطه وجود سیستم عامل توزیعی یا میان افزار از دیدگاه کاربر به عنوان یک کامپیوتر واحد به نظر می رسد ، تشکیل شده است.در یک سیستم توزیع شده کاربر از محل انجام پردازش ها، ذخیره سازی اطلاعات و به طور کلی از محل منابع فیزیکی اطلاعی ندارد.این سیستم ها نقش بسیار مهمی در انجام محاسبات پیچیده و بزرگ دارند. تخصیص کارها به منابع موجود در سیستم ها ی محاسباتی توزیع شده باید به گونه ای صورت گیرد که بار کاری به صورت متوازن روی منابع توزیع گردد تا حداکثر بهره وری از منابع موجود حاصل گردد.ایجاد توازن بار که یکی از شاخص های مهم کارایی مدیریت منابع در سیستم های توزیع شده است.[3]این گونه سیستم ها برای داشتن بهره وری بالا با چالش هایی مواجه هستند ، که از جمله این چالش ها که تاثیر بسیار زیادی در بهره وری این سیستم ها دارد مبحث زمان بندی است.مدل ها ، روش ها و الگوریتم های متنوعی برای زمانبندی وظایف در محیط های محاسباتی گزارش شده است که در ادامه به تفصیل به بررسی و ارزیابی این الگوریتم ها خواهیم پرداخت.
-2 زمانبندی
ایده اصلی زمانبندی این است که برای استفاده بهینه از زمان پردازنده، با این فرض که پردازشهای قابل اجرا وجود دارند، یک پردازش همواره باید در حال اجرا باشد. اگر تعداد پردازشها بیش از تعداد پردازندهها باشد، در هر لحظه برخی از پردازشها در حال اجرا نخواهند بود. این پردازشها منتظر اجرا هستند. تصمیمگیری اینکه با داشتن مجموعهای از پردازشهای قابل اجرا، کدام پردازش در مرحله بعد اجرا شود، تصمیم اصلی است که یک زمانبند باید بگیرد.
ملاکهایی که یک الگوریتم زمانبندی خوب باید دارا باشد عبارت است از :
-1 عدالت : - Fairness - هر پروسس سهم عادلانه ای از CPU را دریافت نماید .
-2 کارایی CPU : - Efficiency - بیکار نماند و وقتی پروسس امکان جلو رفتن ندارد CPU به پروسس دیگری داده شود .
-3 زمان پاسخ : - Response Time - زمان پاسخ ، زمان پاسخ به فرمانهای Interactive کاربر است .
-4 حداقل بودن زمان بازگشت : - Turnaround Time - زمان بازگشت برای یک کار Batch طول زمان از لحظه ورود آن به سیستم تا لحظه پایان یافتن - کامل شدن - آن می باشد
-5 حداکثر شدن :Throughput تعداد کارهایی است که در واحد زمان انجام می شود .
-3 الگوریتم های زمانبندی
الگوریتم های زمانبندی مختلف و متفاوتی در سیستم های توزیع شده وجود دارند که هدف اصلی آنها بهترین توان عملیاتی و زمان بهره وری سیستم است.در سیستم های توزیع شده زمانبندی با هدف تعادل بار ، کیفیت سرویس ، بهترین زمان اجرا و توان عملیاتی سیستم انجام می شود.وظیفه یک زمان بند خوب این است که بتواند عملیات زمان بندی و مدیریت و هماهنگ سازی گره ها را به بهترین روش ممکن انجام دهد.
-4 طبقه بندی الگوریتم های زمانبندی
الگوریتم های زمانبندی به دو دسته سراسری و محلی تقسیم می شوند.در زمانبندی محلی در مورد نحوه تخصیص فرایندها به یک پردازنده و اجرای آن تصمیم گیری می شود و در زمانبندی سراسری که از اطلاعات سیستم ها استفاده می کند،تخصیص فرایندها به چندین پردازنده برای بهینه سازی کارایی کلی سیستم صورت می گیرد.
-5 الگوریتم های زمانبندی موجود
-5-1 الگوریتم های اکتشافی
الگوریتم های اکتشافی که به روش DAG برای حل مسائل کار می کنند و انواع مختلفی دارند و هر کدام پیچیدگی زمانی خاص خود را دارند.
-5-1-1 الگوریتم کلونی مورچه ها - - ACO
این الگوریتم براساس رفتار مورچه های واقعی است.وقتی که هر مورچه در یک مسیر به خصوص حرکت می کند میزان فرمون آن مسیر قویتر می شود.که به وسیله این فرمون ها مورچه ها می توانند مسیر را دنبال کنند.
-5-1-2 الگوریتم LDCP
این الگوریتم از سه مرحله مختلف تشکیل شده است: -1انتخاب کار -2 انتخاب پردازنده -3 بروز کردن وضعیت
در مرحله اول یک مجموعه از کارهایی که نقش اساسی در تعیین طول زمانبندی دارند مشخص می گردند.
در مرحله دوم کار انتخابی به پردازنده ای سپرده می شود که زمان اجرای کمتری دارد و در مرحله سوم بعد از انجام کار سیستم بروز می شود.که پیچیدگی زمانی این روش برابر است با - P*Q^3 - که mتعداد پردازنده و n تعداد کار در سیستم می باشد.[1]
-5-1-3 الگوریتم SNNLD
در این الگوریتم کارها در هر سطح براساس و بر حسب اندازه خودشان دسته بندی می شوند.این الگوریتم بر پایه تقسیم DAG به سطوحی بر حسب سطح وابستگی در میان کارها در DAG می باشد.
