الگوریتم HRRN – آموزش و توضیح به زبان ساده
![الگوریتم HRRN – آموزش و توضیح به زبان ساده](https://blog.faradars.org/wp-content/webp-express/webp-images/doc-root/wp-content/uploads/2024/08/Conceptual-illustration-of-SQL-triggers-showcasing-data-flow.jpg.webp)
الگوریتم HRRN یا «بالاترین نسبت پاسخ» یکی از الگوریتمهای زمان بندی CPU است که عملیات اجرای پردازشها را با روش سریعتر، عادلانهتر و کارآمدتری زمانبندی میکند. این الگوریتم از نوع الگوریتمهای انحصاری است و به عنوان یکی از بهینهترین روشهای زمانبندی CPU شناخته میشود. «زمان بندی پردازشها» (Process Scheduling) در سیستم عامل به فرایندی گفته میشود که به کمک آن، میتوان تصمیم گرفت، کدام پردازش، CPU را اشغال کند و کدام پردازشها برای اجرا شدن در نوبت بمانند. هدف اصلی از فرایند زمانبندی CPU این است که سیستم عامل حداقل یکی از پردازشهای در دسترس را از صف پردازشهای آماده به اجرا برای زمانهای بیکار شدن CPU از پیش انتخاب کرده باشد. الگوریتم HRRN یا تکنیک زمانبندی «بالاترین نسبت پاسخ» (Highest Response Ratio Next) بخشی از زمانبندی CPU به روش انحصاری است.
در این مطلب از مجله فرادرس درباره الگوریتم بالاترین نسبت پاسخ برای زمانبندی CPU و مزایا و معایب آن با بیان جزئیات، بحث کردهایم. همچنین، سعی میکنیم که فرایند اجرای این عملیات زمانبندی را با کمک مثالها، الگوریتمها و برنامههای مختلف نمایش دهیم. یکی از مهمترین فوائد الگوریتم HRRN «جلوگیری از گرسنگی» (Starvation Prevention) است. «گرسنگی» یا «قحطیزدگی» در علوم کامپیوتر، به مشکلی میگویند که در طی آن پردازشی به دلیل اولویت پایینتر نسبت به سایر پردازشها خیلی دیر یا حتی هیچگاه موفق به دسترسی به منبع CPU نمیشود.
الگوریتم HRRN چیست؟
الگوریتم HRRN یکی از بهینهترین روشهای زمانبندی CPU است. این الگوریتم توسط «برینچ هانسن» (Brinch Hansen) توسعه پیدا کرده تا از روی دادن مشکل گرسنگی جلوگیری کند. در الگوریتمهای «اول، کوتاهترین کار» (Shortest Job First) و «بعدا کوتاهترین کار» (Shortest Job Next) با مشکل گرسنگی روبهرو میشویم.
عبارت HRRN سرنامی از واژههای عبارت «Highest Response Ratio Next» است. این الگوریتم از نوع الگوریتمهای انحصاری یا «Non-Preemptive» است. به این معنا که الگوریتم HRRN هیچ پردازشی را بعد از شروع شدن متوقف نمیکند - مگر تا زمانی که فرایند اجرای پردازش به پایان برسد. - زمانبندی HRRN بر اساس پارامتر اضافی پایهگذاری شده است که به نام «نسبت پاسخ» (Response Ratio) شناخته میشود. در این نوع از مسائل، تعداد N پردازش با «زمان ورود» (Arrival Time) و «زمان تکمیل فرایند» (Burst Time) به ازای هر کدام داده میشود. هدف این است که میانگین زمان انتظار برای اجرا و میانگین زمان تکمیل فرایند را با استفاده از الگوریتم HRRN محاسبه کنیم.
![فضای نمادینی از قطعات الکترونیکی بر روی برد - الگوریتم HRRN](https://blog.faradars.org/wp-content/uploads/2024/08/Artistic-depiction-of-the-concept-of-converting-code-into-art.jpg)
همینطور که از نام الگوریتم مشخص است، در ابتدا باید نسبت پاسخ را برای همه پردازشهای در دسترس مشخص کنیم، سپس هر کدام که بالاترین نسبت پاسخ را داشت انتخاب میکنیم. هر پردازشی که انتخاب شد تا زمان تکمیل فرایندش به طور کامل، اجرا خواهد شد. در پایین فرمول محاسبه نسبت پاسخ را نمایش دادهایم.
نسبت پاسخ
در فرمول بالا WT نمایانگر زمان انتظار برای هر پردازش و BT نمایانگر زمان تکمیل فرایند برای هر پردازش است.
مزایا و معایب الگوریتم HRRN
همینطور که میدانیم هر الگوریتمی بر اساس مزایا و نیازهایی طراحی شده است. اما از طرف دیگر، بیشتر الگوریتمها هم دارای محدودیتها و معایب خاص خود هستند. الگوریتم HRRN هم از این قضیه مستثنا نیست. در این بخش به معرفی مزایا و معایب این الگوریتم پرداختهایم.
مزایا
به صورت مختصر و مفید میتوان مزایای الگوریتم «بالاترین نسبت پاسخ» را در سه مورد کلی زیر، خلاصه کرد.
- این الگوریتم زمانبندی نسبت به الگوریتم زمانبندی «اول کوتاهترین کار» ( Shortest Job First) بازدهی بیشتری دارد.
- در این تکنیک زمان انتظار برای پردازشهای طولانی کاهش پیدا میکند. در عین حال CPU، بسته به نسبت پاسخ پردازشهای کوتاهتر هم اختصاص داده میشود.
- با استفاده از الگوریتم HRRN، توان عملیاتی افزایش پیدا میکند.
معایب
معایب این الگوریتم را نیز میتوان به صورت خلاصه به صورت موارد فهرست شده در زیر بیان کرد.
- از آنجا که زمان مورد نیاز برای اجرای هیچ فرایندی را نمیتوان از قبل تعیین کرد، این الگوریتم زمانبندی، قابل پیادهسازی نیست.
- امکان دارد که CPU با «سربار» (Overloading) روبهرو شود.
آشنایی با نوشتن الگوریتم در فرادرس
مطالعه این مطلب به این معنا است که تا حد خوبی با الگوریتمها آشنا هستیم. الگوریتمها در حال حاضر نقش بسیار کلیدی در اکثر پلتفرمها و برنامههای بزرگ و مهم بازی میکنند. برنامههای بزرگتر و کاربردیتر نیاز به مدیریت بهتری هم در مصرف منابع زمان و حافظه دارند. طراحی الگوریتم و پیادهسازی آن خود، تخصص دیگری است که برنامهنویسان خبره باید بر آن مسلط باشند. در ادامه این مطلب، نحوه نوشتن الگوریتم HRRN را نمایش دادهایم، ولی در جایگاه برنامهنویس باید به صورت مستقل نیز توانایی نوشتن الگوریتمها را داشته باشید.
![مجموعه آموزش طراحی الگوریتم – درس، تمرین، حل مثال و تست](https://blog.faradars.org/wp-content/uploads/2024/08/Algoritm-design-learning-collection.png)
فرادرس به عنوان یکی از معتبرترین تولید کنندگان فیلمهای آموزشی فارسی در کشور، فیلمهای آموزشی خوبی را درباره انواع الگوریتمها و تکنیکهای پیادهسازی و استفاده از هر کدام منتشر کرده است. فیلمهای آموزشی فرادرس با توجه به دو حوزه برنامهنویسی عملی و آموزشی تولید شدهاند. هر توسعهدهنده نرمافزاری با مشاهده این فیلمها میتواند مهارت و دانش خود را برای حل مسائل الگوریتمی به طرز بسیار خوبی افزایش دهد. از طرف دیگر دانشجویان و دانشآموزان نیز با کمک این فیلمها میتوانند خود را برای آزمونهای آکادمیک مانند کنکور ارشد و دکتری آماده کنند.
در پایین چهار مورد از فیلمهای آموزشی فرادرس درباره الگوریتم را معرفی کردهایم. هر کدام را که مایل هستید، با توجه به نیاز خود، انتخاب کنید. البته با کلیک بر روی تصویر بالا میتوانید به صفحه اصلی این مجموعه آموزشی هدایت شده و از باقی فیلمها نیز دیدن کنید.
- فیلم آموزش طراحی الگوریتم به صورت جامع و با مفاهیم کلیدی در فرادرس
- فیلم آموزش رابطه های بازگشتی در طراحی الگوریتم و ساختمان گسسته همراه با مرور و تست کنکور ارشد در فرادرس
- فیلم آموزش طراحی الگوریتم همراه با حل مثال های عملی در فرادرس
- فیلم آموزش حل سوالات آزمون های استخدامی طراحی الگوریتم در فرادرس
زمان بندی بالاترین نسبت پاسخ
همینطور که در مطالب بالا بیان شد، معیار زمانبندی بر اساس نسبت پاسخ تعیین میشود. در این تکنیک، پردازش بعدی که در صف پردازشهای آماده برای اجرا قرار دارد، بر اساس بالاترین نسبت پاسخ انتخاب شده و به CPU ارسال میشود.
نسبت پاسخ هم بر اساس فرمول گفته شده در بالا یعنی محاسبه میشود.
مثال
جدول نمایش داده شده در پایین را به عنوان مثالی از بالاترین نسبت پاسخ در نظر میگیریم، در این جدول سه ستون وجود دارد. در این ستونها اطلاعات مربوط به پردازشها و زمان ورود و تکمیل انجام فعالیتشان ذخیره شده است. همانطور که به پیش میرویم، میبینیم که نمودار Gantt چگونه توسعه پیدا میکند.
پردازش | زمان ورود پردازش | «زمان مورد نیاز برای انجام کار» (Burst Time) |
P1 | 0 | 2 |
P2 | 2 | 6 |
P3 | 4 | 7 |
P4 | 5 | 3 |
P5 | 7 | 5 |
فرایند الگوریتم زمانبندی CPU با روش بالاترین نسبت پاسخ به صورت زیر انجام میشود.
در زمان ۰
تنها فرایند P1 در دسترس است. بنابراین اجرای این فرایند شروع شده و تا زمان به پایان رسیدن تکمیل کار ادامه پیدا میکند.
ستونی به اسم ستون «زمان تکمیل عملیات» (Completion Time) به جدول اضافه شده است و جدول به شکل زیر تغییر میکند.
«زمان ورود» (Arrival Time) - پردازش | «زمان مورد نیاز برای انجام کار» (Burst Time) | «زمان تکمیل عملیات» (Completion Time) |
P1 - 0 | 2 | 2 |
P2 - 2 | 6 | |
P3 - 4 | 7 | |
P4 - 5 | 3 | |
P5 - 7 | 5 |
به ترتیب صف مربوط به وظایف انجام شده به شکل زیر شروع به پر شدن میکند.
P1 |
در زمان ۲
در این زمان فرایندهای P1 و P2 در دسترس هستند. اما میدانیم که HRRN از نوع الگوریتمهای انحصاری است. بنابراین اول از همه باید روند اجرای پردازش در حال فعالیت - P1 - به پایان برسد و سپس پردازش بعدی - P2 - برای اجرا به CPU ارسال شود. بعد از به اتمام رسیدن کار P1 از آنجا که تنها پردازش در صف اجرا پردازش P2 است، P2 به CPU ارسال میشود.
پردازش P2 هم فرایند اجرای خود را در زمان ۸ به پایان میرساند. بنابراین جدول به شکل زیر تکمیل میشود.
«زمان ورود» (Arrival Time) - پردازش | «زمان مورد نیاز برای انجام کار» (Burst Time) | «زمان تکمیل عملیات» (Completion Time) |
P1 - 0 | 2 | 2 |
P2 - 2 | 6 | 8 |
P3 - 4 | 7 | |
P4 - 5 | 3 | |
P5 - 7 | 5 |
باز هم صف مربوط به وظایف پردازش شده، تکمیل میشود.
P1 | P2 |
در زمان ۸
در این زمان پردازشهای P3 و P4 و P5 در دسترس هستند. زیرا زمان رسیدن به صف همه این پردازشها تا زمان ۸ اتفاق افتاده است.
از انجا که در صف پردازشهای آماده به اجرا سه پردازش مختلف وجود دارند، برای دسترسی به CPU باید همه آنها زمانبندی شوند. در نتیجه با استفاده از فرمول نمایش داده شده در بالای مطلب، «بالاترین نسبت پاسخ» را برای هر کدام از پردازشهای P3 و P4 و P5 حساب میکنیم.
نسبت پاسخ برای P3 برابر است با [(8 - 4) + 7]/ 7 = 1.57
نسبت پاسخ برای P4 برابر است با [(8 - 5) + 3]/ 3 = 2
نسبت پاسخ برای P5 برابر است با [(8 - 7) + 5]/ 5 = 1.2
با توجه به محاسبات بالا، نسبت پاسخ برای P4 بالاترین نسبت است. بنابراین پردازشی که باید در زمانبندی به عنوان گزینه بعدی به CPU ارسال شود P4 است.
«زمان ورود» (Arrival Time) - پردازش | «زمان مورد نیاز برای انجام کار» (Burst Time) | «زمان تکمیل عملیات» (Completion Time) |
P1 - 0 | 2 | 2 |
P2 - 2 | 6 | 8 |
P3 - 4 | 7 | |
P4 - 5 | 3 | 11 |
P5 - 7 | 5 |
در نتیجه صف مربوط به وظایف پردازش شده به شکل زیر میشود.
P1 | P2 | P4 |
در زمان ۱۱
در این زمان P3 و P5 پردازشهای در دسترس هستند. از آنجا که زمان رسیدن این دو پردازش از صف آماده به اجرا درون زمان ۱۱ است، هر دوی این پردازشهای آماده ارسال به پردازنده هستند.
![زنجیرهای از دادهها به صورت منظم و نورانی](https://blog.faradars.org/wp-content/uploads/2024/08/Illustration-of-a-detailed-overview-of-image-segmentation-techniques.jpg)
باز هم به شکل بالا باید عمل کنیم. یعنی در واقعی دو پردازش P3 و P5 به صورت همزمان آماده اشغال CPU هستند. باید بین این دو پردازش نسبت پاسخ محاسبه شود تا پردازشی با بالاترین Response Ratio شناسایی شده و در اول صف انتظار برای اشغال CPU قرار بگیرد.
نسبت پاسخ برای P3 برابر است با [(11 - 4) + 7)/ 7 = 2
نسبت پاسخ برای P5 برابر است با [(11 - 7) + 5)/ 5 = 1.8
با توجه به محاسبات بالا، بالاترین نسبت پاسخ به P3 تعلق میگیرد. بنابراین پردازشی که باید بعد از پایان عملیات CPU به آن ارسال شود P3 است.
«زمان ورود» (Arrival Time) - پردازش | «زمان مورد نیاز برای انجام کار» (Burst Time) | «زمان تکمیل عملیات» (Completion Time) |
P1 - 0 | 2 | 2 |
P2 - 2 | 6 | 8 |
P3 - 4 | 7 | 18 |
P4 - 5 | 3 | 11 |
P5 - 7 | 5 |
در نتیجه صف وظایف پردازش شده به شکل زیر میشود.
P1 | P2 | P4 | P3 |
در زمان ۱۸
الان بعد از تکمیل عملیات P3 تنها پردازشی که در صف اجرا باقی مانده P5 است. بنابراین، P5 پردازش بعدی است که به CPU ارسال میشود و تا پایان فرایند اجرا هم CPU را در اختیار خودش نگهمیدارد.
«زمان ورود» (Arrival Time) - پردازش | «زمان مورد نیاز برای انجام کار» (Burst Time) | «زمان تکمیل عملیات» (Completion Time) |
P1 - 0 | 2 | 2 |
P2 - 2 | 6 | 8 |
P3 - 4 | 7 | 18 |
P4 - 5 | 3 | 11 |
P5 - 7 | 5 |
در نهایت، صف مربوط به وظایف پردازش شده به شکل زیر میشود.
P1 | P2 | P4 | P3 | P5 |
همینطور که مشاهده میشود، در نهایت میتوانیم زمان کامل اجرای پردازشها را با استفاده از نمودار Gantt بدست بیاوریم.
تکمیل جدول و استخراج اطلاعات
الان میتوانیم از روی جدول اطلاعات بیشتری از قبیل «زمان مورد نیاز برای تکمیل فعالیت» (Turn Around Time | TAT) و «زمان انتظار» (Waiting Time | WT) را بدست بیاوریم.
- زمان مورد نیاز برای تکمیل فعالیت یا TAT برابر است با زمان تکمیل عملیات منهای زمان رسیدن پردازش.
- زمان انتظار یا WT برابر است با زمان مورد نیاز برای تکمیل فعالیت منهای زمان مورد نیاز برای انجام کار.
بنابراین، جدول نهایی به شکل زیر خواهد بود.
Arrival Time - Burst Time - پردازش | Completion Time - Turn Around Time - Waiting Time | نسبت پاسخ |
P1 - 0 - 2 | 0 - 2 - 2 | 0 = 0 - 0 |
P2 - 2 - 6 | 0 - 6 - 8 | 0 = 2 - 2 |
P3 - 4 - 7 | 7 - 14 - 18 | 7 = 4 - 11 |
P4 - 5 - 3 | 3 - 6 - 11 | 3 = 5 - 8 |
P5 - 7 - 5 | 11 - 16 - 23 | 11 = 7 - 18 |
همچنین با تولید جدول بالا میتوان اطلاعات زیر را نیز از جدول استخراج کرد.
- زمان کل تکمیل فعالیت برابر است با ۴۴، بنابراین میانگین زمان مورد نیاز برای تکمیل فعالیت به ازای هر پردازش برابر با ۸٫۸ است.
- مجموع زمان انتظار برابر است با ۲۱، بنابراین میانگین زمان انتظار برابر با ۴٫۲ است.
- مجموع زمان پاسخ برابر است با ۲۱، بنابراین میانگین زمان پاسخ به ازای هر پردازش برابر با ۴٫۲ است.
نکته جالب توجه این است که میزان مجموع کل و میانگین زمان پاسخ به ترتیب با میزان مجموع کل و میانگین زمان انتظار برابر هستند.
مراحل پیاده سازی الگوریتم HRRN
الگوریتم، شالوده و بنیان اصلی حل یک مساله است. طراحی یک الگوریتم مناسب برای حل مسائل، نقش بسزایی در نوشتن کد برنامهنویسی آن دارد. اگر افراد درک درستی از مراحل حل مساله به زبان عامیانه داشته باشند، یعنی بتوانند مراحل حل مساله، شامل اجزای یک مساله، ارتباط بین این اجزا، نحوه انجام محاسبات برای رسیدن به پاسخ منطقی و ایجاد خروجی مورد انتظار را یاد بگیرند، آنگاه به راحتی میتوانند برای مساله خود مستندات و نیازمندیهای لازم را بنویسند و آن را به کد برنامهنویسی تبدیل کنند. به همین منظور فرادرس فیلم آموزش مبانی برنامه نویسی درباره الگوریتم و فلوچارت با رویکرد حل مساله را تولید و منتشر کرده است. برای کمک به مخاطبان مجله لینک مربوط به این فیلم را در پایین نیز قرار دادهایم.
در ادامه این بخش به دنبال پیادهسازی این الگوریتم در زبانهای برنامه نویسی گوناگون هستیم. اما در ابتدا روند کاری الگوریتم را به صورت گام به گام بیان میکنیم.
- تعداد کل پردازشها، زمان ورود هر پردازش و زمان مورد نیاز برای انجام کار آن پردازش را وارد کنید.
- با توجه به زمان ورود پردازشها چینش همه آنها را مرتب کنید.
- در زمانهای داده شده، نسبتهای پاسخ را برای پردازشهای در دسترس محاسبه کرده و پردازش مناسب را برای تکمیل عملیات زمانبندی انتخاب کنید.
- میزان زمان مورد نیاز برای تکمیل فعالیت را از طریق کم کردن زمان ورود از زمان تکمیل عملیات محاسبه کنید. (زمان مورد نیاز برای تکمیل فعالیت = زمان ورود - زمان تکمیل عملیات)
- میزان زمان انتظار را با کم کردن زمان مورد نیاز برای انجام کار از زمان مورد نیاز برای تکمیل فعالیت محاسبه کنید. (زمان انتظار = زمان مورد نیاز برای انجام کار - زمان مورد نیاز برای تکمیل فعالیت)
- اگر زمان مورد نیاز برای تکمیل فعالیت را تقسیم بر زمان مورد نیاز برای انجام کار کنیم، حالت نرمال شده زمان مورد نیاز برای تکمیل فعالیت بدست میآید.
- به ازای همه پردازشها زمانهای انتظار و تکمیل فعالیت را با یکدیگر جمع ببندید، سپس تقسیم بر تعداد کل پردازشها بکنید. با این کار میانگین زمانهای انتظار و تکمیل فعالیت بدست میآیند.
در ادامه این بخش تمام مراحل بالا را برای پیادهسازی الگوریتم HRRN با کمک شش زبان برنامهنویسی مختلف کدنویسی کردهایم.
پیاده سازی الگوریتم HRRN با زبان ++C
در این قسمت از مطلب، الگوریتم HRRN یا بالاترین نسبت پاسخ را با استفاده زبان برنامه نویسی ++C کدنویسی کردهایم.
این پیادهسازی از روی روند کاری بیان شده در ابتدای بخش، انجام شده است.
1// C++ program for Highest Response Ratio Next (HRRN)
2// Scheduling
3#include <bits/stdc++.h>
4using namespace std;
5// Defining process details
6struct process {
7 char name;
8 int at, bt, ct, wt, tt;
9 int completed;
10 float ntt;
11} p[10];
12
13int n;
14
15// Sorting Processes by Arrival Time
16void sortByArrival()
17{
18 struct process temp;
19 int i, j;
20
21 // Selection Sort applied
22 for (i = 0; i < n - 1; i++) {
23 for (j = i + 1; j < n; j++) {
24
25 // Check for lesser arrival time
26 if (p[i].at > p[j].at) {
27
28 // Swap earlier process to front
29 temp = p[i];
30 p[i] = p[j];
31 p[j] = temp;
32 }
33 }
34 }
35}
36
37int main()
38{
39 int i, j, sum_bt = 0;
40 char c;
41 float t, avgwt = 0, avgtt = 0;
42 n = 5;
43
44 // predefined arrival times
45 int arriv[] = { 0, 2, 4, 6, 8 };
46
47 // predefined burst times
48 int burst[] = { 3, 6, 4, 5, 2 };
49
50 // Initializing the structure variables
51 for (i = 0, c = 'A'; i < n; i++, c++) {
52 p[i].name = c;
53 p[i].at = arriv[i];
54 p[i].bt = burst[i];
55
56 // Variable for Completion status
57 // Pending = 0
58 // Completed = 1
59 p[i].completed = 0;
60
61 // Variable for sum of all Burst Times
62 sum_bt += p[i].bt;
63 }
64
65 // Sorting the structure by arrival times
66 sortByArrival();
67 cout << "PN\tAT\tBT\tWT\tTAT\tNTT";
68 for (t = p[0].at; t < sum_bt;) {
69
70 // Set lower limit to response ratio
71 float hrr = -9999;
72
73 // Response Ratio Variable
74 float temp;
75
76 // Variable to store next process selected
77 int loc;
78 for (i = 0; i < n; i++) {
79
80 // Checking if process has arrived and is
81 // Incomplete
82 if (p[i].at <= t && p[i].completed != 1) {
83
84 // Calculating Response Ratio
85 temp = (p[i].bt + (t - p[i].at)) / p[i].bt;
86
87 // Checking for Highest Response Ratio
88 if (hrr < temp) {
89
90 // Storing Response Ratio
91 hrr = temp;
92
93 // Storing Location
94 loc = i;
95 }
96 }
97 }
98
99 // Updating time value
100 t += p[loc].bt;
101
102 // Calculation of waiting time
103 p[loc].wt = t - p[loc].at - p[loc].bt;
104
105 // Calculation of Turn Around Time
106 p[loc].tt = t - p[loc].at;
107
108 // Sum Turn Around Time for average
109 avgtt += p[loc].tt;
110
111 // Calculation of Normalized Turn Around Time
112 p[loc].ntt = ((float)p[loc].tt / p[loc].bt);
113
114 // Updating Completion Status
115 p[loc].completed = 1;
116
117 // Sum Waiting Time for average
118 avgwt += p[loc].wt;
119 cout << "\n" << p[loc].name << "\t" << p[loc].at;
120 cout << "\t" << p[loc].bt << "\t" << p[loc].wt;
121 cout << "\t" << p[loc].tt << "\t" << p[loc].ntt;
122 }
123 cout << "\nAverage waiting time: " << avgwt / n << endl;
124 cout << "Average Turn Around time:" << avgtt / n;
125}
پیاده سازی الگوریتم HRRN با زبان C
در این قسمت از مطلب، الگوریتم HRRN یا بالاترین نسبت پاسخ را با استفاده زبان برنامه نویسی C کدنویسی کردهایم.
این پیادهسازی از روی روند کاری بیان شده در ابتدای بخش، انجام شده است.
1// C program for Highest Response Ratio Next (HRRN) Scheduling
2#include <stdio.h>
3
4// Defining process details
5struct process {
6 char name;
7 int at, bt, ct, wt, tt;
8 int completed;
9 float ntt;
10} p[10];
11
12int n;
13
14// Sorting Processes by Arrival Time
15void sortByArrival()
16{
17 struct process temp;
18 int i, j;
19
20 // Selection Sort applied
21 for (i = 0; i < n - 1; i++) {
22 for (j = i + 1; j < n; j++) {
23
24 // Check for lesser arrival time
25 if (p[i].at > p[j].at) {
26
27 // Swap earlier process to front
28 temp = p[i];
29 p[i] = p[j];
30 p[j] = temp;
31 }
32 }
33 }
34}
35
36void main()
37{
38 int i, j, t, sum_bt = 0;
39 char c;
40 float avgwt = 0, avgtt = 0;
41 n = 5;
42
43 // predefined arrival times
44 int arriv[] = { 0, 2, 4, 6, 8 };
45
46 // predefined burst times
47 int burst[] = { 3, 6, 4, 5, 2 };
48
49 // Initializing the structure variables
50 for (i = 0, c = 'A'; i < n; i++, c++) {
51 p[i].name = c;
52 p[i].at = arriv[i];
53 p[i].bt = burst[i];
54
55 // Variable for Completion status
56 // Pending = 0
57 // Completed = 1
58 p[i].completed = 0;
59
60 // Variable for sum of all Burst Times
61 sum_bt += p[i].bt;
62 }
63
64 // Sorting the structure by arrival times
65 sortByArrival();
66 printf("\nName\tArrival Time\tBurst Time\tWaiting Time");
67 printf("\tTurnAround Time\t Normalized TT");
68 for (t = p[0].at; t < sum_bt;) {
69
70 // Set lower limit to response ratio
71 float hrr = -9999;
72
73 // Response Ratio Variable
74 float temp;
75
76 // Variable to store next process selected
77 int loc;
78 for (i = 0; i < n; i++) {
79
80 // Checking if process has arrived and is Incomplete
81 if (p[i].at <= t && p[i].completed != 1) {
82
83 // Calculating Response Ratio
84 temp = (p[i].bt + (t - p[i].at)) / p[i].bt;
85
86 // Checking for Highest Response Ratio
87 if (hrr < temp) {
88
89 // Storing Response Ratio
90 hrr = temp;
91
92 // Storing Location
93 loc = i;
94 }
95 }
96 }
97
98 // Updating time value
99 t += p[loc].bt;
100
101 // Calculation of waiting time
102 p[loc].wt = t - p[loc].at - p[loc].bt;
103
104 // Calculation of Turn Around Time
105 p[loc].tt = t - p[loc].at;
106
107 // Sum Turn Around Time for average
108 avgtt += p[loc].tt;
109
110 // Calculation of Normalized Turn Around Time
111 p[loc].ntt = ((float)p[loc].tt / p[loc].bt);
112
113 // Updating Completion Status
114 p[loc].completed = 1;
115
116 // Sum Waiting Time for average
117 avgwt += p[loc].wt;
118 printf("\n%c\t\t%d\t\t", p[loc].name, p[loc].at);
119 printf("%d\t\t%d\t\t", p[loc].bt, p[loc].wt);
120 printf("%d\t\t%f", p[loc].tt, p[loc].ntt);
121 }
122 printf("\nAverage waiting time:%f\n", avgwt / n);
123 printf("Average Turn Around time:%f\n", avgtt / n);
124}
پیاده سازی الگوریتم HRRN با زبان جاوا
در این قسمت از مطلب، الگوریتم HRRN یا بالاترین نسبت پاسخ را با استفاده زبان برنامه نویسی جاوا کدنویسی کردهایم. این زبان برنامهنویسی در 23 مه 1995، برابر با ۲ خرداد ۱۳۷۴، توسط جیمز گاسلینگ (James Gosling) طراحی شده و به گواهی سایت معتبر Tiobe از سال 2001 همواره به عنوان اولین یا دومین زبان برنامهنویسی دنیا مطرح بوده است. برای آشنای کامل با این زبان، پیشنهاد میکنیم که مطلب زبان برنامه نویسی جاوا (Java) از صفر تا صد را از مجله فرادرس مطالعه کنید.
این پیادهسازی از روی روند کاری بیان شده در ابتدای بخش، انجام شده است.
1// Java equivalent
2import java.util.Arrays;
3
4// Defining process details
5class Process {
6 char name;
7 int at, bt, ct, wt, tt;
8 int completed;
9 float ntt;
10}
11
12public class HRRN {
13
14 // Sorting Processes by Arrival Time
15 static void sortByArrival(Process p[], int n)
16 {
17 Process temp;
18 int i, j;
19
20 // Selection Sort applied
21 for (i = 0; i < n - 1; i++) {
22 for (j = i + 1; j < n; j++) {
23
24 // Check for lesser arrival time
25 if (p[i].at > p[j].at) {
26
27 // Swap earlier process to front
28 temp = p[i];
29 p[i] = p[j];
30 p[j] = temp;
31 }
32 }
33 }
34 }
35
36 public static void main(String[] args)
37 {
38 int i, j, sum_bt = 0;
39 char c;
40 float t, avgwt = 0, avgtt = 0;
41 int n = 5;
42
43 // predefined arrival times
44 int arriv[] = { 0, 2, 4, 6, 8 };
45
46 // predefined burst times
47 int burst[] = { 3, 6, 4, 5, 2 };
48
49 Process[] p = new Process[n];
50
51 // Initializing the structure variables
52 for (i = 0, c = 'A'; i < n; i++, c++) {
53 p[i] = new Process();
54 p[i].name = c;
55 p[i].at = arriv[i];
56 p[i].bt = burst[i];
57
58 // Variable for Completion status
59 // Pending = 0
60 // Completed = 1
61 p[i].completed = 0;
62
63 // Variable for sum of all Burst Times
64 sum_bt += p[i].bt;
65 }
66
67 // Sorting the structure by arrival times
68 sortByArrival(p, n);
69 System.out.println("PN\tAT\tBT\tWT\tTAT\tNTT");
70 for (t = p[0].at; t < sum_bt;) {
71
72 // Set lower limit to response ratio
73 float hrr = -9999;
74
75 // Response Ratio Variable
76 float temp;
77
78 // Variable to store next process selected
79 int loc = -1;
80 for (i = 0; i < n; i++) {
81
82 // Checking if process has arrived and is
83 // Incomplete
84 if (p[i].at <= t && p[i].completed != 1) {
85
86 // Calculating Response Ratio
87 temp = (p[i].bt + (t - p[i].at)) / p[i].bt;
88
89 // Checking for Highest Response Ratio
90 if (hrr < temp) {
91
92 // Storing Response Ratio
93 hrr = temp;
94
95 // Storing Location
96 loc = i;
97 }
98 }
99 }
100
101 // Updating time value
102 t += p[loc].bt;
103
104 // Calculation of waiting time
105 p[loc].wt = (int)(t - p[loc].at - p[loc].bt);
106
107 // Calculation of Turn Around Time
108 p[loc].tt = (int)(t - p[loc].at);
109
110 // Sum Turn Around Time for average
111 avgtt += p[loc].tt;
112
113 // Calculation of Normalized Turn Around Time
114 p[loc].ntt = ((float)p[loc].tt / p[loc].bt);
115
116 // Updating Completion Status
117 p[loc].completed = 1;
118
119 // Sum Waiting Time for average
120 avgwt += p[loc].wt;
121 System.out.println(p[loc].name + "\t" + p[loc].at + "\t" + p[loc].bt
122 + "\t" + p[loc].wt + "\t" + p[loc].tt
123 + "\t" + p[loc].ntt);
124 }
125 System.out.println("Average waiting time: " + (avgwt / n));
126 System.out.println("Average Turn Around time:" + (avgtt / n));
127 }
128}
پیاده سازی الگوریتم HRRN با زبان پایتون۳
در این قسمت از مطلب، الگوریتم HRRN یا بالاترین نسبت پاسخ را با استفاده زبان برنامه نویسی پایتون کدنویسی کردهایم.
این پیادهسازی از روی روند کاری بیان شده در ابتدای بخش، انجام شده است.
1# Python3 program for Highest Response Ratio
2# Next (HRRN) Scheduling
3
4# Function to sort process by arrival time
5def sortByArrival(at, n):
6
7 # Selection Sort applied
8 for i in range(0, n - 1):
9 for j in range(i + 1, n):
10
11 # Check for lesser arrival time
12 if at[i] > at[j]:
13
14 # Swap earlier process to front
15 at[i], at[j] = at[j], at[i]
16
17# Driver code
18if __name__ == '__main__':
19
20 sum_bt = 0
21 avgwt = 0
22 avgTT = 0
23 n = 5
24
25 completed =[0] * n
26 waiting_time = [0] * n
27 turnaround_time = [0] * n
28 normalised_TT = [0] * n
29
30 # Predefined arrival times
31 arrival_time = [ 0, 2, 4, 6, 8 ]
32
33 # Predefined burst times
34 burst_time = [ 3, 6, 4, 5, 2 ]
35 process = []
36
37 # Initializing the structure variables
38 for i in range(0, n):
39 process.append(chr(65 + i))
40 sum_bt += burst_time[i]
41
42 # Sorting the structure by arrival times
43 sortByArrival(arrival_time, n)
44 print("Name", "Arrival time",
45 "Burst time", "Waiting Time",
46 "Turnaround ", "Normalized TT")
47 t = arrival_time[0]
48
49 while(t < sum_bt):
50
51 # Set lower limit to response ratio
52 hrr = -9999
53 temp, loc = 0, 0
54
55 for i in range(0, n):
56
57 # Checking if process has arrived
58 # and is Incomplete
59 if arrival_time[i] <= t and completed[i] != 1:
60
61 # Calculating Response Ratio
62 temp = ((burst_time[i] +
63 (t - arrival_time[i])) /
64 burst_time[i])
65
66 # Checking for Highest Response Ratio
67 if hrr < temp:
68
69 # Storing Response Ratio
70 hrr = temp
71
72 # Storing Location
73 loc = i
74
75 # Updating time value
76 t += burst_time[loc]
77
78 # Calculation of waiting time
79 waiting_time[loc] = (t - arrival_time[loc] -
80 burst_time[loc])
81
82 # Calculation of Turn Around Time
83 turnaround_time[loc] = t - arrival_time[loc]
84
85 # Sum Turn Around Time for average
86 avgTT += turnaround_time[loc]
87
88 # Calculation of Normalized Turn Around Time
89 normalised_TT = float(turnaround_time[loc] /
90 burst_time[loc])
91
92 # Updating Completion Status
93 completed[loc] = 1
94
95 # Sum Waiting Time for average
96 avgwt += waiting_time[loc]
97
98 print(process[loc], "\t\t", arrival_time[loc],
99 "\t\t", burst_time[loc], "\t\t",
100 waiting_time[loc], "\t\t",
101 turnaround_time[loc], "\t\t",
102 "{0:.6f}".format(normalised_TT))
103
104 print("Average waiting time: {0:.6f}".format(avgwt / n))
105 print("Average Turn Around time: {0:.6f}".format(avgTT / n))
پیاده سازی الگوریتم HRRN با زبان #C
در این قسمت از مطلب، الگوریتم HRRN یا بالاترین نسبت پاسخ را با استفاده زبان برنامه نویسی #C کدنویسی کردهایم.
این پیادهسازی از روی روند کاری بیان شده در ابتدای بخش، انجام شده است.
1using System;
2using System.Collections;
3using System.Collections.Generic;
4using System.Linq;
5
6// C# equivalent
7
8// Defining process details
9class Process {
10 public char name;
11 public int at, bt, ct, wt, tt;
12 public int completed;
13 public float ntt;
14}
15
16class HelloWorld {
17
18 // Sorting Processes by Arrival Time
19 public static void sortByArrival(Process[] p, int n)
20 {
21 Process temp;
22 int i, j;
23
24 // Selection Sort applied
25 for (i = 0; i < n - 1; i++) {
26 for (j = i + 1; j < n; j++) {
27
28 // Check for lesser arrival time
29 if (p[i].at > p[j].at) {
30
31 // Swap earlier process to front
32 temp = p[i];
33 p[i] = p[j];
34 p[j] = temp;
35 }
36 }
37 }
38 }
39
40 static void Main() {
41 int i, j, sum_bt = 0;
42 char c;
43 float t, avgwt = 0, avgtt = 0;
44 int n = 5;
45
46 // predefined arrival times
47 int[] arriv = { 0, 2, 4, 6, 8 };
48
49 // predefined burst times
50 int[] burst = { 3, 6, 4, 5, 2 };
51
52 Process[] p = new Process[n];
53
54 // Initializing the structure variables
55 for (i = 0, c = 'A'; i < n; i++, c++) {
56 p[i] = new Process();
57 p[i].name = c;
58 p[i].at = arriv[i];
59 p[i].bt = burst[i];
60
61 // Variable for Completion status
62 // Pending = 0
63 // Completed = 1
64 p[i].completed = 0;
65
66 // Variable for sum of all Burst Times
67 sum_bt += p[i].bt;
68 }
69
70 // Sorting the structure by arrival times
71 sortByArrival(p, n);
72 Console.WriteLine("PN\tAT\tBT\tWT\tTAT\tNTT");
73 for (t = p[0].at; t < sum_bt;) {
74
75 // Set lower limit to response ratio
76 float hrr = -9999;
77
78 // Response Ratio Variable
79 float temp;
80
81 // Variable to store next process selected
82 int loc = -1;
83 for (i = 0; i < n; i++) {
84
85 // Checking if process has arrived and is
86 // Incomplete
87 if (p[i].at <= t && p[i].completed != 1) {
88
89 // Calculating Response Ratio
90 temp = (p[i].bt + (t - p[i].at)) / p[i].bt;
91
92 // Checking for Highest Response Ratio
93 if (hrr < temp) {
94
95 // Storing Response Ratio
96 hrr = temp;
97
98 // Storing Location
99 loc = i;
100 }
101 }
102 }
103
104 // Updating time value
105 t += p[loc].bt;
106
107 // Calculation of waiting time
108 p[loc].wt = (int)(t - p[loc].at - p[loc].bt);
109
110 // Calculation of Turn Around Time
111 p[loc].tt = (int)(t - p[loc].at);
112
113 // Sum Turn Around Time for average
114 avgtt += p[loc].tt;
115
116 // Calculation of Normalized Turn Around Time
117 p[loc].ntt = ((float)p[loc].tt / p[loc].bt);
118
119 // Updating Completion Status
120 p[loc].completed = 1;
121
122 // Sum Waiting Time for average
123 avgwt += p[loc].wt;
124 Console.WriteLine(p[loc].name + "\t" + p[loc].at + "\t" + p[loc].bt
125 + "\t" + p[loc].wt + "\t" + p[loc].tt
126 + "\t" + p[loc].ntt);
127 }
128 Console.WriteLine("Average waiting time: " + (avgwt / n));
129 Console.WriteLine("Average Turn Around time:" + (avgtt / n));
130 }
131}
پیاده سازی الگوریتم HRRN با زبان جاوا اسکریپت
در این قسمت از مطلب، الگوریتم HRRN یا بالاترین نسبت پاسخ را با استفاده زبان برنامه نویسی جاوا اسکریپت کدنویسی کردهایم.
این پیادهسازی از روی روند کاری بیان شده در ابتدای بخش، انجام شده است.
1// javascript program for Highest Response Ratio Next (HRRN)
2// Scheduling
3
4// Defining process details
5class process {
6
7 constructor(){
8 this.name = '#';
9 this.at = 0;
10 this.bt = 0;
11 this.ct = 0;
12 this.wt = 0;
13 this.tt = 0;
14 this.completed= 0;
15 this.ntt = 0;
16 }
17
18}
19let p = new Array(10);
20for(let i = 0; i < 10; i++){
21 p[i] = new process();
22}
23
24let n;
25
26// Sorting Processes by Arrival Time
27function sortByArrival()
28{
29 let temp;
30 let i, j;
31
32 // Selection Sort applied
33 for (i = 0; i < n - 1; i++) {
34 for (j = i + 1; j < n; j++) {
35
36 // Check for lesser arrival time
37 if (p[i].at > p[j].at) {
38
39 // Swap earlier process to front
40 temp = p[i];
41 p[i] = p[j];
42 p[j] = temp;
43 }
44 }
45 }
46}
47
48
49let i, j, sum_bt = 0;
50let c;
51let t, avgwt = 0, avgtt = 0;
52n = 5;
53
54// predefined arrival times
55let arriv = [0, 2, 4, 6, 8];
56
57// predefined burst times
58let burst = [3, 6, 4, 5, 2];
59
60// Initializing the structure variables
61for (i = 0, c = 'A'; i < n; i++) {
62 p[i].name = c;
63 p[i].at = arriv[i];
64 p[i].bt = burst[i];
65
66 // Variable for Completion status
67 // Pending = 0
68 // Completed = 1
69 p[i].completed = 0;
70
71 // Variable for sum of all Burst Times
72 sum_bt += p[i].bt;
73 c = String.fromCharCode(c.charCodeAt(0) + 1);
74}
75
76// Sorting the structure by arrival times
77sortByArrival();
78console.log("PN\tAT\tBT\tWT\tTAT\tNTT");
79
80for (t = p[0].at; t < sum_bt;) {
81
82 // Set lower limit to response ratio
83 let hrr = -9999;
84
85 // Response Ratio Variable
86 let temp;
87
88 // Variable to store next process selected
89 let loc;
90 for (i = 0; i < n; i++) {
91
92 // Checking if process has arrived and is
93 // Incomplete
94 if (p[i].at <= t && p[i].completed != 1) {
95
96 // Calculating Response Ratio
97 temp = (p[i].bt + (t - p[i].at)) / p[i].bt;
98
99 // Checking for Highest Response Ratio
100 if (hrr < temp) {
101
102 // Storing Response Ratio
103 hrr = temp;
104
105 // Storing Location
106 loc = i;
107 }
108 }
109 }
110
111 // Updating time value
112 t += p[loc].bt;
113
114 // Calculation of waiting time
115 p[loc].wt = t - p[loc].at - p[loc].bt;
116
117 // Calculation of Turn Around Time
118 p[loc].tt = t - p[loc].at;
119
120 // Sum Turn Around Time for average
121 avgtt += p[loc].tt;
122
123 // Calculation of Normalized Turn Around Time
124 p[loc].ntt = (p[loc].tt / p[loc].bt);
125
126 // Updating Completion Status
127 p[loc].completed = 1;
128
129 // Sum Waiting Time for average
130 avgwt += p[loc].wt;
131 console.log(p[loc].name + "\t" + p[loc].at + "\t" + p[loc].bt + "\t" + p[loc].wt + "\t" + p[loc].tt + "\t" + p[loc].ntt);
132}
133console.log("\nAverage waiting time: " + avgwt / n);
134console.log("Average Turn Around time:" + avgtt / n);
خروجی حاصل از اجرای کدهای بالا به صورت زیر به کاربر نمایش داده میشود.
Name Arrival time Burst time Waiting Time Turnaround Normalized TT A 0 3 0 3 1.000000 B 2 6 1 7 1.166667 C 4 4 5 9 2.250000 E 8 2 5 7 3.500000 D 6 5 9 14 2.800000 Average waiting time: 4.000000 Average Turn Around time: 8.000000
آموزش برنامه نویسی با استفاده از فیلم های پروژه محور
برای اینکه بتوانیم به بهترین شکل ممکن با سختافزار ارتباط برقرار کرده و از این نوع الگوریتمها استفاده کنیم، بسیار مهم است که در کار با زبانهای برنامهنویسی هم خبره باشیم. آموزش برنامهنویسی شامل مراحل و سطوح علمی مختلف میشود. این مسیر جالب از آموزش مطالب پایه و مقدماتی برای آشنایی با سینتکس زبان و مفاهیمی مانند حلقهها، عبارات شرطی و غیره شروع شده و تا مراحل پیشرفتهای مانند شیء گرایی ادامه پیدا میکند. اما یکی از بهترین روشها در آموزش برنامهنویس به منظور ورود به دنیای واقعی و بازار کار، معمولا اجرای تمرینات پروژه محور است.
![مجموعه آموزش پروژه محور برنامه نویسی – مقدماتی تا پیشرفته](https://blog.faradars.org/wp-content/uploads/2024/08/Project-based-programming-tutorials-series.png)
در اجرای بعضی از تمرینات پروژه محور، حتی لازم میشود که از چند زبان برنامهنویسی و تکنولوژی مختلف در کنار هم استفاده کنیم. فرادرس به عنوان تولید کننده محتوای آموزشی در این زمینه هم فیلمهای بسیار مفیدی را تولید کرده است. در این بخش چند مورد از فیلمهای آموزشی پروژه محور برنامهنویسی توسط زبانهای مختلف را که در فرادرس آماده شده معرفی میکنیم. در فرادرس برای تهیه این فیلمهای آموزشی حداکثر حساسیت بهکار رفته تا مفیدترین گزینههای ممکن در دسترس شما قرار بگیرد.
- فیلم آموزش مقدماتی ساخت ربات تلگرام با پایتون از فرادرس
- فیلم آموزش پروژه محور برنامه نویسی تحت شبکه با C# در فرادرس
- فیلم آموزش رایگان پروژه محور JavaFX همراه با ساخت بازی Snake در فرادرس
- فیلم آموزش پروژه محور ساخت ربات اینستاگرام با سی شارپ و پایتون فرادرس
- فیلم آموزش پروژه محور ساخت بازی با Vanilla JavaScript فرادرس
جمع بندی
الگوریتم HRRN برای مدیریت زمانبندی اجرای پردازشها توسط CPU طراحی شده است. بر اساس نمرهای که به بالاترین نسبت پاسخ پردازشها اختصاص پیدا میکند، این الگوریتم، جدول زمانبندی استفاده از CPU را میچیند. HRRN از نوع الگوریتمهای «انحصاری» (Non-Preemptive) است، یعنی اینکه تا زمان به پایان رسیدن فرایند اجرای هر پردازش در CPU، بقیه پردازشها با هر اولویتی باید صبر کنند. استفاده از این الگوریتم باعث ارتقای کارایی سیستم عامل میشود.
در این مطلب از مجله فرادرس با الگوریتم HRRN آشنا شدیم. این الگوریتم برای جلوگیری از روی دادن مشکل گرسنگی توسعه یافته است. در ابتدای مطلب با الگوریتم آشنا شده و سپس روند کاری آن را با کمک مثال کوچکی، شرح دادیم.