/*
 * Title:        CloudSim Toolkit
 * Description:  CloudSim (Cloud Simulation) Toolkit for Modeling and Simulation of Clouds
 * Licence:      GPL - http://www.gnu.org/copyleft/gpl.html
 *
 * Copyright (c) 2009-2012, The University of Melbourne, Australia
 */

package org.cloudbus.cloudsim.power;

import java.util.*;

import org.apache.commons.math3.analysis.function.Pow;
import org.cloudbus.cloudsim.Host;
import org.cloudbus.cloudsim.HostDynamicWorkload;
import org.cloudbus.cloudsim.Log;
import org.cloudbus.cloudsim.Vm;
import org.cloudbus.cloudsim.core.CloudSim;
import org.cloudbus.cloudsim.power.lists.PowerVmList;
import org.cloudbus.cloudsim.util.ExecutionTimeMeasurer;

/**
 * An abstract power-aware VM allocation policy that dynamically optimizes the VM
 * allocation (placement) using migration.
 * 
 * <br/>If you are using any algorithms, policies or workload included in the power package please cite
 * the following paper:<br/>
 * 
 * <ul>
 * <li><a href="http://dx.doi.org/10.1002/cpe.1867">Anton Beloglazov, and Rajkumar Buyya, "Optimal Online Deterministic Algorithms and Adaptive
 * Heuristics for Energy and Performance Efficient Dynamic Consolidation of Virtual Machines in
 * Cloud Data Centers", Concurrency and Computation: Practice and Experience (CCPE), Volume 24,
 * Issue 13, Pages: 1397-1420, John Wiley & Sons, Ltd, New York, USA, 2012</a>
 * </ul>
 *
 * 我们在编写VM迁移方面的自定义逻辑时，就是修改optimizeAllocation（）方法的内容，而该方法由相关方法组合而成，包括：
 *
 * 寻找迁出主机相关方法：isHostOverUtilized()、getOverUtilizedHosts()、getUnderUtilizedHost()等；
 *
 * 从迁出主机上选择VM：getVmsToMigrateFromHosts()、getVmsToMigrateFromUnderUtilizedHost()，
 * 同时涉及到PowerVmSelectionPolicy类的二次开发。
 *
 * 为迁出的VM选择迁入主机：getNewVmPlacement（vmsToMigrate, excludedHosts）、
 * getMigrationMapFromUnderUtilizedHosts()以及最核心的findHostForVm(vm, excludedHosts)
 *
 * @author Anton Beloglazov
 * @since CloudSim Toolkit 3.0
 */
public abstract class PowerVmAllocationPolicyMigrationAbstract extends PowerVmAllocationPolicyAbstract {

	/** The vm selection policy. */
	//采用虚拟机选择策略
	private PowerVmSelectionPolicy vmSelectionPolicy;

	/** A list of maps between a VM and the host where it is place.
         * @todo This list of map is implemented in the worst way.
         * It should be used just a Map<Vm, Host> to find out 
         * what PM is hosting a given VM.
         */
	private final List<Map<String, Object>> savedAllocation = new ArrayList<Map<String, Object>>();
	//存储vm -> host的映射列表
	/** A map of CPU utilization history (in percentage) for each host,
         where each key is a host id and each value is the CPU utilization percentage history.
	 每个主机的CPU利用率历史图(百分比)，其中每个键是一个主机id，每个值是CPU利用率历史百分比。
	 	cpu的历史利用率
	 */
	private final Map<Integer, List<Double>> utilizationHistory = new HashMap<Integer, List<Double>>();

	/** 
         * The metric history. 
         * @todo the map stores different data. Sometimes it stores the upper threshold,
         * other it stores utilization threshold or predicted utilization, that
         * is very confusing.
         */
	private final Map<Integer, List<Double>> metricHistory = new HashMap<Integer, List<Double>>();

	/** The time when entries in each history list was added. 
         * All history lists are updated at the same time.
         */
	private final Map<Integer, List<Double>> timeHistory = new HashMap<Integer, List<Double>>();

	/** The history of time spent in VM selection 
         * every time the optimization of VM allocation method is called. 
         * @see #optimizeAllocation(java.util.List) 
         */
	private final List<Double> executionTimeHistoryVmSelection = new LinkedList<Double>();

	/** The history of time spent in host selection 
         * every time the optimization of VM allocation method is called. 
         * @see #optimizeAllocation(java.util.List) 
         */
	private final List<Double> executionTimeHistoryHostSelection = new LinkedList<Double>();

	/** The history of time spent in VM reallocation 
         * every time the optimization of VM allocation method is called. 
         * @see #optimizeAllocation(java.util.List) 
         */
	private final List<Double> executionTimeHistoryVmReallocation = new LinkedList<Double>();

	/** The history of total time spent in every call of the 
         * optimization of VM allocation method. 
         * @see #optimizeAllocation(java.util.List) 
         */
	private final List<Double> executionTimeHistoryTotal = new LinkedList<Double>();

	/**
	 * Instantiates a new PowerVmAllocationPolicyMigrationAbstract.
	 * 
	 * @param hostList the host list
	 * @param vmSelectionPolicy the vm selection policy
	 */
	public PowerVmAllocationPolicyMigrationAbstract(
			List<? extends Host> hostList,
			PowerVmSelectionPolicy vmSelectionPolicy) {
		super(hostList);
		setVmSelectionPolicy(vmSelectionPolicy);
	}

	/**
	 * Optimize allocation of the VMs according to current utilization.
	 * 
	 * @param vmList the vm list
	 * 
	 * @return the array list< hash map< string, object>>
	 *     optimizeAllocation-该方法的过程大致是：先调用getOverUtilizedHosts()获取过载的主机
	 *     再调用getVmsToMigrateFromHosts(overhosts)从这些过载主机上获取适合被迁出的VM列表，
	 *     然后调用getNewVmPlacement(vmsToMigrate, overUtilizedHosts）来进行过载主机上上的VM迁移（填写迁移列表migrationMap），
	 *     再接着调用getMigrationMapFromUnderUtilizedHosts()来进行“过闲”主机上的VM迁移（补充迁移列表migrationMap）；
	 *     该函数中没有实际迁移VM，没有修改全局的savedAllocation，最终该函数返回迁移列表migrationMap。
	 */
	@Override
	public List<Map<String, Object>> optimizeAllocation(List<? extends Vm> vmList) {
		ExecutionTimeMeasurer.start("optimizeAllocationTotal");

		ExecutionTimeMeasurer.start("optimizeAllocationHostSelection");
		List<PowerHostUtilizationHistory> overUtilizedHosts = getOverUtilizedHosts();//获取过载的主机
//		if (overUtilizedHosts.size() > 1){
//			int a = overUtilizedHosts.size();
//			System.out.println(a);
//		}
		getExecutionTimeHistoryHostSelection().add(
				ExecutionTimeMeasurer.end("optimizeAllocationHostSelection"));

		printOverUtilizedHosts(overUtilizedHosts);

		saveAllocation();

		ExecutionTimeMeasurer.start("optimizeAllocationVmSelection");
		List<? extends Vm> vmsToMigrate = getVmsToMigrateFromHosts(overUtilizedHosts);//从这些过载主机上获取适合被迁出的VM列表
		getExecutionTimeHistoryVmSelection().add(ExecutionTimeMeasurer.end("optimizeAllocationVmSelection"));

		Log.printLine("Reallocation of VMs from the over-utilized hosts:");
		ExecutionTimeMeasurer.start("optimizeAllocationVmReallocation");
		List<Map<String, Object>> migrationMap = getNewVmPlacement(vmsToMigrate, new HashSet<Host>(
				overUtilizedHosts));//来进行过载主机上上的VM迁移（填写迁移列表migrationMap）
		getExecutionTimeHistoryVmReallocation().add(
				ExecutionTimeMeasurer.end("optimizeAllocationVmReallocation"));
		Log.printLine();

		migrationMap.addAll(getMigrationMapFromUnderUtilizedHosts(overUtilizedHosts));
		//调用getMigrationMapFromUnderUtilizedHosts()来进行“过闲”主机上的VM迁移（补充迁移列表migrationMap）
		restoreAllocation();

		getExecutionTimeHistoryTotal().add(ExecutionTimeMeasurer.end("optimizeAllocationTotal"));

		return migrationMap;//迁移列表
	}

