FCFS SJF STN RR四种进程调度的算法

FCFS（First Come, First Served）算法是指按照进程到达的先后顺序进行调度。该算法的优点是简单易懂，缺点是容易产生“饥饿”现象，即长作业等待时间过长，严重影响系统的性能。

SJF（Shortest Job First）算法是指按照进程所需的运行时间进行调度，先运行所需运行时间最短的进程。该算法能够最大程度地减少平均等待时间和平均周转时间，但是会导致长作业等待时间过长，同样也会产生“饥饿”现象。

STN（Shortest Time Next）算法是对SJF算法的改进。该算法在SJF算法的基础上，增加了抢占机制。当有新的短作业到来时，可以抢占正在运行的长作业，从而减少长作业的等待时间。

RR（Round Robin）算法是指按照时间片轮流调度进程。每个进程被分配一个时间片，在该时间片内运行，时间片结束后，进程被放到就绪队列末尾，等待下一次调度。该算法能够保证所有进程都能得到一定的CPU时间，但是在时间片较长时会导致响应时间变慢，同时也会浪费一定的CPU资源。

相关问题

用JAVA实现四种进程调度算法（FCFS,SJF,RR,HRN）

使用Java来实现四种进程调度算法（FCFS，SJF，RR，HRN）可以采用以下步骤：1. 创建一个Process类，指定进程的PID，运行时间，运行状态等信息；2. 使用接口定义抽象的调度类，实现FCFS，SJF，RR，HRN四种算法的抽象方法；3. 编写调度程序，使用Process类创建进程，根据不同的调度算法，调用相应的调度类，实现进程的调度。

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` 函数中通过用户输入创建进程列表，依次使用四种算法对进程进行调度，并输出每个进程的信息。