Efficient way to allot the next available VM

Question

The method getNextAvailableVm() allots virtual machines for a particular data center in a round-robin fashion. (The integer returned by this method is the machine allotted)

In a data center there could be virtual machines with different set of configurations. For example :

5 VMs with 1024 memory
4 VMs with 512 memory

Total : 9 VMs

For this data center a machine with 1024 memory will get task 2 times as compared to machine with 512 memory.

So machines for this data center are returned by the getNextAvailableVm() in the following way :

0 0 1 1 2 2 3 3 4 4 5 6 7 8

This is the current way, the machines are being returned.But there is a problem.

There could be cases, when a particular machine is busy and cannot be allotted the task.Instead the next machine available with the highest memory must be allotted the task.I have not been able to implement this.

For example :

0 (allotted first time)
0 (to be allotted the second time)
but if 0 is busy..
allot 1 if 1 is not busy
next circle check if 0 is busy
if not busy allot 0  (only when machine numbered 0 has not handled the requests it is entitled to handle)
if busy, allot the next

cloudSimEventFired method in the following class is called when ever the machine gets freed or is allotted.

    public class TempAlgo extends VmLoadBalancer implements CloudSimEventListener {

    /**
     * Key : Name of the data center
     * Value : List of objects of class 'VmAllocationUIElement'.
     */
    private  Map<String,LinkedList<DepConfAttr>> confMap = new HashMap<String,LinkedList<DepConfAttr>>();
    private Iterator<Integer> availableVms = null;
    private DatacenterController dcc;
    private boolean sorted = false;
    private int currentVM;
    private boolean calledOnce = false;
    private boolean indexChanged = false;
    private LinkedList<Integer> busyList = new LinkedList<Integer>();

    private Map<String,LinkedList<AlgoAttr>> algoMap = new HashMap<String, LinkedList<AlgoAttr>>();
    private Map<String,AlgoHelper> map = new HashMap<String,AlgoHelper>();  
    private Map<String,Integer> vmCountMap = new HashMap<String,Integer>();

    public TempAlgo(DatacenterController dcb) {
        confMap = DepConfList.dcConfMap;
        this.dcc = dcb;
        dcc.addCloudSimEventListener(this);
        if(!this.calledOnce) {
            this.calledOnce = true;
            // Make a new map using dcConfMap that lists 'DataCenter' as a 'key' and 'LinkedList<AlgoAttr>' as 'value'.
            Set<String> keyst =DepConfList.dcConfMap.keySet();
            for(String dataCenter : keyst) {
                LinkedList<AlgoAttr> tmpList = new LinkedList<AlgoAttr>();
                LinkedList<DepConfAttr> list = dcConfMap.get(dataCenter);
                int totalVms = 0;
                for(DepConfAttr o : list) {
                    tmpList.add(new AlgoAttr(o.getVmCount(), o.getMemory()/512, 0));
                    totalVms = totalVms + o.getVmCount();
                }
                Temp_Algo_Static_Var.algoMap.put(dataCenter, tmpList);
                Temp_Algo_Static_Var.vmCountMap.put(dataCenter, totalVms);
            }
            this.algoMap = new HashMap<String, LinkedList<AlgoAttr>>(Temp_Algo_Static_Var.algoMap);
            this.vmCountMap = new HashMap<String,Integer>(Temp_Algo_Static_Var.vmCountMap);
            this.map = new HashMap<String,AlgoHelper>(Temp_Algo_Static_Var.map);
        }
    }

    @Override
    public int getNextAvailableVm() {
        synchronized(this) {
            String dataCenter = this.dcc.getDataCenterName();
            int totalVMs = this.vmCountMap.get(dataCenter);
            AlgoHelper ah = (AlgoHelper)this.map.get(dataCenter);
            int lastIndex = ah.getIndex();
            int lastCount = ah.getLastCount();
            LinkedList<AlgoAttr> list = this.algoMap.get(dataCenter);
            AlgoAttr aAtr = (AlgoAttr)list.get(lastIndex);
            indexChanged = false;
            if(lastCount < totalVMs)  {
                if(aAtr.getRequestAllocated() % aAtr.getWeightCount() == 0) {
                    lastCount = lastCount + 1;
                    this.currentVM = lastCount;
                    if(aAtr.getRequestAllocated() == aAtr.getVmCount() * aAtr.getWeightCount()) {
                        lastIndex++;
                        if(lastIndex != list.size()) {
                            AlgoAttr aAtr_N = (AlgoAttr)list.get(lastIndex);
                            aAtr_N.setRequestAllocated(1);
                            this.indexChanged = true;
                        }
                        if(lastIndex == list.size()) {
                            lastIndex = 0;
                            lastCount = 0;
                            this.currentVM = lastCount;
                            AlgoAttr aAtr_N = (AlgoAttr)list.get(lastIndex);
                            aAtr_N.setRequestAllocated(1);
                            this.indexChanged = true;

                        }
                    }
                }
                if(!this.indexChanged) {
                    aAtr.setRequestAllocated(aAtr.getRequestAllocated() + 1);
                }

                this.map.put(dataCenter, new AlgoHelper(lastIndex, lastCount)); 

                //System.out.println("Current VM : " + this.currentVM + " for data center : " + dataCenter);
                return this.currentVM;
            }}

            System.out.println("--------Before final return statement---------");
            return 0;

    }   

    @Override
    public void cloudSimEventFired(CloudSimEvent e) {
        if(e.getId() == CloudSimEvents.EVENT_CLOUDLET_ALLOCATED_TO_VM) {
            int vmId = (Integer) e.getParameter(Constants.PARAM_VM_ID);
                    busyList.add(vmId);

            System.out.println("+++++++++++++++++++Machine with vmID : " + vmId + " attached");
        }else if(e.getId() == CloudSimEvents.EVENT_VM_FINISHED_CLOUDLET) {
            int vmId = (Integer) e.getParameter(Constants.PARAM_VM_ID);
                            busyList.remove(vmId);
            //System.out.println("+++++++++++++++++++Machine with vmID : " + vmId + " freed");
        }
    }
}