	/**
	 * Gets the migration map from under utilized hosts.
	 * 
	 * @param overUtilizedHosts the over utilized hosts
	 * @return the migration map from under utilized hosts
	 * getMigrationMapFromUnderUtilizedHosts----该方法的功能是返回一个migrationMap，是制定从“过闲”主机上迁移VM到其它主机的迁移方案。
	 * 	 * 传入参数是过载主机列表（有点奇怪），但其作用是作为“被排除元素”，
	 * 即VM不会从上面被迁出（因为该函数只处理“过闲”主机）和迁入（这是自然）。
	 * 该方法的过程大致是：先建立两个excluded列表（不可迁出列表、不可迁入列表），
	 * 两个列表都初始化为过载主机+关闭的主机；接下来该方法循环调用getUnderUtilizedHost()方法来获得“过闲”主机对象，
	 * 并调用getVmsToMigrateFromUnderUtilizedHost(underUtilHost)方法获得该主机上适合迁移的VM对象，
	 * 再调用getNewVmPlacementFromUnderUtilizedHost(vm, 不可迁入列表)来获得最终的调度方案并加入migrationMap中。
	 * 值得一提的是，每个“过闲”主机只被处理一次就被放进不可迁出列表，即一台主机只能最多迁出一台VM。
	 */
	protected List<Map<String, Object>> getMigrationMapFromUnderUtilizedHosts(List<PowerHostUtilizationHistory> overUtilizedHosts){
		List<Map<String, Object>> migrationMap = new LinkedList<Map<String, Object>>();
		List<PowerHost> switchedOffHosts = getSwitchedOffHosts();

		// over-utilized hosts + hosts that are selected to migrate VMs to from over-utilized hosts
		//不可迁出列表
		Set<PowerHost> excludedHostsForFindingUnderUtilizedHost = new HashSet<PowerHost>();
		excludedHostsForFindingUnderUtilizedHost.addAll(overUtilizedHosts);
		excludedHostsForFindingUnderUtilizedHost.addAll(switchedOffHosts);
		excludedHostsForFindingUnderUtilizedHost.addAll(extractHostListFromMigrationMap(migrationMap));

		// over-utilized + under-utilized hosts
		//不可迁入列表
		Set<PowerHost> excludedHostsForFindingNewVmPlacement = new HashSet<PowerHost>();
		excludedHostsForFindingNewVmPlacement.addAll(overUtilizedHosts);
		excludedHostsForFindingNewVmPlacement.addAll(switchedOffHosts);

		int numberOfHosts = getHostList().size();

		while (true) {
			if (numberOfHosts == excludedHostsForFindingUnderUtilizedHost.size()) {
				break;
			}

			PowerHost underUtilizedHost = getUnderUtilizedHost(excludedHostsForFindingUnderUtilizedHost);
			if (underUtilizedHost == null) {
				break;
			}

			Log.printConcatLine("Under-utilized host: host #", underUtilizedHost.getId(), "\n");//找出欠载主机的id

			excludedHostsForFindingUnderUtilizedHost.add(underUtilizedHost);
			excludedHostsForFindingNewVmPlacement.add(underUtilizedHost);

			List<? extends Vm> vmsToMigrateFromUnderUtilizedHost = getVmsToMigrateFromUnderUtilizedHost(underUtilizedHost);
			if (vmsToMigrateFromUnderUtilizedHost.isEmpty()) {
				continue;
			}

			Log.print("Reallocation of VMs from the under-utilized host: ");
			if (!Log.isDisabled()) {
				for (Vm vm : vmsToMigrateFromUnderUtilizedHost) {
					Log.print(vm.getId() + " ");
				}
			}
			Log.printLine();

			List<Map<String, Object>> newVmPlacement = getNewVmPlacementFromUnderUtilizedHost(
					vmsToMigrateFromUnderUtilizedHost,
					excludedHostsForFindingNewVmPlacement);

			excludedHostsForFindingUnderUtilizedHost.addAll(extractHostListFromMigrationMap(newVmPlacement));

			migrationMap.addAll(newVmPlacement);
			Log.printLine();
		}

		return migrationMap;
	}

	/**
	 * Prints the over utilized hosts.
	 * 
	 * @param overUtilizedHosts the over utilized hosts
	 */
	protected void printOverUtilizedHosts(List<PowerHostUtilizationHistory> overUtilizedHosts) {
		if (!Log.isDisabled()) {
			Log.printLine("Over-utilized hosts:");
			for (PowerHostUtilizationHistory host : overUtilizedHosts) {
				Log.printConcatLine("Host #", host.getId());
			}
			Log.printLine();
		}
	}

