先来先服务(FCFS)调度算法（Java实现）

---

前言

在操作系统中作业调度的主要任务是根据PCB中的信息，检查系统中的资源能否满足作业对资源的需求，以及按照一定的调度算法从外存的后备队列中选取某些作业调入内存，并为它们创建进程、分配必要的资源。本文将以Java程序来实现先来先服务（FCFS）作业调度算法。

---

提示：以下是本篇文章正文内容，下面案例可供参考

一、先来先服务（FCFS）是什么？

FCFS是操作系统中最简单的调度算法，该算法既可用于作业调度，也可以用于进程调度。当在作业调度中采用该算法时，系统将按照作业到达的先后次序来进行调度或者说它是优先考虑在系统中等待时间最长的作业，而不管该作业所需执行时间的长短，从后备作业队列中选择几个最先进入该队列的作业，将它们调入内存并为它们分配资源和创建进程。然后把它放入就绪队列。

当在进程调度中采用FCFS算法时，每次调度是从就绪的进程队列中选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。该进程一直运行到完成或发生某事件而阻塞后，进程调度程序才将处理机分配给其它进程。

---

二、先来先服务（FCFS）算法分析

假设当前有四个进程先后到达系统进行调度：

在先来先服务算法中，由于在0时刻系统中只有作业A，因此系统将优先为作业A进行调度。作业A在完成的过程中作业B、C、D分别在5时刻、10时刻、15时刻都到达了系统中。也就是说在作业A调度完成后系统中会有B、C、D三个作业等待调度。根据先来先服务的思想，系统将依次按B、C、D的顺序为接下来的三个作业进行调度。

下面将依次分析各个作业的完成时间、周转时间、带权周转时间与平均带权周转时间：

1. 作业A：
   完成时间：因为作业A从0时刻开始服务，完成时间与服务时间相同为20
   周转时间：周转时间为从作业提交到作业完成的时间间隔，此时作业A的提交时间为0，完成时间为20，因此作业A的周转时间为20（20 - 0，也可以说是作业的完成时间 - 到达时间）
   带权周转时间：带权周转时间是指作业的周转时间与系统为它提供服务的时间之比，因为作业A的周转时间为20，系统提供的服务时间为20，因此作业A的带权周转时间为1（20 / 20，作业的周转时间 / 服务时间）
2. 作业B：
   完成时间：因为作业A在20时刻结束服务，所以作业B在20时刻开始服务，完成时间为开始服务时间加服务时间为35（20 + 15）
   周转时间：此时作业B的提交时间为5（从5时刻到达系统），完成时间为35，因此作业B的周转时间为30（35 - 5，完成时间 - 到达时间）
   带权周转时间：因为作业B的周转时间为30，系统提供的服务时间为15，因此作业B的带权周转时间为2（30 / 15，周转时间 / 服务时间）
3. 作业C：
   完成时间：因为作业B在35时刻结束服务，所以作业C在35时刻开始服务，完成时间为开始服务时间加服务时间为40（35 + 5）
   周转时间：此时作业C的提交时间为10（从10时刻到达系统），完成时间为40，因此作业C的周转时间为30（40 - 10，完成时间 - 到达时间）
   带权周转时间：因为作业C的周转时间为30，系统提供的服务时间为5，因此作业C的带权周转时间为6（30 / 5，周转时间 / 服务时间）
4. 作业D：
   完成时间：因为作业C在40时刻结束服务，所以作业D在40时刻开始服务，完成时间为开始服务时间加服务时间为50（40 + 10）
   周转时间：此时作业D的提交时间为15（从15时刻到达系统），完成时间为50，因此作业D的周转时间为35（50 - 15，完成时间 - 到达时间）
   带权周转时间：因为作业D的周转时间为35，系统提供的服务时间为10，因此作业A的带权周转时间为3.5（35 / 10，周转时间 / 服务时间）

平均周转时间：( 20 + 30 + 30 + 35 ) / 4 = 28.75
平均带权周转时间：( 20 / 20 + 30 / 15 + 30 / 5 + 35 / 10 ) / 4 = 3.125

---

三、实现代码

1、作业数据类

