Job Scheduling Algorithms in Cloud Computing
The main idea of the Min-Min algorithm is to map each task to resources which can complete the task in the shortest possible time. The min- min algorithm estimates the execution and completion time of each job on each available resources. It is two-phase in the Min-Min algorithm.
1.It calculates the minimum execution time for all tasks.
2.The task with the least execution time among all the tasks is chosen. The algorithm further proceeds by assigning the task to the resource that produces the minimum completion time. The same procedure is repeated until all tasks are scheduled.
The working of the Max-min algorithm is similar to the Min-min algorithm. The differentiating feature is as per the name as the word “minimum” is replaced by “maximum” similarly, here the task having the maximum earliest completion time is assigned to the corresponding resource. Here, larger tasks are given priority over the smaller tasks.
Max Min is similar to the min- min algorithm except the following: after finding out minimum execution times, the maximum value is selected which is the maximum time among all the tasks on the resources. Then according to that maximum time, the task is scheduled on the corresponding machine. The execution time for all other tasks is updated on that machine and assigned task is removed from the list of the tasks that are to be assigned to the machines.
RASA is a hybrid scheduling algorithm composed of two traditional techniques- Max-min and Min-min. The min-min strategy is used to execute small tasks before large tasks and Max- Min strategy is applied to avoid the delays in large tasks execution.
Both the strategies are used alternatively for tasks and alternative exchange results in the consecutive execution of a small and a large task on different resources hence ignoring the waiting time of the small tasks in the Max-min algorithm and the waiting time of the large tasks in the Min-min algorithm.
Ant Colony Scheduling
- Ants navigate from nest to food source.
- Shortest path is discovered via Pheromone Trails.
- Each ant moves at random.
- Pheromone is deposited on path.
- More pheromone on path increases probability of path being followed.
- In context of Cloud Computing, “food” implies virtual machines and “ants” implies jobs. The path which is rich in pheromone is mostly chosen by other ants.
- In the ACO algorithm, the load is calculated on each host taking into account the CPU utilization made by all the VMs that are executing on each host. This metric is useful for an ant to choose the least loaded host to allocate its VM.
ACO in Cloud Computing Method
Step 1: Perform initialization of the pheromone
Step 2: while (stopping criteria not reached) do
Step 3: Set locations of all ants in an initial Virtual Machine
Step 4: while (all ants have not reached at a solution) do
Step 5: for each ant do
Step 6: Choose VM for the subsequent task using the intensity of pheromone trail
Step 7: end for
Step 8: end while
Step 9: Update the pheromone
Step 10: end while
Step 11: end
Bee Colony Scheduling
The BCO algorithm is based on the activities of bees while searching for nectar and sharing the information with other bees.
There are three types of agents –
- employed bees
- onlooker bees
- scout bees
The employed bee stays on a food source and provides its surroundings in memory; the onlooker acquires this data from the employed bees and selects one of the food sources to forage, and the scout performs the task of finding new nectar sources
BEE Colony Algorithm Flowchart
|Type of system/environment
|execution and completion time
|Least exec time task assigned to resource producing min completion time
|increase resource utilization rate
|Max earliest time task assigned to resource
|small task delays for long time
|Make Span has to be reduced
|number of resources decide the strategy
|reduce make span
|Scout bees forage the food source
|Each class performs Waggle dance and advertise about food source
|Reduced makespan and improved performance
|Loads each VM
And defines load balancing
|Reduced time, improved results by local