الگوریتم زمان‌بندی Round robin در سی شارپ

در این قسمت ما را با آموزش الگوریتم زمان‌بندی Round robin در سی شارپ همراهی کنید. الگوریتم‌های زمانبندی برای تخصیص CPU به یک فرآیند استفاده می‌شوند. در این جلسه به توضیح و پیاده‌سازی الگوریتم round robin خواهیم پرداخت. پیشنهاد می‌کنیم قبل از مطالعه این جلسه، آموزش‌های زیر را مطالعه کنید:

1. آشنایی با متد در سی شارپ
2. آشنایی با حلقه for در سی شارپ
3. آشنایی با آرایه در سی شارپ
4. آشنایی با حلقه While
5. الگوریتم زمان‌بندی FCFS در سی شارپ

الگوریتم زمان‌بندی Round Robin

Round Robin یکی از الگوریتم‌های زمان‌بندی در سیستم‌عامل است که در بسیاری از سیستم‌های کنونی از آن استفاده و پیاده‌سازی شده است. الگوریتم round robin برعکس FCFS به صورت preemptive می‌باشد.

در الگوریتم Round Robin تمامی فرآیند‌ها به صورت چرخشی، CPU به آن‌ها اختصاص می‌یابد. ویژگی‌های این الگوریتم به شرح زیر است:

• هر فرآیند به صورت مساوی زمانی که به آن quantum می‌گویند CPU اختصاص می‌یابد.
• Preemptive است.
• Starvation در آن رخ نمی‌دهد.
• در صورت اینکه زمان Quantom برای یک فرآیند کافی نبوده، فرآیند برای اختصاص دوباره CPU، وارد صف انتظار خواهد شد.

در این الگوریتم برای هر فرآیند پارامترهای زیر تعریف می‌شود:

• Completion Time : زمانی که یک فرآیند به اتمام می‌رسد.
• Arrival Time : زمانی که یک فرآیند وارد صف نوبت دهی CPU می‌شود.
• Burst Time : مدت زمان مورد نیاز یک فرآیند برای اجرا در CPU .
• Turn Around Time : اختلاف زمانی بین Completion Time و Arrival Time .
• Waiting Time : اختلاف زمانی بین Turn Around Time و Burst Time .

الگوریتم زمانبندی Round Robin در سی شارپ

برای پیاده سازی Round Robin ابتدا پارامتر Burst Time را باید به عنوان ورودی به برنامه بدهیم و در خروچی Completion Time و Turn Around Time و Waiting Time را چاپ می‌کنیم. برای سادگی کد ما فرض کرده‌ایم همه فرآیندها همزمان در زمان صفر وارد صف شده‌اند (Arrival Time برابر با صفر برای همه فرآیند‌ها). کد الگوریتم زمانبندی Round Robin در سی شارپ به صورت زیر است:

class MainClass
	{
		public static void Main (string[] args)
		{
			int[] processes = { 1, 2, 3 };
			int n = processes.Length;
			int[] wt = new int[n], tat = new int[n];
			int[] burst_time = { 10, 5, 8 };
			int quantum = 2;
			findWaitingTime(processes, n, burst_time, wt, quantum);
			findTurnAroundTime(processes, n, burst_time, wt, tat);
			Display(n, burst_time, wt, tat);
			findavgTime(processes, n, tat, wt);
			Console.WriteLine ("Press any key to Finish ...");
			Console.ReadKey ();
		}
		static void findWaitingTime(int[] processes, int n, int[] bt, int[] wt, int quantum) {
			int[] rem_bt = new int[n];
			Array.Copy(bt,rem_bt, n);
			int t = 0;
			int finished_process = 0;
			while (finished_process != n) {
				for (int i = 0; i < n; i++) {
					if (rem_bt[i] > 0) {
						if (rem_bt[i] > quantum) {
							t += quantum;
							rem_bt[i] -= quantum;
						}
						else {
							t = t + rem_bt[i];
							wt[i] = t - bt[i];
							rem_bt[i] = 0;
							finished_process++;
						}
					}
				}
			}
		}
		static void findTurnAroundTime(int[] processes, int n, int[] bt, int[] wt, int[] tat) {
			for (int i = 0; i < n; i++)
				tat[i] = bt[i] + wt[i];
		}
		static void findavgTime(int[] processes, int n, int[] tat, int[] wt) {
			int total_tat = 0;
			int total_wt = 0;
			for (int i = 0; i < n; i++) {
				total_wt = total_wt + wt[i];
				total_tat = total_tat + tat[i];
			}
			Console.WriteLine ("Average waiting time = " + (float) total_wt / (float) n);
			Console.WriteLine ("Average turn around time = " + (float) total_tat / (float) n);
		}
		public static void Display(int n, int[] burst_time, int[] wt, int[] tat) {
			Console.Write ("Processes " + " Burst Time " + " Waiting Time " + " Turn-Around Time " + "\n");
			for (int i = 0; i < n; i++) {
				Console.WriteLine (" " + (i + 1) + "\t\t" + burst_time[i] + "\t " + wt[i] + "\t\t " + tat[i]);
			}
		}
	}

متدهای مورد استفاده در کد بالا به صورت زیر می‌باشد:

• findWaitingTime: این متد جهت محاسبه Waiting Time هر فرآیند می‌باشد.
• findTurnAroundTime: برای محاسبه Turn Around Time فرآیندها از این متد استفاده می‌شود.
• Display: جهت چاپ فرآیندها در خروجی استفاده می‌شود.
• FindavgTime: نحوه کار این متد و دلیل پیاده سازی آن را به شما واگذار می‌کنیم….

متغیرهای مورد استفاده در کد فوق:

• Process: یک کد برای هر فرآیند در این آرایه ذخیره می‌گردد.
• N: تعداد فرآیندها
• Burst_Time یا bt: مدت زمان مورد نیاز فرآیند برای اجرا در CPU
• Wt: منظور همان Watining Time است.
• Tat: منظور همان Turn around time برای هر فرآیند است.
• Quantum: زمان تخصیص CPU به تمام فرآیند‌ها.
• rem_bt: زمان باقی‌مانده از Burst Time یک فرآیند.
• finished_process: تعداد فرآیند‌های پایان یافته.

نحوه کار کد الگوریتم زمان‌بندی round robin در سی شارپ

برای پیاده‌سازی همان‌طور که گفته شد ما arrival Time همه فرآیند‌ها را صفر در نظر گرفتیم. با توجه به صف انتظار به فرآیند‌ها CPU اختصاص می‌یابد. یک فرآیند که به آن CPU اختصاص می‌یابد مراحل زیر را طی می‌کند:

• زمان باقی‌مانده Burst Time فرآیند با quantum مقایسه می‌شود.
  • اگر(باقی‌مانده Burst Time) کمتر از quantum باشد زمان مورد نیاز به فرآیند اختصاص می‌یابد و فرآیند پایان می‌یابد.
  • اگر(باقی‌مانده Burst Time) بیشتر از quantum باشد به اندازه quantum به آن cpu اختصاص می‌یابد و برای انجام ادامه فرآیند وارد صف انتظار خواهد شد.
• فرآیند بعدی وارد صف می‌شود و مرحله بالا را طی می‌کند.
• وقتی تمام فرآیند‌ها به اتمام برسند الگوریتم پایان می‌یابد.

خروجی کد بالا به صورت زیر می‌باشد: