进程调度算法模拟

1、绪论

1.1 了解进程调度算法的特点

1.2 熟悉进程结构体数组。

1.3 掌握进程调度算法：时间片轮转法（RR）、短进程优先法（SJF）

---

2、实验内容

2.1 设计C语言程序，模拟实现进程调度算法

2.1.1 时间片轮转法（RR）

将所有的就绪进程按先来先服务的原则排成一个队列，每次调度时，把处理机分配给队首进程，并令其执行一个时间片。

2.1.2 短进程优先法（SJF）

以进入系统的作业所要求的CPU运行时间的长短为挑选依据，优先选取预计所需服务时间最短的作业进行调度，可以分别用于高级调度和低级调度。

---

3、实验步骤

3.1 环境配置

3.1.1 下载安装开发Visual Studio Code，下载地址https://code.visualstudio.com/，安装中文扩展、C/C++扩展

 

3.1.2 安装MinGW，下载地址：https://sourceforge.net/projects/mingw-w64/files/mingw-w64/，配置好环境变量，然后验证

3.1.3 Visual Studio Code中C++配置

3.1.3.1 新增launch.josn增加如下配置，你的路径（D:\\tools\\MinGW64\\bin）取决于MinGW解压目录

{
    "version": "0.2.0",
    "configurations": [
        {
            "name": "g++.exe",
            "type": "cppdbg",
            "request": "launch",
            "program": "${workspaceFolder}\\${fileBasenameNoExtension}.exe",
            "args": [],
            "stopAtEntry": false,
            "cwd": "${workspaceFolder}",
            "environment": [],
            "externalConsole": true,
            "MIMode": "gdb",
            "miDebuggerPath": "D:\\tools\\MinGW64\\bin\\gdb.exe",
            "setupCommands": [
                {
                    "description": "为 gdb 启用整齐打印",
                    "text": "-enable-pretty-printing",
                    "ignoreFailures": true
                }
            ],
            "preLaunchTask": "g++"
        }
    ]
}

3.1.3.1 新增launch.josn增加如下配置，你的路径（D:\\tools\\MinGW64\\bin）取决于MinGW解压目录

{
	"version": "2.0.0",
	"tasks": [
		{
			"type": "cppbuild",
			"label": "g++",
			"command": "D:\\tools\\MinGW64\\bin\\g++.exe",
			"args": [
				"-g",
				"${file}",
				"-o",
				"${fileDirname}\\${fileBasenameNoExtension}.exe"
			],
			"options": {
				"cwd": "D:\\tools\\MinGW64\\bin"
			},
			"problemMatcher": [
				"$gcc"
			],
			"group": "build",
			"detail": "compiler: D:\\tools\\MinGW64\\bin\\g++.exe"
		}
	]
}

3.2 源代码

3.2.1 时间片轮转法（RR）

//时间片轮转调度算法
#include <bits/stdc++.h>
#define N 100
#define state int
using namespace std;

//进程结构体
struct PCB
{
    string name;         //进程名称
    int pos;             //进程顺序
    double arrival_t;    //到达的时间
    double start_t;      //开始时间
    double end_t;        //结束时间
    double service_t;    //服务时间
    double around_t;     //周转时间
    double val_around_t; //带权周转时间
    double service_tt;   //备份服务时间
} pcb[N];

int num, TIME;
double cur_t = 0;
queue<PCB> q; //普通队列

//比较到达的时间
bool cmp(PCB a, PCB b)
{
    if (a.arrival_t == b.arrival_t)
        return a.service_t < b.service_t;
    return a.arrival_t < b.arrival_t;
}

void init()
{
    cout << "输入时间片大小: ";
    cin >> TIME;
    cout << "输入进程个数: ";
    cin >> num;
    for (int i = 0; i < num; ++i)
    {
        cout << "请输入第" << i + 1 << "个：进程名, 到达时间, 服务时间" << endl;
        cin >> pcb[i].name >> pcb[i].arrival_t >> pcb[i].service_t;
        pcb[i].service_tt = pcb[i].service_t;
        pcb[i].pos = i + 1;
    }
}

//时间轮片调度算法
void rr()
{
    sort(pcb, pcb + num, cmp);
    q.push(pcb[0]);
    int index = 0;
    cur_t = max(pcb[0].arrival_t, cur_t);
    for (int i = 1; i < num; ++i)
    {
        while (!q.empty())
        {
            PCB cnt = q.front();
            q.pop();
            cnt.start_t = cnt.start_t == 0 ? cur_t : cnt.start_t;
            cnt.end_t = cnt.service_t >= TIME ? cur_t + TIME : cur_t + cnt.service_t;
            for (; i < num; ++i)
            {
                if (pcb[i].arrival_t <= cnt.end_t)
                {
                    q.push(pcb[i]);
                }
                else
                    break;
            }
            if (cnt.service_t > TIME)
            {
                cnt.service_t -= TIME;
                q.push(cnt);
                cur_t += TIME;
            }
            else
            {
                cur_t += cnt.service_t;
                pcb[index++] = cnt;
            }
        }
        bool flag = false;
        if (i < num)
        {
            q.push(pcb[i]);
            cur_t = pcb[i].arrival_t;
            flag = true;
        }
        if (!flag)
            break;
    }
}

