操作系统实验1【短作业优先调度算法（C++代码实现——FCFS\SJF\HRRN）】

Dear 丶 2023-01-17 09:28 114阅读 0赞

> 1.  [操作系统 实验1【短作业优先调度算法（C++实现——FCFS\\SJF\\HRRN）】][_1_C_FCFS_SJF_HRRN]
> 2.  [操作系统 实验2【动态高优先权优先调度算法 C++实现】][_2_ C]
> 3.  [操作系统 实验3【动态分区存储管理 Python实现】][_3_ Python]
> 4.  [操作系统 实验4【基本分页存储管理 C++实现】][_4_ C]

**目录**

一、实验目的（目的与任务）

二、实验内容（内容、要求与安排方式）

三、实验代码

①首先需要定义一个作业结构体

②编写排序算法

③计算作业的各个时间值

④FCFS与SJF的具体实现

⑤编写函数，打印输出作业的各个时间值

完整实验代码

将程序打包为exe文件

四、实验结果

测试样例1

测试样例2

五、实验总结

--------------------

# 一、实验目的（目的与任务） #

> 目的：了解并掌握作业调度的功能，熟悉并掌握各种作业调度算法。
> 
> 任务：模拟实现先来先服务调度算法（FCFS）或者短作业优先调度算法（SJF）。

# 二、实验内容（内容、要求与安排方式） #

> 实验学时：2            实验类型：综合型
> 
> **1．实验内容与要求：**
> 
> （1）实验内容
> 
> 模拟实现SJF调度。
> 
> 设置作业体：作业名，作业的到达时间，服务时间，作业状态（W——等待,R——运行,F——完成），作业间的链接指针；
> 
> 作业初始化：由用户输入作业名、服务时间、到达时间进行初始化，同时，初始化作业的状态为W。
> 
> 显示函数：在作业调度前、调度中和调度后进行显示。
> 
> 排序函数：对等待状态的作业按照调度算法排序（不同的调度算法排序方式不同），注意考虑到达时间。
> 
> 调度函数：每次从等待队列队首调度已到达的适合的作业执行，状态变化。当服务结束时，状态变为F。
> 
> 删除函数：撤销状态为F的作业。
> 
> （2）实验要求
> 
> ①测试数据可以随即输入或从文件中读入；
> 
> ②必须要考虑到作业的到达时间；
> 
> ③最终能够计算每一个作业的周转时间、带权周转时间。
> 
> **2．实验安排方式：**
> 
> 上机。
> 
> **3．实验设备**
> 
> 1．所用设备：装有C/C++/JAVA等编程环境的计算机。
> 
> 2．消耗性器材：无。

# 三、实验代码 #

> ![在这里插入图片描述][20201122102523411.png]

### ①首先需要定义一个作业结构体 ###

> struct process
> 
> \{ 
> 
>     string pid;         //作业名（作业号）
> 
>     double come\_time;  //到达时
> 
>     double run\_time;   //运行时
> 
>     double begin\_time; //开始时
> 
>     double over\_time;  //完成时
> 
>     double round\_time; //周转时
> 
>     double avg\_time;   //带权周转时
> 
>     double HRR;        //响应比
> 
> \} pc\[MAXSIZE\];         //作业数

### ②编写排序算法 ###

> bool CmpByComeTime(process p1, process p2) // 按到达时间正序排序
> 
> \{ 
> 
>     return p1.come\_time < p2.come\_time;
> 
> \}
> 
> bool CmpByPid(process p1, process p2) // 按id号正序排序
> 
> \{ 
> 
>     return p1.pid < p2.pid;
> 
> \}
> 
> bool CmpByRunTime(process p1, process p2) // 按运行时长正序排序
> 
> \{ 
> 
>     return p1.run\_time == p2.run\_time ? p1.come\_time < p2.come\_time : p1.run\_time < p2.run\_time;
> 
> \}
> 
> bool CmpByHRR(process p1, process p2) // 按响应比逆序排序
> 
> \{ 
> 
>     return p1.HRR > p2.HRR;
> 
> \}

### ③计算作业的各个时间值 ###