In the above code, all the lists are already sorted with the highest memory first.The whole idea is to balance the memory by allocating more tasks to a machine with higher memory.

Each time a machine is allotted request allocated is incremented by one.Each set of machines have a weight count attached to it, which is calculated by dividing memory_allotted by 512.

The method getNextAvailableVm() is called by multiple threads at a time. For 3 Data Centers 3 threads will simultaneously call getNextAva...() but on different class objects.The data center returned by the statement this.dcc.getDataCenterName() in the same method is returned according to the data center broker policy selected earlier.

How do I make sure that the machine I am currently returning is free and if the machine is not free I allot the next machine with highest memory available.I also have to make sure that the machine that is entitled to process X tasks, does process X tasks even that machine is currently busy.

This is a general description of the data structure used here :

The code of this class is hosted here on github.

This is the link for the complete project on github.

Most of the data structures/classes used here are inside this package

Answer 1

Perhaps you are over thinking the problem. A simple strategy is to have a broker which is aware of all the pending tasks. Each task worker or thread asks the broker for a new message/task to work on. The broker gives out work in the order it was asked for. This is how JMS queues works. For the JVMs which can handle two tasks you can start two threads.

There is many standard JMS which do this but I suggest looking at ActiveMQ as it is simple to get started with.

note in you case, a simpler solution is to have one machine with 8 GB of memory. You can buy 8 GB for a server for very little ($40 - $150 depending on vendor) and it will be used more efficiently in one instance by sharing resource. I assume you are looking at much larger instances. Instances smaller than 8 GB are better off just upgrading it.

How do I make sure that the machine I am currently returning is free

This is your scenario, if you don't know how to tell if a machine is free, I don't see how anyone would have more knowledge of you application.

and if the machine is not free I allot the next machine with highest memory available.

You need to look at the free machines and pick the one with the most available memory. I don't see what the catch is here other than doing what you have stated.

I also have to make sure that the machine that is entitled to process X tasks, does process X tasks even that machine is currently busy.

You need a data source or store for this information. What is allowed to run where. In JMS you would have multiple queues and only pass certain queues to the machines which can process those queue.