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(Integer.valueOf(cpuid))) { 701 LocalityGroup lg = 702 (LocalityGroup) allCPUData.get( 703 Integer.valueOf(cpuid)); 704 if (lgroupdata.containsKey(lg)) { 705 LGroupData cpulgp = (LGroupData) lgroupdata.get(lg); 706 cpulgp.incNumcpu(); 707 } 708 } 709 } 710 Set groups = lgroupdata.keySet(); 711 Iterator groupsIt = groups.iterator(); 712 while (groupsIt.hasNext()) { 713 LocalityGroup lg = (LocalityGroup) groupsIt.next(); 714 LGroupData cpulgp = (LGroupData) lgroupdata.get(lg); 715 if (cpulgp.getNumcpu() > 0) { 716 numlg++; 717 } 718 } 719 if (numlg == 0) { 720 throw new PoolsException(); 721 } 722 } 723 724 /** 725 * Calculate the final quotient with the given 726 * factor and intersection values. 727 * 728 * @param factor double value of factor for this move. 729 * @param intersection int value of intersection for this move. 730 */ calcQ(double factor, int intersection)731 private double calcQ(double factor, int intersection) 732 { 733 double q = factor * ((intersection * intersection) 734 + intersection) / 2.0; 735 return (q); 736 } 737 738 /* 739 * Calulate results for all locality groups for this pset. 740 * 741 * The logic considers all cases of pset populations; 742 * i) pset is empty; ii) pset has only one cpu; 743 * iii) pset more than one cpu. 744 * numlg is never zero so we need not try and catch that here. 745 */ calcqA()746 private void calcqA() 747 throws PoolsException 748 { 749 Set allgroups = (Set) results.keySet(); 750 Iterator groupIt = (Iterator) allgroups.iterator(); 751 while (groupIt.hasNext()) { 752 LocalityGroup lgroup = (LocalityGroup) groupIt.next(); 753 if (lgroupdata.containsKey(lgroup)) { 754 LGroupData cpulgp = 755 (LGroupData) lgroupdata.get(lgroup); 756 ResultTuple rst = (ResultTuple) results.get(lgroup); 757 if (cpulgp.getNumcpu() == 0) { 758 double toresult = 759 (AsIsTotal + rst.getToResult())/(numlg + 1); 760 rst.setToResult(toresult); 761 } 762 if (cpulgp.getNumcpu() == 1) { 763 double fromresult = 764 (AsIsTotal + rst.getFromResult()) 765 /(numlg - 1); 766 rst.setFromResult(fromresult); 767 } 768 if (cpulgp.getNumcpu() > 1) { 769 double toresult = (AsIsTotal 770 - rst.getAsIsResult() 771 + rst.getToResult())/(numlg); 772 rst.setToResult(toresult); 773 double fromresult = (AsIsTotal 774 - rst.getAsIsResult() 775 + rst.getFromResult())/(numlg); 776 rst.setFromResult(fromresult); 777 } 778 results.put(lgroup, rst); 779 } 780 } 781 } 782 783 /* 784 * Populates the results map for each locality group. 785 * 786 * numlg is never zero so do not need to try and catch it. 787 * 788 * @param allLGroups Set of all Locality groups in this config. 789 */ calcResults(Set allLGroups)790 private void calcResults(Set allLGroups) 791 throws PoolsException 792 { 793 Iterator groupIt = (Iterator) allLGroups.iterator(); 794 while (groupIt.hasNext()) { 795 int intersection = 0; 796 double factor = 0; 797 LocalityGroup lgroup = (LocalityGroup) groupIt.next(); 798 if (lgroup.getCPUIDs().length != 0) { 799 if (lgroupdata.containsKey(lgroup)) { 800 LGroupData cpulgp = 801 (LGroupData)lgroupdata.get(lgroup); 802 intersection = cpulgp.getNumcpu(); 803 factor = cpulgp.getFactor(); 804 } 805 ResultTuple thisresult = new ResultTuple( 806 calcQ(factor, intersection), 807 calcQ(factor, intersection-1), 808 calcQ(factor, intersection+1)); 809 AsIsTotal += thisresult.getAsIsResult(); 810 results.put(lgroup, thisresult); 811 } 812 } 813 calcqA(); 814 AsIsTotal /= numlg; 815 } 816 817 /* 818 * Constructor for PSETData. 819 * 820 * @param allLGroups Set of all Locality groups in this config. 821 * @param allCPUData Map of all cpu and their locality group. 822 * @param p Resource (pset) for which the calculations are made. 823 * 824 * @throws PoolsException if accessing the supplied resource 825 * fails. 826 */ PSETData(Set allLGroups, Map allCPUData, Resource p)827 PSETData(Set allLGroups, Map allCPUData, Resource p) 828 throws PoolsException 829 { 830 pset = p; 831 Iterator groupIt = (Iterator) allLGroups.iterator(); 832 while (groupIt.hasNext()) { 833 LocalityGroup lgroup = (LocalityGroup) groupIt.next(); 834 if (lgroup.getCPUIDs().length != 0) { 835 LGroupData cpulgp = new LGroupData(lgroup); 836 lgroupdata.put(lgroup, cpulgp); 837 } 838 } 839 countLgroups(allCPUData); 840 calcResults(allLGroups); 841 } 842 } 843 844 /** 845 * A locality based objective which will assess moves in terms of 846 * their impact on the locality of the sets of resources which are 847 * impacted. 848 * 849 * The objective will assess moves with respect to the type of 850 * locality specified in the objective: 851 * 852 * <ul> 853 * <li><p> 854 * tight - resource locality is sought 855 * <li><p> 856 * loose - resource locality is avoided 857 * <li><p> 858 * none - resource locality has no impact 859 * </ul> 860 */ 861 final class LocalityObjective extends AbstractObjective 862 { 863 /* 864 * The name of the class. 865 */ 866 static final String name = "locality"; 867 868 /* 869 * The locality domain used to describe locality for this 870 * objective. 871 */ 872 private LocalityDomain ldom; 873 874 /* 875 * The set of LocalityGroups in this ldom. 876 */ 877 private Set allLGroups; 878 879 /* 880 * Map of all cpu id and their locality groups 881 */ 882 private Map<Integer, LocalityGroup> allCPUData 883 = new HashMap<Integer, LocalityGroup>(); 884 885 /* 886 * Method to populate the allCPUData cpu locality map. 887 */ getCPUData()888 private void getCPUData() 889 { 890 allLGroups = ldom.getGroups(); 891 Iterator LGroupIt = allLGroups.iterator(); 892 while (LGroupIt.hasNext()) { 893 LocalityGroup lg = (LocalityGroup) LGroupIt.next(); 894 int cpu_ids[] = lg.getCPUIDs(); 895 for (int i = 0; i < cpu_ids.length; i++) { 896 allCPUData.put(Integer.valueOf(cpu_ids[i]), lg); 897 } 898 } 899 900 } 901 902 /* 903 * Map to store all PSET LocalityGroup quotient results. 904 */ 905 private Map<Resource, PSETData> allPSETData 906 = new HashMap<Resource, PSETData>(); 907 908 /** 909 * Prepare the calculation for this objective for the resource to 910 * which it applies. 911 * 912 * @param ldom LocalityDomain containing these resources. 913 * @param res Resource to which this objective is applied. 914 * 915 * @throws PoolsException if accessing the supplied resource 916 * fails. 917 */ prepare(LocalityDomain ldom, Resource res)918 public void prepare(LocalityDomain ldom, Resource res) 919 throws PoolsException 920 { 921 this.ldom = ldom; 922 } 923 924 /* 925 * Calculates the value of a configuration in terms of this 926 * objective. 927 * 928 * Firstly check to see if it is possible to short-cut the 929 * calculation. If not, then start to examine the disposition 930 * of CPUs and locality groups in relation to the processor 931 * set being evaluated. The objective scores moves in terms of 932 * their impact upon the quotient of cpus contained in each 933 * locality group. 934 * 935 * Moves which involve a cpu in the same locality group are equivalent. 936 * i.e for a given pset, the quotient calculation is the same 937 * for a move involving cpu x in localitygroup Z, 938 * as the calculation for cpu y in localitygroup Z, 939 * So we store the quotient calculation of the PSET 940 * i) as it is; ii) a cpu is added; iii) a cpu is removed; 941 * 942 * For each move we encounter, we store the quotient caclulations 943 * on a pset basis, holding a map of results for each pset we evaluate. 944 * The map contains results for each locality group in the system. 945 * The results contains the quotient value for a move of a cpu 946 * to, from and without any move. 947 * 948 * For a given configuration, for each cpu we make one JNI call 949 * to getLongProperty() (which is the most expensive call in this code) 950 * so the time spent in calculate() scales linearly with number of cpu. 951 * 952 * @param conf Configuration to be scored. 953 * @param move Move to be scored. 954 * @param elem The element to which the objective applies 955 * @throws Exception If an there is an error in execution. 956 */ calculate(Configuration conf, Move move, Element elem)957 public double calculate(Configuration conf, Move move, Element elem) 958 throws PoolsException 959 { 960 KVExpression kve = (KVExpression) getExpression(); 961 double ret = 0; 962 double qA = 0; 963 double qB = 0; 964 Resource pset = (Resource) elem; 965 ComponentMove cm = (ComponentMove) move; 966 Poold.MON_LOG.log(Severity.DEBUG, 967 "Calculating objective type: " + name + " for: " + elem); 968 969 /* 970 * If we are set to "none" then we don't care which 971 * configuration so just return 0. 972 */ 973 if (kve.getValue().compareTo("none") == 0) 974 return (ret); 975 /* 976 * If the maximum latency is 0, we don't care about 977 * latency. 978 */ 979 if (ldom.getMaxLatency() == 0) 980 return (ret); 981 /* 982 * If this element doesn't participate in the move, we 983 * should return 0. 984 */ 985 if (elem.equals(move.getFrom()) == false && 986 elem.equals(move.getTo()) == false) 987 return (ret); 988 989 /* 990 * Populate the map of cpu - locality data if it is empty. 991 */ 992 if (allCPUData.isEmpty()) { 993 getCPUData(); 994 } 995 996 /* 997 * Lookup in the pset results map if the pset entry exists. 998 * If this pset entry exists then use it otherwise add it. 999 */ 1000 PSETData psetlg; 1001 1002 if (allPSETData.containsKey(pset)) 1003 psetlg = (PSETData) allPSETData.get(pset); 1004 else { 1005 psetlg = new PSETData(allLGroups, allCPUData, pset); 1006 allPSETData.put(pset, psetlg); 1007 } 1008 1009 /* 1010 * Check the locality group of the cpu involved in this move. 1011 * If it is a cpu from a locality group we have already seen, 1012 * then we can retrieve the results from the pset results map. 1013 */ 1014 List cpulist = (List) cm.getComponents(); 1015 Component cpu = (Component) cpulist.get(0); 1016 int cpuid = (int) cpu.getLongProperty("cpu.sys_id"); 1017 LocalityGroup lgroup = 1018 (LocalityGroup) allCPUData.get(Integer.valueOf(cpuid)); 1019 HashMap allresults = (HashMap) psetlg.getResults(); 1020 ResultTuple result = (ResultTuple) allresults.get(lgroup); 1021 1022 qB = psetlg.getAsIsTotal(); 1023 if (elem.equals(move.getFrom())) 1024 qA = result.getFromResult(); 1025 else 1026 qA = result.getToResult(); 1027 1028 ret = qA - qB; 1029 1030 /* 1031 * We return the value based on what locality objective 1032 * we want to achieve - tight or loose. The calculations 1033 * are based on tightness, so the value is reversed if the 1034 * objective specified "loose" locality. 1035 */ 1036 if (kve.getValue().compareTo("loose") == 0) 1037 ret = 0 - ret; 1038 Poold.MON_LOG.log(Severity.DEBUG, "ret: " + ret); 1039 return (ret); 1040 } 1041 } 1042 /** 1043 * A resource set utilization based objective which will assess moves 1044 * in terms of their (likely) impact on the future performance of a 1045 * resource set with respect to it's specified utilization objective. 1046 * 1047 * The utilization objective must be specified in terms of a 1048 * KVOpExpression, see the class definition for information about the 1049 * form of these expressions. The objective can be examined in terms 1050 * of it's compliance with the aid of a monitoring object. The actual 1051 * assessment of compliance is indicated by the associated monitoring 1052 * object, with this class simply acting as a co-ordinator of the 1053 * relevant information. 1054 */ 1055 final class UtilizationObjective extends AbstractObjective 1056 implements WorkloadDependentObjective 1057 { 1058 /** 1059 * The name of the class. 1060 */ 1061 static final String name = "utilization"; 1062 1063 /** 1064 * Short run detection. 1065 */ 1066 private List zoneList = new LinkedList(); 1067 1068 /** 1069 * Format for printing utilization. 1070 */ 1071 private static final DecimalFormat uf = new DecimalFormat("0.00"); 1072 1073 /** 1074 * Solver used to calculate delta, i.e. gap, between target and 1075 * actual utilization values. 1076 */ 1077 private Solver gapSolver; 1078 1079 /** 1080 * Determine whether an objective is satisfied. If the 1081 * objective is still satisfied, return false; otherwise 1082 * return true. 1083 * 1084 * The assessment of control is made by the monitoring class 1085 * using the supplied Expression and resource. 1086 * 1087 * @param conf The configuration to be examined 1088 * @param solver The solving interface used to get utilization 1089 * information 1090 * @param elem The element to which the objective belongs 1091 * 1092 * @throws PoolsException if there is an error examining the 1093 * pool configuration 1094 * @throws StaleMonitorException if there is an error accessing 1095 * the element's ResourceMonitor 1096 */ examine(Configuration conf, Solver solver, Element elem)1097 public boolean examine(Configuration conf, Solver solver, 1098 Element elem) throws PoolsException, StaleMonitorException 1099 { 1100 KVOpExpression kve = (KVOpExpression) getExpression(); 1101 ResourceMonitor mon; 1102 1103 /* 1104 * If there is no resource monitor, then we cannot 1105 * make an assessment of the objective's achievability. 1106 * Log a message to make clear that this objective is 1107 * not being assessed and then indicate that 1108 * the objective has been achieved. 1109 */ 1110 try { 1111 mon = solver.getMonitor().get((Resource)elem); 1112 } catch (StaleMonitorException sme) { 1113 Poold.MON_LOG.log(Severity.INFO, 1114 elem.toString() + 1115 " utilization objective not measured " + 1116 toString() + " as there are no available " + 1117 "statistics."); 1118 return (false); 1119 } 1120 gapSolver = solver; 1121 1122 double val = solver.getMonitor().getUtilization((Resource)elem); 1123 1124 StatisticList sl = (StatisticList) mon.get("utilization"); 1125 int zone = sl.getZone(kve, val); 1126 1127 if (zoneList.size() == 9) { 1128 zoneList.remove(0); 1129 } 1130 zoneList.add(Integer.valueOf(sl.getZoneMean(val))); 1131 1132 /* 1133 * Evaluate whether or not this objective is under 1134 * control. 1135 */ 1136 if ((zone & StatisticOperations.ZONEZ) == 1137 StatisticOperations.ZONEZ) { 1138 /* 1139 * If the objective is GT or LT, then don't 1140 * return true as long as the objective is 1141 * satisfied. 1142 */ 1143 if (kve.getOp() == KVOpExpression.LT && 1144 (zone & StatisticOperations.ZONET) == 1145 StatisticOperations.ZONELT) 1146 return (false); 1147 1148 if (kve.getOp() == KVOpExpression.GT && 1149 (zone & StatisticOperations.ZONET) == 1150 StatisticOperations.ZONEGT) 1151 return (false); 1152 Poold.MON_LOG.log(Severity.INFO, 1153 elem.toString() + 1154 " utilization objective not satisfied " + 1155 toString() + " with utilization " + uf.format(val) + 1156 " (control zone bounds exceeded)"); 1157 return (true); 1158 } 1159 /* 1160 * Check if our statistics need to be recalculated. 1161 */ 1162 checkShort(mon, elem, val); 1163 return (false); 1164 } 1165 1166 /** 1167 * Calculates the value of a configuration in terms of this 1168 * objective. 1169 * 1170 * Every set must be classified with a control zone when this 1171 * function is called. The move can be assessed in terms of 1172 * the control violation type. zone violations which are minor 1173 * are offered a lower contribution than more significant 1174 * violations. 1175 * 1176 * @param conf Configuration to be scored. 1177 * @param move Move to be scored. 1178 * @param elem The element to which the objective applies 1179 * @throws Exception If an there is an error in execution. 1180 */ calculate(Configuration conf, Move move, Element elem)1181 public double calculate(Configuration conf, Move move, Element elem) 1182 throws PoolsException 1183 { 1184 KVOpExpression kve = (KVOpExpression) getExpression(); 1185 double ret; 1186 1187 /* 1188 * If the move is from the examined element, then 1189 * check to see if the recipient has any 1190 * objectives. If not, score the move poorly since we 1191 * should never want to transfer resources to a 1192 * recipient with no objectives. If there are 1193 * objectives, then return the delta between target 1194 * performance and actual performance for this 1195 * element. 1196 * 1197 * If the move is to the examined element, then check 1198 * to see if the donor has any objectives. If not, 1199 * score the move highly, since we want to favour 1200 * those resources with objectives. If there are 1201 * objectives, return the delta between actual and 1202 * target performance. 1203 * 1204 * If the element is neither the recipient or the 1205 * donor of this proposed move, then score the move 1206 * neutrally as 0. 1207 */ 1208 try { 1209 double val, gap; 1210 StatisticList sl; 1211 1212 if (elem.equals(move.getFrom())) { 1213 val = gapSolver.getMonitor(). 1214 getUtilization(move.getFrom()); 1215 sl = (StatisticList) gapSolver.getMonitor(). 1216 get(move.getFrom()).get("utilization"); 1217 gap = sl.getGap(kve, val) / 100; 1218 1219 if (gapSolver.getObjectives(move.getTo()) == 1220 null) { 1221 /* 1222 * Moving to a resource with 1223 * no objectives should always 1224 * be viewed unfavourably. The 1225 * degree of favourability is 1226 * thus bound between 0 and 1227 * -1. If the source gap is 1228 * negative, then subtract it 1229 * from -1 to get the 1230 * score. If positive, 1231 * just return -1. 1232 */ 1233 if (gap < 0) { 1234 ret = -1 - gap; 1235 } else { 1236 ret = -1; 1237 } 1238 } else { 1239 ret = 0 - gap; 1240 } 1241 } else if (elem.equals(move.getTo())) { 1242 val = gapSolver.getMonitor(). 1243 getUtilization(move.getTo()); 1244 sl = (StatisticList) gapSolver.getMonitor(). 1245 get(move.getTo()).get("utilization"); 1246 gap = sl.getGap(kve, val) / 100; 1247 1248 if (gapSolver.getObjectives(move.getFrom()) == 1249 null) { 1250 /* 1251 * Moving from a resource with 1252 * no objectives should always 1253 * be viewed favourably. The 1254 * degree of favourability is 1255 * thus bound between 0 and 1256 * 1. If the destination gap 1257 * is negative, then add to 1 1258 * to get the score. If 1259 * positive, just return 1. 1260 */ 1261 if (gap < 0) { 1262 ret = 0 - gap; 1263 } else { 1264 ret = 1; 1265 } 1266 } else { 1267 ret = 0 + gap; 1268 } 1269 } else { 1270 ret = 0; 1271 } 1272 } catch (StaleMonitorException sme) { 1273 /* 1274 * We should always find a monitor, 1275 * but if we can't then just assume 1276 * this is a neutral move and return 1277 * 0. 1278 */ 1279 ret = 0; 1280 } 1281 Poold.MON_LOG.log(Severity.DEBUG, "ret: " + ret); 1282 return (ret); 1283 } 1284 1285 /** 1286 * Check whether or not a set's statistics are still useful 1287 * for making decision.. 1288 * 1289 * Each set is controlled in terms of the zones of control 1290 * based in terms of standard deviations from a mean. If the 1291 * utilization of the set is not fluctuating normally around a 1292 * mean, these checks will cause the accumulated statistics to 1293 * be discarded and control suspended until a new sufficient 1294 * set of data is accumulated. 1295 * 1296 * @param mon Resource monitor to examine. 1297 * @param elem Element to which the resource monitor belongs. 1298 * @param val Latest monitored value. 1299 */ checkShort(ResourceMonitor mon, Element elem, double val)1300 private void checkShort(ResourceMonitor mon, Element elem, double val) 1301 { 1302 boolean checkOne = true; 1303 int checkOnePos = 0; 1304 boolean doCheckOne = false; 1305 1306 Iterator itZones = zoneList.iterator(); 1307 while (itZones.hasNext()) { 1308 int zone = ((Integer) itZones.next()).intValue(); 1309 if (doCheckOne) { 1310 if (checkOne) { 1311 if ((zone & StatisticOperations.ZONET) 1312 != checkOnePos) { 1313 checkOne = false; 1314 } 1315 } 1316 } else { 1317 if (zoneList.size() >= 9) { 1318 checkOnePos = zone & 1319 StatisticOperations.ZONET; 1320 doCheckOne = true; 1321 } 1322 } 1323 } 1324 if (zoneList.size() >= 9 && checkOne) { 1325 Poold.MON_LOG.log(Severity.INFO, 1326 elem.toString() + 1327 " utilization objective statistics reinitialized " + 1328 toString() + " with utilization " + uf.format(val) + 1329 " (nine points on same side of mean)"); 1330 mon.resetData("utilization"); 1331 zoneList.clear(); 1332 } 1333 } 1334 } 1335