数据结构
网络
关系数据库管理系统
操作系统
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 次查看
