今天做了一道关于线程调度的题，采用的roundrobin调度算法，求出每个线程的等待时间
输入arrive代表着线程到达时间，run代表每个任务执行完所需要的时间，n代表线程数量，q代表了每个时间片最大的耗时
当时也没什么想法，就想直接模拟这个cpu调度策略，等待所有任务执行完后求出等待时间
1 #include<iostream>
2 #include <queue>
3 using namespace std;
4 int a[]={0,1,3,9};
5 int run[] = {2,1,7,5};
6 float waitingTimeRobin(int *arrival, int *run, int n, int q)
7 {
8 // WRITE YOUR CODE HERE
9 int i=0;
10 queue<int> qq;
11 int j=0;
12 int task = -1;
13 int *wt = new int[n];
14 int *lst = new int[n];
15 for(int tt=0;tt<n;tt++){
16 wt[tt] = 0;
17 lst[tt] = arrival[tt];
18 }
19 while(1){
20 for(;j<n&&arrival[j]<=i;++j){
21 if(arrival[j]==i){
22 qq.push(j++);
23 break;
24 }
25 }
26 if(task == -1 && !qq.empty()){
27 task = qq.front();
28 qq.pop();
29 }
30 if(task!= -1){
31 int tmp = i+q;
32 wt[task] += (i-lst[task]);
33
34 while(i<tmp&&run[task]>0){
35 i++;
36 run[task]--;
37 }
38 lst[task] = i;
39 for(;j<n&&arrival[j]<=i;j++){
40 qq.push(j);
41 }
42 if(run[task]>0)
43 qq.push(task);
44 task = -1;
45 }else{
46 i++;
47 }
48 if(qq.empty()&&j>=n)
49 break;
50 }
51 int total = 0;
52 for(int kk=0;kk<n;++kk)
53 total += wt[kk];
54 float ans = (float)total/(float)n;
55 return ans;
56 }
57 int main(int argc, _TCHAR* argv[])
58 {
59 float ans = waitingTimeRobin(a,run,4,2);
60 cout<<ans<<endl;
61 return 0;
62 }如果有更好的想法欢迎拍砖指正呐~
代码当时写的很糙……后来也没有改了……
样例1：
arrival = [0,1,4] run = [5,2,3] n = 3, q = 3
output = 2.3333333
样例2：
arrival = [0,1,3,9] run = [2,1,7,5] n =4, q = 2
output = 1.0000000