잠금 없는 구조를 어떻게 작성할 수 있나요?

https://stackoverflow.com/questions/92455

01-07-2019
|

문제

내 멀티스레드 애플리케이션에서 잠금 경합이 심해 여러 코어에 걸쳐 확장성이 저하되는 것을 확인했습니다.나는 이 문제를 해결하기 위해 잠금 없는 프로그래밍을 사용하기로 결정했습니다.

잠금 없는 구조를 어떻게 작성할 수 있나요?

해결책

짧은 대답은 다음과 같습니다.

당신은 할 수 없습니다.

긴 대답은 다음과 같습니다.

이 질문을 하는 경우 아마도 잠금 없는 구조를 생성할 수 있을 만큼 충분히 알지 못하는 것입니다.잠금이 없는 구조를 만드는 것은 매우 어려우며 이 분야의 전문가만이 이를 수행할 수 있습니다.직접 작성하는 대신 기존 구현을 검색하세요.그것을 찾으면 그것이 얼마나 널리 사용되는지, 얼마나 잘 문서화되어 있는지, 잘 입증된 경우 제한 사항은 무엇인지 확인하십시오. 심지어 다른 사람들이 게시한 일부 잠금 없는 구조도 깨졌습니다.

현재 사용 중인 구조에 해당하는 잠금 없는 구조를 찾지 못한 경우 기존 구조를 사용할 수 있도록 알고리즘을 조정하세요.

여전히 자신만의 잠금 없는 구조를 만들고 싶다면 다음을 확인하세요.

아주 간단한 것부터 시작해 보세요
대상 플랫폼의 메모리 모델 이해(읽기/쓰기 재정렬 제약 조건, 원자성 작업 포함)
잠금 없는 구조를 구현할 때 다른 사람들이 직면한 문제에 대해 많이 연구하십시오.
효과가 있을지 추측만 하지 말고 증명해 보세요.
결과를 철저히 테스트하라

더 읽어보기:

Wikipedia의 잠금 해제 및 대기 무료 알고리즘

허브 서터:잠금 해제 코드:잘못된 보안 감각

다른 팁

다음과 같은 라이브러리를 사용하십시오. 인텔의 스레딩 빌딩 블록, 여기에는 잠금이 없는 구조와 알고리즘이 많이 포함되어 있습니다.나는 실제로 잠금 없는 코드를 직접 작성하는 것을 권장하지 않습니다. 이는 오류가 발생하기 쉽고 올바르게 작성하기 어렵습니다.

스레드로부터 안전한 잠금이 없는 코드를 작성하는 것은 어렵습니다.하지만 Herb Sutter의 이 기사 시작하게 될 것입니다.

처럼 지저분한 모든 객체가 불변이고 읽기 전용이라면 잠금에 대해 걱정할 필요가 없지만 이는 객체를 많이 복사해야 할 수도 있음을 의미합니다.복사에는 일반적으로 malloc이 포함되고 malloc은 잠금을 사용하여 스레드 전체에 걸쳐 메모리 할당을 동기화하므로 불변 객체는 생각보다 적게 구입할 수 있습니다(malloc 자체는 확장이 다소 나쁘고 malloc은 느린;성능이 중요한 섹션에서 malloc을 많이 수행한다면 좋은 성능을 기대하지 마세요.)

간단한 변수만 업데이트해야 하는 경우(예:32 또는 64비트 정수 또는 포인터), 단순히 덧셈 또는 뺄셈 연산을 수행하거나 두 변수의 값을 교환합니다. 대부분의 플랫폼은 이를 위한 "원자적 연산"을 제공합니다(추가 GCC도 이러한 연산을 제공합니다). Atomic은 스레드로부터 안전한 것과 동일하지 않습니다..그러나 원자는 예를 들어 한 스레드가 64비트 값을 메모리 위치에 쓰고 다른 스레드가 그 값을 읽는 경우 읽기 작업 전이나 쓰기 작업 후에 값을 가져오지만 절대 고장난 쓰기 작업 사이의 값(예:첫 번째 32비트는 이미 새로운 값이고 마지막 32비트는 여전히 이전 값입니다!이러한 변수에 대해 원자적 액세스를 사용하지 않으면 이런 일이 발생할 수 있습니다.

그러나 업데이트하려는 값이 3개 있는 C 구조체가 있는 경우 원자성 작업으로 세 개를 모두 업데이트하더라도 이는 세 가지 독립적인 작업이므로 독자는 값 하나는 이미 업데이트되고 두 개는 업데이트되지 않은 구조체를 볼 수 있습니다. 업데이트되었습니다.여기에서 독자가 구조체의 모든 값이 이전 값이거나 새 값인지 확인해야 하는 경우 잠금이 필요합니다.

잠금 확장성을 훨씬 더 좋게 만드는 한 가지 방법은 R/W 잠금을 사용하는 것입니다.많은 경우 데이터 업데이트는 빈도가 낮지만(쓰기 작업) 데이터에 액세스하는 경우(데이터 읽기)는 매우 자주 발생합니다. 컬렉션(해시테이블, 트리)을 생각해 보세요.이 경우 R/W 잠금은 많은 스레드가 동시에 읽기 잠금을 유지할 수 있고(서로를 차단하지 않음) 한 스레드가 쓰기 잠금을 원하는 경우에만 다른 모든 스레드가 수행되므로 성능이 크게 향상됩니다. 업데이트가 수행되는 동안 차단됩니다.

스레드 문제를 방지하는 가장 좋은 방법은 스레드 간에 데이터를 공유하지 않는 것입니다.모든 스레드가 다른 스레드가 액세스할 수 없는 데이터를 대부분의 시간 동안 처리하는 경우 해당 데이터에 대한 잠금이 전혀 필요하지 않습니다(원자성 작업도 없음).따라서 스레드 간에 가능한 한 적은 데이터를 공유하도록 노력하십시오.그런 다음 실제로 필요한 경우 스레드 간에 데이터를 이동하는 빠른 방법(ITC, Inter Thread Communication)만 필요합니다.운영 체제, 플랫폼 및 프로그래밍 언어(불행히도 귀하는 이들 중 어느 것도 알려주지 않았습니다)에 따라 ITC를 위한 다양하고 강력한 방법이 존재할 수 있습니다.

마지막으로 잠금 없이 공유 데이터로 작업하는 또 다른 비결은 스레드가 공유 데이터의 동일한 부분에 액세스하지 않도록 하는 것입니다.예:두 스레드가 배열을 공유하지만 하나는 짝수 인덱스에만 액세스하고 다른 스레드는 홀수 인덱스에만 액세스하는 경우 잠금이 필요하지 않습니다.또는 둘 다 동일한 메모리 블록을 공유하고 하나는 위쪽 절반만 사용하고 다른 하나는 아래쪽만 사용하는 경우 잠금이 필요하지 않습니다.말하지는 않지만 이것이 좋은 성과로 이어질 것이라고 합니다.특히 멀티 코어 CPU에서는 그렇지 않습니다.이 공유 데이터(하나의 코어 실행)에 대한 하나의 스레드 쓰기 작업으로 인해 다른 스레드(다른 코어에서 실행)에 대해 캐시가 강제로 플러시될 수 있으며 이러한 캐시 플러시는 최신 멀티 코어 CPU에서 실행되는 멀티 스레드 애플리케이션의 병목 현상이 되는 경우가 많습니다.

내 교수("다중 프로세서 프로그래밍의 기술"의 Nir Shavit)는 수업에서 다음과 같이 말했습니다.그러지 마세요.주된 이유는 테스트 가능성입니다. 동기화 코드를 테스트할 수 없습니다.시뮬레이션을 실행할 수 있고 스트레스 테스트도 할 수 있습니다.그러나 기껏해야 대략적인 근사치입니다.실제로 필요한 것은 수학적 정확성 증명입니다.그리고 그것을 이해하는 능력은커녕 글을 쓰는 사람도 거의 없습니다.그래서 다른 사람들이 말했듯이 :기존 라이브러리를 사용합니다. 조 더피의 블로그 몇 가지 기술을 조사합니다(섹션 28).시도해야 할 첫 번째 작업은 트리 분할입니다. 더 작은 작업으로 나누고 결합하는 것입니다.

불변성은 잠금을 방지하는 한 가지 접근 방식입니다.보다 에릭 리퍼트의 토론 불변 스택 및 큐와 같은 구현.

다시.Suma의 답변인 Maurice Herlithy는 The Art of Multiprocessor 프로그래밍에서 실제로 다음과 같은 사실을 보여줍니다. 아무것 잠금 없이 쓸 수 있습니다(6장 참조).iirc, 여기에는 기본적으로 작업을 처리 노드 요소(예: 함수 클로저)로 분할하고 각 요소를 대기열에 추가하는 작업이 포함됩니다.스레드는 최신 캐시된 노드의 모든 노드를 따라 상태를 계산합니다.분명히 이는 최악의 경우 순차적 성능을 초래할 수 있지만 중요한 잠금 없는 속성을 가지고 있어 스레드가 잠금을 보유하고 있을 때 오랜 시간 동안 스레드가 예약될 수 있는 시나리오를 방지합니다.Herlithy는 또한 이론적인 대기 없는 성능을 달성합니다. 즉, 하나의 스레드가 원자 엔큐를 획득하기 위해 영원히 기다리지 않게 됩니다(이것은 매우 복잡한 코드입니다).

멀티스레드 큐/스택은 놀라울 정도로 어렵습니다. ABA 문제).다른 것들은 매우 간단할 수 있습니다.while(true) { 교체할 때까지omicCAS } 블록에 익숙해지십시오.그들은 엄청나게 강력합니다.CAS의 올바른 점에 대한 직관은 개발에 도움이 될 수 있지만 좋은 테스트와 더 강력한 도구를 사용해야 합니다(어쩌면 스케치, 다가오는 MIT 검도, 또는 회전?) 간단한 구조로 줄일 수 있다면 정확성을 확인하는 것입니다.

