FCFS、SJF、RR、Priority算法的实验小结

FCFS、SJF、RR、Priority 算法都是常见的进程调度算法。它们各有优缺点，适用于不同的场景。

FCFS 算法是先来先服务的调度算法，它简单易懂，但是无法处理特定的场景，比如短作业优先的情况。在长作业的情况下，可能会出现饥饿现象，即短作业需要等待长作业执行完成才能得到调度。

SJF 算法是短作业优先的调度算法，它可以有效地避免饥饿现象，但是需要预测作业的执行时间，如果预测不准确可能会导致长作业等待时间过长。

RR 算法是时间片轮转的调度算法，它可以保证每个作业都有执行的机会，并且在短作业和长作业之间平衡，但是时间片大小的选择会影响调度效率。

Priority 算法是根据作业的优先级来进行调度的算法，可以根据不同的场景设置不同的优先级，但是可能会出现优先级反转的情况，即优先级低的作业需要等待优先级高的作业执行完成才能得到调度。

综上所述，不同的算法适用于不同的场景，需要根据具体情况选择合适的算法。在实际应用中，可以根据不同的业务需求和系统特点进行调整，以达到最优的调度效果。

相关问题

C语言实现FCFS 、SJF 、RR 、PSA调度算法

以下是C语言实现FCFS、SJF、RR、PSA调度算法的代码示例：

#include <stdio.h>
#include <stdlib.h>

#define MAX_PROCESSES 10

typedef struct {
    int pid;
    int arrival_time;
    int burst_time;
    int waiting_time;
    int turnaround_time;
} Process;

void fcfs(Process processes[], int n) {
    int current_time = 0;
    for (int i = 0; i < n; i++) {
        if (processes[i].arrival_time > current_time) {
            current_time = processes[i].arrival_time;
        }
        processes[i].waiting_time = current_time - processes[i].arrival_time;
        processes[i].turnaround_time = processes[i].waiting_time + processes[i].burst_time;
        current_time += processes[i].burst_time;
    }
}

void sjf(Process processes[], int n) {
    int current_time = 0;
    int remaining_processes = n;
    while (remaining_processes > 0) {
        int next_process_index = -1;
        int shortest_burst_time = 999999;
        for (int i = 0; i < n; i++) {
            if (processes[i].arrival_time <= current_time && processes[i].burst_time < shortest_burst_time) {
                next_process_index = i;
                shortest_burst_time = processes[i].burst_time;
            }
        }
        if (next_process_index == -1) {
            current_time++;
        } else {
            Process next_process = processes[next_process_index];
            processes[next_process_index] = processes[remaining_processes-1];
            processes[remaining_processes-1] = next_process;
            remaining_processes--;
            next_process.waiting_time = current_time - next_process.arrival_time;
            next_process.turnaround_time = next_process.waiting_time + next_process.burst_time;
            current_time += next_process.burst_time;
        }
    }
}

void rr(Process processes[], int n, int quantum) {
    int current_time = 0;
    int remaining_processes = n;
    while (remaining_processes > 0) {
        for (int i = 0; i < n; i++) {
            if (processes[i].arrival_time <= current_time && processes[i].burst_time > 0) {
                int time_slice = processes[i].burst_time < quantum ? processes[i].burst_time : quantum;
                processes[i].burst_time -= time_slice;
                current_time += time_slice;
                if (processes[i].burst_time == 0) {
                    remaining_processes--;
                    processes[i].waiting_time = current_time - processes[i].arrival_time - processes[i].turnaround_time;
                }
            }
        }
    }
}

void psa(Process processes[], int n) {
    int current_time = 0;
    int remaining_processes = n;
    while (remaining_processes > 0) {
        int highest_priority_index = -1;
        int highest_priority = -1;
        for (int i = 0; i < n; i++) {
            if (processes[i].arrival_time <= current_time && processes[i].burst_time > 0) {
                int priority = 1 + processes[i].waiting_time / processes[i].burst_time;
                if (priority > highest_priority) {
                    highest_priority_index = i;
                    highest_priority = priority;
                }
            }
        }
        if (highest_priority_index == -1) {
            current_time++;
        } else {
            Process next_process = processes[highest_priority_index];
            processes[highest_priority_index] = processes[remaining_processes-1];
            processes[remaining_processes-1] = next_process;
            remaining_processes--;
            next_process.waiting_time = current_time - next_process.arrival_time;
            next_process.turnaround_time = next_process.waiting_time + next_process.burst_time;
            current_time += next_process.burst_time;
        }
    }
}

