2698: 【操作系统】实验三 - 短作业优先(SJF)算法
金币值：10
定数：9
时间限制：1.000 s
内存限制：128 M
正确：2
提交：3
正确率：66.67% 命题人：
题目描述
实验目标
设计一个按先来先服务 $(SJF)$ 调度算法实现处理机调度的程序。
一、算法思想
短作业优先 ($Shortest$ $Job$ $First$, $SJF$) 调度算法的核心思想是从就绪队列中选择服务时间最短的进程进行调度，以减少进程的平均等待时间和平均周转时间。该算法分为非抢占式和抢占式（最短剩余时间优先，$SRTF$）两种。本次实验实现的是非抢占式 $SJF$ 算法，具体步骤如下：按到达时间排序：首先将所有进程按到达时间从小到大排序，确保在调度时优先考虑已到达的进程。
选择最短作业：在当前进程执行完成后，从所有已到达但未执行的进程中选择服务时间最短的进程，分配处理机资源使其执行直到完成。
迭代调度：重复上述步骤，直到所有进程调度完毕。
该算法的目标是通过优先处理短作业，减少短作业的等待时间，从而优化系统整体效率。
二、算法实现
以下是本次实验用到的公式:$1$. 周转时间 $=$ 完成时间 $-$ 到达时间
$2$. 平均周转时间：周转时间 $/$ 进程数
$3$. 带权周转时间：周转时间 $/$ 服务时间
$4$. 平均带权周转时间：带权周转时间 $/$ 进程数
计算方法:
优先调度执行预计执行时间最短的进程，以减少平均等待时间。
typedef struct job{
char name[200]; //进程名称
double reach_time; //到达时间
double st_time; //开始时间
double serve_time; //服务时间
double run_time; //运行时间
double comp_time; //完成时间
double week_time; //周转时间
double quan_time; //带权周转时间
} ZHT;
测试代码 复制
typedef struct job{
char name[200]; //进程名称
double reach_time; //到达时间
double st_time; //开始时间
double serve_time; //服务时间
double run_time; //运行时间
double comp_time; //完成时间
double week_time; //周转时间
double quan_time; //带权周转时间
} ZHT;输入格式
第一行输入一个整数 $n$，代表进程个数。
从第二行开始的 $n$ 行中，每行输入三个量，分别代表进程名称 $name$、到达时间 $reach\_time$、服务时间 $serve\_time$。
输出格式
详见输出样例和温馨提示部分，除输出某些提示性文字外，还需输出每个进程的所有信息，包括进程名称 $name$、到达时间 $reach\_time$、开始时间 $st\_time$、服务时间 $serve\_time$、完成时间 $comp\_time$、周转时间 $week\_time$、带权周转时间 $quan\_time$ 以及所有进程的平均周转时间 $aver\_week\_time$、平均带权周转时间 $aver\_quan\_time$。
输入样例 复制
4
1 9.0 0.2
2 8.5 0.5
3 8.0 1.0
4 9.1 0.1输出样例 复制
请输入任务总体数量:请输入进程名、到达时间和服务时间，以空格分隔:
进程 到达 服务 开始 完成 周转 带权
3 8.0 1.0 8.0 9.0 1.0 1.0
1 9.0 0.2 9.0 9.2 0.2 1.0
4 9.1 0.1 9.2 9.3 0.2 2.0
2 8.5 0.5 9.3 9.8 1.3 2.6提示
温馨提示
你的运行窗口的运行信息依照样例数据应该是这样的，不必查看样例输入输出的内容:请输入任务总体数量:4 请输入进程名、到达时间和服务时间，以空格分隔: 1 9.0 0.2 2 8.5 0.5 3 8.0 1.0 4 9.1 0.1 进程 到达 服务 开始 完成 周转 带权 3 8.0 1.0 8.0 9.0 1.0 1.0 1 9.0 0.2 9.0 9.2 0.2 1.0 4 9.1 0.1 9.2 9.3 0.2 2.0 2 8.5 0.5 9.3 9.8 1.3 2.6
对样例的解释
计算过程
初始排序：程序会先按服务时间对所有进程进行升序排列：$4(0.1) → 1(0.2) → 2(0.5) → 3(1.0)$
时间线推进：
时间 $= 8.0$：进程 $3$ 最先到达，此时没有其他进程，所以立即开始执行。
完成时间：$8.0 + 1.0 = 9.0$
周转时间：$9.0 - 8.0 = 1.0$
带权周转时间：$1.0 / 1.0 = 1.0$
时间 $= 9.0$：进程 $3$ 执行完毕，此时进程 $1$（到达时间 $9.0$）和进程 $2$（到达时间 $8.5$）都已到达。按照服务时间短优先的原则，选择进程 $1$。
完成时间：$9.0 + 0.2 = 9.2$
周转时间：$9.2 - 9.0 = 0.2$
带权周转时间：$0.2 / 0.2 = 1.0$
时间 = $9.2$：进程 $1$ 执行完毕，此时进程 $2$（到达时间 $8.5$）和进程 $4$（到达时间 $9.1$）都已到达。进程 $4$ 的服务时间更短，所以选择进程 $4$。
完成时间：$9.2 + 0.1 = 9.3$
周转时间：$9.3 - 9.1 = 0.2$
带权周转时间：$0.2 / 0.1 = 2.0$
时间 $= 9.3$：进程 $4$ 执行完毕，此时只剩下进程 $2$（到达时间 $8.5$）。
完成时间：$9.3 + 0.5 = 9.8$
周转时间：$9.8 - 8.5 = 1.3$
带权周转时间：$1.3 / 0.5 = 2.6$
关键细节解释
为何进程 $3$ 最先执行：进程 $3$ 的到达时间最早（$8.0$），在这个时间点没有其他进程可供选择，所以它会优先执行。
为何进程 $2$ 最后执行：
尽管进程 $2$ 的到达时间是 $8.5$，早于进程 $1$（到达时间 $9.0$），但进程 $1$ 的服务时间更短（$0.2 < 0.5$）。根据 $SJF$ 算法，短作业会优先执行，所以进程 $1$ 会在进程 $2$ 之前执行。
为何进程 $4$ 在进程 $2$ 之前执行：
当时间到达 $9.2$ 时，进程 $2$ 和进程 $4$ 都处于等待状态。进程 $4$ 的服务时间（$0.1$）比进程 $2$（$0.5$）更短，所以进程 $4$ 会优先执行。