پیاده سازی الگوریتم راند رابین در متلب

پیاده سازی الگوریتم راند رابین در متلب عنوان موضوعی است که در این پست به آن پرداخته‌ایم. در این بخش به نحوه پیاده سازی الگوریتم RR در متلب همراه با یک مثال کامل خواهیم پرداخت. سورس کد الگوریتم راند رابین بصورت کامل همراه با زمان‌های اجرا Burst time و زمان ورود Arrival time هر فرآیند آمده است. در ادامه به بررسی این الگوریتم می‌پردازیم.

مفهوم زمانبندی در سیستم عامل

هدف چند برنامه‌گی Multi Programming در سیستم عامل این است که در همه اوقات، پردازشی در حال اجرا وجود داشته باشد تا بهره‌وری cpu بیشینه شود. هدف اشتراک زمانی Time Sharing آن است که cpu مابین پردازش‌ها Process به قدری مکرر، سوئیچ Switch نماید که کاربران با برنامه در حال اجرا محاوره داشته باشند. زمانی که بیش از یک پروسس قابل اجرا باشد سیستم عامل باید تصمیم بگیرد که کدامیک اول اجرا شود.

بخشی از سیستم عامل که این تصمیم گیری را انجام می‌دهد زمانبند Scheduler نامیده می‌شود. پردازش‌هایی که در حافظه اصلی قرار دارند و منتظر اجرا شدن هستند در صفی به نام صف آماده (ready queue) قرار می‌گیرند. این صف معمولاً به شکل یک لیست پیوندی (linked list) پیاده سازی می‌شود. پردازش در حال اجرا بنا به دلایل زیر می‌تواند به صف آماده برود تا زمانبندی مجدد شود:

1. پردازش می‌تواند یک درخواست I/O منتظر بماند تا به آن سرویس داده شود.
2. پردازش می‌تواند یک پردازش جدید (فرزند) ایجاد نموده و برای اتمام آن صبر کند.
3. پردازش به علت تمام شدن برش زمانی (time slice) از cpu جدا می‌شود تا این امکان به بقیه پردازش‌ها نیز داده شود که از بقیه cpu استفاده کنند.
4. پردازش منتظر وقوع یک وقفه باشد.

شکل زیر این حالات را نشان می‌دهد.

معیار های زمانبندی سیستم عامل

1. عدالت (Fairness): یعنی اطمینان از اینکه هر پروسس سهم عادلانه و منصفانه‌ای از cpu را دریافت کند.
2. کارایی یا بهره وری (utilization-Efficiency): cpu یعنی اینکه cpu در تمام زمان‌ها (حتی الامکان) مشغول باشد.
3. زمان پاسخ (Response Time): یعنی به حداقل رساندن زمان پاسخ برای فرمان‌های محاوره‌ای کاربر. این زمان معمولاَ با سرعت ابزار خروجی محدود می‌شود.
4. زمان برگشت (یا گردش کار Turn around): یعنی به حداقل رساندن زمانی که کاربران دسته‌ای باید منتظر بمانند تا خروجی آن‌ها پدید آید. فاصله زمانی از لحظه تحویل کار تا تکمیل کار را زمان برگشت می‌نامند ولی زمان پاسخ مدت زمانی است که از صدور یک تقاضا تا تولید اولین پاسخ آن طول می‌کشد (نه زمان خروجی کل برنامه) – زمان بارگذاری در حافظه + زمان عملیات I/O + زمان اجرا + زمان انتظار در صف آماده = زمان گردش کار
5. توان عملیاتی یا گذردهی (through put): به تعداد پردازش‌هایی که در واحد زمان تکمیل می‌شوند توان عملیاتی می‌گویند. الگوریتم زمانبندی باید به گونه‌ای باشد که این معیار را افزایش دهد.
6. زمان انتظار (waiting time): الگوریتم زمانبندی cpu ، بر میزان زمان اجرای پردازش یا اعمال I/O اثر نمی‌کند ، بلکه فقط در زمان صرف شده جهت انتظار در صف آماده اثر می‌گذارد. زمان انتظار، مجموع پریودهای زمانی صرف شده در صف آماده می‌باشد. البته ممکن است تعدادی از اهداف فوق با هم در تضاد باشند.

الگوریتم راند رابین round robin

الگوریتم راند رابین round robin یا RR یکی از قدیمی‌ترین، ساده‌ترین و عادلانه‌ترین و همچنین پرکاربردترین الگوریتم‌های زمانبندی است که مخصوص سیستم‌های اشتراک زمانی طراحی شده است. در این روش تمام فرآیندها اولویت یکسانی دارند و پس از آنکه هر فرآیند پردازنده را در اختیار گرفت یک کوانتوم زمانی داده می‌شود. سیستم‌عاملی که از زمانبند الگوریتم راند رابین round robin استفاده می‌کند، اولین فرآیند از صف آماده را می‌گیرد، یک شمارشگر را تنظیم می‌کند تا پس از یک کوانتوم زمانی، قطع شده و پردازنده را به فرآیند بعدی بدهد.

اگر زمان متوالی پردازشی این فرآیند کوچکتر از کوانتوم زمانی باشد، آن‌گاه پردازنده را به‌طور داوطلبانه، یا با فسخ و یا صدور یک درخواست I/O آزاد می‌کند. سپس سیستم‌عامل به پردازش فرآیند بعدی حاضر در صف آماده می‌پردازد. در سوی دیگر اگر زمان متوالی پردازشی فرآیند، بزرگتر از کوانتوم زمانی باشد، آن‌گاه شمارشگر بعد از پایان یک کوانتوم زمانی خاموش می‌شود و فرآیند فعلی را قطع کرده (مانع ادامه‌ی اجرای آن می‌شود) و بلوک کنترل فرآیند آن را به انتهای صف آماده ارسال می‌کند.

مثالی از حل الگوریتم زمانبندی راند رابین با زمان ورود در سورس کد پیاده سازی الگوریتم راند رابین در متلب

پردازش‌های زیر را در نظر می‌گیریم و با استفاده از الگوریتم‌های زمانبندی راند رابین round robin، میانگین زمان انتظار Average waiting time  و زمان کامل شدن Average turn around time آن‌ها را به دست می‌آوریم.

فرض می‌کنیم کوانتوم زمانی نیز برابر با ۲ باشد در این صورت فرآیندها به ترتیب بصورت زیر اجرا خواهند شد.

P1,P1,P2,P3,P4,P5,P1,P2,P3,P4,P3,P4,P3,P4,P4

پس از اجرای فرآیندها معیارهای آن‌ها اندازه گیری می‌شود. که بصورت زیر است.

در کد آماده‌ای که پس از خرید این اثر در اختیار شما قرار می‌گیرد می‌توانید همین مثال را در الگوریتم RR آورده و اجرا کنید. برای مثال‌های دیگر نیز به راحتی می‌توانید ورودی‌های جدید را جایگزین کنید.

درباره سورس کد پیاده سازی الگوریتم راند رابین در متلب

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