> 1.  完成时间=开始时间+服务时间
> 2.  周转时间=完成时间-到达时间
> 3.  带权周转时间=周转时间/服务时间
> 
> void get\_beginAndOver\_time() // 计算作业的开始时间与完成时间
> 
> \{ 
> 
>     for (int i = 0; i < number; i\++)
> 
>     \{ 
> 
>         if (i == 0)
> 
>         \{ 
> 
>             pc\[i\].begin\_time = pc\[i\].come\_time; // 第一个作业的开始时即为其到达时
> 
>         \}
> 
>         else
> 
>         \{ 
> 
>             pc\[i\].begin\_time = pc\[i - 1\].over\_time; // 否则后一作业的开始时为前一个作业的完成时
> 
>         \}
> 
>         pc\[i\].over\_time = pc\[i\].begin\_time + pc\[i\].run\_time; // 作业完成时 = 开始时间 + 运行时间
> 
>     \}
> 
> \}
> 
>  
> 
> void get\_roundAndAvg\_time() // 计算作业的周转时间与带权周转时间
> 
> \{ 
> 
>     for (int i = 0; i < number; ++i)
> 
>     \{ 
> 
>         pc\[i\].round\_time = pc\[i\].over\_time - pc\[i\].come\_time;     // 周转时 = 完成时间 - 到达时间
> 
>         pc\[i\].avg\_time = pc\[i\].round\_time \* 1.0 / pc\[i\].run\_time; // 平均周转时 = 周转时间 / 运行时间
> 
>     \}
> 
> \}

### ④FCFS与SJF的具体实现 ###

> void FCFS()
> 
> \{ 
> 
>     sort(pc, pc + number, CmpByComeTime);
> 
>     get\_beginAndOver\_time();
> 
>     get\_roundAndAvg\_time();
> 
> \}
> 
>  
> 
> void SJF()
> 
> \{ 
> 
>     sort(pc, pc + number, CmpByComeTime);    // 先按到达时排序
> 
>     sort(pc + 1, pc + number, CmpByRunTime); // 再按运行时排序
> 
>     get\_beginAndOver\_time();
> 
>     get\_roundAndAvg\_time();
> 
> \}

### ⑤编写函数，打印输出作业的各个时间值 ###

> void printResult() // 打印输出作业的各个时间值
> 
> \{ 
> 
>     cout << "执行顺序："; // << endl
> 
>     for (int i = 0; i < number; ++i)
> 
>     \{ 
> 
>         /\* code \*/
> 
>         cout << pc\[i\].pid << " ";
> 
>     \}
> 
>     cout << endl;
> 
>     cout << "作业名" << '\\t' << "到达时" << '\\t' << "运行时" << '\\t'
> 
>          << "开始时" << '\\t' << "完成时" << '\\t' << "周转时" << '\\t'
> 
>          << "带权周转时" << '\\t' << endl;
> 
>     sort(pc, pc + number, CmpByPid);
> 
>     double sum\_round\_time = 0.0;
> 
>     double avg\_sum\_round\_time = 0.0;
> 
>     double sum\_avg\_time = 0.0;
> 
>     double avg\_sum\_avg\_time = 0.0;
> 
>     for (int i = 0; i < number; ++i)
> 
>     \{ 
> 
>         sum\_round\_time += pc\[i\].round\_time;
> 
>         sum\_avg\_time += pc\[i\].avg\_time;
> 
>         cout << pc\[i\].pid << '\\t' << pc\[i\].come\_time << '\\t'
> 
>              << pc\[i\].run\_time << '\\t' << pc\[i\].begin\_time << '\\t'
> 
>              << pc\[i\].over\_time << '\\t' << pc\[i\].round\_time << '\\t'
> 
>              << pc\[i\].avg\_time << endl;
> 
>     \}
> 
>     avg\_sum\_round\_time = sum\_round\_time \* 1.0 / number;
> 
>     avg\_sum\_avg\_time = sum\_avg\_time \* 1.0 / number;
> 
>     cout << "平均周转时间: " << avg\_sum\_round\_time << endl
> 
>          << "平均带权周转时间: " << avg\_sum\_avg\_time << endl;
> 
> \}

## 完整实验代码 ##

