xref: /illumos-gate/usr/src/cmd/pools/poold/com/sun/solaris/domain/pools/SystemSolver.java (revision 55fea89d)

/*
 * CDDL HEADER START
 *
 * The contents of this file are subject to the terms of the
 * Common Development and Distribution License, Version 1.0 only
 * (the "License").  You may not use this file except in compliance
 * with the License.
 *
 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
 * or http://www.opensolaris.org/os/licensing.
 * See the License for the specific language governing permissions
 * and limitations under the License.
 *
 * When distributing Covered Code, include this CDDL HEADER in each
 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
 * If applicable, add the following below this CDDL HEADER, with the
 * fields enclosed by brackets "[]" replaced with your own identifying
 * information: Portions Copyright [yyyy] [name of copyright owner]
 *
 * CDDL HEADER END
 */
/*
 * Copyright 2004 Sun Microsystems, Inc.  All rights reserved.
 * Use is subject to license terms.
 *
 * ident	"%Z%%M%	%I%	%E% SMI"
 */

package com.sun.solaris.domain.pools;

import java.io.*;
import java.nio.*;
import java.nio.channels.*;
import java.util.*;
import java.util.regex.*;
import java.text.DecimalFormat;

import com.sun.solaris.service.locality.*;
import com.sun.solaris.service.logging.*;
import com.sun.solaris.service.pools.*;
import com.sun.solaris.service.exception.*;

/**
 * The <code>SystemSolver</code> class implements a dynamic resource
 * allocation solver. The Solver takes a configuration and "solves"
 * the resource allocation problem.
 *
 * This class operates upon a configuration which is suppplied during
 * initialization. Its responsibilities include:
 * <ul>
 * <li><p>
 * Maintaining decision history
 * <li><p>
 * Maintaining information about the locality domain
 * <li><p>
 * Maintaining a map of all elements and their associated set of objectives
 * <li><p>
 * Identifying objective expressions with a configuration
 * </ul>
 */
class SystemSolver implements Solver {
	/**
	 * The default location of this history file.
	 */
	public static final String DH_FILE_DEF_PATH =
	    "/var/adm/pool/history";

	/**
	 * The property overriding the default decision history path.
	 */
	public static final String DH_FILE_PROP_NAME =
	    "system.poold.history-file";

	/**
	 * The LocalityDomain extracted from the configuration.
	 */
	private LocalityDomain ldom;

	/**
	 * The objective map used to link all elements with their set
	 * of objectives.
	 */
	private Map objMap;

	/**
	 * The pattern used to identify objective expressions.
	 */
	private static final Pattern p0 = Pattern.compile(";");

	/**
	 * The configuration for which this solver is "solving".
	 */
	private Configuration conf;

	/**
	 * Monitor providing statistics for this solver.
	 */
	private final Monitor monitor;

	/**
	 * The decision history maintainer.
	 */
	private DecisionHistory dh;

	/**
	 * The path to the decision history file.
	 */
	private String dhPath;

	/**
	 * The number of CPUs on the system.
	 */
	private int cpuCount;

	/**
	 * The number of locality triggered examinations made.
	 */
	private int examineCount;

	/**
	 * Constructs a solver which initialises a decision history
	 * maintainer.  The decision history is be used during operation
	 * to veto historically-poor decisions output from the objective
	 * function.
	 */
	SystemSolver(Monitor monitor)
	{
		/*
		 * Create a HashMap to store all objectives.
		 */
		objMap = new HashMap();
		this.monitor = monitor;
	}

