首页 > 代码库 > 短作业优先调度算法(SJF)
短作业优先调度算法(SJF)
假设有n项作业位于就绪队列中,这些作业的提交时间用数组requestTimes按照提交时间的先后顺序存储,对应的作业服务时间(持续时间)用数组durations存储。采用SJF算法,计算n项作业的平均等待时间。当存在多个相同长度的短作业时,按照提交时间的先后顺序进行调度。假设0<= n <= 100。求出所有作业的平均等待时间。
函数原型:void minWaitingTime(int requestTimes[],int durations[],int n)
测试用例:
输入
4
0 2 4 5
7 4 1 4
输出:
4.0
1 #include <stdio.h> 2 #include <stdlib.h> 3 #include <string.h> 4 5 #define MAX 0x7FFFFFFF 6 7 void minWaitingTime(int requestTimes[],int durations[],int n) 8 { 9 int i,time,j,k;10 float res;11 int index,arriveTime,indextemp;12 int *done = (int *)malloc(sizeof(int) * n); //表示作业是否执行过,1表示执行完毕,0表示未执行13 int *wait = (int *)malloc(sizeof(int) * n); //表示等待时间14 for(i = 0; i < n; ++i){15 wait[i] = 0;16 done[i] = 0;17 } 18 19 time = 0; //time表示总作业执行时间20 for(i = 0; i < n; i++){21 if(i == 0){ //执行第一个作业22 time += durations[i];23 done[i] = 1;24 for(j = 1; j < n; j++){25 if(requestTimes[j] < time)26 wait[j] = time - requestTimes[j];27 }28 }29 else{30 index = GetMin(durations,done,n);31 //判断是否有多个最短作业,如有选择其中先到达的32 arriveTime = requestTimes[index];33 for(indextemp = index + 1; indextemp < n; indextemp++){34 if(done[indextemp] == 0 && durations[indextemp] == durations[index] &&35 requestTimes[indextemp] < arriveTime)36 index = indextemp;37 }38 39 time += durations[index];40 done[index] = 1;41 //执行选出的最短作业,并更新其它作业的等待时间42 for(indextemp = 0; indextemp < n && i < n-1; indextemp++)43 if(done[indextemp] == 0 &&requestTimes[indextemp] < time)44 wait[indextemp] = time - requestTimes[indextemp];45 }46 }47 48 res = 0.0;49 for(i = 0; i < n; i++)50 res += wait[i];51 52 printf("%f\n",res / n);53 54 }55 //每次取出服务时间最短且示执行过的作业56 int GetMin(int durations[],int done[],int n)57 {58 int i,j,min = MAX;59 for(i = 0; i < n; i++)60 if(durations[i] < min && done[i] == 0){61 min = durations[i];62 j = i;63 }64 return j;65 }66 67 int main()68 {69 int requestTimes[100];70 int durations[100];71 int i,n;72 scanf("%d",&n);73 for(i = 0; i < n; i++)74 scanf("%d",&requestTimes[i]);75 for(i = 0; i < n; i++)76 scanf("%d",&durations[i]);77 78 minWaitingTime(requestTimes,durations,n);79 80 system("pause");81 return 0;82 }
短作业优先调度算法(SJF)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。