High Utilization Cluster
Background
A canonical scheduling problem in distributed systems is how do you use a cluster of machines efficiently. The goal is to take a set of jobs that need a certain amount of CPU and memory to run and schedule them on the cluster such that the largest amount of CPU and Memory on the cluster is utilized. The challenge fundamentally boils down to one of initial placement, deciding where a job needs to run and load-balancing, given a set of jobs running on a cluster where to move the jobs to get better efficiency.
Before VMware cluster scheduling wasn't something that was broadly available to most workloads because there was no practical way to mix different applications on the same machine without impacting performance or giving up on security and there was no practical way to move workloads between machines without disrupting the workloads.
VMware solved both of those problems with ESX and vMotion. ESX (and now ESXi) is VMware's hypervisor. A hypervisor runs on bare metal hardware and allows users to run any OS as a virtual machine on a set of virtual hardware. The amount of virtual hardware can actually exceed the amount of physical hardware. vMotion is a mechanism that allows an OS that is running to move between two machines running ESX without any disruption.
With those two capabilities it was possible to build a distributed resource scheduler that did both initial placement (where do you put a job when it arrives) and load balancing (where do you move a job while it's running to improve overall utilization). In this problem we will ask you to implement a very simple version of the DRS algorithm.
Definitions
We need to define some terms
Host= A physical machine with a certain number of CPU's and amount of Physical Memory Cluster = A collection of hosts that you can use to schedule virtual machines Virtual Machine (VM) = a virtual machine represents an OS that requires a fixed amount of CPU and Memory Virtual Machine Operation (VMOP) = an operation performed on a virtual machine. VMOP Power ON = turning a virtual machine on. When a virtual machine is running it uses CPU and Memory VMOP Power OFF = turning a virtual machine off. When a virtual machine is off it uses no CPU or Memory
Problem 1: Initial placement
In this first problem we will ask you to do initial placement of a set of virtual machines on a cluster.
The input will have the following format
VMOTIONOFF CLUSTERBEGIN hostname, CPU, Memory in MB ... CLUSTEREND VMBEGIN vmname, CPU, Memory in MB ... VMEND VMOPSBEGIN vmname, ON .. VMOPSEND
If the VMOTIONOFF tag is in the input file, do not run your load balancing algorithm. The VMOTIONOFF tag will only be used in the first problem.
The goal will be to place all of the VM's on the cluster
The output of your program will be in the following format. The vmname must be in alphabetical order.
VMNOPLACEDBEGIN vmname VMNOPLACEDEND
The first part of the file (VMPLACEDBEGIN/VMPLACEDEND) will be the name of the VM and the host it was placed on. The second part of the file (VMNOPLACEDBEGIN/VMNOPLACEDEND) will be the names of the VM's that you could not place.
Your initial placement can not consider VM's that have not yet been powered on. You can only consider the current machine.
For example with this input:
VMOTIONOFF CLUSTERBEGIN host1,5,100 host2,2,50 CLUSTEREND VMBEGIN vm1,1,50 vm2,4,20 vm3,1,80 VMEND VMOPSBEGIN vm1,ON vm3,ON vm2,ON VMOPSEND
The output would be
VMNOPLACEDBEGIN vm3 VMNOPLACEDEND
Problem 2: Initial placement with Power OFF
In Problem 1, the VM's were only powered on. In this variation a machine can be powered off. If a machine is powered off, all of its resources become available to other machines
For example with this input:
CLUSTERBEGIN host1,5,100 host2,2,50 CLUSTEREND VMBEGIN vm1,1,50 vm2,4,20 vm3,1,80 VMEND VMOPSBEGIN vm1,ON vm2,ON vm1,OFF vm3,ON VMOPSEND
The output would be:
VMNOPLACEDBEGIN VMNOPLACEDEND
Problem 3: Using vmotion
In this version of the problem we will ask you to use vMotion to load-balance across the cluster. vMotion allows you to move any VM between any two hosts. In this implementation of DRS load balancing we will ask you to choose one VM across the cluster to move between nodes to create space to power-on a VM. The goal of this problem is to be able to successfully power-on the most number of VM's. VM's will be powered on and off.
Consider this input:
CLUSTERBEGIN host1,5,100 host2,2,50 CLUSTEREND VMBEGIN vm1,1,50 vm2,4,20 vm3,1,80 VMEND VMOPSBEGIN vm1,ON vm3,ON vm2,ON VMOPSEND
The output would be
VMNOPLACEDBEGIN VMNOPLACEDEND
Using vMotion we were able to move vm1 from host1 to host2 when vm3 needed to be placed. You will notice that the utilization of the cluster improved because vm3 was also placed as compared to problem 1, where vm3 could not be powered on.
The remaining hidden problems all assume you are doing some form of load balancing between VM power ON operations. When implementing your load-balancer only consider the currently powered on VM's and the current VM that wants to power ON.
Input Format
VMOTIONOFF CLUSTERBEGIN hostname, CPU, Memory in MB ... CLUSTEREND VMBEGIN vmname, CPU, Memory in MB ... VMEND VMOPSBEGIN vmname, ON .. VMOPSEND
Output Format
VMNOPLACEDBEGIN vmname VMNOPLACEDEND
Sample Input
VMOTIONOFF CLUSTERBEGIN host1,5,100 host2,2,50 CLUSTEREND VMBEGIN vm1,1,50 vm2,4,20 vm3,1,80 VMEND VMOPSBEGIN vm1,ON vm3,ON vm2,ON VMOPSEND
Sample Output
VMNOPLACEDBEGIN vm3 VMNOPLACEDEND
Explanation
Between VMNOPLACEDBEGIN and VMNOPLACEDEND is a list of vmname's, one per line, that are alphabetically sorted.
xxxxxxxxxx
with Ada.Text_IO, Ada.Integer_Text_IO;
use Ada;
procedure Solution is
-- Enter your code here. Read input from STDIN. Print output to STDOUT
end Solution