#include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    #define MAXSIZE 5 // 作业数
    
    int number; // 用户输入的进程数量
    
    struct process
    {
        string pid;        //作业名（作业号）
        double come_time;  //到达时
        double run_time;   //运行时
        double begin_time; //开始时
        double over_time;  //完成时
        double round_time; //周转时
        double avg_time;   //带权周转时
        double HRR;        //响应比
    } pc[MAXSIZE];         //作业数
    
    bool CmpByComeTime(process p1, process p2) // 按到达时间正序排序
    {
        return p1.come_time < p2.come_time;
    }
    
    bool CmpByPid(process p1, process p2) // 按id号正序排序
    {
        return p1.pid < p2.pid;
    }
    
    bool CmpByRunTime(process p1, process p2) // 按运行时长正序排序
    {
        return p1.run_time == p2.run_time ? p1.come_time < p2.come_time : p1.run_time < p2.run_time;
    }
    
    bool CmpByHRR(process p1, process p2) // 按响应比逆序排序
    {
        return p1.HRR > p2.HRR;
    }
    
    void get_beginAndOver_time() // 计算作业的开始时间与完成时间
    {
        for (int i = 0; i < number; i++)
        {
            if (i == 0)
            {
                pc[i].begin_time = pc[i].come_time; // 第一个作业的开始时即为其到达时
            }
            else
            {
                pc[i].begin_time = pc[i - 1].over_time; // 否则后一作业的开始时为前一个作业的完成时
            }
            pc[i].over_time = pc[i].begin_time + pc[i].run_time; // 作业完成时 = 开始时间 + 运行时间
        }
    }
    
    void get_roundAndAvg_time() // 计算作业的周转时间与带权周转时间
    {
        for (int i = 0; i < number; ++i)
        {
            pc[i].round_time = pc[i].over_time - pc[i].come_time;     // 周转时 = 完成时间 - 到达时间
            pc[i].avg_time = pc[i].round_time * 1.0 / pc[i].run_time; // 平均周转时 = 周转时间 / 运行时间
        }
    }
    
    void get_HRR(int beg) // 计算作业的响应比
    {
        for (int i = beg; i < number; i++)
        {
            pc[i].HRR = (pc[beg - 1].over_time - pc[i].come_time) * 1.0 / pc[i].run_time;
        }
    }
    
    void FCFS() // FCFS（first come first served）：先来先服务，根据到达时间依次执行
    {
        sort(pc, pc + number, CmpByComeTime);
        get_beginAndOver_time();
        get_roundAndAvg_time();
    }
    
    void SJF() // SJF（short job first）：根据作业的运行时间从小到大依次执行
    {
        sort(pc, pc + number, CmpByComeTime);    // 先按到达时排序
        sort(pc + 1, pc + number, CmpByRunTime); // 再按运行时排序
        get_beginAndOver_time();
        get_roundAndAvg_time();
    }
    
    void HRRN() // HRRN（highest response ratio next）：根据响应比从大到小依次执行，响应比动态计算
    {
        sort(pc, pc + number, CmpByComeTime); // 先按到达时排序
        for (int i = 1; i < number; ++i)
        {
            get_HRR(i);
            sort(pc + i, pc + number, CmpByHRR);
        }
        get_beginAndOver_time();
        get_roundAndAvg_time();
    }
    
    void printResult() // 打印输出作业的各个时间值
    {
        cout << "执行顺序："; // << endl
        for (int i = 0; i < number; ++i)
        {
            /* code */
            cout << pc[i].pid << " ";
        }
        cout << endl;
        cout << "作业名" << '\t' << "到达时" << '\t' << "运行时" << '\t'
             << "开始时" << '\t' << "完成时" << '\t' << "周转时" << '\t'
             << "带权周转时" << '\t' << endl;
        sort(pc, pc + number, CmpByPid);
        double sum_round_time = 0.0;
        double avg_sum_round_time = 0.0; // 平均周转时间
        double sum_avg_time = 0.0;
        double avg_sum_avg_time = 0.0; // 平均带权周转时间
        for (int i = 0; i < number; ++i)
        {
            sum_round_time += pc[i].round_time;
            sum_avg_time += pc[i].avg_time;
            cout << pc[i].pid << '\t' << pc[i].come_time << '\t'
                 << pc[i].run_time << '\t' << pc[i].begin_time << '\t'
                 << pc[i].over_time << '\t' << pc[i].round_time << '\t'
                 << pc[i].avg_time << endl;
        }
        avg_sum_round_time = sum_round_time * 1.0 / number;
        avg_sum_avg_time = sum_avg_time * 1.0 / number;
        cout << "平均周转时间: " << avg_sum_round_time << endl
             << "平均带权周转时间: " << avg_sum_avg_time << endl;
    }
    
    int main() // 入口函数
    {
        cout << "请输入进程个数：";
        cin >> number;
    
        cout << endl;
        cout << "请分别输入进程的名称、到达时间、服务时间：" << endl;
        for (int i = 0; i < number; i++)
        {
            cin >> pc[i].pid >> pc[i].come_time >> pc[i].run_time;
        }
    
        cout << endl;
        FCFS();
        cout << "the results of FCFS are：" << endl;
        printResult();
    
        cout << endl;
        SJF();
        cout << "the results of SJF are：" << endl;
        printResult();
    
        cout << endl;
        HRRN();
        cout << "the results of HRRN are：" << endl;
        printResult();
    
        cout << endl;
        system("pause");
        return 0;
    }

