C++の複数のスレッド間のメモリの競合を見つける

RAMがあり、RAMがブロックで編成されているとします。システム上で実行されている複数のプロセスがあります。すべてのプロセスが次の情報を取得することに注意する必要があります（スレッドT、メモリブロックM、時間t、R / W）これは、スレッドTが特定の時間tにメモリブロックMを実装しており、操作がread（R ）またはwrite（W）。

次のケースは、メモリの競合であるかどうかを示しています-

• 同じ場所での複数の読み取り操作は、競合の理由ではありません。

• 書き込み操作がx+5からx-5の間でMの場所に対して実行されている場合、時間xで場所Mにアクセスするスレッドの競合を作成する責任があります。xはある時間と呼ばれます。

したがって、スレッドT1が時刻x + 1でメモリロケーションMにアクセスし、スレッドT2が時刻x + 6より前にロケーションMにアクセスした場合、T1とT2のいずれかが書き込み操作を行うと、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をメモリブロックに基づいて並べ替えます。メモリブロックが同じ場合は、時間を使用します。

• 初期化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と同じです）、do-

        • 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]