	/**
	 * Finds a PM that has enough resources to host a given VM
         * and that will not be overloaded after placing the VM on it.
         * The selected host will be that one with most efficient
         * power usage for the given VM.
	 *
	 * 找到合适的主机，对于迁移的主机而言，此时可以再次制定相关的主机查找规则
	 *
	 * @param vm the VM
	 * @param excludedHosts the excluded hosts
	 * @return the host found to host the VM
	 */
	//现在要进行对虚拟机对主机的进行映射
	public PowerHost findHostForVm(Vm vm, Set<? extends Host> excludedHosts)  {
		double minPower = Double.MAX_VALUE;
		double minCriterion = Double.MIN_VALUE;
		PowerHost allocatedHost = null;
		List<PowerHost> switchedOffHosts = this.<PowerHost>getSwitchedOffHosts();
		List<PowerHost> hostList = this.<PowerHost>getHostList();
        double[][] A = {
                {1, 2, 1.0 / 2},
                {1.0 / 2, 1, 1.0 / 5},
                {2, 5, 1}
        };
        double [] Weights = new double[3];
        for (int i = 0; i < A.length; i++) {
            double rowProduct = 1.0;
            for (int j = 0; j < A[i].length; j++) {
                rowProduct *= A[i][j];
            }
            double cubeRoot = Math.cbrt(rowProduct);

            double rowSum = 0.0;
            for (int j = 0; j < A[i].length; j++) {
                rowSum += A[i][j];
            }

            double result = cubeRoot / rowSum;
            Weights[i] = result;
        }
        double Sw = Weights[0];
        double Bw = Weights[1];
        double Aw = Weights[2];
		//hostList.sortByEnergyEfficiency;
		//现在这里对hostList排序
//		hostList.sort(new Comparator<PowerHost>() {
//			@Override
//			public int compare(PowerHost o1, PowerHost o2) {
//				Double A_efficency=o1.getTotalMips()/o1.getMaxPower();
//				Double B_efficency=o2.getTotalMips()/o2.getMaxPower();
//				return A_efficency.compareTo(B_efficency);
//			}
//		});
		for (PowerHost host : this.<PowerHost>getHostList()) {
			if (excludedHosts.contains(host)) {
				continue;
			}
			if (host.isSuitableForVm(vm)) {
				if (getUtilizationOfCpuMips(host) != 0 && isHostOverUtilizedAfterAllocation(host, vm)) {
					continue;
				}
				try {
					double vmcpu = vm.getCurrentUtilizationOfCpu() * vm.getMips();
					if (vmcpu != 2500 && vmcpu != 2000 && vmcpu != 1000 && vmcpu != 500){
						double powerAfterAllocation = getPowerAfterAllocation(host, vm);
						if (powerAfterAllocation != -1){
							double powerDiff = powerAfterAllocation - host.getPower();
							double a = Math.exp(-powerDiff);
							double b = 1-(1/(1+a));
							double absolute = host.getUtilizaionOfCpu() - host.getUtilizationOfRam();
							if (absolute < 0){
								absolute = -absolute;
							}
							double hostcpu = host.getTotalMips();
							double hostcpu1 = host.getAvailableMips();
							double hostram = host.getRam();
							//double hostram1 = host.getAvailableRam();
							double hostram1 = host.getRam() - host.getUsedRam();
							double hostbw = host.getBw();
							double hostbw1 = host.getBw() - host.getUsedBw();
							double cosx = (hostcpu * hostcpu1 + hostbw1 * hostbw + hostram1 * hostram) / (Math.sqrt(Math.pow(hostcpu, 2) + Math.pow(hostbw, 2) + Math.pow(hostram, 2)) * Math.sqrt(Math.pow(hostcpu1, 2) + Math.pow(hostbw1, 2) + Math.pow(hostram1, 2)));
							double scorepower = (Math.exp(-powerDiff));
							double AR = (1 - host.getUtilizaionOfCpu())/100000;//统一量化级
							double Balance = cosx;
							double comparevalue = Sw * scorepower +  + Aw*AR + Bw*Balance;
							if (comparevalue > minCriterion) {
								minPower = powerDiff;
								allocatedHost = host;
							}
						}
					}
					else {
						double powerAfterAllocation = getPowerAfterAllocation(host, vm);
						if (powerAfterAllocation != -1) {
							double powerDiff = powerAfterAllocation - host.getPower();
							if (powerDiff < minPower) {
								minPower = powerDiff;
								allocatedHost = host;
							}
						}
					}
					/*//使用自己规定的协议;
					double sin=getSin(vm,host);
					double distanceDiff=Double.MAX_VALUE;
					//尝试使用主机的能效对主机进行操作
					//double efficiency=Double.MIN_VALUE;
					//double energy_efficiency=host.getTotalMips()/host.getMaxPower();//使用相关
					//System.out.println("主机的序号为:" + host.getId() + "；其MIPS为：" + host.getTotalMips() + "主机最大的功率为" + host.getMaxPower()+"；其能效值为："+energy_efficiency);
					//if(efficiency<){}
//					if (sin < distanceDiff){
//						distanceDiff=sin;
//						allocatedHost=host;
//					}
					double o = host.getMaxPower();
					double powerAfterAllocation = getPowerAfterAllocation(host, vm);
					if (powerAfterAllocation != -1) {
						double powerDiff = powerAfterAllocation - host.getPower();
//						//double resouceAvaiable=Math.abs(((PowerHost) host).getUtilizationOfCpu()-host.getUtilizationOfStorge())/((PowerHost) host).getUtilizationOfCpu()+host.getUtilizationOfStorge();
//						//此处未经使用
						double performance = (1 - host.getUtilizaionOfCpu()) *
								(1 / (1 + Math.exp(-powerDiff)));
//						if (performance > minPerformance){
//							minPerformance=performance;
//							allocatedHost=host;
//						}
						if (powerDiff < minPower) {
							minPower = powerDiff;
							allocatedHost = host;
						}*/


					} catch (Exception e) {
				}
			}
		}
		return allocatedHost;
	}

