الگوریتم زمان‌بندی LJF در سی شارپ (Longest Job First)

تیر 7, 1399 سعید غریبی درج دیدگاه

این جلسه ما را با ادامه آموزش الگوریتم‌های زمان‌بندی همراهی کنید. در این قسمت به آموزش الگوریتم زمان‌بندی LJF در سی شارپ می‌پردازیم. ابتدا این الگوریتم را معرفی و سپس به پیاده‌سازی آن خواهیم پرداخت. پیشنهاد می‌کنیم قبل از مطالعه این جلسه، آموزش‌های زیر را مطالعه کنید:

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

Longest Job First یا به اختصار LJF یک الگوریتم زمان‌بندی در سیستم عامل است. در این الگوریتم، همه فرآیند‌ها بررسی و از بین فرایندهای منتظر در صف اجرا، فرایندی انتخاب می‌شود که به طولانی‌ترین زمان برای اجرا شدن(burst Time) نیاز داشته باشد. به این جا به چند ویژگی LJF اشاره می‌کنیم:

در این الگوریتم می‌تواند Starvation رخ دهد.
زمان اتمام فرآیندها نزدیک به یکدیگر است.
این روش مقدار Average time بالا است.

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

برای پیاده سازی الگوریتم زمان‌بندی LJF در سی شارپ مراحل زیر را انجام می‌دهیم:

فرآیند‌های خود را تعریف می‌کنیم.
بر اساس arrival Time ، فرآیند‌ها را وارد صف انتظار می‌کنیم.
فرآیند‌های درون صف انتظار را بر اساس Burst Time مرتب می‌کنیم(به صورت نزولی).
به طولانی‌ترین فرآیند CPU اختصاص می‌یابد.
مراحل 2 تا 5 را تا زمان اتمام فرآیند‌ها ادامه می‌دهیم.

کد الگوریتم LJF در سی شارپ به صورت زیر است:

class MainClass
	{
		public static void Main (string[] args)
		{
			ArrayList p = new ArrayList();
			p.Add(new MyProcess(1, 6, 1));
			p.Add(new MyProcess(2, 8, 1));
			p.Add(new MyProcess(3, 7, 2));
			p.Add(new MyProcess(4, 3, 3));

			LJF(p);
			CalWaitingTime(p);
			CalTurnAroundTime(p);
			display(p);


			Console.WriteLine("Press any key to finish program");
			Console.ReadKey ();
		}


		private static void CalTurnAroundTime(ArrayList p) {
			for (int i = 0; i < p.Count; i++) {
				MyProcess temp = (MyProcess)p[i];
				temp.tat = temp.waiting_time + temp.bt;
			}
		}

		public static void display(ArrayList p) {
<div style="clear:both; margin-top:0em; margin-bottom:1em;"><a href="http://codegate.ir/2020/06/01/%d8%b3%d8%a7%d8%ae%d8%aa-%d9%be%db%8c%da%a9%d8%b3%d9%84%e2%80%8c%d9%87%d8%a7%db%8c-%d8%aa%d8%b5%d8%a7%d8%af%d9%81%db%8c-%d8%af%d8%b1-%d8%b3%db%8c-%d8%b4%d8%a7%d8%b1%d9%be/" target="_blank" rel="nofollow" class="ub201e14536c052052e47bc1ec24101f5"><!-- INLINE RELATED POSTS 1/3 //--><style> .ub201e14536c052052e47bc1ec24101f5 { padding:0px; margin: 0; padding-top:1em!important; padding-bottom:1em!important; width:100%; display: block; font-weight:bold; background-color:#e6e6e6; border:0!important; border-left:4px solid #E67E22!important; text-decoration:none; } .ub201e14536c052052e47bc1ec24101f5:active, .ub201e14536c052052e47bc1ec24101f5:hover { opacity: 1; transition: opacity 250ms; webkit-transition: opacity 250ms; text-decoration:none; } .ub201e14536c052052e47bc1ec24101f5 { transition: background-color 250ms; webkit-transition: background-color 250ms; opacity: 1; transition: opacity 250ms; webkit-transition: opacity 250ms; } .ub201e14536c052052e47bc1ec24101f5 .ctaText { font-weight:bold; color:#2980B9; text-decoration:none; font-size: 16px; } .ub201e14536c052052e47bc1ec24101f5 .postTitle { color:inherit; text-decoration: underline!important; font-size: 16px; } .ub201e14536c052052e47bc1ec24101f5:hover .postTitle { text-decoration: underline!important; } </style><div style="padding-left:1em; padding-right:1em;"><span class="ctaText">بیشتر بخوانید:</span>  <span class="postTitle">ساخت پیکسل‌های تصادفی در سی شارپ (Random Pixel)</span></div></a></div>
			Console.WriteLine("Processes " + " Burst time " + " Waiting time " + " Turn around time" + " Completion Time "
				+ " Arrival Time");

			for (int i = 0; i < p.Count; i++) {
				MyProcess temp = (MyProcess)p [i];
				Console.WriteLine(" " + temp.pid + "\t\t" + temp.bt + "\t\t " + temp.waiting_time + "\t\t "
					+ temp.tat + "\t\t" + temp.completion_time + "\t\t" +temp.art);
			}
		}

		public static void LJF(ArrayList AllProcess) {
			ArrayList waitingProcess = new ArrayList();
			int time = 0;
			int complete_process = 0;

			while (AllProcess.Count != complete_process) {
				CheckArrivalTime(AllProcess, waitingProcess, time);
				if (waitingProcess.Count <= 0) {
					time++;
					continue;
				}
				Sort(waitingProcess);

				MyProcess LongestProcess = (MyProcess)waitingProcess[0];
				time += LongestProcess.bt;
				LongestProcess.completion_time = time;
				LongestProcess.is_finished = true;
				waitingProcess.RemoveAt(0);
				complete_process++;

			}

		}



		public static void CalWaitingTime(ArrayList p) {
			for (int i = 0; i < p.Count; i++) {
				MyProcess p1 = (MyProcess)p[i];
				p1.waiting_time = p1.completion_time - p1.bt - p1.art;
				if (p1.waiting_time < 0) {
					p1.waiting_time = 0;
				}

			}
		}

		public static void Sort(ArrayList waitingProcess) {
			for (int i = 0; i < waitingProcess.Count; i++) {
				for (int j = 0; j < waitingProcess.Count - 1; j++) {
					MyProcess p1 = (MyProcess) waitingProcess[j];
					MyProcess p2 =  (MyProcess) waitingProcess[j + 1];
					if (p2.bt > p1.bt) {
						waitingProcess [j] = waitingProcess [j + 1];
						waitingProcess [j + 1] = p1;
					}
				}
			}

		}

		public static void CheckArrivalTime(ArrayList Process, ArrayList waitingProcess, int time) {
			for (int i = 0; i < Process.Count; i++) {
				MyProcess p =  (MyProcess) Process[i];
				if (p.art <= time && !p.addTowaiting) {
					p.addTowaiting = true;
					waitingProcess.Add(p);
				}
			}

		}


	}

	public class MyProcess {
		public int pid; // Process ID
		public int bt; // Burst Time
		public int art; // Arrival Time
		public int completion_time;
		public int waiting_time;
		public int tat;//turn around time
		public bool is_finished = false;
		public bool addTowaiting = false;

		public MyProcess(int pid, int bt, int art) {
			this.pid = pid;
			this.bt = bt;
			this.art = art;
		}
	}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

class MainClass

