Round Robin scheduling in java

Question

I'm trying to implement Round Robin scheduling algorithm. But the code I have done so far only consider the burst time. I also need to consider the arrival time of the process too. I have a time_chart array which I'm using to store the number of the process which is currently executing. But if no process is currently executing (that is if selected process has finished executing and next process has not arrived.), value 0 should be inserted into the time_chart array.

I have stored burst time and arrival time in a 2D array as:

//proc[][0] is the AT array
//proc[][1] is the BT array

and Time Quantum in variable q. Below is my code:

int time_chart[] = new int[total_time];
int sel_proc = 1;
int current_q = 0;

for (int k = 0; k < total_time; k++) {

    //Assign selected process to current time in the Chart
    time_chart[k] = sel_proc;

    //Decrement Remaining Time of selected process by 1 since it has been assigned the CPU for 1 unit of time
    proc[sel_proc - 1][1]--;

    //Updating value of sel_proc for next iteration
    current_q++;

    if (current_q == q || proc[sel_proc - 1][1] == 0)//If Time slice has expired or the current process has completed execution
    {
        current_q = 0;
        //This will select the next valid value for sel_proc
        for (int j = 1; j <= n; j++) {
            sel_proc++;
            if (sel_proc == (n + 1)) {
                sel_proc = 1;
            }
            if (proc[sel_proc - 1][1] != 0) {
                break;
            }
        }
    }
}

// print timeline for testing
for (i = 0; i < total_time; i++) {
System.out.println("Time " + i + ": " + time_chart[i]);
}

currently it will select the next process even though it has not arrived yet. Therefore, I need to check if the next process has arrived or not. I tried using proc[sel_proc][0] <= k to check this but it didn't seem to work. By that I mean I didn't get any output. I can't think of another way to check if the next process has arrived or not. How can I check this and put value 0 into the array if the next process has not arrived?

Answer 1

Although you can accomplish this using only arrays you may find the logic easier if you create a class structure to store the process information and use two Queues. The first Queue being a list of processes ordered by arrival time and the second Queue the processes that are currently being executed.

You can model you process something along these lines

private static class Process {
    public final int id;
    public final int burstTime;
    public final int arrivalTime;
    public int executionTime;

    public Process(int id, int burstTime, int arrivalTime) {
        super();
        this.id = id;
        this.burstTime = burstTime;
        this.arrivalTime = arrivalTime;
    }
}

Then create a Queue call unscheduled processes (Or what ever seems appropriate) and add the processes to that queue ordered by arrival time. Queue<Process> = new LinkedList<>()

Now during your loop every time you just check the head of the queue and see if the process' arrival time is equal or greater than the current time. If it is remove it from the queue and add it to the head of scheduler queue. LinkedList<Process> = new LinkedList<>()

You always remove the head process from the scheduler queue and update the execution time of the process. Make sure not to go beyond burst time, ie execution time is always increased by the quantum OR burstTime - executionTime, depending on which is smaller. After the update, if the execution time is less then the burstTime, add the process back to the scheduler queue.

Remember the the current time will not be increased by quantum, if the remaining time on the process was less than the quantum.

Answer 2

This problem is much simpler if rather than a single int tracking the currently running process, you use a list of all. A good choice is to keep an ordered list where the running process is at the head, and the others follow in the order they should run in the future. Then you can always get the next process to run by rotating the list. It's simple to update the list for each quantum. A Java collection that makes all these options easy is called a Deque.

Something like this:

Deque<Integer> running = new ArrayDeque<>();
for (int quantum = 0; quantum < totalDuration; ++quantum) {
  // Add new arrivals to the list of running processes.
  // Note that if the processes are pre-sorted by arrival time,
  // this loop can be made more efficient. This assumes no sorting.
  for (int process = 1; process <= processCount; ++process) {
    if (arrivalTime[process] == quantum)
      running.addLast(process); // Use addFirst if new procs should run immediately.
  }
  if (running.isEmpty())
    timeChart[quantum] = 0; // Nothing to run
  else {
    // Select the process now at the head.
    int selectedProcess = running.getFirst();

    // Decrement the running process's burst time. If it's done, remove
    // it from the running list.
    if (--burstTime[selectedProcess] == 0) 
      running.removeFirst();

    // Record the run for this quantum.        
    timeChart[quantum] = selectedProcess;

    // Rotate the previous head to the tail of the list for next quantum.
    if (running.size() > 1)
      running.addLast(running.removeFirst());
  }
}

Note I've used more rational names and Java conventions. Your choice of names and data types is a bit hideous. As others have said, it would be still better to group arrival and burst times for a process in a class.

Answer 3

Actually, you should see whether the arrival time of the process is less than or equal the next upcoming time. So, you should check proc[sel_proc][0] <= k + 1. In particular, the only change that you should make is your if which instead of

if (proc[sel_proc - 1][1] != 0) {
    break;
}

should become: (if the remaining burst time is not zero and its arrival time is before or equal the next time, i.e. k + 1)

if (proc[sel_proc - 1][1] != 0 && proc[sel_proc][0] <= k + 1) {
        break;
}

More importantly, make sure that your last valid time unit is total_time - 1 and not total_time itself. Furthermore, are your arrival times 0-based or 1-based, these are corner cases that you have to be careful about.

Answer 4

What do you plan to schedule with your algorithm. I have never heard of anyone that does time slicing, except when implementing an operating system.

Time slicing works at an OS level because the OS can choose which (of the eligible) processes/threads it wants to run on the CPU, and because the OS can basically stop a thread at any instruction and flush CPU registries to cache. This principle will only work in code, if each task can be broken down to very small units of work ('CPU' instructions). That way if you have 100 tasks consisting of 100 units each, and a 4 processor cores, you can implement your own time slicing algorithm (but I would not recommend it).

Traditionally, if you have multiple concurrent tasks, you would use a threadpool with thread count equal to the number of CPU cores (or more it the tasks have IO), and you would simply queue the tasks as they arrive, and let the OS worry about time slicing.