मान लीजिए हमारे पास एक रैम है और वह रैम ब्लॉकों में व्यवस्थित है। कई प्रोसेस सिस्टम पर चल रहे हैं। हमें ध्यान रखना होगा कि हर प्रोसेस को निम्नलिखित जानकारी मिलती है, (थ्रेड T, मेमोरी ब्लॉक M, समय t, R/W) यह इंगित करता है कि थ्रेड T दिए गए समय t पर मेमोरी ब्लॉक M को एक्सेस कर रहा था और ऑपरेशन या तो रीड (R) या राइट (W) हो सकता है।
निम्नलिखित मामला इंगित करता है कि यह मेमोरी संघर्ष है या नहीं -
एक ही स्थान पर एक से अधिक रीड ऑपरेशन संघर्ष का कारण नहीं हैं।
जब x+5 से x-5 तक स्थान M पर राइट ऑपरेशन किया जा रहा है, तो यह समय 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 << "विरोधी थ्रेड्स [" << 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'}}
आउटपुट
विरोधी थ्रेड्स [2, 4] विरोधी थ्रेड्स [2, 6]