	/**
	 * Checks if a host will be over utilized after placing of a candidate VM.
	 * 
	 * @param host the host to verify
	 * @param vm the candidate vm 
	 * @return true, if the host will be over utilized after VM placement; false otherwise
	 */
	protected boolean isHostOverUtilizedAfterAllocation(PowerHost host, Vm vm) {
		boolean isHostOverUtilizedAfterAllocation = true;
		if (host.vmCreate(vm)) {
			isHostOverUtilizedAfterAllocation = isHostOverUtilized(host);
			host.vmDestroy(vm);
		}
		return isHostOverUtilizedAfterAllocation;
	}

	public double getSin(Vm vm,PowerHost host){
		double accountforCPU=(vm.getCurrentUtilizationOfCpu()*vm.getMips())/(host.getAvailableMips());
		double accountforRAM=vm.getRam()/host.getAvailableRam();
		double accountforBW=vm.getBw()/host.getAvailbleBw();
		//if(  (accountforCPU <=1 && accountforCPU >0) && (accountforRAM <= 1 && accountforRAM >0) ){
			double x=0,y=0,z=0;
			x=-accountforRAM/accountforCPU;
			y=-accountforRAM/accountforBW;
			z=1;
			//经过这个平面的法向量设定为：
			double x1=1,y1=0,z1=-1;
			//最终经过设定的为cos的夹角为：
			double cos=0;
			cos=Math.abs((x1*x+y*y1+z*z1)/(Math.sqrt(x*x+y*y+z*z)*Math.sqrt(2)));
			//Log.printLine("虚拟机编号为："+vm.getId()+"；所对应的主机"+host.getId()+"；所占用的空间为："+cos+"；其所占的CPU为"+accountforCPU+"；所占用的RAM为："+accountforRAM+"所对应的BW为");
			return cos;

		//}
		//根据，cpu、RAM、BW求解出相应的法向量(accountforBW <=1 && accountforBW >0)
		//return Double.MAX_VALUE;
	}

	@Override
	public PowerHost findHostForVm(Vm vm)  {
		Set<Host> excludedHosts = new HashSet<Host>();
		if (vm.getHost() != null) {
			excludedHosts.add(vm.getHost());
		}
		return findHostForVm(vm, excludedHosts);
	}

	/**
	 * Extracts the host list from a migration map.
	 * 
	 * @param migrationMap the migration map
	 * @return the list
	 * 从传入的migrationMap中提取主机列表；
	 */
	protected List<PowerHost> extractHostListFromMigrationMap(List<Map<String, Object>> migrationMap) {
		List<PowerHost> hosts = new LinkedList<PowerHost>();
		for (Map<String, Object> map : migrationMap) {
			hosts.add((PowerHost) map.get("host"));
		}
		return hosts;
	}

