forked from davidbrowning/beladysAnomaly
-
Notifications
You must be signed in to change notification settings - Fork 0
/
BeladyThirdTimesTheCharm.cpp
94 lines (87 loc) · 2.38 KB
/
BeladyThirdTimesTheCharm.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <unordered_map>
#include <vector>
#include <cassert>
#include <queue>
#include <iostream>
std::vector<std::vector<int> > generateSequences(){
srand(time(NULL));
std::vector<std::vector<int> > v;
for (int i = 0; i < 100; i++){
std::vector<int> subV;
for(int j = 0; j < 1000; j++){
subV.push_back(rand() % 250);
}
v.push_back(subV);
}
return v;
}
bool isInMemory(int value, std::unordered_map<int, int> & memory){
auto f = memory.find(value);
if(f != memory.end()){
return true;
}
else {
return false;
}
}
int getFramePageFaults(int i, std::vector<int>& sequence){
assert(sequence.size() == 1000);
std::queue<int> que;
std::unordered_map<int, int> memory;
int pageFaults = 0;
for(int j = 0; j < 1000; j++){
if(isInMemory(sequence.at(j), memory)){
j++;
}
else if(que.size() >= i){
pageFaults++;
memory.erase(que.front());
que.pop();
memory.insert({j, sequence.at(j)});
que.push(sequence.at(j));
}
else{
memory.insert({j, sequence.at(j)});
que.push(sequence.at(j));
}
}
return pageFaults;
}
std::vector<int> populateSingleSequencePageFaults(std::vector<int> &sequence){
std::vector<int> thisSequence;
for(int i = 1; i <= 100; i++){
thisSequence.push_back(getFramePageFaults(i, sequence));
}
return thisSequence;
}
std::vector<std::vector<int> > populatePageFaults(std::vector<std::vector<int> >& sequences){
std::vector<std::vector<int> > results;
for(int i = 0; i < 100; i++){
assert(!sequences.at(i).empty());
auto thisSequence = sequences.at(i);
assert(thisSequence.size() == 1000);
results.push_back(populateSingleSequencePageFaults(thisSequence));
}
return results;
}
void printResults(std::vector<std::vector<int> > & results){
int anomalyCounter = 0;
for(int i = 0; i < 100; i++){
for(int j = 0; j < 99; j++){
if(results.at(i).at(j) < results.at(i).at(j+1)){
std::cout << "Anomaly Discovered!" << std::endl;
anomalyCounter++;
std::cout << "\tSequence: " << (i+1) << std::endl;
std::cout << "\tPage Faults: " << results.at(i).at(j) << "@ Frame Size: " << (j + 1) << std::endl;
std::cout << "\tPage Faults: " << results.at(i).at(j + 1) << "@ Frame Size: " << (j + 2) << std::endl;
}
}
}
std::cout << "Anomaly Discovered " << anomalyCounter << " times." << std::endl;
}
int main(){
auto sequences = generateSequences();
auto results = populatePageFaults(sequences);
printResults(results);
return 0;
}