{

public static void Main (string[] args)

{

ArrayList p = new ArrayList();

p.Add(new MyProcess(1, 6, 1));

p.Add(new MyProcess(2, 8, 1));

p.Add(new MyProcess(3, 7, 2));

p.Add(new MyProcess(4, 3, 3));

LJF(p);

CalWaitingTime(p);

CalTurnAroundTime(p);

display(p);

Console.WriteLine("Press any key to finish program");

Console.ReadKey ();

}

private static void CalTurnAroundTime(ArrayList p) {

for (int i = ; i < p.Count; i++) {

MyProcess temp = (MyProcess)p[i];

temp.tat = temp.waiting_time + temp.bt;

}

public static void display(ArrayList p) {

Console.WriteLine("Processes " + " Burst time " + " Waiting time " + " Turn around time" + " Completion Time "

+ " Arrival Time");

for (int i = ; i < p.Count; i++) {

MyProcess temp = (MyProcess)p [i];

Console.WriteLine(" " + temp.pid + "\t\t" + temp.bt + "\t\t " + temp.waiting_time + "\t\t "

+ temp.tat + "\t\t" + temp.completion_time + "\t\t" +temp.art);

}

public static void LJF(ArrayList AllProcess) {

ArrayList waitingProcess = new ArrayList();

int time = ;

int complete_process = ;

while (AllProcess.Count != complete_process) {

CheckArrivalTime(AllProcess, waitingProcess, time);

if (waitingProcess.Count <= ) {

time++;

continue;

}

Sort(waitingProcess);

MyProcess LongestProcess = (MyProcess)waitingProcess[];

time += LongestProcess.bt;

LongestProcess.completion_time = time;

LongestProcess.is_finished = true;

waitingProcess.RemoveAt();

complete_process++;

}

public static void CalWaitingTime(ArrayList p) {

for (int i = ; i < p.Count; i++) {

MyProcess p1 = (MyProcess)p[i];

p1.waiting_time = p1.completion_time - p1.bt - p1.art;

if (p1.waiting_time < ) {

p1.waiting_time = ;

}

public static void Sort(ArrayList waitingProcess) {

for (int i = ; i < waitingProcess.Count; i++) {

for (int j = ; j < waitingProcess.Count - 1; j++) {

MyProcess p1 = (MyProcess) waitingProcess[j];

MyProcess p2 = (MyProcess) waitingProcess[j + 1];

if (p2.bt > p1.bt) {

waitingProcess [j] = waitingProcess [j + 1];

waitingProcess [j + 1] = p1;

}

public static void CheckArrivalTime(ArrayList Process, ArrayList waitingProcess, int time) {

for (int i = ; i < Process.Count; i++) {

MyProcess p = (MyProcess) Process[i];

if (p.art <= time && !p.addTowaiting) {

p.addTowaiting = true;

waitingProcess.Add(p);

}

public class MyProcess {

public int pid; // Process ID

public int bt; // Burst Time

public int art; // Arrival Time

public int completion_time;

public int waiting_time;

public int tat;//turn around time

public bool is_finished = false;

public bool addTowaiting = false;

public MyProcess(int pid, int bt, int art) {

this.pid = pid;

this.bt = bt;

this.art = art;

}

بیشتر بخوانید: ک م م در سی شارپ (کوچکترین مضرب مشترک)

ما برای پیاده‌سازی الگوریتم LJF از دو کلاس زیر استفاده کردیم:

MyProcess: این کلاس برای تعریف یک فرآیند استفاده می‌شود و مواردی همچون Burst Time، arrival Time و waiting time و …. در آن تعریف شده است.
LJF: در این کلاس الگوریتم LJF پیاده سازی شده است.

متدهای کد فوق شامل موارد زیر است:

CheckArrivalTime: این متد زمان ورود فرآیندها را به صف انتظار بررسی می‌کند.
Sort: این متد صف انتظار ما را با روش مرتب سازی حبابی، مرتب می‌کند(به صورت نزولی).
CalWaitingTime: محاسبه waiting time فرآیندها در این متد انجام می‌شود.
LJF: با کمک متدهای موارد بالا، الگوریتم LJF در این متد به اجرا در می‌آید.
Display: جهت نمایش فرآیند ها در خروجی از display استفاده می‌شود.

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

AllProcess یا p یا process: تمامی فرآیندها در Arraylist به نام AllProcess (p یا process) ذخیره می‌شوند.
waitingProcess: منظور صف انتظار ما است.
Bt: منظور burst time فرآیند است.
Art: منظور arrival Time است.
Tat: منظور turn around time است.

خروجی کد فوق به صورت زیر است:

پسورد: www.codegate.ir

دسته بندی: #c, الگوریتم زمانبندی در سی شارپ, سی شارپ برچسب ها: c#, Csharp, الگوریتم LJF, الگوریتم زمان‌بندی, سی شارپ

الگوریتم زمان‌بندی LJF در سی شارپ (Longest Job First)

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

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

مطالب مرتبط:

دیدگاهتان را بنویسید لغو پاسخ