int main() {
    Process processes[MAX_PROCESSES];
    int n;
    int quantum;
    printf("Enter the number of processes: ");
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        printf("Enter arrival time and burst time for process %d: ", i+1);
        scanf("%d %d", &processes[i].arrival_time, &processes[i].burst_time);
        processes[i].pid = i+1;
    }

    printf("\nFCFS:\n");
    fcfs(processes, n);
    for (int i = 0; i < n; i++) {
        printf("Process %d: arrival_time=%d, burst_time=%d, waiting_time=%d, turnaround_time=%d\n", processes[i].pid, processes[i].arrival_time, processes[i].burst_time, processes[i].waiting_time, processes[i].turnaround_time);
    }

    printf("\nSJF:\n");
    sjf(processes, n);
    for (int i = 0; i < n; i++) {
        printf("Process %d: arrival_time=%d, burst_time=%d, waiting_time=%d, turnaround_time=%d\n", processes[i].pid, processes[i].arrival_time, processes[i].burst_time, processes[i].waiting_time, processes[i].turnaround_time);
    }

    printf("\nEnter the time quantum for RR: ");
    scanf("%d", &quantum);
    printf("\nRR:\n");
    rr(processes, n, quantum);
    for (int i = 0; i < n; i++) {
        printf("Process %d: arrival_time=%d, burst_time=%d, waiting_time=%d, turnaround_time=%d\n", processes[i].pid, processes[i].arrival_time, processes[i].burst_time, processes[i].waiting_time, processes[i].turnaround_time);
    }

    printf("\nPSA:\n");
    psa(processes, n);
    for (int i = 0; i < n; i++) {
        printf("Process %d: arrival_time=%d, burst_time=%d, waiting_time=%d, turnaround_time=%d\n", processes[i].pid, processes[i].arrival_time, processes[i].burst_time, processes[i].waiting_time, processes[i].turnaround_time);
    }

    return 0;
}

在上面的代码中，有一个 `Process` 结构体来表示一个进程，包含 PID、到达时间、执行时间、等待时间和周转时间等属性。然后有四个函数 `fcfs`、`sjf`、`rr` 和 `psa` 分别实现先来先服务、最短作业优先、时间片轮转和优先级调度算法。最后在 `main` 函数中通过用户输入创建进程列表，依次使用四种算法对进程进行调度，并输出每个进程的信息。

将FCFS算法，SJF算法，RR算法，PSA算法用一个java程序写出来

以下是一个使用Java语言实现四种调度算法的示例代码：

1. FCFS算法

import java.util.*;

public class FCFS {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("请输入作业数：");
        int n = scanner.nextInt();

        int[] arriveTime = new int[n]; // 到达时间
        int[] serviceTime = new int[n]; // 服务时间

        for (int i = 0; i < n; i++) {
            System.out.print("请输入第" + (i+1) + "个作业的到达时间和服务时间：");
            arriveTime[i] = scanner.nextInt();
            serviceTime[i] = scanner.nextInt();
        }

        int[] finishTime = new int[n]; // 完成时间
        int[] waitingTime = new int[n]; // 等待时间
        int[] turnAroundTime = new int[n]; // 周转时间

        finishTime[0] = serviceTime[0];
        turnAroundTime[0] = finishTime[0] - arriveTime[0];
        waitingTime[0] = turnAroundTime[0] - serviceTime[0];

        for (int i = 1; i < n; i++) {
            finishTime[i] = finishTime[i-1] + serviceTime[i];
            turnAroundTime[i] = finishTime[i] - arriveTime[i];
            waitingTime[i] = turnAroundTime[i] - serviceTime[i];
        }

        double avgWaitingTime = 0.0;
        double avgTurnAroundTime = 0.0;

