資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究在 C++ 中查詢多執行緒之間的記憶體衝突
假設我們有一個 RAM，並且該 RAM 以塊的形式組織。系統上執行著多個程序。我們必須記住，每個程序都會獲取以下資訊，(執行緒 T、記憶體塊 M、時間 t、R/W) 這表示執行緒 T 在給定時間 t 時正在操作記憶體塊 M，並且操作可以是讀取 (R) 或寫入 (W)。
以下情況表明是否存在記憶體衝突：
在同一位置進行多個讀取操作並不是衝突的原因。
當在 M 位置的 x+5 到 x-5 之間執行寫入操作時，它將導致在時間 x 訪問 M 位置的執行緒發生衝突，其中 x 表示某個時間。
因此，如果執行緒 T1 在時間 x+1 訪問記憶體位置 M，而執行緒 T2 在時間 x+6 之前訪問位置 M，那麼當其中一個執行寫入操作時，T1 和 T2 會發生衝突。
如果我們有一個訪問記憶體位置的執行緒列表。我們必須找到所有衝突。
因此，如果輸入類似於 [(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)]，則輸出將是衝突執行緒 (2, 4) 和 (2, 6)，而所有其他操作都是相同的。
為了解決這個問題，我們將遵循以下步驟：
建立包含 id、memory_block、time 和 operation 的執行緒
根據記憶體塊對陣列 th_arr 進行排序，當記憶體塊相同的情況下，使用時間進行排序。
初始化 i := 1，當 i − n 時，更新（將 i 增加 1），執行：
如果 th_arr[i].memory_block 與 th_arr[i - 1].memory_block 相同，則：
如果 th_arr[i].time <= th_arr[i-1].time+5，則：
j := i - 1
當 (th_arr[i].memory_block 與 th_arr[j].memory_block 相同且 th_arr[i].time <= th_arr[j].time+5 且 j >= 0) 時，執行：
如果 th_arr[i].operation 與 'W' 相同或 th_arr[j].operation 與 'W' 相同，則：
顯示衝突執行緒 th_arr[j] 和 th_arr[i]
（將 j 減 1）
示例（C++）
讓我們看看以下實現以獲得更好的理解：
#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);
}輸入
{{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'}}輸出
Conflicting threads [2, 4] Conflicting threads [2, 6]
155 次檢視
