Process scheduling with Java

As we know a single-core CPU executes its processors one by one at a particular time, but when there are lots of processors in the ready queue, the CPU needs some mechanism to choose one of those processors.

In order to do that, we use a logical mechanism for selecting and executing a particular process at a given time. these mechanisms are collectively known as Process Scheduling algorithms. There are 3 main Process Scheduling Algorithms.

  1. First come First Serve (FCFS)
  2. Shorter job first (SJF)
  3. Round Robin (RR)

The easiest one among these Process Scheduling algorithms is the FCFS algorithm, it only gives the highest priority for the firstly arrived process. So, all the processors share the priority in ascending order according to their arrival time. Once a process terminates its execution, the next process which is secondly arrived at the queue will start to execute and it keeps remain until it terminates ( Assume that no interruptions happen).

Suppose, we have 4 processors called P1,P2,P3,P4, which are arrived to the queue at 0ms,2ms,6ms and 8ms, and the corresponding burst times( the time that each of the processors uses to execute its instructions ) are 4ms, 6ms, 5ms, 3ms.

Process numberArrival timeBurst time
P10ms4ms
P22ms6ms
P36ms5ms
P48ms3ms

According to the FCFS algorithm, the CPU will take the P1 process at first as it is the firstly arrived process in the queue. Then the process numbers P2, P3 and P4 will take the chances to be executed by the CPU according to their arrival time. Each of these processors will wait until the termination of the currently executing process. This scenario is somewhat complex to imagine, because of that we use Gantt charts for drawing this.†

As you see here, now you can easily define following terms,

  1. P1 arrives at 0ms, starts to execute at 0ms, waiting time = 0ms.
  2. P2 arrives at 2ms, starts to execute at 4ms, waiting time = 2ms.
  3. P3 arrives at 6ms, starts to execute at 10ms, waiting time = 4ms.
  4. P4 arrives at 8ms, starts to execute at 15ms, waiting time = 7ms.

These terms are the key points of a process scheduling algorithm. By using these derived values from the chart, we can find the following Scheduling Criteria.

  1. Turnaround time.
  2. Waiting time.
  3. Response time.

Let’s find more on these criteria.    

Turnaround time

The interval from the time of submission of a process to the time of completion is the turnaround time.

Waiting time  

Waiting time is the sum of the periods spent waiting to be executed by the CPU.

Response time

The time from the submission of a request until the first response is produced which the time it takes to start responding, not the time it takes to output the response.

In this example, P1 submitted to the ready queue at 0ms and starts to execute at 0ms which means its turn around time is equivalent to its burst time which is 4ms.

Like,

  • P2 turn around time = 8ms
  • P3 turn around time = 9ms
  • P4 turn around time = 10ms

And also, we can find the Waiting time by substituting the arrival time of a process from its execution started time ( which means the time it waits in the ready queue until it starts to be executed – response time).

  • P1 waiting time = 0ms – 0ms = 0ms
  • P2 waiting time = 4ms – 2ms = 2ms
  • P3 waiting time = 10ms – 6ms = 4ms
  • P4 waiting time = 15ms – 8ms = 7ms

The timeline starts responding at 0ms, P1 produces its first response at 0ms which means the response time of the P1 is zero.

Like,

  • P2 response time = 4ms
  • P3 response time = 10ms
  • P4 response time = 15ms

Now, when arrival times and burst times are given for processors, we can find the corresponding Turnaround time, Waiting time and Response time via a Gantt chart. But the challenge here is to create a Java program that generates these criteria when the arrival times and the burst times are given.

There are several approaches that we can use to accomplish this task via Java OOP concept, but here I use a different approach for defining Java classes and methods. Since the main component in this problem is CPU, a class called CPU is created inside the project.

In addition to that, an interface called Process Scheduling is also created (methods for calculating turnaround times, waiting times, and other criteria can be used by other Process Scheduling algorithms also, so all the process algorithms should implement the Process Scheduling interface and Override the methods according to their Scheduling algorithms).

Ex: I created only the FCFS class which implements the Process Scheduling interface since this problem is to implement the FCFS algorithm.

So in this program, we have 2 java classes and 1 interface.

  1. CPU.
  2. ProcessSchedular.
  3. FirstComeFirstServe.
The CPU class

