| 1 | package de.uka.ipd.sdq.reliability.solver.pcm2markov; |
| 2 | |
| 3 | import java.util.ArrayList; |
| 4 | import java.util.List; |
| 5 | |
| 6 | import org.apache.log4j.Logger; |
| 7 | import org.eclipse.emf.common.util.EList; |
| 8 | |
| 9 | import de.uka.ipd.sdq.markov.MarkovChain; |
| 10 | import de.uka.ipd.sdq.markov.State; |
| 11 | import de.uka.ipd.sdq.markov.StateType; |
| 12 | import de.uka.ipd.sdq.pcm.seff.ResourceDemandingSEFF; |
| 13 | import de.uka.ipd.sdq.pcm.seff.ServiceEffectSpecification; |
| 14 | import de.uka.ipd.sdq.pcm.usagemodel.AbstractUserAction; |
| 15 | import de.uka.ipd.sdq.pcm.usagemodel.Branch; |
| 16 | import de.uka.ipd.sdq.pcm.usagemodel.BranchTransition; |
| 17 | import de.uka.ipd.sdq.pcm.usagemodel.Delay; |
| 18 | import de.uka.ipd.sdq.pcm.usagemodel.EntryLevelSystemCall; |
| 19 | import de.uka.ipd.sdq.pcm.usagemodel.Loop; |
| 20 | import de.uka.ipd.sdq.pcm.usagemodel.ScenarioBehaviour; |
| 21 | import de.uka.ipd.sdq.pcm.usagemodel.Start; |
| 22 | import de.uka.ipd.sdq.pcm.usagemodel.Stop; |
| 23 | import de.uka.ipd.sdq.pcm.usagemodel.util.UsagemodelSwitch; |
| 24 | import de.uka.ipd.sdq.pcmsolver.transformations.ContextWrapper; |
| 25 | import de.uka.ipd.sdq.pcmsolver.visitors.EMFQueryHelper; |
| 26 | import de.uka.ipd.sdq.probfunction.math.ManagedPMF; |
| 27 | import de.uka.ipd.sdq.reliability.core.MarkovEvaluationType; |
| 28 | |
| 29 | /** |
| 30 | * This class represents a visitor for a UsageModel within a PCM instance. The |
| 31 | * visitor is used in the transformation from PCM with solved dependencies into |
| 32 | * a Markov Chain Model for reliability prediction. |
| 33 | * |
| 34 | * @author brosch |
| 35 | * |
| 36 | */ |
| 37 | public class MarkovUsageModelVisitor extends UsagemodelSwitch<MarkovChain> { |
| 38 | |
| 39 | /** |
| 40 | * A logger to give detailed information about the PCM instance traversal. |
| 41 | */ |
| 42 | private static Logger logger = Logger |
| 43 | .getLogger(MarkovUsageModelVisitor.class.getName()); |
| 44 | |
| 45 | /** |
| 46 | * The ContextWrapper provides easy access to the decorations of the solved |
| 47 | * PCM instance. |
| 48 | */ |
| 49 | private ContextWrapper contextWrapper = null; |
| 50 | |
| 51 | /** |
| 52 | * The degree of distinction between failure types. |
| 53 | */ |
| 54 | private MarkovEvaluationType evaluationType; |
| 55 | |
| 56 | /** |
| 57 | * The Markov Builder is used to create Markov Chain instances. |
| 58 | */ |
| 59 | private MarkovBuilder markovBuilder; |
| 60 | |
| 61 | /** |
| 62 | * Indicates if the Markov Chain reduction is performed during the |
| 63 | * transformation. If so, then the chain as a whole never exists, because |
| 64 | * during construction, it is already reduced again. |
| 65 | */ |
| 66 | private boolean optimize; |
| 67 | |
| 68 | /** |
| 69 | * The prefix list enables unique naming of all Markov states, which in turn |
| 70 | * allows to search for differences between two chains. |
| 71 | */ |
| 72 | private List<String> prefixes; |
| 73 | |
| 74 | /** |
| 75 | * Indicates if the resulting Makov model shall be augmented with tracing |
| 76 | * information for diagnostic purposes. |
| 77 | */ |
| 78 | private boolean recordTraces; |
| 79 | |
| 80 | /** |
| 81 | * Indicates if resource states are handled according to the simpler |
| 82 | * "always ask" strategy, which may yield less accurate results, but avoids |
| 83 | * iterating over all possible state combinations. |
| 84 | */ |
| 85 | private boolean simplifiedStateHandling; |
| 86 | |
| 87 | /** |
| 88 | * The solved PCM instance that serves as an input for the transformation. |
| 89 | */ |
| 90 | private MarkovTransformationSource transformationState; |
| 91 | |
| 92 | /** |
| 93 | * The constructor. |
| 94 | * |
| 95 | * @param transformationState |
| 96 | * the Markov transformation state |
| 97 | * @param evaluationType |
| 98 | * the degree of differentiation between failure types |
| 99 | * @param simplifiedStateHandling |
| 100 | * controls the handling of physical resource states |
| 101 | * @param optimize |
| 102 | * controls if Markov Chain reduction shall be performed during |
| 103 | * transformation |
| 104 | * @param recordTraces |
| 105 | * controls if traces shall be recorded during transformation |
| 106 | */ |
| 107 | public MarkovUsageModelVisitor( |
| 108 | final MarkovTransformationSource transformationState, |
| 109 | final MarkovEvaluationType evaluationType, |
| 110 | final boolean simplifiedStateHandling, final boolean optimize, |
| 111 | final boolean recordTraces) { |
| 112 | this.evaluationType = evaluationType; |
| 113 | this.transformationState = transformationState; |
| 114 | this.simplifiedStateHandling = simplifiedStateHandling; |
| 115 | this.optimize = optimize; |
| 116 | this.recordTraces = recordTraces; |
| 117 | this.prefixes = new ArrayList<String>(); |
| 118 | this.markovBuilder = new MarkovBuilder(recordTraces); |
| 119 | } |
| 120 | |
| 121 | /** |
| 122 | * Returns a Markov Chain corresponding to this Branch. |
| 123 | * |
| 124 | * @param branch |
| 125 | * the branch action |
| 126 | * @return the resulting Markov Chain |
| 127 | * @see de.uka.ipd.sdq.pcm.usagemodel.util.UsagemodelSwitch#caseBranch(de.uka.ipd.sdq.pcm.usagemodel.Branch) |
| 128 | */ |
| 129 | @Override |
| 130 | public MarkovChain caseBranch(Branch branch) { |
| 131 | |
| 132 | // Logging & naming: |
| 133 | String name = branch.getEntityName() + "[" + branch.getId() + "]"; |
| 134 | prefixes.add(name); |
| 135 | logger.debug("Visit Branch: " + name); |
| 136 | |
| 137 | // Determine the branch probabilities and the inner Markov chains |
| 138 | // associated with the branch behaviors: |
| 139 | ArrayList<MarkovChain> specificMarkovChains = new ArrayList<MarkovChain>(); |
| 140 | ArrayList<Double> branchProbabilities = new ArrayList<Double>(); |
| 141 | EList<BranchTransition> transitions = branch |
| 142 | .getBranchTransitions_Branch(); |
| 143 | for (int i = 0; i < transitions.size(); i++) { |
| 144 | if (transitions.get(i).getBranchProbability() <= 0.0) { |
| 145 | continue; |
| 146 | } |
| 147 | branchProbabilities.add(transitions.get(i).getBranchProbability()); |
| 148 | specificMarkovChains.add((MarkovChain) doSwitch(transitions.get(i) |
| 149 | .getBranchedBehaviour_BranchTransition())); |
| 150 | } |
| 151 | |
| 152 | // Initialize the aggregate Markov chain representing the branch: |
| 153 | MarkovChain aggregateMarkovChain = markovBuilder.initBranchMarkovChain( |
| 154 | prefixes, branchProbabilities); |
| 155 | |
| 156 | // Incorporate the specific Markov chains into the aggregate one: |
| 157 | ArrayList<State> statesToReplace = new ArrayList<State>(); |
| 158 | for (int i = 0; i < aggregateMarkovChain.getStates().size(); i++) { |
| 159 | if (aggregateMarkovChain.getStates().get(i).getType().equals( |
| 160 | StateType.DEFAULT)) { |
| 161 | statesToReplace.add(aggregateMarkovChain.getStates().get(i)); |
| 162 | } |
| 163 | } |
| 164 | for (int i = 0; i < statesToReplace.size(); i++) { |
| 165 | markovBuilder.incorporateMarkovChain(aggregateMarkovChain, |
| 166 | specificMarkovChains.get(i), statesToReplace.get(i), |
| 167 | optimize, false); |
| 168 | } |
| 169 | |
| 170 | // Naming: |
| 171 | prefixes.remove(prefixes.size() - 1); |
| 172 | |
| 173 | // Return the result: |
| 174 | return aggregateMarkovChain; |
| 175 | } |
| 176 | |
| 177 | /** |
| 178 | * Returns a Markov Chain correponding to this Delay. |
| 179 | * |
| 180 | * @param delay |
| 181 | * the delay action |
| 182 | * @return the resulting Markov Chain |
| 183 | */ |
| 184 | @Override |
| 185 | public MarkovChain caseDelay(final Delay delay) { |
| 186 | |
| 187 | // Do the logging: |
| 188 | String name = delay.getEntityName() + "[" + delay.getId() + "]"; |
| 189 | prefixes.add(name); |
| 190 | logger.debug("Visit Delay: " + name); |
| 191 | |
| 192 | // Create a Markov chain for the Delay action: |
| 193 | MarkovChain resultChain = markovBuilder.initBasicMarkovChain(prefixes); |
| 194 | |
| 195 | // Naming: |
| 196 | prefixes.remove(prefixes.size() - 1); |
| 197 | |
| 198 | // Return the result: |
| 199 | return resultChain; |
| 200 | } |
| 201 | |
| 202 | /** |
| 203 | * |
| 204 | * Returns a Markov Chain that corresponds to this EntryLevelSystemCall. |
| 205 | * |
| 206 | * @param call |
| 207 | * the call |
| 208 | * @return the resulting Markov Chain |
| 209 | */ |
| 210 | @Override |
| 211 | public MarkovChain caseEntryLevelSystemCall(final EntryLevelSystemCall call) { |
| 212 | |
| 213 | // Logging & naming: |
| 214 | String name = call.getEntityName() + "[" + call.getId() + "]"; |
| 215 | prefixes.add(name); |
| 216 | logger.debug("Visit EntryLevelSystemCall: " + name); |
| 217 | |
| 218 | // Get List of ContextWrappers, one for each called component instance |
| 219 | List<ContextWrapper> contextWrapperList; |
| 220 | // Create a new context wrapper for this entry level system call: |
| 221 | if (contextWrapper == null) { |
| 222 | contextWrapperList = ContextWrapper.getContextWrapperFor(call, |
| 223 | transformationState.getModel()); |
| 224 | } else { |
| 225 | contextWrapperList = contextWrapper.getContextWrapperFor(call); |
| 226 | } |
| 227 | |
| 228 | // FIXME: The Reliability solver does not support replication yet |
| 229 | if (contextWrapperList.size() > 1) { |
| 230 | logger |
| 231 | .error("The Reliability solver only supports one AllocationContext per AssemblyContext. Picking one of the called Allocation contexts for call " |
| 232 | + call.getEntityName() |
| 233 | + " " |
| 234 | + call.getId() |
| 235 | + " ignoring the others. Results will be inaccurate."); |
| 236 | } else if (contextWrapperList.size() == 0) { |
| 237 | throw new RuntimeException( |
| 238 | "Internal Error: Could not create a Context Wrapper for call " |
| 239 | + call.getEntityName() + " " + call.getId()); |
| 240 | } |
| 241 | contextWrapper = contextWrapperList.get(0); |
| 242 | |
| 243 | // We need to get from the entryLevelSystemCall to the RDSEFF that |
| 244 | // fulfills the call: |
| 245 | ServiceEffectSpecification seff = contextWrapper.getNextSEFF(call); |
| 246 | MarkovChain resultChain = null; |
| 247 | if (seff != null) { |
| 248 | MarkovSeffVisitor seffVisitor = new MarkovSeffVisitor( |
| 249 | transformationState, contextWrapper, prefixes, |
| 250 | evaluationType, simplifiedStateHandling, optimize, |
| 251 | recordTraces); |
| 252 | resultChain = seffVisitor.doSwitch((ResourceDemandingSEFF) seff); |
| 253 | } |
| 254 | |
| 255 | // Naming: |
| 256 | prefixes.remove(prefixes.size() - 1); |
| 257 | |
| 258 | // Return the result: |
| 259 | return resultChain; |
| 260 | } |
| 261 | |
| 262 | /** |
| 263 | * Returns a Markov Chain corresponding to this Loop. |
| 264 | * |
| 265 | * @param loop |
| 266 | * the loop action |
| 267 | * @return the resulting Markov Chain |
| 268 | */ |
| 269 | @Override |
| 270 | public MarkovChain caseLoop(final Loop loop) { |
| 271 | |
| 272 | // Logging & naming: |
| 273 | String name = loop.getEntityName() + "[" + loop.getId() + "]"; |
| 274 | prefixes.add(name); |
| 275 | logger.debug("Visit Loop: " + name); |
| 276 | |
| 277 | // Get the solved loop probability mass function: |
| 278 | String specification = loop.getLoopIteration_Loop().getSpecification(); |
| 279 | ManagedPMF pmf; |
| 280 | try { |
| 281 | pmf = ManagedPMF.createFromString(specification); |
| 282 | } catch (Exception e) { |
| 283 | logger.error("Could not create a ManagedPMF from string \"" |
| 284 | + specification + "\""); |
| 285 | return null; |
| 286 | } |
| 287 | |
| 288 | // Determine the inner Markov Chain associated with the loop behavior: |
| 289 | ArrayList<String> prefixesCopy = new ArrayList<String>(); |
| 290 | prefixesCopy.addAll(prefixes); |
| 291 | prefixes.clear(); |
| 292 | MarkovChain specificMarkovChain = (MarkovChain) doSwitch(loop |
| 293 | .getBodyBehaviour_Loop()); |
| 294 | prefixes.addAll(prefixesCopy); |
| 295 | |
| 296 | // Initialize the aggregate Markov Chain representing the loop: |
| 297 | MarkovChain aggregateMarkovChain = markovBuilder.initLoopMarkovChain( |
| 298 | prefixes, pmf); |
| 299 | |
| 300 | // Incorporate the specific MarkovChain into the aggregate one: |
| 301 | ArrayList<State> statesToReplace = new ArrayList<State>(); |
| 302 | for (int i = 0; i < aggregateMarkovChain.getStates().size(); i++) { |
| 303 | if (aggregateMarkovChain.getStates().get(i).getType().equals( |
| 304 | StateType.DEFAULT)) { |
| 305 | statesToReplace.add(aggregateMarkovChain.getStates().get(i)); |
| 306 | } |
| 307 | } |
| 308 | for (int i = 0; i < statesToReplace.size(); i++) { |
| 309 | markovBuilder |
| 310 | .incorporateMarkovChain(aggregateMarkovChain, |
| 311 | specificMarkovChain, statesToReplace.get(i), |
| 312 | optimize, true); |
| 313 | } |
| 314 | |
| 315 | // Naming: |
| 316 | prefixes.remove(prefixes.size() - 1); |
| 317 | |
| 318 | // Return the result: |
| 319 | return aggregateMarkovChain; |
| 320 | } |
| 321 | |
| 322 | /** |
| 323 | * Returns a Markov Chain that corresponds to the first SystemLevelEntryCall |
| 324 | * within this ScenarioBehaviour. |
| 325 | * |
| 326 | * @param scenarioBehaviour |
| 327 | * the scenario behaviour |
| 328 | * @return the resulting Markov Chain |
| 329 | */ |
| 330 | @Override |
| 331 | public MarkovChain caseScenarioBehaviour( |
| 332 | final ScenarioBehaviour scenarioBehaviour) { |
| 333 | |
| 334 | // Logging & naming: |
| 335 | String name = scenarioBehaviour.getEntityName() + "[" |
| 336 | + scenarioBehaviour.getId() + "]"; |
| 337 | prefixes.add(name); |
| 338 | logger.debug("Visit Scenario Behaviour: " + name); |
| 339 | |
| 340 | // Go through the chain of actions that constitute this behavior. Each |
| 341 | // action is expected to create its own specific Markov Chain: |
| 342 | ArrayList<AbstractUserAction> actions = new ArrayList<AbstractUserAction>(); |
| 343 | ArrayList<String> actionNames = new ArrayList<String>(); |
| 344 | ArrayList<MarkovChain> chains = new ArrayList<MarkovChain>(); |
| 345 | AbstractUserAction action = (Start) EMFQueryHelper.getObjectByType( |
| 346 | scenarioBehaviour.getActions_ScenarioBehaviour(), Start.class); |
| 347 | while (action != null) { |
| 348 | actions.add(action); |
| 349 | actionNames |
| 350 | .add(action.getEntityName() + "[" + action.getId() + "]"); |
| 351 | MarkovChain specificMarkovChain = (MarkovChain) doSwitch(action); |
| 352 | chains.add(specificMarkovChain); |
| 353 | action = action.getSuccessor(); |
| 354 | } |
| 355 | |
| 356 | // Initialize a new aggregate Markov Chain that has one state for each |
| 357 | // action of the action chain: |
| 358 | ArrayList<State> states = new ArrayList<State>(); |
| 359 | MarkovChain aggregateMarkovChain = markovBuilder |
| 360 | .initSequentialMarkovChain(prefixes, actionNames, states); |
| 361 | |
| 362 | // Incorporate the specific Chains into the aggregate Chain: |
| 363 | for (int i = 0; i < actions.size(); i++) { |
| 364 | markovBuilder.incorporateMarkovChain(aggregateMarkovChain, chains |
| 365 | .get(i), states.get(i), optimize, false); |
| 366 | } |
| 367 | |
| 368 | // Naming: |
| 369 | prefixes.remove(prefixes.size() - 1); |
| 370 | |
| 371 | // Return the resulting Markov Chain: |
| 372 | return aggregateMarkovChain; |
| 373 | } |
| 374 | |
| 375 | /** |
| 376 | * Returns a Markov Chain that corresponds to this start action. |
| 377 | * |
| 378 | * @param start |
| 379 | * the start action |
| 380 | * @return the resulting Markov Chain |
| 381 | */ |
| 382 | @Override |
| 383 | public MarkovChain caseStart(final Start start) { |
| 384 | |
| 385 | // Do the logging: |
| 386 | String name = start.getEntityName() + "[" + start.getId() + "]"; |
| 387 | prefixes.add(name); |
| 388 | logger.debug("Visit Start: " + name); |
| 389 | |
| 390 | // Create a Markov Chain for the Start action: |
| 391 | MarkovChain resultChain = markovBuilder.initBasicMarkovChain(prefixes); |
| 392 | |
| 393 | // Naming: |
| 394 | prefixes.remove(prefixes.size() - 1); |
| 395 | |
| 396 | // Return the result: |
| 397 | return resultChain; |
| 398 | } |
| 399 | |
| 400 | /** |
| 401 | * Returns a Markov Chain that corresponds to this stop action. |
| 402 | * |
| 403 | * @param stop |
| 404 | * the stop action |
| 405 | * @return the resulting Markov Chain |
| 406 | */ |
| 407 | @Override |
| 408 | public MarkovChain caseStop(final Stop stop) { |
| 409 | |
| 410 | // Logging & Naming: |
| 411 | String name = stop.getEntityName() + "[" + stop.getId() + "]"; |
| 412 | logger.debug("Visit Stop: " + name); |
| 413 | prefixes.add(name); |
| 414 | |
| 415 | // Create a Markov chain for the Stop action: |
| 416 | MarkovChain resultChain = markovBuilder.initBasicMarkovChain(prefixes); |
| 417 | |
| 418 | // Naming: |
| 419 | prefixes.remove(prefixes.size() - 1); |
| 420 | |
| 421 | // Return the result: |
| 422 | return resultChain; |
| 423 | } |
| 424 | } |