۰
subtitle
ارسال: #۱
  
الگوریتم RR
ســـــــــــلام دوستای عزیزم.
میشه کمکم کنین؟
الگوریتم rr رو یکی بهم بگه
با مثال که بگه دیگه حله
فداتون شم.منتظرما
میشه کمکم کنین؟
الگوریتم rr رو یکی بهم بگه
با مثال که بگه دیگه حله
فداتون شم.منتظرما
Fardad-A، در تاریخ ۱۴ دى ۱۳۹۱ ۰۷:۵۲ ب.ظ برای این مطلب یک پانوشت گذاشته است:
چون دوست گرامی جواب سوالتون را داده اند تاپیک منتقل شد. لطفا" سوالتون را در محل مناسب درج کنید تا حذف یا بسته نشه. در لینک زیر این موضوع توضیح داده شده است.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
۰
ارسال: #۲
  
الگوریتم RR
سلام دوست خوبم
الگوریتم RR نوع غیر انحصاری الگوریتم FIFO هست یعنی مثل الگوریتم FIFO پردازنده رو به فرایندها به ترتیب ورودشون اختصاص میدیم اما در اینجا تا اتمام کار فرایند یا زمان نیازش به I/O پردازنده در اختیارش نیست
در این الگوریتم CPU رو به فرایندها به اندازه برش زمانی یا time slice اختصاص میدیم و زمانی که برش زمانی یک فرایند تموم شد فرایند باید به انتهای صف فرایندهای در انتظار وارد بشه و فرایند بعد از اون که در صف منتظر پردازش بوده به اندازه برش زمانی CPU رو در اختیار بگیره
یه مثال میزنم. فرض کنین در سیستمی ابتدا فرایند A وارد میشه با زمان اجرای ۵ میلی ثانیه. بعد از ۱ میلی ثانیه فرایند B با زمان اجرای ۴ میلی ثانیه و پس از ۳ میلی ثانیه فرایند C وارد میشه که زمان اجراش ۷ میلی ثانیه است و time slice هم ۲ میلی ثانیه است یعنی در هرنوبت CPU میتونه به هر فرایند ۲ میلی ثانیه اختصاص داده بشه.
در ابتدا و در لحظه صفر فقط فرایند A وجود داره که همونطوری که گفتیم چون برش زمانی ۲ میلی ثانیه است به اندازه ۲ میلی ثانیه فرایند A پردازنده رو در اختیار میگیره و زمان اجراش از ۵ میلی ثانیه به ۳ میلی ثانیه میرسه و وارد صف فرایندهای منتظر میشه.
حالا چون فرایند B در لحظه ۱ وارد شده و بعد از A وارد سیستم شده نوبت اونه که پردازش بشه و CPU به مدت ۲ میلی ثانیه در اختیارش قرار میگیره و B هم زمان اجراش به ۲ میلی ثانیه کاهش پیدا میکنه چون ۴ بود و ۲ میلی ثانیه الان پردازش شده و در صف انتظار فرایندها پشت سر فرایند A قرار میگیره.
آخرین فرایند C وارد سیستم شده و نوبت C هست که CPU بهش داده بشه. فرایند C پردازنده رو در اختیار میگیره تا اون هم ۲ میلی ثانیه اجرا بشه و پس از اون در انتهای صف پشت فرایند B منتظر میشه در حالی که زمانی که برای اجرا لازم داره الان ۵ میلی ثانیه شده.
دوباره همین چرخه تکرار میشه و فرایندها به اندازه برش زمانی یا همون کوانتوم که تو این مثال ۲ میلی ثانیه است به ترتیبی که وارد شدن و الان در صف هستن یعنی A بعد B و سپس C تا زمانی که اجراشون تموم بشه CPU رو در اختیار میگیرن.
فقط باید دقت کرد که فرایندها به ترتیب زمان ورود و هرسری به اندازه برش زمانی پردازنده بهشون واگذار میشه.
یه سری خصوصیاتی هم که الگوریتم RR یا Round-Robin داره اینهاست:
-همون طور که گفتم غیر انحصاریه یعنی پردازنده مثل الگوریتم FIFO تا زمان اجرای فرایند به پایان برسه در اختیارش قرار نمیگیره بلکه به اندازه برش زمانی بهش اختصاص پیدا میکنه ولی مثل FIFO هرفرایندی که زودتر وارد سیستم بشه زودتر سرویس میگیره.
-مناسب سیستم های اشتراک زمانی و محاوره ایه چون عادلانه است و فرایندها به خاطر اجرای یه فرایند به عنوان مثال سنگین مجبور نیستن منتظر بمونن در حالیکه در الگوریتم FIFO این اتفاق می افته.
-قابل پیاده سازی به صورت عملیه چون لازم نیست زمان اجرای فرایندها رو از قبل بدونیم. در مثالی که زدم زمان اجرای هر فرایند از قبل بهمون داده شده بود ولی در عمل تخمین زدن زمانی که هر فرایند نیاز به اجرا داره همیشه ممکن نیست و در این الگوریتم هم لازم نیست بدونیم. برای اجرا شدن و اختصاص CPU به فرایندها ترتیب ورود و مقدار برش زمانی مهمه.
-این الگوریتم قحطی زدگی نداره. چون در هر نوبت به هر فرایند CPU به مدت یکسانی واگذار میشه و تمام فراینها اجرا میشن.
-ساختمان داده مورد استفاده برای صف فرایندها صف حلقوی است.
-در این الگوریتم اگه برش زمانی کوتاه باشه کارایی CPU کاهش پیدا میکنه چون بعد از یه مدت خیلی کوتاه باید CPU از یه فرایند گرفته بشه و به فرایند دیگه داده بشه که به این زمان، زمان سوییچ کردن گفته میشه و برای سیستم سربار محسوب میشه.
-اگه برش زمانی خیلی زیاد باشه الگوریتم به حالت انحصاری خودش یعنی FIFO نزدیکتر میشه چون وقتی time slice زیاد باشه عملا در حق فرایندهایی که به زمان اجرای کمتری نیاز دارن ظلم میشه و ممکنه اونها مدت زمان زیادی تو صف منتظر بشن تا اجرا بشن.
سعی کردم واضح و کامل توضیح بدم. امیدوارم تونسته باشم.
موفق باشید.
الگوریتم RR نوع غیر انحصاری الگوریتم FIFO هست یعنی مثل الگوریتم FIFO پردازنده رو به فرایندها به ترتیب ورودشون اختصاص میدیم اما در اینجا تا اتمام کار فرایند یا زمان نیازش به I/O پردازنده در اختیارش نیست
در این الگوریتم CPU رو به فرایندها به اندازه برش زمانی یا time slice اختصاص میدیم و زمانی که برش زمانی یک فرایند تموم شد فرایند باید به انتهای صف فرایندهای در انتظار وارد بشه و فرایند بعد از اون که در صف منتظر پردازش بوده به اندازه برش زمانی CPU رو در اختیار بگیره
یه مثال میزنم. فرض کنین در سیستمی ابتدا فرایند A وارد میشه با زمان اجرای ۵ میلی ثانیه. بعد از ۱ میلی ثانیه فرایند B با زمان اجرای ۴ میلی ثانیه و پس از ۳ میلی ثانیه فرایند C وارد میشه که زمان اجراش ۷ میلی ثانیه است و time slice هم ۲ میلی ثانیه است یعنی در هرنوبت CPU میتونه به هر فرایند ۲ میلی ثانیه اختصاص داده بشه.
در ابتدا و در لحظه صفر فقط فرایند A وجود داره که همونطوری که گفتیم چون برش زمانی ۲ میلی ثانیه است به اندازه ۲ میلی ثانیه فرایند A پردازنده رو در اختیار میگیره و زمان اجراش از ۵ میلی ثانیه به ۳ میلی ثانیه میرسه و وارد صف فرایندهای منتظر میشه.
حالا چون فرایند B در لحظه ۱ وارد شده و بعد از A وارد سیستم شده نوبت اونه که پردازش بشه و CPU به مدت ۲ میلی ثانیه در اختیارش قرار میگیره و B هم زمان اجراش به ۲ میلی ثانیه کاهش پیدا میکنه چون ۴ بود و ۲ میلی ثانیه الان پردازش شده و در صف انتظار فرایندها پشت سر فرایند A قرار میگیره.
آخرین فرایند C وارد سیستم شده و نوبت C هست که CPU بهش داده بشه. فرایند C پردازنده رو در اختیار میگیره تا اون هم ۲ میلی ثانیه اجرا بشه و پس از اون در انتهای صف پشت فرایند B منتظر میشه در حالی که زمانی که برای اجرا لازم داره الان ۵ میلی ثانیه شده.
دوباره همین چرخه تکرار میشه و فرایندها به اندازه برش زمانی یا همون کوانتوم که تو این مثال ۲ میلی ثانیه است به ترتیبی که وارد شدن و الان در صف هستن یعنی A بعد B و سپس C تا زمانی که اجراشون تموم بشه CPU رو در اختیار میگیرن.
فقط باید دقت کرد که فرایندها به ترتیب زمان ورود و هرسری به اندازه برش زمانی پردازنده بهشون واگذار میشه.
یه سری خصوصیاتی هم که الگوریتم RR یا Round-Robin داره اینهاست:
-همون طور که گفتم غیر انحصاریه یعنی پردازنده مثل الگوریتم FIFO تا زمان اجرای فرایند به پایان برسه در اختیارش قرار نمیگیره بلکه به اندازه برش زمانی بهش اختصاص پیدا میکنه ولی مثل FIFO هرفرایندی که زودتر وارد سیستم بشه زودتر سرویس میگیره.
-مناسب سیستم های اشتراک زمانی و محاوره ایه چون عادلانه است و فرایندها به خاطر اجرای یه فرایند به عنوان مثال سنگین مجبور نیستن منتظر بمونن در حالیکه در الگوریتم FIFO این اتفاق می افته.
-قابل پیاده سازی به صورت عملیه چون لازم نیست زمان اجرای فرایندها رو از قبل بدونیم. در مثالی که زدم زمان اجرای هر فرایند از قبل بهمون داده شده بود ولی در عمل تخمین زدن زمانی که هر فرایند نیاز به اجرا داره همیشه ممکن نیست و در این الگوریتم هم لازم نیست بدونیم. برای اجرا شدن و اختصاص CPU به فرایندها ترتیب ورود و مقدار برش زمانی مهمه.
-این الگوریتم قحطی زدگی نداره. چون در هر نوبت به هر فرایند CPU به مدت یکسانی واگذار میشه و تمام فراینها اجرا میشن.
-ساختمان داده مورد استفاده برای صف فرایندها صف حلقوی است.
-در این الگوریتم اگه برش زمانی کوتاه باشه کارایی CPU کاهش پیدا میکنه چون بعد از یه مدت خیلی کوتاه باید CPU از یه فرایند گرفته بشه و به فرایند دیگه داده بشه که به این زمان، زمان سوییچ کردن گفته میشه و برای سیستم سربار محسوب میشه.
-اگه برش زمانی خیلی زیاد باشه الگوریتم به حالت انحصاری خودش یعنی FIFO نزدیکتر میشه چون وقتی time slice زیاد باشه عملا در حق فرایندهایی که به زمان اجرای کمتری نیاز دارن ظلم میشه و ممکنه اونها مدت زمان زیادی تو صف منتظر بشن تا اجرا بشن.
سعی کردم واضح و کامل توضیح بدم. امیدوارم تونسته باشم.
موفق باشید.
۰
ارسال: #۳
  
الگوریتم RR
عزیزم میشه یا یه پیوست بیشتر راهنمائیم کنی؟
البته اگه میشه!
اگه بشه که حله همه چی...
البته اگه میشه!
اگه بشه که حله همه چی...
۰
۰
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close