공유 트리 데이터 구조에서 스레드 동기화를 어떻게 처리해야합니까?

Question

이 단지 동시성 재교육의 종류입니다 ...

I 메모리에서 B + 트리 데이터 구조가 상상 - 노드 당 여러 항목을 만 리프 노드 항목을 포함, 리프 노드는 쉽게 순차적에 대한 링크 목록을 형성 접속하다. 삽입 및 삭제는 대부분 리프 노드에만 영향을 미치지 만 노드가 루트로 전파 될 수있는 프로세스에서 분할되거나 병합 될 수 있습니다.

단일 스레드 구현이 있으며 업데이트는 일종의 사전 계획 방식을 따릅니다. 재귀는 노드가 변경해야하는 한 리프 수준에서 트리를 올라가 필요한 변경 사항을 설명하는 링크 된 목록 (다른 재귀에서 로컬 변수 연결)을 작성합니다. 필요한 것을 알고있을 때 필요한 모든 노드를 할당 할 수 있는지 여부를 확인하고 재귀에서 빠져 나가기 전에이 계획을 참조하여 필요한 모든 변경 사항을 적용할지 여부를 결정할 수 있습니다. 반복자는 삽입에 의해 무효화되지 않도록

이 구현은 그들이 가리키는 특정 항목을 삭제하는 않는 한 삭제/업데이트에 반복자를 "유지". 동일한 노드 내에서 삽입/삭제하면 해당 노드를 가리키는 반복자가 업데이트됩니다. 한 번에 잠재적으로 많은 독자와 작가를 지원하는 -

문제는, 나는 그것이 멀티 스레드 할 필요가있다.

나는 여러 독자가 너무 오래 결과로 손상의 위험이 없기 때문에, 읽고 동시에 쓸 수 있어야합니다. 그래서 독서를 위해, 나는 심지어 독점 노드에 대해서도 상호 배타적 인 접근을 원하지 않는다. 필자는 변경에 필요한 최소 수의 노드를 잠급니다. 물론 교착 상태는 피하고 싶습니다.

다행히, 내가 실제로해야 할 일이 아니다 -하지만 난 내 동시성 능력을 무시 했으므로, 이것은 단지 좋은 사고 실험처럼 보인다.

이것은 데이터베이스 및 파일 시스템이 처리 할 수있는 문제의 종류에 분명 유사하다, 그래서 내가 좋은 것 그런 종류의, 일부 참조를 얻을 수 있습니다 같은데요.

그래서 어떻게 스레드 동기화를 처리 할 수 ​​있습니까? 노드에서 뮤텍스 및/또는 세마포를위한 역할을 막연하게 볼 수는 있지만이를 사용하기 위해 어떤 전략을 사용합니까?

Answer 1

확실히 도전 과제! 나는 당신이 C++ 프로그래머임을 알지만, C++에서 자바와 비슷한 개념이 있으며 자바 관점에서 도움을 얻을 것이라고 믿습니다.

그래서 읽기, 심지어 단일 노드

당신이하는 ReadWriteLock를 사용할 수에 전혀 상호 배타적 인 접근을 원하지 않는다. 라이터가없는 한, 복수의 리더 thread에 의해 동시에 보관 유지됩니다. 쓰기 잠금은 독점적입니다. 글쓰기를 할 때 독점적 인 접근 만하면됩니다. C++에서 아날로그가 있습니까?

와 나는 물론, 교착 상태를 피하려고.

여러 노드를 레벨 순서 (예 : 위에서 아래로)로 고정하면됩니다. 그렇게하면 교착 상태로부터 보호받을 수 있습니다 (Lamport의 Bakery Algorithm과 비슷한).

데이터베이스의 경우 : 하나의 프로세스를 죽여 교착 상태를 해결합니다 .-).주문을 잠금 장치가있는 것은이입니다