Average waiting time of SJF and Round Robin scheduling

求non-preemptive Shortest Job First与Round Robin的平均等待时间。

输入为两个array，一个为到达时间，一个为执行时间。对于Round Robin还另外有time slice.

直接看代码吧。思路挺直接的，就想象自己就是处理器，有一个CPU时间一直在走，到点该做什么做什么。不过得注意细节。

还有想清楚waiting time是怎么得到的，比如对于RR，等待时间 = 结束时间 - 到达时间 - 执行时间。

SJF：

 1 public class ShortestJobFirst {
 2     class Node {
 3         int startTime;
 4         int burstTime;
 5         Node(int s, int b) {
 6             startTime = s;
 7             burstTime = b;
 8         }
 9     }
10 
11     public int average(int[] arr, int[] bur) {
12         if (arr == null || bur == null || arr.length == 0 || bur.length == 0) {
13             return 0;
14         }
15         //use PriorityQueue to get shortest job
16         PriorityQueue<Node> queue = new PriorityQueue<Node>(arr.length, new Comparator<Node>(){
17             @Override
18             public int compare(Node n1, Node n2) {
19                 return n1.burstTime - n2.burstTime;
20             }
21         });
22         
23         int timeStep = 0;
24         int index = 0;
25         int excTime = 0;
26         int waitTime = 0;
27 
28 
29         while(true) {
30             while(index < arr.length && arr[index] <= timeStep) {
31                 queue.add(new Node(arr[index], bur[index]));
32                 index++;
33             }
34             
35             Node cur = queue.poll();
36             if (cur != null) {
37                 waitTime += timeStep - cur.startTime;
38                 excTime = cur.burstTime;
39                 timeStep += excTime;
40             }else{
41                 timeStep++;
42             }
43             
44             if (index >= arr.length && queue.isEmpty()) {
45                 break;
46             }
47         }
48         return waitTime / arr.length;
49 
50     }
51     
52     public static void main(String[] args) {
53         int[] arrival = {0, 2, 4, 5};
54         int[] burst = {7, 4, 1, 4};
55         ShortestJobFirst test = new ShortestJobFirst();
56         int res = test.average(arrival, burst);
57         System.out.println(res);
58     }
59 }

View Code

Round Robin：

 1 public class RoundRobin {
 2     class Node {
 3         int startTime;
 4         int burstTime;
 5         int leftExcTime = 0;
 6         Node(int s, int b) {
 7             startTime = s;
 8             burstTime = b;
 9             leftExcTime = b;
10         }
11         Node(int s, int b, int l) {
12             startTime = s;
13             burstTime = b;
14             leftExcTime = l;
15         }
16     }
17     public int average (int[] arr, int[] bur, int unit) {
18         if (arr == null || bur == null || arr.length == 0 || bur.length == 0) {
19             return 0;
20         }
21         Queue<Node> queue = new LinkedList<Node>();
22 
23         int timeStep = 0;
24         int index = 0;
25         int waitTime = 0;
26         while (true) {
27             //add node to waiting queue
28             while (index < arr.length && arr[index] <= timeStep) {
29                 queue.add(new Node(arr[index], bur[index]));
30                 index++;
31             }
32             Node cur = queue.poll();
33             if (cur != null) {
34                 if (cur.leftExcTime > unit) {
35                     timeStep += unit;
36                     //add new arrival into waiting queue first,
37                     while (index < arr.length && arr[index] <= timeStep) {
38                         queue.add(new Node(arr[index], bur[index]));
39                         index++;
40                     }
41                     //then add "current" task back
42                     queue.add(new Node(cur.startTime, cur.burstTime, cur.leftExcTime - unit));
43                 } else{
44                     timeStep += cur.leftExcTime;
45                     waitTime += timeStep - cur.startTime - cur.burstTime;
46                 }
47             }else{
48                 timeStep++;
49             }
50             
51             if (index >= arr.length && queue.isEmpty()) {
52                 break;
53             }
54         }
55         return waitTime / arr.length;
56     }
57     public static void main(String[] args) {
58         int[] arr = {0,2,4,5};
59         int[] bur = {7,4,1,4};
60         RoundRobin test = new RoundRobin();
61         System.out.println(test.average(arr, bur, 3));
62         
63     }
64 }

View Code

应该还有不使用额外空间的办法吧。如果有更好解法的欢迎指教哈。