diff options
Diffstat (limited to 'works')
5 files changed, 108 insertions, 4 deletions
diff --git a/works/life/operating-system-experiment/DeadLockDetectionDemo.cpp b/works/life/operating-system-experiment/DeadLockDetectionDemo.cpp index b22549e..e043161 100644 --- a/works/life/operating-system-experiment/DeadLockDetectionDemo.cpp +++ b/works/life/operating-system-experiment/DeadLockDetectionDemo.cpp @@ -1,14 +1,66 @@ -#include <fstream>
#include <iostream>
+#include <unordered_map>
+#include <unordered_set>
#include <vector>
+const int LOCK_START_INDEX = 10000;
+
+struct Node {
+ int id;
+};
+
+bool operator==(const Node &left, const Node &right) {
+ return left.id == right.id;
+}
+
+template <> struct std::hash<Node> {
+ std::size_t operator()(const Node &node) const {
+ return std::hash<int>{}(node.id);
+ }
+};
+
+std::ostream &operator<<(std::ostream &left, const Node &right) {
+ left << (right.id > LOCK_START_INDEX ? "lock" : "process") << ' '
+ << (right.id > LOCK_START_INDEX ? right.id - LOCK_START_INDEX
+ : right.id);
+ return left;
+}
+
+bool dfs(
+ const Node *root,
+ std::unordered_map<const Node *, std::unordered_set<const Node *>> &edges,
+ std::unordered_map<const Node *, bool> &visited) {
+
+ if (visited[root]) {
+ std::cout << "Ohhhhhh, it is already visited!\n";
+ return true;
+ }
+
+ visited[root] = true;
+ auto r = edges.find(root);
+ if (r != edges.cend())
+ for (auto n : r->second) {
+ std::cout << "from " << *root << " go to " << *n << "\n";
+ if (dfs(n, edges, visited))
+ return true;
+ std::cout << "from " << *n << " back to " << *root << "\n";
+ }
+
+ edges.erase(root);
+ return false;
+}
+
+// 1 10001 -> process 1 is waiting for lock 10001
+// 10001 1 -> lock 10001 is owned by process 1
+
int main() {
std::vector<int> ns;
- while (!std::cin.eof() || std::cin) {
+ while (std::cin) {
int n;
std::cin >> n;
- ns.push_back(n);
+ if (std::cin)
+ ns.push_back(n);
}
if (!std::cin.eof()) {
@@ -21,5 +73,34 @@ int main() { return -1;
}
-
+ std::unordered_set<Node> nodes;
+ std::unordered_map<const Node *, std::unordered_set<const Node *>> edges;
+
+ for (int i = 0; i < ns.size(); i += 2) {
+ int p = ns[i];
+ int l = ns[i + 1];
+ auto r1 = nodes.insert({p});
+ auto r2 = nodes.insert({l});
+ edges[&(*r1.first)].insert(&(*r2.first));
+ }
+
+ bool h = false;
+
+ while (!edges.empty()) {
+ auto n = edges.cbegin()->first;
+ std::unordered_map<const Node *, bool> visited;
+ std::cout << "Begin to detect child graph containing '" << *n << "'.\n";
+ if (dfs(n, edges, visited)) {
+ h = true;
+ break;
+ }
+ }
+
+ if (h) {
+ std::cout << "Cycle, aka dead lock, detected.\n";
+ } else {
+ std::cout << "You are free of dead lock!!!\n";
+ }
+
+ return 0;
}
diff --git a/works/life/operating-system-experiment/DeadLockTestData1.txt b/works/life/operating-system-experiment/DeadLockTestData1.txt new file mode 100644 index 0000000..0c8dd14 --- /dev/null +++ b/works/life/operating-system-experiment/DeadLockTestData1.txt @@ -0,0 +1,4 @@ +1 10001
+2 10001
+3 10001
+4 10001
diff --git a/works/life/operating-system-experiment/DeadLockTestData2.txt b/works/life/operating-system-experiment/DeadLockTestData2.txt new file mode 100644 index 0000000..d632f2a --- /dev/null +++ b/works/life/operating-system-experiment/DeadLockTestData2.txt @@ -0,0 +1,4 @@ +10001 1
+1 10002
+2 10001
+10002 2
diff --git a/works/life/operating-system-experiment/DeadLockTestData3.txt b/works/life/operating-system-experiment/DeadLockTestData3.txt new file mode 100644 index 0000000..1e1692d --- /dev/null +++ b/works/life/operating-system-experiment/DeadLockTestData3.txt @@ -0,0 +1,6 @@ +1 10001
+10001 2
+2 10002
+10002 3
+3 10003
+10003 1
diff --git a/works/life/operating-system-experiment/DeadLockTestData4.txt b/works/life/operating-system-experiment/DeadLockTestData4.txt new file mode 100644 index 0000000..d124102 --- /dev/null +++ b/works/life/operating-system-experiment/DeadLockTestData4.txt @@ -0,0 +1,9 @@ +1 10001
+2 10001
+3 10002
+3 10004
+10001 3
+4 10001
+4 10005
+10004 5
+10005 5
|