Revision f8c033b6
Added some code to askHeuristic function
src/sim/cheuristic.cc  

20  20 
**/ 
21  21 
#include <string.h> 
22  22  
23 
#include "cmessage.h" 

23  24 
#include "cheuristic.h" 
24  25  
25 
bool cHeuristic::askHeuristic() 

26 
// TODO: 

27  
28 
// cNode 

29 
// cNode::cNode 

30 
// cNode::getProbability() 

31 
// cNode::getSuccessors() 

32 
// cNode::getProbabilityDistribution() 

33  
34 
// eventSet_t 

35 
// eventSet_t::begin() 

36 
// eventSet_t::end() 

37 
// eventSet_t::iterator 

38 
// eventSet_t::iterator::++operator 

39 
// eventSet_t::iterator::operator!=(eventSet_t::iterator) 

40 
// eventSet_t::iterator::operator= 

41  
42 
// evType_t 

43  
44 
// abstractEvent_t 

45 
// abstractEvent_t eventSet_t::iterator::operator> 

46 
// evType_t abstractEvent_t::getEvType() 

47 
// int abstractEvent_t::getEvModId() 

48 
// pdf_t abstractEvent_t::getProbabilityDistribution() 

49  
50 
// pdf_t 

51 
// pdf_t::pdf_t(simtime_t) 

52 
// pdf_t::operator+ (=convolution) 

53  
54 
typedef std::list<abstractEvent_t> succList_t; 

55  
56 
/** 

57 
* A tree to perform a BFS and predict the probability 

58 
* for a causal violation to occur. 

59 
*/ 

60 
class cTree 

26  61 
{ 
62 
private: 

63 
// Lower and upper bounds for the causal violation probability: 

64 
double lowerBound; 

65 
double upperBound; 

66 
std::list<cNode> leaves; 

67  
68 
public: 

69 
/** 

70 
* Constructor for tree 

71 
* The probability for a causal violation resides (obviously) in the interval [0;1]. 

72 
*/ 

73 
cTree() 

74 
{ 

75 
lowerBound=0; 

76 
upperBound=1; 

77 
} 

78  
79 
/** 

80 
* Adding a node into the tree. 

81 
* @param parent The parent node in the tree. If parent==NULL, the new node will 

82 
* be inserted as one of the roots of the tree (forest) 

83 
* @param eventType The OMNeT++ message kind 

84 
* @param moduleId The module the event takes place at 

85 
* @param probabilityDistribution The PDF to be stored inside the node 

86 
* @param isConflicting Whether this node is a conflicting node, i.e. an event on this 

87 
* node would conflict with the pending event since the pending event 

88 
* takes place at the same module. 

89 
*/ 

90 
void addNode(cNode* parent, evType_t evType, int moduleId, pdf_t probabilityDistribution, bool isConflicting) 

91 
{ 

92 
cNode newNode(evType,moduleId,probabilityDistribution); 

93 
double dangerProb=newNode>getProbability() 

94 
upperBound=1(1upperBound)*(1dangerProb); 

95 
if(isConflicting) lowerBound=1(1lowerBound)*(1dangerProb); 

96 
if(parent && leaves.contains(parent)) 

97 
{ 

98 
upperBound=1(1upperBound)/(1parent>getProbability()); 

99 
leaves.remove(parent); 

100 
} 

101 
leaves.push_back(newNode); 

102 
} 

103  
104 
// Performing BFS and spanning the tree: 

105 
bool bfs(double threshold, int moduleId) 

106 
{ 

107 
for(nodeSet_t::iterator leaf=leaves.begin();leaf!=leaves.end();++leaf) 

108 
{ 

109 
if(leaf>isConflicting()) 

110 
{ 

111 
continue; 

112 
} 

113 
succList_t succs=leaf>getSuccessors(); 

114 
for(succList_t::iterator succ=succs.begin();succ!=succs.end();++succ) 

115 
{ 

116 
// We need to convolve the PDF of the (previous) leaf node with the PDF of its successors: 

117 
pdf_t convolvedPdf=leaf>getProbabilityDistribution()+succ>getProbabilityDistribution(); 

118 
evType_t succEvType=succ>getEvType(); 

119 
int succModId=succ>getEvModId(); 

120 
bool isConflicting=moduleId==succModId; 

121 
// We add the new node as a child of the leaf into the tree: 

122 
addNode(leaf,succEvType,convolvedPdf,isConflicting); 

123 
// If both bounds for the probability are below (above) the threshold, 

124 
// the probability itself is also below (above) the threshold, 

125 
// i.e. we can yield the decision without further inspecting the BFS tree. 

126 
if(lowerBound<=threshold && upperBound<=threshold) return true; 

127 
if(lowerBound>=threshold && upperBound>=threshold) return false; 

128 
} 

129 
} 

130 
} 

131 
}; 

132  
133 
/** 

134 
* This function will be executed whenever the event scheduler encounters 

135 
* an event that cannot be executed conservatively at that moment. In this 

136 
* case the heuristic computes a probability for a causal violation to occur / 

137 
* to not occur, and returns a recommendation whether to execute the event 

138 
* speculatively (return value=true) or not (return value=false). 

139 
* @param pendingEv The pending event (message in OMNeT++). 

140 
* @param setO The set $O$ of currently executed events. 

141 
* @param threshold The threshold to compare against. 

142 
* @return true iff recommendation for speculative execution is positive. 

143 
*/ 

144 
bool cHeuristic::askHeuristic(cMessage* pendingEv,eventSet_t setO,double threshold) 

145 
{ 

146 
cTree bfsTree; 

147 
int pendingEvModId=pendingEv>getArrivalModuleId(); 

148  
149 
for (eventSet_t::iterator it=setO>begin();it!=setO>end();++it) 

150 
{ 

151 
evType_t runningEvType=it>getEvType(); 

152 
int runningEvModId=it>getEvModId(); 

153 
bool isConflicting=pendingEvModId==runningEvModId; 

154 
pdf_t pdf(eventInO>arrivalTime()pendingEvent>arrivalTime()); 

155 
bfsTree.addNode(NULL,runningEvType,pdf,isConflicting); 

156 
} 

27  157  
158 
return bfsTree.bfs(threshold,pendingEvModId); 

28  159 
} 
29  160 
Also available in: Unified diff