단독 링크드리스트 삽입 동기

Question

가정하자 I가 (K < < N)의 각 일부를 삽입하려는 어떠한 중복 함유하지 N 정수 및 K 스레드 정렬 단독 링크드리스트 정수 (헤드 노드보다 큼)를 목록에 추가합니다.

것이 가능 그러한리스트로 삽입을 동기화되도록 :

는

• 스레드 만의 (즉시) 이전 노드에 대한 액세스를 차단할 수
  
• (이하 "전리스트"잠금 없음) 가장 O (K) 뮤텍스와 조건 변수 없음 선점/인터럽트

발생할 수 없다

사용될 수있다?

Answer 1

첫 번째로 컬렉션에 삽입하는 것이 매우 드문 경우지만 링크 된 목록은 큰 해결책이 아닙니다. 삽입 지점을 찾는 것이 정렬 된 목록에서도 O(N) 작업이기 때문에 나쁘게 스케일링을 끝내기. cur

새 노드를 작성,

1. 찾기 삽입 지점 :

   당신은 아직도 그것을 할 필요가 있다면, 그것은 몇 가지주의, 잠금없는 작업으로 정렬 된 목록으로 (삭제 달리) 삽입을 수행하는 것이 가능

2. 원자 연산 (cur/cur->next에 이전/다음 링크를 할당) : compare_and_swap(cur->next, new, new->next);
   실패 할 경우 그렇지 if (new->value == next->value) return; // someone beat us to it
   : cur = cur->next 그리고 춤을 반복한다 (목록은 정렬된다. 우리 앞에 삽입 된 누군가)

즉. 새 노드를 연결하려는 시도의 결과는 우리가 성공했거나 누군가가 같은 노드를 삽입하는 것입니다 (이 경우 이미 이미 존재합니다). 또는 누군가가 갭에 삽입되었습니다. N, N+3, N+1을 시도한 사람, 다른 사람이 성공한 사람 N+2) 성공할 때까지 또는 다른 사람이 수행 한 '우리'노드를 찾으면 다시 시도합니다.

삭제를 동기화하는 것이 훨씬 어렵습니다. 그것을위한 RCU (Read-Copy-Update)를 찾는다.