Program to implement Weighted Round Robin Scheduling Algorithm

Download Full Doc

Hayward Education

 

The weighted round-robin scheduling is designed to better handle servers with different processing capacities. Each server can be assigned a weight, an integer value that indicates the processing capacity. Servers with higher weights receive new connections first than those with less weights, and servers with higher weights get more connections than those with less weights and servers with equal weights get equal connections. The pseudo code of weighted round-robin scheduling is as follows:

 Supposing that there is a server set ''S'' = {S0, S1, …, Sn-1};

 W(Si) indicates the weight of Si;

 ''i'' indicates the server selected last time, and ''i'' is initialized with -1;

 ''cw'' is the current weight in scheduling, and cw is initialized with zero;

 max(S) is the maximum weight of all the servers in S;

 gcd(S) is the greatest common divisor of all server weights in S;

 while (true) {

     i = (i + 1) mod n;

     if (i == 0) {

         cw = cw - gcd(S);

         if (cw <= 0) {

             cw = max(S);

             if (cw == 0)

             return NULL;

         }

     }

     if (W(Si) >= cw)

         return Si;

 }

For example, the real servers, A, B and C, have the weights, 4, 3, 2 respectively, a scheduling sequence will be AABABCABC in a scheduling period (mod sum(Wi)).

In an optimized implementation of the weighted round-robin scheduling, a scheduling sequence will be generated according to the server weights after the rules of [[IPVS]] are modified. The network connections are directed to the different real servers based on the scheduling sequence in a round-robin manner.

The weighted round-robin scheduling is better than the [[Round-Robin Scheduling|round-robin scheduling]], when the processing capacity of real servers are different. However, it may lead to dynamic load imbalance among the real servers if the load of the requests vary highly. In short, there is the possibility that a majority of requests requiring large responses may be directed to the same real server.

Actually, the [[Round-Robin Scheduling|round-robin scheduling]] is a special instance of the weighted round-robin scheduling, in which all the weights are equal.

Program:

import java.util.*;

class WeightedRounRobin {

    Scanner sc = new Scanner(System.in);

    int[] S, W;

    int size, i = -1, cw = 0, max, gcd;

    WeightedRounRobin(int size) {

        this.size = size;

        W = new int[size];

        S = new int[size];

    }

    public void execute() {

        for (int j = 0; j < size; j++) {

            System.out.print("Enter weight of P" + (j + 1) + ":");

            W[j] = sc.nextInt();

        }

        max = getMaxValue(W);

        gcd = new GCD().getGcdOfArray(W);

//        algorithm

        System.out.println("Scheduling sequence will be as follow");

        while (true) {

            i = (i + 1) % size;

            if (i == 0) {

                cw = cw - gcd;

                if (cw <= 0) {

                    cw = max;

                    if (cw == 0) {

                        return;

                    }

                }

            }

            if (W[i] >= cw) {

                System.out.print("P" + i + "\t");

            }

        }

    }

    private int gcd(int number1, int number2) //Finds GCD of 2 numbers.

    {

        if (number2 == 0) {

            return number1;

        }

        return gcd(number2, number1 % number2);

    }

    public int getGcdOfArray(int[] arr) {

        int result = arr[0];

        for (int i = 1; i < arr.length; i++) {

            result = gcd(result, arr[i]);

        }

        return result;

    }

    private int getMaxValue(int[] array) {

        int maxValue = array[0];

        for (int i = 1; i < array.length; i++) {

            if (array[i] > maxValue) {

                maxValue = array[i];

            }

        }

        return maxValue;

    }

    public static void main(String arg[]) {

        Scanner s = new Scanner(System.in);

        System.out.print("Enter the no of process:");

        int n = s.nextInt();

//        WeightedRounRobin rounRobin = new WeightedRounRobin(n);

        WeightedRounRobin robin = new WeightedRounRobin(n);

        robin.execute();

    }

}

Output:

Enter the no of process:3

Enter weight of P1:4

Enter weight of P2:3

Enter weight of P3:2

Scheduling sequence will be as follow

Enter the no of process:3

Enter weight of P1:4

Enter weight of P2:3

Enter weight of P3:2

Scheduling sequence will be as follow

P0        P0        P1        P0        P1        P2        P0        P1        P2