进程调度模拟实验报告

实验目的：
通过本次实验，了解进程调度算法的基本概念、原理和实现方法，掌握进程调度模拟的基本方法，加深对操作系统的理解。

实验环境：
操作系统：Windows 10
编程语言：C++

实验过程：
本次实验主要实现了三种进程调度算法：先来先服务（FCFS）、最短作业优先（SJF）、时间片轮转（RR）。下面将分别介绍这三种算法的实现过程和模拟结果。

1. 先来先服务（FCFS）
先来先服务是指按照进程到达的时间先后顺序进行调度，先到达的进程先执行。实现该算法的主要思路是维护一个进程队列，每当有一个新进程到达时，将其加入队列尾部，然后从队列头部取出一个进程执行。

实现过程中，需要定义一个进程结构体，包含进程的ID、到达时间、执行时间等属性。进程队列可以使用STL中的队列容器实现。具体代码如下：

struct Process {
    int id; // 进程ID
    int arriveTime; // 到达时间
    int executeTime; // 执行时间
    int startTime; // 开始时间
    int endTime; // 结束时间
};
queue<Process> q; // 进程队列

对于每个新到达的进程，可以使用以下代码将其加入进程队列：

Process p;
// 初始化进程属性
q.push(p); // 加入队列尾部

每次从队列头部取出一个进程执行，可以使用以下代码实现：

Process p = q.front(); // 取出队列头部进程
q.pop(); // 删除队列头部进程
// 执行进程，并更新进程的开始时间和结束时间

完整的先来先服务算法实现代码如下：

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

struct Process {
    int id; // 进程ID
    int arriveTime; // 到达时间
    int executeTime; // 执行时间
    int startTime; // 开始时间
    int endTime; // 结束时间
};

queue<Process> q; // 进程队列

bool cmp(Process a, Process b) {
    return a.arriveTime < b.arriveTime; // 按照到达时间升序排序
}

int main() {
    int n; // 进程数量
    cout << "请输入进程数量：";
    cin >> n;

    vector<Process> processes(n); // 进程数组
    cout << "请输入每个进程的到达时间和执行时间：" << endl;
    for (int i = 0; i < n; i++) {
        processes[i].id = i + 1;
        cin >> processes[i].arriveTime >> processes[i].executeTime;
    }

    sort(processes.begin(), processes.end(), cmp); // 按照到达时间升序排序

    int currentTime = 0; // 当前时间
    for (int i = 0; i < n; i++) {
        // 将所有到达时间小于等于当前时间的进程加入队列
        while (i < n && processes[i].arriveTime <= currentTime) {
            q.push(processes[i]);
            i++;
        }

        if (!q.empty()) {
            Process p = q.front(); // 取出队列头部进程
            q.pop(); // 删除队列头部进程

            p.startTime = currentTime; // 记录开始时间
            p.endTime = currentTime + p.executeTime; // 计算结束时间
            currentTime = p.endTime; // 更新当前时间

            cout << "进程" << p.id << "在时间" << p.startTime << "开始执行，" << "在时间" << p.endTime << "结束执行。" << endl;
        } else {
            currentTime = processes[i].arriveTime; // 更新当前时间为下一个进程的到达时间
            i--; // 下一轮循环要重新判断当前进程是否可以加入队列
        }
    }

    return 0;
}

2. 最短作业优先（SJF）
最短作业优先是指按照进程执行时间的大小顺序进行调度，执行时间短的进程先执行。实现该算法的主要思路是维护一个进程队列，每当有一个新进程到达时，将其加入队列并按照执行时间进行排序，然后从队列头部取出一个进程执行。

实现过程中，可以直接使用STL中的优先队列容器，按照执行时间进行排序。具体代码如下：

struct cmp {
    bool operator() (Process a, Process b) {
        return a.executeTime > b.executeTime; // 按照执行时间升序排序
    }
};
priority_queue<Process, vector<Process>, cmp> q; // 进程队列