	/**
	 * Initialize the solver for operation upon the supplied
	 * configuration. Possible objective expressions set upon
	 * target elements are identified and stored in an objective
	 * map which associates elements with the set of their
	 * objectives.
	 *
	 * @param conf The configuration to be manipulated.
	 * @throws PoolsException If the initialization fails.
	 */
	public void initialize(Configuration conf) throws PoolsException
	{
		String oString = null;
		String exps[];

		this.conf = conf;
		/*
		 * Count the CPUs in the system, this is used to
		 * control locality objective processing in the
		 * examine() method.
		 */
		cpuCount = conf.getComponents(null).size();
		examineCount = 0;
		/*
		 * Remove any old objectives
		 */
		objMap.clear();

		/*
		 * Extract any configuration objectives
		 */
		try {
			oString = conf.getStringProperty(
			    "system.poold.objectives");
			if (oString.length() > 0) {
				Set oSet = new HashSet();
				objMap.put(conf, oSet);
				Poold.CONF_LOG.log(Severity.DEBUG,
				    "adding configuration objective " +
				    oString);
				exps = p0.split(oString);
				for (int i = 0; i < exps.length; i++) {
					try {
						Expression exp =
						    Expression.valueOf(
						    exps[i]);
						addObjective(oSet, "system",
						    exp);
					} catch (IllegalArgumentException iae) {
						Poold.utility.warn(
						    Poold.CONF_LOG, iae, false);
					}
				}
			}
		} catch (PoolsException pe) {
			/*
			 * Ignore as this means there is no objective
			 * property
			 */
		}
		/*
		 * Now extract all pset objectives
		 */
		Value typeProp = new Value("type", "pset");
		List valueList = new LinkedList();
		valueList.add(typeProp);
		Iterator resIt = conf.getResources(valueList).iterator();
		typeProp.close();
		while (resIt.hasNext()) {
			Resource resource = (Resource)resIt.next();

			try {
				oString = resource.getStringProperty(
				    "pset.poold.objectives");
				if (oString.length() > 0) {
					Set oSet = new HashSet();
					objMap.put(resource, oSet);
					Poold.CONF_LOG.log(Severity.DEBUG,
					    "adding " +
					    resource.getStringProperty(
					    "pset.name") +
					    " objective \"" + oString + "\"");
					exps = p0.split(oString);
					for (int i = 0; i < exps.length; i++) {
						Expression exp = null;
						try {
							exp = Expression.
							    valueOf(exps[i]);
							addObjective(oSet,
							    "pset", exp);
						} catch
						    (IllegalArgumentException e)
						{
							Poold.utility.warn(
							    Poold.CONF_LOG, e,
							    false);
						}
					}
				}
			} catch (PoolsException pe) {
				continue;
			}
		}
		Poold.CONF_LOG.log(Severity.DEBUG, "objective map: " +
		    objMap.toString());

		/*
		 * Capture the LocalityDomain details.
		 */
		if (ldom != null) {
			ldom.close();
		}
		try {
			ldom = new LocalityDomain(LocalityDomain.LGRP_VIEW_OS);
		} catch (Exception e) {
			Poold.utility.die(Poold.OPT_LOG, e);
		}

		/*
		 * Load or create the decision history.
		 */
		String newDhPath;
		try {
			newDhPath = conf.getStringProperty(
			    DH_FILE_PROP_NAME);
		} catch (PoolsException pe) {
			newDhPath = DH_FILE_DEF_PATH;
		}

		if (!newDhPath.equals(dhPath)) {
			try {
				dh = DecisionHistory.loadFromFile(newDhPath);
				Poold.CONF_LOG.log(Severity.DEBUG,
				    "loaded history file " + newDhPath);
			} catch (Exception e) {
				if (!(e instanceof FileNotFoundException)) {
					Poold.CONF_LOG.log(Severity.WARNING,
					    newDhPath +
					    ": contents unusable; ignoring");
					Poold.CONF_LOG.log(Severity.DEBUG,
					    newDhPath + ": contents unusable",
					    e);
				}
				/*
				 * Use current DecisionHistory instead,
				 * if any.
				 */
				if (dh == null)
					dh = new DecisionHistory();
			}

			/*
			 * Try using the new path.
			 */
			try {
				dh.syncToFile(newDhPath);
			} catch (Exception e) {
				Poold.utility.die(Poold.CONF_LOG,
				    new PooldException(newDhPath +
				    ": couldn't synchronize history file")
				    .initCause(e), false);
			}
			dhPath = newDhPath;
		}
	}

