\documentclass[12pt,a4paper,twocolumn]{article}

\usepackage{ptext} 
\usepackage{graphicx}
\usepackage{amsmath} 
\usepackage[colorlinks=true]{hyperref} 
\usepackage{float}
\usepackage{xepersian}
\settextfont{B Nazanin}
\setlatintextfont[Scale=1]{Times New Roman}
\title{ارزیابی عملکرد دسته ای از گروه ها در یک سیستم توزیع شده ناهمگن}
\author{مهین وظیفه دان\\
گروه کامپیوتر،دانشگاه آزاد اسلامی واحد مشهد،ایران\\
\texttt{mahinvazifehdan@yahoo.com}
}
\date{\today}

\begin{document}
\twocolumn[
\begin{@twocolumnfalse}
\maketitle
\begin{abstract}
 سیستم های توزیع شده یک راه حل مقرون به صرفه و مقیاس پذیر به منظور افزایش برنامه های فشرده با استفاده از چندین منبع به اشتراگ گذاشته شده را ارائه میدهد.زمان بندی گروهی یک الگوریتم زمان بندی موثر برای سیستم های توزیع شده و موازی میباشد.در این مقاله ما عملکرد سیاست های زمان بندی دسته ای از گروه های مستقل در یک سیستم توزیع شده ناهمگن را مورد بررسی قرار میدهیم.یک مدل شبیه سازی به منظور ارزیابی عملکرد زمان بندی دسته ای از گروه ها در حضور کارهای با اولویت بالا همراه با پیاده سازی مهاجرت در نظر گرفته شده است.نتایج شبیه سازی نقش قابل توجه طرح مهاجرت پیاده سازی شده را به عنوان فاکتور تعادل بار در یک سیستم توزیع شده ناهمگن نشان میدهد.یکی دیگر از جنبه های قابل توجه پیاده سازی مهاجرت کاهش تکه تکه شدن ناشی از زمان بندی گروه ها و همچنین جلوگیری از اثر ورود کارهای با اولویت بالا در محیط ناهمگن میباشد.
 

کلمات کلیدی: زمان بندی گروهی،استراتژی های زمان بندی،سیستم های توزیع شده،کارایی،شبیه سازی
\end{abstract}
\end{@twocolumnfalse}
]
\section{مقدمه}  \label{section.intro}
سیستم های توزیع شده به دلیل ویژگی های قابل توجه شان مانند مقرون به صرفه بودن،قابلیت مقیاس پذیری،عملکرد و قابلیت اطمینان پذیریشان بسیار محبوب شده اند.یک سیستم توزیع شده از تعدادی منابع به اشتراک گذاری شده تشکیل شده است که به وسیله یک شبکه ارتباطی به یک دیگر متصل شده اند.منابع محلی میتوانند در قالب یک کلاستر گروه بندی شوند و بخشی از یک شبکه گسترده تر(گرید) را ایجاد کنند.به دلیل وجود کلاسترها در اندازه و عملکرد های متفاوت،ما شاهد سیستم های ناهمگن متفاوتی هستیم.

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

زمان بندی گروهی یک الگوریتم زمان بندی اشتراک گذاری کارامد برای اجرای موازی وظایف در یک سیستم توزیع شده ناهمگن میباشد.در حقیقت مفهوم اصلی زمان بندی گروهی این است که تمام وظایف مربوط به یک کار را گروه بندی کند تا گروه حاصل شود و سپس بعد از آن شروع به اجرای همزمان وظایف بر روی پردازنده های مختلف کنیم.در این روش،ما خطر انتظار یک وظیفه که هنوز در حال اجرا بر روی هیچ پردازنده ای نیست را از بین میبریم.نکته قابل توجه این است که نباید تعداد وظایف یک گروه از تعداد پردازنده های در دسترس بیشتر باشند،به عبارتی دیگر باید نگاشتی یک به یک بین وظایف یک گروه و پردازنده های در دسترس وجود داشته باشد.در این مقاله،ما کارهایی خواهیم داشت که دسته ای از گروه های مستقل هستند نه گروه های تنها.یک کار یا دسته ای از گروه ها زمانی اجرایش به پایان رسیده است که تمام گروه های متعلق به آن دسته اجرایشان به اتمام رسیده باشد.گروه های متعلق به یک دسته میتوانند بر روی هر پردازنده ای با هر ترتیبی اجرا شوند.در زمان بندی گروهی بیشتر اوقات ما شاهد بیکاری اکثر پردازنده های سیستم هستم به همین دلیل چالشی به نام تکه تکه شدن در اجرای وظایف به وجود میاید که باعث افت شدید کارایی میشود،به بیان ساده تر زمان هایی وجود دارد که اکثر پردانده ها در حال اجرای وظایف هستند ولی برعکس،در واحدی از زمان ما شاهد بیکاری اغلب پردازنده ها هستیم به دلیل آنکه وظیفه مناسبی در اختیار پردازنده قرار نگرفته است.راه حل استفاده شده در این مقاله،مهاجرت پویای وظایفی است که قابلیت اجرا بر روی پردازنده های خود را ندارند،این کار باعث ایجاد سیستمی با انعطاف پذیری بالا و کارایی مناسب خواهد شد.در نتیجه میتوان گفت سیستم های چند کلاستری برای رسیدن به تعادل بار نیاز به عمل مهاجرت دارند.