        for (int i = 0; i < n; i++) {
            avgWaitingTime += waitingTime[i];
            avgTurnAroundTime += turnAroundTime[i];
        }

        avgWaitingTime /= n;
        avgTurnAroundTime /= n;

        System.out.println("作业\t到达时间\t服务时间\t完成时间\t等待时间\t周转时间");
        for (int i = 0; i < n; i++) {
            System.out.println((i+1) + "\t" + arriveTime[i] + "\t\t" + serviceTime[i] + "\t\t" + finishTime[i] + "\t\t" + waitingTime[i] + "\t\t" + turnAroundTime[i]);
        }
        System.out.println("平均等待时间：" + avgWaitingTime);
        System.out.println("平均周转时间：" + avgTurnAroundTime);
    }
}

2. SJF算法

import java.util.*;

public class SJF {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("请输入作业数：");
        int n = scanner.nextInt();

        int[] arriveTime = new int[n]; // 到达时间
        int[] serviceTime = new int[n]; // 服务时间

        for (int i = 0; i < n; i++) {
            System.out.print("请输入第" + (i+1) + "个作业的到达时间和服务时间：");
            arriveTime[i] = scanner.nextInt();
            serviceTime[i] = scanner.nextInt();
        }

        int[] finishTime = new int[n]; // 完成时间
        int[] waitingTime = new int[n]; // 等待时间
        int[] turnAroundTime = new int[n]; // 周转时间
        boolean[] visited = new boolean[n]; // 标记作业是否已经完成

        int currentTime = 0;
        int count = 0;

        while (count < n) {
            int minServiceTime = Integer.MAX_VALUE;
            int minIndex = -1;
            for (int i = 0; i < n; i++) {
                if (!visited[i] && arriveTime[i] <= currentTime && serviceTime[i] < minServiceTime) {
                    minServiceTime = serviceTime[i];
                    minIndex = i;
                }
            }
            if (minIndex != -1) {
                finishTime[minIndex] = currentTime + serviceTime[minIndex];
                turnAroundTime[minIndex] = finishTime[minIndex] - arriveTime[minIndex];
                waitingTime[minIndex] = turnAroundTime[minIndex] - serviceTime[minIndex];
                visited[minIndex] = true;
                count++;
                currentTime = finishTime[minIndex];
            } else {
                currentTime++;
            }
        }

        double avgWaitingTime = 0.0;
        double avgTurnAroundTime = 0.0;

        for (int i = 0; i < n; i++) {
            avgWaitingTime += waitingTime[i];
            avgTurnAroundTime += turnAroundTime[i];
        }

        avgWaitingTime /= n;
        avgTurnAroundTime /= n;

        System.out.println("作业\t到达时间\t服务时间\t完成时间\t等待时间\t周转时间");
        for (int i = 0; i < n; i++) {
            System.out.println((i+1) + "\t" + arriveTime[i] + "\t\t" + serviceTime[i] + "\t\t" + finishTime[i] + "\t\t" + waitingTime[i] + "\t\t" + turnAroundTime[i]);
        }
        System.out.println("平均等待时间：" + avgWaitingTime);
        System.out.println("平均周转时间：" + avgTurnAroundTime);
    }
}

3. RR算法

import java.util.*;

public class RR {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("请输入作业数：");
        int n = scanner.nextInt();

        int[] arriveTime = new int[n]; // 到达时间
        int[] serviceTime = new int[n]; // 服务时间

        for (int i = 0; i < n; i++) {
            System.out.print("请输入第" + (i+1) + "个作业的到达时间和服务时间：");
            arriveTime[i] = scanner.nextInt();
            serviceTime[i] = scanner.nextInt();
        }

        int quantum = 2; // 时间片大小

        int[] finishTime = new int[n]; // 完成时间
        int[] waitingTime = new int[n]; // 等待时间
        int[] turnAroundTime = new int[n]; // 周转时间

        int[] remainTime = new int[n]; // 剩余服务时间
        for (int i = 0; i < n; i++) {
            remainTime[i] = serviceTime[i];
        }

        int currentTime = 0;
        int count = 0;