	/**
	 * Determine if the given resource has non-workload-dependent
	 * objectives.
	 * @param elem The element to examine.
	 */
	private boolean hasNonWorkloadDependentObjectives(Element elem)
	{
		Set elemObj = (Set)objMap.get(elem);

		/*
		 * This code relies upon the fact that an element with
		 * no objectives will not have an empty set, but rather
		 * no value in the objMap.
		 */

		if (elemObj == null)
			return (false);

		Iterator elemObjIt = elemObj.iterator();
		while (elemObjIt.hasNext())
			if (elemObjIt.next() instanceof
			    WorkloadDependentObjective)
				return (false);

		return (true);
	}

	/**
	 * Determine if the given resource has workload-dependent
	 * objectives.
	 * @param elem The element to examine.
	 */
	private boolean hasWorkloadDependentObjectives(Element elem)
	{
		Set elemObj = (Set)objMap.get(elem);

		/*
		 * This code relies upon the fact that an element with
		 * no objectives will not have an empty set, but rather
		 * no value in the objMap.
		 */

		if (elemObj == null)
			return (false);

		Iterator elemObjIt = elemObj.iterator();
		while (elemObjIt.hasNext())
			if (elemObjIt.next() instanceof
			    WorkloadDependentObjective)
				return (true);

		return (false);
	}

	/**
	 * Return true if the monitored configuration should be
	 * reconfigured. All workload-dependent objectives are
	 * examined to determine if the configuration is still
	 * satisfying all specified objectives on all elements. If any
	 * objectives are failing, then this method will return true.
	 *
	 * @param mon The monitoring object used to assess objective
	 * compliance.
	 */
	public boolean examine(Monitor mon) throws PoolsException,
	    StaleMonitorException
	{
		/*
		 * Take advantage of the guaranteed-valid monitor data
		 * for measuring the improvement of any past decisions.
		 */
		dh.expireAndMeasureImprovements(mon);

		Iterator objIt = objMap.keySet().iterator();
		boolean ret = false;
		boolean hasLocalityObjectives = false;
		boolean isMonitorValid = true;

		/*
		 * All objectives are examined, even though failure
		 * could be detected earlier. This is because logging
		 * of all objectives is required and the information
		 * about failure can be stored and used during
		 * solving.
		 */
		while (objIt.hasNext()) {
			Element elem = (Element) objIt.next();
			Set elemObj = (Set) objMap.get(elem);
			Iterator elemObjIt = elemObj.iterator();
			while (elemObjIt.hasNext()) {
				Objective obj = (Objective) elemObjIt.next();
				Poold.OPT_LOG.log(Severity.DEBUG,
				    "checking objective " + obj);
				if (obj instanceof WorkloadDependentObjective) {
					if (isValid()) {
						/*
						 * If any objectives
						 * are violated, then
						 * we must
						 * reconfigure, so
						 * check them all in
						 * turn.
						 */
					ret = ((WorkloadDependentObjective)
					    obj).examine(conf, this, elem) ||
					    ret;
					} else
						isMonitorValid = false;
				}
			}

			/*
			 * Check if this is the first element, seen in
			 * this pass, that has locality objectives.
			 */
			if (!hasLocalityObjectives &&
			    hasNonWorkloadDependentObjectives(elem))
				hasLocalityObjectives = true;
		}
		if (isMonitorValid == false) {
			Poold.MON_LOG.log(Severity.INFO,
			    "not evaluating workload-dependent objectives " +
			    "until sufficient statistics are collected");
		}
		/*
		 * If we don't have locality objectives, we don't force
		 * the reexamination.  This is controlled by
		 * hasLocalityObjectives.
		 *
		 * So that we don't continually trigger
		 * reconfiguration examinations for locality
		 * objectives we stop forcing recalculations when we
		 * reach cpuCount / 2. This should be enough moves to
		 * get good locality for those configurations which
		 * have no WorkloadDependentObjectives.
		 */
		return (ret || (hasLocalityObjectives && (examineCount++ <
		    cpuCount / 2)));
	}

