หา Memory Conflicts ระหว่าง Multiple Threads ใน C++

สมมติมี RAM จัดเป็นบล็อก มีหลายโปรเซสทำงาน แต่ละ Thread ได้ข้อมูล: (Thread T, Memory Block M, Time t, R/W) แสดงว่า Thread T เข้าถึงบล็อก M เวลา t ด้วยการอ่าน (R) หรือเขียน (W)

เงื่อนไข Conflict

• หลายการอ่าน (Read) ตำแหน่งเดียวกัน → ไม่ใช่ Conflict
• การเขียน (Write) ระหว่างเวลา x-5 ถึง x+5 ของบล็อก M → เป็น Conflict กับ Thread อื่นที่เข้าถึง M ที่เวลา x (ถ้ามีอย่างน้อย 1 ตัวเป็น Write)

เช่น Thread T1 เข้าถึง M เวลา x+1, Thread T2 เข้าถึง M ก่อน x+6 → Conflict ถ้ามีการ Write

อัลกอริทึม

1. สร้างโครงสร้าง Thread: id, memory_block, time, operation
2. เรียงอาร์เรย์ theo memory_block, แล้วค่อย time
3. วนลูป i=1 ถึง n-1:
   • ถ้า memory_block[i] == memory_block[i-1] และ time[i] ≤ time[i-1] + 5:
   • วนย้อนหลัง j=i-1 ลงมา ตรวจสอบเงื่อนไขเดียวกัน
   • ถ้า operation[i]=='W' หรือ operation[j]=='W' → รายงาน Conflict

โค้ดตัวอย่าง

#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;
    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 (j >= 0 && th_arr[i].memory_block == th_arr[j].memory_block && th_arr[i].time <= th_arr[j].time + 5) {
                    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);
}

ผลลัพธ์

Conflicting threads [2, 4]
Conflicting threads [2, 6]

คำอธิบาย: Thread 2 เขียน (W) ที่บล็อก 512 เวลา 2, Thread 4 อ่าน (R) บล็อก 512 เวลา 4 (ต่าง 2 ≤ 5) → Conflict, Thread 6 อ่าน (R) บล็อก 512 เวลา 6 (ต่าง 4 ≤ 5) → Conflict