문제 개요
RAM이 블록 단위로 구성되어 있고, 시스템에서는 여러 프로세스가 동시에 실행되고 있다고 가정해 보겠습니다. 각 프로세스는 다음과 같은 형식의 메모리 접근 정보를 가집니다.
(스레드 T, 메모리 블록 M, 시간 t, R/W)
이 정보는 스레드 T가 시간 t에 메모리 블록 M에 접근했으며, 해당 연산이 읽기(R) 또는 쓰기(W) 중 하나였음을 의미합니다.
메모리 충돌 판정 조건
- 같은 메모리 위치에서 여러 스레드가 동시에 읽기(R) 연산을 수행하는 것은 충돌이 아닙니다.
- 어떤 스레드가 시간 x에 메모리 블록 M에 접근할 때, 시간 범위 [x−5, x+5] 안에 해당 위치에 대한 쓰기(W) 연산이 수행되면 충돌로 간주합니다.
예를 들어, 스레드 T1이 시간 x+1에 메모리 위치 M에 접근했고, 스레드 T2가 시간 x+6 이전에 같은 위치에 접근했다면, 두 스레드 중 하나라도 쓰기 연산을 수행하는 경우 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)이며, 나머지 연산들은 서로 충돌하지 않습니다.
해결 접근 방법
이 문제는 다음 단계를 통해 해결할 수 있습니다.
- Thread 클래스 생성: id(스레드 식별자), memory_block(메모리 블록), time(접근 시간), operation(연산 종류) 네 가지 필드를 가진 Thread 클래스를 정의합니다.
- 배열 정렬: th_arr 배열을 메모리 블록 기준으로 오름차순 정렬하고, 메모리 블록이 동일한 경우에는 시간 순으로 정렬합니다. 이렇게 하면 같은 블록에 접근한 기록들이 인접하게 배치됩니다.
- 충돌 검사: i를 1부터 n−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부터 시작하여, 같은 메모리 블록이면서 시간 차이가 5 이내인 모든 이전 항목을 역방향으로 검사합니다.
- 검사 과정에서 두 연산 중 하나라도 'W'(쓰기)라면 해당 스레드 쌍을 충돌로 출력합니다.
이 알고리즘의 시간 복잡도는 정렬 단계에서 O(n log n)이며, 충돌 검사 단계는 최악의 경우 O(n²)까지 증가할 수 있습니다. 다만 실제 환경에서는 특정 시간 창(±5) 안에 접근하는 기록이 많지 않기 때문에 대부분 효율적으로 동작합니다.
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]
결과 분석
실행 결과를 살펴보면, 스레드 2가 시간 2에 메모리 블록 512에 대해 쓰기(W) 연산을 수행했습니다. 이후 스레드 4(시간 4)와 스레드 6(시간 6)이 같은 블록 512에 읽기(R) 연산으로 접근했는데, 시간 차이가 각각 2와 4로 모두 5 이내이므로 두 쌍 모두 충돌로 판정된 것입니다. 반면 스레드 1과 3은 블록 932에 대해 모두 읽기 연산만 수행했기 때문에 충돌로 처리되지 않습니다.