	/**
	 * Reallocate resources in a configuration to achieve user
	 * specified objectives. Return true if the configuration has
	 * been updated, false otherwise.
	 *
	 * This method should only be invoked if a previous
	 * examination of the configuration which is monitored
	 * indicates that objectives are failing. The monitored
	 * configuration is re-opened for editing, locking that
	 * configuration for the duration of this operation.
	 *
	 * @throws Exception If the solve fails.
	 */
	public boolean solve() throws Exception
	{
		boolean madeMove = false;
		/*
		 * All solving operations must be done in an
		 * "editable" context, so create a new modifiable
		 * configuration which is at the same location as the
		 * monitored configuration
		 */
		Configuration rwConf = new Configuration(conf.getLocation(),
		    PoolInternal.PO_RDWR);

		try {
			/*
			 * Build a resource set importance map for use
			 * when propagating pool importance to each
			 * possible solution. Use the same logic as
			 * libpool and let a resource take the highest
			 * importance value from all pools associated
			 * with the set.
			 */
			Map resImp = new HashMap();
			List poolList = rwConf.getPools(null);
			Iterator itPool = poolList.iterator();
			while (itPool.hasNext()) {
				Pool pool = (Pool) itPool.next();
				long newImp = pool.
				    getLongProperty("pool.importance");
				List resList = pool.getResources(null);
				Iterator itRes = resList.iterator();
				while (itRes.hasNext()) {
					Resource res = (Resource) itRes.next();
					if (resImp.containsKey(res)) {
						Long imp = (Long) resImp.
						    get(res);
						if (newImp > imp.longValue())
							resImp.put(res,
							    new Long(newImp));
					} else
						resImp.put(res,
						    new Long(newImp));
				}
			}
			/*
			 * Consider all possible alternative
			 * configurations.  This list is generated as a
			 * series of moves.  Administrative constraints
			 * are applied to the moves to prune the list of
			 * possible configurations.
			 */
			Value val = new Value("type", "pset");
			List valueList = new LinkedList();
			valueList.add(val);


			List resList = rwConf.getResources(valueList);
			val.close();
			List donors = getDonors(resList);
			List receivers = getRecipients(resList);
			Poold.OPT_LOG.log(Severity.DEBUG, "donors: " +
			    donors);
			Poold.OPT_LOG.log(Severity.DEBUG, "receivers: " +
			    receivers);
			Iterator itDonor = donors.iterator();
			List moves = new ArrayList();
			while (itDonor.hasNext()) {
				Resource donor = (Resource) itDonor.next();
				List processors = getProcessors(donor);
				Poold.OPT_LOG.log(Severity.DEBUG,
				    "donor processors: " + processors);
				Iterator itProcessor = processors.iterator();
				while (itProcessor.hasNext()) {
					Component cpu = (Component) itProcessor.
					    next();
					Iterator itReceiver = receivers.
					    iterator();
					while (itReceiver.hasNext()) {
						Resource receiver =
						    (Resource) itReceiver.
						    next();
						/*
						 * Can't move to yourself
						 */
						if (receiver == donor)
							continue;
						moves.add(new ComponentMove(
						      donor, receiver, cpu));
					}
				}
			}
			Poold.OPT_LOG.log(Severity.DEBUG,
			    "potential moves: " + moves);
			/*
			 * Now that we have our alternative configurations,
			 * score each configuration by applying all objectives
			 * to each configuration. Hold the scores in the
			 * score set.
			 */
			HashSet scores = new HashSet();
			Iterator itMoves = moves.iterator();
			while (itMoves.hasNext()) {
				double totalContrib = 0;
				Move move = (Move) itMoves.next();
				Iterator objIt = objMap.keySet().iterator();
				while (objIt.hasNext()) {
					Element elem = (Element) objIt.next();
					Set elemObj = (Set) objMap.get(elem);
					Iterator elemObjIt = elemObj.iterator();
					while (elemObjIt.hasNext()) {
						Objective obj =
						    (Objective)elemObjIt.next();
						if (obj instanceof
						    LocalityObjective)
							((LocalityObjective)obj)
							    .prepare(ldom,
							    (Resource)elem);
						/*
						 * If the monitor is
						 * invalid, do not
						 * process
						 * WorkloadDependentObjectives
						 * since they have an
						 * implicit dependency
						 * on the monitor
						 * data.
						 */
						if (obj instanceof
						    WorkloadDependentObjective)
							if (!isValid())
								continue;
						double contrib = obj.calculate(
						    rwConf, move, elem);
						if (contrib < -1 || contrib > 1)
							throw new
							IllegalOFValueException(
						        "x: " + contrib +
							" is invalid, legal " +
							"range is -1 <= x <= " +
							"1");
						/*
						 * Modify the basic
						 * score by the
						 * importance of the
						 * objective and (if
						 * appropriate) the
						 * importance of an
						 * associated pool.
						 */
						if (resImp.containsKey(elem)) {
							contrib *= ((Long)
							    resImp.get(elem)).
							    longValue();
						}

						totalContrib += contrib *
						    obj.getExpression().
						    getImportance();
					}
				}
				Poold.OPT_LOG.log(Severity.DEBUG,
				    "scored move (" + move + ") " +
				    totalContrib);
				scores.add(new ScoreMove(move, totalContrib));
			}
			if (scores.size() != 0) {
				/*
				 * Try to find a move to apply which
				 * yields a positive contribution.
				 */
				Object scoresArray[] = scores.toArray();
				Arrays.sort(scoresArray,
				    Collections.reverseOrder());
				if ((madeMove = processMoves(rwConf,
				    scoresArray, false)) == false)
					madeMove = processMoves(rwConf,
					    scoresArray, true);
			} else
				Poold.OPT_LOG.log(Severity.INFO,
				    "no moves found");
			rwConf.close();
			Poold.OPT_LOG.log(Severity.DEBUG,
			    "synchronizing decision history");
			dh.syncToFile(dhPath);
		} catch (Exception ex) {
			rwConf.close();
			throw ex;
		}
		return (madeMove);
	}

