Shorest Job First

Analysis

• Very similar to round robin scheduling (easier)
• Keep a priority queue to store processes so that they can be extracted according to priority
• Need to overide priority
• 输入：int[] req: request time； int[] dur: duration time
• 输出：average wait time

Pseudo code

Create a new priority queue(Define compare function)
curTime, waitTime, index all set to 0
while (queue里面还有process，或者index没有reach最后一个process){
    如果queue里面还有process{
        cur = queue.poll()
        waitTime累计
        curTime更新到加上cur.dur
        把该过程中arrive的新process加入queue
        index更新
    }
    如果（queue里面没有process）{
        1. 把index process放入queue
        2. curTime设为index arrival time
        3. index++ (因为index指向下一个还没有处理的process)
    }

    return waitTime/length 
}

Code

class process {
    int reqTime;
    int durTime;
    process(int req, int dur) {
        reqTime = req;
        durTime = dur;
    }
}

public class ShortestJobFirst{
    public floate Solution(int[] req, int[] dur){
        if (req.length==0 || dur.length==0 || req.length!=dur.length) {return 0;}
        int curTime = 0, waitTime = 0, index = 0, len = req.length;
        PriorityQueue<process> queue = new priorityQueue<process>(new Comparator<process>(){
            @Override
            public int compare(process p1, process p2){
                if(p1.durTime==p2.durTime) {return p1.reqTime-p2.reqTime;}
                return p1.durTime-p2.durTime;
            }
        });
        while(!queue.isEmpty() || index<len){
            if(!queue.isEmpty()){
                process cur = queue.poll();
                waitTime += curTime - cur.reqTime;
                curTime +=cur.durTime;
                for(;index < length && req[index]<=curTime;index++){
                    queue.offer(new process(req[index],dur[index]));
                }
            }
            else{
                queue.offer(new process(req[index],dur[index]));
                curTime = req[index++];
            }
        }
        return (float)waitTime/length;

    }
}

Reference

Youtube