进程调度

Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/65536K (Java/Other)

Total Submission(s) : 103 Accepted Submission(s) : 41

Font: Times New Roman | Verdana | Georgia

Font Size: ← →

Problem Description

　　下面考虑单处理机的先进先出(FIFO)进程调度算法。
　　所谓进程调度就是指操作系统按照某种算法把处理机动态地分配给某一就绪进程（仅差处理机就可进行的进程）。其中，FIFO算法是最简单、最直接的进程调度算法之一。其原则就是：先进入就绪队列的先执行，后进入就绪队列的后执行，再不考虑其他情况的前提下，这里认为某进程一旦开始执行，就一直占用处理机，直到执行结束。一个进程从进入就绪队列到执行完毕所用的时间为其周转时间。现在有若干个进程在不同时间到达就绪队列，请你编程序计算：对于FIFO算法的平均周转时间。
　　例如：有四个进程A、B、C、D依次在1.0,3.0,5.0,7.5时刻到达就绪队列，运行所需时间依次为1.5,3.0,5.0,2.0。则以FIFO算法进行调度的过程可描述如下：
　　时刻  进程A  进程B  进程C  进程D
　　1.0  执行  未  未  未
　　2.5  结束  未  未  未
　　3.0  结束  执行  未  未
　　5.0  结束  执行  就绪  未
　　6.0  结束  结束  执行  未
　　7.5  结束  结束  执行  就绪
　　11.0  结束  结束  结束  执行
　　13.0  结束  结束  结束  结束
　　易求得平均周转时间为：[(2.5-1.0)+(6.0-3.0)+(11.0-5.0)+(13.0-7.5)]/4=4.0

Input

　　输入数据的第一行为一个正整数N(1≤N≤100)，表示要处理的进程数目。
　　接下来的N行每行用于描述一个进程；
　　每行包含两个实数A_i,T_i(0.0＜A_i,T_i≤10000.0,小数点后保留4位)，分别表示i(i=1,2,...,N)号进程到达就绪队列的时刻和执行所需时间。
　　注意：输入数据不一定按到达时间的顺序给出。

Output

　　输出数据为一个实数，表示平均周转时间。结果保留4位小数，若末尾有零须保留，不考虑四舍五入的情况。你可以在prinf()函数中使用"%.4f"格式控制串。

Sample Input

4
1.0652 1.5055
7.5001 2.0082
3.1522 3.1221
5.7805 5.0200

Sample Output

3.9860

Author

河北大学算法艺术协会

Source

2010年河北大学程序设计竞赛

Statistic | Submit | Back