	/*
	 * Process the supplied array of scored moves, trying to find
	 * a move to apply. Return true if a move could be applied,
	 * false otherwise.
	 *
	 * @param conf The configuration to be modified.
	 * @param scores The areay of scored moves to be tried.
	 * @param ignoreDH Ignore Decision History details.
	 */
	private boolean processMoves(Configuration rwConf, Object scores[],
	    boolean ignoreDH) throws PoolsException, StaleMonitorException
	{
		boolean madeMove = false;

		for (int i = 0; i < scores.length; i++) {
			ScoreMove move = (ScoreMove) scores[i];
			if (move.getScore() <= 0) {
				if (ignoreDH)
					Poold.OPT_LOG.log(Severity.INFO,
					    move + " not applied as " +
					    "benefit not significant");
				break;
			}
			if ((madeMove = applyMove(rwConf, move, ignoreDH)) ==
			    true)
				break;
		}
		return (madeMove);
	}

	/*
	 * Attempt to apply the supplied move to the
	 * configuration. Return true if the move could be applied,
	 * false otherwise.
	 *
	 * @param conf The configuration to be modified.
	 * @param move The move to be applied.
	 * @param ignoreDH Ignore Decision History details.
	 */
	private boolean applyMove(Configuration conf, ScoreMove move,
	    boolean ignoreDH)
	    throws PoolsException, StaleMonitorException
	{
		boolean madeMove = false;
		boolean wdpInvolved = false;
		double utilization = 0.0;

		Poold.OPT_LOG.log(Severity.DEBUG, "selected " + move);
		if (hasWorkloadDependentObjectives(move.getMove().getTo()) ||
		    hasWorkloadDependentObjectives(conf)) {
			Poold.OPT_LOG.log(Severity.DEBUG,
			    "Attempting to retrieve utilization for:" + move
			    .getMove().getTo());
			utilization = monitor.getUtilization(move
			    .getMove().getTo());
			wdpInvolved = true;
		}

		/*
		 * Unless a move can be vetoed (i.e. decision history
		 * is effective and there are is a workload-dependent
		 * involved), the move should alwways be applied.
		 */
		if (ignoreDH || !wdpInvolved || !dh.veto(move.getMove(),
		    utilization)) {
			Poold.OPT_LOG.log(Severity.INFO,
			    "applying move " + move.getMove());
			move.getMove().apply();
			ResourceMonitor mon = getMonitor().get(move.getMove().
			    getFrom());
			mon.resetData("utilization");
			mon = getMonitor().get(move.getMove().getTo());
			mon.resetData("utilization");
			try {
				Poold.OPT_LOG.log(Severity.DEBUG,
				    "committing configuration");
				conf.commit(0);
				try {
					if (move.getMove() instanceof
					    ComponentMove)
						if (wdpInvolved)
							dh.recordProcessorMove(
							    (ComponentMove)move
							    .getMove(),
							    utilization,
							    monitor
							    .getSampleCount());
						else
							Poold.OPT_LOG.log(
							    Severity.DEBUG,
							    "decision not " +
							    "recorded due to " +
							    "lack of workload-"
							    + "dependent " +
							    "objectives");
				} catch (Exception e) {
					Poold.OPT_LOG.log(Severity.INFO,
					    "couldn't update " +
					    "decision history (" +
					    e.toString() + ")");
				}
				madeMove = true;
			} catch (PoolsException pe) {
				conf.rollback();
				Poold.OPT_LOG.log(Severity.INFO,
				    "move failed, possibly due to a " +
				    "bound process in a 1-processor " +
				    "set");
			}
		} else {
			/*
			 * Move was vetoed.
			 */
			if (!ignoreDH && wdpInvolved)
				Poold.OPT_LOG.log(Severity.INFO,
				    move.getMove() + " not applied due to " +
				    "poor past results");
		}
		return (madeMove);
	}

