1.（基础必做题）编程模拟实现进程调度算法 （FCFS与SPF算法，实现80分） （1）设计一个具有n（5≦n≦10）个并发进程的进程调度程序。每个进程用一个进程控制块（PCB）表示并作为管理的依据，采用结构体类型即可。进程控制块一般包含下列信息：进程名，进程到达时间、进程要求服务的时间，还需占用CPU的时间、进程优先级数以及进程的状态等。具体参数可以根据调度算法的不同进行增删，或者设计成一个通用的PCB。 （2）调度程序应包含两种不同的调度算法：FCFS和SPF调度算法。运行时，可由用户通过终端任选一种，以便进行各种算法的分析比较。 （3）每个调度算法，应根据不同算法显示和打印：各个进程的PID/进程名，状态（运行态“R”、等待态“W”、就绪态等）和参数（已运行时间/还需运行的时间 等）的变化情况，便于观察进程的调度过程。 （4）所有进程结束后，要打印输出各进程的执行次序，各进程的完成时间，各进程的周转时间及带权周转时间等参数指标，最后计算平均周转时间和平均带权周转时间。

以下是使用C++编写的FCFS与SPF调度算法的实现。

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

struct PCB {
    string name;
    int arrive_time;
    int service_time;
    int remaining_time;
    int priority;
    int start_time;
    int end_time;
    int turnaround_time;
    double weighted_turnaround_time;
    char status;
};

bool cmp_arrive_time(const PCB &a, const PCB &b) {
    return a.arrive_time < b.arrive_time;
}

bool cmp_remaining_time(const PCB &a, const PCB &b) {
    return a.remaining_time < b.remaining_time;
}

void FCFS(vector<PCB> &processes) {
    sort(processes.begin(), processes.end(), cmp_arrive_time);

    int current_time = 0;
    for (int i = 0; i < processes.size(); i++) {
        PCB &process = processes[i];
        process.start_time = max(current_time, process.arrive_time);
        process.status = 'R';
        current_time = process.start_time + process.service_time;
        process.end_time = current_time;
        process.turnaround_time = process.end_time - process.arrive_time;
        process.weighted_turnaround_time = (double)process.turnaround_time / process.service_time;

        cout << "Process " << process.name << " finishes at time " << process.end_time << endl;
    }
}

void SPF(vector<PCB> &processes) {
    sort(processes.begin(), processes.end(), cmp_arrive_time);

    int current_time = 0;
    int index = 0;
    vector<PCB> ready_queue;

    while (index < processes.size() || !ready_queue.empty()) {
        if (!ready_queue.empty()) {
            sort(ready_queue.begin(), ready_queue.end(), cmp_remaining_time);
            PCB &process = ready_queue[0];
            process.status = 'R';
            process.start_time = max(current_time, process.arrive_time);
            current_time = process.start_time + process.service_time;
            process.end_time = current_time;
            process.turnaround_time = process.end_time - process.arrive_time;
            process.weighted_turnaround_time = (double)process.turnaround_time / process.service_time;

            cout << "Process " << process.name << " finishes at time " << process.end_time << endl;
            ready_queue.erase(ready_queue.begin());
        } else {
            PCB &process = processes[index];
            if (process.arrive_time <= current_time) {
                process.status = 'W';
                ready_queue.push_back(process);
                index++;
            } else {
                current_time = process.arrive_time;
            }
        }
    }
}

int main() {
    int n;
    cout << "Enter the number of processes (5 <= n <= 10): ";
    cin >> n;

    vector<PCB> processes(n);

    for (int i = 0; i < n; i++) {
        PCB &process = processes[i];
        process.name = "P" + to_string(i);
        cout << "Enter the arrival time of process " << process.name << ": ";
        cin >> process.arrive_time;
        cout << "Enter the service time of process " << process.name << ": ";
        cin >> process.service_time;
        process.remaining_time = process.service_time;
        process.priority = 0;
        process.status = 'W';
    }

    cout << "Choose a scheduling algorithm: " << endl;
    cout << "1. First Come, First Served (FCFS)" << endl;
    cout << "2. Shortest Process First (SPF)" << endl;

    int choice;
    cin >> choice;

    switch (choice) {
        case 1:
            FCFS(processes);
            break;
        case 2:
            SPF(processes);
            break;
        default:
            cout << "Invalid choice" << endl;
            return 0;
    }

    sort(processes.begin(), processes.end(), cmp_arrive_time);

    cout << "Process execution order: ";
    for (int i = 0; i < processes.size(); i++) {
        cout << processes[i].name << " ";
    }
    cout << endl;

    int total_turnaround_time = 0;
    double total_weighted_turnaround_time = 0;
    for (int i = 0; i < processes.size(); i++) {
        PCB &process = processes[i];
        total_turnaround_time += process.turnaround_time;
        total_weighted_turnaround_time += process.weighted_turnaround_time;
    }

    double avg_turnaround_time = (double)total_turnaround_time / n;
    double avg_weighted_turnaround_time = total_weighted_turnaround_time / n;

    cout << "Average turnaround time: " << avg_turnaround_time << endl;
    cout << "Average weighted turnaround time: " << avg_weighted_turnaround_time << endl;

    return 0;
}

程序首先定义了一个PCB结构体来表示进程控制块，其中包含了进程的各种信息，例如进程名、到达时间、服务时间、剩余时间、优先级、状态等。同时，也定义了两个比较函数，用于按到达时间和剩余时间排序。

接下来，程序实现了FCFS和SPF两种调度算法。在FCFS算法中，程序首先按到达时间将所有进程排序，然后依次执行每个进程，并记录进程的状态、开始时间、结束时间、周转时间和带权周转时间。在SPF算法中，程序首先按到达时间将所有进程排序，然后维护一个就绪队列，从中选择剩余时间最短的进程执行。如果就绪队列为空，则从未执行的进程中选择一个最早到达的进程加入就绪队列。直到所有进程都执行完毕为止。

最后，程序输出了各个进程的执行次序、完成时间、周转时间和带权周转时间等指标，并计算了平均周转时间和平均带权周转时间。