리소스 충돌을보고하기위한 데이터 구조를 디자인하십시오.

Question

1024 개의 주소가있는 메모리 주소 풀이 있습니다. 읽기 또는 쓰기 작업을 수행하는 메모리 위치에 액세스하는 프로그램 내부에서 16 개의 스레드가 실행됩니다.

예 Q1 = (12,578, R (읽기/쓰기, 시간이 메모리 어드레스를 나사)이 프로그램의 출력은 4 배 defn이이

쿼드 러플 Q1처럼 일련의 형태 인 , 2t), q2 = (16,578, w, 6t)

quadruples의 스트림을 입력으로 사용하고 2 개 이상의 스레드가 동일한 메모리 자원에 액세스하려고 할 때 발생하는 모든 충돌을보고하는 프로그램을 설계하려고합니다 적어도 하나의 기록 동작으로 5 초 간격으로 기록된다.

나는 여러 가지 해결책을 가지고 있지만이 문제를 해결할 수있는 최선의 방법인지 잘 모르겠습니다. 나는 디자인과 데이터 구조의 관점에서 해결책을 찾고있다.

Answer 1

여기에서 기본적인 문제는 충돌 감지입니다. 필자는 일반적으로 어떤 종류의 연관 컬렉션에 요소가 추가되는 솔루션을 찾습니다. 새로운 요소가 추가 되려고 할 때 콜렉션에 충돌을 나타내는 유사한 요소가 이미 있는지 여부를 알 수 있어야합니다. 여기에서는 STL 멀티 맵과 같은 중복 요소를 허용하는 컬렉션 유형이 필요할 것으로 보입니다. Quadraple (quadruple?)은 분명히 연관 컬렉션의 값 유형이되며 키 유형은 두 요소가 충돌, 즉 메모리 주소 및 시간을 나타내는 지 여부를 결정하는 데 필요한 데이터를 포함합니다. STL 멀티 맵과 같은 표준 연관 컬렉션을 사용하려면 키 유형에 대해 연산자 <을 정의하여 키에 대한 순서를 정의해야합니다 (여기서는 C++이라고 가정하고 지정하지 않았습니다). 충돌을 메모리 위치가 동일하고 시간 값이 일부 임계 값보다 작은 두 요소로 정의합니다. 키 유형의 순서는 충돌을 나타내는 두 개의 키가 순서에 따라 동등한 값을 가져야합니다. 이 디자인에 문제가

bool operator<(Key const& a, Key const& b) { 
    if (a.address == b.address) { 
     if (abs(a.time - b.time) < threshold) { 
      return false; 
     } 
     return a.time < b.time; 
    } 
    return a.address < b.address; 
} 

인해에있어서 : < B가 거짓이며 오더링이 오퍼레이터에 의해 정의 될 수 있도록, B <가이 아니라 거짓으로 < 연산자 하에서 동등한 표현되는 사실 두 개의 키가 같지 않고 <에서 동일 할 수 있습니다. 즉, 다른 두 개의 유사한 Quadraples, 즉 서로 충돌하는 두 개의 값이 같은 키 아래에 저장됩니다. 당신이 그들을 찾을 수있을 것입니다, 그래서 당신은 쉽게, 정렬 연관 컨테이너에 인접한 (하지만 서로 다른 키에서) 결국 요소를 충돌이 순서 정의의 밑에 주문

bool operator<(Key const& a, Key const& b) { 
    if (a.address == b.address) { 
     return a.time < b.time; 
    } 
    return a.address < b.address; 
} 

의 간단한 정의를 사용할 수 있습니다 그것들이 모두 컬렉션에 추가 된 후 사후 처리 단계.