| 1 | package de.uka.ipd.sdq.scheduler.loaddistribution.balancers; |
| 2 | |
| 3 | import java.util.ArrayList; |
| 4 | import java.util.Collection; |
| 5 | import java.util.Hashtable; |
| 6 | import java.util.Iterator; |
| 7 | import java.util.List; |
| 8 | |
| 9 | import de.uka.ipd.sdq.probfunction.math.util.MathTools; |
| 10 | import de.uka.ipd.sdq.scheduler.loaddistribution.ILoadBalancer; |
| 11 | import de.uka.ipd.sdq.scheduler.processes.IActiveProcess; |
| 12 | import de.uka.ipd.sdq.scheduler.queueing.strategies.MultipleQueuesStrategy; |
| 13 | import de.uka.ipd.sdq.scheduler.resources.IResourceInstance; |
| 14 | |
| 15 | public abstract class OriginalAbstractLoadBalancer implements ILoadBalancer { |
| 16 | |
| 17 | /** |
| 18 | * Minimum time that needs to pass between two load balancing attempts |
| 19 | */ |
| 20 | protected double balance_interval; |
| 21 | |
| 22 | /** |
| 23 | * If !do_global_balance, this table is used to track the time that passed |
| 24 | * since the last execution of a load balancer for an instance. |
| 25 | */ |
| 26 | protected Hashtable<IResourceInstance, Double> last_load; |
| 27 | |
| 28 | /** |
| 29 | * Holder of the runqueues that need to be balanced. |
| 30 | */ |
| 31 | protected MultipleQueuesStrategy queue_holder; |
| 32 | |
| 33 | /** |
| 34 | * Determines the order how movable processes are returned. If true, the |
| 35 | * priority of the processes is increasing, otherwise decreasing. |
| 36 | */ |
| 37 | protected boolean prio_increasing; |
| 38 | |
| 39 | /** |
| 40 | * Determines the order how movable processes are returned. If true, the |
| 41 | * first processes are returned in the same order of the queue, otherwise |
| 42 | * they are returned in reverse order. |
| 43 | */ |
| 44 | protected boolean queue_ascending; |
| 45 | |
| 46 | /** |
| 47 | * Creates a new instance of a load balancer. |
| 48 | * |
| 49 | * @param balance_interval |
| 50 | * Minimum time that needs to pass between two executions of the |
| 51 | * load balancer. |
| 52 | * |
| 53 | * @param do_global_balance |
| 54 | * Indicates whether all instances should be balanced or only the |
| 55 | * specified and busiest one. |
| 56 | * |
| 57 | * @param prio_increasing |
| 58 | * Determines the order how movable processes are returned. If |
| 59 | * true, the priority of the processes is increasing, otherwise |
| 60 | * decreasing. |
| 61 | * |
| 62 | * @param queue_ascending |
| 63 | * Determines the order how movable processes are returned. If |
| 64 | * true, the first processes are returned in the same order of |
| 65 | * the queue, otherwise they are returned in reverse order. |
| 66 | * |
| 67 | * @param max_iterations |
| 68 | * Gives the maximum number of iterations for a global balancing. |
| 69 | */ |
| 70 | protected OriginalAbstractLoadBalancer(double balance_interval, |
| 71 | boolean do_global_balance, boolean prio_increasing, |
| 72 | boolean queue_ascending, int max_iterations) { |
| 73 | super(); |
| 74 | this.balance_interval = balance_interval; |
| 75 | this.prio_increasing = prio_increasing; |
| 76 | this.queue_ascending = queue_ascending; |
| 77 | this.queue_holder = null; |
| 78 | this.last_load = new Hashtable<IResourceInstance, Double>(); |
| 79 | } |
| 80 | |
| 81 | public void setQueueHolder(MultipleQueuesStrategy queue_holder) { |
| 82 | this.queue_holder = queue_holder; |
| 83 | for (IResourceInstance instance : queue_holder.getResourceInstances()) { |
| 84 | this.last_load.put(instance, 0.0); |
| 85 | } |
| 86 | } |
| 87 | |
| 88 | /** |
| 89 | * Template Method. Checks if both queues are balanced with respect to a |
| 90 | * given criteria. |
| 91 | * |
| 92 | * @param busyQueue |
| 93 | * @param idleQueue |
| 94 | * @return |
| 95 | */ |
| 96 | protected abstract boolean isBalanced(IResourceInstance firstInstance, |
| 97 | IResourceInstance secondInstance); |
| 98 | |
| 99 | public void activelyBalance(IResourceInstance instance) { |
| 100 | double load = queue_holder.getRunQueueFor(instance).getCurrentLoad(); |
| 101 | if (MathTools.less(0, Math.abs(load - last_load.get(instance)))) { |
| 102 | doBalance(instance); |
| 103 | } |
| 104 | last_load.put(instance, load); |
| 105 | } |
| 106 | |
| 107 | /** |
| 108 | * Moves processes from the src instance to the dest instance until both are |
| 109 | * balanced. |
| 110 | * |
| 111 | * @param src |
| 112 | * source instance of the processes moved |
| 113 | * @param dest |
| 114 | * destination instance of the processes moved |
| 115 | */ |
| 116 | protected void balanceTwoInstances(IResourceInstance src, |
| 117 | IResourceInstance dest, int max_processes_needed) { |
| 118 | List<IActiveProcess> movable_process_list = identifyMovableProcesses( |
| 119 | src, dest, max_processes_needed); |
| 120 | Iterator<IActiveProcess> iterator = movable_process_list.iterator(); |
| 121 | |
| 122 | while (iterator.hasNext() && load(src) > 1 && !isBalanced(src, dest)) { |
| 123 | queue_holder.move(iterator.next(), src, dest); |
| 124 | } |
| 125 | |
| 126 | src.schedulingInterrupt(0); |
| 127 | dest.schedulingInterrupt(0); |
| 128 | } |
| 129 | |
| 130 | /** |
| 131 | * Returns an ordered list of movable processes. The processes are ordered |
| 132 | * with respect to their "movability". |
| 133 | * |
| 134 | * @return Ordered list of movable processes. |
| 135 | */ |
| 136 | protected List<IActiveProcess> identifyMovableProcesses( |
| 137 | IResourceInstance source_instance, |
| 138 | IResourceInstance target_instance, int processes_needed) { |
| 139 | return queue_holder.getRunQueueFor(source_instance) |
| 140 | .identifyMovableProcesses(target_instance, prio_increasing, |
| 141 | queue_ascending, processes_needed); |
| 142 | } |
| 143 | |
| 144 | /** |
| 145 | * Returns the load of the given instance. |
| 146 | * |
| 147 | * @param instance |
| 148 | * @return |
| 149 | */ |
| 150 | protected int load(IResourceInstance instance) { |
| 151 | int queueLength = queue_holder.getRunQueueFor(instance).getCurrentLoad(); |
| 152 | if(instance.getRunningProcess() != null){ |
| 153 | queueLength ++; |
| 154 | } |
| 155 | return queueLength; |
| 156 | } |
| 157 | |
| 158 | /** |
| 159 | * Returns the busiest queue in the given list. |
| 160 | * |
| 161 | * @param runQueues |
| 162 | * @return |
| 163 | */ |
| 164 | protected IResourceInstance getBusiest( |
| 165 | Collection<IResourceInstance> instance_list) { |
| 166 | IResourceInstance busiest = null; |
| 167 | for (IResourceInstance instance : instance_list) { |
| 168 | if (busiest == null || load(instance) > load(busiest)) |
| 169 | busiest = instance; |
| 170 | } |
| 171 | return busiest; |
| 172 | } |
| 173 | |
| 174 | /** |
| 175 | * Returns the idlest queue in the given list. |
| 176 | * |
| 177 | * @param runQueues |
| 178 | * @return |
| 179 | */ |
| 180 | protected IResourceInstance getLaziest( |
| 181 | Collection<IResourceInstance> instance_list) { |
| 182 | IResourceInstance laziest = null; |
| 183 | for (IResourceInstance instance : instance_list) { |
| 184 | if (laziest == null || load(instance) < load(laziest)) |
| 185 | laziest = instance; |
| 186 | } |
| 187 | return laziest; |
| 188 | } |
| 189 | |
| 190 | /** |
| 191 | * Returns all queues with more than one job. |
| 192 | * |
| 193 | * @param runQueueCollection |
| 194 | * @return |
| 195 | */ |
| 196 | protected List<IResourceInstance> getInstancesWithMoreThanOneProcess() { |
| 197 | List<IResourceInstance> busyQueues = new ArrayList<IResourceInstance>(); |
| 198 | for (IResourceInstance instance : queue_holder.getResourceInstances()) { |
| 199 | if (load(instance) > 1) |
| 200 | busyQueues.add(instance); |
| 201 | } |
| 202 | return busyQueues; |
| 203 | } |
| 204 | |
| 205 | /** |
| 206 | * Returns the maximum number of processes needed to balance both queues. |
| 207 | * |
| 208 | * @param first_instance |
| 209 | * @param second_instance |
| 210 | * @return |
| 211 | */ |
| 212 | protected int numProcessedNeeded(IResourceInstance first_instance, |
| 213 | IResourceInstance second_instance) { |
| 214 | int firstLoad = load(first_instance); |
| 215 | int secondLoad = load(second_instance); |
| 216 | return Math.abs(firstLoad - secondLoad) / 2; |
| 217 | } |
| 218 | |
| 219 | /** |
| 220 | * Balances the queue of the given instance and the queue of the busiest |
| 221 | * instance. |
| 222 | * |
| 223 | * @param instance |
| 224 | */ |
| 225 | protected void doBalance(IResourceInstance instance) { |
| 226 | IResourceInstance busiest = getBusiest(queue_holder |
| 227 | .getResourceInstances()); |
| 228 | IResourceInstance idlest = getLaziest(queue_holder |
| 229 | .getResourceInstances()); |
| 230 | if (!busiest.equals(instance) && !isBalanced(busiest, instance) |
| 231 | && load(busiest) > 1) { |
| 232 | int max_processes_needed = numProcessedNeeded(busiest, instance); |
| 233 | balanceTwoInstances(busiest, instance, max_processes_needed); |
| 234 | } else if (!idlest.equals(instance) && !isBalanced(idlest, instance) |
| 235 | && load(instance) > 1) { |
| 236 | int max_processes_needed = numProcessedNeeded(instance, idlest); |
| 237 | balanceTwoInstances(instance, idlest, max_processes_needed); |
| 238 | } |
| 239 | } |
| 240 | } |