ধরুন আমাদের একটি RAM আছে এবং সেই RAM ব্লকে সংগঠিত। সিস্টেমে চলমান একাধিক প্রক্রিয়া আছে। আমাদের মনে রাখতে হবে যে প্রতিটি প্রক্রিয়া নিম্নলিখিত তথ্য পায়, (থ্রেড টি, মেমরি ব্লক এম, টাইম টি, আর/ডব্লিউ) এটি নির্দেশ করে যে থ্রেড টি প্রদত্ত সময়ে মেমরি ব্লক এম বাস্তবায়ন করছে এবং অপারেশনটি রিড(R) হতে পারে ) অথবা লিখুন(W).
নিম্নলিখিত কেসটি ইঙ্গিত করছে যে এটি মেমরির দ্বন্দ্ব কিনা −
-
একই স্থানে একাধিক রিড অপারেশন বিরোধের কারণ নয়৷
-
যখন x+5 থেকে x-5 থেকে M-এর অবস্থানের মধ্যে লেখার ক্রিয়াকলাপ সম্পাদিত হয়, তখন এটি একটি থ্রেড অ্যাক্সেস করার অবস্থান M-এর জন্য x সময়ে একটি দ্বন্দ্ব তৈরির জন্য দায়ী থাকবে যেখানে x কে কিছু সময় বলা হয়।
সুতরাং, যদি থ্রেড T1 মেমরি অবস্থান M অ্যাক্সেস করে x+1 সময়ে এবং থ্রেড 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), এবং অন্যান্য সমস্ত অপারেশন একই।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
আইডি, মেমরি_ব্লক, সময় এবং অপারেশন
দিয়ে থ্রেড তৈরি করুন -
মেমরি ব্লকের উপর ভিত্তি করে অ্যারে 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].অপারেশন 'W' বা th_arr[j].অপারেশন '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]