	/**
	 * Add an objective based on the supplied expression to the
	 * supplied set of objectives.
	 *
	 * @param oSet Set of objectives to be extended
	 * @param type Type of element to which the expression is applied
	 * @param exp Expression to be used in the objective
	 * @throws IllegalArgumentException If a duplicate objective
	 * is identified or an invalid expression is supplied for this
	 * type of element
	 */
	private void addObjective(Set oSet, String type, Expression exp)
	    throws IllegalArgumentException
	{
		Objective o = AbstractObjective.getInstance(type, exp);
		Poold.CONF_LOG.log(Severity.DEBUG, "parsed objective " + o);
		/*
		 * Check the set of objectives and find contradictions.
		 */
		Iterator itObjs = oSet.iterator();
		while (itObjs.hasNext()) {
			Objective other = (Objective) itObjs.next();
			if (o.getExpression().contradicts(
			    other.getExpression()))
				throw new IllegalArgumentException(
				    "contradictory objectives:" + other +
				    ", " + o);
		}

		if (oSet.add(o) != true)
			throw new IllegalArgumentException(
			    "duplicate objective:" + o);
	}

	/**
	 * Return a list of resource sets prepared to receive
	 * resources
	 *
	 * The list consists of all resource setss (of the supplied
	 * type) whose size is < their max constraint.
	 *
	 * @param resList The list of all resource sets from which
	 * recipients will be chosen
	 * @throws PoolsException if there is an error manipulation
	 * the pool resources
	 */
	private List getRecipients(List resList) throws PoolsException
	{
		List recipientList = new ArrayList();
		long size, max;
		for (int i = 0; i < resList.size(); i++) {
			Resource res;
			res = (Resource)resList.get(i);
			String type = res.getStringProperty("type");
			size = res.getLongProperty(type+".size");
			max = res.getLongProperty(type+".max");
			if (size < max)
				recipientList.add(res);
		}
		return (recipientList);
	}

	/**
	 * Return a list of resource sets prepared to donate resources
	 *
	 * The list consists of all resource sets (of the supplied
	 * type) whose size (minus the number of pinned resources
	 * where applicable) is > their min constraint.
	 *
	 * @param resList The list of all resource sets from which
	 * recipients will be chosen
	 * @throws PoolsException if there is an error manipulation
	 * the pool resources
	 */
	private List getDonors(List resList) throws PoolsException
	{
		List donorList = new ArrayList();
		long size, min;
		for (int i = 0; i < resList.size(); i++) {
			Value bValue;
			Resource res;
			List pinned;
			ArrayList valueList = new ArrayList();

			res = (Resource)resList.get(i);
			String type = res.getStringProperty("type");
			size = res.getLongProperty(type+".size");
			bValue = new Value("cpu.pinned", true);
			valueList.add(bValue);
			pinned = res.getComponents(valueList);
			bValue.close();
			min = res.getLongProperty(type+".min");
			if (pinned.size() > min)
				size -= pinned.size() - min;
			if (size > min)
				donorList.add(res);
		}
		return (donorList);
	}

	/**
	 * Return a list of Processors for the supplied resource.
	 *
	 * The list consists of all Processors (excluding the pinned
	 * Processors) in the set.
	 *
	 * @param set The resource for which Processors should be found
	 * @throws PoolsException if there is an error manipulation
	 * the pool resources
	 */
	private List getProcessors(Resource set) throws PoolsException
	{
		Iterator it = set.getComponents(null).iterator();
		List ret = new ArrayList();

		while (it.hasNext()) {
			Component cpu = (Component) it.next();
			try
			{
				if (cpu.getBoolProperty("cpu.pinned") == false)
					ret.add(cpu);
			} catch (PoolsException pe)
			{
				ret.add(cpu);
			}
		}
		return (ret);
	}

	/**
	 * Return true if the solver is capable of working with
	 * statistically valid data.
	 */
	public boolean isValid()
	{
		return (monitor.isValid());
	}

	/**
	 * Return the monitor used by this solver.
	 */
	public Monitor getMonitor()
	{
		return (monitor);
	}

	/**
	 * Return the set of objectives associated with the supplied
	 * element.
	 *
	 * @param elem Retrieve objectives for this element.
	 */
	public Set getObjectives(Element elem)
	{
		return ((Set)objMap.get(elem));
	}

	/**
	 * Holds details about the score of a proposed configuration
	 * move. Each move must be scored so that they can ranked in
	 * terms of increasing desirability
	 */
	static class ScoreMove implements Comparable {
		/**
		 * The move which is being scored.
		 */
		private final Move m;

		/**
		 * The score of the move.
		 */
		private final double score;

		/**
		 * Score formatter.
		 */
		private static final DecimalFormat scoreFormat =
		    new DecimalFormat("0.00");

		/**
		 * Constructor.
		 *
		 * @param m The move under consideration.
		 * @param score The score of the move.
		 */
		public ScoreMove(Move m, double score)
		{
			this.m = m;
			this.score = score;
		}

		public int compareTo(Object o)
		{
			ScoreMove other = (ScoreMove) o;

			return ((score < other.getScore()) ? -1 :
			    (score > other.getScore()) ? 1 : 0);
		}

		public String toString()
		{
			return ("move (" + m + ") score "
			    + scoreFormat.format(score));
		}

		/**
		 * Return the score.
		 */
		double getScore()
		{
			return (score);
		}

		/**
		 * Return the move.
		 */
		Move getMove()
		{
			return (m);
		}
	}
}