문제에 대해 자세히 게시해 주세요.자세한 내용이 없이는 좋은 답변을 드리기 어렵습니다.

편집하다 불변성은 좋지만 내가 올바르게 이해하고 있다면 적용 가능성이 제한됩니다.실제로 읽기 후 쓰기 위험을 극복하지는 못합니다."mem = NewNode(mem)"를 실행하는 두 개의 스레드를 고려하십시오.그들은 둘 다 me를 읽고 쓸 수 있었습니다.고전적인 증분 기능에는 적합하지 않습니다.또한 힙 할당(스레드 간에 동기화되어야 함)으로 인해 속도가 느려질 수 있습니다.

불변성은 이러한 효과를 갖습니다.개체를 변경하면 새 개체가 생성됩니다.Lisp는 내부적으로 이런 방식으로 작동합니다.

항목 13 효과적인 자바 이 기술을 설명합니다.

Cliff Click은 유한 상태 머신을 활용하여 잠금 없는 데이터 구조에 대한 주요 연구를 수행했으며 Java에 대한 많은 구현도 게시했습니다.그의 블로그에서 그의 논문, 슬라이드 및 구현을 찾을 수 있습니다. http://blogs.azulsystems.com/cliff/

이 작업 영역은 도메인 전문가 및 박사의 영역이므로 기존 구현을 사용하십시오(제대로 수행하려면!)

예를 들어 여기에 코드 라이브러리가 있습니다.

http://www.cl.cam.ac.uk/research/srg/netos/lock-free/

대부분의 잠금 없는 알고리즘이나 구조는 원자적 연산으로 시작합니다.스레드에 의해 시작된 일부 메모리 위치에 대한 변경은 다른 스레드가 동일한 작업을 수행하기 전에 완료됩니다.귀하의 환경에 그러한 작업이 있습니까?

