Min Min Algorithm in Grid Computing with code in C

Here you will find the easiest explanation for min min algorithm in grid computing.

Let us first know why this algorithm is needed?

This is a static task scheduling algorithm used for load balancing.

Let us take an example before moving to the code

Image
Image

Here Task 1 will execute in 140ms in VM1 and in 100 ms in VM2. Task 2 will execute for 20ms in VM1 and in 100ms in VM2 . Task 3 will run for 60 ms in VM1 and for 70 ms in VM2.

What is a Task ?

Let’s take an example. Suppose you have developed a social media app called fakebook. Now user one wants to change her DP , another user wants to create her account and the third user wants to like a picture.

All these are the tasks and involve manipulation in the database. The entity responsible for that change is the backend server. For effective use of the server you have made virtual partitions of the server making some virtual machines good for light computation and some virtual machines for heavy computation.

Algorithm to solve the problem

  1. Find minimum time for each task , in the above image minimum time for each task is (100 ms ,T1 ,VM2), (20 ms, T2, VM1) ,(60 ms, T3, VM1)
  2. Now find the set with minimum time and that is (20 ms, T2, VM1)
  3. Execute T2 in VM1 for 20 ms
  4. Since 20ms has been elapsed we need to update our data. New data is:

5. Here we impute T2 as INT_Max(2³¹) to let our code know that this task is over and it denotes infinite. Now repeat step 1

6. Find minimum time for each task , in the above image minimum time for each task is (100 ms ,T1 ,VM2), (70 ms, T3, VM2)

7. Now find the set with minimum time and that is (70 ms, T3, VM2)

8. Execute T3 in VM1 for 70ms

9. Since 70ms has been elapsed we need to update our data. New data is:

10. Find minimum time for each task , in the above image minimum time for each task is (160 ms ,T1 ,VM2)

11. Exit Since all task has been scheduled.

Makespan produced by any algorithm for a schedule can be calculated as follows:

Here makespan = max(20,70,160) = 160 ms

Finally the Code

Final Words

Min-Min algorithm is simple and fast, at the same time it produces a better makespan. But it considers the shortest jobs first so it fails to utilize the resources efficiently which leads to a load imbalance.

Hi, I am a final year undergraduate from KIIT Bhubaneshwar pursuing my B.Tech in Computer Science and Engineering