	/**
	 * Gets a new vm placement considering the list of VM to migrate.
	 * @param vmsToMigrate the list of VMs to migrate
	 * @param excludedHosts the list of hosts that aren't selected as destination hosts
	 * @return the new vm placement map
	 * 为传入的VM列表制定放置计划。该方法的大致过程是：
	 * 先按CPU利用率(in MIPS）降序排列vm列表，然后遍历该vm列表，
	 * 调用findHostForVm(vm,excludedHosts)获得分配方案。
	 */
	protected List<Map<String, Object>> getNewVmPlacement(
			List<? extends Vm> vmsToMigrate,
			Set<? extends Host> excludedHosts) {
		List<Map<String, Object>> migrationMap = new LinkedList<Map<String, Object>>();
		//PowerVmList.sortByTotalProfomance(vmsToMigrate);
		PowerVmList.sortByCpuUtilization(vmsToMigrate);
		//降序排列vm列表
		//PowerVmList.sortByCpuUtilizationOfMips(vmsToMigrate);
		for (Vm vm : vmsToMigrate) {
			PowerHost allocatedHost = findHostForVm(vm, excludedHosts);
			if (allocatedHost != null) {
				allocatedHost.vmCreate(vm);
				Log.printConcatLine("VM #", vm.getId(), " allocated to host #", allocatedHost.getId());

				Map<String, Object> migrate = new HashMap<String, Object>();
				migrate.put("vm", vm);
				migrate.put("host", allocatedHost);
				migrationMap.add(migrate);
			}
		}
		return migrationMap;
	}


	/**
	 * Gets the new vm placement from under utilized host.
	 * 
	 * @param vmsToMigrate the list of VMs to migrate
	 * @param excludedHosts the list of hosts that aren't selected as destination hosts
	 * @return the new vm placement from under utilized host
	 */
	protected List<Map<String, Object>> getNewVmPlacementFromUnderUtilizedHost(
			List<? extends Vm> vmsToMigrate,
			Set<? extends Host> excludedHosts) {
		List<Map<String, Object>> migrationMap = new LinkedList<Map<String, Object>>();
		PowerVmList.sortByCpuUtilization(vmsToMigrate);
		//PowerVmList.sortByCpuUtilizationOfMips(vmsToMigrate);
		for (Vm vm : vmsToMigrate) {
			PowerHost allocatedHost = findHostForVm(vm, excludedHosts);
			if (allocatedHost != null) {
				allocatedHost.vmCreate(vm);
				Log.printConcatLine("VM #", vm.getId(), " allocated to host #", allocatedHost.getId());
				Map<String, Object> migrate = new HashMap<String, Object>();
				migrate.put("vm", vm);
				migrate.put("host", allocatedHost);
				migrationMap.add(migrate);
			} else {
				Log.printLine("Not all VMs can be reallocated from the host, reallocation cancelled");
				for (Map<String, Object> map : migrationMap) {
					((Host) map.get("host")).vmDestroy((Vm) map.get("vm"));
				}
				migrationMap.clear();
				break;
			}
		}
		return migrationMap;
	}

	/**
	 * Gets the VMs to migrate from hosts.
	 * 
	 * @param overUtilizedHosts the over utilized hosts
	 * @return the VMs to migrate from hosts
	 */


	//此处是从过载的主机上获得需要迁移的虚拟机的列表，

	protected List<? extends Vm>
	  getVmsToMigrateFromHosts(List<PowerHostUtilizationHistory> overUtilizedHosts) {
		List<Vm> vmsToMigrate = new LinkedList<Vm>();
		for (PowerHostUtilizationHistory host : overUtilizedHosts) {
			while (true) {
				Vm vm = getVmSelectionPolicy().getVmToMigrate(host);
				if (vm == null) {
					break;
				}
				vmsToMigrate.add(vm);
				host.vmDestroy(vm);
				if (!isHostOverUtilized(host)) {
					break;
				}
			}
		}
		return vmsToMigrate;
	}

	/**
	 * Gets the VMs to migrate from under utilized host.
	 * 
	 * @param host the host
	 * @return the vms to migrate from under utilized host
	 */

	//从负载不足的主机上产生新的虚拟机迁移列表,从主机迁移出新的虚拟机需要考虑到相关的协议进行迁移，
	//	// 全部从负载不足的主机上进行迁移生成新的迁移虚拟机列表
	protected List<? extends Vm> getVmsToMigrateFromUnderUtilizedHost(PowerHost host) {
		List<Vm> vmsToMigrate = new LinkedList<Vm>();
		for (Vm vm : host.getVmList()) {
			if (!vm.isInMigration()) {
				vmsToMigrate.add(vm);
			}
		}
		return vmsToMigrate;
	}

