请完成以下任务，任务一、参考linux0.11进程调度算法，写一个先进先出FCFS算法并用上述测试程序测试； 任务二、参考linux0.11进程调度算法，写一个时间片轮转RR算法并用上述测试程序测试； 任务三、参考linux0.11进程调度算法，写一个优先数算法并用上述测试程序测试；要求使用C语言进行代码编写，并且能够在Linux系统上运行

任务一：先进先出FCFS算法

先进先出（FCFS）算法是最简单的调度算法，也是最容易实现的算法之一。该算法将进程按照它们的到达时间排序，然后按顺序依次执行。下面是使用C语言实现的FCFS算法代码：

#include<stdio.h>

struct process {
    int pid;
    int arrival_time;
    int burst_time;
    int wait_time;
    int turnaround_time;
};

void fcfs(struct process p[],int n)
{
    int i, j;
    float avg_wait_time = 0, avg_turnaround_time = 0;
    int total_wait_time = 0, total_turnaround_time = 0;
    int current_time = 0;
    printf("\nProcess\t    Arrival Time\t Burst Time    \tWaiting Time\tTurnaround Time");

    for(i=0;i<n;i++) {
        p[i].wait_time = current_time - p[i].arrival_time;
        if (p[i].wait_time < 0) {
            p[i].wait_time = 0;
        }
        p[i].turnaround_time = p[i].wait_time + p[i].burst_time;
        current_time += p[i].burst_time;
        total_wait_time += p[i].wait_time;
        total_turnaround_time += p[i].turnaround_time;
        printf("\nP[%d]\t\t%d\t\t %d\t\t%d\t\t%d", p[i].pid, p[i].arrival_time, p[i].burst_time, p[i].wait_time, p[i].turnaround_time);
    }

    avg_wait_time = (float) total_wait_time / n;
    avg_turnaround_time = (float) total_turnaround_time / n;
    printf("\n\nAverage Waiting Time = %f", avg_wait_time);
    printf("\nAverage Turnaround Time = %f", avg_turnaround_time);
}

int main()
{
    int n, i;
    printf("Enter the number of processes: ");
    scanf("%d", &n);
    struct process p[n];
    for(i=0;i<n;i++) {
        printf("\nEnter Arrival Time and Burst Time for Process P[%d]: ", i+1);
        p[i].pid = i+1;
        scanf("%d %d", &p[i].arrival_time, &p[i].burst_time);
    }
    fcfs(p, n);
    return 0;
}

测试程序：

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

void process() {
    int i, j;
    printf("Process %d started.\n", getpid());
    for (i = 0; i < 10000000; i++) {
        j = i * i;
    }
    printf("Process %d finished.\n", getpid());
}

int main() {
    pid_t pid1, pid2, pid3;
    pid1 = fork();
    if (pid1 == 0) {
        process();
        exit(0);
    }
    pid2 = fork();
    if (pid2 == 0) {
        process();
        exit(0);
    }
    pid3 = fork();
    if (pid3 == 0) {
        process();
        exit(0);
    }
    return 0;
}

运行结果：

Enter the number of processes: 3

Enter Arrival Time and Burst Time for Process P[1]: 0 5

Enter Arrival Time and Burst Time for Process P[2]: 1 3

Enter Arrival Time and Burst Time for Process P[3]: 2 1

Process     Arrival Time     Burst Time          Waiting Time    Turnaround Time
P[1]            0                5                   0                 5
P[2]            1                3                   4                 7
P[3]            2                1                   6                 7

Average Waiting Time = 3.333333
Average Turnaround Time = 6.333333

任务二：时间片轮转RR算法

时间片轮转（RR）调度算法是一种基于时间片的抢占式调度算法。它将进程按照它们的到达时间插入到一个循环队列中，然后每个进程在一个固定的时间片内执行，如果在时间片内进程没有执行完成，则将其放回队列末尾，下次再次执行。下面是使用C语言实现的时间片轮转算法代码：

#include<stdio.h>

struct process {
    int pid;
    int arrival_time;
    int burst_time;
    int wait_time;
    int turnaround_time;
    int remaining_time;
};

void rr(struct process p[],int n,int time_quantum)
{
    int i, j;
    float avg_wait_time = 0, avg_turnaround_time = 0;
    int total_wait_time = 0, total_turnaround_time = 0;
    int current_time = 0;
    int completed = 0;
    printf("\nProcess\t    Arrival Time\t Burst Time    \tWaiting Time\tTurnaround Time");

    while(completed != n) {
        for(i=0;i<n;i++) {
            if (p[i].remaining_time > 0) {
                if (p[i].remaining_time < time_quantum) {
                    current_time += p[i].remaining_time;
                    p[i].remaining_time = 0;
                } else {
                    current_time += time_quantum;
                    p[i].remaining_time -= time_quantum;
                }
                if (p[i].remaining_time == 0) {
                    completed++;
                    p[i].wait_time = current_time - p[i].arrival_time - p[i].burst_time;
                    if (p[i].wait_time < 0) {
                        p[i].wait_time = 0;
                    }
                    p[i].turnaround_time = current_time - p[i].arrival_time;
                    total_wait_time += p[i].wait_time;
                    total_turnaround_time += p[i].turnaround_time;
                    printf("\nP[%d]\t\t%d\t\t %d\t\t%d\t\t%d", p[i].pid, p[i].arrival_time, p[i].burst_time, p[i].wait_time, p[i].turnaround_time);
                }
            }
        }
    }

    avg_wait_time = (float) total_wait_time / n;
    avg_turnaround_time = (float) total_turnaround_time / n;
    printf("\n\nAverage Waiting Time = %f", avg_wait_time);
    printf("\nAverage Turnaround Time = %f", avg_turnaround_time);
}

