Mục lục
Trong bài viết này chúng ta sẽ cùng nhau tìm hiểu thuật toán irst come first serve (fcfs) và cách triển khai thuật toán này bằng ngôn ngữ Java.
First Come First Serve (FCFS) Scheduling
First come First serve có nghĩa là công việc nào tới trước sẽ được xử lý trước. Ví dụ chúng ta đang xếp hàng để đợi đến lượt mua vé xem phim, ai đến trước thì sẽ được xếp lên trên và được ưu tiên mua vé trước.
Quay trở lại với ngữ cảnh của giải thuật này, một bộ xử lý có thể được phân công xử lý nhiều công việc cùng lúc vì vậy nó cần có một lịch trình cụ thể để thực thi các công việc trên. Nếu sử dụng chiến lược FCFS để lập lịch trình thì công việc nào được gửi đến bộ xử lý trước thì sẽ được xử lý trước và những công việc đến sau sẽ phải đợi cho đến khi công việc hiện tại hoàn thành thì mới được xử lý.
Ví dụ
| Process | Arrival Time | Burst Time |
| P1 | 0 ms | 9 ms |
| P2 | 1 ms | 4 ms |
| P3 | 2 ms | 9 ms |
Trong đó:
- Process: Công việc cần xử lý
- Arrival time: Thời gian mà công việc được gửi đến bộ xử lý
- Burst time: Thời gian cần thiết để hoàn thành công việc
Nếu áp dụng FCFS để lập lịch trình cho bộ xử lý thì P0 đến đầu tiên cho nên nó sẽ được thực thi đầu tiên. Sau khi P0 hoàn tất mất khoảng 9ms, tại thời điểm này hàng đợi đã có 2 cả P2 và P3. Tuy nhiên P2 đến sớm hơn cho nên nó sẽ được xử lý trước. Sau đó P3 sẽ được thực thi cuối cùng.
Sơ đồ thực thi:
Waiting time:
| Process | Waiting time = first scheduled time – arrival time (ms) |
| P0 | 0-0 = 0 |
| P1 | 9-1= 8 |
| P2 | 13-2 =11 |
Average waiting time là (0+8+11)/3 = 6.33ms
Turnaround Times:
| Process | Turnaround Time = execution time + waiting time |
| P0 | 0+9=9 |
| P1 | 8+4=12 |
| P2 | 11+9=20 |
Average turnaround time = (9+12+20)/3 = 13.66ms
Triển khai First Come First Serve (FCFS) bằng Java
import java.util.*;
public class FCFS {
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
System.out.println("enter no of process: ");
int n = sc.nextInt();
int pid[] = new int[n];
int ar[] = new int[n];
int bt[] = new int[n];
int ct[] = new int[n];
int ta[] = new int[n];
int wt[] = new int[n];
int temp;
float avgwt = 0, avgta = 0;
for (int i = 0; i < n; i++) {
System.out.println("enter process " + (i + 1) + " arrival time: ");
ar[i] = sc.nextInt();
System.out.println("enter process " + (i + 1) + " brust time: ");
bt[i] = sc.nextInt();
pid[i] = i + 1;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n - (i + 1); j++) {
if (ar[j] > ar[j + 1]) {
temp = ar[j];
ar[j] = ar[j + 1];
ar[j + 1] = temp;
temp = bt[j];
bt[j] = bt[j + 1];
bt[j + 1] = temp;
temp = pid[j];
pid[j] = pid[j + 1];
pid[j + 1] = temp;
}
}
}
for (int i = 0; i < n; i++) {
if (i == 0) {
ct[i] = ar[i] + bt[i];
} else {
if (ar[i] > ct[i - 1]) {
ct[i] = ar[i] + bt[i];
} else
ct[i] = ct[i - 1] + bt[i];
}
ta[i] = ct[i] - ar[i];
wt[i] = ta[i] - bt[i];
avgwt += wt[i];
avgta += ta[i];
}
System.out.println("\npid arrival brust complete turn waiting");
for (int i = 0; i < n; i++) {
System.out.println(pid[i] + " \t " + ar[i] + "\t" + bt[i] + "\t" + ct[i] + "\t" + ta[i] + "\t" + wt[i]);
}
sc.close();
System.out.println("\naverage waiting time: " + (avgwt / n));
System.out.println("average turnaround time:" + (avgta / n));
}
}
Output
enter no of process: 3 enter process 1 arrival time: 0 enter process 1 brust time: 9 enter process 2 arrival time: 1 enter process 2 brust time: 4 enter process 3 arrival time: 2 enter process 3 brust time: 9 pid arrival brust complete turn waiting 1 0 9 9 9 0 2 1 4 13 12 8 3 2 9 22 20 11 average waiting time: 6.3333335 average turnaround time:13.666667 Process finished with exit code 0
FCFS có lợi thế là dễ hiểu và dễ triển khai tuy nhiên nó có một số nhược điểm là nếu một công việc tốn nhiều thời gian thực thi đến trước thì tất cả các công việc cần ít thời gian hơn sẽ bị đẩy vào hàng chờ. Nó sẽ làm tăng thời gian chờ đợi trung bình.
Nguồn tham khảo
https://www.geeksforgeeks.org/program-for-fcfs-cpu-scheduling-set-1/
Java Program for First Come First Serve (FCFS) Scheduling Algorithm