Giả sử chúng ta có một RAM và RAM đó được tổ chức thành các khối. có nhiều tiến trình đang chạy trên hệ thống. Chúng ta phải lưu ý rằng mọi tiến trình đều nhận được thông tin sau, (Luồng T, Khối bộ nhớ M, thời gian t, R / W) Điều này cho thấy luồng T đang triển khai khối bộ nhớ M tại thời điểm t nhất định và hoạt động có thể được đọc (R ) hoặc viết (W).
Trường hợp sau cho biết đó có phải là xung đột bộ nhớ hay không -
-
Nhiều hơn một thao tác đọc tại cùng một vị trí không phải là lý do xung đột.
-
Khi thao tác ghi đang được thực hiện trong khoảng từ x + 5 đến x-5 đến vị trí của M, nó sẽ chịu trách nhiệm tạo ra xung đột cho vị trí truy cập luồng M tại thời điểm x trong đó x được gọi là một thời điểm nào đó.
Vì vậy, nếu luồng T1 truy cập vị trí bộ nhớ M tại thời điểm x + 1 và luồng T2 truy cập vị trí M trước thời điểm x + 6, thì T1 và T2 đang tạo ra xung đột khi một trong số chúng thực hiện thao tác ghi.
Nếu chúng ta có một danh sách các luồng đang truy cập các vị trí bộ nhớ. Chúng tôi phải tìm ra tất cả các xung đột.
Vì vậy, nếu đầu vào giống như [(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)], thì đầu ra sẽ là các luồng xung đột (2, 4 ) và (2, 6), và tất cả các thao tác khác đều giống nhau.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
Tạo chuỗi với id, memory_block, thời gian và hoạt động
-
sắp xếp mảng th_arr dựa trên khối bộ nhớ, khi các khối bộ nhớ giống nhau thì sử dụng thời gian.
-
để khởi tạo i:=1, khi i - n, cập nhật (tăng i lên 1), thực hiện -
-
nếu th_arr [i] .memory_block giống với th_arr [i - 1] .memory_block, thì -
-
nếu th_arr [i] .time <=th_arr [i-1] .time + 5, thì -
-
j:=i - 1
-
while (th_arr [i] .memory_block giống với th_arr [j] .memory_block và th_arr [i] .time <=th_arr [j] .time + 5 và j> =0), do -
-
nếu th_arr [i]. hoạt động giống như 'W' hoặc th_arr [j]. hoạt động giống như 'W', thì -
-
hiển thị các chuỗi xung đột th_arr [j] và th_arr [i]
-
-
(giảm j đi 1)
-
-
-
-
Ví dụ (C ++)
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
#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;
else 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 << "Conflicting threads [" << 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 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
Conflicting threads [2, 4] Conflicting threads [2, 6]