void output()
{
    cout << "进 程 名" << "\t"
         << "到达时间" << "\t"
         << "开始时间" << "\t"
         << "结束时间" << "\t"
         << "周转时间" << "\t"
         << "带权周转时间"
         << endl;
    for (int i = 0; i < num; ++i)
    {
        pcb[i].around_t = pcb[i].end_t - pcb[i].start_t;
        pcb[i].val_around_t = pcb[i].around_t / pcb[i].service_tt;
        cout << pcb[i].name      << "\t\t"
             << pcb[i].arrival_t << "\t\t"
             << pcb[i].start_t   << "\t\t"
             << pcb[i].end_t     << "\t\t"
             << pcb[i].around_t  << "\t\t"
             << pcb[i].val_around_t
             << endl;
    }
}

int main()
{
    init();
    rr();
    output();
    system("pause");
    return 0;
}

3.2.2 短进程优先法（SJF）

//短进程优先调度算法 (非抢占式)
#include <bits/stdc++.h>
#define TIME 500 //限制最长进程执行时间
#define N 100
#define state int
using namespace std;

//进程结构体
struct PCB
{
    string name;         //进程名称
    int pos;             //进程顺序
    double arrival_t;    //到达的时间
    double start_t;      //开始时间
    double end_t;        //结束时间
    double service_t;    //服务时间
    double around_t;     //周转时间
    double val_around_t; //带权周转时间   周转时间 / 服务时间
    //比较服务时间
    bool operator<(const PCB &a) const
    {
        if (service_t == a.service_t)
            return arrival_t > a.arrival_t;
        return service_t > a.service_t;
    }

} pcb[N];

int num;
double cur_t = 0;
priority_queue<PCB> q;//优先级队列
bool vis[N];

//比较到达的时间
bool cmp(PCB a, PCB b)
{
    if (a.arrival_t == b.arrival_t)
        return a.service_t < b.service_t;
    return a.arrival_t < b.arrival_t;
}

void init()
{
    cout << "输入进程个数: ";
    cin >> num;
    for (int i = 0; i < num; ++i)
    {
        cout << "请输入第" << i + 1 << "个：进程名, 到达时间, 服务时间" << endl;
        cin >> pcb[i].name >> pcb[i].arrival_t >> pcb[i].service_t;
        pcb[i].pos = i + 1;
    }
}

//短进程优先调度算法
void sjf()
{
    sort(pcb, pcb + num, cmp);
    q.push(pcb[0]);
    int index = 0;
    for (int i = 1; i < num; ++i)
    {
        while (!q.empty())
        {
            PCB cnt = q.top();
            q.pop();
            cnt.start_t = max(cur_t, cnt.arrival_t);
            cnt.end_t = cnt.start_t + cnt.service_t;
            cnt.around_t = cnt.end_t - cnt.arrival_t;
            cnt.val_around_t = cnt.around_t / cnt.service_t;
            for (; i < num; ++i)
            {
                if (pcb[i].arrival_t <= cnt.end_t)
                {
                    q.push(pcb[i]);
                }
                else
                {
                    break;
                }
            }
            cur_t = cnt.end_t;
            pcb[index++] = cnt;
        }
        bool flag = false;
        if (i < num)
        {
            q.push(pcb[i]);
            flag = true;
        }
        if (!flag)
            break;
    }
}

void output()
{
    cout << "进 程 名" << "\t"
         << "到达时间" << "\t"
         << "开始时间" << "\t"
         << "结束时间"
         << endl;
    for (int i = 0; i < num; ++i)
    {
        cout << pcb[i].name      << "\t\t"
             << pcb[i].arrival_t << "\t\t"
             << pcb[i].start_t   << "\t\t"
             << pcb[i].end_t
             << endl;
    }
}

int main()
{
    init();
    sjf();
    output();
    system("pause");
    return 0;
}

3.3 编译代码

3.3.1 手动点（如下图），或者按F5

---

4、实验结果

4.1 时间片轮转法，运行结果如下

4.2 短进程优先法，运行结果如下

---

5、小结与体会

比如C++环境，VS Code咋用啥的，进程调度算法啥的，自己YY了！！！