首页 > 代码库 > 短作业优先调度算法(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)