每当有一个新进程到达时，可以使用以下代码将其加入进程队列并排序：

Process p;
// 初始化进程属性
q.push(p); // 加入队列

每次从队列头部取出一个进程执行，可以使用以下代码实现：

Process p = q.top(); // 取出队列头部进程
q.pop(); // 删除队列头部进程
// 执行进程，并更新进程的开始时间和结束时间

完整的最短作业优先算法实现代码如下：

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

struct Process {
    int id; // 进程ID
    int arriveTime; // 到达时间
    int executeTime; // 执行时间
    int startTime; // 开始时间
    int endTime; // 结束时间
};

struct cmp {
    bool operator() (Process a, Process b) {
        return a.executeTime > b.executeTime; // 按照执行时间升序排序
    }
};
priority_queue<Process, vector<Process>, cmp> q; // 进程队列

int main() {
    int n; // 进程数量
    cout << "请输入进程数量：";
    cin >> n;

    vector<Process> processes(n); // 进程数组
    cout << "请输入每个进程的到达时间和执行时间：" << endl;
    for (int i = 0; i < n; i++) {
        processes[i].id = i + 1;
        cin >> processes[i].arriveTime >> processes[i].executeTime;
    }

    sort(processes.begin(), processes.end(), cmp); // 按照执行时间升序排序

    int currentTime = 0; // 当前时间
    for (int i = 0; i < n; i++) {
        // 将所有到达时间小于等于当前时间的进程加入队列
        while (i < n && processes[i].arriveTime <= currentTime) {
            q.push(processes[i]);
            i++;
        }

        if (!q.empty()) {
            Process p = q.top(); // 取出队列头部进程
            q.pop(); // 删除队列头部进程

            p.startTime = currentTime; // 记录开始时间
            p.endTime = currentTime + p.executeTime; // 计算结束时间
            currentTime = p.endTime; // 更新当前时间

            cout << "进程" << p.id << "在时间" << p.startTime << "开始执行，" << "在时间" << p.endTime << "结束执行。" << endl;
        } else {
            currentTime = processes[i].arriveTime; // 更新当前时间为下一个进程的到达时间
            i--; // 下一轮循环要重新判断当前进程是否可以加入队列
        }
    }

    return 0;
}

3. 时间片轮转（RR）
时间片轮转是指将所有进程按照到达时间顺序加入队列，然后每个进程执行一个时间片（通常为10ms），如果该进程还有剩余执行时间，则将其放回队列尾部等待下一次调度。实现该算法的主要思路是维护一个进程队列，按照到达时间顺序加入队列，然后轮流执行每个进程。

实现过程中，需要定义一个进程结构体，包含进程的ID、到达时间、执行时间、开始时间、结束时间和剩余执行时间等属性。进程队列可以使用STL中的队列容器实现。具体代码如下：

struct Process {
    int id; // 进程ID
    int arriveTime; // 到达时间
    int executeTime; // 执行时间
    int startTime; // 开始时间
    int endTime; // 结束时间
    int remainTime; // 剩余执行时间
};
queue<Process> q; // 进程队列

对于每个新到达的进程，可以使用以下代码将其加入进程队列：

Process p;
// 初始化进程属性
q.push(p); // 加入队列尾部

每次从队列头部取出一个进程执行一个时间片，如果该进程还有剩余执行时间，则将其放回队列尾部等待下一次调度，可以使用以下代码实现：

Process p = q.front(); // 取出队列头部进程
q.pop(); // 删除队列头部进程
p.remainTime -= timeSlice; // 执行一个时间片
if (p.remainTime <= 0) {
    p.endTime = currentTime + timeSlice + p.remainTime; // 计算结束时间
} else {
    q.push(p); // 放回队列尾部
}

完整的时间片轮转算法实现代码如下：

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

struct Process {
    int id; // 进程ID
    int arriveTime; // 到达时间
    int executeTime; // 执行时间
    int startTime; // 开始时间
    int endTime; // 结束时间
    int remainTime; // 剩余执行时间
};
queue<Process> q; // 进程队列

