Find memory conflicts among multiple threads
Consider a RAM organized in blocks. There are multiple processes running on the system. Every application gets below information.
(Thread T, Memory Block M, time t, R/W) which essentially tells that the thread T was using memory block M at time t and operation could be read or write. Memory conflict is defined as – – Multiple read operations at the same location are not cause of conflict. – One write operation between x+5 to x-5 to location M, will be cause of conflict for a thread accessing location M at time x where x is some time in standard unit of time measurement. – Example – If thread T1 accessed memory location M at time x+1 and if a thread T2 accesses location M before time x+6, then T1 and T2 are candidate of conflict given one of them does write operation. You are given with the list of threads accessing memory locations, you have to find all conflicts. Example–
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.
We strongly recommend you to minimize your browser and try this yourself first.
The idea is to sort all threads by memory block and if memory block is same, then by time. Once we have all threads sorted, we can traverse all threads one by one. For every thread being traversed, we simply need to check previous adjacent threads of same block as threads are sorted by time. Below is C++ implementation of this idea.
// 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;
}
import java.util.*;
// Class for details of thread
class Thread {
int id, memblck, time;
char access;
// Constructor
public Thread(int id, int memblck, int time, char access) {
this.id = id;
this.memblck = memblck;
this.time = time;
this.access = access;
}
}
public class Main {
// Function to print all conflicts among threads
public static void printConflicts(Thread arr[]) {
/* Sort the threads first by memblock, then by
time */
Arrays.sort(arr, Comparator.comparing((Thread t) -> t.memblck).thenComparing(t -> t.time));
/*start from second thread till last thread*/
for (int i = 1; i < arr.length; 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') {
System.out.println("threads " + arr[j].id + " and "
+ arr[i].id + " conflict.");
}
j--;
}
}
}
}
System.out.println("All other operations are same");
}
// Driver program to test above function
public static void main(String[] args) {
Thread arr[] = { new Thread(1, 512, 1, 'R'), new Thread(2, 432, 2, 'W'),
new Thread(3, 512, 3, 'R'), new Thread(4, 932, 4, 'R'),
new Thread(5, 512, 5, 'W'), new Thread(6, 932, 6, 'R'),
new Thread(7, 835, 7, 'R'), new Thread(8, 432, 8, 'R')
};
printConflicts(arr);
}
}
# Importing required libraries
from typing import List, Tuple
from operator import itemgetter
# Function to print all conflicts among threads
def print_conflicts(arr: List[Tuple[int, int, int, str]]) -> None:
# Sort the threads first by memblock, then by time
arr.sort(key=itemgetter(1, 2))
# Start from second thread till last thread
for i in range(1, len(arr)):
# As threads are sorted, We check further for conflict possibility only if their memblock is same
if arr[i][1] == arr[i-1][1]:
# 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][2] <= arr[i-1][2] + 5:
j = i - 1 # start with previous thread
# Find all previous conflicting threads
while arr[i][1] == arr[j][1] and arr[i][2] <= arr[j][2] + 5 and j >= 0:
if arr[i][3] == 'W' or arr[j][3] == 'W':
print(f"threads {arr[j][0]} and {arr[i][0]} conflict.")
j -= 1
print("All other operations are same")
# Driver program to test above function
if __name__ == "__main__":
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')]
print_conflicts(arr)
// Class for details of thread
class Thread {
// Constructor
constructor(id, memblck, time, access) {
this.id = id;
this.memblck = memblck;
this.time = time;
this.access = access;
}
}
// Function to print all conflicts among threads
function printConflicts(arr) {
/* Sort the threads first by memblock, then by
time */
arr.sort((a, b) => a.memblck - b.memblck || a.time - b.time);
/*start from second thread till last thread*/
for (let i = 1; i < arr.length; 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) {
let 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') {
console.log("threads " + arr[j].id + " and "
+ arr[i].id + " conflict.");
}
j--;
}
}
}
}
console.log("All other operations are same");
}
// Driver program to test above function
let arr = [ new Thread(1, 512, 1, 'R'), new Thread(2, 432, 2, 'W'),
new Thread(3, 512, 3, 'R'), new Thread(4, 932, 4, 'R'),
new Thread(5, 512, 5, 'W'), new Thread(6, 932, 6, 'R'),
new Thread(7, 835, 7, 'R'), new Thread(8, 432, 8, 'R')
];
printConflicts(arr);
Output:
threads 3 and 5 conflict.
threads 1 and 5 conflict.
All other operations are same
Time complexity: The above solution uses sorting to sort threads. Sorting can be done in O(nLogn) time. Then it prints all conflicts. Printing all conflicts takes O(n + m) time where m is number of conflicts. So overall time complexity is O(nLogn + m).