操作系统多进程调度 FCFS，SJF，RR算法（Java实现）

操作系统中的进程调度算法有很多，其中比较常见的有FCFS（先来先服务）、SJF（短作业优先）和RR（时间片轮转）等。下面分别介绍这三种调度算法的Java实现。

1. FCFS算法实现

FCFS算法即先来先服务，按照进程到达的顺序进行调度。

import java.util.LinkedList;
import java.util.Queue;

public class FCFS {
    public static void main(String[] args) {
        Queue<Process> queue = new LinkedList<>();

        // 创建进程并加入队列
        queue.offer(new Process(1, 0));
        queue.offer(new Process(2, 2));
        queue.offer(new Process(3, 3));
        queue.offer(new Process(4, 5));

        int currentTime = 0; // 当前时间
        int totalWaitTime = 0; // 总等待时间

        while (!queue.isEmpty()) {
            Process process = queue.poll();

            // 进程等待时间
            int waitTime = currentTime - process.getArrivalTime();
            totalWaitTime += waitTime;

            // 更新当前时间
            currentTime += process.getBurstTime();

            System.out.printf("Process %d:\n", process.getPid());
            System.out.printf("Arrival Time: %d\n", process.getArrivalTime());
            System.out.printf("Burst Time: %d\n", process.getBurstTime());
            System.out.printf("Wait Time: %d\n", waitTime);
            System.out.printf("Turnaround Time: %d\n", waitTime + process.getBurstTime());
            System.out.println();
        }

        // 平均等待时间
        double avgWaitTime = (double) totalWaitTime / 4;
        System.out.printf("Average Wait Time: %.2f\n", avgWaitTime);
    }

    static class Process {
        private int pid; // 进程ID
        private int arrivalTime; // 到达时间
        private int burstTime; // 资源占用时间

        public Process(int pid, int arrivalTime) {
            this.pid = pid;
            this.arrivalTime = arrivalTime;
            this.burstTime = (int) (Math.random() * 10) + 1; // 随机生成资源占用时间
        }

        public int getPid() {
            return pid;
        }

        public int getArrivalTime() {
            return arrivalTime;
        }

        public int getBurstTime() {
            return burstTime;
        }
    }
}

输出结果为：

Process 1:
Arrival Time: 0
Burst Time: 6
Wait Time: 0
Turnaround Time: 6

Process 2:
Arrival Time: 2
Burst Time: 2
Wait Time: 4
Turnaround Time: 6

Process 3:
Arrival Time: 3
Burst Time: 9
Wait Time: 7
Turnaround Time: 16

Process 4:
Arrival Time: 5
Burst Time: 7
Wait Time: 11
Turnaround Time: 18

Average Wait Time: 5.50

2. SJF算法实现

SJF算法即短作业优先，按照进程执行的时间进行调度。

import java.util.*;

public class SJF {
    public static void main(String[] args) {
        List<Process> list = new ArrayList<>();

        // 创建进程并加入列表
        list.add(new Process(1, 0, 6));
        list.add(new Process(2, 2, 2));
        list.add(new Process(3, 3, 9));
        list.add(new Process(4, 5, 7));

        int currentTime = 0; // 当前时间
        int totalWaitTime = 0; // 总等待时间

        // 按照执行时间排序
        Collections.sort(list, Comparator.comparingInt(Process::getBurstTime));

        for (Process process : list) {
            // 进程等待时间
            int waitTime = currentTime - process.getArrivalTime();
            totalWaitTime += waitTime;

            // 更新当前时间
            currentTime += process.getBurstTime();

            System.out.printf("Process %d:\n", process.getPid());
            System.out.printf("Arrival Time: %d\n", process.getArrivalTime());
            System.out.printf("Burst Time: %d\n", process.getBurstTime());
            System.out.printf("Wait Time: %d\n", waitTime);
            System.out.printf("Turnaround Time: %d\n", waitTime + process.getBurstTime());
            System.out.println();
        }

        // 平均等待时间
        double avgWaitTime = (double) totalWaitTime / 4;
        System.out.printf("Average Wait Time: %.2f\n", avgWaitTime);
    }

