• 操作系统第一次实验——短作业优先调度算法（SJF）

    一、实验目的：

    目的：了解并掌握作业调度的功能，熟悉并掌握各种作业调度算法。

    任务：模拟实现先来先服务或者短作业优先调度算法。

    二、实验内容：

    1、实验内容

    模拟实现SJF调度。

    设置作业体：作业名，作业的到达时间，服务时间，作业状态（W——等待,R——运行,F——完成），作业间的链接指针；

    作业初始化：由用户输入作业名、服务时间、到达时间进行初始化，同时，初始化作业的状态为W。

    显示函数：在作业调度前、调度中和调度后进行显示。

    排序函数：对等待状态的作业按照调度算法排序（不同的调度算法排序方式不同），注意考虑到达时间。

    调度函数：每次从等待队列队首调度已到达的适合的作业执行，状态变化。当服务结束时，状态变为F。

    删除函数：撤销状态为F的作业。

    2、实验要求

    （1）测试数据可以随即输入或从文件中读入；

    （2）必须要考虑到作业的到达时间；

    （3）最终能够计算每一个作业的周转时间、带权周转时间。

    三、实验代码 （C++）

    1、首先定义函数体

    1. struct process
    2. {
    3.     string pid;        //作业名（作业号）
    4.     double come_time;  //到达时
    5.     double run_time;   //运行时
    6.     double begin_time; //开始时
    7.     double over_time;  //完成时
    8.     double round_time; //周转时
    9.     double avg_time;   //带权周转时
    10.     double HRR;        //响应比
    11.     char state;		   // 状态 
    12. 	double need_time;  // 所剩余需要服务的时间 
    13. } pc[MAXSIZE];         //作业数

    2、定义完函数体后，对进程进行排序算法。

    1. bool CmpByComeTime(process p1, process p2) // 按到达时间正序排序
    2. {
    3.     return p1.come_time < p2.come_time;
    4. }
    5. bool CmpByPid(process p1, process p2) // 按id号正序排序
    6. {
    7.     return p1.pid < p2.pid;
    8. }
    9. bool CmpByRunTime(process p1, process p2) // 按运行时长正序排序
    10. {
    11.     return p1.run_time == p2.run_time ? p1.come_time < p2.come_time : p1.run_time < p2.run_time;
    12. }

     3、写完排序函数后，计算进程的开始时间与到达时间

    1. void get_beginAndOver_time() // 计算作业的开始时间与完成时间
    2. {
    3.     for (int i = 0; i < number; i++)
    4.     {
    5.         if (i == 0)
    6.         {
    7.             pc[i].begin_time = pc[i].come_time; // 第一个作业的开始时即为其到达时
    8.         }
    9.         else
    10.         {
    11.             pc[i].begin_time = pc[i - 1].over_time; // 否则后一作业的开始时为前一个作业的完成时
    12.         }
    13.         pc[i].over_time = pc[i].begin_time + pc[i].run_time; // 作业完成时 = 开始时间 + 运行时间
    14.     }
    15. }

    4、进行对周转时间，带权周转时间的计算

    1. 完成时间=开始时间+服务时间
    2. 周转时间=完成时间-到达时间
    3. 带权周转时间=周转时间/服务时间
    1. void get_roundAndAvg_time() // 计算作业的周转时间与带权周转时间
    2. {
    3.     for (int i = 0; i < number; ++i)
    4.     {
    5.         pc[i].round_time = pc[i].over_time - pc[i].come_time;     // 周转时 = 完成时间 - 到达时间
    6.         pc[i].avg_time = pc[i].round_time * 1.0 / pc[i].run_time; // 平均周转时 = 周转时间 / 运行时间
    7.     }
    8. }

     5、计算完成后，写SJF的函数体

    1. void SJF() // SJF（short job first）：根据作业的运行时间从小到大依次执行
    2. {
    3.     sort(pc, pc + number, CmpByComeTime);    // 先按到达时排序
    4.     sort(pc + 1, pc + number, CmpByRunTime); // 再按运行时排序
    5.     get_beginAndOver_time();
    6.     get_roundAndAvg_time();
    7. }

    四、实验结果 

    如图

     

    五、完整代码

    1. #include 
    2. #include 
    3. using namespace std;
    4. #define MAXSIZE 5 // 作业数
    5. int number; // 用户输入的进程数量
    6. struct process
    7. {
    8.     string pid;        //作业名（作业号）
    9.     double come_time;  //到达时
    10.     double run_time;   //运行时
    11.     double begin_time; //开始时
    12.     double over_time;  //完成时
    13.     double round_time; //周转时
    14.     double avg_time;   //带权周转时
    15.     double HRR;        //响应比
    16.     char state;		   // 状态 
    17. 	double need_time;  // 所剩余需要服务的时间 
    18. } pc[MAXSIZE];         //作业数
    19. bool CmpByComeTime(process p1, process p2) // 按到达时间正序排序
    20. {
    21.     return p1.come_time < p2.come_time;
    22. }
    23. bool CmpByPid(process p1, process p2) // 按id号正序排序
    24. {
    25.     return p1.pid < p2.pid;
    26. }
    27. bool CmpByRunTime(process p1, process p2) // 按运行时长正序排序
    28. {
    29.     return p1.run_time == p2.run_time ? p1.come_time < p2.come_time : p1.run_time < p2.run_time;
    30. }
    31.  
    32. void get_beginAndOver_time() // 计算作业的开始时间与完成时间
    33. {
    34.     for (int i = 0; i < number; i++)
    35.     {
    36.         if (i == 0)
    37.         {
    38.             pc[i].begin_time = pc[i].come_time; // 第一个作业的开始时即为其到达时
    39.         }
    40.         else
    41.         {
    42.             pc[i].begin_time = pc[i - 1].over_time; // 否则后一作业的开始时为前一个作业的完成时
    43.         }
    44.         pc[i].over_time = pc[i].begin_time + pc[i].run_time; // 作业完成时 = 开始时间 + 运行时间
    45.     }
    46. }
    47. void get_roundAndAvg_time() // 计算作业的周转时间与带权周转时间
    48. {
    49.     for (int i = 0; i < number; ++i)
    50.     {
    51.         pc[i].round_time = pc[i].over_time - pc[i].come_time;     // 周转时 = 完成时间 - 到达时间
    52.         pc[i].avg_time = pc[i].round_time * 1.0 / pc[i].run_time; // 平均周转时 = 周转时间 / 运行时间
    53.     }
    54. }
    55.  
    56. void SJF() // SJF（short job first）：根据作业的运行时间从小到大依次执行
    57. {
    58.     sort(pc, pc + number, CmpByComeTime);    // 先按到达时排序
    59.     sort(pc + 1, pc + number, CmpByRunTime); // 再按运行时排序
    60.     get_beginAndOver_time();
    61.     get_roundAndAvg_time();
    62. }
    63.  
    64. void qianprint()
    65. {
    66. 	cout << endl;
    67.     cout << "作业名" << '\t' << "到达时" << '\t' << "运行时" << '\t'
    68. 	         << "开始时" << '\t' << "完成时" << '\t' << "状态" << '\t'
    69. 	         << endl;
    70.     for (int i = 0; i < number; ++i)
    71.     {
    72.         /* code */
    73. //		sum_round_time = pc[i].over_time;
    74. 		pc[i].state='W';
    75. 	}
    76.     for (int i = 0; i < number; ++i)
    77.     {
    78.  
    79.         cout << pc[i].pid << '\t' << pc[i].come_time << '\t'
    80. 	             << pc[i].run_time << '\t' << pc[i].begin_time << '\t'
    81. 	             << pc[i].over_time << '\t' << pc[i].state<<'\t' << endl;
    82.     }
    83. }
    84. void printProcess() // 打印作业的过程 
    85. {
    86. 	double atime=1;
    87. 	double sum_round_time = 0.0;
    88. 	for (int i = 0; i < number; ++i)
    89.     {
    90.         /* code */
    91. 		sum_round_time = pc[i].over_time;
    92. 		pc[i].state='W';
    93. 	}
    94. //	cout<
    95. 	for (atime;atime<=sum_round_time;++atime){
    96. 		cout<<'\t'<
    97. 		cout << "第"<"个时间周期" <<'\t'<< endl;
    98. 		cout << endl;
    99. 	    cout << "作业名" << '\t' << "到达时" << '\t' << "运行时" << '\t'
    100. 	         << "开始时" << '\t' << "需要时" << '\t' << "状态" << '\t'
    101. 	         << endl;
    102. 	    for (int i = 0; i < atime&&i
    103.     	{
    104.     		for (int j = 0; j < number; ++j)
    105.     		{
    106.     			
    107. 		        if (atime==pc[j].come_time&&(pc[j-1].state=='\0'||pc[j-1].state=='F'))
    108. 				{
    109. 					pc[j].state='R';
    110. 				}
    111. 				else if(atime>=pc[j].over_time){
    112. 					pc[j].state='F';
    113. 					pc[j+1].state='R';
    114. 				}
    115. 			}
    116. 		pc[i].need_time=pc[i].over_time-atime;
    117. 		if(pc[i].need_time>=0)
    118. 		{
    119. 			pc[i].need_time=pc[i].need_time;
    120. 			
    121. 		}
    122. 		else
    123. 		{
    124. 			pc[i].need_time=0;
    125. 		}
    126. 		if(atime>=pc[i].come_time){
    127. 			 cout << pc[i].pid << '\t' << pc[i].come_time << '\t'
    128. 	             << pc[i].run_time << '\t' << pc[i].begin_time << '\t'
    129. 	             << pc[i].need_time << '\t' << pc[i].state<<'\t' << endl;
    130. 		} 
    131.     	}     
    132.     }
    133.         
    134.     
    135. }
    136.  
    137. void printResult() // 打印输出作业的各个时间值
    138. {
    139.     cout << "执行顺序："; // << endl
    140.     for (int i = 0; i < number; ++i)
    141.     {
    142.         /* code */
    143.         cout << pc[i].pid<< " ";
    144.         
    145.     }
    146.     cout << endl;
    147.     cout << "作业名" << '\t' << "到达时" << '\t' << "运行时" << '\t'
    148.          << "开始时" << '\t' << "完成时" << '\t' << "周转时" << '\t'
    149.          << "带权周转时" << '\t' << endl;
    150.     sort(pc, pc + number, CmpByPid);
    151.     double sum_round_time = 0.0;
    152.     double avg_sum_round_time = 0.0; // 平均周转时间
    153.     double sum_avg_time = 0.0;
    154.     double avg_sum_avg_time = 0.0; // 平均带权周转时间
    155.     for (int i = 0; i < number; ++i)
    156.     {
    157.         sum_round_time += pc[i].round_time;
    158.         sum_avg_time += pc[i].avg_time;
    159.         cout << pc[i].pid << '\t' << pc[i].come_time << '\t'
    160.              << pc[i].run_time << '\t' << pc[i].begin_time << '\t'
    161.              << pc[i].over_time << '\t' << pc[i].round_time << '\t'
    162.              << pc[i].avg_time << endl;
    163.     }
    164.     avg_sum_round_time = sum_round_time * 1.0 / number;
    165.     avg_sum_avg_time = sum_avg_time * 1.0 / number;
    166.     cout << "平均周转时间: " << avg_sum_round_time << endl
    167.          << "平均带权周转时间: " << avg_sum_avg_time << endl;
    168. }
    169. int main() // 入口函数
    170. {
    171. 	int atime=1;
    172.     cout << "请输入进程个数：";
    173.     cin >> number;
    174.     cout << endl;
    175.     cout << "请分别输入进程的名称、到达时间、服务时间：" << endl;
    176.     for (int i = 0; i < number; i++)
    177.     {
    178.         cin >> pc[i].pid >> pc[i].come_time >> pc[i].run_time;
    179.     }
    180.     cout << endl;
    181.     SJF();
    182.     cout << "运行前的任务：" <<'\t'<< endl;
    183.     qianprint();
    184.     cout << "运行中的任务调度过程：" <<'\t'<< endl;
    185.     printProcess();
    186.     cout << "the results of SJF are：" << endl;
    187. 	printResult();
    188.     
    189.     system("pause");
    190.     return 0;
    191. }

  • 相关阅读:
    智慧工地综合管理平台-环境监测子系统集成部署方案
    LCR 012.寻找数组的中心下标
    Vue+Vux引入国际化
    Maven 基础教程系列
    PMO制定的流程机制如何落地实施？
    艾美捷PEG化蛋白ELISA试剂盒—高度灵敏度，高通量格式！
    数据结构与算法
    Java端集成drools6.4.0.Final
    AI网络爬虫：用GraphQL查询爬取动态网页数据
    Java 封装通用 web 服务端响应客户端数据的结果类
  • 原文地址：https://blog.csdn.net/qq_61897141/article/details/134338114