C.进程调度实例讲解
C.进程调度
Time Limit: 1000 MS | Memory Limit: 65536 KB |
Total Submissions: 270 | Accepted: 66 |
Description
操作系统的一个重要功能是进行进程调度,其进程调度的算法有多种,其中最简单的调度算法是先来先服务(FCFS)算法。该算法的思想是:先进入就绪队列的先执行,后进入就绪队列的后执行,同一时刻进入就绪队列的执行时间少的先执行。我们认为某一进程一旦开始执行,就一直占用处理机,直到执行结束。而一旦处理机被其它进程占用,就绪队列中的进程就必须等待。当某一进程执行结束后,队列中排在最前面的进程就会立即执行。一个进程从进入就绪队列到执行完毕所用的时间为其周转时间,即周转时间=等待时间+执行时间。现在给你若干进程到达就绪队列的时间以及每个队列的执行时间,请编程计算这些进程的平均周转时间。
Input
多组测试数据。
每组测试数据的第一行为一个正整数N(N<=1000),表示要处理的进程数目。
接下来有N行,每行有两个正整数Ai(Ai<=1000)和Ei(Ei<=1000),分别表示一个进程到达就绪队列的时刻和执行该进程所需的时间。
Output
对于每组测试数据,输出平均周转时间,结果保留4位小数。
每组输出占一行。
Sample Input
4
11
33
22
44
Sample Output
3.5000
Hint
进程1等待时间为0,执行时间为1,其周转时间为0+1=1;
进程3等待时间为0,执行时间为2,其周转时间为0+2=2;
进程2等待时间为1,执行时间为3,其周转时间为1+3=4;
进程4等待时间为3,执行时间为4,其周转时间为3+4=7;
故平均周转时间=(1+2+4+7)/4=3.5000。
Source
2013 Anhui College Student Programming Contest--ahfywff
# include <stdio.h> # define M 1000 # define N 2 void Dsort(intint *tree[],int n); int A[M][N],*P[M]; int main() { int n,i,time0=0,time1=0,sum; //freopen("AAA.txt","r",stdin); while(~scanf("%d",&n)) { for(i=0;i<n;P[i]=A[i],i++) scanf("%d %d",&A[i][0],&A[i][1]); Dsort(P,n); time1=P[0][0]+P[0][1]; time0=0; sum=P[0][1]; //printf("%d %d %lld\n",time0,time1,sum); for(i=1;i<n;i++) { if(P[i][0]<time1)time0=time1-P[i][0]; else { time0=0;//time0=当前进程-时间点=等待时间 time1=P[i][0]; } time1+=P[i][1];//当前进程结束后的时间点 sum+=time0+P[i][1]; //printf("%d %d %lld\n",time0,time1,sum); } printf("%.4lf\n",sum*1.0/n); } return 0; } void Dsort(intint *tree[],int n) { int i,j=0,k,L,*R; tree--; while((i=++j)<=n) { R=tree[i]; while(i>1) { L=(i>>1); for(k=0; k<N&&tree[L][k]==R[k]; k++); if(tree[L][k]>=R[k]) break; tree[i]=tree[L]; i=L; } tree[i]=R; } while(n) { R=tree[n]; tree[n--]=tree[1]; i=1; L=2; while(L<=n) { if(L<n) { for(k=0; k<N&&tree[L+1][k]==tree[L][k]; k++); if(tree[L+1][k]>tree[L][k])L++; } for(k=0; k<N&&tree[L][k]==R[k]; k++); if(tree[L][k]<=R[k]) break; tree[i]=tree[L]; i=L; L<<=1; } tree[i]=R; } tree++; }
上一篇: Object-C,NumberDemo和StringDemo
下一篇: 一种C语言"打桩"的源码实现