잠금(대기)이 없는 이중 연결 목록이 가능합니까?
https://stackoverflow.com/questions/849786
-
21-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
C# 태그로 이런 질문을 하는데, 가능하다면 어떤 언어에서도 가능해야 합니다.
대기하지 않는 잠금을 제공하기 위해 Interlocked 작업을 사용하여 이중 연결 목록을 구현할 수 있습니까?기다리지 않고 삽입하고 추가하고 제거하고 지우고 싶습니다.
해결책
간단한 Google 검색은 많은 잠금이없는 이중 연결 목록 용지를 공개합니다.
그러나 원자 CA (비교 및 스왑)를 기반으로합니다.
C#의 운영이 얼마나 원자력인지는 모르겠지만이 웹 사이트에 따르면
http://www.albahari.com/threading/part4.aspx
C# 운영은 32 비트 필드를 읽고 쓰는 데 원자력으로 보장됩니다. CAS에 대한 언급이 없습니다.
다른 팁
예, 가능합니다. STL과 유사한 구현은 다음과 같습니다. 잠금 없는 이중 연결 목록 C++에서.
목록에서 무작위로 작업을 수행하기 위해 스레드를 생성하는 샘플 코드
ABA 문제 없이 작동하려면 64비트 비교 및 교환이 필요합니다.이 목록은 다음 때문에 가능합니다. 잠금 없는 메모리 관리자.
확인해 보세요 12페이지의 벤치마크.목록의 성능은 경합이 증가함에 따라 스레드 수에 따라 선형적으로 확장됩니다.알고리즘은 분리된 액세스에 대한 병렬성을 지원하므로 목록 크기가 증가하면 경합이 줄어들 수 있습니다.
여기에는 종이 잠금이 없는 이중 연결 목록을 설명합니다.
우리는 분리 할 수있는 접근 가능하고 현대 컴퓨터 시스템에서 사용할 수있는 원자 프리미티브를 사용하는 동시 디크의 효율적이고 실용적인 잠금 장치 구현을 제시합니다.Deques의 이전에 알려진 잠금 알고리즘은 이용할 수없는 원자 동기화 프리미티브를 기반으로하거나 기능의 하위 집합 만 구현하거나 분리 액세스를 위해 설계되지 않았습니다.우리의 알고리즘은 이중 링크 된 목록을 기반으로하며 단일 단어 비교 및 스웨이 만 필요합니다 ...
Ross Bencina는 "에 대한 수많은 논문과 소스 코드 예제가 포함된 정말 좋은 링크를 방금 찾았습니다.잠금 없음 및 대기 없음 알고리즘에 대한 몇 가지 참고 사항".
한 번에 여러 참조를 설정해야 하고 연동 작업의 성능이 제한되어 있기 때문에 이것이 가능하다고 생각하지 않습니다.
예를 들어, 추가 작업을 수행합니다. A와 C 사이에 노드 B를 삽입하는 경우 하나의 원자적 작업에서 B->next, B->prev, A->next 및 C->prev를 설정해야 합니다.Interlocked에서는 처리할 수 없습니다.B의 요소를 미리 설정하는 것은 도움이 되지 않습니다. "B"를 준비하는 동안 다른 스레드가 삽입을 결정할 수 있기 때문입니다.
이 경우에는 잠금을 제거하는 것이 아니라 잠금을 최대한 세밀하게 만드는 데 더 집중하겠습니다.
각주 읽기 - VS2010의 최종 릴리스 전에 4.0에서 ConcurrentLinkedList를 끌어 올릴 계획입니다.
글쎄, 당신은 실제로 그것을하는 방법을 묻지 않았습니다. 그러나 C#에서 원자 CA를 수행 할 수 있다면 전적으로 가능합니다.
사실 저는 지금 C ++에서 이중 링크 된 대기 무료 목록의 구현을 통해 노력하고 있습니다.
여기에 설명하는 논문이 있습니다.http://www.cse.chalmers.se/~tsigas/papers/haakan-thesis.pdf
그리고 당신에게 몇 가지 단서를 제공 할 수있는 프레젠테이션.http://www.ida.liu.se/~chrke/courses/multi/slides/lock-free_doublylinkedlist.pdf
잠금 무료 알고리즘을 작성할 수 있습니다 모두 대부분의 아키텍처에서 복사 가능한 데이터 구조 [1]. 그러나 효율적인 글을 쓰는 것은 어렵습니다.
나는 썼다 구현 의 Håkan Sundell과 Philippas Tsigas의 잠금없는 이중 링크 목록 .NET의 경우. 개념으로 인해 원자 포수를 지원하지는 않습니다.
[1]: Maurice Herlihy : 대기중인 chronization의 불가능과 보편성 결과 (1988)
나는 대답이 매우 깊은 자격을 갖춘 "예, 그것은 가능한, 그러나 어려운 ". 당신이 요구하는 것을 구현하려면, 당신은 기본적으로 충돌을 보장하기 위해 운영을 함께 컴파일하는 무언가가 필요할 것입니다. 따라서 그 목적을 위해 일반적인 구현을 만드는 것은 매우 어려울 것입니다. 여전히 중요한 제한 사항이있을 것입니다. 정확한 요구에 맞는 특정 구현을 만드는 것이 더 간단 할 것입니다. 심지어는 "단순한"것이 아닙니다.
