Round Robin

Analysis

  • 输入：arrival time array, execution time array, quantum time
  • 输出：每个process的平均等待时间
  • Keep a queue to store processes (a process is characterized by its arrival time and execution time)
  • curTime: 记录当前时间
  • waitTime: 累计所有等待时间
  • cur: 当前进行的process
  • index：指向下一个还没有处理到的process

Pseudo Code

create a new queue
curTime, waitTime, index set to 0
while(queue里面还有process，或者还有process没有处理过) {
    如果（queue里面还有process）{
        1. poll queue得到当前process cur
        2. 更新wait time（开始处理的时间-到达时间就是waitTime）
        3. 更新curTime到下一个节点。下一节点或者过了q时间，或者当前process run完。通过比较q和cur.exetime取小的那个。
        4. 把这个过程中有可能arrive的新的process加入（判断条件，arrive time小于新的时间点并且index在范围内，同时更新index）
        5. 如果cur还没有run完，更新剩下的时间加入到queue末尾

    }

    //出现以下情况有两种可能：
    //1. 初始情况 
    //2. 之前的process都已经run完，新的process的arrival time还没有到。所以只需要更新arrival time，不需要更新waitTime。

    如果（queue里面没有process）{
        1. 把index process放入queue
        2. curTime设为index arrival time
        3. index++ (因为index指向下一个还没有处理的process)
    }
return waitTime/length   
}

Code

package amazon;

import java.util.LinkedList;
import java.util.Queue;

class process {
    int arrTime;
    int exeTime;
    process(int arr, int exe) {
        arrTime = arr;
        exeTime = exe;
    }
}

public class RoundRobinScheduling {
    public float Solution(int[] Atime, int[] Etime, int q) {
        if (Atime == null || Etime == null || Atime.length != Etime.length)    return 0;
        int length = Atime.length;
        Queue<process> queue = new LinkedList<process>();
        int curTime = 0, waitTime = 0;
        int index = 0;
        while (!queue.isEmpty() || index < length) {
            if (!queue.isEmpty()) {
                process cur = queue.poll();
                waitTime += curTime - cur.arrTime;
                curTime += Math.min(cur.exeTime, q);
                for (; index < length && Atime[index] <= curTime; index++)
                    queue.offer(new process(Atime[index], Etime[index]));
                if (cur.exeTime > q)
                    queue.offer(new process(curTime, cur.exeTime - q));
            }
            else {
                queue.offer(new process(Atime[index], Etime[index]));
                curTime = Atime[index++];
            }
        }
        return (float) waitTime / length;
    }
}

Refenrence