C++で複数スレッド間のメモリ競合を検出するアルゴリズム

RAMがブロック単位で構成されており、システム上では複数のプロセスが同時に動作している状況を想定します。各プロセスは次のような形式のアクセス情報を持っています。
(スレッドT、メモリブロックM、時刻t、R/W)
これは、スレッドTが時刻tにメモリブロックMへアクセスし、その操作が読み取り(R)または書き込み(W)のいずれかであったことを意味します。

メモリ競合の判定条件

メモリ競合が発生しているかどうかは、以下のルールで判断されます。

• 同じメモリ位置に対する複数の読み取り操作は、競合の原因にはなりません。
• あるスレッドが時刻xにメモリ位置Mへアクセスしている場合、x−5からx+5の範囲内で書き込み操作が行われると、競合が発生します。

つまり、スレッド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(スレッドID)、memory_block(メモリブロック)、time(時刻)、operation(操作種別)を持つThreadクラスを作成します。
• 配列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または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]