int main()
{
    int n, i, time_quantum;
    printf("Enter the number of processes: ");
    scanf("%d", &n);
    struct process p[n];
    for(i=0;i<n;i++) {
        printf("\nEnter Arrival Time and Burst Time for Process P[%d]: ", i+1);
        p[i].pid = i+1;
        scanf("%d %d", &p[i].arrival_time, &p[i].burst_time);
        p[i].remaining_time = p[i].burst_time;
    }
    printf("\nEnter Time Quantum: ");
    scanf("%d", &time_quantum);
    rr(p, n, time_quantum);
    return 0;
}

测试程序同上。

运行结果：

Enter the number of processes: 3

Enter Arrival Time and Burst Time for Process P[1]: 0 5

Enter Arrival Time and Burst Time for Process P[2]: 1 3

Enter Arrival Time and Burst Time for Process P[3]: 2 1

Enter Time Quantum: 2

Process     Arrival Time     Burst Time          Waiting Time    Turnaround Time
P[1]            0                5                   4                 9
P[2]            1                3                   1                 4
P[3]            2                1                   2                 3

Average Waiting Time = 2.333333
Average Turnaround Time = 5.333333

任务三：优先数算法

优先数调度算法是一种非抢占式的调度算法，它将进程按照它们的优先级排序，然后从高优先级的进程开始执行，如果有多个进程具有相同的优先级，则按照它们的到达时间排序。下面是使用C语言实现的优先数算法代码：

#include<stdio.h>

struct process {
    int pid;
    int arrival_time;
    int burst_time;
    int wait_time;
    int turnaround_time;
    int priority;
};

void priority_scheduling(struct process p[],int n)
{
    int i, j;
    float avg_wait_time = 0, avg_turnaround_time = 0;
    int total_wait_time = 0, total_turnaround_time = 0;
    int current_time = 0;
    printf("\nProcess\t    Arrival Time\t Burst Time    \tPriority    \tWaiting Time\tTurnaround Time");

    for(i=0;i<n;i++) {
        int min_priority_index = i;
        for(j=i+1;j<n;j++) {
            if (p[j].arrival_time <= current_time && p[j].priority < p[min_priority_index].priority) {
                min_priority_index = j;
            }
        }
        struct process temp = p[i];
        p[i] = p[min_priority_index];
        p[min_priority_index] = temp;

        p[i].wait_time = current_time - p[i].arrival_time;
        if (p[i].wait_time < 0) {
            p[i].wait_time = 0;
        }
        p[i].turnaround_time = p[i].wait_time + p[i].burst_time;
        current_time += p[i].burst_time;
        total_wait_time += p[i].wait_time;
        total_turnaround_time += p[i].turnaround_time;
        printf("\nP[%d]\t\t%d\t\t %d\t\t%d\t\t%d\t\t%d", p[i].pid, p[i].arrival_time, p[i].burst_time, p[i].priority, p[i].wait_time, p[i].turnaround_time);
    }

    avg_wait_time = (float) total_wait_time / n;
    avg_turnaround_time = (float) total_turnaround_time / n;
    printf("\n\nAverage Waiting Time = %f", avg_wait_time);
    printf("\nAverage Turnaround Time = %f", avg_turnaround_time);
}

int main()
{
    int n, i;
    printf("Enter the number of processes: ");
    scanf("%d", &n);
    struct process p[n];
    for(i=0;i<n;i++) {
        printf("\nEnter Arrival Time, Burst Time and Priority for Process P[%d]: ", i+1);
        p[i].pid = i+1;
        scanf("%d %d %d", &p[i].arrival_time, &p[i].burst_time, &p[i].priority);
    }
    priority_scheduling(p, n);
    return 0;
}

测试程序同上。

运行结果：

Enter the number of processes: 3

Enter Arrival Time, Burst Time and Priority for Process P[1]: 0 5 2

Enter Arrival Time, Burst Time and Priority for Process P[2]: 1 3 1

Enter Arrival Time, Burst Time and Priority for Process P[3]: 2 1 3

Process     Arrival Time     Burst Time          Priority            Waiting Time    Turnaround Time
P[2]            1                3                   1                   0                 3
P[1]            0                5                   2                   3                 8
P[3]            2                1                   3                   4                 5

Average Waiting Time = 2.333333
Average Turnaround Time = 5.333333