School Papers

Contents the jobs evenly across all the nodes.

 

Contents
Introduction. 2
Round Robin. 2
What does the Round Robin algorithm do?. 2
Round Robin Algorithm.. 3
Algorithm features and functionality. 4
What is a job?. 4
Weighted Round Robin. 5
What is the Weighted Round Robin?. 5
Weighted Round Robin Algorithm.. 6
Algorithm Features and functionality. 7
Ordering Jobs. 8
Messages sent in both algorithms. 8
References. 9
 

 

 

 

 

 

 

 

 

 

 

 

 

 

Introduction

I
have investigated how the Round Robin and Weighted Round Robin scheduling
strategy’s work in the field of distributed systems. From this investigation, I
have created my own algorithm to show how they work in the form of a flow
diagram and justification behind this in my report.

Round Robin

What does the Round
Robin algorithm do?

The round robin is a scheduling
algorithm that will send jobs to each node in the order that they arrive this
will distribute the jobs evenly across all the nodes. The need for a scheduling
algorithm is to perform multitasking which will increase efficiency in a
distributed system. In my version of the round robin the jobs will be processed
until completion however a problem with this method is that it takes preference
over larger jobs over the smaller ones which can lead to small tasks taking
longer than necessary.

In
a distributed system, the round robin algorithm ensures that the computers
CPU’s aren’t going to be overworked as it only allows 1 task to be given to
each node and that the rest of the jobs are queued up waiting for an available
node. Using figure 1, if the user wanted 4 jobs to be completed the round robin
would take the first job and see that there is an available node and pass the
job to the 1st node and it would do the same for the next 2 jobs.
However, when it comes to jobs 4, it will be put in a queue and if another job
was added then it would join the queue in the order that they arrived and as
nodes becomes available the jobs will be processed in the queue order.

 

 

Round Robin Algorithm

Algorithm features
and functionality

 

The
first thing my round robin algorithm does is to loop my initiator and
constantly check for new job requests from the load balancer, making sure that
any new jobs are not missed. It will receive the load balancers IP, so it knows
where to send the job request to.

The
load balancer will receive any messages sent to it and the messages will be
checked to see whether it is a node or a job. The nodes will also be added to an
array of available nodes so that the load balancer can easily give each node a
job to do without having to check to see what nodes are available. The job will
be forwarded to the first available node listed in the array and will also
remove the node from the list so that it is not overused.

The
node will send its name and it’s IP to the load balancer to identify itself
within the node array. The node will then receive a job from the load balancer
when it is at the top of the list, and will then complete the job. Once it has
completed the job, it will re-join the array of available nodes.

What is a job?

 

A
job is a unit of work. A job can be identified with a single process, which may
have sub-processes which perform the tasks that comprise the work of the job. A
job is important as it can be scheduled for non-interactive execution by a job
scheduler this allows the scheduler to execute the jobs without the users
input. This is important as it allows the load balancer to receive the jobs and
send them to the free available nodes without any interaction of the user which
increases efficiency of the algorithm.

 

Weighted Round Robin

What is the Weighted
Round Robin?

 

The
weighted round robin is very similar to the regular round robin however in the
weighted round robin each node has a weight attached to it to signify its
traffic handling capacity.

For
example, if you had two nodes A and B with weights 3 and 2 respectively, and
assuming the jobs carried the same weight. The load balancer would send three
jobs to node A for every two jobs that it sent to B.

In
a distributed system, the weighted round robin algorithm ensures that the
computers CPU’s are equally distributed the jobs that they are suitable to do
based on weighting. This makes for a more efficient system as each node has a
queue of jobs it can perform optimally instead of being assigned the first job
on the list and the correct utilization of each node will lead to increased
productivity from this distrusted system

 

 

 

 

 

 

 

 

Weighted Round Robin Algorithm

Algorithm Features
and functionality

 

As
in the round robin algorithm the first thing my round robin algorithm does is
to loop my initiator and constantly check for new job requests from the load
balancer, making sure that any new jobs are not missed. It will receive the
load balancers IP, so it knows where to send the job request to.

The
load balancer will receive any messages sent to it and the messages will be
checked to see whether it is a node or a job. The nodes will also be added to
an array of available nodes so that the load balancer can easily give each node
a job to do without having to check to see what nodes are available. The job
will be forwarded to the first available node listed in the array and will also
remove the node from the list so that it is not overused.

The
node will send its name and it’s IP to the load balancer to identify itself
within the node array and will then be added to a list ordering the nodes based
on their weight and if they’re being used to process a job they will be order
based on their available weight or load percentage (load percentage could be
calculated based on the weight of the node and the amount of jobs it has
queueing). It will then take the node with the most available resources and
check to see if a job can be added to its queue without going over the load
percentage. If the job can’t be added to the end of the queue on any nodes it
will wait for a node to become available.

Once
there is a node with enough resources it will get the first process from the
queue and send it to the node to be processed and the nodes load percentage
will go up updating the list so that it doesn’t get jobs it can’t process.  

