发现多线程间内存冲突

Input:
(1, 512, 1, R)
(2, 432, 2, W)
(3, 512, 3, R)
(4, 932, 4, R)
(5, 512, 5, W)
(6, 932, 6, R)
(7, 835, 7, R)
(8, 432, 8, R)
Output:
Thread 1 & 3 conflict with thread 5
All other operations are safe.


// C++ program to find memory conflicts among threads
#include<bits/stdc++.h>
using namespace std;
/* Structure for details of thread */
struct Thread
{
    int id, memblck, time;
    char access;
};
/* Compare function needed for sorting threads
   We first sort threads on the basis of memory block,
   If they are same, then we sort on the basis of time */
bool compare(const Thread& x, const Thread& y)
{
    if (x.memblck == y.memblck)
        return x.time < y.time;
    else return x.memblck < y.memblck;
}
// Function to print all conflicts among threads
void printConflicts(Thread arr[], int n)
{
    /* Sort the threads first by memblock, then by
       time */
    sort(arr, arr+n, compare);
    /*start from second thread till last thread*/
    for (int i = 1; i < n; i++)
    {
        /* As threads are sorted, We check further
           for conflict possibility only if there
           memblock is same*/
        if(arr[i].memblck == arr[i-1].memblck)
        {
            /* As threads with same block are sorted in increasing order
               of access time. So we check possibility conflict from last
               thread to all previous threads which access the same block
               of memory such that the current thread access under the
               arr[i-1].time + 5.. and if any of them does read operation
               than conflict occurs. at any point memblock becomes different
               or current thread moves out of vulnerable time of latest
               previous processed thread, the loop breaks.
            */
            if (arr[i].time <= arr[i-1].time+5)
            {
                int j = i-1; /* start with previous thread */
                // Find all previous conflicting threads
                while (arr[i].memblck == arr[j].memblck &&
                        arr[i].time <= arr[j].time+5 &&
                        j >= 0)
                {
                    if (arr[i].access == 'W' || arr[j].access == 'W')
                    {
                        cout << "threads " << arr[j].id << " and "
                             << arr[i].id << " conflict.\n";
                    }
                    j--;
                }
            }
        }
    }
    cout << "All other operations are same\n";
}
// Driver program to test above function
int main()
{
    Thread arr[] = { {1, 512, 1, 'R'}, {2, 432, 2, 'W'},
                     {3, 512, 3, 'R'}, {4, 932, 4, 'R'},
                     {5, 512, 5, 'W'}, {6, 932, 6, 'R'},
                     {7, 835, 7, 'R'}, {8, 432, 8, 'R'}
                   };
    int n = sizeof(arr)/sizeof(arr[0]);
    printConflicts(arr, n);
    return 0;
}


threads 3 and 5 conflict.
threads 1 and 5 conflict.
All other operations are same