KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > gov > nasa > jpf > search > heuristic > Interleaving


1 //
2 // Copyright (C) 2005 United States Government as represented by the
3 // Administrator of the National Aeronautics and Space Administration
4 // (NASA). All Rights Reserved.
5 //
6 // This software is distributed under the NASA Open Source Agreement
7 // (NOSA), version 1.3. The NOSA has been approved by the Open Source
8 // Initiative. See the file NOSA-1.3-JPF at the top of the distribution
9 // directory tree for the complete NOSA document.
10 //
11 // THE SUBJECT SOFTWARE IS PROVIDED "AS IS" WITHOUT ANY WARRANTY OF ANY
12 // KIND, EITHER EXPRESSED, IMPLIED, OR STATUTORY, INCLUDING, BUT NOT
13 // LIMITED TO, ANY WARRANTY THAT THE SUBJECT SOFTWARE WILL CONFORM TO
14 // SPECIFICATIONS, ANY IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR
15 // A PARTICULAR PURPOSE, OR FREEDOM FROM INFRINGEMENT, ANY WARRANTY THAT
16 // THE SUBJECT SOFTWARE WILL BE ERROR FREE, OR ANY WARRANTY THAT
17 // DOCUMENTATION, IF PROVIDED, WILL CONFORM TO THE SUBJECT SOFTWARE.
18 //
19 package gov.nasa.jpf.search.heuristic;
20
21 import gov.nasa.jpf.Config;
22 import gov.nasa.jpf.VM;
23 import gov.nasa.jpf.jvm.TrailInfo;
24
25
26 /**
27  * Heuristic to maximize thread interleavings. It is particularly good at
28  * flushing out concurrency errors, since it schedules different threads
29  * as much as possible.
30  *
31  */
32 public class Interleaving implements Heuristic {
33   private int[] threads;
34   HeuristicSearch search;
35   VM vm;
36   int threadHistoryLimit;
37
38   public Interleaving (Config config, HeuristicSearch hSearch) {
39     vm = hSearch.getVM();
40     search = hSearch;
41     
42     threadHistoryLimit = config.getInt("search.heuristic.thread_history_limit", -1);
43   }
44
45   public int heuristicValue () {
46     int aliveThreads = vm.getAliveThreadCount();
47
48     int lastRun = ((TrailInfo) vm.getLastTransition()).getThread();
49     int h_value = 0;
50
51     if (aliveThreads > 1) {
52       for (int i = 0; i < threads.length; i++) {
53         if (lastRun == threads[i]) {
54           h_value += ((threads.length - i) * aliveThreads);
55         }
56       }
57     }
58
59     int newSize = threads.length + 1;
60
61     if ((threadHistoryLimit > 0) &&
62             (newSize > threadHistoryLimit)) {
63       newSize = threadHistoryLimit;
64     }
65
66     int[] newThreads = new int[newSize];
67     newThreads[0] = lastRun;
68
69     for (int i = 1; i < newSize; i++) {
70       newThreads[i] = threads[i - 1];
71     }
72
73     search.getNew().otherData = newThreads;
74
75     return h_value;
76   }
77
78   public void processParent () {
79     Object JavaDoc oldValue = search.getOld().otherData;
80
81     if (oldValue == null) {
82       threads = new int[0];
83     } else {
84       threads = (int[]) oldValue;
85     }
86   }
87 }
88
Popular Tags