This class is responsible for taking inputs (the Arrival time and the Burst time of a process) from a user, and send those data to the corresponding Process Scheduling classes ( In this case, FirstComeFirstServe), and those Scheduling classes will send back the calculated values (turnaround time, waiting time ..etc) to the CPU class, in order to display them.

The ProcessSchedular interface

Here, all the abstract methods for calculating Turnaround time, Waiting time…etc are declared.

Note: The importance of using an interface is the same interface and the same methods name can be accessed according to one single structure which is defined by different Processing Algorithm classes.Note:

In this interface, there are 5 main methods are declared.

  1. Turnaround time
  2. Waiting time
  3. Response time
  4. Average turnaround time
  5. Average waiting time

a particular scheduling algorithm will have to define these methods, in order to use them.

The FirstComeFirstServe class

This is the Process Scheduling algorithm that we use in this program. So, this class defines all the abstract methods in the ProcessScheduler interface according to the way of First Come First Serve(FCFS) behaves.

In order to Override all the methods in the interface, the interface class should be implemented by this class.

Source codes

Source codes for the ProcessSchedular interface.

public interface ProcessSchedular {
    //here all the abstract methods are implemented

    public abstract int[] calculateTurnAroundTime(int[] burstTime,int[] arrivalTime);
    public abstract int[] calculateResponseTime(int[] burstTime, int[] arrivalTime);
    public abstract int[] calculateWaitingTime(int[] burstTime, int[] arrivalTime);
    public abstract double calculateAvgTurnAroundTime(int[] turnAroundTime);
    public abstract double calculateAvgWaitingTime(int[] waitingTime);


}


Source codes for the FirstComeFirstServe class

/*
The algorithm for the FCFS is programmed here
 */

package lk.ac.kln.cal.FCFS;

public class FirstComeFirstServe implements ProcessSchedular {

    @Override
    public int[] calculateTurnAroundTime(int[] burstTime,int[] arrivalTime) {
        //Once this method is called by the CPU, the turn arround times will be generated
        //In FCFS the turn around time is the sum of waiting time + I/O waiting time + burst time
        int length = burstTime.length;
        int[] waitingTime = calculateWaitingTime(burstTime,arrivalTime);
        int[] turnArroundTime = new int[length];


        turnArroundTime[0] = burstTime[0];

        for(int i = 1; i<length; i++){
            turnArroundTime[i] = burstTime[i]+waitingTime[i];
        }
        return turnArroundTime;

    }

    @Override
    public int[] calculateResponseTime(int[] burstTime,int[] arrivalTime) {
        // this method is responsible for calculating response time
        // the time that each process takes to generate its first out put since the zero
        int length = burstTime.length;
        int[] responseTime = new int[length];

        responseTime[0] = arrivalTime[0];

        for(int i = 1; i<length; i++){
            responseTime[i] = responseTime[i-1]+burstTime[i-1];
        }
        return responseTime;
    }


    @Override
    public int[] calculateWaitingTime(int[] burstTime, int[] arrivalTime) {
        /*this method calculates the waiting time of a process. Basically we defined that the waiting time
        of the first process is almost zero
         */

        int length = burstTime.length;
        int[] waitingtTime = new int[length];
        //waitingtTime[0] = 0;

        int [] responseTime = calculateResponseTime(burstTime,arrivalTime);
        for( int i = 0; i<length; i++){
            waitingtTime[i] = responseTime[i] - arrivalTime[i];
        }
        return waitingtTime;
    }



    @Override
    public double calculateAvgTurnAroundTime(int[] turnAroundTime) {
        //this method is created for calculating the average turn around time
        double totalTurnAroundTime = 0;
        double length = turnAroundTime.length;
        double avgTurnAroundTime ;

        for(int i = 0; i<length; i++){
            totalTurnAroundTime += turnAroundTime[i];
        }

        avgTurnAroundTime = totalTurnAroundTime/length;

        return avgTurnAroundTime;
    }


    @Override
    public double calculateAvgWaitingTime(int[] waitingTime) {
        //this method is created for calculating the average turn around time
        double totolWaitingTime = 0;
        double length = waitingTime.length;
        double avgWaitingTime ;

        for (int i = 0; i<length; i++){
            totolWaitingTime += waitingTime[i];
        }

        avgWaitingTime = totolWaitingTime/length;

        return avgWaitingTime;
    }


}