보다 여기 이 주제에 대한 표준 논문을 참조하세요.

또한 이것을 시도하십시오 위키피디아 기사 추가 아이디어와 링크에 대한 기사.

잠금 없는 동기화의 기본 원칙은 다음과 같습니다.

구조를 읽을 때마다 읽기를 시작한 이후 구조가 변경되었는지 확인하기 위해 테스트를 통해 읽기를 추적하고, 읽는 동안 다른 일이 발생하거나 변경되지 않고 읽기에 성공할 때까지 다시 시도합니다.
구조를 변경할 때마다 알고리즘과 데이터를 정렬하여 단일 원자 단계를 수행하면 전체 변경 사항이 다른 스레드에 표시되고, 그렇지 않으면 변경 사항이 표시되지 않도록 정렬합니다. 그 조치가 취해졌습니다.해당 단계에서는 플랫폼에 존재하는 잠금 없는 원자 메커니즘을 사용합니다(예:비교 및 설정, 로드 링크+저장 조건 등).해당 단계에서는 변형 작업이 시작된 이후 다른 스레드가 객체를 변형했는지 확인하고, 그렇지 않은 경우 커밋하고, 있는 경우 다시 시작해야 합니다.

웹에는 잠금이 없는 구조의 예가 많이 있습니다.무엇을 구현하고 있는지, 어떤 플랫폼에서 구현하고 있는지에 대해 더 자세히 알지 못하면 더 구체적으로 설명하기가 어렵습니다.

멀티 코어 CPU에 대한 잠금 없는 데이터 구조를 직접 작성하는 경우 메모리 장벽을 잊지 마세요!또한 다음 사항을 고려해보세요. 소프트웨어 트랜잭션 메모리 기법.

뭐, 구조의 종류에 따라 다르지만, 발생할 수 있는 충돌을 조심스럽고 조용히 감지하고 처리할 수 있도록 구조를 만들어야 합니다.

100% 잠금이 없는 것을 만들 수 있을지는 의문이지만, 다시 말하지만 어떤 종류의 구조를 구축해야 하는지에 따라 달라집니다.

여러 스레드가 개별 항목에 대해 작업한 다음 나중에 동기화/재결합할 수 있도록 구조를 분할해야 할 수도 있습니다.

언급했듯이 실제로 어떤 유형의 구조에 대해 이야기하고 있는지에 따라 다릅니다.예를 들어 제한된 잠금 없는 대기열을 작성할 수 있지만 임의 액세스를 허용하는 대기열은 작성할 수 없습니다.

공유된 변경 가능 상태를 줄이거나 제거합니다.

Java에서는 직접 작성하는 대신 JDK 5+의 java.util.concurrent 패키지를 활용하세요.위에서 언급했듯이 이 분야는 실제로 전문가를 위한 분야이며, 1~2년의 여유 시간이 없다면 직접 운영하는 것은 선택 사항이 아닙니다.

구조가 무엇을 의미하는지 명확히 할 수 있습니까?

지금 당장은 전반적인 아키텍처를 의미한다고 가정합니다.프로세스 간에 메모리를 공유하지 않고 프로세스에 행위자 모델을 사용하여 이를 수행할 수 있습니다.

내 좀 봐 ConcurrentLinkedHashMap 링크 잠금 없는 데이터 구조를 작성하는 방법에 대한 예입니다.이는 학술 논문을 기반으로 하지 않으며 다른 사람들이 암시하는 것처럼 수년간의 연구가 필요하지 않습니다.주의 깊은 엔지니어링이 필요합니다.

