RAM이 있고 RAM이 블록으로 구성되어 있다고 가정합니다. 시스템에서 여러 프로세스가 실행 중입니다. 우리는 모든 프로세스가 다음 정보를 얻는다는 것을 명심해야 합니다. (Thread T, Memory Block M, time t, R/W) 이것은 스레드 T가 주어진 시간 t에서 메모리 블록 M을 구현하고 있었고 작업이 읽기(R)일 수 있음을 나타냅니다. ) 또는 쓰기(W).
다음의 경우는 메모리 충돌 여부를 나타냅니다. -
-
동일한 위치에서 둘 이상의 읽기 작업이 충돌의 원인이 아닙니다.
-
쓰기 작업이 x+5에서 x-5 사이에서 M의 위치까지 수행될 때 x는 시간이라고 하는 x 시간에 위치 M에 액세스하는 스레드에 대한 충돌을 일으키는 책임이 있습니다.
따라서 스레드 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, 시간 및 작업으로 스레드 생성
-
메모리 블록이 같을 때 시간을 사용하여 메모리 블록을 기준으로 배열 th_arr을 정렬합니다.
-
initialize 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 :=나는 - 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]