From 47c7c50288ca3447c0d50e39ccffc0a97e2c179f Mon Sep 17 00:00:00 2001 From: Andreas Egger Date: Tue, 21 May 2013 19:19:40 +0200 Subject: [PATCH] Implemented Scheduler A and utility classes --- src/at/ac/tuwien/lsdc/SchedSimulator.java | 6 +- .../ActiveApplicationsException.java | 8 ++ .../lsdc/exception/VMsRunningException.java | 8 ++ .../lsdc/management/MachineManager.java | 65 +++++++++- .../tuwien/lsdc/sched/AbstractScheduler.java | 65 ++++++++-- src/at/ac/tuwien/lsdc/sched/SchedulerA.java | 113 +++++++++++++++++- src/at/ac/tuwien/lsdc/sched/SchedulerB.java | 4 +- src/at/ac/tuwien/lsdc/sched/SchedulerC.java | 4 +- .../ac/tuwien/lsdc/types/PhysicalMachine.java | 50 +++++--- .../tuwien/lsdc/types/SortedApplication.java | 38 ++++++ .../lsdc/types/SortedPhysicalMachine.java | 32 +++++ .../ac/tuwien/lsdc/types/VirtualMachine.java | 17 ++- 12 files changed, 371 insertions(+), 39 deletions(-) create mode 100644 src/at/ac/tuwien/lsdc/exception/ActiveApplicationsException.java create mode 100644 src/at/ac/tuwien/lsdc/exception/VMsRunningException.java create mode 100644 src/at/ac/tuwien/lsdc/types/SortedApplication.java create mode 100644 src/at/ac/tuwien/lsdc/types/SortedPhysicalMachine.java diff --git a/src/at/ac/tuwien/lsdc/SchedSimulator.java b/src/at/ac/tuwien/lsdc/SchedSimulator.java index 83256c0..90bc3e6 100644 --- a/src/at/ac/tuwien/lsdc/SchedSimulator.java +++ b/src/at/ac/tuwien/lsdc/SchedSimulator.java @@ -57,11 +57,11 @@ public class SchedSimulator { AbstractScheduler scheduler; switch (schedulerType) { case A: - scheduler = new SchedulerA(schedulerLog,schedulerType,scenario); + scheduler = new SchedulerA(schedulerLog, schedulerType, scenario, numPMs, numCloudPartners); case B: - scheduler = new SchedulerB(schedulerLog,schedulerType,scenario); + scheduler = new SchedulerB(schedulerLog, schedulerType, scenario, numPMs, numCloudPartners); default: - scheduler = new SchedulerC(schedulerLog,schedulerType,scenario); + scheduler = new SchedulerC(schedulerLog, schedulerType, scenario, numPMs, numCloudPartners); } ScenarioData data = scheduler.initAndStart(apps); CSVLogger logger = new CSVLogger(generalLog); diff --git a/src/at/ac/tuwien/lsdc/exception/ActiveApplicationsException.java b/src/at/ac/tuwien/lsdc/exception/ActiveApplicationsException.java new file mode 100644 index 0000000..1de3c8d --- /dev/null +++ b/src/at/ac/tuwien/lsdc/exception/ActiveApplicationsException.java @@ -0,0 +1,8 @@ +package at.ac.tuwien.lsdc.exception; + +public class ActiveApplicationsException extends Exception { + + public ActiveApplicationsException(String msg) { + super(msg); + } +} diff --git a/src/at/ac/tuwien/lsdc/exception/VMsRunningException.java b/src/at/ac/tuwien/lsdc/exception/VMsRunningException.java new file mode 100644 index 0000000..113e7ee --- /dev/null +++ b/src/at/ac/tuwien/lsdc/exception/VMsRunningException.java @@ -0,0 +1,8 @@ +package at.ac.tuwien.lsdc.exception; + +public class VMsRunningException extends Exception { + + public VMsRunningException(String message) { + super(message); + } +} diff --git a/src/at/ac/tuwien/lsdc/management/MachineManager.java b/src/at/ac/tuwien/lsdc/management/MachineManager.java index 49bf340..133faa7 100644 --- a/src/at/ac/tuwien/lsdc/management/MachineManager.java +++ b/src/at/ac/tuwien/lsdc/management/MachineManager.java @@ -1,16 +1,75 @@ package at.ac.tuwien.lsdc.management; +import java.util.Collection; import java.util.HashMap; +import java.util.List; +import at.ac.tuwien.lsdc.exception.VMsRunningException; import at.ac.tuwien.lsdc.types.PhysicalMachine; +/** + * This class is responsible to start and stop PMs & VMs + * also it will be used to put an application on a VM + * move an application and get utilization data + * + */ public class MachineManager { - // this class is responsible to start and stop PMs & VMs - // also it will be used to put an application on a VM - // move an application and get utilization data private HashMap PMs = new HashMap(); + + private int maxPMs; + + public MachineManager(int maxPMs) { + this.maxPMs = maxPMs; + } + + + /** + * Start a physical machine + * @return the PM that was started, null if all machines already running + */ + public PhysicalMachine startPhysicalMachine() { + if(PMs.size() < maxPMs) { + PhysicalMachine pm = new PhysicalMachine(); + PMs.put(pm.getId(), pm); + pm.start(); + return pm; + } + return null; + } + + /** + * Stops a physical machine with the given id + * @param id the id of the PM to stop + * @throws VMsRunningException is thrown when there are still VMs running on this PM + */ + public void stopPhysicalMachine(int id) throws VMsRunningException { + if(PMs.containsKey(id)) { + PMs.get(id).stop(); + PMs.remove(id); + } + } + + /** + * Returns all running physical machines + * @return the currently active PMs + */ + public Collection getPMs () { + return PMs.values(); + } + + /** + * Returns the maximum number of available physical machines + * @return the maximum number of PMs + */ + public int getMaxPMs() { + return maxPMs; + } + /** + * Gets the total power consumption summed up from each PM + * @return the total power consumption + */ public double getTotalConsumption() { double consumption = 0; for (PhysicalMachine pm : PMs.values()) { diff --git a/src/at/ac/tuwien/lsdc/sched/AbstractScheduler.java b/src/at/ac/tuwien/lsdc/sched/AbstractScheduler.java index 7c336de..4a9f84e 100644 --- a/src/at/ac/tuwien/lsdc/sched/AbstractScheduler.java +++ b/src/at/ac/tuwien/lsdc/sched/AbstractScheduler.java @@ -10,12 +10,16 @@ import java.util.Map; import org.slf4j.Logger; import org.slf4j.LoggerFactory; +import at.ac.tuwien.lsdc.federation.Federation; +import at.ac.tuwien.lsdc.management.MachineManager; import at.ac.tuwien.lsdc.types.Application; import at.ac.tuwien.lsdc.types.ScenarioData; import at.ac.tuwien.lsdc.types.ScenarioType; import at.ac.tuwien.lsdc.types.SchedulerData; import at.ac.tuwien.lsdc.types.SchedulerEvent; +import at.ac.tuwien.lsdc.types.SchedulerEvent.EventType; import at.ac.tuwien.lsdc.types.SchedulerType; +import at.ac.tuwien.lsdc.types.VirtualMachine.VMType; import at.ac.tuwien.lsdc.util.CSVLogger; public abstract class AbstractScheduler { @@ -31,13 +35,21 @@ public abstract class AbstractScheduler { protected int numCurrInSourced; protected int numCurrOutSourced; - File schedulerLog; - CSVLogger logger; + protected MachineManager machineManager; + protected Federation federation; + protected File schedulerLog; + protected CSVLogger logger; + protected VMType VMType; // this map saves the following Type of Events: // start of an Application, end of an Application // (start outSourced, end outSourced, start inSourced, end inSourced) protected HashMap> eventMap; + +// // this map saves the following Type of Events: +// // start of an Application, end of an Application +// // (start outSourced, end outSourced, start inSourced, end inSourced) +// protected HashMap> endEventMap; // Scheduler has an internal Time "Abstraction" // at every point in time it checks for Events in his "EventList" @@ -48,10 +60,12 @@ public abstract class AbstractScheduler { // it is updated with every added "EndEvent" protected long endTime; - public AbstractScheduler(File schedulerLog, SchedulerType schedulerType, ScenarioType scenario) throws IOException { + public AbstractScheduler(File schedulerLog, SchedulerType schedulerType, ScenarioType scenario, int numPMs, int numCloudPartners) throws IOException { this.schedulerLog = schedulerLog; this.schedulerType = schedulerType; this.scenario = scenario; + this.machineManager = new MachineManager(numPMs); + this.federation = new Federation(numCloudPartners); this.eventMap = new HashMap>(); this.logger = new CSVLogger(schedulerLog); } @@ -59,10 +73,9 @@ public abstract class AbstractScheduler { // Initialize Scheduler with Data from CSV // CSV will be parsed and sent as List to Scheduler public ScenarioData initAndStart(LinkedList apps) { - for (Application a : apps) { - //System.out.println(a); - // read start timestamp - // save event in map + for (Application app : apps) { + insertStartEvent(app.getTimestamp(), app); + insertStopEvent(app.getTimestamp() + app.getDuration(), app); } startScheduling(); try { @@ -72,6 +85,43 @@ public abstract class AbstractScheduler { } return doEndLogging(); } + + /** + * Insert a start event into the map, at timestamp when the application should start + * @param timestamp the timestamp when the application should start + * @param app the application to start + */ + private void insertStartEvent(long timestamp, Application app) { + SchedulerEvent evt = new SchedulerEvent(timestamp, EventType.startApplication, app); + if(!eventMap.containsKey(timestamp)) { + LinkedList list = new LinkedList(); + list.add(evt); + eventMap.put(timestamp, list); + } else { + LinkedList list = eventMap.get(timestamp); + list.add(evt); + } + } + + /** + * Insert a stop event into the map, at timestamp when the application should stop + * @param timestamp the timestamp when the application should stop + * @param app the application to stop + */ + private void insertStopEvent(long timestamp, Application app) { + SchedulerEvent evt = new SchedulerEvent(timestamp, EventType.endApplication, app); + if(!eventMap.containsKey(timestamp)) { + LinkedList list = new LinkedList(); + list.add(evt); + eventMap.put(timestamp, list); + } else { + LinkedList list = eventMap.get(timestamp); + list.add(evt); + } + if(endTime < timestamp) { + endTime = timestamp; + } + } protected void startScheduling() { while (true) { @@ -79,6 +129,7 @@ public abstract class AbstractScheduler { handleEvents(events); doStateLogging(); //advance Time to next Event + currTime++; if (currTime == endTime) { // reached last Event, Scheduler will shut down break; diff --git a/src/at/ac/tuwien/lsdc/sched/SchedulerA.java b/src/at/ac/tuwien/lsdc/sched/SchedulerA.java index 91588d2..4ce79c9 100644 --- a/src/at/ac/tuwien/lsdc/sched/SchedulerA.java +++ b/src/at/ac/tuwien/lsdc/sched/SchedulerA.java @@ -2,23 +2,130 @@ package at.ac.tuwien.lsdc.sched; import java.io.File; import java.io.IOException; +import java.util.Iterator; import java.util.LinkedList; +import java.util.List; +import org.slf4j.Logger; +import org.slf4j.LoggerFactory; + +import edu.emory.mathcs.backport.java.util.Collections; + +import at.ac.tuwien.lsdc.exception.ActiveApplicationsException; +import at.ac.tuwien.lsdc.types.Application; +import at.ac.tuwien.lsdc.types.PhysicalMachine; import at.ac.tuwien.lsdc.types.ScenarioType; import at.ac.tuwien.lsdc.types.SchedulerEvent; +import at.ac.tuwien.lsdc.types.SchedulerEvent.EventType; import at.ac.tuwien.lsdc.types.SchedulerType; +import at.ac.tuwien.lsdc.types.SortedApplication; +import at.ac.tuwien.lsdc.types.SortedPhysicalMachine; +import at.ac.tuwien.lsdc.types.VirtualMachine; public class SchedulerA extends AbstractScheduler { - public SchedulerA(File logFile, SchedulerType schedulerType, ScenarioType scenario) throws IOException { - super(logFile, schedulerType, scenario); + private static final Logger log = LoggerFactory.getLogger(SchedulerA.class); + + public SchedulerA(File logFile, SchedulerType schedulerType, ScenarioType scenario, int numPMs, int numCloudPartners) throws IOException { + super(logFile, schedulerType, scenario, numPMs, numCloudPartners); + this.VMType = VMType.NonResizable; } @Override protected void handleEvents(LinkedList events) { - // TODO Auto-generated method stub + for(SchedulerEvent evt : events) { + if(evt.getType() == EventType.endApplication) { + VirtualMachine vm = evt.getApp().getRunningOn(); + vm.stopApplication(evt.getApp()); + PhysicalMachine pm = vm.getRunningOn(); + try { + pm.stopVirtualMachine(vm); + } catch (ActiveApplicationsException e) { + log.warn("VM "+vm.getId()+"could not be stopped, "+e.getMessage()); + } + } + } + + // sorting applications by amount of resources (descending) + List sortedApps = sortApps(events); + + for(Iterator iter = sortedApps.iterator(); iter.hasNext(); ) { + boolean appDeployed = false; + Application app = iter.next().getApp(); + + if(machineManager.getPMs().size() == 0) { + PhysicalMachine pm = machineManager.startPhysicalMachine(); + boolean enoughResources = pm.checkVM(app.getSize(), app.getRam(), app.getCpu()); + + if(enoughResources) { + pm.startVirtualMachine(app.getSize(), app.getRam(), app.getCpu(), VMType); + appDeployed = true; + log.debug("Application "+app.toString()+" started on new pm "+pm.getId()); + } + else { + log.warn("Application "+app.toString()+" cannot be run on empty pm "+pm.getId()); + } + } + else { + // sorting physical machines by resource utilization (descending) + List sortedPMs = sortPMs(); + + for(Iterator it = sortedPMs.iterator(); iter.hasNext(); ) { + PhysicalMachine pm = it.next().getPm(); + boolean enoughResources = pm.checkVM(app.getSize(), app.getRam(), app.getCpu()); + + if(enoughResources) { + VirtualMachine vm = pm.startVirtualMachine(app.getSize(), app.getRam(), app.getCpu(), VMType); + vm.startApplication(app); + appDeployed = true; + log.debug("Application "+app.toString()+" started on new pm "+pm.getId()); + break; + } + } + if(!appDeployed && (machineManager.getPMs().size() < machineManager.getMaxPMs())) { + + PhysicalMachine pm = machineManager.startPhysicalMachine(); + boolean enoughResources = pm.checkVM(app.getSize(), app.getRam(), app.getCpu()); + + if(enoughResources) { + VirtualMachine vm = pm.startVirtualMachine(app.getSize(), app.getRam(), app.getCpu(), VMType); + vm.startApplication(app); + appDeployed = true; + log.debug("Application "+app.toString()+" started on new pm "+pm.getId()); + } + else { + log.warn("Application "+app.toString()+" cannot be run on empty pm "+pm.getId()); + } + } + } + if(!appDeployed) + log.warn("Application "+app.toString()+" could not be deployed on any pm"); + } + } + + // sorting applications by amount of resources (descending) + private List sortApps(LinkedList events) { + List sortedApps = new LinkedList(); + for(SchedulerEvent evt : events) { + if(evt.getType() == EventType.startApplication) + sortedApps.add(new SortedApplication(evt.getApp())); + } + Collections.sort(sortedApps); + Collections.reverse(sortedApps); + return sortedApps; + } + + // sorting physical machines by resource utilization (descending) + private List sortPMs() { + List sortedPMs = new LinkedList(); + for(PhysicalMachine pm : machineManager.getPMs()) + sortedPMs.add(new SortedPhysicalMachine(pm)); + + Collections.sort(sortedPMs); + Collections.reverse(sortedPMs); + return sortedPMs; } } diff --git a/src/at/ac/tuwien/lsdc/sched/SchedulerB.java b/src/at/ac/tuwien/lsdc/sched/SchedulerB.java index 4e54be1..892067a 100644 --- a/src/at/ac/tuwien/lsdc/sched/SchedulerB.java +++ b/src/at/ac/tuwien/lsdc/sched/SchedulerB.java @@ -11,8 +11,8 @@ import at.ac.tuwien.lsdc.types.SchedulerType; public class SchedulerB extends AbstractScheduler { - public SchedulerB(File logFile, SchedulerType schedulerType, ScenarioType scenario) throws IOException { - super(logFile, schedulerType, scenario); + public SchedulerB(File logFile, SchedulerType schedulerType, ScenarioType scenario, int numPMs, int numCloudPartners) throws IOException { + super(logFile, schedulerType, scenario, numPMs, numCloudPartners); } @Override diff --git a/src/at/ac/tuwien/lsdc/sched/SchedulerC.java b/src/at/ac/tuwien/lsdc/sched/SchedulerC.java index cc21496..910886c 100644 --- a/src/at/ac/tuwien/lsdc/sched/SchedulerC.java +++ b/src/at/ac/tuwien/lsdc/sched/SchedulerC.java @@ -11,8 +11,8 @@ import at.ac.tuwien.lsdc.types.SchedulerType; public class SchedulerC extends AbstractScheduler { - public SchedulerC(File logFile, SchedulerType schedulerType, ScenarioType scenario) throws IOException { - super(logFile,schedulerType,scenario); + public SchedulerC(File logFile, SchedulerType schedulerType, ScenarioType scenario, int numPMs, int numCloudPartners) throws IOException { + super(logFile, schedulerType, scenario, numPMs, numCloudPartners); } @Override diff --git a/src/at/ac/tuwien/lsdc/types/PhysicalMachine.java b/src/at/ac/tuwien/lsdc/types/PhysicalMachine.java index 9489797..9de683f 100644 --- a/src/at/ac/tuwien/lsdc/types/PhysicalMachine.java +++ b/src/at/ac/tuwien/lsdc/types/PhysicalMachine.java @@ -2,6 +2,10 @@ package at.ac.tuwien.lsdc.types; import java.util.HashMap; +import at.ac.tuwien.lsdc.exception.ActiveApplicationsException; +import at.ac.tuwien.lsdc.exception.VMsRunningException; +import at.ac.tuwien.lsdc.types.VirtualMachine.VMType; + public class PhysicalMachine { private static int count = 0; @@ -36,9 +40,10 @@ public class PhysicalMachine { running = true; } - public void stop() { - // TODO: anything else we need to do? maybe implement a stop method in - // VirtualMachine and call it on every VM + public void stop() throws VMsRunningException { + if(VMs.size() > 0) + throw new VMsRunningException("PM cannot be stopped. Some VMs still running"); + VMs = new HashMap(); size = 0; RAM = 0; @@ -47,38 +52,35 @@ public class PhysicalMachine { } public double getConsumption() { - return 200 + 0.3 * CPU; + return 200 + 0.3 * (CPU - initialCPU); } - public int startVirtualMachine(int size, int RAM, int CPU) { - if (checkVM(size, RAM, CPU)) { - VirtualMachine vm = new VirtualMachine(size, RAM, CPU, this); + public VirtualMachine startVirtualMachine(int sz, int ram, int cpu, VMType type) { + if (checkVM(sz, ram, cpu)) { + VirtualMachine vm = new VirtualMachine(sz, ram, cpu, this, type); VMs.put(vm.getId(), vm); size = size + vm.getSize(); RAM = RAM + vm.getRAM(); CPU = CPU + vm.getCPU(); - return vm.getId(); + return vm; } else - return -1; + return null; } - public boolean stopVirtualMachine(VirtualMachine vm) { + public void stopVirtualMachine(VirtualMachine vm) throws ActiveApplicationsException { if (VMs.containsKey(vm.getId())) { if (vm.getApplications().size() != 0) { - // apps must be migrated before stopping a VM - return false; + throw new ActiveApplicationsException("Applications must be migrated before stopping a vm, vm id "+vm.getId()); } else { VMs.remove(vm.getId()); size = size - vm.getSize(); RAM = RAM - vm.getRAM(); CPU = CPU - vm.getCPU(); - return true; } - } else - return false; + } } - private boolean checkVM(int size, int RAM, int CPU) { + public boolean checkVM(int size, int RAM, int CPU) { return (size <= availableSize()) && (RAM <= availableRAM()) && (CPU <= availableCPU()); } @@ -94,6 +96,22 @@ public class PhysicalMachine { private int availableCPU() { return maxCPU - CPU; } + + public double getSizeUtilization() { + return ((double)(size - initialSize) / (maxSize - initialSize)) * 100; + } + + public double getRamUtilization() { + return ((double)(RAM - initialRAM) / (maxRAM - initialRAM)) * 100; + } + + public double getCpuUtilization() { + return ((double)(CPU - initialCPU) / (maxCPU - initialCPU)) * 100; + } + + public double getAverageUtilization() { + return (getSizeUtilization() + getRamUtilization() + getCpuUtilization()) / 3.0; + } public int getId() { return id; diff --git a/src/at/ac/tuwien/lsdc/types/SortedApplication.java b/src/at/ac/tuwien/lsdc/types/SortedApplication.java new file mode 100644 index 0000000..ff052a3 --- /dev/null +++ b/src/at/ac/tuwien/lsdc/types/SortedApplication.java @@ -0,0 +1,38 @@ +package at.ac.tuwien.lsdc.types; + +public class SortedApplication implements Comparable { + + + private Application app; + final int BEFORE = -1; + final int EQUAL = 0; + final int AFTER = 1; + + public SortedApplication(Application app) { + this.app = app; + } + + @Override + public int compareTo(SortedApplication other) { + if (this == other) + return EQUAL; + + if(getResourceDifference(other) < 0) + return BEFORE; + else if(getResourceDifference(other) > 0) + return AFTER; + else + return EQUAL; + } + + public Application getApp() { + return app; + } + + public int getResourceDifference(SortedApplication other) { + return app.getSize() - other.getApp().getSize() + + app.getRam() - other.getApp().getRam() + + app.getCpu() - other.getApp().getCpu(); + } + +} diff --git a/src/at/ac/tuwien/lsdc/types/SortedPhysicalMachine.java b/src/at/ac/tuwien/lsdc/types/SortedPhysicalMachine.java new file mode 100644 index 0000000..6d61fbf --- /dev/null +++ b/src/at/ac/tuwien/lsdc/types/SortedPhysicalMachine.java @@ -0,0 +1,32 @@ +package at.ac.tuwien.lsdc.types; + +public class SortedPhysicalMachine implements Comparable { + + private PhysicalMachine pm; + final int BEFORE = -1; + final int EQUAL = 0; + final int AFTER = 1; + + public SortedPhysicalMachine(PhysicalMachine pm) { + this.pm = pm; + } + + @Override + public int compareTo(SortedPhysicalMachine other) { + if(this == other) + return EQUAL; + + if(pm.getAverageUtilization() < other.getPm().getAverageUtilization()) + return BEFORE; + else if(pm.getAverageUtilization() > other.getPm().getAverageUtilization()) + return AFTER; + else + return EQUAL; + } + + + public PhysicalMachine getPm() { + return pm; + } + +} diff --git a/src/at/ac/tuwien/lsdc/types/VirtualMachine.java b/src/at/ac/tuwien/lsdc/types/VirtualMachine.java index 766e55c..ae9c680 100644 --- a/src/at/ac/tuwien/lsdc/types/VirtualMachine.java +++ b/src/at/ac/tuwien/lsdc/types/VirtualMachine.java @@ -5,6 +5,11 @@ import java.util.HashMap; public class VirtualMachine { + public enum VMType { + Resizable, NonResizable + } + + private static int count = 0; private PhysicalMachine runningOn; @@ -20,18 +25,24 @@ public class VirtualMachine { private int size; private int RAM; private int CPU; + + private VMType type; - public VirtualMachine(int size, int RAM, int CPU, PhysicalMachine pm) { + public VirtualMachine(int size, int RAM, int CPU, PhysicalMachine pm, VMType type) { this.id = count; count++; this.size = size + initialSize; this.RAM = RAM + initialRAM; this.CPU = CPU + initialCPU; this.runningOn = pm; + this.type = type; } public boolean startApplication(Application app) { - if (checkApp(app)) { + if (enoughResources(app)) { + applications.put(app.getID(), app); + return true; + } else if (type == VMType.Resizable && runningOn.checkVM(app.getSize(), app.getRam(), app.getCpu())) { applications.put(app.getID(), app); size = size + app.getSize(); RAM = RAM + app.getRam(); @@ -52,7 +63,7 @@ public class VirtualMachine { return false; } - private boolean checkApp(Application app) { + private boolean enoughResources(Application app) { return (app.getSize() <= availableSize()) && (app.getRam() <= availableRAM()) && (app.getCpu() <= availableCPU()); -- 2.43.0