الگوریتم زمان‌بندی 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 در جاوا به صورت زیر است:

public class RoundRobin {
	static void findWaitingTime
(int processes[], int n, int bt[], 
			int wt[], int quantum) {
		int rem_bt[] = new int[n];
		rem_bt = Arrays.copyOf(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];
		}
		System.out.println("Average waiting time = " + 
		(float) total_wt / (float) n);
		System.out.println("Average turn around time = " +
		(float) total_tat / (float) n);
	}
	public static void Display
(int n, int[] burst_time, int[] wt, int[] tat) {
		System.out.print("Processes " 
+ " Burst Time " + " Waiting Time "
		+ " Turn-Around Time " + "\n");
		for (int i = 0; i < n; i++) {
			System.out.println
(" " + (i + 1) + "\t\t" + burst_time[i] +
					"\t " + wt[i] + "\t\t " + tat[i]);
		}
	}
	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);
	}
}

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

• 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 اختصاص می‌یابد و برای انجام ادامه فرآیند وارد صف انتظار خواهد شد.
• به فرآیند بعدی درصف انتظار CPU اختصاص می‌یابد و مرحله بالا را طی می‌کند.
• وقتی تمام فرآیند‌ها به اتمام برسند الگوریتم پایان می‌یابد.

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