Source codes for the CPU class


/*
This is a simple program that simulates the process of CPU scheduling, specially this program
implements the process of First Serve First Come algorithm , but this whole program with all the classes are designed to
adapt any of the CPU Scheduling algorithms.
As you see, the FirstComeFirstServe class implements the ProcessSchedular interface, In this way we can adapt more scheduling algorithms
to the ProcessSchedular interface and that can be used by this CPU class.

CTEC 21032

programmed by:- Mahesh M.G.H
Reg No: - CT/2016/041

 */


package lk.ac.kln.cal.FCFS;

import java.util.Arrays;
import java.util.Scanner;

public class CPU {

    public static void main(String[] args) {

        // This is for getting the number of processors from the user
        System.out.print("Enter number of processes: ");
        Scanner getNumberOfProcessors = new Scanner(System.in);
        int numberOFProc = getNumberOfProcessors.nextInt();


        //This is for getting the important details(Arrival time, burst time) of process
        System.out.print("Enter each process arrival time (ms) and CPU burst: ");
        Scanner getProcessDetails = new Scanner(System.in);
        String ProcessDetails = getProcessDetails.nextLine();

        // Here the inputed details of a process is splited into an array that can be used to further split as burst time and arrival time
        String[] ProcessDetailsArray = new String[numberOFProc];
        ProcessDetailsArray = ProcessDetails.split(" \\| ");

//***here i assume that the user enters the details of processes in acsending order of their arrival time,if it is not then a sorting algorithm should be used***

        //creating arrays for storing arrival time and the burst time of a process
        int[] ProcessArrivalTime = new int[numberOFProc];
        int[] ProcessBurstTime = new int[numberOFProc];


        //this for loop is used for storing the arrival time of a process
        for(int i = 0; i <numberOFProc; i++){
            /*In here a little bit conversion between a String and an Integer is happened,
            I extract the corresponding arrival time for a process that is stored in the ProcessDetailsArray and store it in the
            ProcessArrivalArray
             */
            String temp[] = ProcessDetailsArray[i].split("\\,");  // since the arrival time is stored as the 0th character of the item, I used the temp array to split it by ','
            ProcessArrivalTime[i] = Integer.parseInt(temp[0]);

        }



        //this for loop is used for storing the burst time of a process
        for(int i = 0; i <numberOFProc; i++) {
            /*In here a little bit conversion between a String and an Integer is happened,
            I extract the corresponding arrival time for a process that is stored in the ProcessDetailsArray and store it in the
            ProcessArrivalArray
             */
            String temp[] = ProcessDetailsArray[i].split("\\,");  // since the arrival time is stored as the 0th character of the item, I used the temp array to split it by ','
            ProcessBurstTime[i] = Integer.parseInt(temp[1]);
        }


            //scheduling the processes according to the FCFS algorithm
            ProcessSchedular processSchedular = new FirstComeFirstServe();

            //calculating the turn arround time
            int[] turnAroundTime =  processSchedular.calculateTurnAroundTime(ProcessBurstTime,ProcessArrivalTime);

            //calculating the response time
            int[] responceTime = processSchedular.calculateResponseTime(ProcessBurstTime,ProcessArrivalTime);

            //calculating the waiting time
            int[] waitingTime = processSchedular.calculateWaitingTime(ProcessBurstTime,ProcessArrivalTime);

            //calculating the average turn arround time
            double avgTurnAroundTime = processSchedular.calculateAvgTurnAroundTime(turnAroundTime);

            //calculating the average waiting time
            double avgWaitingTime = processSchedular.calculateAvgWaitingTime(waitingTime);

            //This is the output process of this program

            System.out.println("Process     |Turnaround time     |Response time     |Waiting time");

            for(int i = 0; i<numberOFProc; i++){
                int ta = turnAroundTime[i];
                int rt = responceTime[i];
                int wt = waitingTime[i];

                System.out.println((i+1)+"\t\t\t\t"+ta+"\t\t\t\t\t"+rt+"\t\t\t\t\t"+wt);

            }
        System.out.println("Average turnaround time: "+Math.round(avgTurnAroundTime)+"ms");
        System.out.println("Average waiting time: "+Math.round(avgWaitingTime)+"ms");

        }

    }







Sample Outputs

Answers from the Java Program

Leave a comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.