내 구현에서는 버킷당 잠금 알고리즘인 ConcurrentHashMap을 사용하지만 해당 구현 세부 사항에 의존하지 않습니다.Cliff Click의 잠금 없는 구현으로 쉽게 대체될 수 있습니다.저는 Cliff의 아이디어를 빌렸지만 훨씬 더 명시적으로 사용하여 모든 CAS 작업을 상태 머신으로 모델링하는 것입니다.'ing 상태를 통해 의사 잠금이 있음을 알 수 있듯이 이는 모델을 크게 단순화합니다.또 다른 비결은 게으름을 허용하고 필요에 따라 해결하는 것입니다.역추적하거나 다른 스레드가 정리를 "도움"하도록 허용할 때 이러한 현상을 자주 볼 수 있습니다.내 경우에는 목록 중간에서 제거하는 복잡성을 처리하기보다는 목록의 죽은 노드가 헤드에 도달하면 제거되도록 허용하기로 결정했습니다.변경할 수도 있지만 역추적 알고리즘을 완전히 신뢰하지 않았으며 3노드 잠금 접근 방식을 채택하는 것과 같은 주요 변경을 미루고 싶었습니다.

"다중 프로세서 프로그래밍의 기술"이라는 책은 훌륭한 입문서입니다.하지만 전반적으로 애플리케이션 코드에서는 잠금 없는 디자인을 피하는 것이 좋습니다.종종 오류가 발생하기 쉬운 다른 기술이 더 적합한 경우 이는 단순히 과잉입니다.

잠금 경합이 발생하면 먼저 완전히 잠금이 없는 알고리즘보다는 데이터 구조에 더 세부적인 잠금을 사용하려고 합니다.

예를 들어, 저는 현재 스레드 간에 정보를 전달하기 위한 사용자 정의 메시징 시스템(각 스레드에 대한 대기열 목록, 처리할 스레드에 대한 메시지가 포함된 대기열)이 있는 다중 스레드 응용 프로그램을 작업하고 있습니다.이 구조에는 전역 잠금이 있습니다.저 같은 경우는 속도가 그다지 필요하지 않아서 크게 상관은 없습니다.그러나 이 잠금이 문제가 될 경우 예를 들어 각 대기열의 개별 잠금으로 대체할 수 있습니다.그러면 특정 대기열에 요소를 추가/제거해도 다른 대기열에는 영향을 미치지 않습니다.새 대기열 등을 추가하기 위한 전역 잠금은 여전히 존재하지만 그렇게 많이 경합되지는 않습니다.

단일 다중 생산/소비자 큐도 전역 잠금을 사용하는 대신 각 요소에 대한 세분화된 잠금을 사용하여 작성할 수 있습니다.이는 또한 경합을 제거할 수도 있습니다.

해당 주제와 관련된 여러 구현 및 논문을 읽으면 다음과 같은 공통 주제가 있음을 알 수 있습니다.

1) 공유 상태 객체는 lisp/clojure 스타일을 변경할 수 없습니다.:즉, 모든 쓰기 작업은 새 개체의 기존 상태를 복사하여 구현되고, 새 개체를 수정한 다음 공유 상태(CAS 프리미티브로 업데이트할 수 있는 정렬된 포인터에서 가져옴)를 업데이트하려고 시도합니다.즉, 현재 스레드보다 더 많이 읽을 수 있는 기존 개체를 절대로 수정하지 마십시오.불변성은 크고 복잡한 객체에 대해 Copy-on-Write 의미론을 사용하여 최적화할 수 있지만 이는 또 다른 견과류 트리입니다.

2) 현재 상태와 다음 상태 사이에 허용된 전환이 유효한지 명확하게 지정합니다.:그러면 알고리즘이 유효한지 확인하는 것이 훨씬 더 쉬워집니다.

3) 스레드당 위험 포인터 목록에서 삭제된 참조를 처리합니다..참조 객체가 안전한 후에는 가능하면 재사용하세요.

세마포어 및 뮤텍스로 구현된 일부 코드가 (부분적으로) 잠금 없는 스타일로 다시 구현된 다른 관련 게시물을 참조하세요.상호 배제 및 세마포어

라이센스 : CC-BY-SA ~와 함께 속성

제휴하지 않습니다 StackOverflow