查找多个线程之间的内存冲突-yiteyi-C++库

考虑在块中组织的RAM。系统上运行多个进程。每个应用程序都会获得以下信息。

null

（线程T，内存块M，时间T，R/W），这基本上说明线程T在时间T使用内存块M，操作可以读取或写入。

记忆冲突定义为—— –同一位置的多个读取操作不会导致冲突。 –x+5到x-5到位置M之间的一次写入操作将导致线程在时间x访问位置M时发生冲突，其中x是标准时间单位中的某个时间。 –示例–如果线程T1在时间x+1访问了内存位置M，而线程T2在时间x+6之前访问了位置M，那么T1和T2可能会发生冲突，因为其中一个执行了写操作。

你会看到访问内存位置的线程列表，你必须找到所有冲突。

例如——

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++实现这一思想。

                     // 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."                               ;                   
                                         }                   
                                         j--;                   
                                         }                   
                                         }                   
                                         }                   
                                         }                   
                             
                                         cout <<                               "All other operations are same"                               ;                   
                     }                   
                             
                     // 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

时间复杂度：上述解决方案使用排序对线程进行排序。排序可以在O（nLogn）时间内完成。然后打印所有冲突。打印所有冲突需要O（n+m）时间，其中m是冲突数。所以总的时间复杂度是O（nLogn+m）。

本文由高拉夫·阿希瓦。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章