Submissions will no longer be placed on the leaderboard. You may still attempt this problem for practice.

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.

Line: 1 Col: 1
  1. Challenge Walkthrough
    Let's walk through this sample challenge and explore the features of the code editor.1 of 6
  2. Review the problem statement
    Each challenge has a problem statement that includes sample inputs and outputs. Some challenges include additional information to help you out.2 of 6
  3. Choose a language
    Select the language you wish to use to solve this challenge.3 of 6
  4. Enter your code
    Code your solution in our custom editor or code in your own environment and upload your solution as a file.4 of 6
  5. Test your code
    You can compile your code and test it for errors and accuracy before submitting.5 of 6
  6. Submit to see results
    When you're ready, submit your solution! Remember, you can go back and refine your code anytime.6 of 6
  1. Check your score