From 60fb578a0202d354b2fdc5cdf86c04fb9d62c729 Mon Sep 17 00:00:00 2001
From: crupest <crupest@outlook.com>
Date: Mon, 14 Jun 2021 18:38:04 +0800
Subject: import(life): ...

---
 .../DeadLockDetectionDemo.cpp                      | 89 +++++++++++++++++++++-
 .../DeadLockTestData1.txt                          |  4 +
 .../DeadLockTestData2.txt                          |  4 +
 .../DeadLockTestData3.txt                          |  6 ++
 .../DeadLockTestData4.txt                          |  9 +++
 5 files changed, 108 insertions(+), 4 deletions(-)
 create mode 100644 works/life/operating-system-experiment/DeadLockTestData1.txt
 create mode 100644 works/life/operating-system-experiment/DeadLockTestData2.txt
 create mode 100644 works/life/operating-system-experiment/DeadLockTestData3.txt
 create mode 100644 works/life/operating-system-experiment/DeadLockTestData4.txt

(limited to 'works/life')

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
-- 
cgit v1.2.3