Cách triển khai thuật toán First Come First Serve (FCFS) trong Java

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ụ 

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:

Average waiting time là (0+8+11)/3 = 6.33ms

Turnaround Times:

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