소프트웨어 트랜잭션 메모리를 어떻게 구현합니까?

Question

실제 저수준 원자 명령 및 메모리 펜스(사용되는 것으로 가정) 측면에서 STM을 어떻게 구현합니까?

나에게 신비한 부분은 임의의 코드 덩어리가 주어지면 나중에 돌아가서 각 단계에서 사용된 값이 유효한지 확인할 수 있는 방법이 필요하다는 것입니다.어떻게 그렇게 하고, 어떻게 효율적으로 할 수 있나요?이는 또한 다른 '잠금' 솔루션과 마찬가지로 중요한 섹션을 가능한 한 작게 유지하려는(충돌 가능성을 줄이기 위해) 제안하는 것처럼 보입니다. 맞습니까?

또한 STM은 단순히 "계산이 실행되는 동안 다른 스레드가 이 영역에 들어왔으므로 계산이 유효하지 않습니다"를 감지할 수 있습니까? 아니면 실제로 클로버링된 값이 사용되었는지 여부를 감지할 수 있습니까(따라서 운 좋게도 때때로 두 스레드가 동일한 중요 섹션을 실행하지 않고 동시에 실행할 수 있습니다) 롤백이 필요합니까?)

Answer 1

가장 간단한 대답은 "의존적"입니다. 상상할 수있는 거의 어떤 방식 으로든 근본적으로 다른 구현이 많이 있습니다.

나에게 신비한 부분은 임의의 코드 덩어리가 주어지면 나중에 돌아가서 각 단계에 사용 된 값이 유효한지 확인하는 방법이 필요하다는 것입니다. 어떻게 그렇게하고 어떻게 효율적으로 수행합니까?

한 가지 해결책은 버전 작성을 사용하는 것입니다. 객체가 수정 될 때마다 버전 번호가 업데이트됩니다. 트랜잭션이 실행되는 동안 액세스 된 각 객체의 버전을 검증하고 트랜잭션이 커지면 객체가 아직 유효한. 이 검증은 간단한 정수 비교가 될 수 있습니다 ( transaction_start_version >= object_version, 객체가 유효하므로) 상당히 효율적으로 수행 할 수 있습니다.

이것은 또한 다른 '잠금'솔루션과 마찬가지로 중요한 섹션을 최대한 작게 유지하려는 것 같습니다 (충돌 가능성을 줄이기 위해).

가능성이 매우 높다. 몇 가지 구현이 가정/요구의 경로가되었다고 생각합니다. 모든 것 거래가되지만, 대부분의 구현에서 트랜잭션은 특별히 코드 덩어리가 표시되고 거래가 더 길수록 거래가 롤백 될 수있는 충돌 가능성이 커집니다.

또한 STM은 단순히 "계산이 실행되는 동안 다른 스레드 가이 영역에 입력 했으므로 계산이 유효하지 않습니다"를 감지 할 수 있습니까? 또는 실제로 클로버 값이 사용되었는지 여부를 실제로 감지 할 수 있습니다 (따라서 운 좋게도 두 개의 스레드가 동시에 동시에 실행될 수 있습니다. 롤백 필요)?

후자의. TM의 아이디어는 보호하는 것입니다. 데이터,보다는 암호.

다른 코드 경로는 다른 트랜잭션에서 동일한 변수에 액세스 할 수 있습니다. 이것은 TM 시스템에 의해 감지되어야합니다. "이 영역"이라는 진정한 개념은 없습니다. 이는 데이터보다는 코드를 지칭하기 때문입니다. TM 시스템은 실행중인 코드를 신경 쓰지 않으며 수정중인 데이터를 추적합니다. 그런 식으로, 그것은 결정적인 섹션과는 전혀 다릅니다 (데이터보다는 코드를 보호하는).

Answer 2

일부 논문은 실제로 읽기가 어려울 수 있지만 매우 명확하고 간결한 두 가지는 다음과 같습니다.

거래 잠금 II, Dave Dice, Ori Shalev, Nir Shavit "TL2"STM 알고리즘을 모든 언어로 설명합니다.

듀스 : Java, Guy Korland, Nir Shavit, Pascal Felber의 비 침습적 소프트웨어 트랜잭션 메모리 이는 일반 Java 클래스를 STM을 수행하기 위해 추가 바이트 코드를 갖는 메모리 클래스로 변환하는로드 타임 클래스 변압기를 설명합니다. 이 논문은 STM이없는 코드가 모든 OO 언어로 STM을 수행하는 코드로 기계적으로 변환 할 수있는 방법을 설명 하듯이 질문과 관련이 있습니다.

듀스 프레임 워크를 사용하면 사용하려는 실제 알고리즘을 플러그인 할 수 있습니다. TL2 알고리즘 포함. 듀스 프레임 워크가 Java이므로 다음 토론은 Java 용어를 사용하지만 OO 언어로 작성한다고 가정합니다.