ساختار مقاله بدین صورت میباشد که در بخش
\ref{relatedwork.intro}
کارهای مربوطه،در بخش
\ref{system.intro}
توصیفی از سیستمی که قرار است ارزیابی بر روی آن صورت گیرد را خواهیم داشت در بخش 
\ref{strategi.intro}
استراتژِی های زمان بندی،در بخش 
\ref{evaluation.intro}
نتایج شبیه سازی و ارزیابی و در بخش
\ref{calcusion.intro}
جمع بندی و کارهای آینده را توضیح خواهیم داد.



\section{کارهای مربوطه} \label{relatedwork.intro}
در ناهمگنی در سیستم های مختلف از دیدگاه های مختلفی نشان داده شده است،دو نوع ناهمگنی تعریف شده است، ناهمگنی زمانی که به تنوع در محاسبه قدرت یا پهنای باند ارتباطات در دسترس برای یک وظیفه در طول بُعد زمان اشاره دارد و ناهمگنی فاصله ای که به قابلیت تغییر پذیری قدرت محاسبات میان کامپیوترها توجه میکند.در زمان بندی کارهای موازی در یک محیط ناهمگن مورد مطالعه قرار گرفته است که در هر موقعیت،مجموعه ای از پردازنده های یکسان در سیستم وجود دارند.پردازنده ها بسته به اینکه در چه شرایطی قرار دارند سرعت های مختلفی را از خود نشان میدهند.با توجه به عدم شباهت کلاسترها از نظر توان محاسباتی بهتر است در ارزیابی های خود از سیستمی استفاده کنیم که کلاسترهای مشابهی نداشته باشند.ما در تحقیقات خود،سیستمی را به کار برده ایم که از این قاعده تبعیت میکند.سیستمی که تعداد پردازنده ها در کلاسترها متفاوت میباشند هرچند پردازنده های یکسانی به کار برده شده است.در حقیقت این رویکرد میتواند نماینده سیستم های مدرن به حساب آید به دلیل اینکه پردازنده ها در تعدا هستشان متفاوت هستند نه در سرعت محاسباتیشان.

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

\section{سیستم و مدل های حجم کاری} \label{system.intro}
در این مطالعه از یک مدل شبیه سازی برای بررسی عملکرد زمان بندی گروهی دسته ای از گروه ها استفاده شده است.سیستمی با دو کلاستر ناهمگن که کلاستر اولی دارای 16 پردازنده و کلاستر دومی دارای 32 پردازنده میباشد،ساختار سیستم مورد نظر را میتوانید در شکل\ref{pic-1} مشاهده فرمایید.نتیجه میگیریم که کلاستر دومی از توان محاسباتی بالاتری برخوردار است،هر پردازنده ای مسئولیت سرویس دهی صف خود را برعهده دارد.در این مقاله ما فرض میکنیم که ارتباط بین پردازنده ها بدون مداخله میباشد.زمان سرویس به طور نمایی برابر با $1/\mu$
است.حجم کاری که در سیستم شاهد آن خواهیم بود شامل دو نوع کار است:دسته ای از گروه ها و کارهایی با اولویت بالا.

دسته ای از گروه های مستقل در شکل\ref{pic-3} نشان داده شده است،توجه نمایید که یک گروه قسمتی از یک دسته به حساب میاید.تعداد گروه ها در هر دسته در بازه 4-1 میباشد.پس در نتیجه میتوان گفت تعداد متوسط گروه ها در هر دسته برابر با 2.5=4+1 است.همچنین هر گروه دارای وظایفی است که تعداد وظایف در بازه 8-1 میباشند که میتوانید ساختار گروه را در شکل\ref{pic-2} مشاهده فرمایید.تعداد متوسط وظایف در هر گروه برابر با 4.5=8+1 میباشد.نرخ ورود کارهای دسته ای از گروه ها،$\lambda_1 $ و نرخ ورود کارهای با اولویت بالا برابر با $\lambda_2 $ است  که در این مطالعه توجه ما بیشتر مقدار نرخ ورود دسته ای از گروه ها میباشد.لازم به ذکر است که نرخ ورود دسته ای از گروه ها در سیستم بیشتر از نرخ ورود کارهای با اولویت بالا میباشد.

\begin{figure} [H]
\centering
\includegraphics[width=0.52\textwidth,height=7cm]{BOG.jpg}
\caption{مدل صف بندی شبکه}
\label{pic-1}
\end{figure}