## 将程序打包为exe文件 ##

> codeblocks下 写程序，先要建立一个工程。写好程序后，选择Build（构建），在工程目录里面就有个Debug或者Release的文件夹，里面就是打包好的exe文件。
> 
> ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk0OTEzNQ_size_16_color_FFFFFF_t_70][]  ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk0OTEzNQ_size_16_color_FFFFFF_t_70 1][]
> 
> ![20210428211737682.png][]

# 四、实验结果 #

> 输入作业的个数，然后分别输入进程的名称、到达时间、服务时间，对程序进行测试。

## 测试样例1 ##

> ![20210428211239210.png][]

## 测试样例2 ##

> ![20210428212644487.png][]
> 
> ![2021042821272625.png][]

# 五、实验总结 #

> 通过此次实验，对进程的常用算法有了更深的理解，知道了FCFS/SJF进程调度算法的实现过程和程序编写。对作业的完成时间、周转时间、带权周转时间等计算掌握地更加熟练。实验中，将理论和实践相结合，对操作系统的学习更加深入。
> 
> [操作系统实验：FCFS调度算法（C语言）][FCFS_C]

> ![在这里插入图片描述][20191108104815519.png]
> 
> 1.  FCFS（first come first served）：先来先服务，根据到达时间依次执行。
> 2.  SJF（short job first）：根据作业的运行时间从小到大依次执行。
> 3.  HRRN（highest response ratio next）：根据响应比从大到小依次执行，响应比动态计算。

> 周转时间 = 完成时间 - 到达时间
> 
> 带权周转时间 = 周转时间 / 运行时间
> 
> 响应比 = （运行时间+已经等待时间） / 运行时间 = 1+已经等待时间 / 运行时间【响应比可能表达方法不同，但是意义是一样的。】

[_1_C_FCFS_SJF_HRRN]: https://blog.csdn.net/weixin_44949135/article/details/116242551
[_2_ C]: https://blog.csdn.net/weixin_44949135/article/details/116539292
[_3_ Python]: https://blog.csdn.net/weixin_44949135/article/details/116755819
[_4_ C]: https://blog.csdn.net/weixin_44949135/article/details/116850356
[20201122102523411.png]: /images/20221021/a4d28a6a9d9849628f582d2397ac125d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk0OTEzNQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210428211640207.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk0OTEzNQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk0OTEzNQ_size_16_color_FFFFFF_t_70 1]: /images/20221021/b279b3a60490429ba53a63a8bbf6d8c5.png
[20210428211737682.png]: /images/20221021/bdf0e21b93f04b82bc049255ce041d70.png
[20210428211239210.png]: /images/20221021/3ba49da38ed04b959472910bc688754c.png
[20210428212644487.png]: /images/20221021/d2365beebd4c48bebcfda0e3f39cc652.png
[2021042821272625.png]: /images/20221021/c88e71fbc4634ec89f1c9f33fc0a01d4.png
[FCFS_C]: https://blog.csdn.net/weixin_44529350/article/details/109922113
[20191108104815519.png]: /images/20221021/2a466985ae0d42118854039877980519.png