아래는 TL2 접근법을 간략하게 설명합니다. 이 논문은 대체 접근 방식과 관련이 있지만 하나의 알고리즘을 연구하면 많은 질문에 답변합니다.

STM을 어떻게 구현합니까? 나에게 신비한 부분은 임의의 코드 덩어리가 주어지면 나중에 돌아가서 각 단계에 사용 된 값이 유효한지 확인하는 방법이 필요하다는 것입니다.

TL2가 STM을 수행하는 방법에 대한 짧은 대답 중 하나는 "부기"이며 커밋 시간에 쓰기 잠금 장치 만 사용합니다. 세부 사항은 용지를 읽지 만 보드 브러시 개요는 다음과 같습니다. 원래 코드에서 사용할 수있는 모든 속성에는 getter and setter가 있습니다. 변환 된 코드에는 속성의 버전 번호와 Getter 및 Setter에 추가 된 추가 코드가 있습니다. 트랜잭션 내에서 읽은 모든 속성의 버전을 트랜잭션 "읽기 세트"로 기록해야합니다. 모든 getter가 보이는 속성의 버전을 ThreadLocal LinkedList에 추가하도록하여이를 수행 할 수 있습니다. 또한 저지 할 때까지 쓰기를 Threadlocal에서 "쓰기 세트"로 버퍼링해야합니다. Getter 메소드는 주어진 필드가있는 경우 주어진 필드에 대해 ThreadLocal 쓰기 세트 값을 확인하고 반환해야합니다. 그렇게하면 당신은 당신의 커밋되지 않은 쓰기가 당신의 읽기에서 보이지만 당신이 커밋 할 때까지 다른 스레드는 그것들을 볼 수 없습니다.

커밋시기에 당신은 당신이 쓰려는 모든 속성에 대해 쓰기 잠금을 취합니다. 잠금 장치가있는 동안 읽기 세트가 여전히 유효한지 다시 확인하십시오. 트랜잭션에서 읽은 속성이 다른 트랜잭션으로 더 높은 버전으로 업데이트되지 않았습니다. 그렇다면 일관성이없는 읽기가있을 수 있으므로 비즈니스 로직이 유효하지 않을 수 있으므로 전체 트랜잭션을 롤백해야합니다. 최종 검사가 통과되면 쓰기 세트를 플러시하여 커밋하고 해당 속성의 버전을 부딪 히고 쓰기 잠금을 해제하며 쓰기 세트 및 읽기 세트 스레드 Local 목록을 최종 지우십시오.

이 논문은 TX가 시작된 이후로 읽는 속성이 작성되었음을 감지하면 알고리즘이 조기에 중단 될 수 있다고 설명합니다. 이 논문에는 읽기 전용 거래 속도를 높이기위한 몇 가지 깔끔한 트릭이 있습니다. 심지어 어떤 블록이 읽기 전용이고 읽기 쓰기가 있는지 알아내는 트릭도 있습니다. 그러한 것들에 관심을 표명하는 사람은 실제로 두 논문을 즐기어야합니다.

위의 논문의 듀스 프레임 워크는로드 타임에 새로운 Java 바이트 코드를 클래스에 주입하여 모든 게터와 세터를 변경하는 방법을 보여줍니다. 다른 언어에는 정상 코드를 STM 활성화 코드로 동일한 기계적 변환을 수행하는 특수 컴파일러 또는 전처리 기가있을 수 있습니다. 구체적으로 소스 코드 객체는 간단한 getter setter 쌍을 가질 수 있지만 런타임에 변환 된 클래스에는 책장을 수행하는 getter 세터가 풍부합니다.

일반 코드를 STM 코드 (특히 런타임에)로 변환하는 것은 흥미롭지 만 실제로 STM 활성화 데이터 구조를 작성 해야하는 경우 매직 소스가 필요하지 않습니다. 대신 a를 만듭니다 Ref a get() 그리고 a set(x) 그리고 데이터 구조 객체 사이의 모든 단일 관계를 구성합니다. Ref 손잡이. 에서 get 그리고 set 당신의 Ref 클래스 threadLocal Bookwork를 수행 할 수 있습니다. 그런 다음 간단한 버전의 "TL2"또는 데이터 구조에 적합한 다른 알고리즘과 읽기 대 쓰기의 동시성을 구현할 수 있습니다.

이것은 또한 다른 '잠금'솔루션과 마찬가지로 중요한 섹션을 최대한 작게 유지하려는 것 같습니다 (충돌 가능성을 줄이기 위해).

