2697: 【操作系统】实验二 - 先来先服务(FCFS)算法
金币值：10
定数：8
时间限制：1.000 s
内存限制：128 M
正确：7
提交：9
正确率：77.78% 命题人：
题目描述
实验目标
设计一个按先来先服务 $(FCFS)$ 调度算法实现处理机调度的程序。
一、算法思想
先来先服务（$First-Come$, $First-Served$, $FCFS$）调度算法是一种最简单的调度算法，其核心思想是按照进程到达就绪队列的先后顺序进行调度。具体来说，进程按照到达时间的先后排序，调度程序总是选择队列中第一个到达的进程，为其分配处理机资源，使其执行直到完成或阻塞。该算法不考虑进程的 $CPU$ 执行时间、优先级等因素，完全遵循 “先来后到” 的公平原则。在单处理机环境下，一旦某个进程开始执行，就会一直运行到结束或被阻塞，不会被其他进程抢占。二、算法实现
以下是本次实验用到的公式:$1$. 周转时间 $=$ 完成时间 $-$ 到达时间
$2$. 平均周转时间：周转时间 $/$ 进程数
$3$. 带权周转时间：周转时间 $/$ 服务时间
$4$. 平均带权周转时间：带权周转时间 $/$ 进程数
计算方法:
$1$.找出最先到达的进程(该进程的完成时间 $=$ 到达时间 $+$ 服务时间)$2$.根据给出的到达时间，找出下一个到达的进程(该进程的完成时间 $=$ 上一进程的完成时间 $+$ 该进程的服务时间)；
$3$.重复 $2$ 直至完成所有进程的计算；
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$。
输入样例 复制
3
1 0 5
2 1 2
3 2 3输出样例 复制
请输入进程个数：请输入各进程的信息（格式：作业名 到达时间 服务时间）：
名称 到达 开始 服务 完成 周转 带权
1 0.0 0.0 5.0 5.0 5.0 1.000000
2 1.0 5.0 2.0 7.0 6.0 3.000000
3 2.0 7.0 3.0 10.0 8.0 2.666667
平均周转时间：6.33
平均带权周转时间：2.222提示
温馨提示
你的运行窗口的运行信息依照样例数据应该是这样的，不必查看样例输入输出的内容:请输入进程个数：3 请输入各进程的信息（格式：作业名 到达时间 服务时间）： 1 0 5 2 1 2 3 2 3 名称 到达 开始 服务 完成 周转 带权 1 0.0 0.0 5.0 5.0 5.0 1.000000 2 1.0 5.0 2.0 7.0 6.0 3.000000 3 2.0 7.0 3.0 10.0 8.0 2.666667 平均周转时间：6.33 平均带权周转时间：2.222
对样例的解释
对于这 $3$ 个进程，时间点从 $0$ 开始计时，根据 $FCFS$ 算法优先处理先到达的进程可知，进程处理的顺序为 $ 1,2,3。$$0$ 时刻 $1$ 进程到达，优先处理。服务时间为 $5$ 个时间点，所以完成时间为 $0 + 5 = 5$。周转时间 $=$ 完成时间 $-$ 到达时间，即 $5 - 0 = 5$。带权周转时间为 周转时间 $/$ 服务时间，即 $5 / 5 = 1$。
当时间来到 $5$ 时，此时 $2$ 和 $3$ 进程都到达，$2$ 进程完成时间为 $5 + 2 = 7$，周转时间为 $7 - 1 = 6$，带权周转时间为 $6 / 2 = 3$。
当时间来到 $7$ 时，此时 $3$ 进程到达，进程完成时间为 $10$，周转时间为 $8$，带权周转时间为 $\frac{8}{3}$。
平均周转时间为 $\frac{5+6+8}{3} = \frac{19}{3}$,平均带权周转时间为 $\frac{1+3+\frac{8}{3}}{3} = \frac{20}{9}$。