	/**
	 * Gets the over utilized hosts.
	 * 
	 * @return the over utilized hosts
	 */
	protected List<PowerHostUtilizationHistory> getOverUtilizedHosts() {
		List<PowerHostUtilizationHistory> overUtilizedHosts = new LinkedList<PowerHostUtilizationHistory>();
		for (PowerHostUtilizationHistory host : this.<PowerHostUtilizationHistory> getHostList()) {
			if (isHostOverUtilized(host)) {
				overUtilizedHosts.add(host);
			}
		}
		return overUtilizedHosts;
	}

	/**
	 * Gets the switched off hosts.
	 * 
	 * @return the switched off hosts
	 */
	protected List<PowerHost> getSwitchedOffHosts() {
		List<PowerHost> switchedOffHosts = new LinkedList<PowerHost>();
		for (PowerHost host : this.<PowerHost> getHostList()) {
			if (host.getUtilizationOfCpu() == 0) {
				switchedOffHosts.add(host);
			}
		}
		return switchedOffHosts;
	}

	/**
	 * Gets the most under utilized host.
	 * 获取最负载不足的主机
	 * @param excludedHosts the excluded hosts
	 * @return the most under utilized host
	 */
	protected PowerHost getUnderUtilizedHost(Set<? extends Host> excludedHosts) {
		double minUtilization = 1;
		PowerHost underUtilizedHost = null;
		for (PowerHost host : this.<PowerHost> getHostList()) {
			if (excludedHosts.contains(host)) {
				continue;
			}
			double utilization = host.getUtilizationOfCpu();
			if (utilization > 0 && utilization < minUtilization
					&& !areAllVmsMigratingOutOrAnyVmMigratingIn(host)) {
				minUtilization = utilization;
				underUtilizedHost = host;
			}
		}
		return underUtilizedHost;
	}

	/**
	 * Checks whether all VMs of a given host are in migration.
	 * 
	 * @param host the host
	 * @return true, if successful
	 */
	protected boolean areAllVmsMigratingOutOrAnyVmMigratingIn(PowerHost host) {
		for (PowerVm vm : host.<PowerVm> getVmList()) {
			if (!vm.isInMigration()) {
				return false;
			}
			if (host.getVmsMigratingIn().contains(vm)) {
				return true;
			}
		}
		return true;
	}


	/**
	 * Checks if host is over utilized.
	 * 
	 * @param host the host
	 * @return true, if the host is over utilized; false otherwise
	 */
	protected abstract boolean isHostOverUtilized(PowerHost host) ;




	/**
	 * Adds an entry for each history map of a host.
	 * 
	 * @param host the host to add metric history entries
	 * @param metric the metric to be added to the metric history map
	 */
	protected void addHistoryEntry(HostDynamicWorkload host, double metric) {
		int hostId = host.getId();
		if (!getTimeHistory().containsKey(hostId)) {
			getTimeHistory().put(hostId, new LinkedList<Double>());
		}
		if (!getUtilizationHistory().containsKey(hostId)) {
			getUtilizationHistory().put(hostId, new LinkedList<Double>());
		}
		if (!getMetricHistory().containsKey(hostId)) {
			getMetricHistory().put(hostId, new LinkedList<Double>());
		}
		if (!getTimeHistory().get(hostId).contains(CloudSim.clock())) {
			getTimeHistory().get(hostId).add(CloudSim.clock());
			getUtilizationHistory().get(hostId).add(host.getUtilizationOfCpu());
			getMetricHistory().get(hostId).add(metric);
		}
	}

	/**
	 * Updates the list of maps between a VM and the host where it is place.
         * @see #savedAllocation
	 */
	protected void saveAllocation() {
		getSavedAllocation().clear();
		for (Host host : getHostList()) {
			for (Vm vm : host.getVmList()) {
				if (host.getVmsMigratingIn().contains(vm)) {
					continue;
				}
				Map<String, Object> map = new HashMap<String, Object>();
				map.put("host", host);
				map.put("vm", vm);
				getSavedAllocation().add(map);
			}
		}
	}

	/**
	 * Restore VM allocation from the allocation history.
         * @see #savedAllocation
	 */
	protected void restoreAllocation() {
		for (Host host : getHostList()) {
			host.vmDestroyAll();
			host.reallocateMigratingInVms();
		}
		for (Map<String, Object> map : getSavedAllocation()) {
			Vm vm = (Vm) map.get("vm");
			PowerHost host = (PowerHost) map.get("host");
			if (!host.vmCreate(vm)) {
				Log.printConcatLine("Couldn't restore VM #", vm.getId(), " on host #", host.getId());
				System.exit(0);
			}
			getVmTable().put(vm.getUid(), host);
		}
	}