class ProcessData {
    // 到达时间
    public int arriveTime;
    // 服务时间
    public int serviceTime;
    // 完成时间
    public int finishTime;
    // 周转时间
    public int turnTime;
    // 带权周转时间
    public double powerTime;

	// 作业的构造方法中传来的初值为到达时间和服务时间
    public ProcessData(int arriveTime, int serviceTime) {
        this.arriveTime = arriveTime;
        this.serviceTime = serviceTime;
    }

	// 重写toString方法便于之后的数据展示
    @Override
    public String toString() {
        return  arriveTime + "\t" +
                serviceTime + "\t" + 
                finishTime + "\t" + 
                turnTime + "\t" + 
                powerTime;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

2、作业调度类

public class ProcessProject {
    // 平均周转时间
    public static double avgTotalTime;
    // 平均带权周转时间
    public static double avgPowerTime;

    public static void main(String[] args) {
    	// 定义长度为4，类型为作业数据类的作业数组用于存储4个作业
        ProcessData[] processData = new ProcessData[4];

        // 定义四个作业
        processData[0] = new ProcessData(0, 20);
        processData[1] = new ProcessData(5, 15);
        processData[2] = new ProcessData(10, 5);
        processData[3] = new ProcessData(15, 10);
        
        // 调用先来先服务算法
        FCFS(processData);
    }

    // 先来先服务算法实现
    private static void FCFS(ProcessData[] processData) {
        int preFinished = 0; // 前一个作业的完成时间即为下一个作业的开始时间
        avgTotalTime = 0;    // 平均周转时间
        avgPowerTime = 0;  // 平均带权周转时间

        // 初始化完成时间、周转时间、带权周转时间的初值为0
        for (int i = 0; i < processData.length; i++) {
            processData[i].finishTime = 0; // 设置初始完成时间为0
            processData[i].turnTime = 0; // 设置初始周转时间为0
            processData[i].powerTime = 0; // 设置初始带权周转时间为0
        }

        // 如果第一个作业的到达时间不等于前一个作业的完成时间，就将前一个作业的完成时间定义为当前作业的到达时间
        if (processData[0].arriveTime != preFinished) {
            preFinished = processData[0].arriveTime;
        }

        for (int i = 0; i < processData.length; i++) {
        	// 作业的完成时间为上一个作业的完成时间加当前作业的服务时间
            processData[i].finishTime = preFinished + processData[i].serviceTime;
            preFinished = processData[i].finishTime;
            // 周转时间 = 完成时间 - 到达时间
            processData[i].turnTime = processData[i].finishTime - processData[i].arriveTime;
            // 带权周转时间 = 作业的周转时间 / 系统提供服务的时间
            processData[i].powerTime = (double) processData[i].turnTime / (double) processData[i].serviceTime;
        }

        System.out.println("先来先服务（FCFS）算法：");

        // 打印进程的信息
        Display(processData);
    }

    private static void Display(ProcessData[] processData) {
        System.out.println("到达时间\t" + "服务时间\t" + "完成时间\t" + "周转时间\t" + "带权周转时间\t");
        for (int i = 0; i < processData.length; i++) {
            System.out.println(processData[i]);
            avgTotalTime += processData[i].turnTime; // 求总周转时间，此时avgTotalTime中存储的值为总周转时间
            avgPowerTime += processData[i].powerTime; // 求总带权周转时间，此时avgPowerTime中存储的值为总带权周转时间
        }

        avgTotalTime = avgTotalTime / processData.length; // 平均周转时间
        avgPowerTime = avgPowerTime / processData.length; // 平均带权周转时间

        System.out.println("平均周转时间：" + avgTotalTime);
        System.out.println("平均带权周转时间：" + avgPowerTime);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

3、运行结果

---

总结

以上便为操作系统中先来先服务（FCFS）作业调度的Java实现，FCFS算法在单处理机操作系统中已很少作为主调算法，但是经常把它与其它调度算法相结合使用，形成一种更为有效的调度算法。例如，可以在系统中按进程的优先级设置多个队列，每个优先级对应一个队列，其中每一个队列的调度都基于FCFS算法。