bool cmp(Process a, Process b) {
    return a.arriveTime < b.arriveTime; // 按照到达时间升序排序
}

int main() {
    int n; // 进程数量
    cout << "请输入进程数量：";
    cin >> n;

    vector<Process> processes(n); // 进程数组
    cout << "请输入每个进程的到达时间和执行时间：" << endl;
    for (int i = 0; i < n; i++) {
        processes[i].id = i + 1;
        cin >> processes[i].arriveTime >> processes[i].executeTime;
        processes[i].remainTime = processes[i].executeTime; // 初始化剩余执行时间
    }

    sort(processes.begin(), processes.end(), cmp); // 按照到达时间升序排序

    int timeSlice; // 时间片长度
    cout << "请输入时间片长度：";
    cin >> timeSlice;

    int currentTime = 0; // 当前时间
    while (!q.empty() || processes.size() > 0) {
        // 将所有到达时间小于等于当前时间的进程加入队列
        while (processes.size() > 0 && processes[0].arriveTime <= currentTime) {
            q.push(processes[0]);
            processes.erase(processes.begin());
        }

        if (!q.empty()) {
            Process p = q.front(); // 取出队列头部进程
            q.pop(); // 删除队列头部进程

            p.startTime = currentTime; // 记录开始时间
            p.remainTime -= timeSlice; // 执行一个时间片
            if (p.remainTime <= 0) {
                p.endTime = currentTime + timeSlice + p.remainTime; // 计算结束时间
            } else {
                q.push(p); // 放回队列尾部
            }

            currentTime += timeSlice; // 更新当前时间

            cout << "进程" << p.id << "在时间" << p.startTime << "开始执行，" << "在时间" << p.endTime << "结束执行。" << endl;
        } else {
            currentTime = processes[0].arriveTime; // 更新当前时间为下一个进程的到达时间
        }
    }

    return 0;
}

实验结果：
为了方便演示，我们假设有5个进程，它们的到达时间和执行时间分别为：

进程1：0 10
进程2：2 5
进程3：4 7
进程4：6 3
进程5：8 6

以下是三种调度算法的模拟结果：

先来先服务（FCFS）：

请输入进程数量：5
请输入每个进程的到达时间和执行时间：
0 10
2 5
4 7
6 3
8 6
进程1在时间0开始执行，在时间10结束执行。
进程2在时间10开始执行，在时间15结束执行。
进程3在时间15开始执行，在时间22结束执行。
进程4在时间22开始执行，在时间25结束执行。
进程5在时间25开始执行，在时间31结束执行。

最短作业优先（SJF）：

请输入进程数量：5
请输入每个进程的到达时间和执行时间：
0 10
2 5
4 7
6 3
8 6
进程1在时间0开始执行，在时间10结束执行。
进程4在时间10开始执行，在时间13结束执行。
进程2在时间13开始执行，在时间18结束执行。
进程3在时间18开始执行，在时间25结束执行。
进程5在时间25开始执行，在时间31结束执行。

时间片轮转（RR）：

请输入进程数量：5
请输入每个进程的到达时间和执行时间：
0 10
2 5
4 7
6 3
8 6
请输入时间片长度：3
进程1在时间0开始执行，在时间3结束执行。
进程2在时间3开始执行，在时间6结束执行。
进程3在时间6开始执行，在时间9结束执行。
进程4在时间9开始执行，在时间12结束执行。
进程5在时间12开始执行，在时间16结束执行。
进程1在时间16开始执行，在时间19结束执行。
进程3在时间19开始执行，在时间22结束执行。
进程5在时间22开始执行，在时间25结束执行。
进程1在时间25开始执行，在时间28结束执行。
进程5在时间28开始执行，在时间31结束执行。

可以看到，三种调度算法产生的结果不同，但都能正确地完成进程调度。其中，最短作业优先算法在本例中获得了最短的平均等待时间和平均周转时间，同时也是最优的算法。