        while (count < n) {
            boolean flag = false;
            for (int i = 0; i < n; i++) {
                if (arriveTime[i] <= currentTime && remainTime[i] > 0) {
                    if (remainTime[i] > quantum) {
                        currentTime += quantum;
                        remainTime[i] -= quantum;
                    } else {
                        currentTime += remainTime[i];
                        finishTime[i] = currentTime;
                        turnAroundTime[i] = finishTime[i] - arriveTime[i];
                        waitingTime[i] = turnAroundTime[i] - serviceTime[i];
                        remainTime[i] = 0;
                        count++;
                    }
                    flag = true;
                }
            }
            if (!flag) {
                currentTime++;
            }
        }

        double avgWaitingTime = 0.0;
        double avgTurnAroundTime = 0.0;

        for (int i = 0; i < n; i++) {
            avgWaitingTime += waitingTime[i];
            avgTurnAroundTime += turnAroundTime[i];
        }

        avgWaitingTime /= n;
        avgTurnAroundTime /= n;

        System.out.println("作业\t到达时间\t服务时间\t完成时间\t等待时间\t周转时间");
        for (int i = 0; i < n; i++) {
            System.out.println((i+1) + "\t" + arriveTime[i] + "\t\t" + serviceTime[i] + "\t\t" + finishTime[i] + "\t\t" + waitingTime[i] + "\t\t" + turnAroundTime[i]);
        }
        System.out.println("平均等待时间：" + avgWaitingTime);
        System.out.println("平均周转时间：" + avgTurnAroundTime);
    }
}

4. PSA算法

import java.util.*;

public class PSA {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("请输入作业数：");
        int n = scanner.nextInt();

        int[] arriveTime = new int[n]; // 到达时间
        int[] serviceTime = new int[n]; // 服务时间
        int[] priority = new int[n]; // 优先级

        for (int i = 0; i < n; i++) {
            System.out.print("请输入第" + (i+1) + "个作业的到达时间、服务时间和优先级：");
            arriveTime[i] = scanner.nextInt();
            serviceTime[i] = scanner.nextInt();
            priority[i] = scanner.nextInt();
        }

        int[] finishTime = new int[n]; // 完成时间
        int[] waitingTime = new int[n]; // 等待时间
        int[] turnAroundTime = new int[n]; // 周转时间
        boolean[] visited = new boolean[n]; // 标记作业是否已经完成

        int currentTime = 0;
        int count = 0;

        while (count < n) {
            int maxPriority = Integer.MIN_VALUE;
            int maxIndex = -1;
            for (int i = 0; i < n; i++) {
                if (!visited[i] && arriveTime[i] <= currentTime && priority[i] > maxPriority) {
                    maxPriority = priority[i];
                    maxIndex = i;
                }
            }
            if (maxIndex != -1) {
                finishTime[maxIndex] = currentTime + serviceTime[maxIndex];
                turnAroundTime[maxIndex] = finishTime[maxIndex] - arriveTime[maxIndex];
                waitingTime[maxIndex] = turnAroundTime[maxIndex] - serviceTime[maxIndex];
                visited[maxIndex] = true;
                count++;
                currentTime = finishTime[maxIndex];
            } else {
                currentTime++;
            }
        }

        double avgWaitingTime = 0.0;
        double avgTurnAroundTime = 0.0;

        for (int i = 0; i < n; i++) {
            avgWaitingTime += waitingTime[i];
            avgTurnAroundTime += turnAroundTime[i];
        }

        avgWaitingTime /= n;
        avgTurnAroundTime /= n;

        System.out.println("作业\t到达时间\t服务时间\t优先级\t完成时间\t等待时间\t周转时间");
        for (int i = 0; i < n; i++) {
            System.out.println((i+1) + "\t" + arriveTime[i] + "\t\t" + serviceTime[i] + "\t\t" + priority[i] + "\t\t" + finishTime[i] + "\t\t" + waitingTime[i] + "\t\t" + turnAroundTime[i]);
        }
        System.out.println("平均等待时间：" + avgWaitingTime);
        System.out.println("平均周转时间：" + avgTurnAroundTime);
    }
}