Cho RAM tổ chức thành khối (block). Nhiều tiến trình chạy. Mỗi truy cập có thông tin: (Thread T, Khối bộ nhớ M, thời gian t, R/W). Xác định xung đột bộ nhớ.
Quy tắc xung đột:
- Nhiều thao tác đọc (R) cùng vị trí KHÔNG gây xung đột.
- Thao tác ghi (W) tại thời điểm x tạo xung đột cho luồng khác truy cập cùng vị trí M trong khoảng [x-5, x+5].
Ví dụ: Thread T1 truy cập M tại x+1, T2 truy cập M trước x+6 → xung đột nếu một trong hai ghi.
Ví dụ
Đầu vào: [(1,932,1,R), (2,512,2,W), (3,932,3,R), (4,512,4,R), (5,432,5,R), (6,512,6,R), (7,835,7,W), (8,432,8,R)]
Đầu ra: Xung đột: (2,4) và (2,6). Các thao tác khác không xung đột.
Giải pháp
- Tạo struct Thread với id, memory_block, time, operation.
- Sắp xếp mảng theo memory_block, nếu bằng thì theo time.
- Duyệt mảng, nếu memory_block giống nhau và time chênh lệch ≤ 5, kiểm tra ngược lại các phần tử trước đó cùng block và trong khoảng thời gian. Nếu có operation 'W' → báo xung đột.
Ví dụ
#include <bits/stdc++.h>
using namespace std;
class Thread {
public:
int id, memory_block, time;
char operation;
};
bool compare(const Thread& x, const Thread& y) {
if (x.memory_block == y.memory_block)
return x.time < y.time;
return x.memory_block < y.memory_block;
}
void display_conflicts(Thread th_arr[], int n) {
sort(th_arr, th_arr + n, compare);
for (int i = 1; i < n; i++) {
if (th_arr[i].memory_block == th_arr[i-1].memory_block) {
if (th_arr[i].time <= th_arr[i-1].time + 5) {
int j = i - 1;
while (th_arr[i].memory_block == th_arr[j].memory_block &&
th_arr[i].time <= th_arr[j].time + 5 && j >= 0) {
if (th_arr[i].operation == 'W' || th_arr[j].operation == 'W') {
cout << "Xung đột luồng [" << th_arr[j].id << ", " << th_arr[i].id << "]\n";
}
j--;
}
}
}
}
}
int main() {
Thread th_arr[] = {{1,932,1,'R'},{2,512,2,'W'},{3,932,3,'R'},{4,512,4,'R'},{5,432,5,'R'},{6,512,6,'R'},{7,835,7,'W'},{8,432,8,'R'}};
int n = sizeof(th_arr) / sizeof(th_arr[0]);
display_conflicts(th_arr, n);
}
Đầu ra
Xung đột luồng [2, 4] Xung đột luồng [2, 6]