It
will then check for all jobs that have been completed allowing the list of load
percentage to update allowing more jobs to be complete. This process could be
done outside of this loop to increase efficiency so that finished jobs aren’t
checked at the end of each cycle and are constantly being checked.

 

 

Ordering Jobs

 

The
method of ordering jobs in the Round Robin and Weighted Round Robin algorithm
is the First Come, First Served scheduling method (FCFS) this method only
considers the order that it arrives. Jobs are executed in the order that they
arrive, this method of scheduling is poor in performance as the average wait
time is high.  

Another
method of ordering jobs is the shortest job first method this orders and
processes the jobs based on the size of the job. This method is great at
minimising queue waiting times as all the shortest jobs are done first,
however, if jobs keep coming in the larger tasks won’t be processed until all
the smaller jobs are complete. This method can easily be implemented into the
weighted round robin algorithm as the jobs have been assigned a time allowing
the algorithm to easily order the jobs upon arrival.

Priority
based ordering is the most common scheduling strategy in batch systems. In this
method, a priority is given to each job, the jobs would then be ordered based
on priority and the highest priority jobs would be executed first.

If
the user was to implement the priority of jobs before being sent to the load
balancer this method of ordering would be simple to implement as the algorithm
would only have to sort them based on their priority and then send them to the
nodes.

 

 

 

 

 

 

 

Messages sent in both
algorithms

In
both algorithms, the first message would be the from the load balancer to the
initiator with the load balancer’s IP, so the initiator knows where to send the
job requests. Messages would be sent from the user to the initiator in the form
of a job request, which would then be forwarded to the load balancer.

However,
in weighted round robin algorithm the message the load balancer would receive
from the initiator would contain the weight of the job request, so it can be
correctly sorted in the array. In both algorithms, the load balancer would
begin receiving messages from both nodes and the initiator, which would then be
separated into the available node array or the job queue.

In
the weighted round robin, the same process would happen however more
information would be present when receiving the messages such as the weighting
of the node and the job weight. This would then affect how the array is sorted,
but wouldn’t really affect the job queue as the jobs would be taken by a node
if it meets the weighting criteria.

Within
the nodes there would also be messages sent as the servers would have to
communicate with each other so they’re able to find out the nodes weight when
it comes to the weighted round robin algorithm. They would also be communicating
about the servers within the node.

When
the load balancer is sending messages to the nodes the load balancer would have
to set up a connection for the job to travel along, it would do this by sending
a message stating that it is send a job, the node would then send an
acknowledgement back to the load balancer.

The
load balancer would then send the job to the node, once the job has been sent
the load balancer would send another message to the node asking to terminate
the connection, the node would then send a message back to say OK and the
connection would be terminated. It would terminate the connection, so it can
connect to another node.

Once
the node has completed the job it would send a message to the load balancer
asking for a connection the load balancer would acknowledge the response and
the completed job would be sent across the node would then terminate the
connection.

 

Summary

While
investigating both round robin and weighted round robin scheduling strategies,
many positive and negative benefits were found which would affect my decision
of which strategy to use when creating a distributed system.

Round Robin is excellent for
Parallel computing is because round-robin is great for load balancing if the
tasks are around the same lengths. There is also fairness with round robin
as each task gets an equal share of the CPU.

Some
disadvantages of using round robin include no basic priority assignment. Round-robin
scheduling, like other first-come, first-served methods, has no special
priority to assigned to more important tasks. This means an urgent request
doesn’t get handled any faster than other requests in queue. The best round
robin-based systems will include a tool that allows you to suspend the usual
priorities for a “rush job”, allowing for urgent tasks to be
completed quicker. It also suffers from its ability to assign equal amounts of time to each task. It can slow down
those with medium-length tasks. For example, if there are 2 jobs that take 10
seconds to complete within the queue but after there is a job that will take
180 seconds to complete and behind that job there is 5 more jobs that will only
take 5 seconds. On a distributed system that has 3 nodes, one node will be
occupied with the 180 second job for the duration of the job meaning that
smaller jobs will take a longer amount of time then necessary. This isn’t a
problem for computers, but it can frustrate users.

Weighted Round robin is perfect for
using with real time scheduling systems as it can effectively manage different jobs
that are sent to it using the job weighting system. The weighted approach is also
designed to better handle servers with different processing capabilities, meaning
that the distributed system’s nodes do not have be the same in terms of computational
power. However, there is
a lack of effective mechanisms to decide the weight assigned to each server to
achieve an overall optimal revenue of the system.

 

 

With these reasons, I have decided that when implementing
my distributed system algorithm, I will use the Weighted Round Robin scheduling
strategy as it addresses the issues with round robin and performs more optimally
in real time distributed systems.

 

References

 

Barth, N. (2016). Job
(computing). Available:
https://en.wikipedia.org/wiki/Job_(computing). Last accessed 10th Jan 2018.

Aida,
K. (2000). Effect of Job Size Characteristics on Job Scheduling Performance.
Available: http://www.cs.huji.ac.il/~feit/parsched/jsspp00/p-00-1.pdf. Last
Accessed 11th January 2018