	/**
	 * Gets the power consumption of a host after placement of a candidate VM.
         * The VM is not in fact placed at the host.
	 * 
	 * @param host the host
	 * @param vm the candidate vm
	 * 
	 * @return the power after allocation
	 */
	protected double getPowerAfterAllocation(PowerHost host, Vm vm) {
		double power = 0;
		try {
			//获得主机在迁移之后的一奋能耗的过程
			power = host.getPowerModel().getPower(getMaxUtilizationAfterAllocation(host, vm));
		} catch (Exception e) {
			e.printStackTrace();
			System.exit(0);
		}
		return power;
	}

	/**
	 * Gets the max power consumption of a host after placement of a candidate VM.
         * The VM is not in fact placed at the host.
         * We assume that load is balanced between PEs. The only
	 * restriction is: VM's max MIPS < PE's MIPS
	 * 
	 * @param host the host
	 * @param vm the vm
	 * 
	 * @return the power after allocation
	 */
	protected double getMaxUtilizationAfterAllocation(PowerHost host, Vm vm) {
		double requestedTotalMips = vm.getCurrentRequestedTotalMips();
		double hostUtilizationMips = getUtilizationOfCpuMips(host);
		double hostPotentialUtilizationMips = hostUtilizationMips + requestedTotalMips;
		double pePotentialUtilization = hostPotentialUtilizationMips / host.getTotalMips();
		return pePotentialUtilization;
	}
	
	/**
	 * Gets the utilization of the CPU in MIPS for the current potentially allocated VMs.
	 *
	 * @param host the host
	 *
	 * @return the utilization of the CPU in MIPS
	 */
	protected double getUtilizationOfCpuMips(PowerHost host) {
		double hostUtilizationMips = 0;
		for (Vm vm2 : host.getVmList()) {
			if (host.getVmsMigratingIn().contains(vm2)) {
				// calculate additional potential CPU usage of a migrating in VM
				hostUtilizationMips += host.getTotalAllocatedMipsForVm(vm2) * 0.9 / 0.1;
			}
			hostUtilizationMips += host.getTotalAllocatedMipsForVm(vm2);
		}
		return hostUtilizationMips;
	}

	/**
	 * Gets the saved allocation.
	 * 
	 * @return the saved allocation
	 */
	protected List<Map<String, Object>> getSavedAllocation() {
		return savedAllocation;
	}

	/**
	 * Sets the vm selection policy.
	 * 
	 * @param vmSelectionPolicy the new vm selection policy
	 */
	protected void setVmSelectionPolicy(PowerVmSelectionPolicy vmSelectionPolicy) {
		this.vmSelectionPolicy = vmSelectionPolicy;
	}

	/**
	 * Gets the vm selection policy.
	 * 
	 * @return the vm selection policy
	 */
	protected PowerVmSelectionPolicy getVmSelectionPolicy() {
		return vmSelectionPolicy;
	}

	/**
	 * Gets the utilization history.
	 * 
	 * @return the utilization history
	 */
	public Map<Integer, List<Double>> getUtilizationHistory() {
		return utilizationHistory;
	}

	/**
	 * Gets the metric history.
	 * 
	 * @return the metric history
	 */
	public Map<Integer, List<Double>> getMetricHistory() {
		return metricHistory;
	}

	/**
	 * Gets the time history.
	 * 
	 * @return the time history
	 */
	public Map<Integer, List<Double>> getTimeHistory() {
		return timeHistory;
	}

	/**
	 * Gets the execution time history vm selection.
	 * 
	 * @return the execution time history vm selection
	 */
	public List<Double> getExecutionTimeHistoryVmSelection() {
		return executionTimeHistoryVmSelection;
	}

	/**
	 * Gets the execution time history host selection.
	 * 
	 * @return the execution time history host selection
	 */
	public List<Double> getExecutionTimeHistoryHostSelection() {
		return executionTimeHistoryHostSelection;
	}

	/**
	 * Gets the execution time history vm reallocation.
	 * 
	 * @return the execution time history vm reallocation
	 */
	public List<Double> getExecutionTimeHistoryVmReallocation() {
		return executionTimeHistoryVmReallocation;
	}

	/**
	 * Gets the execution time history total.
	 * 
	 * @return the execution time history total
	 */
	public List<Double> getExecutionTimeHistoryTotal() {
		return executionTimeHistoryTotal;
	}

}