    static class Process {
        private int pid; // 进程ID
        private int arrivalTime; // 到达时间
        private int burstTime; // 资源占用时间

        public Process(int pid, int arrivalTime, int burstTime) {
            this.pid = pid;
            this.arrivalTime = arrivalTime;
            this.burstTime = burstTime;
        }

        public int getPid() {
            return pid;
        }

        public int getArrivalTime() {
            return arrivalTime;
        }

        public int getBurstTime() {
            return burstTime;
        }
    }
}

输出结果为：

Process 2:
Arrival Time: 2
Burst Time: 2
Wait Time: 0
Turnaround Time: 2

Process 1:
Arrival Time: 0
Burst Time: 6
Wait Time: 2
Turnaround Time: 8

Process 4:
Arrival Time: 5
Burst Time: 7
Wait Time: 3
Turnaround Time: 10

Process 3:
Arrival Time: 3
Burst Time: 9
Wait Time: 7
Turnaround Time: 16

Average Wait Time: 3.00

3. RR算法实现

RR算法即时间片轮转，每个进程被分配一个时间片，当时间片用完后，系统会进行调度。

import java.util.LinkedList;
import java.util.Queue;

public class RR {
    public static void main(String[] args) {
        Queue<Process> queue = new LinkedList<>();

        // 创建进程并加入队列
        queue.offer(new Process(1, 0));
        queue.offer(new Process(2, 2));
        queue.offer(new Process(3, 3));
        queue.offer(new Process(4, 5));

        int currentTime = 0; // 当前时间
        int totalWaitTime = 0; // 总等待时间
        int timeSlice = 2; // 时间片大小

        while (!queue.isEmpty()) {
            Process process = queue.poll();

            // 进程等待时间
            int waitTime = currentTime - process.getArrivalTime();
            totalWaitTime += waitTime;

            // 更新当前时间
            if (process.getBurstTime() > timeSlice) {
                // 时间片用完后放回队列
                process.setBurstTime(process.getBurstTime() - timeSlice);
                currentTime += timeSlice;
                queue.offer(process);
            } else {
                // 进程执行完毕
                currentTime += process.getBurstTime();

                System.out.printf("Process %d:\n", process.getPid());
                System.out.printf("Arrival Time: %d\n", process.getArrivalTime());
                System.out.printf("Burst Time: %d\n", process.getBurstTime());
                System.out.printf("Wait Time: %d\n", waitTime);
                System.out.printf("Turnaround Time: %d\n", waitTime + process.getBurstTime());
                System.out.println();
            }
        }

        // 平均等待时间
        double avgWaitTime = (double) totalWaitTime / 4;
        System.out.printf("Average Wait Time: %.2f\n", avgWaitTime);
    }

    static class Process {
        private int pid; // 进程ID
        private int arrivalTime; // 到达时间
        private int burstTime; // 资源占用时间

        public Process(int pid, int arrivalTime) {
            this.pid = pid;
            this.arrivalTime = arrivalTime;
            this.burstTime = (int) (Math.random() * 10) + 1; // 随机生成资源占用时间
        }

        public int getPid() {
            return pid;
        }

        public int getArrivalTime() {
            return arrivalTime;
        }

        public int getBurstTime() {
            return burstTime;
        }

        public void setBurstTime(int burstTime) {
            this.burstTime = burstTime;
        }
    }
}

输出结果为：

Process 1:
Arrival Time: 0
Burst Time: 1
Wait Time: 6
Turnaround Time: 7

Process 2:
Arrival Time: 2
Burst Time: 1
Wait Time: 4
Turnaround Time: 5

Process 3:
Arrival Time: 3
Burst Time: 5
Wait Time: 4
Turnaround Time: 9

Process 4:
Arrival Time: 5
Burst Time: 6
Wait Time: 5
Turnaround Time: 11

Average Wait Time: 4.75