این جلسه ما را با ادامه آموزش الگوریتمهای زمانبندی همراهی کنید. در این قسمت به آموزش الگوریتم زمانبندی LJF در جاوا میپردازیم. ابتدا این الگوریتم را معرفی و سپس به پیادهسازی آن خواهیم پرداخت. پیشنهاد میکنیم قبل از مطالعه این جلسه، آموزشهای زیر را مطالعه کنید:
- الگوریتم Round Robin در جاوا
- الگوریتم FCFS در جاوا
- الگوریتم SJF در جاوا
- متد در جاوا
- Arraylist در جاوا
- شی گرایی در جاوا
- مرتب سازی حبابی در جاوا
- Constructor در جاوا
- حلقه for در جاوا
- حلقه while در جاوا
- If در جاوا
الگوریتم زمانبندی LJF
Longest Job First یا به اختصار LJF یک الگوریتم زمانبندی در سیستم عامل است. در این الگوریتم، همه فرآیندها بررسی و از بین فرایندهای منتظر در صف اجرا، فرایندی انتخاب میشود که به طولانیترین زمان برای اجرا شدن(burst Time) نیاز داشته باشد. به این جا به چند ویژگی LJF اشاره میکنیم:
- در این الگوریتم میتواند Starvation رخ دهد.
- زمان اتمام فرآیندها نزدیک به یکدیگر است.
- این روش مقدار Average time بالا است.
پیادهسازی الگوریتم زمانبندی LJF در جاوا
برای پیاده سازی الگوریتم زمانبندی LJF در جاوا مراحل زیر را انجام میدهیم:
- فرآیندهای خود را تعریف میکنیم.
- بر اساس arrival Time ، فرآیندها را وارد صف انتظار میکنیم.
- فرآیندهای درون صف انتظار را بر اساس Burst Time مرتب میکنیم(به صورت نزولی).
- به طولانیترین فرآیند CPU اختصاص مییابد.
- مراحل 2 تا 5 را تا زمان اتمام فرآیندها ادامه میدهیم.
کد الگوریتم LJF در جاوا به صورت زیر است:
import java.util.ArrayList;
import java.util.Collections;
public class LJF {
public static void main(String[] args) {
ArrayList<Process> p = new ArrayList<>();
p.add(new Process(1, 6, 1));
p.add(new Process(2, 8, 1));
p.add(new Process(3, 7, 2));
p.add(new Process(4, 3, 3));
LJF(p);
CalWaitingTime(p);
CalTurnAroundTime(p);
display(p);
}
private static void CalTurnAroundTime
(ArrayList<Process> p) {
for (int i = 0; i < p.size(); i++) {
p.get(i).tat = p.get(i).waiting_time + p.get(i).bt;
}
}
public static void display(ArrayList<Process> p) {
System.out.println
("Processes " + " Burst time " + " Waiting time " +
" Turn around time" + " Completion Time "+ " Arrival Time");
for (int i = 0; i < p.size(); i++) {
System.out.println
(" " + p.get(i).pid + "\t\t" + p.get(i).bt +
"\t\t " + p.get(i).waiting_time + "\t\t "+ p.get(i).tat +
"\t\t" + p.get(i).completion_time + "\t\t" + p.get(i).art);
}
}
public static void LJF(ArrayList<Process> AllProcess) {
ArrayList<Process> waitingProcess = new ArrayList<>();
int time = 0;
int complete_process = 0;
while (AllProcess.size() != complete_process) {
CheckArrivalTime
(AllProcess, waitingProcess, time);
if (waitingProcess.size() <= 0) {
time++;
continue;
}
Sort(waitingProcess);
Process LongestProcess = waitingProcess.get(0);
time += LongestProcess.bt;
LongestProcess.completion_time = time;
LongestProcess.is_finished = true;
waitingProcess.remove(0);
complete_process++;
}
}
public static void CalWaitingTime(ArrayList<Process> p) {
for (int i = 0; i < p.size(); i++) {
Process p1 = p.get(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<Process> waitingProcess) {
for (int i = 0; i < waitingProcess.size(); i++) {
for (int j = 0; j < waitingProcess.size() - 1; j++) {
Process p1 = waitingProcess.get(j);
Process p2 = waitingProcess.get(j + 1);
if (p2.bt > p1.bt) {
Collections.swap(waitingProcess, j, j + 1);
}
}
}
}
public static void CheckArrivalTime
(ArrayList<Process> Process,
ArrayList<Process> waitingProcess, int time) {
for (int i = 0; i < Process.size(); i++) {
Process p = Process.get(i);
if (p.art <= time && !p.addTowaiting) {
p.addTowaiting = true;
waitingProcess.add(p);
}
}
}
}
ما برای پیادهسازی الگوریتم LJF از دو کلاس زیر استفاده کردیم:
- Process: این کلاس برای تعریف یک فرآیند استفاده میشود و مواردی همچون 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 است.
خروجی کد فوق به صورت زیر است: