1 /* 2 * CDDL HEADER START 3 * 4 * The contents of this file are subject to the terms of the 5 * Common Development and Distribution License (the "License"). 6 * You may not use this file except in compliance with the License. 7 * 8 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE 9 * or http://www.opensolaris.org/os/licensing. 10 * See the License for the specific language governing permissions 11 * and limitations under the License. 12 * 13 * When distributing Covered Code, include this CDDL HEADER in each 14 * file and include the License file at usr/src/OPENSOLARIS.LICENSE. 15 * If applicable, add the following below this CDDL HEADER, with the 16 * fields enclosed by brackets "[]" replaced with your own identifying 17 * information: Portions Copyright [yyyy] [name of copyright owner] 18 * 19 * CDDL HEADER END 20 */ 21 22 /* 23 * Copyright 2010 Sun Microsystems, Inc. All rights reserved. 24 * Use is subject to license terms. 25 * 26 */ 27 28 package com.sun.solaris.domain.pools; 29 30 import java.io.FileInputStream; 31 import java.io.IOException; 32 import java.lang.reflect.Field; 33 import java.text.DecimalFormat; 34 import java.util.*; 35 import java.util.logging.*; 36 37 import com.sun.solaris.service.logging.Severity; 38 import com.sun.solaris.service.locality.*; 39 import com.sun.solaris.service.pools.*; 40 41 42 /** 43 * An objective interface. All classes which wish to contribute to the 44 * Objective Function (OF hence) calculation must implement this 45 * interface. This interface defines a strategy which can be used to 46 * make a contribution to the Objective Function calculation. 47 * 48 * The OF calculation (which is implemented by <code>Poold</code>) 49 * consists of determining all possible resource moves across all 50 * resources. Once all moves are known, all registered objectives 51 * (i.e. instances of this interface) are called and asked to value 52 * the move. 53 * 54 * Note, the output of this method is constrained to be between -1 and 55 * 1, representing minimum and maximum desirability of this move in 56 * terms of this objective. This is enforced by <code>Poold</code> and 57 * an <code>IllegalOFValueException</code> will be thrown if this 58 * constraint is broken. 59 */ 60 interface Objective 61 { 62 /** 63 * Return the contribution of this objective. The contribution 64 * is constrainted to be a value between -1 and +1 to ensure 65 * that no objective can make a disproportionate contribution 66 * to the total result. 67 * 68 * The more desirable this move appears in terms of this 69 * objective, the closer to +1 will be the value. A value of 0 70 * indicates that the move is neutral in terms of the 71 * objective. A negative value indicates that the move is 72 * undesirable. 73 * 74 * @param conf The configuration which is being examined 75 * @param move The move under consideration 76 * @param elem The element to which the objective applies 77 * 78 * @throws PoolsException if there is an error manipulating 79 * the configuration 80 */ calculate(Configuration conf, Move move, Element elem)81 public double calculate(Configuration conf, Move move, Element elem) 82 throws PoolsException; 83 84 /** 85 * Set the objective's expression to the supplied parameter. 86 * 87 * @param exp An expression for this objective. 88 */ setExpression(Expression exp)89 public void setExpression(Expression exp); 90 91 /** 92 * Get the objective's expression. 93 */ getExpression()94 public Expression getExpression(); 95 } 96 97 /** 98 * This interface must be implemented by all Objectives which are 99 * workload dependent. The examine method is used by a Solver to 100 * determine if the objective is still being satisfied. 101 */ 102 interface WorkloadDependentObjective extends Objective 103 { 104 /** 105 * This method returns true if the Objective is no longer 106 * satisfied. If the objective is still satisfied, then return 107 * false. 108 * 109 * @param conf The configuration to be examined 110 * @param solver The solving interface used to get utilization 111 * information 112 * @param elem The element to which the objective belongs 113 * 114 * @throws PoolsException if there is an error examining the 115 * pool configuration 116 * @throws StaleMonitorException if there is an error accessing 117 * the element's ResourceMonitor 118 */ examine(Configuration conf, Solver solver, Element elem)119 public boolean examine(Configuration conf, Solver solver, 120 Element elem) throws PoolsException, StaleMonitorException; 121 } 122 123 /** 124 * This class provides a skeletal implementation of the 125 * <code>Objective</code> interface to minimize the effort required 126 * to implement this interface. 127 * 128 * To implement an objective, the programmer need only to extend this 129 * class and add the name of the class into the appropriate element 130 * objectives property in the <code>poold.properties</code> file. 131 */ 132 abstract class AbstractObjective implements Objective 133 { calculate(Configuration conf, Move move, Element elem)134 abstract public double calculate(Configuration conf, Move move, 135 Element elem) throws PoolsException; 136 137 /** 138 * The objectives which are recognized by this class 139 */ 140 private static Map objectives; 141 142 /** 143 * The expression associated with this objective 144 */ 145 private Expression exp; 146 147 /** 148 * Set the objective's expression to the supplied parameter. 149 * 150 * @param exp An expression for this objective. 151 */ setExpression(Expression exp)152 public void setExpression(Expression exp) 153 { 154 this.exp = exp; 155 } 156 157 /** 158 * Get the objective's expression. 159 */ getExpression()160 public Expression getExpression() 161 { 162 return (exp); 163 } 164 165 /** 166 * A factory method which returns a created objective which is 167 * associated with the supplied expression. The type and the 168 * expression are used to identify valid types of objectives 169 * to which this expression may be applied. If an acceptable 170 * objective cannot be found for the supplied type, then an 171 * <code>IllegalArgumentException</code> will be thrown. 172 * 173 * @param type The element type for which an objective must be 174 * found 175 * @param exp The expression which will be associated with the 176 * objective 177 * 178 * @throws IllegalArgumentExcetion if the supplied expression 179 * cannot be associated with an objective of the supplied type 180 */ getInstance(String type, Expression exp)181 public static Objective getInstance(String type, Expression exp) 182 throws IllegalArgumentException 183 { 184 Objective ret = null; 185 Map typeObjs = null; 186 187 initMapIfNecessary(); 188 typeObjs = (Map)objectives.get(type); 189 if (typeObjs != null) { 190 Class objClass = (Class)typeObjs.get(exp.getName()); 191 if (objClass != null) { 192 try { 193 ret = (Objective) objClass. 194 newInstance(); 195 } catch (Exception e) { 196 Poold.utility.die(Poold.OPT_LOG, e, 197 true); 198 } 199 ret.setExpression(exp); 200 } 201 } 202 if (ret == null) 203 throw new IllegalArgumentException( 204 "unrecognized objective name for " + type + ": " + 205 exp.toString()); 206 return (ret); 207 } 208 209 /** 210 * Return a string representation of this objective. 211 */ toString()212 public String toString() 213 { 214 return (exp.toString()); 215 } 216 217 /** 218 * Initialize the implementation map the first time it's 219 * called. 220 */ initMapIfNecessary()221 private static void initMapIfNecessary() 222 { 223 /* 224 * Setup the objectives map for the known classes 225 */ 226 if (objectives == null) { 227 objectives = new HashMap(); 228 Properties props = new Properties(); 229 try { 230 props.load( 231 new FileInputStream( 232 Poold.POOLD_PROPERTIES_PATH)); 233 } catch (IOException ioe) { 234 Poold.utility.die(Poold.CONF_LOG, ioe); 235 } 236 registerObjectives(props, objectives, "system"); 237 registerObjectives(props, objectives, "pset"); 238 } 239 } 240 241 /** 242 * Add the objectives contained in the supplied properties to 243 * the set of valid objectives. The objectives are updated 244 * with objectives of the supplied type contained in the 245 * properties. 246 * 247 * @param props The properties containing the objectives 248 * @param objectives The objectives to be updated 249 * @param type The type of objectives to be added 250 */ registerObjectives(Properties props, Map objectives, String type)251 private static void registerObjectives(Properties props, 252 Map objectives, String type) 253 { 254 Map typeObjs = new HashMap(); 255 String objs = props.getProperty(type + ".objectives"); 256 String objNames[] = objs.split(","); 257 for (int i = 0; i < objNames.length; i++) { 258 String objName = objNames[i].trim(); 259 try { 260 Class clazz = Class.forName(objName); 261 Field field = clazz.getDeclaredField("name"); 262 String key = (String) field.get(null); 263 typeObjs.put(key, clazz); 264 } catch (ClassNotFoundException cnfe) { 265 Poold.utility.die(Poold.CONF_LOG, cnfe); 266 } catch (NoSuchFieldException nsfe) { 267 Poold.utility.die(Poold.CONF_LOG, nsfe); 268 } catch (IllegalAccessException iae) { 269 Poold.utility.die(Poold.CONF_LOG, iae); 270 } 271 } 272 objectives.put(type, typeObjs); 273 } 274 275 /** 276 * Indicates whether some other Objective is "equal to this 277 * one. 278 * @param o the reference object with which to compare. 279 * @return <code>true</code> if this object is the same as the 280 * o argument; <code>false</code> otherwise. 281 * @see #hashCode() 282 */ equals(Object o)283 public boolean equals(Object o) 284 { 285 if (o == this) 286 return (true); 287 if (!(o instanceof Objective)) 288 return (false); 289 Objective other = (Objective) o; 290 291 return (getExpression().equals(other.getExpression())); 292 } 293 294 /** 295 * Returns a hash code value for the object. This method is 296 * supported for the benefit of hashtables such as those provided by 297 * <code>java.util.Hashtable</code>. 298 * 299 * @return a hash code value for this object. 300 * @see #equals(java.lang.Object) 301 * @see java.util.Hashtable 302 */ hashCode()303 public int hashCode() 304 { 305 return (getExpression().hashCode()); 306 } 307 } 308 309 310 /** 311 * The <code>WeightedLoadObjective</code> class implements a Weighted 312 * Load Objective for <code>Poold</code>. 313 * 314 * The goal is to allocate more resources to those resource partitions 315 * which are heavily loaded. The weighting is determined from the 316 * objective importance and the pool.importance. 317 */ 318 final class WeightedLoadObjective extends AbstractObjective 319 implements WorkloadDependentObjective 320 { 321 /** 322 * The name of the class. 323 */ 324 static final String name = "wt-load"; 325 326 /** 327 * The map of calculations made during examination. 328 */ 329 Map calcMap; 330 331 /** 332 * Determine whether an objective is satisfied. If the 333 * objective is still satisfied, return false; otherwise 334 * return true. 335 * 336 * This objective examination determines if all resource sets 337 * are allocated the share of resources that their utilization 338 * would indicate they should be. This attempts to ensure that 339 * highly utilized resource sets recieve the greater 340 * proportion of available resources. 341 * 342 * @param conf The configuration to be examined 343 * @param solver The solving interface used to get utilization 344 * information 345 * @param elem The element to which the objective belongs 346 * 347 * @throws PoolsException if there is an error examining the 348 * pool configuration 349 * @throws StaleMonitorException if there is an error accessing 350 * the element's ResourceMonitor 351 */ examine(Configuration conf, Solver solver, Element elem)352 public boolean examine(Configuration conf, Solver solver, 353 Element elem) throws PoolsException, StaleMonitorException 354 { 355 Monitor mon = solver.getMonitor(); 356 Value val = new Value("type", "pset"); 357 List valueList = new LinkedList(); 358 calcMap = new HashMap(); 359 valueList.add(val); 360 361 List resList = conf.getResources(valueList); 362 val.close(); 363 Iterator itRes = resList.iterator(); 364 365 Calculation.totalUtil = 0; 366 Calculation.resQ = 0; 367 368 while (itRes.hasNext()) { 369 Resource res = (Resource) itRes.next(); 370 List CPUs = res.getComponents(null); 371 372 try { 373 Calculation calc = new Calculation(res, CPUs, 374 mon.getUtilization(res), 375 res.getLongProperty("pset.min"), 376 res.getLongProperty("pset.max")); 377 calcMap.put(res, calc); 378 } catch (StaleMonitorException sme) { 379 Poold.MON_LOG.log(Severity.INFO, 380 res.toString() + 381 " not participating in " + toString() + 382 " calculatation as it has no " + 383 "available statistics."); 384 } 385 } 386 Iterator itCalc = calcMap.values().iterator(); 387 while (itCalc.hasNext()) { 388 Calculation calc = (Calculation) itCalc.next(); 389 if (calc.getShare() != calc.comp.size() && 390 calc.getShare() >= calc.min) { 391 Poold.MON_LOG.log(Severity.INFO, 392 elem.toString() + 393 " utilization objective not satisfied " + 394 toString() + " with desired share " + 395 calc.getShare() + " and actual share " + 396 calc.comp.size()); 397 return (true); 398 } 399 } 400 return (false); 401 } 402 403 /** 404 * Holds data about weighted load calculations. This class is 405 * basically a structure which holds information specific to a 406 * weighted-load calculation 407 */ 408 static class Calculation { 409 /** 410 * The resource on which this calculation is based. 411 */ 412 Resource res; 413 414 /** 415 * The list of component resources held by this resource. 416 */ 417 List comp; 418 419 /** 420 * The utilization of this resource. 421 */ 422 double util; 423 424 /** 425 * The minimum value of this resource's size. 426 */ 427 long min; 428 429 /** 430 * The maximum value of this resource's size. 431 */ 432 long max; 433 434 /** 435 * The total utilization of all instances of this class. 436 */ 437 static double totalUtil; 438 439 /** 440 * The total quantity of resource for all instances of 441 * this class. 442 */ 443 static int resQ; 444 445 /** 446 * Constructor. The class is immutable and holds 447 * information specific to a set of calculations about 448 * load. 449 * 450 * @param res The resource set 451 * @param comp The resource components 452 * @param util The resource utilization 453 * @param min The minimum qty of resource for this set 454 * @param max The maximum qty of resource for this set 455 */ Calculation(Resource res, List comp, double util, long min, long max)456 public Calculation(Resource res, List comp, double util, 457 long min, long max) 458 { 459 this.res = res; 460 this.comp = comp; 461 this.min = min; 462 this.max = max; 463 this.util = (util / 100) * comp.size(); 464 Calculation.totalUtil += this.util; 465 Calculation.resQ += comp.size(); 466 } 467 468 /** 469 * Return the share of the total resource for this 470 * resource. 471 */ getShare()472 long getShare() 473 { 474 if (util == 0) 475 return (0); 476 return (Math.round((util / totalUtil) * resQ)); 477 } 478 toString()479 public String toString() 480 { 481 StringBuffer buf = new StringBuffer(); 482 buf.append("res: " + res.toString()); 483 buf.append(" components: " + comp.toString()); 484 buf.append(" min: " + min); 485 buf.append(" max: " + max); 486 buf.append(" util: " + util); 487 buf.append(" total resource: " + resQ); 488 buf.append(" total utilization: " + totalUtil); 489 buf.append(" share: " + getShare()); 490 return (buf.toString()); 491 } 492 } 493 494 /** 495 * Calculates the value of a configuration in terms of this 496 * objective. 497 * 498 * In the examination step, calculations of each resource's 499 * current and desired share were made. The moves can thus be 500 * assessed in terms of their impact upon the desired 501 * share. The current difference from desired is already 502 * known, so each move will serve to reduce or increase that 503 * difference. Moves that increase the difference have a 504 * negative score, those that reduce it have a positive 505 * score. All scores are normalized to return a value between 506 * -1 and 1. 507 * 508 * @param conf Configuration to be scored. 509 * @param move Move to be scored. 510 * @param elem The element to which the objective applies 511 * @throws PoolsException If an there is an error in execution. 512 */ calculate(Configuration conf, Move move, Element elem)513 public double calculate(Configuration conf, Move move, Element elem) 514 throws PoolsException 515 { 516 double ret = 0; 517 518 Poold.OPT_LOG.log(Severity.DEBUG, 519 "Calculating objective type: " + name); 520 /* 521 * There shouldn't be any empty moves, but if there 522 * are they are rated at 0. 523 */ 524 if (move.getQty() == 0) 525 return (0); 526 527 /* 528 * Find the calculations that represent the source and 529 * target of the move. 530 */ 531 Calculation src = (Calculation) calcMap.get(move.getFrom()); 532 Calculation tgt = (Calculation) calcMap.get(move.getTo()); 533 534 /* 535 * Use the calculation details to determine the "gap" 536 * i.e. number of discrete resources (for a processor 537 * set these are CPUs), between the desired quantity in 538 * the set which the calculations represent. Do this 539 * both before and after the proposed move. 540 * 541 * The maximum possible improvement is equal to the 542 * total number of resources for each set participating 543 * in the calculation. Since there are two sets we 544 * know the maximum possible improvement is resQ * 2. 545 * 546 * Divide the aggregated change in gap across participating 547 * sets by the maximum possible improvement to obtain 548 * a value which scores the move and which is normalised 549 * between -1 <= ret <= 1. 550 */ 551 long oldGap = Math.abs(src.getShare() - 552 src.comp.size()); 553 long newGap = Math.abs(src.getShare() - 554 (src.comp.size() - move.getQty())); 555 ret = oldGap - newGap; 556 oldGap = Math.abs(tgt.getShare() - 557 tgt.comp.size()); 558 newGap = Math.abs(tgt.getShare() - 559 (tgt.comp.size() + move.getQty())); 560 ret += oldGap - newGap; 561 ret /= ((double) Calculation.resQ * 2); 562 563 Poold.MON_LOG.log(Severity.DEBUG, "ret: " + ret); 564 return (ret); 565 } 566 } 567 568 /* 569 * The following LGroupData and Resulttuple and PSETData classes 570 * are used for the purposes of calculating and storing 571 * results sets for the LocalityObjective calculate method. 572 */ 573 574 /* 575 * To store data for a Localitygroup. 576 * 577 * The lgroup is the LocalityGroup. 578 * The numcpu is the number of cpu in the LocalityGroup. 579 * The factor is a value required in calculating the LocalityGroup quotient. 580 * 581 * The value of factor will always be a finite number 582 * because the LocalityGroup will never be empty. 583 */ 584 final class LGroupData 585 { 586 private LocalityGroup lgroup; 587 private int numcpu = 0; 588 private double factor; 589 LGroupData(LocalityGroup l)590 LGroupData(LocalityGroup l) { 591 lgroup = l; 592 int numcpuinlgroup = lgroup.getCPUIDs().length; 593 factor = 2.0 / ((numcpuinlgroup * numcpuinlgroup) 594 + numcpuinlgroup); 595 } 596 getNumcpu()597 int getNumcpu() { 598 return numcpu; 599 } 600 getFactor()601 double getFactor() { 602 return factor; 603 } 604 incNumcpu()605 void incNumcpu() { 606 numcpu++; 607 } 608 } 609 610 /* 611 * Stores the results of caclulated locality quotients for a PSET. 612 * 613 * The AsIsResult is the quotient without any move. 614 * The FromResult is the quotient when a cpu is taken from it. 615 * The To result is the quotient when a cpu is added to it. 616 */ 617 final class ResultTuple 618 { 619 private double AsIsResult = 0; 620 private double FromResult = 0; 621 private double ToResult = 0; 622 ResultTuple(double a, double f, double t)623 ResultTuple(double a, double f, double t) { 624 setAsIsResult(a); 625 setFromResult(f); 626 setToResult(t); 627 } 628 getAsIsResult()629 double getAsIsResult() { 630 return AsIsResult; 631 } 632 getFromResult()633 double getFromResult() { 634 return FromResult; 635 } 636 getToResult()637 double getToResult() { 638 return ToResult; 639 } 640 setAsIsResult(double asis)641 void setAsIsResult(double asis) { 642 AsIsResult = asis; 643 } 644 setFromResult(double from)645 void setFromResult(double from) { 646 FromResult = from; 647 } 648 setToResult(double to)649 void setToResult(double to) { 650 ToResult = to; 651 } 652 } 653 654 /* 655 * The PSETData class enables storage and population of the data 656 * required for the LocalityObjective calculate() method. 657 * 658 * The lgroupdata HashMap stores LGroupData objects 659 * for each LGroup in the pset. 660 * The results HashMap stores resultsTuple objects for each LGroup. 661 * The countLgroups() method populates the lgroupdata HashMap. 662 * The calcQ() method calculates the quotient for any given 663 * value of intersection and lgroup size. 664 * The calcResults() method populates the results HashMap. 665 */ 666 final class PSETData 667 { 668 private Resource pset; 669 private Map<LocalityGroup, LGroupData> lgroupdata 670 = new HashMap<LocalityGroup, LGroupData>(); 671 private Map<LocalityGroup, ResultTuple> results 672 = new HashMap<LocalityGroup, ResultTuple>(); 673 double AsIsTotal = 0; 674 int numlg = 0; 675 getAsIsTotal()676 double getAsIsTotal() { 677 return AsIsTotal; 678 } 679 getResults()680 Map<LocalityGroup, ResultTuple> getResults() { 681 return results; 682 } 683 684 /* 685 * Count the number of cpu in each locality group in this pset 686 * and count the number of locality groups in this pset. 687 * 688 * @param allCPUData Map of all cpu and their LocalityGroup. 689 * 690 * @throws new PoolsException if no lgroups found, i.e numlg = 0; 691 */ countLgroups(Map allCPUData)692 private void countLgroups(Map allCPUData) 693 throws PoolsException 694 { 695 List cpuList = pset.getComponents(null); 696 Iterator cpuIt = cpuList.iterator(); 697 while (cpuIt.hasNext()) { 698 Component currentCPU = (Component) cpuIt.next(); 699 int cpuid = (int) currentCPU.getLongProperty("cpu.sys_id"); 700 if (allCPUData.containsKey(new Integer(cpuid))) { 701 LocalityGroup lg = 702 (LocalityGroup) allCPUData.get(new Integer(cpuid)); 703 if (lgroupdata.containsKey(lg)) { 704 LGroupData cpulgp = (LGroupData) lgroupdata.get(lg); 705 cpulgp.incNumcpu(); 706 } 707 } 708 } 709 Set groups = lgroupdata.keySet(); 710 Iterator groupsIt = groups.iterator(); 711 while (groupsIt.hasNext()) { 712 LocalityGroup lg = (LocalityGroup) groupsIt.next(); 713 LGroupData cpulgp = (LGroupData) lgroupdata.get(lg); 714 if (cpulgp.getNumcpu() > 0) { 715 numlg++; 716 } 717 } 718 if (numlg == 0) { 719 throw new PoolsException(); 720 } 721 } 722 723 /** 724 * Calculate the final quotient with the given 725 * factor and intersection values. 726 * 727 * @param factor double value of factor for this move. 728 * @param intersection int value of intersection for this move. 729 */ calcQ(double factor, int intersection)730 private double calcQ(double factor, int intersection) 731 { 732 double q = factor * ((intersection * intersection) 733 + intersection) / 2.0; 734 return (q); 735 } 736 737 /* 738 * Calulate results for all locality groups for this pset. 739 * 740 * The logic considers all cases of pset populations; 741 * i) pset is empty; ii) pset has only one cpu; 742 * iii) pset more than one cpu. 743 * numlg is never zero so we need not try and catch that here. 744 */ calcqA()745 private void calcqA() 746 throws PoolsException 747 { 748 Set allgroups = (Set) results.keySet(); 749 Iterator groupIt = (Iterator) allgroups.iterator(); 750 while (groupIt.hasNext()) { 751 LocalityGroup lgroup = (LocalityGroup) groupIt.next(); 752 if (lgroupdata.containsKey(lgroup)) { 753 LGroupData cpulgp = 754 (LGroupData) lgroupdata.get(lgroup); 755 ResultTuple rst = (ResultTuple) results.get(lgroup); 756 if (cpulgp.getNumcpu() == 0) { 757 double toresult = 758 (AsIsTotal + rst.getToResult())/(numlg + 1); 759 rst.setToResult(toresult); 760 } 761 if (cpulgp.getNumcpu() == 1) { 762 double fromresult = 763 (AsIsTotal + rst.getFromResult()) 764 /(numlg - 1); 765 rst.setFromResult(fromresult); 766 } 767 if (cpulgp.getNumcpu() > 1) { 768 double toresult = (AsIsTotal 769 - rst.getAsIsResult() 770 + rst.getToResult())/(numlg); 771 rst.setToResult(toresult); 772 double fromresult = (AsIsTotal 773 - rst.getAsIsResult() 774 + rst.getFromResult())/(numlg); 775 rst.setFromResult(fromresult); 776 } 777 results.put(lgroup, rst); 778 } 779 } 780 } 781 782 /* 783 * Populates the results map for each locality group. 784 * 785 * numlg is never zero so do not need to try and catch it. 786 * 787 * @param allLGroups Set of all Locality groups in this config. 788 */ calcResults(Set allLGroups)789 private void calcResults(Set allLGroups) 790 throws PoolsException 791 { 792 Iterator groupIt = (Iterator) allLGroups.iterator(); 793 while (groupIt.hasNext()) { 794 int intersection = 0; 795 double factor = 0; 796 LocalityGroup lgroup = (LocalityGroup) groupIt.next(); 797 if (lgroup.getCPUIDs().length != 0) { 798 if (lgroupdata.containsKey(lgroup)) { 799 LGroupData cpulgp = 800 (LGroupData)lgroupdata.get(lgroup); 801 intersection = cpulgp.getNumcpu(); 802 factor = cpulgp.getFactor(); 803 } 804 ResultTuple thisresult = new ResultTuple( 805 calcQ(factor, intersection), 806 calcQ(factor, intersection-1), 807 calcQ(factor, intersection+1)); 808 AsIsTotal += thisresult.getAsIsResult(); 809 results.put(lgroup, thisresult); 810 } 811 } 812 calcqA(); 813 AsIsTotal /= numlg; 814 } 815 816 /* 817 * Constructor for PSETData. 818 * 819 * @param allLGroups Set of all Locality groups in this config. 820 * @param allCPUData Map of all cpu and their locality group. 821 * @param p Resource (pset) for which the calculations are made. 822 * 823 * @throws PoolsException if accessing the supplied resource 824 * fails. 825 */ PSETData(Set allLGroups, Map allCPUData, Resource p)826 PSETData(Set allLGroups, Map allCPUData, Resource p) 827 throws PoolsException 828 { 829 pset = p; 830 Iterator groupIt = (Iterator) allLGroups.iterator(); 831 while (groupIt.hasNext()) { 832 LocalityGroup lgroup = (LocalityGroup) groupIt.next(); 833 if (lgroup.getCPUIDs().length != 0) { 834 LGroupData cpulgp = new LGroupData(lgroup); 835 lgroupdata.put(lgroup, cpulgp); 836 } 837 } 838 countLgroups(allCPUData); 839 calcResults(allLGroups); 840 } 841 } 842 843 /** 844 * A locality based objective which will assess moves in terms of 845 * their impact on the locality of the sets of resources which are 846 * impacted. 847 * 848 * The objective will assess moves with respect to the type of 849 * locality specified in the objective: 850 * 851 * <ul> 852 * <li><p> 853 * tight - resource locality is sought 854 * <li><p> 855 * loose - resource locality is avoided 856 * <li><p> 857 * none - resource locality has no impact 858 * </ul> 859 */ 860 final class LocalityObjective extends AbstractObjective 861 { 862 /* 863 * The name of the class. 864 */ 865 static final String name = "locality"; 866 867 /* 868 * The locality domain used to describe locality for this 869 * objective. 870 */ 871 private LocalityDomain ldom; 872 873 /* 874 * The set of LocalityGroups in this ldom. 875 */ 876 private Set allLGroups; 877 878 /* 879 * Map of all cpu id and their locality groups 880 */ 881 private Map<Integer, LocalityGroup> allCPUData 882 = new HashMap<Integer, LocalityGroup>(); 883 884 /* 885 * Method to populate the allCPUData cpu locality map. 886 */ getCPUData()887 private void getCPUData() 888 { 889 allLGroups = ldom.getGroups(); 890 Iterator LGroupIt = allLGroups.iterator(); 891 while (LGroupIt.hasNext()) { 892 LocalityGroup lg = (LocalityGroup) LGroupIt.next(); 893 int cpu_ids[] = lg.getCPUIDs(); 894 for (int i = 0; i < cpu_ids.length; i++) { 895 allCPUData.put(new Integer(cpu_ids[i]), lg); 896 } 897 } 898 899 } 900 901 /* 902 * Map to store all PSET LocalityGroup quotient results. 903 */ 904 private Map<Resource, PSETData> allPSETData 905 = new HashMap<Resource, PSETData>(); 906 907 /** 908 * Prepare the calculation for this objective for the resource to 909 * which it applies. 910 * 911 * @param ldom LocalityDomain containing these resources. 912 * @param res Resource to which this objective is applied. 913 * 914 * @throws PoolsException if accessing the supplied resource 915 * fails. 916 */ prepare(LocalityDomain ldom, Resource res)917 public void prepare(LocalityDomain ldom, Resource res) 918 throws PoolsException 919 { 920 this.ldom = ldom; 921 } 922 923 /* 924 * Calculates the value of a configuration in terms of this 925 * objective. 926 * 927 * Firstly check to see if it is possible to short-cut the 928 * calculation. If not, then start to examine the disposition 929 * of CPUs and locality groups in relation to the processor 930 * set being evaluated. The objective scores moves in terms of 931 * their impact upon the quotient of cpus contained in each 932 * locality group. 933 * 934 * Moves which involve a cpu in the same locality group are equivalent. 935 * i.e for a given pset, the quotient calculation is the same 936 * for a move involving cpu x in localitygroup Z, 937 * as the calculation for cpu y in localitygroup Z, 938 * So we store the quotient calculation of the PSET 939 * i) as it is; ii) a cpu is added; iii) a cpu is removed; 940 * 941 * For each move we encounter, we store the quotient caclulations 942 * on a pset basis, holding a map of results for each pset we evaluate. 943 * The map contains results for each locality group in the system. 944 * The results contains the quotient value for a move of a cpu 945 * to, from and without any move. 946 * 947 * For a given configuration, for each cpu we make one JNI call 948 * to getLongProperty() (which is the most expensive call in this code) 949 * so the time spent in calculate() scales linearly with number of cpu. 950 * 951 * @param conf Configuration to be scored. 952 * @param move Move to be scored. 953 * @param elem The element to which the objective applies 954 * @throws Exception If an there is an error in execution. 955 */ calculate(Configuration conf, Move move, Element elem)956 public double calculate(Configuration conf, Move move, Element elem) 957 throws PoolsException 958 { 959 KVExpression kve = (KVExpression) getExpression(); 960 double ret = 0; 961 double qA = 0; 962 double qB = 0; 963 Resource pset = (Resource) elem; 964 ComponentMove cm = (ComponentMove) move; 965 Poold.MON_LOG.log(Severity.DEBUG, 966 "Calculating objective type: " + name + " for: " + elem); 967 968 /* 969 * If we are set to "none" then we don't care which 970 * configuration so just return 0. 971 */ 972 if (kve.getValue().compareTo("none") == 0) 973 return (ret); 974 /* 975 * If the maximum latency is 0, we don't care about 976 * latency. 977 */ 978 if (ldom.getMaxLatency() == 0) 979 return (ret); 980 /* 981 * If this element doesn't participate in the move, we 982 * should return 0. 983 */ 984 if (elem.equals(move.getFrom()) == false && 985 elem.equals(move.getTo()) == false) 986 return (ret); 987 988 /* 989 * Populate the map of cpu - locality data if it is empty. 990 */ 991 if (allCPUData.isEmpty()) { 992 getCPUData(); 993 } 994 995 /* 996 * Lookup in the pset results map if the pset entry exists. 997 * If this pset entry exists then use it otherwise add it. 998 */ 999 PSETData psetlg; 1000 1001 if (allPSETData.containsKey(pset)) 1002 psetlg = (PSETData) allPSETData.get(pset); 1003 else { 1004 psetlg = new PSETData(allLGroups, allCPUData, pset); 1005 allPSETData.put(pset, psetlg); 1006 } 1007 1008 /* 1009 * Check the locality group of the cpu involved in this move. 1010 * If it is a cpu from a locality group we have already seen, 1011 * then we can retrieve the results from the pset results map. 1012 */ 1013 List cpulist = (List) cm.getComponents(); 1014 Component cpu = (Component) cpulist.get(0); 1015 int cpuid = (int) cpu.getLongProperty("cpu.sys_id"); 1016 LocalityGroup lgroup = 1017 (LocalityGroup) allCPUData.get(new Integer(cpuid)); 1018 HashMap allresults = (HashMap) psetlg.getResults(); 1019 ResultTuple result = (ResultTuple) allresults.get(lgroup); 1020 1021 qB = psetlg.getAsIsTotal(); 1022 if (elem.equals(move.getFrom())) 1023 qA = result.getFromResult(); 1024 else 1025 qA = result.getToResult(); 1026 1027 ret = qA - qB; 1028 1029 /* 1030 * We return the value based on what locality objective 1031 * we want to achieve - tight or loose. The calculations 1032 * are based on tightness, so the value is reversed if the 1033 * objective specified "loose" locality. 1034 */ 1035 if (kve.getValue().compareTo("loose") == 0) 1036 ret = 0 - ret; 1037 Poold.MON_LOG.log(Severity.DEBUG, "ret: " + ret); 1038 return (ret); 1039 } 1040 } 1041 /** 1042 * A resource set utilization based objective which will assess moves 1043 * in terms of their (likely) impact on the future performance of a 1044 * resource set with respect to it's specified utilization objective. 1045 * 1046 * The utilization objective must be specified in terms of a 1047 * KVOpExpression, see the class definition for information about the 1048 * form of these expressions. The objective can be examined in terms 1049 * of it's compliance with the aid of a monitoring object. The actual 1050 * assessment of compliance is indicated by the associated monitoring 1051 * object, with this class simply acting as a co-ordinator of the 1052 * relevant information. 1053 */ 1054 final class UtilizationObjective extends AbstractObjective 1055 implements WorkloadDependentObjective 1056 { 1057 /** 1058 * The name of the class. 1059 */ 1060 static final String name = "utilization"; 1061 1062 /** 1063 * Short run detection. 1064 */ 1065 private List zoneList = new LinkedList(); 1066 1067 /** 1068 * Format for printing utilization. 1069 */ 1070 private static final DecimalFormat uf = new DecimalFormat("0.00"); 1071 1072 /** 1073 * Solver used to calculate delta, i.e. gap, between target and 1074 * actual utilization values. 1075 */ 1076 private Solver gapSolver; 1077 1078 /** 1079 * Determine whether an objective is satisfied. If the 1080 * objective is still satisfied, return false; otherwise 1081 * return true. 1082 * 1083 * The assessment of control is made by the monitoring class 1084 * using the supplied Expression and resource. 1085 * 1086 * @param conf The configuration to be examined 1087 * @param solver The solving interface used to get utilization 1088 * information 1089 * @param elem The element to which the objective belongs 1090 * 1091 * @throws PoolsException if there is an error examining the 1092 * pool configuration 1093 * @throws StaleMonitorException if there is an error accessing 1094 * the element's ResourceMonitor 1095 */ examine(Configuration conf, Solver solver, Element elem)1096 public boolean examine(Configuration conf, Solver solver, 1097 Element elem) throws PoolsException, StaleMonitorException 1098 { 1099 KVOpExpression kve = (KVOpExpression) getExpression(); 1100 ResourceMonitor mon; 1101 1102 /* 1103 * If there is no resource monitor, then we cannot 1104 * make an assessment of the objective's achievability. 1105 * Log a message to make clear that this objective is 1106 * not being assessed and then indicate that 1107 * the objective has been achieved. 1108 */ 1109 try { 1110 mon = solver.getMonitor().get((Resource)elem); 1111 } catch (StaleMonitorException sme) { 1112 Poold.MON_LOG.log(Severity.INFO, 1113 elem.toString() + 1114 " utilization objective not measured " + 1115 toString() + " as there are no available " + 1116 "statistics."); 1117 return (false); 1118 } 1119 gapSolver = solver; 1120 1121 double val = solver.getMonitor().getUtilization((Resource)elem); 1122 1123 StatisticList sl = (StatisticList) mon.get("utilization"); 1124 int zone = sl.getZone(kve, val); 1125 1126 if (zoneList.size() == 9) { 1127 zoneList.remove(0); 1128 } 1129 zoneList.add(new Integer(sl.getZoneMean(val))); 1130 1131 /* 1132 * Evaluate whether or not this objective is under 1133 * control. 1134 */ 1135 if ((zone & StatisticOperations.ZONEZ) == 1136 StatisticOperations.ZONEZ) { 1137 /* 1138 * If the objective is GT or LT, then don't 1139 * return true as long as the objective is 1140 * satisfied. 1141 */ 1142 if (kve.getOp() == KVOpExpression.LT && 1143 (zone & StatisticOperations.ZONET) == 1144 StatisticOperations.ZONELT) 1145 return (false); 1146 1147 if (kve.getOp() == KVOpExpression.GT && 1148 (zone & StatisticOperations.ZONET) == 1149 StatisticOperations.ZONEGT) 1150 return (false); 1151 Poold.MON_LOG.log(Severity.INFO, 1152 elem.toString() + 1153 " utilization objective not satisfied " + 1154 toString() + " with utilization " + uf.format(val) + 1155 " (control zone bounds exceeded)"); 1156 return (true); 1157 } 1158 /* 1159 * Check if our statistics need to be recalculated. 1160 */ 1161 checkShort(mon, elem, val); 1162 return (false); 1163 } 1164 1165 /** 1166 * Calculates the value of a configuration in terms of this 1167 * objective. 1168 * 1169 * Every set must be classified with a control zone when this 1170 * function is called. The move can be assessed in terms of 1171 * the control violation type. zone violations which are minor 1172 * are offered a lower contribution than more significant 1173 * violations. 1174 * 1175 * @param conf Configuration to be scored. 1176 * @param move Move to be scored. 1177 * @param elem The element to which the objective applies 1178 * @throws Exception If an there is an error in execution. 1179 */ calculate(Configuration conf, Move move, Element elem)1180 public double calculate(Configuration conf, Move move, Element elem) 1181 throws PoolsException 1182 { 1183 KVOpExpression kve = (KVOpExpression) getExpression(); 1184 double ret; 1185 1186 /* 1187 * If the move is from the examined element, then 1188 * check to see if the recipient has any 1189 * objectives. If not, score the move poorly since we 1190 * should never want to transfer resources to a 1191 * recipient with no objectives. If there are 1192 * objectives, then return the delta between target 1193 * performance and actual performance for this 1194 * element. 1195 * 1196 * If the move is to the examined element, then check 1197 * to see if the donor has any objectives. If not, 1198 * score the move highly, since we want to favour 1199 * those resources with objectives. If there are 1200 * objectives, return the delta between actual and 1201 * target performance. 1202 * 1203 * If the element is neither the recipient or the 1204 * donor of this proposed move, then score the move 1205 * neutrally as 0. 1206 */ 1207 try { 1208 double val, gap; 1209 StatisticList sl; 1210 1211 if (elem.equals(move.getFrom())) { 1212 val = gapSolver.getMonitor(). 1213 getUtilization(move.getFrom()); 1214 sl = (StatisticList) gapSolver.getMonitor(). 1215 get(move.getFrom()).get("utilization"); 1216 gap = sl.getGap(kve, val) / 100; 1217 1218 if (gapSolver.getObjectives(move.getTo()) == 1219 null) { 1220 /* 1221 * Moving to a resource with 1222 * no objectives should always 1223 * be viewed unfavourably. The 1224 * degree of favourability is 1225 * thus bound between 0 and 1226 * -1. If the source gap is 1227 * negative, then subtract it 1228 * from -1 to get the 1229 * score. If positive, 1230 * just return -1. 1231 */ 1232 if (gap < 0) { 1233 ret = -1 - gap; 1234 } else { 1235 ret = -1; 1236 } 1237 } else { 1238 ret = 0 - gap; 1239 } 1240 } else if (elem.equals(move.getTo())) { 1241 val = gapSolver.getMonitor(). 1242 getUtilization(move.getTo()); 1243 sl = (StatisticList) gapSolver.getMonitor(). 1244 get(move.getTo()).get("utilization"); 1245 gap = sl.getGap(kve, val) / 100; 1246 1247 if (gapSolver.getObjectives(move.getFrom()) == 1248 null) { 1249 /* 1250 * Moving from a resource with 1251 * no objectives should always 1252 * be viewed favourably. The 1253 * degree of favourability is 1254 * thus bound between 0 and 1255 * 1. If the destination gap 1256 * is negative, then add to 1 1257 * to get the score. If 1258 * positive, just return 1. 1259 */ 1260 if (gap < 0) { 1261 ret = 0 - gap; 1262 } else { 1263 ret = 1; 1264 } 1265 } else { 1266 ret = 0 + gap; 1267 } 1268 } else { 1269 ret = 0; 1270 } 1271 } catch (StaleMonitorException sme) { 1272 /* 1273 * We should always find a monitor, 1274 * but if we can't then just assume 1275 * this is a neutral move and return 1276 * 0. 1277 */ 1278 ret = 0; 1279 } 1280 Poold.MON_LOG.log(Severity.DEBUG, "ret: " + ret); 1281 return (ret); 1282 } 1283 1284 /** 1285 * Check whether or not a set's statistics are still useful 1286 * for making decision.. 1287 * 1288 * Each set is controlled in terms of the zones of control 1289 * based in terms of standard deviations from a mean. If the 1290 * utilization of the set is not fluctuating normally around a 1291 * mean, these checks will cause the accumulated statistics to 1292 * be discarded and control suspended until a new sufficient 1293 * set of data is accumulated. 1294 * 1295 * @param mon Resource monitor to examine. 1296 * @param elem Element to which the resource monitor belongs. 1297 * @param val Latest monitored value. 1298 */ checkShort(ResourceMonitor mon, Element elem, double val)1299 private void checkShort(ResourceMonitor mon, Element elem, double val) 1300 { 1301 boolean checkOne = true; 1302 int checkOnePos = 0; 1303 boolean doCheckOne = false; 1304 1305 Iterator itZones = zoneList.iterator(); 1306 while (itZones.hasNext()) { 1307 int zone = ((Integer) itZones.next()).intValue(); 1308 if (doCheckOne) { 1309 if (checkOne) { 1310 if ((zone & StatisticOperations.ZONET) 1311 != checkOnePos) { 1312 checkOne = false; 1313 } 1314 } 1315 } else { 1316 if (zoneList.size() >= 9) { 1317 checkOnePos = zone & 1318 StatisticOperations.ZONET; 1319 doCheckOne = true; 1320 } 1321 } 1322 } 1323 if (zoneList.size() >= 9 && checkOne) { 1324 Poold.MON_LOG.log(Severity.INFO, 1325 elem.toString() + 1326 " utilization objective statistics reinitialized " + 1327 toString() + " with utilization " + uf.format(val) + 1328 " (nine points on same side of mean)"); 1329 mon.resetData("utilization"); 1330 zoneList.clear(); 1331 } 1332 } 1333 } 1334