Trong hệ điều hành, deadlock xảy ra khi các tiến trình tranh chấp tài nguyên và chờ đợi lẫn nhau, dẫn đến trạng thái không thể tiếp tục mà không có sự can thiệp từ bên ngoài. Để xác định sự tồn tại của deadlock, mô hình hóa bài toán bằng đồ thị phân bổ tài nguyên và áp dụng thuật toán sắp xếp topo là phương pháp hiệu quả.
Đồ thị này bao gồm hai loại nút: tiến trình (P) và tài nguyên (R). Cạnh từ tiến trình đến tài nguyên (pi → rj) biểu thị yêu cầu tài nguyên, trong khi cạnh từ tài nguyên đến tiến trình (rj → pi) cho biết tài nguyên đang được giữ. Nếu đồ thị không chứa chu trình, hệ thống an toàn; ngược lại, có thể xảy ra deadlock.
Dữ liệu đầu vào bắt đầu với số lượng bộ dữ liệu T. Mỗi bộ gồm bốn số nguyên P, R, E1, E2 lần lượt là số tiến trình, tài nguyên, cạnh từ tiến trình đến tài nguyên, và từ tài nguyên đến tiến trình. Các cạnh tiếp theo được cung cấp theo thứ tự.
Ví dụ, hai tiến trình A và B, A giữ tài nguyên X và chờ Y, B giữ Y và chờ X, tạo thành chu trình.
Dưới đây là hai cách triển khai thuật toán để kiểm tra chu trình:
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAX_NODES = 1100;
int state[MAX_NODES];
int adjMatrix[MAX_NODES][MAX_NODES];
int topologicalOrder[MAX_NODES];
int currentIndex, totalNodes;
const int UNVISITED = 0;
const int VISITING = -1;
const int VISITED = 1;
bool detectCycle(int node) {
state[node] = VISITING;
for (int neighbor = 0; neighbor < totalNodes; neighbor++) {
if (adjMatrix[node][neighbor]) {
if (state[neighbor] == VISITING) {
return false;
} else if (state[neighbor] == UNVISITED && !detectCycle(neighbor)) {
return false;
}
}
}
state[node] = VISITED;
topologicalOrder[--currentIndex] = node;
return true;
}
bool hasCycle() {
currentIndex = totalNodes;
memset(state, UNVISITED, sizeof(state));
for (int node = 0; node < totalNodes; node++) {
if (state[node] == UNVISITED && !detectCycle(node)) {
return true;
}
}
return false;
}
int main() {
int testCases;
scanf("%d", &testCases);
for (int caseNum = 1; caseNum <= testCases; caseNum++) {
int processCount, resourceCount, edgeProcToRes, edgeResToProc;
scanf("%d %d %d %d", &processCount, &resourceCount, &edgeProcToRes, &edgeResToProc);
totalNodes = processCount + resourceCount;
memset(adjMatrix, 0, sizeof(adjMatrix));
for (int i = 0; i < edgeProcToRes; i++) {
int proc, res;
scanf("%d %d", &proc, &res);
adjMatrix[proc][res + processCount] = 1;
}
for (int i = 0; i < edgeResToProc; i++) {
int res, proc;
scanf("%d %d", &res, &proc);
adjMatrix[res + processCount][proc] = 1;
}
if (hasCycle()) {
printf("Case %d: Possible\n", caseNum);
} else {
printf("Case %d: Impossible\n", caseNum);
}
}
return 0;
}
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int MAX_NODES = 1100;
int adjMatrix[MAX_NODES][MAX_NODES];
int inDegree[MAX_NODES];
int totalNodes;
bool hasCycle() {
queue<int> q;
int processedCount = 0;
for (int i = 0; i < totalNodes; i++) {
if (inDegree[i] == 0) {
q.push(i);
}
}
while (!q.empty()) {
int current = q.front();
q.pop();
processedCount++;
for (int neighbor = 0; neighbor < totalNodes; neighbor++) {
if (adjMatrix[current][neighbor]) {
inDegree[neighbor]--;
if (inDegree[neighbor] == 0) {
q.push(neighbor);
}
}
}
}
return processedCount != totalNodes;
}
int main() {
int testCases;
scanf("%d", &testCases);
for (int caseNum = 1; caseNum <= testCases; caseNum++) {
int processCount, resourceCount, edgeProcToRes, edgeResToProc;
scanf("%d %d %d %d", &processCount, &resourceCount, &edgeProcToRes, &edgeResToProc);
totalNodes = processCount + resourceCount;
memset(adjMatrix, 0, sizeof(adjMatrix));
memset(inDegree, 0, sizeof(inDegree));
for (int i = 0; i < edgeProcToRes; i++) {
int proc, res;
scanf("%d %d", &proc, &res);
adjMatrix[proc][res + processCount] = 1;
inDegree[res + processCount]++;
}
for (int i = 0; i < edgeResToProc; i++) {
int res, proc;
scanf("%d %d", &res, &proc);
adjMatrix[res + processCount][proc] = 1;
inDegree[proc]++;
}
if (hasCycle()) {
printf("Case %d: Possible\n", caseNum);
} else {
printf("Case %d: Impossible\n", caseNum);
}
}
return 0;
}