Implementing round robin scheduling algorithm in Java

Question

After hours of braining I've finally crashed and have come to result that I have no clue how to implement round robin into java. I've tried different approaches and the closest I've got.. well i explain with an example..

AT = Arrival Time
BT = Burst Time (Execution Time)

At first i have this row of numbers (0,5;6,9;6,5;15,10) where elements in position 0-2-4 represent arrival times and elements in position 1-3-5 represent burst times. My code is so far that this input is turned into a class, called Process which comes with a constructor: Process(String name, int AT, int BT). I've separated processes with in the ArrayList. So now i have an ArrayList alst = [P0,P1,P2,P3] where P0 has AT 0 and BT 5 and so on`..

I created a method which will return me a list of processes which have been cut with a quantum of time - For example in case of (0,5;6,9;6,5;15,10) i will get a result: [P0,P0,P1,P1,P1,P2,P2,P3,P3,P3,P3]

So round robin method is a method where every process gets quantum time for execution which I've chosen 3.

1. P0 with AT 0 & BT 3 comes in - added to the final list (time passed = 3)
2. P0 with AT 0 & BT 2 comes in - added to the final list (time passed = 5)
3. P0 finished
4. P1 with AT 6 & BT 3 comes in - added to the final list (time passed = 9)
5. next P1 is added to the queue
6. P2 with AT 6 & BT 3 comes in - added to the final list (time passed = 12)
7. next P2 is added to the queue
8. P1 with AT 6 & BT 3 comes in from queue - added to the final list (time passed = 15)
9. next P1 goes to the queue
10. P3 arrives, added to the final list (time passed = 18)
11. P1 comes from the queue - added to the final list

And that's the point where I feel like my mind has crashed and i have no idea how to queue them.

The result should look like: [P0,P0,P1,P2,P1,P3,P2,P1,P3,P3,P3]

What I coded based on the first answer given. Still doesn't work..

public ArrayList roundRobinJarjestus(ArrayList pstlst) {
    ArrayList queue = new ArrayList();// järjekord, alguses tühi
    ArrayList uuspst = new ArrayList();
    queue.add(pstlst.get(0));
    int i = 0;
    double time = 0;
    double pworkTime = 0;
    int kvant = 3;

    while (i < pstlst.size()) {
        Protsess p = (Protsess) queue.get(i); //first process is taken
        pworkTime = p.getTooaeg(); //execute time
        time = time + pworkTime;

        // if next arrival time is lower than time passed
        if (((Protsess) pstlst.get(i + 1)).getSaabumisaeg() < time) {
            queue.add(pstlst.get(i + 1));
        }

        // if worktime - quantum is higher than zero
        // and still left something to execute
        if (pworkTime - kvant > 0) {
            p.setTooaeg(pworkTime - kvant);
            queue.add(p);
        }
        uuspst.add(queue.get(i));
        i = i + 1;
    }
    return uuspst;
}

Answer 1

You can maintain a queue of waiting processes and use the following algorithm:

1. Pick the first process in the queue(if it is not empty). Add it to the output list.

2. Execute it for a given quantum of time(or less if its remaining time is less then one quantum) and subtract this quantum from the remaining time of this process.

3. If new processes have arrived, add them to the end of the queue.

4. If the last executed process is not finished(that is, its remaining time is not 0), add it to the end of the waiting queue.

5. Go to step 1 if there are any processes left.