\begin{figure}[H]
\includegraphics[width=0.5\textwidth,height=5cm]{gang.jpg}
\centering
\caption{ساختار یک گروه مستقل}
\label{pic-2}
\end{figure}

\begin{figure*} [H]
\includegraphics[width=0.5\textwidth,height=7cm]{Bogs.jpg}
\centering
\caption{ساختار دسته ای از گروه ها}
\label{pic-3}
\end{figure*}



در این مطالعه،ما درنظر گرفته این که هر کار با اولویت بالا تنها دارای یک وظیفه باشد،همان طور که قبلا اشاره شد،کارهای با اولویت بالا به محض ورود به سیستم نیاز دارند که سریع اجرا شوند بنابراین ما مجبور خواهیم شد وظیفه ای که در حال اجرا بر روی یک پردازنده است را به حالت مسدود برده و کار با اولویت بالا را به حالت اجرا هدایت نماییم.وظیفه ای که به حالت مسدود میرود قطعا متعلق به یک گروه خاصی است،مسدود شدن یک وظیفه گروه منجر به مسدود شدن تمام وظایف آن گروه میشود و همچنین باعث از بین رفتن تمام پیشرفت های انجام شده میشود و همه وظایف متعلق به یک گروه باید دوباره اجرا شوند.بدیعی است که هر چه زمان مسدود شدن وظایف بیشتر باشد،زمان پاسخ گروه هم بیشتر و در نهایت زمان پاسخ کار هم بیشتر خواهد شد.متوسط زمان سرویس کارهای با اولویت بالا برابر با $1/\mu_2 $ و متوسط زمان سرویس دسته ای از گروه ها برابر با $1/\mu_1 $ میباشد.

\section{استراتژی های زمان بندی} \label{strategi.intro}
\subsection{مسیریابی کار}
یکی از مهم ترین قسمت های یک سیستم کلاستربندی شده،توزیع کننده سراسری است که مسئولیت توزیع کردن مناسب کارها بین کلاسترها را بر عهده دارد،معیار انتخاب مناسب کلاستر برای کاری که به تازگی وارد سیستم شده است تعداد گروه های متعلق به دسته و توان محاسباتی کلاستر برای پردازش میباشد.اگر تعداد گروه های یک دسته مقادیر 1 یا 2 باشند،توزیع کننده سراسری ، کار را به کلاستر اولی که دارای 16 پردازنده است ارسال خواهد کرد و اگر تعداد مقادیر 3 یا 4 باشند،کار به کلاستر دومی ارسال خواهد شد.احتمال حضور یک کار با اولویت بالا در هر کدام از کلاستر ها برابرا است. توزیع کننده محلی که در هر کدام از کلاستر ها وجود دارند،مسئولیت توزیع کردن وظایف برای صف های در دسترس را بر عهده دارند.باید توجه کرد وظایفی که متعلق به یک گروه هستند(وظایف هم نژاد) نمیتوانند در اختیار یک پردازنده قرار گیرند به دلیل اینکه یک گروه زمانی میتواند اجرا شود که تمام وظیفه هایش به صورت همزمان اجرا شوند.قاعدتا یک پردازنده نمیتواند یه صورت همزمان دو وظیفه هم نژاد را اجرا کند.

در مجموع تعداد پردازنده های سیستم برابر با 48=32+16 میباشد،نرخ ورود کارهای با اولویت بالا به نسبت تعداد پردازنده ها بسیار کم و برابر با1.5,1.10=$ \lambda_2 $ است.در حقیقت میتوان گفت در هر واحد زمانی سیستم پاسخگوی 48 کار با اولویت بالا است ولی از آنجایی که نرخ ورود این نوع کار بسیار کم است ما هیچ زمانی در سیستم خواهیم داشت که تمام پردازنده ها توسط کارهای با اولویت بالا اشغال شوند.با این وجود حتی یک نرخ ورود کم $\lambda_2 $ اثر قابل توجهی را بر روی عملکرد سیستم میگذارد به دلیل اینکه زمانی که یک کار با اولویت بالا وارد سیستم میشود پردازنده ای را از یک وظیفه میگیرد و مسدود شدن وظیفه منجر به مسدود شدن تمام وظایف هم نژادش میشود و وظایف مجبورند تا دوباره زمان بندی شوند و همچنین پیشرفت کارشان را از دست میدهند.
\subsection{زمان بندی گروهی}
در مدل شبیه سازیمان از استراتژی های زمان بندی زیر برای بررسی عملکرد دسته ای گروه ها استفاده کرده ایم.لازم به ذکر است که زمان بند از زمان اجرای وظایف اطلاعی ندارد بلکه تنها از تعداد وظایف یک گروه مطلع است.
\subsubsection{اولین ورود اولین سرویس تطبیق شده}
\subsubsection{بزرگ ترین گروه،اولین سرویس شده}

\section{ارزیابی و شبیه سازی} \label{evaluation.intro}


\section{جمع بندی و کارهای آینده} \label{calcusion.intro}

\section{منابع}

\end{document}