একটি র্যাম আছে যা ব্লকে বিভক্ত। একাধিক থ্রেড র্যাম এক্সেস করে। প্রতিটি অ্যাক্সেস: (Thread ID, Memory Block, Time, R/W)। মেমরি কনফ্লিক্ট হয় যখন:
- একই সময়ে একাধিক রাইট অপারেশন একই ব্লকে।
- রাইট অপারেশনের সময়
tহলে,[t-5, t+5]রেঞ্জে অন্য থ্রেড সেই ব্লকে অ্যাক্সেস করলে (রিড বা রাইট) কনফ্লিক্ট। - শুধু রিড-রিড কনফ্লিক্ট নয়।
উদাহরণ
Accesses: (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] and [2, 6]
অ্যালগরিদম
- অ্যাক্সেসগুলো মেমরি ব্লক অনুযায়ী সর্ট করুন, তারপর টাইম অনুযায়ী।
- প্রতিটি অ্যাক্সেসের জন্য তার আগের ৫ টাইম ইউনিটের মধ্যে একই ব্লকে রাইট অপারেশন আছে কিনা চেক করুন।
C++ প্রোগ্রাম
#include <bits/stdc++.h>
using namespace std;
struct Thread {
int id, memBlock, time;
char op;
};
bool cmp(const Thread& a, const Thread& b) {
if (a.memBlock != b.memBlock) return a.memBlock < b.memBlock;
return a.time < b.time;
}
void detectConflicts(Thread arr[], int n) {
sort(arr, arr+n, cmp);
for (int i=1;i=0 && arr[j].memBlock==arr[i].memBlock && arr[i].time <= arr[j].time+5; j--) {
if (arr[i].op=='W' || arr[j].op=='W')
cout << "Conflicting threads [" << arr[j].id << ", " << arr[i].id << "]\n";
}
}
}
}
}
int main() {
Thread th[] = {{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'}};
detectConflicts(th, 8);
return 0;
}
আউটপুট: Conflicting threads [2, 4] Conflicting threads [2, 6]
