src/main/gov/nasa/jpf/search/heuristic/Interleaving.java

   1 /*
   2  * Copyright (C) 2014, United States Government, as represented by the
   3  * Administrator of the National Aeronautics and Space Administration.
   4  * All rights reserved.
   5  *
   6  * The Java Pathfinder core (jpf-core) platform is licensed under the
   7  * Apache License, Version 2.0 (the "License"); you may not use this file except
   8  * in compliance with the License. You may obtain a copy of the License at
   9  *
  10  *        http://www.apache.org/licenses/LICENSE-2.0.
  11  *
  12  * Unless required by applicable law or agreed to in writing, software
  13  * distributed under the License is distributed on an "AS IS" BASIS,
  14  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  15  * See the License for the specific language governing permissions and
  16  * limitations under the License.
  17  */
  18 package gov.nasa.jpf.search.heuristic;
  19
  20 import gov.nasa.jpf.Config;
  21 import gov.nasa.jpf.vm.VM;
  22 import gov.nasa.jpf.vm.Path;
  23
  24
  25 /**
  26  * Heuristic to maximize thread interleavings. It is particularly good at
  27  * flushing out concurrency errors, since it schedules different threads
  28  * as much as possible.
  29  *
  30  */
  31 public class Interleaving extends SimplePriorityHeuristic {
  32
  33   int historyLimit;
  34
  35   public Interleaving (Config config, VM vm) {
  36     super(config,vm);
  37
  38     historyLimit = config.getInt("search.heuristic.thread_history_limit", -1);
  39   }
  40
  41   /*
  42    * heuristic based on how often, how long ago, and within how many
  43    * live threads a certain thread did run
  44    */
  45   @Override
  46   protected int computeHeuristicValue () {
  47     int aliveThreads = vm.getThreadList().getMatchingCount(aliveThread);
  48
  49     Path path = vm.getPath();
  50     int  pathSize = path.size();
  51
  52     int tid = vm.getCurrentThread().getId();
  53     int h_value = 0;
  54
  55     if (aliveThreads > 1) { // otherwise there's nothing to interleave
  56
  57       for (int i= Math.max(0, pathSize - historyLimit); i<pathSize; i++) {
  58         if (path.get(i).getThreadIndex() == tid) {
  59           h_value += (pathSize - i) * aliveThreads;
  60         }
  61       }
  62     }
  63
  64     return h_value;
  65   }
  66 }