TL2는 쓰기 잠금 장치를 보유하고 최종 확인 및 쓰기를 수행하는 데 중요한 기간이있어 응용 프로그램 비즈니스 로직을 이해하지 않고 이해하고 최적화하기 쉬운 쓰기입니다. 각 숫자에 고유 한 속성을 할당하면 오름차순 순서로 잠금을 취하여 교착 상태를 피할 수 있습니다. 커밋 수표가 통과 될 것이라고 가정 할 때 모든 비즈니스 로직이 수행된다는 점에 유의해야합니다. 임의의 느린 비즈니스 로직을 수행하는 동안 자물쇠를 보유하지 않습니다. 여러 웹 서비스 조회 또는 느린 데이터베이스 호출을 수행 할 수 있으며 커밋까지 잠금 장치를 사용하지 않습니다. 분명히 전문가들은 일반적인 비판적 섹션에서 도대체를 조정할 것입니다.

이 논문은 알고리즘이 특정 비즈니스 논리에 필요한 경우 더 자주 중단 될 수 있음을 분명히합니다. 일반 알고리즘은 특정 더러운 판독 값이 실제 쓰기 결과에 영향을 미치지 않는지 알지 못합니다. 실제 비즈니스 로직을 이해하는 필기 논리는 주어진 더러운 읽기 세트에 롤백이 필요하지 않은 경우 특별한 경우를 알 수 있습니다. 그러나 쓸 코드가 많고 롤백 가능성이 매우 낮은 응용 프로그램이 있다면 일반적인 기계적 STM 접근 방식은 버그가 줄어들고 성능이 좋을 수 있습니다.

또한 STM은 단순히 "계산이 실행되는 동안 다른 스레드 가이 영역에 입력 했으므로 계산이 유효하지 않습니다"를 감지 할 수 있습니까? 또는 실제로 클로버 값이 사용되었는지 여부를 실제로 감지 할 수 있습니다 (따라서 운 좋게도 두 개의 스레드가 동시에 동시에 실행될 수 있습니다. 롤백 필요)?

TL2는 데이터를 읽거나 쓰여진 모든 코드에 관한 모든 방법으로 접근합니다. 그것은 당신이 얻고 설정하고 어느 정도 중요합니다. 그리고 모든 쓰기를 플러시하기 전에 다른 실이 발가락에 닿는 지 여부. 코드에 필요한 것은 당신이 begin(), commit() 그리고 rollback() 비즈니스 로직에서 거래를 시작하고 종료하고 중단합니다. 그것조차도 코드를 생성 할 수 있습니다. Java를 사용하면 메소드에 대한 @Transactional 주석으로 메소드를 표시 한 다음 Try/Commit/Rollback을 관용 Java로 수행하는 시도/캐치/마침내 메소드 호출을 래핑하는 코드를 생성 할 수 있습니다. 듀스는 클래스 하중 시간에 그러한 논리를 주입합니다.

다시 한 번 자신의 STM 활성화 데이터 구조에서 시작/커밋/롤백을 위해 마법 소스가 필요하지 않습니다. 당신은 명시 적으로 모든 것을 데이터 구조 로직 코드에 넣어 모든 OO 언어로 명시 적으로 STM 활성화 클래스를 만들 수 있습니다.

Answer 3

GHC의 STM 구현은 6 절에 설명되어 있습니다.

종합 가능한 메모리 트랜잭션. Tim Harris, Simon Marlow, Simon Peyton Jones, Maurice Herlihy. PPOPP'05 : ACM Sigplan Symposium on Parallel Programming의 원리 및 실습, 시카고, 일리노이, 2005 년 6 월

그리고 섹션 5의 :

데이터 불변량을 통한 트랜잭션 메모리. 팀 해리스, 사이먼 페이튼 존스. 2006 년 3 월 Transact '06

Answer 4

다음 프레젠테이션을 시청해 보시기 바랍니다. http://www.infoq.com/presentations/Value-Identity-State-Rich-Hickey

후반부에서는 값을 정의되지 않은 상태로 두지 않고 업데이트하는 방법을 설명합니다.예를 들어 STM 스타일로 업데이트하려는 트리가 있는 경우 이전 버전을 전혀 변경하지 않습니다.라고하자 tree 트리의 루트에 대한 포인터입니다.사용자가 생성하는 유일한 것은 변경된 노드입니다(그러나 해당 노드는 트리의 원본 스냅샷에 있는 노드를 참조할 수 있습니다).

그런 다음 비교 및 ​​교환을 수행합니다. tree 바늘.성공하면 이제 모든 사람이 새 트리를 볼 수 있으며 이전 트리는 가비지 수집될 수 있습니다.그렇지 않은 경우 프로세스를 반복하면 방금 구성한 트리가 가비지 수집됩니다.

가장 큰 아이디어는 다른 사람이 변경했는지 감지할 필요가 없다는 것입니다. tree 실제로 새 값과 이전 값을 바꿀 때까지 일반적인 멀티스레드 프로그래밍에서 "충돌"이나 "막힌 값"이 발생하지 않습니다.

Answer 5

.NET Framework를 사용하는 경우

이 실험을 확인할 수 있습니다

• .NET 4.0 stm.net
  
• .NET Rocks Podcast의 STM.NET : Dana Groff와 Yossi Levanoni Talk STM